A Hybrid Truck-Drone Routing Problem Considering Deprivation Cost in the Post-Disaster Situation

Document Type : Research Paper

Authors

Department of Industrial Engineering, K. N. Toosi University of Technology, Tehran, Iran

10.22070/jqepo.2021.14935.1201

Abstract

Natural disasters and their destructive effects on life and property are the most important issues these days.  Implementation time of the relief operation and limitations associated with the ground infrastructure in disaster situations is the main priority of humanitarian logistics. So the necessity of using Unmanned Aerial Vehicles (UAVs) to reduce the service time is evident. On the Other hand, considering the deprivation cost function as an appropriate objective function can improve existing problems in disaster situations. This paper proposes a hybrid vehicle-drone routing model in the post-disaster phase. Multi trucks and multi drones with complementary capabilities are applied. Trucks are restricted to travel to the nodes with undamaged road networks, known as LD nodes. Drones can fly from the trucks to the nodes with damaged roads, known as DN nodes. They are used multiple times from each truck at LD nodes. The objective is to minimize the deprivation cost as a function of the deprivation time of both types of nodes. So by minimizing the deprivation cost, the vehicles' arrival times are minimized, and better routes are selected for vehicles. The effect of the population rate of the affected area on the route determination also is considered by the deprivation cost function. Finally, the validation of the proposed model is tested by solving it in GAMS software. Some examples are solved to show how applying the deprivation cost can improve the selecting routes by this model.

Keywords

References

Agatz, N., Bouman, P., & Schmidt, M. (2018). Optimization Approaches for the Traveling Salesman Problem with Drone. Transportation Science, 52(4):965-981.
AlMuhaideb, S., Alhussan, T., Alamri, S., Altwaijry, Y., Aljarbou, L., and Alrayes, H. (2021). Optimization of Truck-Drone Parcel Delivery Using Metaheuristics. Applied sciences, 11(14), 6443.
Al Theeb, N., & Murray, C. (2017). Vehicle routing and resource distribution in post-disaster humanitarian relief operations. International Transactions in Operational Research, 24(6), 1253-1284
Bektas, T. (2006). The multiple traveling salesman problem: An overview of formulations and solution procedures. Omega, 34(3), 209–219
Bertazzi, L., Golden, B., & Wang, X. (2015). Min-max vs. min-sum vehicle routing: A worst-case analysis. European Journal of Operational Research, 240(2), 372–381.
Bouman, P., Agatz, N., & Schmidt, M. (2018). Dynamic Programming Approaches for the Traveling Salesman Problem with Drone. Networks, 72(4), 528-542.
Campbell, J., Sweeney, D., & Zhang, J. (2017). Strategic Design for Delivery with Trucks and Drones(Tech.).
Carlsson, J. & Song, S. (2017). Coordinated logistics with a truck and a drone Management Science, 64(9), 3971-4470.
Cantillo V., Serrano I., Macea L.F., Holguín-Veras J. (2018). Discrete choice approach for assessing deprivation cost in humanitarian relief operations, Soc. Econ. Plan. Sci. 63
Cheng, C., Adulyasak, Y., & Rousseau, L. M. (2018). Formulations and Exact Algorithms for Drone Routing Problem. Working Paper.
Dascioglu, B. G., Vayvay, O., & Kalender, Z. T. (2019). Humanitarian Supply Chain Management: Extended Literature Review Industrial Engineering in the Big Data Era (pp. 443-459): Springer.
Dayarian, I., Savelsbergh, M., & Clarke, J. P. (2018). Same-Day Delivery with Drone Resupply. Technical Report. 2018. Available at: http://www. optimization-online. org/DB_FILE/2017/09/6206. pdf.
Dorling, K., Heinrichs, J., Messier, G. G., & Magierowski, S. (2017). Vehicle Routing Problems for Drone Delivery. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 47(1), 70-85.
Dell'Amico, M., Montemanni, R., & Novellani, S. (2020). Metaheuristic algorithms for the parallel drone scheduling traveling salesman problem. Annals of Operations Research, 289, 211-226.
Drexl, M. (2012). Synchronization in Vehicle Routing—A Survey of VRPs with Multiple Synchronization Constraints. Transportation Science, 46(3), 297-316.
de Freitas, J. C., & Penna, P. H. V. (2020). A variable neighborhood search for flying sidekick traveling salesman problem. International Transactions in Operational Research, 27, 267-290.
Gonz´ alez-R, L., Canca, D., Andrade-Pineda, J.L., Calle, M., (2020). Truck-drone team logistics: A heuristic approach to multi-drop route planning. Transport. Res. Part C: Emerg. Technol. 114, 657–680.
Gutjahr W.J., Fischer S., Equity and deprivation costs in humanitarian logistics, (2018). Eur. J. Oper. Res. 270 ,185–197
Hern, A. (2014). DHL launches first commercial drone 'parcelcopter' delivery service, https://www.theguardian.com/technology/2014/sep/25/german-dhl-launches-first commercial drone-delivery-service
Ha, Q., Deville, Y., Pham, Q., & Hà, M. (2018). On the min-cost Traveling Salesman Problem with Drone. Transportation Research Part C, 86, 597-621.
Ham, A. M. (2018). 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, 91, 1-14.
Holguín-Veras  J., Perez N., Jaller M., Van Wassenhove L.N., Aros-Vera F., (2013). On the appropriate objective function for post-disaster humanitarian logistics models, J. Oper. Manag. 31, 262–280
Hong, I., Kuby, M., & Murray, A. (2017). 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, 125-132.
Hughes, M. (2017). UPS successfully delivered a package with a drone. https://thenextweb.com/insider/2017/02/21/ups-successfully-delivered-package-drone/.
Jeong, H.Y., Lee, S., & Song, B.D. (2019) Truck-drone hybrid delivery routing: Payload-energy dependency and no-fly zones. International Journal of Production Economics.
Karak, A., & Abdelghany, K. (2019). The hybrid vehicle-drone routing problem for pickup and delivery services. Transportation Research Part C: Emerging Technologies, 102, 427-449.
Kim, S., & Moon, I. (2019). Traveling salesman problem with a drone station. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 49(1), 42-52.
Kitjacharoenchai, P., Ventresca, M., Moshref-Javadi, M., Lee, S., Tanchoco, J. M., & Brunese, P. A. (2019). Multiple traveling salesman problem with drones: Mathematical model and heuristic approach. Computers & Industrial Engineering, 129, 14-30.
Kivelevitch, E. H., Cohen, K., & Kumar, M. (2013). A binary programming solution to the min-max multiple-depots, multiple traveling salesman problem. AIAA Infotech@Aerospace (I@A) conference
Luo, Z., Liu, Z., & Shi, J. (2017). A two-echelon cooperated routing problem for a ground vehicle and its carried unmanned aerial vehicle. Sensors, 17(5), 1144.
Marinelli, M., Caggiani, L., Ottomanelli, M., & Dellorco, M. (2018). En route truck–drone parcel delivery for optimal vehicle routing strategies. IET Intelligent Transport Systems, 12(4), 253- 261.
Meola, A. (2017). Shop online and get your items delivery by a drone delivery service: The future Amazon and Domino's have envisioned for us. Retrieved from https://www.businessinsider.com/delivery-drones-market-service-2017-7
Murray, C. C., & Chu, A. G. (2015). The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies, 54, 86-109.
Murray, C. & Raj, R. (2019) The Multiple Flying Sidekicks Traveling Salesman Problem: Parcel Delivery with Multiple Drones. Available at SSRN: https://ssrn.com/abstract=3338436 or http://dx.doi.org/10.2139/ssrn.3338436
Otto, A., Agatz, N., Campbell, J., Golden, B., & Pesch, E. (2018). Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey. Networks, 72(4), 411-458
Ponza, A. (2015) Optimization of Drone-Assisted Parcel Delivery. http://tesi.cab.unipd.it/51947/1/Andrea_Ponza_Analisi_e_ottimizzazione_nell%27uso_di_droni _ per_la_consegna_di_prodotti.pdf
Poikonen, S., & Golden, B. (2020). Multi-visit drone routing problem. Computers & Operations Research, 113, 104802.
Poikonen, S., Wang, X., & Golden, B. (2017). The vehicle routing problem with drones: Extended models and connections. Networks, 70(1), 34-43.
Pugliese, L. D. P., & Guerriero, F. (2017). Last-Mile Deliveries by Using Drones and Classical Vehicles. In International Conference on Optimization and Decision Science (pp. 557-565). Springer, Cham.
Roberti, R.,  Ruthmair, M. (2021). Exact Methods for the Traveling Salesman Problem with Drone. Transportation Science, 55(2): 315-335.
Schermer, Daniel & Moeini, Mahdi & Wendt, Oliver. (2018). A Variable Neighborhood Search Algorithm for Solving the Vehicle Routing Problem with Drones.
Tu, P., Dat, N., & Dung, P. (2018). Traveling salesman problem with multiple drones. In Proceedings of the Ninth International Symposium on Information and Communication Technology, 46-53. ACM.
Ulmer, M. W., & Thomas, B. W. (2017). Same-day delivery with a heterogeneous fleet of drones and vehicles (pp. 1-30). Technical report.
Van Wassenhove, L.N., (2006). Humanitarian aid logistics: supply chain management in high gear. J. Operat. Res. Soc. 57 (5), 475–489.
Volkman, E. (2018, June 21). 8 Things That Can Be Delivered By Drone. Retrieved from https://tech.co/8-things-can-delivered-drone-2017-12.
Wang, X., Poikonen, S., & Golden, B. (2016). The vehicle routing problem with drones: Several worst-case results. Optimization Letters, 11(4), 679-697.
Wang, Z., & Sheu, J. B. (2019). Vehicle routing problem with drones. Transportation research part B: methodological, 122, 350-364.
Yurek, E. E., & Ozmutlu, H. C. (2018). A decomposition-based iterative optimization algorithm for traveling salesman problem with drone. Transportation Research Part C: Emerging Technologies, 91, 249-262.
Journal of Quality Engineering and Production Optimization
Volume 6, Issue 1
May 2021
Pages 233-256

Files

Share

How to cite

Statistics