A Branch-Cut-and-Price Approach for the Single-Trip and Multi-Trip Two-Echelon Vehicle Routing Problem with Time Windows

References

• Allen J, Browne M, Woodburn A, Leonardi J (2012) The role of urban consolidation centres in sustainable freight transport. Transport Rev. 32(4):473–490.Crossref, Google Scholar
• Amarouche Y, Guibadj RN, Moukrim A (2018) A neighborhood search and set cover hybrid heuristic for the two-echelon vehicle routing problem. Borndörfer R, Storandt S, eds. Proc. 18th Workshop on Algorithmic Approaches for Transportation Modeling, Optim., and Systems, vol. 65 of OpenAccess Series in Informatics (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 11:1–15.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:351–385.Crossref, Google Scholar
• Baldacci R, Mingozzi A, Roberti R, Calvo RW (2013) An exact algorithm for the two-echelon capacitated vehicle routing problem. Oper. Res. 61(2):298–314.Link, Google Scholar
• Bjorklund M, Johansson H (2018) Urban consolidation centre: A literature review, categorisation, and a future research agenda. Internat. J. Phys. Distribution Logist. Management 48(8):745–764.Crossref, Google Scholar
• Breunig U, Schmid V, Hartl R, Vidal T (2016) A large neighbourhood based heuristic for two-echelon routing problems. Comput. Oper. Res. 76:208–225.Crossref, Google Scholar
• Clarke S, Leonardi J (2017) Agile Gnewt cargo: parcels deliveries with electric vehicles in central london multi-carrier central London micro-consolidation and final delivery via low carbon vehicles. Data report. Technical report, Greater London Authority, London.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, Hemmelmayr V, Crainic TG (2012) Lower and upper bounds for the two-echelon capacitated location-routing problem. Comput. Oper. Res. 39(12):3185–3199.Crossref, Google Scholar
• Crainic TG, Ricciardi N, Storchi G (2009) Models for evaluating and planning city logistics systems. Transportation Sci. 43(4):432–454.Link, Google Scholar
• Cuda R, Guastaroba G, Speranza M (2015) A survey on two-echelon routing problems. Comput. Oper. Res. 55:185–199.Crossref, Google Scholar
• Dellaert N, Saridarq FD, Woensel TV, Crainic TG (2019) Branch and price based algorithms for the two-echelon vehicle routing problem with time windows. Transportation Sci. 53(2):463–479.Link, Google Scholar
• Dellaert N, Van Woensel T, Crainic TG, Dashty Saridarq F (2021) A multi-commodity two-echelon capacitated vehicle routing problem with time windows: Model formulations and solution approach. Comput. Oper. Res. 127:105154.Crossref, Google Scholar
• Gonzalez-Feliu J, Perboli G, Tadei R, Vigo D (2007) The two-echelon capacitated vehicle routing problem. Technical report, Department of Electronics, Computer Science, and Systems, University of Bologna, Bologna, Italy.Google Scholar
• Grangier P, Gendreau M, Lehuédé F, Rousseau LM (2016) An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization. Eur. J. Oper. Res. 254(1):80–91.Crossref, Google Scholar
• He P, Li J (2019) The two-echelon multi-trip vehicle routing problem with dynamic satellites for crop harvesting and transportation. Appl. Soft Comput. 77:387–398.Crossref, Google Scholar
• Hemmelmayr VC, Cordeau JF, Crainic TG (2012) An adaptive large neighborhood search heuristic for Two-Echelon Vehicle Routing Problems arising in city logistics. Comput. Oper. Res. 39(12):3215–3228.Crossref, Google Scholar
• Holguín-Veras J, Amaya Leal J, Sanchez-Diaz I, Browne M, Wojtowicz J (2020) State of the art and practice of urban freight management Part II: Financial approaches, logistics, and demand management. Transportation Res. Part A: Policy Practice 137:383–410.Crossref, Google Scholar
• PI TLSIoachim I, Gélinas S, Soumis F, Desrosiers J (1998) A dynamic programming algorithm for the shortest path problem with time windows and linear node costs. Networks 31(3):193–204.Crossref, Google Scholar
• Jepsen M, Spoorendonk S, Ropke S (2013) A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem. Transportation Sci. 47(1):23–37.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
• Katsela K, Browne M (2019) Importance of the stakeholders’ interaction: Comparative, longitudinal study of two city logistics initiatives. Sustainability 11(20):5844.Crossref, Google Scholar
• Laporte G, Nobert Y (1983) A branch and bound algorithm for the capacitated vehicle routing problem. Oper. Res. Spektrum 5(2):77–85.Crossref, Google Scholar
• Li H, Liu Y, Chen K, Lin Q (2020a) The two-echelon city logistics system with on-street satellites. Comput. Industry Engrg. 139:105577.Crossref, Google Scholar
• Li H, Wang H, Chen J, Bai M (2020b) Two-echelon vehicle routing problem with time windows and mobile satellites. Transportation Res., Part B: Methodological 138:179–201.Crossref, Google Scholar
• Li H, Zhang L, Lv T, Chang X (2016) The two-echelon time-constrained vehicle routing problem in linehaul-delivery systems. Transportation Res. Part B: Methodological 94:169–188.Crossref, Google Scholar
• Lysgaard J (2018) CVRPSEP: A package of separation routines for the capacitated vehicle routing problem. Accessed March 2, 2022, http://econ.au.dk/research/researcher-websites/jens-lysgaard/cvrpsep/.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
• Marques G, Sadykov R, Deschamps JC, Dupes R (2020) An improved branch-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem. Comput. Oper. Res. 114:104833.Crossref, Google Scholar
• McDermott DR (1975) An alternative framework for urban goods distribution: Consolidation. Transp. J. 15(1):29–39.Google Scholar
• Muñoz G, Espinoza D, Goycoolea M, Moreno E, Queyranne M, Letelier OR (2018) A study of the Bienstock–Zuckerberg algorithm: Applications in mining and resource constrained project scheduling. Comput. Optim. Appl. 69(2):501–534.Crossref, Google Scholar
• Muter I, Cordeau JF, Laporte G (2014) A branch-and-price algorithm for the multidepot vehicle routing problem with interdepot routes. Transportation Sci. 48(3):425–441.Link, Google Scholar
• Muter I, Ilker Birbil Ş, Bülbül K (2018) Benders decomposition and column-and-row generation for solving large-scale linear programs with column-dependent-rows. Eur. J. Oper. Res. 264(1):29–45.Crossref, Google Scholar
• Nolz PC, Absi N, Cattaruzza D, Feillet D (2020) Two-echelon distribution with a single capacitated city hub. EURO J. Transporation Logist. 9:100015.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
• Perboli G, Tadei R, Vigo D (2011) The two-echelon capacitated vehicle routing problem: Models and math-based heuristics. Transportation Sci. 45(3):364–380.Link, 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, vol. 43 of Operations Research/Computer Science Interfaces (Springer, New York), 297–325.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
• 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, Sadykov R, Uchoa E, Vanderbeck F (2020) A generic exact solver for vehicle routing and related problems. Math. Programming 183:483–523.Crossref, Google Scholar
• Rothberg E (2007) An evolutionary algorithm for polishing mixed integer programming solutions. INFORMS J. Comput. 19(4):534–541.Link, Google Scholar
• Sadykov R, Vanderbeck F (2013) Column generation for extended formulations. EURO J. Comput. Optim. 1(1-2):81–115.Crossref, Google Scholar
• Sadykov R, Vanderbeck F (2021) BaPCod—A generic branch-and-price code. Technical report, Inria Bordeaux—Sud-Ouest, Talence, France.Google Scholar
• Sadykov R, Uchoa E, Pessoa A (2021) A bucket graph–based labeling algorithm with application to vehicle routing. Transportation Sci. 55(1):4–28.Link, Google Scholar
• Santos FA, Mateus GR, da Cunha AS (2015) A branch-and-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem. Transportation Sci. 49(2):355–368.Link, Google Scholar
• Simon Bohne MR, Leonardi J (2014) Best practice factory for freight transport in Europe: Demonstrating how ‘good’ urban freight cases are improving business profit and public sectors benefits. Procedia Soc. Behav. Sci. 125:84–98.Google Scholar
• van Rooijen T, Quak H (2010) Local impacts of a new urban consolidation centre: The case of binnenstadservice.nl. Procedia Soc. Behav. Sci. 2(3):5967–5979.Crossref, Google Scholar
• Wang Z, Wen P (2020) Optimization of a low-carbon two-echelon heterogeneous-fleet vehicle routing for cold chain logistics under mixed time window. Sustainability 12(5):179–201.Crossref, Google Scholar
• Wang K, Shao Y, Zhou W (2017) Matheuristic for a two-echelon capacitated vehicle routing problem with environmental considerations in city logistics service. Transportation Res. Part D Transportation Environ. 57:262–276.Crossref, Google Scholar
• Zeng ZY, Xu WS, Xu ZY, Shao WH (2014) A hybrid GRASP+VND heuristic for the two-echelon vehicle routing problem arising in city logistics. Math. Problems Engrg. 2014:517467.Google Scholar