New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows

References

• Balas E (1977) Some valid inequalities for the set partitioning problem. Hammer PL, Johnson EL, Korte BH, Nemhauser G, eds. Studies in Integer Programming, Annals of Discrete Mathematics (North-Holland, New York), 13–47.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, Mingozzi A, Roberti R (2012) Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. Eur. J. Oper. Res. 218(1):1–6.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
• 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(1):129–146.Crossref, Google Scholar
• Cordeau J, Desaulniers G, Desrosiers J, Solomon M, Soumis F (2002) VRP with time windows. Toth P, Vigo D, eds. The Vehicle Routing Problem (SIAM Monographs on Discrete Mathematics and Applications, Philadelphia), 309–324.Crossref, Google Scholar
• Desaulniers G, Desrosiers J, Spoorendonk S (2011) Cutting planes for branch-and-price algorithms. Networks 58(4):301–310.Crossref, Google Scholar
• Desaulniers G, Lessard F, Hadjar A (2008) Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows. Transportation Sci. 42(3): 387–404.Link, Google Scholar
• Desaulniers G, Madsen O, Ropke S (2014) The vehicle routing problem with time windows. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods, and Applications, MOS-SIAM Series on Optimization (SIAM, Philadelphia), 119–159.Crossref, Google Scholar
• Desrochers M, Desrosiers J, Solomon M (1992) A new optimization algorithm for the vehicle routing problem with time windows. Oper. Res. 40(2):342–354.Link, 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
• 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
• Gehring H, Homberger J (2001) A parallel two-phase metaheuristic for routing problems with time windows. Asia-Pacific J. Oper. Res. 18(1):35–47.Google Scholar
• Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. Desaulniers G, Desrosiers J, Solomon M, eds. Column Generation, Chap. 2 (Springer, New York), 33–65.Crossref, Google Scholar
• Irnich S, Desaulniers G, Desrosiers J, Hadjar A (2010) Path-reduced costs for eliminating arcs in routing and scheduling. INFORMS J. Comput. 22(2):297–313.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
• Kallehauge B, Larsen J, Madsen O (2006) Lagrangian duality applied to the vehicle routing problem with time windows. Comput. Oper. Res. 33(5):1464–1487.Crossref, Google Scholar
• Kohl N, Desrosiers J, Madsen OBG, 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
• Laporte G, Nobert Y (1983) A branch and bound algorithm for the capacitated vehicle routing problem. Operations-Research-Spektrum 5(2):77–85.Crossref, Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Lysgaard J (2003) CVRPSEP: A package of separation routines for the capacitated vehicle routing problem. Accessed May 25, 2016, http://www.asb.dk/~lys.Google Scholar
• Lysgaard J, Letchford A, Eglese R (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Programming 100(2):423–445.Crossref, Google Scholar
• Martinelli R, Pecin D, Poggi M (2014) Efficient elementary and restricted non-elementary route pricing. Eur. J. Oper. Res. 239(1): 102–111.Crossref, Google Scholar
• Pecin D, Pessoa A, Poggi M, Uchoa E (2014) Improved branch-cut-and-price for capacitated vehicle routing. Lee J, Vygen J, eds. Integer Programming and Combinatorial Optimization (Springer, Cham, Switzerland), 393–403.Crossref, Google Scholar
• Pecin D, Pessoa A, Poggi M, Uchoa E (2017a) Improved branch-cut-and-price for capacitated vehicle routing. Math. Programming Comput. 9(1): 61–100.Crossref, Google Scholar
• Pecin D, Pessoa A, Poggi M, Uchoa E, Santos H (2017b) Limited memory rank-1 cuts for vehicle routing problems. Oper. Res. Lett. 45(3): 206–209.Crossref, Google Scholar
• Pessoa A, Uchoa E, Poggi de Aragão M (2009) A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem. Networks 54(4):167–177.Crossref, Google Scholar
• Petersen B, Pisinger D, Spoorendonk S (2008) Chvátal-Gomory rank-1 cuts used in a Dantzig-Wolfe decomposition of the vehicle routing problem with time windows. Golden B, Raghavan S, Wasil E, eds. The Vehicle Routing Problem: Latest Advances and New Challenges (Springer, New York), 397–419.Crossref, Google Scholar
• Poggi de Aragão M, Uchoa E (2003) Integer program reformulation for robust branch-and-cut-and-price. Wolsey L, ed. Annals of Mathematical Programming in Rio, Búzios, Brazil, 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
• Santos H, Toffolo T, Gomes R, Ribas S (2016) Integer programming techniques for the nurse rostering problem. Ann. Oper. Res. 239(1):225–251.Crossref, Google Scholar
• Sherali H, Adams W (1990) A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3):411–430.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
• Vidal T, Crainic T, Gendreau M, Prins C (2013) A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time windows. Comput. Oper. Res. 40(1):475–489.Crossref, Google Scholar
• Wolsey L, Nemhauser G (1988) Integer and Combinatorial Optimization (John Wiley & Sons, New York).Google Scholar