Optimizing synchronized truck-drone delivery with priority in disaster relief. (English) Zbl 1524.90098
Summary: Rapid delivery of emergency supplies is of vital importance in disaster relief, and innovative means of delivery has been actively explored. Recently, a novel delivery approach that takes advantage of both trucks and drones is emerging in the commercial field. This synchronized truck-drone delivery (STDD) mode can benefit from the large capacity of trucks as well as the speed and flexibility of drones, which makes it promising for sending ungently-needed supplies to disaster-stricken sites, especially the areas severely damaged and thus inaccessible by trucks. This paper attempts to optimize the synchronized truck-drone paths for quick responses in disaster relief, when accounting for the priority of different disaster-stricken sites. We propose an integer programming model and develop exact algorithm to solve small-scale problems. For large-scale problems, we propose an algorithm based on dynamic programming. We verify that the STDD mode is more efficient than truck-only delivery. Further numerical analysis suggests that a drone with higher speed and longer endurance is not always the best choice. The efficiency of rescue efforts relies on careful calibration of the speed ratio of the drone to the truck and the maximum flight distance of the drone. Finally, the application of the model is illustrated by a case study of the 2008 earthquake at Wenchuan County in Sichuan Province of China.
References:
| [1] | N. P. M. Agatz Bouman Schmidt, Optimization approaches for the traveling salesman problem with drone, Transportation Science, 52, 965-981 (2018) · doi:10.1002/net.21864 |
| [2] | N. W. G. Altay Green, OR/MS research in disaster operations management, European Journal of Operational Research, 175, 475-493 (2006) · Zbl 1137.90574 · doi:10.1016/j.ejor.2005.05.016 |
| [3] | A. F. M. P. Ayough Farhadi Zandieh Rastkhadiv, Genetic algorithm for obstacle location-allocation problems with customer priorities, Journal of Industrial and Management Optimization, 17, 1753-1769 (2021) · Zbl 1476.90069 · doi:10.3934/jimo.2020044 |
| [4] | J. E. Beasley, Route first-cluster second methods for vehicle routing, Omega, 11, 403-408 (1983) · doi:10.1016/0305-0483(83)90033-6 |
| [5] | C. M. P. Fikar Gronalt Hirsch, A decision support system for coordinated disaster relief distribution, Expert Systems with Applications, 57, 104-116 (2016) · doi:10.1016/j.eswa.2016.03.039 |
| [6] | E. R. A. Garone Naldi Casavola, Traveling salesman problem for a class of carrier-vehicle systems, Journal of Guidance Control and Dynamics, 34, 1272-1276 (2011) · doi:10.2514/1.50539 |
| [7] | E. Garone, R. Naldi, A. Casavola and E. Frazzoli, Cooperative mission planning for a class of carrier-vehicle systems, In: 49th IEEE Conference on Decision and Control (CDC), (2010), 1354-1359. |
| [8] | P. L. D. J. L. M. J. M. Gonzalez-R Canca Andrade-Pineda Calle Leon-Blanco, Truck-drone team logistics: A heuristic approach to multi-drop route planning, Transportation Research Part C: Emerging Technologies, 114, 657-680 (2020) · doi:10.1016/j.trc.2020.02.030 |
| [9] | 7-Eleven, Flirtey make first FAA-approved drone delivery to home, Report of GPS World Staff, 2016. Available from: https://www.gpsworld.com/7-eleven-flirtey-make-first-faa-approved-drone-delivery-to-home/., |
| [10] | Q. M. Y. Q. D. M. H. Ha Deville Pham \(H \grave{a} \), On the min-cost traveling salesman problem with drone, Transportation Research Part C: Emerging Technologies, 86, 597-621 (2018) · doi:10.1016/j.trc.2017.11.015 |
| [11] | Q. M. Y. Q. D. M. H. Ha Deville Pham \(H \grave{a} \), A hybrid genetic algorithm for the traveling salesman problem with drone., Journal of Heuristics, 26, 219-247 (2020) · doi:10.1007/s10732-019-09431-y |
| [12] | E. U. N. T. S. Jacobson Argon Ziya, Priority assignment in emergency response, Operations Research, 60, 813-832 (2012) · Zbl 1260.90103 · doi:10.1287/opre.1120.1075 |
| [13] | S. S. J. K. Jin Jeong Kim Kim, A logistics model for the transport of disaster victims with various injuries and survival probabilities, Annals of Operations Research, 230, 17-33 (2015) · Zbl 1317.90049 · doi:10.1007/s10479-013-1515-0 |
| [14] | P. M. M. S. J. M. P. A. Kitjacharoenchai Ventresca Moshref-Javadi Lee Tanchoco Brunese, Multiple traveling salesman problem with drones: Mathematical model and heuristic approach, Computers and Industrial Engineering, 129, 14-30 (2019) · doi:10.1016/j.cie.2019.01.020 |
| [15] | J. B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical Society, 7, 48-50 (1956) · Zbl 0070.18404 · doi:10.1090/S0002-9939-1956-0078686-7 |
| [16] | D. M. Z. Z. M. Lei Cui Li, A dynamical artificial bee colony for vehicle routing problem with drones, Engineering Applications of Artificial Intelligence, 107, 104510 (2022) · doi:10.1016/j.engappai.2021.104510 |
| [17] | M. L. S. A. W. Y. X. B. Li Zhen Wang Lv Qu, Unmanned aerial vehicle scheduling problem for traffic monitoring, Computers and Industrial Engineering, 122, 15-23 (2018) · doi:10.1016/j.cie.2018.05.039 |
| [18] | M. McFarland, UPS drives may tag team deliveries with drones, Report of Business, 2017. |
| [19] | C. C. A. G. Murray Chu, The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery, Transportation Research Part C: Emerging Technologies, 54, 86-109 (2015) · doi:10.1016/j.trc.2015.03.005 |
| [20] | C. C. R. Murray Raj, The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones, Transportation Research Part C: Emerging Technologies, 110, 368-398 (2020) · doi:10.1016/j.trc.2019.11.003 |
| [21] | K. G. Orphanides, Drones can now land on moving cars, Report of Wired, 2016. |
| [22] | M. L. M. M. Marineelli Caggiani Ottomanelli Dell’Orco, En-route truck-drone parcel delivery for optimal vehicle routing strategies, Iet Intelligent Transport Systems, 12, 253-261 (2018) · doi:10.1049/iet-its.2017.0227 |
| [23] | S. B. Poikonen Golden, Multi-visit drone routing problem, Computers and Operations Research, 113, 104802 (2020) · Zbl 1458.90128 · doi:10.1016/j.cor.2019.104802 |
| [24] | N. G. F. D. Q. B. M. Samuel Diego Elias Abraham, A memetic algorithm for the cumulative capacitated vehicle routing problem including priority indexes, Applied Sciences-Basel, 10, 3943 (2020) · doi:10.3390/app10113943 |
| [25] | F. U. Tamke Buscher, A branch-and-cut algorithm for the vehicle routing problem with drones, Transportation Research Part B-Methdological, 144, 174-203 (2021) · doi:10.1016/j.trb.2020.11.011 |
| [26] | P. A. Tu, N. T. Dat and P. Q. Dung, Traveling salesman problem with multiple drones, in Proceedings of the Ninth International Symposium on Information and Communication Technology, Association for Computing Machinery, New York, USA, (2018), 46-53. |
| [27] | M. W. B. W. Ulmer Thomas, Same-day delivery with heterogeneous fleets of drones and vehicles, Networks, 72, 475-505 (2018) · doi:10.1002/net.21855 |
| [28] | D. S. P. J. X. P. T. P. M. L. Wang Hu Du Zhou Deng Hu, Routing and scheduling for hybrid truck-drone collaborative parcel delivery with independent and truck-carried drones, IEEE Internet of Things Journal, 6, 10483-10495 (2019) · doi:10.1109/JIOT.2019.2939397 |
| [29] | X. Y. S. B. Wang Poikonen Golden, The vehicle routing problem with drones: Several worst-case results, Optimization Letters, 11, 679-697 (2017) · Zbl 1367.90012 · doi:10.1007/s11590-016-1035-3 |
| [30] | Wenchuan 8.0 Magnitude Earthquake Intensity Distribution Map, Report of China Earthquake Administration, 2008. |
| [31] | Alibaba’s Drones Deliver Packages to Islands, Report of Xinhua, 2017. |
| [32] | D. McClean, Earth Day: 2020 Saw a Major Rise in Floods and Storms, Report of United Nations Office for Disaster Risk Reduction, 2021. |
| [33] | R. X. P. X. N. R. Yan Zhu Zhu Peng, Optimal routes and aborting strategies of trucks and drones under random attacks, Reliability Engineering and System Safety, 222, 108457 (2022) · doi:10.1016/j.ress.2022.108457 |
| [34] | L. Y. M. Y. S. J. Zhu Gong Xu Gu, Emergency relief routing models for injured victims considering equity and priority, Annals of Operations Research, 283, 1573-1606 (2019) · Zbl 1433.90035 · doi:10.1007/s10479-018-3089-3 |
| [35] | G. W. N. S. F. J. Zhang Zhu Ma Xia, Humanitarian relief network assessment using collaborative truck-and-drone system, Transportation Research Part E-Logistics and Transportation Review, 152, 102417 (2021) · doi:10.1016/j.tre.2021.102417 |
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.
