A p-Step Formulation for the Capacitated Vehicle Routing Problem

References

• Alyasiry AM, Forbes M, Bulmer M (2019) An exact algorithm for the pickup and delivery problem with time windows and last-in-first-out loading. Transportation Sci. 53(6):1695–1705.Link, Google Scholar
• Augerat P (1995) Approche polyèdrale du problème de tournées de véhicules. PhD thesis, Institut Nationale Polytechnique de Grenoble, Grenoble, France.Google Scholar
• Baldacci R, Hadjiconstantinou E, Mingozzi A (2004) An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Oper. Res. 52(5):723–738.Link, 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
• Christofides N, Eilon S (1969) An algorithm for the vehicle dispatching problem. J. Oper. Res. Soc. 20(3):309–318.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
• Desaulniers G, Desrosiers J, Solomon MM (2006) Column Generation, vol. 5 (Springer Science & Business Media, Boston).Google Scholar
• Desrochers M, Laporte G (1991) Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints. Oper. Res. Lett. 10(1):27–36.Crossref, Google Scholar
• Dollevoet TAB, Munari P, Spliet R (2020) A p-step formulation for the capacitated vehicle routing problem. Accessed November 17, 2025, https://repub.eur.nl/pub/123411/EI-2020-01.pdf.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 40(3):216–229.Crossref, Google Scholar
• Gavish B (1984) The delivery problem: New cutting plane procedures. Proc. TIMS XXVI Conf. (Copenhagen, Denmark).Google Scholar
• Godinho M, Gouveia L, Magnanti T (2008) Combined route capacity and route length models for unit demand vehicle routing problems. Discrete Optim. 5(2):350–372.Crossref, Google Scholar
• Jepsen M, Petersen B (2009) Partial path column generation for the vehicle routing problem Internat. Network Optim. Conf. (INOC) (Pisa, Italy), 1–6.Google Scholar
• Karp R (1972) Reducibility among combinatorial problems. Miller R, Thatcher J, eds. Complexity of Computer Computations (Springer, Boston), 85–103.Crossref, Google Scholar
• Laporte G, Nobert Y (1987) Exact algorithms for the vehicle routing problem. North-Holland Math. Stud. 132:147–184. Crossref, Google Scholar
• Leggieri V, Haouari M (2017) Lifted polynomial size formulations for the homogenous and heterogeneous vehicle routing problems. Eur. J. Oper. Res. 263(3):755–767.Crossref, Google Scholar
• Letchford A, Salazar-González J (2015) Stronger multi-commodity flow formulations of the capacitated vehicle routing problem. Eur. J. Oper. Res. 244(3):730–738.Crossref, 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 (2017) Improved branch-cut-and-price for capacitated vehicle routing. Math. Programming Comput. 9(1):61–101.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
• Righini G, Salani M (2008) New dynamic programming algorithms for the resource constrained elementary shortest path problem. Networks 51(3):155–170.Crossref, Google Scholar
• Rist Y, Forbes M (2021) A new formulation for the dial-a-ride problem. Transportation Sci. 55(5):1113–1135.Link, Google Scholar
• Rist Y, Forbes M (2022) A column generation and combinatorial benders decomposition algorithm for the selective dial-a-ride-problem. Comput. Oper. Res. 140:105649.Crossref, Google Scholar
• Spliet R (2023) The complexity of the pricing problem of the set partitioning formulation of vehicle routing problems. Oper. Res. 71(5):1454–1457.Link, Google Scholar
• Toth P, Vigo D (2014) Vehicle Routing, Problems, Methods, and Applications, 2nd ed. (Society for Industrial and Applied Mathematics, Philadelphia).Google Scholar