Technical Note—The Complexity of the Pricing Problem of the Set Partitioning Formulation of Vehicle Routing Problems

References

• Archetti C, Bianchessi N, Speranza MG (2011) A column generation approach for the split delivery vehicle routing problem. Networks 58(4):241–254.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
• Bulhoes T, Ha MH, Martinelli R, Vidal T (2018) The vehicle routing problem with service level constraints. Eur. J. Oper. Res. 265(2):544–558.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
• 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
• Gélinas S, Desrochers M, Desrosiers J, Solomon MM (1995) A new branching strategy for time constrained routing problems with application to backhauling. Ann. Oper. Res. 61(1):91–109.Crossref, Google Scholar
• Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer, New York), 33–65.Crossref, 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
• Kallehauge B (2008) Formulations and exact algorithms for the vehicle routing problem with time windows. Comput. Oper. Res. 35(7):2307–2330.Crossref, Google Scholar
• Karp RM (1972) Reducibility among combinatorial problems. Miller RE, Thatcher JW, Bohlinger JD, eds. Complexity of Computer Computations, The IBM Research Symposia Series (Springer, Boston), 85–103.Crossref, 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
• Mingozzi A, Roberti R, Toth P (2013) An exact algorithm for the multitrip vehicle routing problem. INFORMS J. Comput. 25(2):193–207.Link, 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–100.Crossref, Google Scholar
• Ribeiro GM, Desaulniers G, Desrosiers J (2012) A branch-price-and-cut algorithm for the workover rig routing problem. Comput. Oper. Res. 39(12):3305–3315.Crossref, Google Scholar
• Tilk C, Bianchessi N, Drexl M, Irnich S, Meisel F (2018) Branch-and-price-and-cut for the active-passive vehicle-routing problem. Transportation Sci. 52(2):300–319.Link, Google Scholar
• Toth P, Vigo D (2002) Models, relaxations and exact approaches for the capacitated vehicle routing problem. Discrete Appl. Math. 123(1–3):487–512.Crossref, Google Scholar