Improving Column Generation for Vehicle Routing Problems via Random Coloring and Parallelization

References

• Adaji A, Melin GJ, Campbell RL, Lohse CM, Westphal JJ, Katzelnick DJ (2018) Patient-centered medical home membership is associated with decreased hospital admissions for emergency department behavioral health patients. Population Health Management 21(3):172–179.Crossref, Google Scholar
• Allaoua H, Borne S, Létocart L, Calvo RW (2013) A matheuristic approach for solving a home healthcare problem. Electronic Notes Discrete Math. 41:471–478.Crossref, Google Scholar
• Alon N, Yuster R, Zwick U (1995) Color-coding. J. ACM 42(4):844–856.Crossref, Google Scholar
• Alon N, Dao P, Hajirasouliha I, Hormozdiari F, Sahinalp SC (2008) Biomolecular network motif counting and discovery by color coding. Bioinformatics 24(13):i241–i249.Crossref, Google Scholar
• American Academy of Family Physicians (2008) Joint principles of the patient-centered medical home. Delaware Medical J. 80(1):21.Google Scholar
• Bachouch RB, Guinet A, Hajri-Gabouj S (2011) A decision-making tool for home healthcare nurses’ planning. Supply Chain Forum: Internat. J. 12(1):14–20.Crossref, Google Scholar
• Baldacci R, Christofides N, Mingozzi A (2008) An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Programming 115(2):351–385.Crossref, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283.Link, Google Scholar
• Baldacci R, Bartolini E, Mingozzi A, Roberti R (2010) An exact solution framework for a broad class of vehicle routing problems. Comput. Management Sci. 7(3):229–268.Crossref, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MW, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• Bettinelli A, Ceselli A, Righini G (2011) A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows. Transportation Res. Part C: Emerging Tech. 19(5):723–740.Crossref, Google Scholar
• Braekers K, Ramaekers K, Van Nieuwenhuyse I (2016) The vehicle routing problem: State of the art classification and review. Comput. Indust. Engrg. 99:300–313.Crossref, Google Scholar
• Christofides N, Mingozzi A, Toth P (1981) Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations. Math. Programming 20(1):255–282.Crossref, Google Scholar
• Contardo C, Martinelli R (2014) A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Discrete Optim. 12:129–146.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
• Dabia S, Ropke S, Van Woensel T, De Kok T (2013) Branch and price for the time-dependent vehicle routing problem with time windows. Transportation Sci. 47(3):380–396.Link, Google Scholar
• Desaulniers G, Desrosiers J, Solomon MM (2006) Column Generation (Springer Science & Business Media, New York).Google Scholar
• Desrosiers J, Dumas Y, Solomon MM, Soumis F (1995) Time constrained routing and scheduling. Ball MO, Magnanti TL, Monma CL, Nemhauser GL, eds. Network Routing, Handbooks in Operations Research Management Science, vol. 8 (Elsevier Science, Amsterdam), 35–139.Crossref, Google Scholar
• Dohn A, Kolind E, Clausen J (2009) The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach. Comput. Oper. Res. 36(4):1145–1157.Crossref, Google Scholar
• Downey RG, Fellows MR (2012) Parameterized Complexity (Springer Science & Business Media, Berlin).Google Scholar
• Dror M (1994) Note on the complexity of the shortest path models for column generation in VRPTW. Oper. Res. 42(5):977–978.Link, Google Scholar
• Duque D, Lozano L, Medaglia AL (2015) Solving the orienteering problem with time windows via the pulse framework. Comput. Oper. Res. 54:168–176.Crossref, Google Scholar
• Eveborn P, Flisberg P, Rönnqvist M (2006) Laps care—An operational system for staff planning of home care. Eur. J. Oper. Res. 171(3):962–976.Crossref, Google Scholar
• Feillet D, Gendreau M, Rousseau L-M (2007) New refinements for the solution of vehicle routing problems with branch and price. INFOR Inform. Systems Oper. Res. 45(4):239–256.Crossref, Google Scholar
• Feillet D, Dejax P, Gendreau M, Gueguen C (2004) An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks 44(3):216–229.Crossref, Google Scholar
• Fernandez J, Blacking J, Dundes A, Edmonson MS, Etzkorn KP, Haydu GG, Kearney M, et al. (1974) The mission of metaphor in expressive culture. Current Anthropology 15(2):119–145.Crossref, Google Scholar
• Fikar C, Hirsch P (2017) Home healthcare routing and scheduling: A review. Comput. Oper. Res. 77:86–95.Crossref, Google Scholar
• Fukasawa R, He Q, Song Y (2015) A branch-cut-and-price algorithm for the energy minimization vehicle routing problem. Transportation Sci. 50(1):23–34.Link, Google Scholar
• Fukasawa R, Longo H, Lysgaard J, de Aragão MP, Reis M, Uchoa E, Werneck RF (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming 106(3):491–511.Crossref, Google Scholar
• Harris-Kojetin L, Sengupta M, Park-Lee E, Valverde R (2013) Long-term care services in the United States: 2013 overview. Vital Health Statist. Ser. 3, Analytical Epidemiological Stud. 3(37):1–107.Google Scholar
• Irnich S, Villeneuve D (2006) The shortest-path problem with resource constraints and k-cycle elimination for k≥3. INFORMS J. Comput. 18(3):391–406.Link, Google Scholar
• Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. 56(2):497–511.Link, Google Scholar
• Kohl N, Desrosiers J, Madsen OB, Solomon MM, Soumis F (1999) 2-path cuts for the vehicle routing problem with time windows. Transportation Sci. 33(1):101–116.Link, Google Scholar
• Kruskal JB (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc. 7(1):48–50.Crossref, Google Scholar
• Lanzarone E, Matta A (2014) Robust nurse-to-patient assignment in home care services to minimize overtimes under continuity of care. Oper. Res. Health Care 3(2):48–58.Crossref, Google Scholar
• Lozano L, Medaglia AL (2013) On an exact method for the constrained shortest path problem. Comput. Oper. Res. 40(1):378–384.Crossref, Google Scholar
• Lozano L, Duque D, Medaglia AL (2015) An exact algorithm for the elementary shortest path problem with resource constraints. Transportation Sci. 50(1):348–357.Link, Google Scholar
• Lysgaard J, Letchford AN, Eglese RW (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Programming 100(2):423–445.Crossref, Google Scholar
• Musich S, Wang SS, Hawkins K, Yeh CS (2015) Homebound older adults: Prevalence, characteristics, healthcare utilization and quality of care. Geriatric Nursing 36(6):445–450.Crossref, Google Scholar
• Pecin D, Contardo C, Desaulniers G, Uchoa E (2017a) New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS J. Comput. 29(3):489–502.Link, Google Scholar
• Pecin D, Pessoa A, Poggi M, Uchoa E (2014) Improved branch-cut-and-price for capacitated vehicle routing. Internat. Conf. Integer Programming Combinatorial Optim. (Springer, Basel, Switzerland), 393–403.Google Scholar
• Pecin D, Pessoa A, Poggi M, Uchoa E (2017b) Improved branch-cut-and-price for capacitated vehicle routing. Math. Programming Comput. 9(1):61–100.Crossref, Google Scholar
• Poggi de Aragao M, Uchoa E (2003) Integer program reformulation for robust branch-and-cut-and-price algorithms. Proc. Conf. Math. Program Rio: Conf. Honour Nelson Maculan, 56–61.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
• Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2):254–265.Link, Google Scholar
• Subramanian A, Uchoa E, Ochi LS (2013) A hybrid algorithm for a class of vehicle routing problems. Comput. Oper. Res. 40(10):2519–2531.Crossref, Google Scholar
• The National Association for Home Care & Hospice (2010) Basic statistics about home care. Technical report, The National Association for Home Care & Hospice, Washington, DC.Google Scholar
• Toth P, Vigo D (2014) Vehicle Routing: Problems, Methods, and Applications, vol. 18 (SIAM, Philadelphia).Crossref, Google Scholar
• Uchoa E, Pecin D, Pessoa A, Poggi M, Vidal T, Subramanian A (2017) New benchmark instances for the capacitated vehicle routing problem. Eur. J. Oper. Res. 257(3):845–858.Crossref, Google Scholar
• Vidal T, Crainic TG, Gendreau M, Lahrichi N, Rei W (2012) A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Oper. Res. 60(3):611–624.Link, Google Scholar