Two-echelon Vehicle Cooperated Operations Problems: The State of the Art and Future Direction

Abstract

In the Two-Echelon Vehicle Cooperation Problem (2ECOP), different vehicles operate on primary and secondary echelons to optimize package delivery, resulting in cost savings and efficient services. Our work focuses on the cooperation of two-echelon vehicles and their optimal scheduling and routing strategies, as well as their numerous applications across industry. We examine the literature of the 2ECOP across various dimensions, including various cooperated modes, distinct optimization methodologies, and practical settings. Our work identifies various effective algorithms and heuristic solution procedures for the 2ECOP. We also propose a unified approach for delivery that is designed for reducing cost and improving service efficiency. We believe that academic research and industry would both benefit from a unified classification scheme that extends to new two-echelon operated logistics models that may emerge in response to future technological advances.

Keywords

Two-echelon vehicles / delivery / literature review / future research directions

References

[1] Agatz N, Bouman P, Schmidt M. Optimization approaches for the traveling salesman problem with drone. Transportation Science, 2018, 52(4): 965-981

[2] Alfandari L, Ivana L, Marcos D M. A tailored Benders decomposition approach for last-mile delivery with autonomous robots. European Journal of Operational Research, 2022, 299: 510-525

[3] Bai X, Ye Y, Zhang B, Ge S S. Efficient package delivery task assignment for truck and high capacity drone. IEEE Transactions on Intelligent Transportation Systems, 2023, 17(1): 248-260

[4] Boccia M, Masone A, Sforza A, Sterle C. A column-and-row generation approach for the flying sidekick travelling salesman problem. Transportation Research Part C, 2021, 124(4): 102913

[5] Boysen N, Schwerdfeger S, Weidinger F. Scheduling last-mile deliveries with truck-based autonomous robots. European Journal of Operational Research, 2018, 271: 1085-1099

[6] Cai Y J, Choi T M. Extended producer responsibility: A systematic review and innovative proposals for improving sustainability. IEEE Transactions on Engineering Management, 2021, 68(1): 272-288

[7] Cavani S, Iori M, Roberti R. Exact methods for the traveling salesman problem with multiple drones. Transportation Research Part C: Emerging Technologies, 2021, 130: 103280

[8] Chang Y S, Lee H J. Optimal delivery routing with wider drone-delivery areas along a shorter truck-route. Expert Systems with Applications, 2018, 104: 307-317

[9] Chen C, Demir E, Huang Y. An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots. European Journal of Operational Research, 2021, 294(3): 1164-1180

[10] Chen C, Demir E, Huang Y, Qiu R. The adoption of self-driving delivery robots in last mile logistics. Transportation Research Part E, 2021, 146: 102214

[11] Chiang W C, Li Y, Shang J, Urban T L. Impact of drone delivery on sustainability and cost: Realizing the UAV potential through vehicle routing optimization. Applied Energy, 2019, 242: 1164-1175

[12] Chung S H, Sah B, Lee J. Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions. Computers & Operations Research, 2020, 123: 105004

[13] Dayarian I, Savelsbergh M, Clarke J P. Same-day delivery with drone resupply. Transportation Science, 2020, 54(1): 229-249

[14] Dell’Amico M, Montemanni R, Novellani S. Drone-assisted deliveries: New formulations for the flying sidekick traveling salesman problem. Optimization Letters, 2019, 15: 1-32

[15] Dell’Amico M, Montemanni R, Novellani S. Algorithms based on branch and bound for the flying sidekick traveling salesman problem. Omega, 2021, 104(4): 102493

[16] Dienstknecht M, Boysen N, Briskorn D. The traveling salesman problem with drone resupply. OR Spectrum, 2022, 4441045-1086

[17] Dukkanci O, Koberstein A, Kara B Y. Drones for relief logistics under uncertainty after an earthquake. European Journal of Operational Research, 2023, 310: 117-132

[18] El-Adle A M, Ghoniem A, Haouari M. A variable neighborhood search for parcel delivery by vehicle with drone cycles. Computers and Operations Research, 2023, 159: 106319

[19] Gonzalez R P L, Canca D, Andrade-Pineda J L, Calle M, Leon-Blanco J M. Truck-drone team logistics: A heuristic approach to multi-drop route planning. Transportation Research Part C: Emerging Technologies, 2020, 114: 657-680

[20] Gu R, Poon M, Luo Z, Liu Y, Liu Z. A hierarchical solution evaluation method and a hybrid algorithm for the vehicle routing problem with drones and multiple visits. Transportation Research Part C, 2022, 141: 103733

[21] Ha Q M, Deville Y, Pham Q D, Minh H H. On the min-cost traveling salesman problem with drone. Transportation Research Part C, 2018, 86: 597-621

[22] Heimfarth A, Ostermeier M, Alexander H. A mixed truck and robot delivery approach for the daily supply of customers. European Journal of Operational Research, 2022, 303: 401-421

[23] Imran N M, Mishra S, Won M. A-VRPD: Automating drone-based last-mile delivery using self-driving cars. IEEE Transactions on Intelligent Transportation Systems, 2023, 24(9): 9599-9612

[24] Jacobsen S K, Madsen O B G. A comparative study of heuristics for a two-level routing-location problem. European Journal of Operational Research, 1980, 5(6): 378-387

[25] Jeong H Y, Song B D, Lee S. Truck-drone hybrid delivery routing: Payload-energy dependency and no-fly zones. International Journal of Production Economics, 2019, 214: 220-233

[26] Kang M, Lee C. An exact algorithm for heterogeneous drone-truck routing problem. Transportation Science, 2021, 55(5): 1088-1112

[27] Karak A, Abdelghany K. The hybrid vehicle-drone routing problem for pick-up and delivery services. Transportation Research Part C: Emerging Technologies, 2019, 102: 427-449

[28] Kitjacharoenchai P, Min B C, Lee S. Two echelon vehicle routing problem with drones in last mile delivery. International Journal of Production Economics, 2020, 225: 107598

[29] Kitjacharoenchai P, Ventresca M, Moshref-Javadi M, Lee S, Tanchoco J M A, Brunese P A. Multiple traveling salesman problem with drones: Mathematical model and heuristic approach. Computers & Industrial Engineering, 2019, 129: 14-30

[30] Kloster K, Moeini M, Vigo D, Wendt O. The multiple traveling salesman problem in presence of drone- and robot-supported packet stations. European Journal of Operational Research, 2023, 305(2): 630-643

[31] Kuo R J, Edbert E, Zulvia F E, Lu S H. Applying NSGA-II to vehicle routing problem with drones considering makespan and carbon emission. Expert Systems with Applications, 2023, 221: 119777

[32] Lei D, Cui Z, Li M. A dynamical artificial bee colony for vehicle routing problem with drones. Engineering Applications of Artificial Intelligence, 2022, 107: 104510

[33] Li H, Chen J, Wang F, Bai M. Ground-vehicle and unmanned-aerial-vehicle routing problems from two-echelon scheme perspective: A review. European Journal of Operational Research, 2021, 294(3): 1078-1095

[34] Liang Y J, Luo Z X. A survey of truck-drone routing problem: Literature review and research prospects. Journal of the Operations Research Society of China, 2022, 10(2): 343-377

[35] Liu D, Yan P, Pu Zet al.. Hybrid artificial immune algorithm for optimizing a van-robot e-grocery delivery system. Transportation Research Part E: Logistics and Transportation Review, 2021, 154: 102466

[36] Liu Y, Liu Z, Shi J, Wu G, Pedrycz W. Two-echelon routing problem for parcel delivery by cooperated truck and drone. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2020, 51(12): 7450-7465

[37] Lu Y, Yang C, Yang J. A multi-objective humanitarian pickup and delivery vehicle routing problem with drones. Annals of Operations Research, 2022, 319: 291-353

[38] Lu Y, Yang J, Yang C. A humanitarian vehicle routing problem synchronized with drones in time-varying weather conditions. Computers & Industrial Engineering, 2023, 184: 109563

[39] Luo Q, Wu G, Ji B, Wang L, Suganthan P N. Hybrid multi-objective optimization approach with Pareto local search for collaborative truck-drone routing problems considering flexible time windows. IEEE Transactions on Intelligent Transportation Systems, 2021, 23(8): 13011-13025

[40] Macrina G, Pugliese L D P, Guerriero F, Laporte G. Drone-aided routing: A literature review. Transportation Research Part C: Emerging Technologies, 2020, 120: 102762

[41] Madani B, Ndiaye M. Hybrid truck-drone delivery systems: A systematic literature review. IEEE Access, 2022, 10: 92854-92878

[42] Mara S T W, Achmad P R, Bertha M S. An adaptive large neighborhood search heuristic for the flying sidekick traveling salesman problem with multiple drops. Expert Systems with Applications, 2022, 205: 117647

[43] Masmoudi M A, Mancini S, Baldacci R, Kuo Y H. Vehicle routing problems with drones equipped with multi-package payload compartments. Transportation Research Part E: Logistics and Transportation Review, 2022, 164: 102757

[44] Meng S, Guo X, Li D, Liu G. The multi-visit drone routing problem for pickup and delivery services. Transportation Research Part E: Logistics and Transportation Review, 2023, 169: 102990

[45] Momeni M, Mirzapour Al-e-Hashem S M J, Heidari A. A new truck-drone routing problem for parcel delivery by considering energy consumption and altitude. Annals of Operations Research, 2023, 337: 1-47

[46] Moshref-Javadi M, Hemmati A, Winkenbach M. A truck and drones model for last-mile delivery: A mathematical model and heuristic approach. Applied Mathematical Modelling, 2020, 80: 290-318

[47] Moshref-Javadi M, Lee S, Winkenbach M. Design and evaluation of a multi-trip delivery model with truck and drones. Transportation Research Part E, 2020, 136: 101887

[48] Moshref-Javadi M, Winkenbach M. Applications and research avenues for drone-based models in logistics: A classification and review. Expert Systems with Applications, 2021, 177: 114854

[49] Murray C C, Chu G A. The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C, 2015, 54: 54-109

[50] Murray C C, Raj R. The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones. Transportation Research Part C, 2020, 110: 268-398

[51] Najy W, Archetti C, Diabat A. Collaborative truck-and-drone delivery for inventory-routing problems. Transportation Research Part C: Emerging Technologies, 2023, 146: 103791

[52] Ostermeier M, Heimfarth A, Alexander H. The multi-vehicle truck-and-robot routing problem for last-mile delivery. European Journal of Operational Research, 2023, 310: 680-697

[53] Pina-Pardo J C, Silva D F, Smith A E. The traveling salesman problem with release dates and drone resupply. Computers & Operations Research, 2021, 129: 105170

[54] Poikonen S, Golden B. Multi-visit drone routing problem. Computers and Operations Research, 2020, 113: 104802

[55] Raj R, Murray C C. The multiple flying sidekicks traveling salesman problem with variable drone speeds. Transportation Research Part C, 2020, 120: 102813

[56] Rave A, Fontaine P, Kuhn H. Drone location and vehicle fleet planning with trucks and aerial drones. European Journal of Operational Research, 2023, 308(1): 113-130

[57] Roberti R, Ruthmair M. Exact methods for the traveling salesman problem with drone. Transportation Science, 2021, 55(2): 315-335

[58] Sacramento D, Pisinger D, Ropke S. An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transportation Research, 2019, 102: 289-315

[59] Salama M R, Srinivas S. Collaborative truck multi-drone routing and scheduling problem: Package delivery with flexible launch and recovery sites. Transportation Research Part E, 2022, 164: 102788

[60] Schermer D, Moeini M, Wendt O. A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations. Computers & Operations Research, 2019, 109: 134-158

[61] Schermer D, Moeini M, Wendt O. A matheuristic for the vehicle routing problem with drones and its variants. Transportation Research Part C: Emerging Technologies, 2019, 106: 166-204

[62] Simoni M D, Kutanoglu E, Claudel C G. Optimization and analysis of a robot-assisted last mile delivery system. Transportation Research Part E: Logistics and Transportation Review, 2020, 142: 102049

[63] Sluijk N, Florio M A, Kinable J, Dellaert N, Woensel V T. Two-echelon vehicle routing problems: A literature review. European Journal of Operational Research, 2023, 304: 865-886

[64] Srinivas S, Ramachandiran S, Rajendran S. Autonomous robot-driven deliveries: A review of recent developments and future directions. Transportation Research Part E, 2022, 165: 102834

[65] Tamke F, Buscher U. A branch-and-cut algorithm for the vehicle routing problem with drones. Transportation Research Part B, 2021, 144: 174-203

[66] Thomas T, Srinivas S, Rajendran C. Collaborative truck multi-drone delivery system considering drone scheduling and enroute operations. Annals of Operations Research, 2023, 339: 1-47

[67] Tinic G O, Karasan O E, Kara B Y, Campbell J F, Ozel A. Exact solution approaches for the minimum total cost traveling salesman problem with multiple drones. Transportation Research Part B:Methodological, 2023, 168: 81-123

[68] Wang K, Yuan B, Zhao M, Lu Y. Cooperative route planning for the drone and truck in delivery services: A bi-objective optimisation approach. Journal of the Operational Research Society, 2020, 71(10): 1657-1674

[69] Wang Y, Wang Z, Hu X, Xue G, Guan X. Truck-drone hybrid routing problem with time-dependent road travel time. Transportation Research Part C, 2022, 144: 103901

[70] Wang Z, Sheu J B. Vehicle routing problem with drones. Transportation Research Part B: Methodological, 2019, 122: 350-364

[71] Wu G, Mao N, Luo Q, Xu B, Shi J, Suganthan P N. Collaborative truck-drone routing for contactless parcel delivery during the epidemic. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(12): 25077-25091

[72] Xia Y, Zeng W, Zhang C, Yang H. A branch-and-price-and-cut algorithm for the vehicle routing problem with load-dependent drones. Transportation Research Part B: Methodological, 2023, 171: 80-110

[73] Yang Y, Yan C, Cao Y, Roberti R. Planning robust drone-truck delivery routes under road traffic uncertainty. European Journal of Operational Research, 2023, 309(3): 1145-1160

[74] Yin Y, Li D, Wang D, Ignatius J, Cheng T C E, Wang S. A branch-and-price-and-cut algorithm for the truck-based drone delivery routing problem with time windows. European Journal of Operational Research, 2023, 309(3): 1125-1144

[75] Yin Y, Yang Y, Yu Y, Wang D, Cheng T C E. Robust vehicle routing with drones under uncertain demands and truck travel times in humanitarian logistics. Transportation Research Part B, 2023, 174: 102781

[76] Yu S, Puchinger J, Sun S. Van-based robot hybrid pickup and delivery routing problem. European Journal of Operational Research, 2022, 298: 894-914

[77] Zhang G, Zhu N, Ma S, Xia J. Humanitarian relief network assessment using collaborative truck-and-drone system. Transportation Research Part E, 2021, 152: 102417

RIGHTS & PERMISSIONS

Systems Engineering Society of China and Springer-Verlag GmbH Germany