A Bucket Graph–Based Labeling Algorithm with Application to Vehicle Routing

References

• Achterberg T (2007) Constraint integer programming. Unpublished doctoral dissertation, Technische Universitat, Berlin.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
• Bulhoes T, Sadykov R, Uchoa E (2018) A branch-and-price algorithm for the minimum latency problem. Comput. Oper. Res. 93:66–78.Crossref, Google Scholar
• Christofides N, Mingozzi A, Toth P (1979) The vehicle routing problem. Christofides N, Mingozzi A, Toth P, Sandi C, eds. Combinatorial Optimization (Wiley, Chichester, UK), 315–338.Google Scholar
• Christofides N, Mingozzi A, Toth P (1981) State-space relaxation procedures for the computation of bounds to routing problems. Networks 11(2):145–164.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
• Contardo C, Desaulniers G, Lessard F (2015) Reaching the elementary lower bound in the vehicle routing problem with time windows. Networks 65(1):88–99.Crossref, Google Scholar
• Cordeau JF, Laporte G (2001) A tabu search algorithm for the site dependent vehicle routing problem with time windows. Inform. Systems Oper. Res. 39(3):292–298.Crossref, Google Scholar
• Cordeau JF, Maischberger M (2012) A parallel iterated tabu search heuristic for vehicle routing problems. Comput. Oper. Res. 39(9):2033–2050.Crossref, Google Scholar
• Cordeau JF, Gendreau M, Laporte G (1997) A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks 30(2):105–119.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
• Duhamel C, Lacomme P, Prodhon C (2011) Efficient frameworks for greedy split and new depth first search split procedures for routing problems. Comput. Oper. Res. 38(4):723–739.Crossref, Google Scholar
• Fukasawa R, Longo H, Lysgaard J, Poggi de Aragão M, Reis M, Uchoa E, Werneck R (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming 106(3):491–511.Crossref, Google Scholar
• Gehring H, Homberger J (2002) Parallelization of a two-phase metaheuristic for routing problems with time windows. J. Heuristics 8(3):251–276.Crossref, Google Scholar
• Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer, Boston), 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
• Jiang J, Ng KM, Poh KL, Teo KM (2014) Vehicle routing problem with a heterogeneous fleet and time windows. Expert Systems Appl. 41(8):3748–3760.Crossref, Google Scholar
• Kallehauge B, Larsen J, Madsen OB (2006) Lagrangian duality applied to the vehicle routing problem with time windows. Comput. Oper. Res. 33(5):1464–1487.Crossref, Google Scholar
• Laporte G, Nobert Y (1983) A branch and bound algorithm for the capacitated vehicle routing problem. OR Spectrum 5(2):77–85.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
• Nagata Y, Bräysy O (2009) Edge assembly-based memetic algorithm for the capacitated vehicle routing problem. Networks 54(4):205–215.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. 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 (2017b) 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 (2017c) Limited memory rank-1 cuts for vehicle routing problems. Oper. Res. Lett. 45(3):206–209.Crossref, Google Scholar
• Penna PHV, Subramanian A, Ochi LS, Vidal T, Prins C (2019) A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet. Ann. Oper. Res. 273(1):5–74.Crossref, Google Scholar
• Pessoa A, de Aragão MP, Uchoa ME (2008) Robust branch-cut-and-price algorithms for vehicle routing problems. Golden B, Raghavan S, Wasil E, eds. The Vehicle Routing Problem: Latest Advances and New Challenges (Springer Science and Business Media, New York), 297–325.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
• Pessoa A, Uchoa E, de Aragão MP, Rodrigues R (2010) Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems. Math. Programming Comput. 2(3):259–290.Crossref, Google Scholar
• Poggi M, Uchoa E (2014) New exact algorithms for the capacitated vehicle routing problem. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods, and Applications (SIAM, Philadelphia), 59–86.Crossref, Google Scholar
• Pugliese LDP, Guerriero F (2013) A survey of resource constrained shortest path problems: Exact solution approaches. Networks 62(3):183–200.Crossref, 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
• Roberti R, Mingozzi A (2014) Dynamic ng-path relaxation for the delivery man problem. Transportation Sci. 48(3):413–424.Link, 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
• Tilk C, Rothenbächer AK, Gschwind T, Irnich S (2017) Asymmetry matters: Dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster. Eur. J. Oper. Res. 261(2):530–539.Crossref, Google Scholar
• Vanderbeck F, Sadykov R, Tahiri I (2017) BaPCod—A generic branch-and-price code. https://realopt.bordeaux.inria.fr/?page\_id=2.Google Scholar
• Vidal T, Crainic TG, 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
• 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