A Multi-Visit Heterogeneous Drone Routing Model Considering Recharging Decision in Disaster

Document Type : Research Paper


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


The complex nature of disasters has required communities and governments to implement plans to reduce the disturbing effects of these disasters. With the breakdown and destruction of road infrastructure in times of disaster, the need to use an Unmanned Aerial Vehicle (UAV) fleet under the concept of humanitarian logistics has become increasingly essential. Therefore, we present a Multi-Visit Drone Routing Problem in this paper. The relief goods are delivered to the disaster-affected areas by using heterogeneous drones. We use a linear approximation function to calculate energy consumption. We formulated the proposed bi-objective Mixed Integer Linear Programming (MILP) model by a compromise programming method. To validate the proposed model and to show the model’s efficiency, we generate several test problems with the data extracted by experts. The computational results show the satisfactory performance of the model for the delivery of relief items to the damaged nodes by humanitarian drones in the shortest possible time.


       [1]        Center for Research on the Epidemiology of Disasters (CRED). EM-DAT: The International Disaster Database. Brussels, Belgium: Ecole de Sante Publique, Universite Catholique de Louvain
       [2]        Tricoire, F., Graf, A., and Gutjahr, W. J. (2012). The bi-objective stochastic covering tour problem. Computers and operations research39(7), 1582-1592.
       [3]        Abounacer, R., Rekik, M., and Renaud, J. (2014). An exact solution approach for multi-objective location–transportation problem for disaster response. Computers and Operations Research41, 83-93.
       [4]        Rabta, B., Wankmüller, C., and Reiner, G. (2018). A drone fleet model for last-mile distribution in disaster relief operations. International Journal of Disaster Risk Reduction28, 107-112.
       [5]        Kouadio, I. K., Aljunid, S., Kamigaki, T., Hammad, K., and Oshitani, H. (2012). Infectious diseases following natural disasters: prevention and control measures. Expert review of anti-infective therapy10(1), 95-104.
       [6]        Hirschinger, M. (2016). No vehicle means no aid–A paradigm change for the humanitarian logistics business model. In Essays on Supply Chain Management in Emerging Markets (pp. 43-64). Springer Gabler, Wiesbaden.
       [7]        Sudbury, A. W., and Hutchinson, E. B. (2016). A cost analysis of amazon prime air (drone delivery). Journal for Economic Educators16(1), 1-12.
       [8]        Glaser, A. (2018). Watch Amazon’s Prime Air make its first public US drone delivery (2017).
       [9]        Vincent, J. (2017). Google’s Project Wing has successfully tested its air traffic control system for drones.
     [10]      Agatz, N., Bouman, P., and Schmidt, M. (2018). Optimization approaches for the traveling salesman problem with drone. Transportation Science52(4), 965-981.
     [11]      Chowdhury, S., Emelogu, A., Marufuzzaman, M., Nurre, S. G., and Bian, L. (2017). Drones for disaster response and relief operations: A continuous approximation model. International Journal of Production Economics188, 167-184.
     [12]      Mishra, B., Garg, D., Narang, P., and Mishra, V. (2020). Drone-surveillance for search and rescue in natural disaster. Computer Communications156, 1-10.
     [13]      Flammini, F., Pragliola, C., and Smarra, G. (2016, November). Railway infrastructure monitoring by drones. In 2016 International Conference on Electrical Systems for Aircraft, Railway, Ship Propulsion and Road Vehicles and International Transportation Electrification Conference (ESARS-ITEC) (pp. 1-6). IEEE.
     [14]      Bayram, V., and Yaman, H. (2018). A stochastic programming approach for shelter location and evacuation planning. RAIRO-Operations Research52(3), 779-805.
     [15]      Oladi, S., Bashiri, M., and Nikzad, E. (2018). An Algorithm for the Multi-Stage Stochastic Relief Routing Problem. Advances in Industrial Engineering, 52(3), 325-336.
     [16]      Camacho-Vallejo, J. F., González-Rodríguez, E., Almaguer, F. J., and González-Ramírez, R. G. (2015). A bi-level optimization model for aid distribution after the occurrence of a disaster. Journal of Cleaner Production105, 134-145.
     [17]      Tzeng, G. H., Cheng, H. J., and Huang, T. D. (2007). Multi-objective optimal planning for designing relief delivery systems. Transportation Research Part E: Logistics and Transportation Review43(6), 673-686.
     [18]      Ozdamar, L. (2011). Planning helicopter logistics in disaster relief. OR spectrum33(3), 655-672.
     [19]      Sahin, H., Kara, B. Y., and Karasan, O. E. (2016). Debris removal during disaster response: A case for Turkey. Socio-Economic Planning Sciences53, 49-59.
     [20]      Berktaş, N., Kara, B. Y., and Karaşan, O. E. (2016). Solution methodologies for debris removal in disaster response. EURO Journal on Computational Optimization4(3), 403-445.
     [21]      Ebrahimnejad, S., Bakhtiari, M., and Yavari-Moghaddam, M. (2019). A Mathematical Model for Solving Location-Routing Problem with Simultaneous Pickup and Delivery Using a Robust Optimization Approach. Advances in Industrial Engineering, 53(4), 185-208.
     [22]      Caunhye, A. M., Zhang, Y., Li, M., and Nie, X. (2016). A location-routing model for prepositioning and distributing emergency supplies. Transportation research part E: logistics and transportation review90, 161-176.
     [23]      Nedjati, A., Izbirak, G., and Arkat, J. (2017). Bi-objective covering tour location routing problem with replenishment at intermediate depots: Formulation and meta-heuristics. Computers and Industrial Engineering110, 191-206.
     [24]      Macrina, G., Pugliese, L. D. P., Guerriero, F., and Laporte, G. (2020). Drone-aided routing: A literature review. Transportation Research Part C: Emerging Technologies120, 102762.
     [25]      Choi, Y., and Schonfeld, P. M. (2017, January). Optimization of multi-package drone deliveries considering battery capacity. In Proceedings of the 96th Annual Meeting of the Transportation Research Board, Washington, DC, USA (pp. 8-12).
     [26]      San, K. T., Lee, E. Y., and Chang, Y. S. (2016, October). The delivery assignment solution for swarms of UAVs dealing with multi-dimensional chromosome representation of genetic algorithm. In 2016 IEEE 7th Annual Ubiquitous Computing, Electronics and Mobile Communication Conference (UEMCON) (pp. 1-7). IEEE.
     [27]      Dorling, K., Heinrichs, J., Messier, G. G., and Magierowski, S. (2016). Vehicle routing problems for drone delivery. IEEE Transactions on Systems, Man, and Cybernetics: Systems47(1), 70-85.
     [28]      Troudi, A., Addouche, S. A., Dellagi, S., and Mhamedi, A. E. (2018). Sizing of the drone delivery fleet considering energy autonomy. Sustainability10(9), 3344.
     [29]      Figliozzi, M. A. (2017). Lifecycle modeling and assessment of unmanned aerial vehicles (Drones) CO2e emissions. Transportation Research Part D: Transport and Environment57, 251-261.
     [30]      Liu, Z., Sengupta, R., and Kurzhanskiy, A. (2017, June). A power consumption model for multi-rotor small unmanned aircraft systems. In 2017 International Conference on Unmanned Aircraft Systems (ICUAS) (pp. 310-315). IEEE.
     [31]      Zhang, J., Campbell, J. F., Sweeney II, D. C., and Hupman, A. C. (2020). Energy consumption models for delivery drones: A comparison and assessment. Transportation Research Part D: Transport and Environment90, 102668.
     [32]      Chmaj, G., and Selvaraj, H. (2015). Distributed processing applications for UAV/drones: a survey. In Progress in Systems Engineering (pp. 449-454). Springer, Cham.
     [33]      Garapati, K., Roldán, J. J., Garzón, M., del Cerro, J., and Barrientos, A. (2017, November). A game of drones: Game theoretic approaches for multi-robot task allocation in security missions. In Iberian robotics conference (pp. 855-866). Springer, Cham
     [34]      Alfeo, A. L., Cimino, M. G., and Vaglini, G. (2019). Enhancing biologically inspired swarm behavior: Metaheuristics to foster the optimization of UAVs coordination in target search. Computers and Operations Research110, 34-47.
     [35]      Zema, N. R., Natalizio, E., and Yanmaz, E. (2017, May). An unmanned aerial vehicle network for sport event filming with communication constraints. In First International Balkan Conference on Communications and Networking (Balkancom 2017).
     [36]      Molina, P., Colomina, I., Victoria, T., Skaloud, J., Kornus, W., Prades, R., and Aguilera, C. (2012). Searching lost people with UAVs: the system and results of the close-search project. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences39(CONF), 441-446.
     [37]      Scott, J., and Scott, C. (2017, January). Drone delivery models for healthcare. In Proceedings of the 50th Hawaii international conference on system sciences.
     [38]      Huang, H., Long, J., Yi, W., Yi, Q., Zhang, G., and Lei, B. (2017). A method for using unmanned aerial vehicles for emergency investigation of single geo-hazards and sample applications of this method. Natural Hazards and Earth System Sciences17(11), 1961-1979.
     [39]      Choi-Fitzpatrick, A., Chavarria, D., Cychosz, E., Dingens, J. P., Duffey, M., Koebel, K, and Almquist, L. (2016). Up in the Air: A Global Estimate of Non-Violent Drone Use 2009-2015.
     [40]      Mosterman, P. J., Sanabria, D. E., Bilgin, E., Zhang, K., and Zander, J. (2014). A heterogeneous fleet of vehicles for automated humanitarian missions. Computing in Science and Engineering16(3), 90-95.
     [41]      Chowdhury, S. (2020). Drone routing and optimization for post-disaster inspection (Doctoral dissertation, Mississippi State University).
     [42]      Rottondi, C., Malandrino, F., Bianco, A., Chiasserini, C. F., and Stavrakakis, I. (2020). Scheduling of emergency tasks for multiservice UAVs in post-disaster scenarios. Computer Networks, 107644.
     [43]      Yadav, Y., Narasimhamurthy, A., 2017. Algorithms for solving the vehicle routing problem with drones. In: 2017 Ninth International Conference on Advances in Pattern Recognition (ICAPR), IEEE, Bangalore, India
     [44]      Liu, Y. (2019). An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones. Computers and Operations Research111, 1-20.
     [45]      Poikonen, S., and Golden, B. (2020). Multi-visit drone routing problem. Computers and Operations Research113, 104802.