An Exact Algorithm to Solve Vehicle Routing Problem with Drones for Delivery and Surveillance Tasks After Disasters

References

• Abramson DM, Redlener I (2012) Hurricane Sandy: Lessons learned, again. Disaster Medical Public Health Preparation 6(4):328–329.Crossref, Google Scholar
• Agatz N, Bouman P, Schmidt M (2018) Optimization approaches for the traveling salesman problem with drone. Transportation Sci. 52(4):965–981.Link, Google Scholar
• Beraldi P, Chagas GO, Coelho LC, Laganà D (2024) A Dynamic Drone Routing Problem with Uncertain Demand and Energy Consumption (Université Laval, Faculté des Sciences de l’Administration, Québec).Google Scholar
• Bravo RZB, Leiras A, Cyrino Oliveira FL (2019) The use of UAVs in humanitarian relief: An application of POMDP-based methodology for finding victims. Production Oper. Management 28(2):421–440.Crossref, Google Scholar
• Caunhye AM, Nie X, Pokharel S (2012) Optimization models in emergency logistics: A literature review. Socio-Econom. Planning Sci. 46(1):4–13.Crossref, Google Scholar
• Chowdhury S, Shahvari O, Marufuzzaman M, Li X, Bian L (2021) Drone routing and optimization for post-disaster inspection. Comput. Industrial Engrg. 159:107495.Crossref, Google Scholar
• Cui P, Chen X, Zhu Y, Su F, Wei F, Han Y, Liu H, et al. (2011) The Wenchuan earthquake (May 12, 2008), Sichuan province, China, and resulting geohazards. Natl. Hazards 56:19–36.Crossref, Google Scholar
• Das DN, Sewani R, Wang J, Tiwari MK (2020) Synchronized truck and drone routing in package delivery logistics. IEEE Trans. Intelligent Transportation Systems 22(9):5772–5782.Crossref, Google Scholar
• Daud SMSM, Yusof MYPM, Heo CC, Khoo LS, Singh MKC, Mahmood MS, Nawawi H (2022) Applications of drone in disaster management: A scoping review. Sci. Justice 62(1):30–42.Crossref, Google Scholar
• Deng M, Li Y, Ding J, Zhou Y, Zhang L (2024) Stochastic and robust truck-and-drone routing problems with deadlines: A Benders decomposition approach. Transportation Res. Part E: Logist. Transportation Rev. 190:103709.Crossref, Google Scholar
• DJI (2023) DJI flycart 30, DJI’s first delivery drone, released: Ushering in a new era of low-altitude delivery. Accessed October 19, 2023, https://www.dji.com/cn/newsroom/news/fly-cart-30-cn.Google Scholar
• Escribano Macias J, Goldbeck N, Hsu PY, Angeloudis P, Ochieng W (2020) Endogenous stochastic optimisation for relief distribution assisted with unmanned aerial vehicles. OR Spectrum 42(4):1089–1125.Crossref, Google Scholar
• Faiz TI, Vogiatzis C, Noor-E-Alam M (2024) Computational approaches for solving two-echelon vehicle and UAV routing problems for post-disaster humanitarian operations. Expert Systems Appl. 237:121473.Crossref, Google Scholar
• Faiz TI, Vogiatzis C, Liu J, Noor-E-Alam M (2024) A robust optimization framework for two-echelon vehicle and UAV routing for post-disaster humanitarian logistics operations. Networks 84(2):200–219.Crossref, Google Scholar
• Gao J, Zhen L, Laporte G, He X (2023) Scheduling trucks and drones for cooperative deliveries. Transportation Res. Part E: Logist. Transportation Rev. 178:103267.Crossref, Google Scholar
• Gurobi Optimization, LLC (2024) Gurobi Optimizer reference manual. Accessed March 3, 2025, https://www.gurobi.com.Google Scholar
• Jessie Y (2023) Hong kong paralyzed by flash flooding after heaviest rainfall since 1884. Accessed October 19, 2023, https://edition.cnn.com/2023/09/07/asia/hong-kong-black-rainstorm-flooding-intl-hnk/index.html.Google Scholar
• Jiang Z, Ouyang Y (2021) Reliable location of first responder stations for cooperative response to disasters. Transportation Res. Part B: Methodological 149:20–32.Crossref, Google Scholar
• Joo J, Lee C (2025) A branch-and-price algorithm for robust drone-vehicle routing problem with time windows. INFORMS J. Comput. 1–24.Google Scholar
• Kang M, Lee C (2021) An exact algorithm for heterogeneous drone-truck routing problem. Transportation Sci. 55(5):1088–1112.Link, Google Scholar
• Kuo R, Lu S, Lai P, Mara STW (2022) Vehicle routing problem with drones considering time windows. Expert Systems Appl. 191:116264.Crossref, Google Scholar
• Levin MW, Rey D (2023) Branch-and-price for drone delivery service planning in urban airspace. Transportation Sci. 57(4):843–865.Link, Google Scholar
• Long Y, Xu G, Zhao J, Xie B, Fang M (2024) Dynamic truck–UAV collaboration and integrated route planning for resilient urban emergency response. IEEE Trans. Engrg. Management 71:9826–9838.Crossref, Google Scholar
• Luo Z, Qin H, Zhu W, Lim A (2016) Branch-and-price-and-cut for the manpower routing problem with synchronization constraints. Naval Res. Logist. 63(2):138–171.Crossref, Google Scholar
• Macrina G, Pugliese LDP, Guerriero F, Laporte G (2020) Drone-aided routing: A literature review. Transportation Res. Part C: Emerging Tech 120:102762.Crossref, Google Scholar
• Masmoudi MA, Mancini S, Baldacci R, Kuo YH (2022) Vehicle routing problems with drones equipped with multi-package payload compartments. Transportation Res. Part E: Logist. Transportation Rev. 164:102757.Crossref, Google Scholar
• Momeni M, Soleimani H, Shahparvari S, Afshar-Nadjafi B (2022) Coordinated routing system for fire detection by patrolling trucks with drones. Internat. J. Disaster Risk Reduction 73:102859.Crossref, Google Scholar
• Murray CC, Chu AG (2015) The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Res. Part C: Emerging Tech. 54:86–109.Crossref, Google Scholar
• Nedjati A, Vizvari B, Izbirak G (2016) Post-earthquake response by small UAV helicopters. Natl. Hazards 80(3):1669–1688.Crossref, Google Scholar
• Oruc BE, Kara BY (2018) Post-disaster assessment routing problem. Transportation Res. Part B: Methodological 116:76–102.Crossref, Google Scholar
• Otto A, Golden B, Lorenz C, Luo Y, Pesch E, Rocha LA (2025) On delivery policies for a truckand-drone tandem in disaster relief. IISE Trans. 57(10):1198–1214.Google Scholar
• Park JH, Park SH, Kim KA (2019) Disaster management and land administration in south Korea: Earthquakes and the real estate market. Land Use Policy 85:52–62.Crossref, Google Scholar
• Peng W, Wang D, Yin Y, Cheng T (2025) Multi-agent deep reinforcement learning-based truck-drone collaborative routing with dynamic emergency response. Transportation Res. Part E: Logist. Transportation Rev. 195:103974.Crossref, Google Scholar
• Poikonen S, Golden B (2020) The mothership and drone routing problem. INFORMS J. Comput. 32(2):249–262.Link, Google Scholar
• Poikonen S, Golden B, Wasil EA (2019) A branch-and-bound approach to the traveling salesman problem with a drone. INFORMS J. Comput. 31(2):335–346.Link, Google Scholar
• Poikonen S, Wang X, Golden B (2017) The vehicle routing problem with drones: Extended models and connections. Networks 70(1):34–43.Crossref, Google Scholar
• Ponza A (2016) Optimization of drone-assisted parcel delivery. MS thesis, University of Padova, Padova, Italy.Google Scholar
• Rabta B, Wankmüller C, Reiner G (2018) A drone fleet model for last-mile distribution in disaster relief operations. Internat. J. Disaster Risk Reduction 28:107–112.Crossref, Google Scholar
• Rezapour S, Naderi N, Morshedlou N, Rezapourbehnagh S (2018) Optimal deployment of emergency resources in sudden onset disasters. Internat. J. Production Econom. 204:365–382.Crossref, Google Scholar
• Robusto CC (1957) The cosine-haversine formula. Amer. Math. Monthly 64(1):38–40.Crossref, Google Scholar
• Rottondi C, Malandrino F, Bianco A, Chiasserini CF, Stavrakakis I (2021) Scheduling of emergency tasks for multiservice UAVs in post-disaster scenarios. Comput. Networks 184:107644.Crossref, Google Scholar
• Salama MR, Srinivas S (2022) Collaborative truck multi-drone routing and scheduling problem: Package delivery with flexible launch and recovery sites. Transportation Res. Part E: Logist. Transportation Rev. 164:102788.Crossref, Google Scholar
• Schermer D, Moeini M, Wendt O (2019) A matheuristic for the vehicle routing problem with drones and its variants. Transportation Res. Part C: Emerging Tech. 106:166–204.Crossref, Google Scholar
• SCMP (2023) Typhoon saola aftermath: Hong kong wakes to fallen trees and debris, but damage not as bad as feared. Accessed October 19, 2023, https://www.scmp.com/yp/discover/news/hong-kong/article/3233188/hong-kong-downgrades-t10-warning-t8-typhoon-saola-departs-signal-remain-force-until-4pm-least.Google Scholar
• She R, Ouyang Y (2024) Hybrid truck–drone delivery under aerial traffic congestion. Transportation Res. Part B: Methodological 185:102970.Crossref, Google Scholar
• Sheu JB (2024) Mass evacuation planning for disasters management: A household evacuation route choice behavior analysis. Transportation Res. Part E: Logist. Transportation Rev. 186:103544.Crossref, Google Scholar
• Siu T, Master F (2023) Hong Kong, Shenzhen deluged by heaviest rain on record. Accessed October 19, 2023, https://www.reuters.com/world/asia-pacific/hong-kongs-heaviest-rain-least-140-years-floods-city-streets-metro-2023-09-08/.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
• Tamke F, Buscher U (2021) A branch-and-cut algorithm for the vehicle routing problem with drones. Transportation Res. Part B: Methodological 144:174–203.Crossref, Google Scholar
• van Steenbergen RM, van Heeswijk WJA, Mes MRK (2025) The stochastic dynamic postdisaster inventory allocation problem with trucks and UAVs. Transportation Sci. 59(2):360–390.Link, Google Scholar
• Wang Z, Sheu JB (2019) Vehicle routing problem with drones. Transportation Res. Part B: Methodological 122:350–364.Crossref, Google Scholar
• Wang K, Yuan B, Zhao M, Lu Y (2020) Cooperative route planning for the drone and truck in delivery services: A bi-objective optimisation approach. J. Oper. Res. Soc. 71(10):1657–1674.Crossref, Google Scholar
• Xia Y, Zeng W, Zhang C, Yang H (2023) A branch-and-price-and-cut algorithm for the vehicle routing problem with load-dependent drones. Transportation Res. Part B: Methodological 171:80–110.Crossref, Google Scholar
• Xie S, Li X, Ouyang Y (2015) Decomposition of general facility disruption correlations via augmentation of virtual supporting stations. Transportation Res. Part B: Methodological 80:64–81.Crossref, Google Scholar
• Yakushiji K, Fujita H, Murata M, Hiroi N, Hamabe Y, Yakushiji F (2020) Short-range transportation using unmanned aerial vehicles (UAVs) during disasters in Japan. Drones 4(4):68.Crossref, Google Scholar
• Yang X, Cao W, Wang K, Yin H, Wu J, Wu L (2025) Integrated scheduling of truck and drone fleets for cargo transportation in post-disaster relief: A two-stage stochastic optimization approach. Transportation Res. Part E: Logist. Transportation Rev. 196:104015.Crossref, Google Scholar
• Yin Y, Yang Y, Yu Y, Wang D, Cheng T (2023) Robust vehicle routing with drones under uncertain demands and truck travel times in humanitarian logistics. Transportation Res. Part B: Methodological 174:102781.Crossref, Google Scholar
• Zeng F, Chen Z, Clarke JP, Goldsman D (2022) Nested vehicle routing problem: Optimizing drone-truck surveillance operations. Transportation Res. Part C: Emerging Tech. 139:103645.Crossref, Google Scholar
• Zhang G, Zhu N, Ma S, Xia J (2021) Humanitarian relief network assessment using collaborative truck-and-drone system. Transportation Res. Part E: Logist. Transportation Rev. 152:102417.Crossref, Google Scholar
• Zhen L, Gao J, Tan Z, Wang S, Baldacci R (2023) Branch-price-and-cut for trucks and drones cooperative delivery. IISE Trans. 55(3):271–287.Crossref, Google Scholar
• Zhou H, Qin H, Cheng C, Rousseau LM (2023) An exact algorithm for the two-echelon vehicle routing problem with drones. Transportation Res. Part B: Methodological 168:124–150.Crossref, Google Scholar