Drone routing problem with swarm synchronization. (English) Zbl 07833040
Summary: The advantages of rotary-wing drone (RWD) delivery modes have already been delineated. However, single-unit RWDs do not completely solve real problems in last-mile parcel deliveries because of limited payload capacity and flight endurance. Currently, drone swarm technology is being rapidly developed. An RWD swarm can deliver heavy or multiple packages to customers; therefore, the RWD swarm strategy can address the payload capacity limitation of RWDs. Herein, an RWD delivery mode that involves dynamic swarms of RWDs in addition to single-unit RWDs is explored. The “dynamic” characteristic permits the RWD members in swarms to vary by coupling/decoupling operations at nodes. From the routing plan perspective, using RWD swarms for last-mile parcel deliveries is challenging; accordingly, we introduce a swarm synchronization mode that involves interactions among RWD routes. We formally define the drone routing problem with swarm synchronization (DRP-SS) and develop a mixed-integer linear programming model, which considers the decision on RWD swarms and multi trips. An adaptive large neighborhood search heuristic with specific operators is proposed. In the computational experiments, both small- and large-scale instances are used to validate the effectiveness of the mathematical formulation and the heuristic. Several managerial insights are obtained regarding the influence of detours, the utilization of RWD swarms, and the benefits of multi trips. The DRP-SS model and solution method can be used to estimate the performance of the selection of RWD swarms in practical situations.
MSC:
| 90Bxx | Operations research and management science |
Keywords:
routing; drone swarm synchronization; time window; mixed-integer linear programming; adaptive large neighborhood searchSoftware:
VRPSolverReferences:
| [1] | Ahmed, G.; Sheltami, T.; Mahmoud, A., IoD swarms collision avoidance via improved particle swarm optimization. Transportation Research Part A, 260-278 (2020) |
| [2] | Ali, Z. A.; Han, Z., Multi-unmanned aerial vehicle swarm formation control using hybrid strategy. Transactions of the Institute of Measurement and Control, 12, 2689-2701 (2021) |
| [3] | Alkouz, B.; Bouguettaya, A.; Mistry, S., Swarm-based drone-as-a-service (SDaaS) for delivery, 441-448 |
| [4] | Bianchessi, N.; Irnich, S., Branch-and-cut for the split delivery vehicle routing problem with time windows. Transportation Science, 2, 442-462 (2019) |
| [5] | Bortfeldt, A.; Yi, J., The split delivery vehicle routing problem with three-dimensional loading constraints. European Journal of Operational Research, 2, 545-558 (2020) · Zbl 1430.90062 |
| [6] | Boysen, N.; Fedtke, S.; Schwerdfeger, S., Last-mile delivery concepts: A survey from an operational research perspective. OR Spectrum, 1-58 (2020) |
| [7] | Chen, Y. B.; Yu, J. Q.; Su, X. L., Path planning for multi-UAV formation. Journal of Intelligent & Robotic Systems, 1, 229-246 (2015) |
| [8] | Cheng, C.; Adulyasak, Y.; Rousseau, L. M., Drone routing with energy function: Formulation and exact algorithm. Transportation Research Part B, 364-387 (2020) |
| [9] | 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) · Zbl 1458.90072 |
| [10] | Coelho, B. N.; Coelho, V. N.; Coelho, I. M., A multi-objective green UAV routing problem. Computers & Operations Research, 306-315 (2017) · Zbl 1391.90544 |
| [11] | D’Amato, E.; Mattei, M.; Notaro, I., Bi-level flight path planning of UAV formations with collision avoidance. Journal of Intelligent & Robotic Systems, 1, 193-211 (2019) |
| [12] | Dasdemir, E.; Köksalan, M.; Öztürk, D., A flexible reference point-based multi-objective evolutionary algorithm: An application to the UAV route planning problem. Computers & Operations Research (2019) |
| [13] | Demir, E.; Bektaş, T.; Laporte, G., An adaptive large neighborhood search heuristic for the pollution-routing problem. European Journal of Operational Research, 2, 346-359 (2012) · Zbl 1292.90045 |
| [14] | Di Puglia Pugliese, L.; Macrina, G.; Guerriero, F., Trucks and drones cooperation in the last-mile delivery process. Networks, 4, 371-399 (2021) · Zbl 1528.90026 |
| [15] | Dorling, K.; Heinrichs, J.; Messier, G. G., Vehicle routing problems for drone delivery. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 1, 70-85 (2017) |
| [16] | Drexl, M., Synchronization in vehicle routing—A survey of VRPs with multiple synchronization constraints. Transportation Science, 3, 297-316 (2012) |
| [17] | Fazi, S.; Choudhary, S. K.; Dong, J. X., The multi-trip container drayage problem with synchronization for efficient empty containers re-usage. European Journal of Operational Research (2023) · Zbl 07709821 |
| [18] | Fink, M.; Desaulniers, G.; Frey, M.; Kiermaier, F.; Kolisch, R.; Soumis, F., Column generation for vehicle routing problems with multiple synchronization constraints. European Journal of Operational Research, 2, 699-711 (2019) · Zbl 1403.90107 |
| [19] | Frey, C. M.; Jungwirth, A.; Frey, M.; Kolisch, R., The vehicle routing problem with time windows and flexible delivery locations. European Journal of Operational Research, 3, 1142-1159 (2023) · Zbl 07709271 |
| [20] | Guerriero, F.; Surace, R.; Loscri, V., A multi-objective approach for unmanned aerial vehicle routing problem with soft time windows constraints. Applied Mathematical Modelling, 3, 839-852 (2014) · Zbl 1427.90045 |
| [21] | Hà, M. H.; Nguyen, T. D.; Duy, T. N.; Pham, H. G.; Do, T.; Rousseau, L. M., A new constraint programming model and a linear programming-based adaptive large neighborhood search for the vehicle routing problem with synchronization constraints. Computers & Operations Research (2020) · Zbl 1458.90098 |
| [22] | Habib, D.; Jamal, H.; Khan, S. A., Employing multiple unmanned aerial vehicles for co-operative path planning. International Journal of Advanced Robotic Systems, 5, 235 (2013) |
| [23] | Hashemi Doulabi, H.; Pesant, G.; Rousseau, L. M., Vehicle routing problems with synchronized visits and stochastic travel and service times: Applications in healthcare. Transportation Science, 4, 1053-1072 (2020) |
| [24] | He, P.; Hao, J. K., General edge assembly crossover-driven memetic search for split delivery vehicle routing. Transportation Science, 2, 482-511 (2023) |
| [25] | Khorsi, M.; Chaharsooghi, S. K.; Husseinzadeh Kashan, A.; Bozorgi-Amiri, A., Solving the humanitarian multi-trip cumulative capacitated routing problem via a grouping metaheuristic algorithm. Annals of Operations Research, 1-38 (2022) |
| [26] | Kratky, V.; Alcantara, A.; Capitan, J., Autonomous aerial filming with distributed lighting by a team of unmanned aerial vehicles. IEEE Robotics and Automation Letters, 4, 7580-7587 (2021) |
| [27] | 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, 3, 1078-1095 (2021) · Zbl 1487.90130 |
| [28] | Li, J.; Luo, Z.; Baldacci, R.; Qin, H., A new exact algorithm for single-commodity vehicle routing with split pickups and deliveries. INFORMS Journal on Computing, 1, 31-49 (2023) · Zbl 1533.90023 |
| [29] | Li, J.; Qin, H.; Baldacci, R.; Zhu, W., Branch-and-price-and-cut for the synchronized vehicle routing problem with split delivery, proportional service time and multiple time windows. Transportation Research Part E (2020) |
| [30] | Li, H.; Wang, H.; Chen, J.; Bai, M., Two-echelon vehicle routing problem with time windows and mobile satellites. Transportation Research Part B, 179-201 (2020) |
| [31] | Li, H.; Wang, F., Branch-price-and-cut for the truck-drone routing problem with time windows. Naval Research Logistics (NRL), 2, 184-204 (2023) · Zbl 1525.90064 |
| [32] | Lim, A.; Zhang, Z.; Qin, H., Pickup and delivery service with manpower planning in Hong Kong public hospitals. Transportation Science, 2, 688-705 (2017) |
| [33] | Liu, Y., An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones. Computers & Operations Research, 1-20 (2019) · Zbl 1458.90113 |
| [34] | Macrina, G.; Pugliese, L. D.P.; Guerriero, F.; Laporte, G., Drone-aided routing: A literature review. Transportation Research Part C: Emerging Technologies (2020) |
| [35] | Murray, C. C.; Chu, A. G., The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies, 86-109 (2015) |
| [36] | Nagasawa, R.; Mas, E.; Moya, L., Model-based analysis of multi-UAV path planning for surveying postdisaster building damage. Scientific Reports, 1, 1-14 (2021) |
| [37] | Otto, A.; Agatz, N.; Campbell, J.; Golden, B.; Pesch, E., Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey. Networks, 4, 411-458 (2018) |
| [38] | Pan, B.; Zhang, Z.; Lim, A., Multi-trip time-dependent vehicle routing problem with time windows. European Journal of Operational Research, 1, 218-231 (2021) · Zbl 1487.90158 |
| [39] | Pecin, D.; Contardo, C.; Desaulniers, G.; Uchoa, E., New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS Journal on Computing, 3, 489-502 (2017) · Zbl 1378.90027 |
| [40] | Pessoa, A.; Sadykov, R.; Uchoa, E.; Vanderbeck, F., A generic exact solver for vehicle routing and related problems. Mathematical Programming, 483-523 (2020) · Zbl 1450.90017 |
| [41] | Rajaei, M.; Moslehi, G.; Reisi-Nafchi, M., The split heterogeneous vehicle routing problem with three-dimensional loading constraints on a large scale. European Journal of Operational Research, 2, 706-721 (2022) · Zbl 1490.90064 |
| [42] | Ropke, S.; Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 4, 455-472 (2006) |
| [43] | Sarasola, B.; Doerner, K. F., Adaptive large neighborhood search for the vehicle routing problem with synchronization constraints at the delivery location. Networks, 1, 64-85 (2020) · Zbl 1526.90003 |
| [44] | Shao, S.; Peng, Y.; He, C., Efficient path planning for UAV formation via comprehensively improved particle swarm optimization. ISA transactions, 415-430 (2020) |
| [45] | Shao, Z.; Yan, F.; Zhou, Z., Path planning for multi-UAV formation rendezvous based on distributed cooperative particle swarm optimization. Applied Sciences, 13, 2621 (2019) |
| [46] | Shetty, V. K.; Sudit, M.; Nagi, R., Priority-based assignment and routing of a fleet of unmanned combat aerial vehicles. Computers & Operations Research, 6, 1813-1828 (2008) · Zbl 1139.90345 |
| [47] | Solomon, M. M., Algorithms for the vehicle routing and scheduling problem with time window constraints. Operations Research, 2, 254-265 (1987) · Zbl 0625.90047 |
| [48] | Song, B. D.; Park, K.; Kim, J., Persistent UAV delivery logistics: MILP formulation and efficient heuristic. Computers & Industrial Engineering, 418-428 (2018) |
| [49] | Vidal, T.; Crainic, T. G.; Gendreau, M.; Prins, C., A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows. Computers & Operations Research, 1, 475-489 (2013) · Zbl 1349.90137 |
| [50] | Vincent, F. Y.; Jodiawan, P.; Hou, M. L., Design of a two-echelon freight distribution system in last-mile logistics considering covering locations and occasional drivers. Transportation Research Part E (2021) |
| [51] | Wang, L.; Kinable, J.; Van Woensel, T., The fuel replenishment problem: A split-delivery multi-compartment vehicle routing problem with multiple trips. Computers & Operations Research (2020) · Zbl 1458.90149 |
| [52] | Zhen, L.; Ma, C.; Wang, K., Multi-depot multi-trip vehicle routing problem with time windows and release dates. Transportation Research Part E (2020) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
