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

Document Type : Research Paper

Authors

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

Abstract

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.

Keywords

References

       [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 research, 39(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 Research, 41, 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 Reduction, 28, 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 therapy, 10(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 Educators, 16(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 Science, 52(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 Economics, 188, 167-184.
     [12]      Mishra, B., Garg, D., Narang, P., and Mishra, V. (2020). Drone-surveillance for search and rescue in natural disaster. Computer Communications, 156, 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 Research, 52(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 Production, 105, 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 Review, 43(6), 673-686.
     [18]      Ozdamar, L. (2011). Planning helicopter logistics in disaster relief. OR spectrum, 33(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 Sciences, 53, 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 Optimization, 4(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 review, 90, 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 Engineering, 110, 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 Technologies, 120, 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: Systems, 47(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. Sustainability, 10(9), 3344.
     [29]      Figliozzi, M. A. (2017). Lifecycle modeling and assessment of unmanned aerial vehicles (Drones) CO2e emissions. Transportation Research Part D: Transport and Environment, 57, 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 Environment, 90, 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 Research, 110, 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 Sciences, 39(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 Sciences, 17(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 Engineering, 16(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 Research, 111, 1-20.
     [45]      Poikonen, S., and Golden, B. (2020). Multi-visit drone routing problem. Computers and Operations Research, 113, 104802.
Advances in Industrial Engineering
Volume 54, Issue 1
January 2020
Pages 53-73

Files

Share

How to cite

Statistics