An Exact Price-Cut-and-Enumerate Method for the Capacitated Multitrip Vehicle Routing Problem with Time Windows

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
• Amazon (2021) Amazon’s custom electric delivery vehicles are starting to hit the road (February 3), https://www.aboutamazon.com/news/transportation/amazons-custom-electric-delivery-vehicles-are-starting-to-hit-the-road.Google Scholar
• Azi N, Gendreau M, Potvin JY (2007) An exact algorithm for a single-vehicle routing problem with time windows and multiple routes. Eur. J. Oper. Res. 178(3):755–766.Crossref, Google Scholar
• Azi N, Gendreau M, Potvin JY (2010) An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles. Eur. J. Oper. Res. 202(3):756–763.Crossref, Google Scholar
• Azi N, Gendreau M, Potvin JY (2014) An adaptive large neighborhood search for a vehicle routing problem with multiple routes. Comput. Oper. Res. 41:167–173.Crossref, 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(2):351–385.Crossref, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2012) New state-space relaxations for solving the traveling salesman problem with time windows. INFORMS J. Comput. 24(3):356–371.Link, Google Scholar
• Benkebir N, Pouliquen ML, Trévien J, Bounceur A, Euler R, Pardiac E, Sevaux M (2019) On a multi-trip vehicle routing problem with time windows integrating European and French driver regulations. J. Vehicle Routing Algorithms 2(1):55–74.Crossref, Google Scholar
• Braekers K, Ramaekers K, Van Nieuwenhuyse I (2016) The vehicle routing problem: State of the art classification and review. Comput. Indust. Engrg. 99:300–313.Crossref, Google Scholar
• Cattaruzza D, Absi N, Feillet D (2016a) The multi-trip vehicle routing problem with time windows and release dates. Transportation Sci. 50(2):676–693.Link, Google Scholar
• Cattaruzza D, Absi N, Feillet D (2016b) Vehicle routing problems with multiple trips. 4OR 14(3):223–259.Crossref, Google Scholar
• Cattaruzza D, Absi N, Feillet D, Vigo D (2014) An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows. Comput. Oper. Res. 51:257–267.Crossref, Google Scholar
• Cheng C, Adulyasak Y, Rousseau LM (2020) Drone routing with energy function: Formulation and exact algorithm. Transportation Res. Part B Methodological 139:364–387.Crossref, Google Scholar
• Choi Y, Robertson B, Choi Y, Mavris D (2019) A multi-trip vehicle routing problem for small unmanned aircraft systems-based urban delivery. J. Aircraft 56(6):2309–2323.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
• Dantzig GB, Ramser JH (1959) The truck dispatching problem. Management Sci. 6(1):80–91.Link, Google Scholar
• Derigs U, Kurowsky R, Vogel U (2011) Solving a real-world vehicle routing problem with multiple use of tractors and trailers and EU-regulations for drivers arising in air cargo road feeder services. Eur. J. Oper. Res. 213(1):309–319.Crossref, Google Scholar
• Desaulniers G, Gschwind T, Irnich S (2020) Variable fixing for two-arc sequences in branch-price-and-cut algorithms on path-based models. Transportation Sci. 54(5):1170–1188.Link, Google Scholar
• Dorling K, Heinrichs J, Messier GG, Magierowski S (2016) Vehicle routing problems for drone delivery. IEEE Trans. Systems Man Cybernetics Systems 47(1):70–85.Crossref, 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
• Figliozzi MA (2020) Carbon emissions reductions in last mile and grocery deliveries utilizing air and ground autonomous vehicles. Transportation Res. Part D Transportation Environ. 85:102443.Crossref, Google Scholar
• Fleischmann B (1990) The vehicle routing problem with multiple use of vehicles. Working paper, Department of Economics, Universität Hamburg.Google Scholar
• François V, Arda Y, Crama Y (2019) Adaptive large neighborhood search for multitrip vehicle routing with time windows. Transportation Sci. 53(6):1706–1730.Link, Google Scholar
• Golden BL, Raghavan S, Wasil EA (2008) The Vehicle Routing Problem: Latest Advances and New Challenges (Springer, New York).Crossref, Google Scholar
• Gurobi Optimization LLC (2021) Gurobi optimizer reference manual, https://www.gurobi.com/documentation/9.1/refman/index.html.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
• Hernandez F, Feillet D, Giroudeau R, Naud O (2014) A new exact algorithm to solve the multi-trip vehicle routing problem with time windows and limited duration. 4OR 12(3):235–259.Crossref, Google Scholar
• Hernandez F, Feillet D, Giroudeau R, Naud O (2016) Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows. Eur. J. Oper. Res. 249(2):551–559.Crossref, Google Scholar
• Homberger J, Gehring H (2005) A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. Eur. J. Oper. Res. 162(1):220–238.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, 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
• Janic M (2007) Modelling the full costs of an intermodal and road freight transport network. Transportation Res. Part D Transportation Environ. 12(1):33–44.Crossref, 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
• Kunovjanek M, Wankmüller C (2021) Containing the Covid-19 pandemic with drones-feasibility of a drone enabled back-up transport system. Transportation Policy 106:141–152.Crossref, Google Scholar
• Labadie N, Mansini R, Melechovský J, Calvo RW (2012) The team orienteering problem with time windows: An LP-based granular variable neighborhood search. Eur. J. Oper. Res. 220(1):15–27.Crossref, Google Scholar
• Lim A, Zhang Z, Qin H (2017) Pickup and delivery service with manpower planning in Hong Kong public hospitals. Transportation Sci. 51(2):688–705.Link, Google Scholar
• Liu S, Wu H, Xiang S, Li X (2017) Mobile robot scheduling with multiple trips and time windows. Cong G, Peng W-C, Zhang WE, Li C, Sun A, eds. Proc. Internat. Conf. Advanced Data Mining Appl. (Springer, Cham, Switzerland), 608–620.Google Scholar
• Lyons L, Lozano A, Granados F, Guzmán A (2017) Impacts of time restriction on heavy truck corridors: The case study of Mexico City. Transportation Res. Part A Policy Practice 102:119–129.Crossref, Google Scholar
• Macedo R, Alves C, Valério de Carvalho J, Clautiaux F, Hanafi S(2011) Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model. Eur. J. Oper. Res. 214(3):536–545.Crossref, Google Scholar
• Pan B, Zhang Z, Lim A (2021) Multi-trip time-dependent vehicle routing problem with time windows. Eur. J. Oper. Res. 291(1):218–231.Crossref, Google Scholar
• Paradiso R, Roberti R, Laganá D, Dullaert W (2020) An exact solution framework for multitrip vehicle-routing problems with time windows. Oper. Res. 68(1):180–198.Link, 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 (2017b) Improved branch-cut-and-price for capacitated vehicle routing. Math. Programming Comput. 9(1):61–100.Crossref, Google Scholar
• Pelletier S, Jabali O, Laporte G (2016) Goods distribution with electric vehicles: Review and research perspectives. Transportation Sci. 50(1):3–22.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(1):483–523.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
• Salhi S (1987) The integration of routing into the location-allocation and vehicle composition problems. Unpublished doctoral dissertation, University of Lancaster, UK.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
• Sun Y, Wang D, Lang M, Zhou X (2019) Solving the time-dependent multi-trip vehicle routing problem with time windows and an improved travel speed model by a hybrid solution algorithm. Cluster Comput. 22(6):15459–15470.Crossref, Google Scholar
• Tang J, Yu Y, Li J (2015) An exact algorithm for the multi-trip vehicle routing and scheduling problem of pickup and delivery of customers to the airport. Transportation Res. Part E Logist. Transportation Rev. 73:114–132.Crossref, Google Scholar
• Tilk C, Irnich S (2017) Dynamic programming for the minimum tour duration problem. Transportation Sci. 51(2):549–565.Link, Google Scholar
• Toth P, Vigo D (2014) Vehicle Routing: Problems, Methods, and Applications (SIAM, Philadelphia).Crossref, Google Scholar
• Vansteenwegen P, Souffriau W, Berghe GV, Van Oudheusden D(2009) Iterated local search for the team orienteering problem with time windows. Comput. Oper. Res. 36(12):3281–3290.Crossref, Google Scholar
• Vidal T, Laporte G, Matl P (2020) A concise guide to existing and emerging vehicle routing problem variants. Eur. J. Oper. Res. 286(2):401–416.Crossref, Google Scholar
• Wang Z, Liang W, Hu X (2014) A metaheuristic based on a pool of routes for the vehicle routing problem with multiple trips and time windows. J. Oper. Res. Soc. 65(1):37–48.Crossref, Google Scholar