Integration of Three Vehicle Fleet Types for Delivering Relief Supplies During a Natural Disaster
Article Sidebar
Main Article Content
Abstract
The combined use of trucks and drones in last-mile delivery offers a more efficient and faster way to make deliveries from an operational standpoint. In this paper, we propose a new routing model that combines different vehicle fleets, including hybrid trucks, traditional trucks, and large drones, to deliver packages from a depot to different destinations cooperatively. This research will give us a better understanding of this drone logistics application, particularly in routing optimization. It can be further implemented to mitigate the impacts of natural disasters, mainly earthquakes, flooding, and landslides. This research aims to study the possibility of using drones to deliver relief supplies such as food, water, and medicine for humanitarian purposes during natural disaster periods to find the best possible route to directly reach the destination and minimize the flying time in the air. We develop a Mixed Integer Programming (MIP) formulation to solve the I-VRPD optimally on a simulated small-scale problem and conduct a case study in one of the most affected regions by natural disasters. The numerical analysis demonstrates an improvement in the delivery time using three experiments that include testing the model on a set of benchmark problems and a case study based on the real scenario. The results show that the delivery time of the proposed model with the integration of three types of vehicle fleets can outperform the operation performed by a single-vehicle fleet by a significant percentage.
Article Details
References
T. Laseter, A. Tipping, and F. Duiven, “The Rise of the Last-Mile Exchange,” 2018. [Online]. Available: https://www.strategy-business.com/ article/The-Rise-of-the-Last-Mile-Exchange
A. Otto, N, Agatz, J. Campbell, B. Golden, and E. Pesch, “Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey,” Networks, vol. 72, no. 4, pp. 411–458, 2018.
S. Herrera, “The Drones Are Coming! How Amazon, Alphabet and Uber Are Taking to the Skies,” 2019. [Online]. Available: https:// www.wsj.com/articles/the-drones-are-coming- 11571995806
A. Hern, “DHL launches first commercial drone 'parcelcopter' delivery service,” 2014. [Online]. Available: https://www.theguardian.com/ technology/2014/sep/25/german-dhl-launchesfirst commercial-drone-delivery-service
C. C. Murray and A. G. Chu, “The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery,” Transportation Research Part C: Emerging Technologies, vol. 54, pp. 86–109, 2015.
A. J. Hawkins, “Elroy Air's massive cargo drone completes its first test flight,” 2019. [Online]. Available: https://www.theverge. com/2019/8/28/20812547/elroy-air-cargo-dronedelivery- test-flight-camp-roberts-san-francisco
F. Shivakumar, “Giant cargo drones will deliver packages farther and faster,” 2019. [Online]. Available: https://www.theverge. com/2019/6/10/18657150/autonomous-cargodrones- delivery-boeing-aircraft-faa-regulation
N. Boysen, S. Fedtke, and S. Schwerdfeger, “Last-mile delivery concepts: A survey from an operational research perspective,” OR Spectrum, vol. 43, pp. 1–58, 2020.
G. Macrina, L. D. P. Pugliese, F. Guerriero, and G. Laporte, “Drone-aided routing: A literature review,” Transportation Research Part C: Emerging Technologies, vol. 120, 2020, Art. no. 102762.
D. R. Viloria, E. L. Solano-Charris, A. Muñoz-Villamizar, and J. R. Montoya-Torres, “Unmanned aerial vehicles/drones in vehicle routing problems: A literature review,” International Transactions in Operational Research, vol. 28, no. 4, pp. 1626–1657, 2020.
J. F. Cordeau, G. Laporte, M. W. Savelsbergh, and D. Vigo, “Chapter 6 Vehicle Routing,” Transportation Handbooks in Operations Research and Management Science, vol. 14, pp. 367–428, 2007, doi: 10.1016/s0927-0507 (06)14006-2.
B. Golden, S. Raghavan, and E. Wasil, “The vehicle routing problem: Latest advances and new challenges,” in Operations Research/ Computer Science Interfaces. New York: Springer, 2008.
J. Krarup, “Vehicle routing: Methods and studies,” European Journal of Operational Research, vol. 38, no. 1, pp. 126–127, 1989.
P. Toth and D. Vigo, “Vehicle routing: Problems, methods, and applications,” in Society for Industrial and Applied Mathematics. Pennsylvania: Society for Industrial and Applied Mathematics, 2014.
A. Ponza, “Optimization of Drone-Assisted Parcel Delivery,” 2015. [Online]. Available: http://tesi.cab.unipd.it/51947/1/Andrea PonzaAnalisieottimizzazionenell%27usodidroni perlaconsegnadiprodotti.pdf
Q. M. Ha, Y. Deville, Q. D. Pham, and M. H. Hà, “On the min-cost traveling salesman problem with drone,” Transportation Research Part C: Emerging Technologies, vol. 86, pp. 597–621, 2018.
H. Y. Jeong, B. D. Song, and S. Lee, “Truck-drone hybrid delivery routing: Payload-energy dependency and No-Fly zones,” International Journal of Production Economics, vol. 214, pp. 220–233, 2019.
C. C. Murray and R. Raj, “The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones,” Transportation Research Part C: Emerging Technologies, vol. 110, pp. 368–398, 2020.
P. Kitjacharoenchai, M. Ventresca, M. Moshref- Javadi, S. Lee, J. M. Tanchoco, and P. A. Brunese, “Multiple traveling salesman problem with drones: Mathematical model and heuristic approach,” Computers & Industrial Engineering, vol. 129, pp. 14–30, 2019.
N. Agatz, P. Bouman, and M. Schmidt, “Optimization approaches for the traveling salesman problem with drone,” Transportation Science, vol. 52, no. 4, pp. 965–981, 2018.
P. Bouman, N. Agatz, and M. Schmidt, “Dynamic programming approaches for the traveling salesman problem with drone,” Networks, vol. 72, no. 4, pp. 528–542, 2018.
E. E. Yurek and H. C. Ozmutlu, “A decompositionbased iterative optimization algorithm for traveling salesman problem with drone,” Transportation Research Part C: Emerging Technologies, vol. 91, pp. 249–262, 2018.
M. Marinelli, L. Caggiani, M. Ottomanelli, and M. Dellorco, “En-route truck–drone parcel delivery for optimal vehicle routing strategies,” IET Intelligent Transport Systems, vol. 12 no. 4, pp. 253–261, 2018.
N. Mathew, S. L. Smith, and S. L. Waslander, “Planning paths for package delivery in heterogeneous multirobot teams,” IEEE Transactions on Automation Science and Engineering, vol. 12, no. 4, pp. 1298–1308, 2015.
P. Tu, N. Dat, and P. Dung, “Traveling salesman problem with multiple drones,” in Proceedings of the Ninth International Symposium on Information and Communication Technology, ACM, pp. 46–53, 2018.
S. Kim and I. Moon, “Traveling salesman problem with a drone station,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 49, no. 1, pp. 42–52, 2019.
S. M. Ferrandez, T. Harbison, T. Weber, R. Sturges, and R. Rich, “Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm,” Journal of Industrial Engineering and Management, vol. 9, no. 2, pp. 374–388, 2016.
S. Poikonen and B. Golden, “Multi-visit drone routing problem,” Computers & Operations Research, vol. 113, Art. 104802, 2020.
X. Wang, S. Poikonen, and B. Golden, “The vehicle routing problem with drones: Several worst-case results,” Optimization Letters, vol. 11, no. 4, pp. 679–697, 2016.
J. F. Campbell, D. Sweeney, and J. Zhang, “Strategic design for delivery with trucks and drones,” College of Business Administration, University of Missouri-St. Louis, Missouri, USA, Rep. SCMA-2017-0201, Apr. 2017.
J. G. Carlsson and S. Song, “Coordinated logistics with a truck and a drone,” Management Science, vol. 64, no. 9, pp. 4052–4069, 2018.
I. Hong, M. Kuby, and A. Murray, “A deviation flow refueling location model for continuous space: A commercial drone delivery system for urban areas,” Advances in Geocomputation Advances in Geographic Information Science, pp. 125–132, Art. no. 10727561, 2017.
D. Schermer, M. Daniel, and O. Wendt, “A variable neighborhood search algorithm for solving the vehicle routing problem with drones,” Technische Universitat Kaiserslautern, Germany, Rep. BISOR-02/2018, 2018.
K. Dorling, J. Heinrichs, G. G. Messier, and S. Magierowski, “Vehicle routing problems for drone delivery,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 47, no. 1, pp. 70–85, 2017.
A. M. Ham, “Integrated scheduling of m-truck, m-drone, and m-depot constrained by time- window, drop-pickup, and m-visit using constraint programming,” Transportation Research Part C: Emerging Technologies, vol. 91, pp. 1–14, 2018.
M. W. Ulmer and B. W. Thomas, “Same-day delivery with a heterogeneous fleet of drones and vehicles,” Networks, vol. 72, no. 4, pp. 475–505, 2018.
C. Cheng, Y. Adulyasak, and L. M. Rousseau, “Formulations and exact algorithms for drone routing problem,” Centre interuniversitaire de recherche sur les reseaux d'entreprise, la logistique et le transport, Université de Montréal, Canada, Rep. CIRRELT-2018-31, 2018
L. D. P. Pugliese and F. Guerriero, “Last-mile deliveries by using drones and classical vehicles,” in International Conference on Optimization and Decision Science, pp. 557–565 , 2017.
I. Dayarian, M. Savelsbergh, and J. P. Clarke, “Same-Day Delivery with Drone Resupply,” 2018. [Online]. Available: http://www.optimizationonline. org/DBFILE/2017/09/6206. pdf
Z. Luo, Z. Liu, and J. Shi, “A two-echelon cooperated routing problem for a ground vehicle and its carried unmanned aerial vehicle,” Sensors, vol. 17, no. 5, p. 1144, 2017.
A. Karak and K. Abdelghany, “The hybrid vehicle-drone routing problem for pick- up and delivery services,” Transportation Research Part C: Emerging Technologies, vol. 102, pp. 427–449, 2019.
Z. Wang and J. B. Sheu, “Vehicle routing problem with drones,” Transportation Research Part B: Methodological, vol. 122, pp. 350–364, 2019.
S. Poikonen and B. Golden, “Multi-visit drone routing problem,” Computers & Operations Research, vol. 113, Art. no. 104802, 2020.
S. Poikonen, X. Wang, and B. Golden, “The vehicle routing problem with drones: Extended models and connections,” Networks, vol. 70, no. 1, pp. 34–43, 2017.
P. Kitjacharoenchai, B. C. Min, and S. Lee, “Two echelon vehicle routing problem with drones in last mile delivery,” International Journal of Production Economics, vol. 225, Art. 107598, 2020.
K. Zhu, H. Bin, and Z. Tao. “Multi-UAV distributed collaborative coverage for target search using heuristic strategy,” Guidance, Navigation and Control, vol. 1, no. 1, Art. no. 2150002, 2021.
M. R. Salama and S. Srinivas, “Collaborative truck multi-drone routing and scheduling problem: Package delivery with flexible launch and recovery sites,” Transportation Research Part E: Logistics and Transportation Review, vol. 164, Art. no. 102788, 2022.
M. Desrochers and G. Laporte, “Improvements and extensions to the Miller-Tucker- Zemlin subtour elimination constraints,” Operations Research Letters, vol. 10, no.1, pp. 27–36, 1991.
S. Brar, R. Rabbat, V. Raithatha, G. Runcie, and A. Yu, “Drones for Deliveries,” 2015. [Online]. Available:http://scet.berkeley.edu/wp-content/ uploads/ConnCarProjectReport-1.pdf
P. Augerat, “VRP Problem Instances,” 1995. [Online]. Available: http://vrp.atd-lab.inf.puc-rio. br/index.php/en/
G. Clarke and J. R.Wright, “Scheduling of vehicle routing problem from a central depot to a number of delivery points,” Operations Research, vol. 12, pp. 568–581, 1964.
G. Laporte, “Fifty years of vehicle routing,” Transportation Science, vol. 43, no. 4, pp. 408– 416, 2009.