A Dedicated Pricing Algorithm to Solve a Large Family of Nurse Scheduling Problems with Branch-and-Price

References

• Abdallah KS, Jang J (2014) An exact solution for vehicle routing problems with semi-hard resource constraints. Comput. Industrial Engrg. 76:366–377.Crossref, Google Scholar
• Abdelghany M, Eltawil AB, Yahia Z, Nakata K (2021) A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. J. Industrial Management Optim. 17(4):2051.Crossref, Google Scholar
• Abuhamdah A, Boulila W, Jaradat GM, Quteishat AM, Alsmadi MK, Almarashdeh IA (2021) A novel population-based local search for nurse rostering problem. Internat. J. Electrical Comput. Engrg. 11(1):471.Google Scholar
• Bard JF, Purnomo HW (2005) Preference scheduling for nurses using column generation. Eur. J. Oper. Res. 164(2):510–534.Crossref, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• Beasley JE, Christofides N (1989) An algorithm for the resource constrained shortest path problem. Networks 19(4):379–394.Crossref, Google Scholar
• Bettinelli A, Ceselli A, Righini G (2014) A branch-and-price algorithm for the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows. Math. Programming Comput. 6(2):171–197.Crossref, Google Scholar
• Bolívar MA, Lozano L, Medaglia AL (2014) Acceleration strategies for the weight constrained shortest path problem with replenishment. Optim. Lett. 8(8):2155–2172.Crossref, Google Scholar
• Burke EK, Curtois T (2014) New approaches to nurse rostering benchmark instances. Eur. J. Oper. Res. 237(1):71–81.Crossref, Google Scholar
• Burke EK, Curtois T, Qu R, Vanden Berghe G (2013) A time predefined variable depth search for nurse rostering. INFORMS J. Comput. 25(3):411–419.Link, Google Scholar
• Carlyle WM, Royset JO, Kevin Wood R (2008) Lagrangian relaxation and enumeration for solving constrained shortest-path problems. Networks 52(4):256–270.Crossref, Google Scholar
• Ceschia S, Guido R, Schaerf A (2020) Solving the static INRC-II nurse rostering problem by simulated annealing based on large neighborhoods. Annals Oper. Res. 288(1):95–113.Crossref, Google Scholar
• Ceschia S, Dang N, De Causmaecker P, Haspeslagh S, Schaerf A (2019) The second international nurse rostering competition. Annals Oper. Res. 274(1–2):171–186.Crossref, Google Scholar
• Cheang B, Li H, Lim A, Rodrigues B (2003) Nurse rostering problems: A bibliographic survey. Eur. J. Oper. Res. 151(3):447–460.Crossref, Google Scholar
• Costa L, Contardo C, Desaulniers G (2019) Exact branch-price-and-cut algorithms for vehicle routing. Transportation Sci. 53(4):946–985.Link, Google Scholar
• Curtois T, Qu R (2014) Computational Results on New Staff Scheduling Benchmark Instances (ASAP Research Group, School of Computer Science, University of Nottingham, Nottingham, UK).Google Scholar
• Desaulniers G, Desrosiers J, Solomon MM (2006) Column Generation, vol. 5 (Springer Science & Business Media, New York).Google Scholar
• Dohn A, Mason A (2013) Branch-and-price for staff rostering: An efficient implementation using generic programming and nested column generation. Eur. J. Oper. Res. 230(1):157–169.Crossref, Google Scholar
• Du Merle O, Villeneuve D, Desrosiers J, Hansen P (1999) Stabilized column generation. Discrete Math. 194(1–3):229–237.Crossref, Google Scholar
• Dumitrescu I, Boland N (2003) Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem. Networks 42(3):135–153.Crossref, Google Scholar
• Gérard M, Clautiaux F, Sadykov R (2016) Column generation based approaches for a tour scheduling problem with a multi-skill heterogeneous workforce. Eur. J. Oper. Res. 252(3):1019–1030.Crossref, Google Scholar
• Gomes RA, Toffolo TA, Santos HG (2017) Variable neighborhood search accelerated column generation for the nurse rostering problem. Electronic Notes Discrete Math. 58:31–38.Crossref, Google Scholar
• Haspeslagh S, De Causmaecker P, Schaerf A, Stølevik M (2014) The first international nurse rostering competition 2010. Annals Oper. Res. 218(1):221–236.Crossref, Google Scholar
• He F, Qu R (2012) A constraint programming based column generation approach to nurse rostering problems. Comput. Oper. Res. 39(12):3331–3343.Crossref, Google Scholar
• Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. Column Generation (Springer, New York), 33–65.Crossref, Google Scholar
• Jaumard B, Semet F, Vovor T (1998) A generalized linear programming model for nurse scheduling. Eur. J. Oper. Res. 107(1):1–18.Crossref, Google Scholar
• Joksch H (1966) The shortest route problem with constraints. J. Math. Analysis Appl. 14(2):191–197.Crossref, Google Scholar
• Kohl N, Karisch SE (2004) Airline crew rostering: Problem types, modeling, and optimization. Ann. Oper. Res. 127(1–4):223–257.Crossref, Google Scholar
• Legrain A, Omer J (2023) wssuite/nursescheduler: Soft domination. Accessed January 19, 2024, https://doi.org/10.5281/zenodo.10041942.Google Scholar
• Legrain A, Omer J, Rosat S (2020) A rotation-based branch-and-price approach for the nurse scheduling problem. Math. Programming Comput. (12):417–450.Crossref, Google Scholar
• Lensing W (2020) Heuristic branch-and-price algorithms for the nurse rostering problem. PhD dissertation, Faculty of Economics and Business, University of Groningen, Groningen, Germany.Google Scholar
• Liberatore F, Righini G, Salani M (2011) A column generation algorithm for the vehicle routing problem with soft time windows. 4OR 9(1):49–82.Crossref, Google Scholar
• Maenhout B, Vanhoucke M (2010) Branching strategies in a branch-and-price approach for a multiple objective nurse scheduling problem. J. Scheduling 13(1):77–93.Crossref, Google Scholar
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2018) Automation and combination of linear-programming based stabilization techniques in column generation. INFORMS J. Comput. 30(2):339–360.Link, Google Scholar
• Qurashi AG, Taniguchi E, Yamada T (2010) Column generation-based heuristics for vehicle routing problem with soft time windows. J. Eastern Asia Soc. Transportation Stud. 8:15.Google Scholar
• Righini G, Salani M (2006) Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optim. 3(3):255–273.Crossref, Google Scholar
• Römer M (2016) Future demand uncertainty in personnel scheduling: Investigating deterministic lookahead policies using optimization and simulation. Claus T, Herrmann F, Manitz M, Rose O, eds. Proc. 30th Eur. Conf. on Modelling and Simulation (ECMS, Caserta, Italy).Google Scholar
• Santos HG, Toffolo TA, Gomes RA, Ribas S (2016) Integer programming techniques for the nurse rostering problem. Ann. Oper. Res. 239(1):225–251.Crossref, Google Scholar
• Sexton TR, Choi YM (1986) Pickup and delivery of partial loads with “soft” time windows. Amer. J. Math. Management Sci. 6(3–4):369–398.Crossref, Google Scholar
• Smet P (2018) Constraint reformulation for nurse rostering problems. Proc. 12th Internat. Conf. on the Practice and Theory of Automated Timetabling (Vienna, Austria), 69–80.Google Scholar
• Strandmark P, Qu Y, Curtois T (2020) First-order linear programming in a column generation-based heuristic approach to the nurse rostering problem. Comput. Oper. Res. 120:104945.Crossref, Google Scholar
• Tagmouti M, Gendreau M, Potvin JY (2007) Arc routing problems with time-dependent service costs. Eur. J. Oper. Res. 181:30–39.Crossref, Google Scholar
• Villeneuve D, Desaulniers G (2005) The shortest path problem with forbidden paths. Eur. J. Oper. Res. 165(1):97–107.Crossref, Google Scholar
• Zhu X, Wilhelm WE (2012) A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation. Comput. Oper. Res. 39(2):164–178.Crossref, Google Scholar