×

Drones for relief logistics under uncertainty after an earthquake. (English) Zbl 07709807

Summary: This study presents a post-disaster delivery problem called the relief distribution problem using drones under uncertainty, in which critical relief items are distributed to disaster victims gathered at assembly points after a disaster, particularly an earthquake. Because roads may be obstructed by debris after an earthquake, drones can be used as the primary transportation mode. As the impact of an earthquake cannot be easily predicted, the demand and road network uncertainties are considered. Additionally, the objective is to minimize the total unsatisfied demand subject to a time-bound constraint on the deliveries, as well as the range and capacity limitations of drones. A two-stage stochastic programming and its deterministic equivalent problem formulations are presented. The scenario decomposition algorithm is implemented as an exact solution approach. To apply this study to real-life applications, a case study is conducted based on the western (European) side of Istanbul, Turkey. The computational results are used to evaluate the performance of the scenario decomposition algorithm and analyze the value of stochasticity and the expected value of perfect information under different parametric settings. We additionally conduct sensitivity analyses by varying the key parameters of the problem, such as the time-bound and capacities of the drones.

MSC:

90Bxx Operations research and management science
Full Text: DOI

References:

[1] Ahmed, S., A scenario decomposition algorithm for 0-1 stochastic programs, Operations Research Letters, 41, 6, 565-569 (2013) · Zbl 1287.90041
[2] Amazon (2022). Amazon Prime Air prepares for drone deliveries. Available from: https://www.aboutamazon.com/news/transportation/amazon-prime-air-prepares-for-drone-deliveries [Accessed 5 September 2022].
[3] Anaya-Arenas, A. M.; Renaud, J.; Ruiz, A., Relief distribution networks: A systematic review, Annals of Operations Research, 223, 1, 53-79 (2014) · Zbl 1306.90021
[4] Balfour Beatty (2017). Flying into the future of bridge inspections. May 12, 2017. Available from: https://www.balfourbeatty.com/news/flying-into-the-future-of-bridge-inspections/ [Accessed 5 September 2022].
[5] Battarra, M.; Balcik, B.; Xu, H., Disaster preparedness using risk-assessment methods from earthquake engineering, European Journal of Operational Research, 269, 2, 423-435 (2018) · Zbl 1388.90078
[6] Bayrak, E.; Nas, M.; Bayrak, Y., New macroseismic intensity predictive models for turkey, Acta Geophysica, 67, 6, 1483-1513 (2019)
[7] Chauhan, D.; Unnikrishnan, A.; Figliozzi, M., Maximum coverage capacitated facility location problem with range constrained drones, Transportation Research Part C: Emerging Technologies, 99, 1-18 (2019)
[8] Chauhan, D. R.; Unnikrishnan, A.; Figliozzi, M.; Boyles, S. D., Robust maximum coverage facility location problem with drones considering uncertainties in battery availability and consumption, Transportation Research Record, 2675, 2, 25-39 (2021)
[9] Chowdhury, S.; Emelogu, A.; Marufuzzaman, M.; Nurre, S. G.; Bian, L., Drones for disaster response and relief operations: A continuous approximation model, International Journal of Production Economics, 188, 167-184 (2017)
[10] Chung, S. H.; Sah, B.; Lee, J., Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions, Computers and Operations Research, 123, 105004 (2020) · Zbl 1458.90072
[11] DHL (2018). Rapid response from the air: Medicines successfully delivered using a parcel drone in east africa. October 4, 2018. Available from: https://www.dhl.com/global-en/home/press/press-archive/2018/rapid-response-from-the-air-medicines-successfully-delivered-using-a-parcel-drone-in-east-africa.html [Accessed 5 September 2022].
[12] Dorling, K.; Heinrichs, J.; Messier, G. G.; Magierowski, S., Vehicle routing problems for drone delivery, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 47, 1, 70-85 (2017)
[13] Dukkanci, O.; Kara, B. Y.; Bektaş, T., Minimizing energy and cost in range-limited drone deliveries with speed optimization, Transportation Research Part C: Emerging Technologies, 125, 102985 (2021)
[14] Erbeyoğlu, G.; Bilge, Ü., A robust disaster preparedness model for effective and fair disaster response, European Journal of Operational Research, 280, 2, 479-494 (2020) · Zbl 1430.90077
[15] Erdik, M.; Eren, K., Attenuation of intensities for earthquake associated with the north anatolian fault (1983), Middle East Technical University Earthquake Engineering Research Center: Middle East Technical University Earthquake Engineering Research Center Ankara
[16] Faiz, T. I., Vogiatzis, C. et al. (2020). Robust two echelon vehicle and drone routing for post disaster humanitarian operations. arXiv preprint arXiv:2001.06456
[17] Fikar, C.; Gronalt, M.; Hirsch, P., A decision support system for coordinated disaster relief distribution, Expert Systems with Applications, 57, 104-116 (2016)
[18] Gentili, M.; Mirchandani, P. B.; Agnetis, A.; Ghelichi, Z., Locating platforms and scheduling a fleet of drones for emergency delivery of perishable items, Computers & Industrial Engineering, 168, 108057 (2022)
[19] Golabi, M.; Shavarani, S. M.; Izbirak, G., An edge-based stochastic facility location problem in UAV-supported humanitarian relief logistics: A case study of tehran earthquake, Natural Hazards, 87, 3, 1545-1565 (2017)
[20] Grass, E.; Fischer, K., Two-stage stochastic programming in disaster management: A literature survey, Surveys in Operations Research and Management Science, 21, 2, 85-100 (2016)
[21] Grass, E.; Fischer, K.; Rams, A., An accelerated l-shaped method for solving two-stage stochastic programs in disaster management, Annals of Operations Research, 284, 2, 557-582 (2020) · Zbl 1434.90106
[22] Holguín-Veras, J.; Pérez, N.; Jaller, M.; Van Wassenhove, L. N.; Aros-Vera, F., On the appropriate objective function for post-disaster humanitarian logistics models, Journal of Operations Management, 31, 5, 262-280 (2013)
[23] Huang, M.; Smilowitz, K.; Balcik, B., Models for relief routing: Equity, efficiency and efficacy, Transportation Research Part E: Logistics and Transportation Review, 48, 1, 2-18 (2012)
[24] Jeong, H. Y.; David, J. Y.; Min, B.-C.; Lee, S., The humanitarian flying warehouse, Transportation Research Part E: Logistics and Transportation Review, 136, 101901 (2020)
[25] Kim, D.; Lee, K.; Moon, I., Stochastic facility location model for drones considering uncertain flight distance, Annals of Operations Research, 283, 1, 1283-1302 (2019)
[26] Kyriakakis, N. A.; Marinaki, M.; Matsatsinis, N.; Marinakis, Y., A cumulative unmanned aerial vehicle routing problem approach for humanitarian coverage path planning, European Journal of Operational Research, 300, 3, 992-1004 (2022) · Zbl 1506.90048
[27] Lewis, N. (2020). A tech company engineered drones to deliver vital COVID-19 medical supplies to rural ghana and rwanda in minutes. May 12, 2020. Available from: https://www.businessinsider.com/zipline-drone-coronavirus-supplies-africa-rwanda-ghana-2020-5 [Accessed 5 September 2022].
[28] Li, H.; Chen, J.; Wang, F.; Bai, M., Ground-vehicle and unmanned-aerial-vehicle routing problems from two-echelon scheme perspective: A review, European Journal of Operational Research, 294, 3, 1078-1095 (2021) · Zbl 1487.90130
[29] Macias, J. E.; Angeloudis, P.; Ochieng, W., Optimal hub selection for rapid medical deliveries using unmanned aerial vehicles, Transportation Research Part C: Emerging Technologies, 110, 56-80 (2020)
[30] Macrina, G.; Pugliese, L. D.P.; Guerriero, F.; Laporte, G., Drone-aided routing: A literature review, Transportation Research Part C: Emerging Technologies, 120, 102762 (2020)
[31] Manalo, M. (2015). This budget airline is doing something really smart with drones — and big airlines should pay attention. Business Insider. June 13, 2015. Available from: http://www.businessinsider.com/easyjet-uk-uses-drones-airplane-inspection-2015-6 [Accessed 5 September 2022].
[32] Meola, A. (2021). Precision agriculture in 2021: The future of farming is using drones and sensors for efficient mapping and spraying. Available from: https://www.businessinsider.com/agricultural-drones-precision-mapping-spraying [Accessed 5 September 2022].
[33] Mohammadi, R.; Ghomi, S. F.; Jolai, F., Prepositioning emergency earthquake response supplies: A new multi-objective particle swarm optimization algorithm, Applied Mathematical Modelling, 40, 9-10, 5183-5199 (2016) · Zbl 1465.90126
[34] Moreno, A.; Alem, D.; Ferreira, D.; Clark, A., An effective two-stage stochastic multi-trip location-transportation model with social concerns in relief supply chains, European Journal of Operational Research, 269, 3, 1050-1071 (2018) · Zbl 1388.90022
[35] Murray, C. C.; Chu, A. G., The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery, Transportation Research Part C: Emerging Technologies, 54, 86-109 (2015)
[36] Murray, C. C.; Raj, R., The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones, Transportation Research Part C: Emerging Technologies, 110, 368-398 (2020)
[37] Noyan, N.; Balcik, B.; Atakan, S., A stochastic optimization model for designing last mile relief networks, Transportation Science, 50, 3, 1092-1113 (2016)
[38] Noyan, N.; Kahvecioğlu, G., Stochastic last mile relief network design with resource reallocation, OR Spectrum, 40, 1, 187-231 (2018) · Zbl 1390.90117
[39] Otto, A.; Agatz, N.; Campbell, J.; Golden, B.; Pesch, E., Optimization approaches for civil applications of unmanned aerial vehicles UAVs or aerial drones: A survey, Networks, 72, 4, 411-458 (2018)
[40] Özmen, B., Istanbul ili için deprem senaryosu, Türkiye Mühendislik Haberleri, 427, 23-28 (2002)
[41] Pérez-Rodríguez, N.; Holguín-Veras, J., Inventory-allocation distribution models for postdisaster humanitarian logistics with explicit consideration of deprivation costs, Transportation Science, 50, 4, 1261-1285 (2016)
[42] Rabta, B.; Wankmüller, C.; Reiner, G., A drone fleet model for last-mile distribution in disaster relief operations, International Journal of Disaster Risk Reduction, 28, 107-112 (2018)
[43] ReportLinker (2021). The overall drone inspection and monitoring market is projected to grow from USD 9.1 billion in 2021 to USD 33.6 billion by 2030, at a CAGR of 15.7
[44] Shavarani, S. M., Multi-level facility location-allocation problem for post-disaster humanitarian relief distribution, Journal of Humanitarian Logistics and Supply Chain Management, 9, 1, 70-81 (2019)
[45] Stolaroff, J. K.; Samaras, C.; O’Neill, E. R.; Lubers, A.; Mitchell, A. S.; Ceperley, D., Energy use and life cycle greenhouse gas emissions of drones for commercial package delivery, Nature Communications, 9, 1, 409 (2018)
[46] Techmonitor (2019). Amazon’s new delivery drone: Five key things we know so far. Available from: https://techmonitor.ai/technology/data/amazon-delivery-drone [Accessed 5 September 2022].
[47] Tofighi, S.; Torabi, S. A.; Mansouri, S. A., Humanitarian logistics network design under mixed uncertainty, European Journal of Operational Research, 250, 1, 239-250 (2016) · Zbl 1346.90184
[48] Tzeng, G.-H.; Cheng, H.-J.; Huang, T. D., Multi-objective optimal planning for designing relief delivery systems, Transportation Research Part E: Logistics and Transportation Review, 43, 6, 673-686 (2007)
[49] Unicef (2017). Humanitarian drone corridor launched in malawi. August 23, 2017. Available from: https://www.unicef.org/stories/humanitarian-drone-corridor-launched-malawi [Accessed 5 September 2022].
[50] Unicef (2018). Child given world’s first drone-delivered vaccine in vanuatu - UNICEF. December 18, 2018. Available from: https://www.unicef.org/press-releases/child-given-worlds-first-drone-delivered-vaccine-vanuatu-unicef [Accessed 5 September 2022].
[51] UPS (2017). UPS tests residential delivery via drone launched from atop package car. February 21, 2017. Available from: https://www.globenewswire.com/news-release/2017/02/21/925955/0/en/UPS-Tests-Residential-Delivery-Via-Drone-Launched-From-Atop-Package-Car.html [Accessed 5 September 2022].
[52] Vincent, J. (2021). Self-flying drones are helping speed deliveries of COVID-19 vaccines in Ghana. March 9, 2021. Available from: https://www.theverge.com/2021/3/9/22320965/drone-delivery-vaccine-ghana-zipline-cold-chain-storage [Accessed 5 September 2022].
[53] Volocopter (2021). Available from: https://www.volocopter.com/solutions/volodrone/ [Accessed 5 September 2022].
[54] Wang, Z.; Sheu, J.-B., Vehicle routing problem with drones, Transportation Research Part B: Methodological, 122, 350-364 (2019)
[55] Yang, M.; Kumar, S.; Wang, X.; Fry, M. J., Scenario-robust pre-disaster planning for multiple relief items, Annals of Operations Research, 1-26 (2021)
[56] Yang, Y.; Yin, Y.; Wang, D.; Ignatius, J.; Cheng, T.; Dhamotharan, L., Distributionally robust multi-period location-allocation with multiple resources and capacity levels in humanitarian logistics, European Journal of Operational Research, 305, 3, 1042-1062 (2023) · Zbl 1541.90092
[57] Zeng, Y.; Xu, J.; Zhang, R., Energy minimization for wireless communication with rotary-wing UAV, IEEE Transactions on Wireless Communications, 18, 4, 2329-2345 (2019)
[58] Zhang, G.; Jia, N.; Zhu, N.; Adulyasak, Y.; Ma, S., Robust drone selective routing in humanitarian transportation network assessment, European Journal of Operational Research, 305, 1, 400-428 (2023) · Zbl 1541.90095
[59] Zhu, T.; Boyles, S. D.; Unnikrishnan, A., Two-stage robust facility location problem with drones, Transportation Research Part C: Emerging Technologies, 137, 103563 (2022)
[60] Zipline (2022). Global healthcare. Available from: https://www.flyzipline.com/global-healthcare/ [Accessed 5 September 2022].
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.