Charging Stations Distribution Optimization using Drones  Fleet for Disaster Prone Areas

Zohaib Hassan; Irtiza Ali Shah; Ahsan Sarwar Rana

Authors

Zohaib Hassan Air University
Irtiza Ali Shah
Ahsan Sarwar Rana

Keywords:

Drone Charging Stations, Prepadness and Response, Drone Path Planning, Energy Optimization, Drone Recharging

Abstract

A disaster is an unforeseen calamity that causes damage to property or brings about a loss of human life. Quick response and rapid distribution of vital relief items into the affected region could save precious lives. In this regard, disaster management comes into play, which is highly dependent on the topography of the disaster-hit area. If the disaster-hit area has little or no road connectivity, the use of drones in such areas becomes essential for the delivery of health packages. Since the battery capacity of the drone is limited, there is a need of charging stations that should be transported using road infrastructure and pre-installed in disaster-prone areas, as access to these areas may be denied once the disaster hits. In this article, a simulation model was used to optimize the number and location of drone charging stations for deployment in a disaster-prone area in the pre-disaster scenario, aiming at the distribution of relief items to disaster-hit areas in the post-disaster scenario. We consider the relative priority of locations where a preference is given to the locations that have higher priority levels. An optimal number of charging stations and optimal routes have also been determined by using our optimization model. To illustrate the use of our model, numerical examples have been simulated for different sizes of the disaster-hit area and the number of targets. In our numerical simulation, it was observed that the drone's maximum distance capacity is the key factor in determining the optimal grid size, which directly correlates to the number of charging stations.

References

A. Jabbarzadeh, B. Fahimnia, and F. Sabouhi, "Resilient and sustainable supply chain design: sustainability analysis under disruption risks," Int. J. Prod. Res., vol. 56, no. 17, pp. 5945–5968, Sep. 2018, doi: 10.1080/00207543.2018.1461950.

"KIT - KIT - Media - Press Releases - Archive Press Releases - Natural Disasters since 1900: Over 8 Million Deaths and 7 Trillion US Dollars damage."

Y. Fukubayashi and M. Kimura, "Improvement of rural access roads in developing countries with initiative for self-reliance of communities," Soils Found., vol. 54, no. 1, pp. 23–35, Feb. 2014, doi: 10.1016/J.SANDF.2013.12.003.

J. Escribano Macias, N. Goldbeck, P. Y. Hsu, P. Angeloudis, and W. Ochieng, "Endogenous stochastic optimisation for relief distribution assisted with unmanned aerial vehicles," OR Spectr., vol. 42, no. 4, pp. 1089–1125, Dec. 2020, doi: 10.1007/S00291-020-00602-Z/TABLES/7.

M. F. N. Maghfiroh and S. Hanaoka, "Multimodal relief distribution model for disaster response operations," Prog. Disaster Sci., vol. 6, no. April, p. 100095, 2020, doi: 10.1016/j.pdisas.2020.100095.

S. Chowdhury, A. Emelogu, M. Marufuzzaman, S. G. Nurre, and L. Bian, "Drones for disaster response and relief operations: A continuous approximation model," Int. J. Prod. Econ., vol. 188, pp. 167–184, Jun. 2017, doi: 10.1016/J.IJPE.2017.03.024.

X. Wei, H. Qiu, D. Wang, J. Duan, Y. Wang, and T. C. E. Cheng, "An integrated location-routing problem with post-disaster relief distribution," Comput. Ind. Eng., vol. 147, p. 106632, Sep. 2020, doi: 10.1016/J.CIE.2020.106632.

M. Moshref-Javadi and S. Lee, "The customer-centric, multi-commodity vehicle routing problem with split delivery," Expert Syst. Appl., vol. 56, pp. 335–348, Sep. 2016, doi: 10.1016/J.ESWA.2016.03.030.

S. M. R. Davoodi and A. Goli, "An integrated disaster relief model based on covering tour using hybrid Benders decomposition and variable neighborhood search: Application in the Iranian context," Comput. Ind. Eng., vol. 130, pp. 370–380, Apr. 2019, doi: 10.1016/J.CIE.2019.02.040.

M. A. Ertem, M. İşbilir, and A. Şahin Arslan, "Review of intermodal freight transportation in humanitarian logistics," Eur. Transp. Res. Rev., vol. 9, no. 1, pp. 1–11, Mar. 2017, doi: 10.1007/S12544-017-0226-Z/FIGURES/5.

A. Sebatli, F. Cavdur, and M. Kose-Kucuk, "Determination of relief supplies demands and allocation of temporary disaster response facilities," Transp. Res. Procedia, vol. 22, pp. 245–254, 2017, doi: 10.1016/j.trpro.2017.03.031.

T. I. Faiz, C. Vogiatzis, and M. Noor-E-Alam, "Robust Two Echelon Vehicle and Drone Routing for Post Disaster Humanitarian Operations," arXiv, no. January, pp. 1–44, 2020.

D. Rivera-Royero, G. Galindo, and R. Yie-Pinedo, "Planning the delivery of relief supplies upon the occurrence of a natural disaster while considering the assembly process of the relief kits," Socioecon. Plann. Sci., vol. 69, p. 100682, Mar. 2020, doi: 10.1016/J.SEPS.2019.01.004.

C. C. Lu, K. C. Ying, and H. J. Chen, "Real-time relief distribution in the aftermath of disasters – A rolling horizon approach," Transp. Res. Part E Logist. Transp. Rev., vol. 93, pp. 1–20, Sep. 2016, doi: 10.1016/J.TRE.2016.05.002.

S. Hu, C. Han, Z. S. Dong, and L. Meng, "A multi-stage stochastic programming model for relief distribution considering the state of road network," Transp. Res. Part B Methodol., vol. 123, pp. 64–87, May 2019, doi: 10.1016/J.TRB.2019.03.014.

F. Sabouhi, A. Bozorgi-Amiri, and P. Vaez, "Stochastic optimization for transportation planning in disaster relief under disruption and uncertainty," Kybernetes, vol. 50, no. 9, pp. 2632–2650, 2020, doi: 10.1108/K-10-2020-0632/FULL/XML.

S. Baskaya, M. A. Ertem, and S. Duran, "Pre-positioning of relief items in humanitarian logistics considering lateral transhipment opportunities," Socioecon. Plann. Sci., vol. 57, pp. 50–60, Mar. 2017, doi: 10.1016/J.SEPS.2016.09.001.

A. Moreno, D. Alem, and D. Ferreira, "Heuristic approaches for the multiperiod location-transportation problem with reuse of vehicles in emergency logistics," Comput. Oper. Res., vol. 69, pp. 79–96, May 2016, doi: 10.1016/J.COR.2015.12.002.

J. M. Ferrer, F. J. Martín-Campo, M. T. Ortuño, A. J. Pedraza-Martínez, G. Tirado, and B. Vitoriano, “Multi-criteria optimization for last mile distribution of disaster relief aid: Test cases and applications,” Eur. J. Oper. Res., vol. 269, no. 2, pp. 501–515, Sep. 2018, doi: 10.1016/J.EJOR.2018.02.043.

P. H. V. Penna, A. C. Santos, and C. Prins, "Vehicle routing problems for last mile distribution after major disaster," https://doi.org/10.1080/01605682.2017.1390534, vol. 69, no. 8, pp. 1254–1268, Aug. 2017, doi: 10.1080/01605682.2017.1390534.

D. Kim, K. Lee, and I. Moon, "Stochastic facility location model for drones considering uncertain flight distance," Ann. Oper. Res. 2018 2831, vol. 283, no. 1, pp. 1283–1302, Dec. 2018, doi: 10.1007/S10479-018-3114-6.

H. Baharmand, T. Comes, and M. Lauras, "Bi-objective multi-layer location–allocation model for the immediate aftermath of sudden-onset disasters," Transp. Res. Part E Logist. Transp. Rev., vol. 127, pp. 86–110, Jul. 2019, doi: 10.1016/J.TRE.2019.05.002.

C. Rottondi, F. Malandrino, A. Bianco, C. F. Chiasserini, and I. Stavrakakis, "Scheduling of emergency tasks for multiservice UAVs in post-disaster scenarios," Comput. Networks, vol. 184, p. 107644, Jan. 2021, doi: 10.1016/J.COMNET.2020.107644.

M. Won, "UBAT: On Jointly Optimizing UAV Trajectories and Placement of Battery Swap Stations," Proc. - IEEE Int. Conf. Robot. Autom., pp. 427–433, May 2020, doi: 10.1109/ICRA40945.2020.9197227.

H. Huang and A. V. Savkin, "Deployment of Charging Stations for Drone Delivery Assisted by Public Transportation Vehicles," IEEE Trans. Intell. Transp. Syst., 2021, doi: 10.1109/TITS.2021.3136218.

Y. Qin, M. A. Kishk, and M. S. Alouini, "On the Influence of Charging Stations Spatial Distribution on Aerial Wireless Networks," IEEE Trans. Green Commun. Netw., vol. 5, no. 3, pp. 1395–1409, Apr. 2021, doi: 10.48550/arxiv.2104.01461.

S. Huma Ahmed Hassan, Syed Amer Mahmood , SairaBatool, AreebaAmer, Mareena Khurshid, HinaYaqub, "Generation of Digital Surface Model (DSM) USING UAV/ QUADCOPTER," Int. J. Innov. Sci. Technol., vol. 2, no. 3, pp. 89–107, 2020.

Y. Qin, M. A. Kishk, and M.-S. Alouini, "Drone Charging Stations Deployment in Rural Areas for Better Wireless Coverage: Challenges and Solutions," IEEE Internet Things Mag., vol. 5, no. 1, pp. 148–153, May 2022, doi: 10.1109/IOTM.001.2100083.

X. Lin, Y. Yazcoglu, and D. Aksaray, "Robust Planning for Persistent Surveillance With Energy-Constrained UAVs and Mobile Charging Stations," IEEE Robot. Autom. Lett., vol. 7, no. 2, pp. 4157–4164, Apr. 2022, doi: 10.1109/LRA.2022.3146938.

Y. Qin, M. A. Kishk, and M. S. Alouini, "Performance evaluation of uav-enabled cellular networks with battery-limited drones," IEEE Commun. Lett., vol. 24, no. 12, pp. 2664–2668, Dec. 2020, doi: 10.1109/LCOMM.2020.3013286.

H. Huang and A. V. Savkin, "A Method of Optimized Deployment of Charging Stations for Drone Delivery," IEEE Trans. Transp. Electrif., vol. 6, no. 2, pp. 510–518, Jun. 2020, doi: 10.1109/TTE.2020.2988149.

Jung, Sunghun and kim hyunsu, "Analysis of Amazon Prime Air UAV Delivery Service," J. Knowl. Inf. Technol. Syst., vol. 12, no. 2, pp. 253–266, 2017, doi: 10.34163/jkits.2017.12.2.005.