# Charging Station Distribution Optimization Using Drone Fleet in a Disaster

Authors: Zohaib Hassan; Syed Irtiza Ali Shah; Ahsan Sarwar Rana
Journal: Journal of Robotics
 (2022)

---

## Abstract

A disaster is an unforeseen calamity that can cause damage to properties and can bring about a loss of human lives. Usually, many relief supplies, such as clean water, food, and medical supplies, are required by disaster victims. Quick response and rapid distribution of essential relief items into the affected region can save countless lives and prevent or slow down the effects of disasters. In this regard, disaster management comes into play, which is highly dependent on the topography and access of the disaster-hit area. If the disaster-hit site has little or no road connectivity, the use of UAVs/drones becomes essential in delivering health packages to the affected areas to assist with humanitarian aid. Since the battery capacity of the drone is limited, UAVs/drones require charging stations located at various places to carry out the necessary relief work. These charging stations should be transported using road infrastructure and preinstalled in disaster-prone areas, as access to these areas may be denied once the disaster hits. This article presents a novel optimization model to distribute relief items to disaster-hit areas. The objective of this model is to optimize the location and the number of the charging stations. We consider the relative priority of locations where a preference is given to locations with higher priority levels. The optimal number of charging stations and optimal routes has also been determined by using our optimization model. To illustrate the use of our model, numerical examples have been simulated for a different number of targets. Through 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.


---

## Body

## 1. Introduction

Recent disasters have caused significant economic and human losses, such as earthquakes in Iran (2003, 2017) and Chile (2011, 2015), and tsunamis in Japan (2011) [1]. Disaster is usually a breakdown in the normal functioning of nature that has a significant adverse impact on people, their work, and the environment. There is a high rate of fatality that results from a shortage of relief items following a disaster [2]. Large amounts of relief supplies, such as clean water, food, medical supplies, water purification tablets, and vaccines are required by disaster victims in the event of natural disasters such as hurricanes, earthquakes, and floods.Logistics activities in response to a disaster are commonly known as humanitarian logistics. Humanitarian logistics can be defined as the process of planning, implementing, and controlling the efficient and cost-effective flow of goods and related information, from a point of origin to a point of consumption to provide relief to the affected regions.There are four stages of disaster management, namely, mitigation, preparedness, response, and recovery. Our research can be included in the response stage since it involves all those activities that are performed immediately before, during, and right after a disaster occurs.In postdisaster situations, quick response and rapid distribution of vital relief items into affected regions could save precious lives. The main challenges of relief items distribution are associated with means of transport and transport infrastructure. Humanitarian aid agencies often face issues like poor or destroyed road infrastructure in disaster-hit areas. In the event of a disaster, the already poor conditions of the transport infrastructure are further disrupted, as roads are flooded or blocked and bridges are collapsed [3]. Under these conditions, roads are impassable and many locations are completely unreachable by land-based means of transportation. Consequently, the distribution of relief items becomes very difficult using traditional ground transport infrastructure. Distribution of relief supplies via helicopters is often not applicable due to the lack of trained pilots. Bringing human and material resources from outside to disaster locations is costly and often takes too much time when the time pressure to provide relief is very high.There is a need for alternative means of transport. In this regard, unmanned aerial vehicles, commonly known as drones, can provide solutions to the problems associated with ground transportation of relief items to disaster-hit areas. They save time and cost compared to traditional means of transport and make relief items supply to cut-off regions possible in the first place, as depicted in Figure1.Figure 1
Typical drone route for delivering relief packages to the targets while stopping at charging stations.Drones are autonomous or teleoperated flying machines that do not need constant user control. Small drones can fly at low altitudes and can avoid obstacles at low altitudes quite easily. They have many versatile applications but they also come up with some limitations. The limited battery capacity of the drones puts an upper bound on the maximum distance that a drone can travel. Therefore, charging stations are needed that can be used by the drones to recharge their battery. These charging stations should be transported using road infrastructure and preinstalled in the disaster-prone area, as access may be denied once it is hit with disaster. In the postdisaster phase, the already-installed charging stations can then be used by drones to recharge their batteries.In the literature, we find several studies that address the problem of distributing relief items in a disaster setting. Macias et al. [4] presented an endogenous stochastic vehicle routing problem model, in which a drone provides information to the ground vehicle for the distribution of relief items. Ma et al. [5] introduced the single depot vehicle routing problem with a time window constraint. Tu et al. [6] suggested a bilevel Voronoi diagram-based metaheuristic for a multidepot vehicle routing problem. Sundar [7] and Archetti [8] proposed, respectively, a tabu search algorithm and an optimization-based heuristic for split delivery capacitated vehicle routing problems. Dorling [9] proposed two multitrip vehicle routing problems for drone delivery that address the issues of minimizing cost and delivery time. The existing literature mentioned in this paragraph addresses the single and multidepot vehicle routing problems. However, in our proposed model we have considered a single depot that stores the relief items and drone batteries.The location of depot facilities is also crucial for the efficient flow of relief items. In this regard, different models have been proposed. Maghfiroh andHanaoka [10] and Sundar and Rathinam [7] proposed a multimodal relief distribution model that determined the optimal locations of depots. Escribano Macias et al. [11] present a novel approach consisting of an integrated trajectory location-routing algorithm to determine the optimal location of depots in the distribution supply chain. Kim et al. [12] developed a stochastic modeling framework to determine the locations and transport capacities of drone facilities to counter a disaster effectively. The developed model applies to emergency planning that incorporates drones into humanitarian logistics while considering the uncertain characteristics of drone operating conditions. Baharmand et al. [13] proposed a location-allocation model that divides the topography of affected areas into multiple layers. It considers the constrained number and capacity of facilities and fleets which allows decision-makers to explore trade-offs between response time and logistics costs. Klibi et al. [14] studied the strategic problem of designing emergency supply networks to support disaster relief over a planning horizon. The problem addresses decisions on the location and number of distribution centers needed, their capacity, and the quantity of each emergency item to keep in stock. Chowdhury et al. [15] presented a continuous approximation model to determine the optimal depot locations. Wei et al. [16] proposed an integrated-location routing problem for depot selection and vehicle assignment. Wang studied the location routing problem of an open emergency logistics system after an earthquake and designed a heuristic algorithm to solve a nonlinear integer location routing problem optimization model [17]. The models proposed by Moshref-Javadi and Lee [18], Wei et al. [16], and Davoodi and Goli [19] examine the simultaneous location routing problems for supply distribution operations. A biobjective location routing and scheduling model was proposed by Wei et al. [16] with two objective functions, consisting of the total cost and penalty cost caused by time window violations. In the literature work discussed here, the optimization problems of the depot locations are discussed. In our model, the location of the depot is fixed.The decisions making regarding location, allocation, and distribution of relief items is of great importance to the Humanitarian Relief Chain (HRC) managers in response to disasters such as earthquakes. Sahebjamnia et al. [20] developed a hybrid decision support system consisting of a simulator, a rule-based inference engine, and a knowledge-based system to configure a three-level HRC. The performance measures including the coverage, total cost, and response time are considered to make a trade-off analysis between cost efficiency and responsiveness of the designed HRC. Liu et al. [21] studied a location routing problem (LRP) to address the shortage of relief in disaster areas during the early stages of an earthquake. A multiobjective model for the fair location routing problem was developed by lexicographic order object optimal method in consideration of the urgent window constraints, partial road damage, multimodal relief delivery, disaster severity, and vulnerability of each demand node when its demand is not satisfied. The goals of this model are to minimize the maximum loss of the demand node, the total loss of the demand node, and the maximum time required for the demand node to receive relief.The challenges faced in the disaster response phase are numerous, due to the limited availability of resources and the lack of centralized coordination and infrastructure. Silva et al. [22] presented a procedure for the decision-making process of structuring an aid distribution network in disaster response operations with the application of drone technologies and geographic information systems. Balcik et al. [23] considered a vehicle-based last mile distribution system, in which a local distribution center (LDC) stores and distributes emergency relief supplies to a number of demand locations. The main decisions are allocating the relief supplies at the LDCs among the demand locations and determining the delivery routes for each vehicle throughout the planning horizon. This work proposes a mixed-integer programming model that determines delivery schedules for vehicles and allocates resources, based on supply, vehicle capacity, and delivery time restrictions, with the objectives of minimizing transportation costs and maximizing benefits to relief recipients. The previous studies discussed in this paragraph addresses the decision-making regarding the allocation of relief supplies at different depots for distribution purpose. We have made an assumption that the relief supplies are present in a fixed depot location.Some studies in the literature focus on multiple sources of transportation for relief items distribution to the disaster areas. Sahe [24] proposed a novel model in which multiple drones and trucks can work together to deliver vital relief items. A drone can depart from a truck and return to the same or a different truck after completing the delivery process and a truck can accommodate multiple drones. Escribano Macias et al. [4] presented a novel endogenous stochastic vehicle routing problem that coordinates drone and land-based relief vehicle deployments to minimize the mission cost. Ertem et al. [25] determined that the use of multimodal and intermodal transportation can be alternatives if relief distribution cannot be accomplished using an infeasible single mode of transportation. One of the studies conducted by Barbarosoglu and Arda [26] proposed a multicommodity and multimodal network flow model for the distribution of relief supplies in disaster responses. Najafi et al. [27] proposed a multimodal stochastic model to manage the logistics of both commodities and injured persons in earthquake response operations and developed a dynamic model for the same problem. Chung et al. [28] present a survey of the state-of-the-art optimization approaches in the civil application of drone operations and drone truck combined operations including infrastructure, agriculture, logistics, disaster management, and entertainment. The author reviews ongoing research on various optimization issues related to drone operations and drone and truck combined operations including mathematical models, solution methods, synchronization between a drone and a truck, and barriers in implementing drone operations and drone and truck combined operations. Maghfiroh and Hanaoka [29] investigated the application of the dynamic vehicle routing problem for last-mile distribution during disaster response. This work explored a model that involves limited heterogeneous vehicles, multiple trips, locations with different accessibilities, and uncertain demands to build responsive last-mile distribution systems. The existing work mentioned in this paragraph focuses on multimodal transportation for transporting relief items whereas our proposed work involves only a single mode of transportation, i.e., drones.It is essential to determine the type, number, and location of the demand areas for timely delivery of relief supplies. In this regard, Sebatli et al. [30] presented a simulation-based approach to determine the demand of disaster-hit areas and appropriately assign depot locations. Holguin-Veras et al. [31] discussed the effect of late deliveries and unmet demand on the performance of the postdisaster humanitarian logistic operations. Rivera Royero et al. [32] addressed the problem of distributing relief supplies after the occurrence of a disaster. In this work, a dynamic model is developed to serve demand, while prioritizing the response, according to the level of urgency of demand points. Faiz et al. [33] presented a two-echelon vehicle routing computational framework. In this work, a hotspot drone captured the demand by providing communication capabilities to the disaster-hit area, and a delivery drone satisfied the demand. Rivera-Royero et al. [34] proposed a rolling horizon methodology that considered dynamic parameters, such as demand quantity, capacities of drones, and demand priorities, for the distribution of relief items by including relief goods. This methodology also included assembling activities before the delivery of items. Zhan et al. [35] included the reliability of the distribution network while reflecting stochastic demand in a disaster situation. Lu et al. [36] developed a real-time relief distribution model for disaster response that includes a demand and time estimator as well as a module for solving optimal distribution flows. Mishra et al. [37] presented a two-phase bounded heuristic approach for logistics distribution as a response to the postdisaster relief operation. The proposed approach is focused on two major objectives: minimization of unmet demand and travel distance.The arrival time of the relief items mainly depends on the state of the road. We have made an assumption in our proposed model that the type, quantity, and location of demand points are known.In literature, we find studies that consider factors such as the state of the road, which affects the delivery time. Hu et al. [38] proposed a multistage stochastic programming model for disaster relief distribution that considered multiple vehicle types and the state of the road network. Sabouhi et al. [39] considered the expected arrival time of relief vehicles to the disaster-hit areas keeping into consideration the disruptions caused due to disasters. Baskaya et al. [40] used different route distances between centers and affected locations to reveal the disruption levels of the road network. Alem et al. [41], Moreno et al. [42], and Ferrer et al. [43] used binary variables to describe the state of arcs in the relief distribution problems. Penna et al. [44] used the concept of rich vehicle routing and considered accessibility constraints that allowed only compatible vehicles to serve particular routes owing to road blockage or geographical conditions. The existing literature discussed here addresses the effects of the state of the road on the delivery time of the relief items to the affected areas. Our proposed model utilizes aerial vehicles (UAVs/drones) that are not dependent on the state of the road for the delivery of the relief items.Some studies in the literature discuss the effects of a drone’s flight-related parameters. Poudel et al. [45] demonstrated the applicability of drones in transporting emergency medical products and investigate how different parameters that affect the drone flight contribute to the cost of transportation. Zafar et al. [46] proposed a distributed method that allows a fleet of drones with diverse capabilities to communicate and collaborate, to increase the task completion rate of rescue operations. The proposed solution consists of three main modules. The communication and message transmission module enables collaboration between drones, the realignment module allows drones to negotiate and occupy the best position in the air to optimize the coverage area, and the situation monitoring module identifies the ground situation and acts accordingly. Kim et al. [12] presented a stochastic modeling framework to determine the locations of drone facilities and transport capacities of drones for effectively handling the disaster. Baharmand et al. [13] proposed a location-allocation model that considered the capacity of facilities and vehicle fleets and enabled decision-makers to determine trade-offs between response time and logistics costs. Rottondi et al. [47] explored the joint planning of multitasking missions using a fleet of drones that were equipped with a standard set of accessories, which enabled heterogeneous tasks. In our proposed model, we have considered a drone capable of performing homogeneous tasks for the single-tasking mission.In literature, some authors have addressed the problems of drone routing and path planning. However, most of the research focused on finding the optimal path considering only geometrical constraints, without taking into account the features of the robot, like maximum energy capacity, weight, and maximum speed. Di Franco et al. [48] proposed an energy-aware path planning algorithm that minimizes energy consumption while satisfying a set of other requirements, such as coverage and resolution. Drones powered by batteries or fuel cells require refueling or recharging stations for extending coverage to a wider area. Hong et al. [49] proposed a location model to support spatially configuring a system of recharging stations for drone delivery service.The optimization techniques discussed in [50, 51] are taken as a guide to solving our proposed optimization model. The work proposed in [52] is the most relevant to our work. Huang and Savkin [52] presented a model to investigate the deployment of several charging stations to cover the targets in an urban demand area. In this model, the location coordinates of the target areas are already known. The charging stations covering no or fewer target locations are removed. Therefore, some areas are not reachable by drone. Our study aims to develop a mathematical model and use existing techniques to optimize drone delivery of relief items to disaster-hit areas considering the technical specifications of drones. The proposed model considers drone energy consumption as a function of the payload and Euclidean distance. In our proposed model, the target locations are unknown, so we performed our simulation using random target locations.The contribution of the proposed study is listed as follows:1.
In this study, we present a novel optimization model to optimize the location and number of charging stations for the predisaster phase2.
The relative priority of locations is attributed and a preference is given to the disaster-hit areas with higher priority levels3.
The routes of drones are optimized for the postdisaster phaseThe remainder of this study is organized as follows: In Section2, the cost function and constraints are defined to build the optimization model. Section 3 presents the methods used for grouping and path planning. In Section 4, the simulation results of numerical examples are discussed. Future work and conclusion sections are given at the end.


## 2. Problem Formulation

In this section, we have discussed all the parameters of our model. Let us say we have a set of target/disaster-hit locationsŤ = {T1, T2,…,TM} and a set of drone charging stations Ř = {R1, R2, R3,…,RC}, where M and C are the total numbers of target/disaster-hit locations and drone charging stations, respectively. Let the set of base stations Ή = {H} be a singleton set. Y = Ť ∪ Ř ∪ Ή is the set of all locations in the system. We assume that the target locations are of low-, medium-, and high-priority categories. K is the number of clusters into which the target locations are divided. N is the total number of drones.LetS be the maximum distance that this drone can cover with a maximum payload weight and maximum battery capacity. We assume that the payload capacity of the drone is three packages, each with a weight equal to 5 kg. The maximum payload weight that the selected drone can carry is 15 kg.We assume that the demand of every target location isc = 1. Therefore, a drone can deliver relief packages to three target locations in one route.Let us discuss a scenario in which a drone follows two different routes for the same target locations given in Figures2(a) and 2(b).Figure 2
Two different drone routes for the same targets of (a) four charging stations and (b) six charging stations.
(a)(b)LetG, the grid size, be the distance between adjacent drone charging stations. The number of charging stations in a defined area depends on the value of the grid size G. For a larger value of G, we have fewer charging stations in the defined area and vice versa. In Figure 2(a), there are four charging stations. The dotted line shows the shortest path (displacement) from target T2 to target T3. Suppose the drone does not have enough energy to reach T3 directly from T2. It will need to visit a nearby charging station to recharge its battery; therefore, it covers an off-track distance, as shown by the solid line in Figure 1(a). In Figure 2(b), a grid of six charging stations is shown. In this scenario, the drone travels over a shorter off-track distance to reach the charging station from target location T2. When the charging stations are fewer in number, there is a higher probability that the drone travels a longer off-track distance and vice versa.


### 2.1. Cost Function

As discussed before, there is an inverse relationship between the number of charging stations and the distance traveled by the drone. The objective of our model is to minimize both the number of charging stations and the total traveled distance.The cost function is defined as follows:(1)minuC+D,where C is the number of charging stations and D is the total distance. We have assumed that the value of u in (1) is 10, i.e., the cost of traveling a distance of 10 km is equal to the cost of installing one drone charging station.


### 2.2. Constraints

#### 2.2.1. Degree Constraints

LetΉ be the singleton set of the base stations. Ť is a set of target locations, Ř is the set of charging stations, xij is the number of times a drone travels from location i to j, and Y is the set of all locations in the system. Degree constraints are given as follows:We assume that each demand location inŤ is visited exactly once by only one drone, as given in(2)∑i∈Y/jxij=1,j∈Ť.At least one drone is used to supply relief items to demand locations inŤ. Therefore, the number of drone moves xij between the depot and demand locations Ť or charging stations Ř must be greater than 0, as expressed in(3)∑j∈Y/Ήxij>0,i∈Ή.


#### 2.2.2. Demand Constraints

Letwij be the payload carried by the drone when it travels from location i to j. W is the total payload capacity of the drone, and c is the unit package demand. The demand constraints are given as follows:For energy-saving purposes, the drone does not need to carry the maximum payload on each route. We impose that the drone returns to the depot empty, as expressed in(4)∑jwji=0,i∈Ή.If the drone travels fromi to j, the difference in the payload (between arrival and departure) is equal to the demand at location i, which is a unit package, given in (5), except for the charging station locations given in (6).(5)∑jwji−∑jwij=c,i∈Ť,(6)∑jwji−∑jwij=0,i∈Ř.The payload on any route cannot exceed the maximum payload of the drone, as given in(7)wij≤W,i∈Y,j∈Y.


#### 2.2.3. Energy Constraints

Leteij be the energy level of the drone when it leaves location i to travel to j. E is the maximum battery capacity of the drone, dij is the distance between locations i and j, ρ0 is the energy required for an empty drone to fly one unit distance, and ρ is the additional energy needed for a drone to fly one unit distance with one package. The energy constraints are given as follows.We assume that the drone’s battery is always fully charged when it leaves the depot or a charging station, as expressed in(8)eij=E,i∈Ή∪Ř,j∈Y/i.The energy level of the battery is always lower or equal to the maximum energy levelE, as expressed in(9)eij≤E,i∈Ť,j∈Y/i.Equation (10) gives the energy balance, i.e., the amount of energy consumed to move from any location to location i in Ť.(10)∑j∈Y/ieji−∑j∈Y/ieji=∑j∈Y/idjiρο+ρwji,i∈Ť.The energy level in the battery when the drone leaves locationi must be sufficient for it to reach any charging station Ř and demand location Ť, as expressed in(11)eij≥dijρo+ρwij,i∈Y,j∈Ř,(12)eij≥dijρο+ρwij+djkρο+ρwjk,i∈Y,j∈Ť,k∈Ř.All the constraints have been used just to validate the path taken by a drone and that they do not affect the value of the cost function in our model. Some constraints apply before the drone makes a single move, some apply after the drone has made a single move and some apply on the whole route of the drone. The constraints given in (4), (7)–(9), and (11) apply before the drone has made a single move. The constraints given in (5), (6), and (10) apply when the drone has made a single move while the constraints given in (3) and (4) apply on the whole route.


### 2.3. Assumptions in Our Model

We proposed a model to optimize the number of charging stations to be preinstalled in the disaster-prone area. We assume that historical data is available about the location of the disaster-prone areas, where the charging stations will be transported and installed. The charging stations will be fixed facilities. In the postdisaster phase, the location of the charging stations will not be changed concerning the location of the targets, as it will be costly and crucial time will be lost. We assume that the mobile phones or the hot spot drone will be used to get the data on the location and the priority level of the targets. We have selected a rotary drone for our simulation. The maximum distance capacity of the selected drone is 16 km. The payload capacity is 15 kg, with each package equal to 5 kg that contains vital relief items like dry ration, water, and a first-aid kit. The base station has relief packages and a battery charging mechanism. The drone will look for the charging station when its battery level is less than 50 percent of the maximum battery capacity.


## 2.1. Cost Function

As discussed before, there is an inverse relationship between the number of charging stations and the distance traveled by the drone. The objective of our model is to minimize both the number of charging stations and the total traveled distance.The cost function is defined as follows:(1)minuC+D,where C is the number of charging stations and D is the total distance. We have assumed that the value of u in (1) is 10, i.e., the cost of traveling a distance of 10 km is equal to the cost of installing one drone charging station.


## 2.2. Constraints

### 2.2.1. Degree Constraints

LetΉ be the singleton set of the base stations. Ť is a set of target locations, Ř is the set of charging stations, xij is the number of times a drone travels from location i to j, and Y is the set of all locations in the system. Degree constraints are given as follows:We assume that each demand location inŤ is visited exactly once by only one drone, as given in(2)∑i∈Y/jxij=1,j∈Ť.At least one drone is used to supply relief items to demand locations inŤ. Therefore, the number of drone moves xij between the depot and demand locations Ť or charging stations Ř must be greater than 0, as expressed in(3)∑j∈Y/Ήxij>0,i∈Ή.


### 2.2.2. Demand Constraints

Letwij be the payload carried by the drone when it travels from location i to j. W is the total payload capacity of the drone, and c is the unit package demand. The demand constraints are given as follows:For energy-saving purposes, the drone does not need to carry the maximum payload on each route. We impose that the drone returns to the depot empty, as expressed in(4)∑jwji=0,i∈Ή.If the drone travels fromi to j, the difference in the payload (between arrival and departure) is equal to the demand at location i, which is a unit package, given in (5), except for the charging station locations given in (6).(5)∑jwji−∑jwij=c,i∈Ť,(6)∑jwji−∑jwij=0,i∈Ř.The payload on any route cannot exceed the maximum payload of the drone, as given in(7)wij≤W,i∈Y,j∈Y.


### 2.2.3. Energy Constraints

Leteij be the energy level of the drone when it leaves location i to travel to j. E is the maximum battery capacity of the drone, dij is the distance between locations i and j, ρ0 is the energy required for an empty drone to fly one unit distance, and ρ is the additional energy needed for a drone to fly one unit distance with one package. The energy constraints are given as follows.We assume that the drone’s battery is always fully charged when it leaves the depot or a charging station, as expressed in(8)eij=E,i∈Ή∪Ř,j∈Y/i.The energy level of the battery is always lower or equal to the maximum energy levelE, as expressed in(9)eij≤E,i∈Ť,j∈Y/i.Equation (10) gives the energy balance, i.e., the amount of energy consumed to move from any location to location i in Ť.(10)∑j∈Y/ieji−∑j∈Y/ieji=∑j∈Y/idjiρο+ρwji,i∈Ť.The energy level in the battery when the drone leaves locationi must be sufficient for it to reach any charging station Ř and demand location Ť, as expressed in(11)eij≥dijρo+ρwij,i∈Y,j∈Ř,(12)eij≥dijρο+ρwij+djkρο+ρwjk,i∈Y,j∈Ť,k∈Ř.All the constraints have been used just to validate the path taken by a drone and that they do not affect the value of the cost function in our model. Some constraints apply before the drone makes a single move, some apply after the drone has made a single move and some apply on the whole route of the drone. The constraints given in (4), (7)–(9), and (11) apply before the drone has made a single move. The constraints given in (5), (6), and (10) apply when the drone has made a single move while the constraints given in (3) and (4) apply on the whole route.


## 2.2.1. Degree Constraints

LetΉ be the singleton set of the base stations. Ť is a set of target locations, Ř is the set of charging stations, xij is the number of times a drone travels from location i to j, and Y is the set of all locations in the system. Degree constraints are given as follows:We assume that each demand location inŤ is visited exactly once by only one drone, as given in(2)∑i∈Y/jxij=1,j∈Ť.At least one drone is used to supply relief items to demand locations inŤ. Therefore, the number of drone moves xij between the depot and demand locations Ť or charging stations Ř must be greater than 0, as expressed in(3)∑j∈Y/Ήxij>0,i∈Ή.


## 2.2.2. Demand Constraints

Letwij be the payload carried by the drone when it travels from location i to j. W is the total payload capacity of the drone, and c is the unit package demand. The demand constraints are given as follows:For energy-saving purposes, the drone does not need to carry the maximum payload on each route. We impose that the drone returns to the depot empty, as expressed in(4)∑jwji=0,i∈Ή.If the drone travels fromi to j, the difference in the payload (between arrival and departure) is equal to the demand at location i, which is a unit package, given in (5), except for the charging station locations given in (6).(5)∑jwji−∑jwij=c,i∈Ť,(6)∑jwji−∑jwij=0,i∈Ř.The payload on any route cannot exceed the maximum payload of the drone, as given in(7)wij≤W,i∈Y,j∈Y.


## 2.2.3. Energy Constraints

Leteij be the energy level of the drone when it leaves location i to travel to j. E is the maximum battery capacity of the drone, dij is the distance between locations i and j, ρ0 is the energy required for an empty drone to fly one unit distance, and ρ is the additional energy needed for a drone to fly one unit distance with one package. The energy constraints are given as follows.We assume that the drone’s battery is always fully charged when it leaves the depot or a charging station, as expressed in(8)eij=E,i∈Ή∪Ř,j∈Y/i.The energy level of the battery is always lower or equal to the maximum energy levelE, as expressed in(9)eij≤E,i∈Ť,j∈Y/i.Equation (10) gives the energy balance, i.e., the amount of energy consumed to move from any location to location i in Ť.(10)∑j∈Y/ieji−∑j∈Y/ieji=∑j∈Y/idjiρο+ρwji,i∈Ť.The energy level in the battery when the drone leaves locationi must be sufficient for it to reach any charging station Ř and demand location Ť, as expressed in(11)eij≥dijρo+ρwij,i∈Y,j∈Ř,(12)eij≥dijρο+ρwij+djkρο+ρwjk,i∈Y,j∈Ť,k∈Ř.All the constraints have been used just to validate the path taken by a drone and that they do not affect the value of the cost function in our model. Some constraints apply before the drone makes a single move, some apply after the drone has made a single move and some apply on the whole route of the drone. The constraints given in (4), (7)–(9), and (11) apply before the drone has made a single move. The constraints given in (5), (6), and (10) apply when the drone has made a single move while the constraints given in (3) and (4) apply on the whole route.


## 2.3. Assumptions in Our Model

We proposed a model to optimize the number of charging stations to be preinstalled in the disaster-prone area. We assume that historical data is available about the location of the disaster-prone areas, where the charging stations will be transported and installed. The charging stations will be fixed facilities. In the postdisaster phase, the location of the charging stations will not be changed concerning the location of the targets, as it will be costly and crucial time will be lost. We assume that the mobile phones or the hot spot drone will be used to get the data on the location and the priority level of the targets. We have selected a rotary drone for our simulation. The maximum distance capacity of the selected drone is 16 km. The payload capacity is 15 kg, with each package equal to 5 kg that contains vital relief items like dry ration, water, and a first-aid kit. The base station has relief packages and a battery charging mechanism. The drone will look for the charging station when its battery level is less than 50 percent of the maximum battery capacity.


## 3. Methods and Strategies

In this section, we discuss the methods and strategies used for obtaining the optimal number of charging stations and optimal routes. We proposed an algorithm for obtaining the optimal number of charging stations. The flow chart is given in Figure3. The flow chart determines the minimum value of the cost function which gives us the optimal grid size and the optimal number of charging stations. The process is explained as follows. The drone’s maximum distance capacity S is used to get the maximum valid grid size, VGmax, for a given size of the disaster area. The “for” loop in Figure 3 is run for different values of the grid size. For each grid size value, different number of charging stations is obtained. For simulation, random targets of different priority levels are scattered in the defined area. The targets are grouped into three targets each as the payload capacity of the selected drone is three packages. Each drone visits three targets and returns to the depot empty. The total average distance covered by the drone is calculated. For each iteration of the “for” loop different number of charging stations and total average distance is obtained. The expression given in (1) gives different values of the cost function for different numbers of charging stations and the total average distance. The minimum value of the cost function determines the optimal value of the grid size which correlates to the optimal number of charging stations.Figure 3
Flow chart of the proposed algorithm for determining the optimal number of charging stations.We randomly distribute low-, medium-, and high-priority targets within the defined area, as shown in Figure4.Figure 4
Random distribution of low-, medium-, and high-priority targets.Further sections explain the modules of the grouping of targets, group ordering, and path planning/routing.


### 3.1. Grouping

The objective of making groups is to first visit those targets that are closer to each other and have a higher priority level value. Hence, the drone covers a shorter distance and covers more high-priority areas, also achieving a greater summed priority score if all priority values of the visited group are summed.


#### 3.1.1. Selection of the First and Second Target

The base station is taken as the reference location for selecting the first target of a group. The distance between every target in a cluster and the base station is calculated. In Figure5, the arrows indicate the distances between each target and the base station. The shortest distance is termed dmin.Figure 5
Proposed layout showing distances between the targets and the base station.First, we calculate the value ofαi for the ith target in a cluster using(13)αi=dmindHTi.In equation (13), dHTi is the distance between the ith target and the base station, and dmin is the distance of the target that is closest to the base station. The value of αi for the ith target is at its maximum for the closest target from the base station.βi is the priority of the ith target, as given in (14), which is at a maximum for a high-priority target.(14)δi=αiβi.The target with the highest value ofδ is chosen as the first target of a group. For selecting the second target of a group, the location of the first target is considered as the reference location instead of the base station.


#### 3.1.2. Selection of the Third Target of a Group

The first and second selected targets are taken as the references for the selection of the remaining three targets to complete a group. The sum of the distances of theith target from the first and second selected targets is calculated. The arrows shown in Figure 6 indicate the distances of the ith target from the first and second selected targets.Figure 6
Proposed layout showing distances of targets from first and second selected targets.In Figure6, P and Q are the first and second selected targets, respectively, where dPi is the distance between the ith target and the first selected target P, and dQi is the distance between the ith target and the second selected target Q. First, we calculate the value μi of the ith target using(15)μi=dmindQi+dPi,where dmin is the minimum distance of the ith target from both reference locations P and Q, dQi and dPi are the distances between the ith target and the reference locations Q and P, respectively. μi of the ith target location will be greater for a target that is closer to both P and Q. βi is the priority value of the ith target, and ζi of the ith target is calculated using the formula given in(16)ςi=μiβi.The target with the highest value ofζi is selected as the third target location to complete the group of three targets. Groups of the targets are shown in Figure 7.Figure 7
Division of targets into groups of three targets each. The square symbol indicates high-priority targets, the diamond symbol shows medium-priority targets, and the triangle symbol shows low-priority targets.


#### 3.1.3. Method to Order Groups

In this section, we devise a method to arrange the groups in order, so that the groups that are closer to the base station and have higher throughput are visited first. Here, summed priority score is the sum of the priority level values of the targets in a group. In Figure8, arrows indicate distances between the centroids of groups and the base station.Figure 8
Proposed layout showing distances between centroids of groups and the base station.The value ofλi for the ith group is calculated using the expression in(17)λi=dmindHi,where dmin is the closest distance between that group and the base station, dHi is the distance between the centroid of the ith group and the base station, and λ is the maximum of the group for which the centroid is closest to the base station. Ui is the throughput of the ith group. ξi for the ith group is calculated using (18), and the groups are arranged in descending order concerning ξ.(18)ξi=λiUi.The group with the highest value ofξ is served first, and that with the lowest value of ξ is served at the end.


### 3.2. Path Planning

We define a route as the path followed by a drone to visit targets and return to the base station. Equation (12) is the energy required to visit any target location. A drone requires a charging station when it cannot reach the target destination directly. The drone may need to visit more than one charging station if the destination target is very not reachable with the current battery level. In our model, the drone will search for the nearby charging station when its battery level is less than 50 percent of the maximum battery capacity. The drone will select the charging station which is near to the destination if there are multiple charging stations at an equal distance from the current location of the drone. For each iteration of the loop in Figure 3, we get a different number of charging stations, total distance, and the value of the cost function corresponding to the different values of the grid size.The optimal grid size is determined by the value ofG for which the cost function is at its minimum. The optimal number of charging stations corresponds to the optimal value of the grid size for a defined area.The algorithm given in Figure9 determines the optimal routes using the optimal number of charging stations obtained using the algorithm given in Figure 3.Figure 9
Methodology of the proposed algorithm for optimal routes.


## 3.1. Grouping

The objective of making groups is to first visit those targets that are closer to each other and have a higher priority level value. Hence, the drone covers a shorter distance and covers more high-priority areas, also achieving a greater summed priority score if all priority values of the visited group are summed.


### 3.1.1. Selection of the First and Second Target

The base station is taken as the reference location for selecting the first target of a group. The distance between every target in a cluster and the base station is calculated. In Figure5, the arrows indicate the distances between each target and the base station. The shortest distance is termed dmin.Figure 5
Proposed layout showing distances between the targets and the base station.First, we calculate the value ofαi for the ith target in a cluster using(13)αi=dmindHTi.In equation (13), dHTi is the distance between the ith target and the base station, and dmin is the distance of the target that is closest to the base station. The value of αi for the ith target is at its maximum for the closest target from the base station.βi is the priority of the ith target, as given in (14), which is at a maximum for a high-priority target.(14)δi=αiβi.The target with the highest value ofδ is chosen as the first target of a group. For selecting the second target of a group, the location of the first target is considered as the reference location instead of the base station.


### 3.1.2. Selection of the Third Target of a Group

The first and second selected targets are taken as the references for the selection of the remaining three targets to complete a group. The sum of the distances of theith target from the first and second selected targets is calculated. The arrows shown in Figure 6 indicate the distances of the ith target from the first and second selected targets.Figure 6
Proposed layout showing distances of targets from first and second selected targets.In Figure6, P and Q are the first and second selected targets, respectively, where dPi is the distance between the ith target and the first selected target P, and dQi is the distance between the ith target and the second selected target Q. First, we calculate the value μi of the ith target using(15)μi=dmindQi+dPi,where dmin is the minimum distance of the ith target from both reference locations P and Q, dQi and dPi are the distances between the ith target and the reference locations Q and P, respectively. μi of the ith target location will be greater for a target that is closer to both P and Q. βi is the priority value of the ith target, and ζi of the ith target is calculated using the formula given in(16)ςi=μiβi.The target with the highest value ofζi is selected as the third target location to complete the group of three targets. Groups of the targets are shown in Figure 7.Figure 7
Division of targets into groups of three targets each. The square symbol indicates high-priority targets, the diamond symbol shows medium-priority targets, and the triangle symbol shows low-priority targets.


### 3.1.3. Method to Order Groups

In this section, we devise a method to arrange the groups in order, so that the groups that are closer to the base station and have higher throughput are visited first. Here, summed priority score is the sum of the priority level values of the targets in a group. In Figure8, arrows indicate distances between the centroids of groups and the base station.Figure 8
Proposed layout showing distances between centroids of groups and the base station.The value ofλi for the ith group is calculated using the expression in(17)λi=dmindHi,where dmin is the closest distance between that group and the base station, dHi is the distance between the centroid of the ith group and the base station, and λ is the maximum of the group for which the centroid is closest to the base station. Ui is the throughput of the ith group. ξi for the ith group is calculated using (18), and the groups are arranged in descending order concerning ξ.(18)ξi=λiUi.The group with the highest value ofξ is served first, and that with the lowest value of ξ is served at the end.


## 3.1.1. Selection of the First and Second Target

The base station is taken as the reference location for selecting the first target of a group. The distance between every target in a cluster and the base station is calculated. In Figure5, the arrows indicate the distances between each target and the base station. The shortest distance is termed dmin.Figure 5
Proposed layout showing distances between the targets and the base station.First, we calculate the value ofαi for the ith target in a cluster using(13)αi=dmindHTi.In equation (13), dHTi is the distance between the ith target and the base station, and dmin is the distance of the target that is closest to the base station. The value of αi for the ith target is at its maximum for the closest target from the base station.βi is the priority of the ith target, as given in (14), which is at a maximum for a high-priority target.(14)δi=αiβi.The target with the highest value ofδ is chosen as the first target of a group. For selecting the second target of a group, the location of the first target is considered as the reference location instead of the base station.


## 3.1.2. Selection of the Third Target of a Group

The first and second selected targets are taken as the references for the selection of the remaining three targets to complete a group. The sum of the distances of theith target from the first and second selected targets is calculated. The arrows shown in Figure 6 indicate the distances of the ith target from the first and second selected targets.Figure 6
Proposed layout showing distances of targets from first and second selected targets.In Figure6, P and Q are the first and second selected targets, respectively, where dPi is the distance between the ith target and the first selected target P, and dQi is the distance between the ith target and the second selected target Q. First, we calculate the value μi of the ith target using(15)μi=dmindQi+dPi,where dmin is the minimum distance of the ith target from both reference locations P and Q, dQi and dPi are the distances between the ith target and the reference locations Q and P, respectively. μi of the ith target location will be greater for a target that is closer to both P and Q. βi is the priority value of the ith target, and ζi of the ith target is calculated using the formula given in(16)ςi=μiβi.The target with the highest value ofζi is selected as the third target location to complete the group of three targets. Groups of the targets are shown in Figure 7.Figure 7
Division of targets into groups of three targets each. The square symbol indicates high-priority targets, the diamond symbol shows medium-priority targets, and the triangle symbol shows low-priority targets.


## 3.1.3. Method to Order Groups

In this section, we devise a method to arrange the groups in order, so that the groups that are closer to the base station and have higher throughput are visited first. Here, summed priority score is the sum of the priority level values of the targets in a group. In Figure8, arrows indicate distances between the centroids of groups and the base station.Figure 8
Proposed layout showing distances between centroids of groups and the base station.The value ofλi for the ith group is calculated using the expression in(17)λi=dmindHi,where dmin is the closest distance between that group and the base station, dHi is the distance between the centroid of the ith group and the base station, and λ is the maximum of the group for which the centroid is closest to the base station. Ui is the throughput of the ith group. ξi for the ith group is calculated using (18), and the groups are arranged in descending order concerning ξ.(18)ξi=λiUi.The group with the highest value ofξ is served first, and that with the lowest value of ξ is served at the end.


## 3.2. Path Planning

We define a route as the path followed by a drone to visit targets and return to the base station. Equation (12) is the energy required to visit any target location. A drone requires a charging station when it cannot reach the target destination directly. The drone may need to visit more than one charging station if the destination target is very not reachable with the current battery level. In our model, the drone will search for the nearby charging station when its battery level is less than 50 percent of the maximum battery capacity. The drone will select the charging station which is near to the destination if there are multiple charging stations at an equal distance from the current location of the drone. For each iteration of the loop in Figure 3, we get a different number of charging stations, total distance, and the value of the cost function corresponding to the different values of the grid size.The optimal grid size is determined by the value ofG for which the cost function is at its minimum. The optimal number of charging stations corresponds to the optimal value of the grid size for a defined area.The algorithm given in Figure9 determines the optimal routes using the optimal number of charging stations obtained using the algorithm given in Figure 3.Figure 9
Methodology of the proposed algorithm for optimal routes.


## 4. Simulations and Results

In this section of the paper, we present numerical examples for predisaster and postdisaster scenarios to illustrate the use of our proposed model. We have selected Matlab (MathWorks) tool for our simulation. We have assumed that the payload capacity of the drone isW = 3 packages. The demand at each target is c = 1 package. The weight of each package is 5 kg which contains a dry ration, water, and a first aid kit. Each target is assigned a value based on its priority level. The high-priority value is equal to 1, the medium-priority value is 0.7, and the low-priority value is 0.4. Initially, the drones are located at the base station at the start of the delivery process. The process of simulation is explained as follows.The targets are divided into groups of three targets each. The initial value of the grid size is less than the drone’s maximum distance capacity, S. The grid size value determines the number of charging stations. The route of the drone is completed when it departs from the base station and returns after visiting three targets for supplying relief packages. The simulation is run 1000 times for each value of the grid size value. In each iteration of the simulation, the targets change their location. The grid size will be valid only if the charging stations corresponding to the specific grid size are accessible to the drones for recharging. The average minimum distance covered by the drones is calculated for each grid size value. The value of the cost function is calculated for different values of the grid size. The minimum value of the cost function determines the optimal value of the grid size. The number of charging stations determined by the optimal grid size is the optimal charging station. Table1 shows the average minimum distance, charging stations, and cost function value against different values of the grid size.Table 1
Total distance and the calculated cost function.
ScenarioGrid size (km)Charging stationsDistance (km)Cost function1154180.93220.932144155.46195.463134139.40179.404124131.37171.375114125.12165.126104123.91163.9179.54122.93162.9389.254121.46161.46994122.53162.531084125.25165.251179117.53207.531269117.09207.09The minimum cost function value is obtained at a 9.25 km grid size.In scenario 1, the number of targets isM = 12. The disaster area is a square with sides of 15 km each. The optimal charging stations are 4, corresponding to the optimal grid size value of 9.25 km, as shown in Table 1.Figure10 shows the graph of the grid size and the cost function. At a grid size value of 9.25 km, we get the minima. (see Table2)Figure 10
The graph of the grid size versus the cost function. At a grid size value of 9.25 km, we get the minima.Table 2
Symbols and abbreviations.
SymbolDescriptionŤSet of target locationsŘSet of charging stationsΉSet of base stationsYSet of all locations in the systemMNumber of target locationsCNumber of charging stationsSdrone’s maximum distance capacityCDemand of target locationGGrid sizeDTotal distance covered by all dronesxijNumber of times drone travels from locationi to jIIndex used for locationsJIndex used for locationswijPayload carried while leaving locationi to jWTotal payload capacity of the droneeijdrone’s energy level while leaving locationi to jETotal energy capacity of the dronedijDistance between locationi and jρ0Energy required for an empty drone to fly one unit distanceρAdditional energy needed for a drone to fly one unit distancedminDistance of the target that is closest to the base stationαRatio of distancesdHtiDistance between theith target and the base stationβiPriority value of theith targetμiLikelihood measure ofith target to be selectedPFirst selected target of a groupQsecond selected target of a groupdPiDistance between theith target and the first selected target PdQiDistance between theith target and the second selected target QΜRatio of distancesζiLikelihood measure ofith target to be selectedΛRatio of distancesξiLikelihood measure ofith group to be served firstIn the second scenario, simulations were done for the predisaster phase to get the optimal grid size value and the optimal charging stations for various targets. The area of the disaster is fixed, and the number of the targets is varied. Figure11 shows the graph of the grid size values and the cost function values for the different numbers of the targets. The simulation is done with four different numbers of targets, i.e., 6, 9, 12, and 15. The simulation results indicate that the optimal grid size value in all the plots is the same as 9.25 km as shown in Figure 11. The optimal value of the grid size is the same for different numbers of targets.Figure 11
Cost function versus the grid size values for the different numbers of the targets. Optimal grid size is the same for different numbers of targets.In the third scenario, simulations were done for the postdisaster phase. The optimal routes of the drones were determined. The charging stations, in this case, are optimal charging stations determined in the predisaster phase. In this case, the number of the targets is kept equal to 12, and the size of the disaster area is kept equal to a square with sides of 15 km. The number of optimal charging stations is four. Figure12 shows the optimal routes for the targets in four groups.Figure 12
Calculated optimal routes for the optimal number of charging stations.


### 4.1. Discussion on Results

We ran our simulations to get the optimal grid size for a defined area and the number of targets. Our results show that the optimal grid size is equal to 9.25 km, which determined the optimal charging stations to be equal to four. The simulations were also done for the various targets. The optimal grid size was determined to be the same as 9.25 km for the different number of targets. Our simulation results show that the optimal grid size and the number of optimal charging stations are independent of the number of targets and that they only depend on the drone’s maximum distance capacity, S.


### 4.2. Limitations of the Proposed Model

In our model, we have assumed that the group size is three targets. If the number of targets is not a multiple of three, then some targets will be left ungrouped. As of now, we have considered only the flying mode of the drone in the energy equation. The proposed model does not take into account real-life constraints like the wind speed and other flight-related parameters of the drone. We have not considered the possibility that the charging station can be already occupied by a drone for recharging when another drone visits that charging station. We have allowed only one visit to a target location. If we consider multiple visits to a target location, the time at which the package is delivered would become a relevant parameter in the model.


### 4.3. Future Work and Recommendations

In future work, we can consider some parameters like the speed of the wind and other flight-related parameters of a drone to get more realistic simulations. The vertical take-off landing mode of the drone may also be considered in the energy equation. Multiple visits to a target location may be allowed to cater to a large demand of the target locations.


## 4.1. Discussion on Results

We ran our simulations to get the optimal grid size for a defined area and the number of targets. Our results show that the optimal grid size is equal to 9.25 km, which determined the optimal charging stations to be equal to four. The simulations were also done for the various targets. The optimal grid size was determined to be the same as 9.25 km for the different number of targets. Our simulation results show that the optimal grid size and the number of optimal charging stations are independent of the number of targets and that they only depend on the drone’s maximum distance capacity, S.


## 4.2. Limitations of the Proposed Model

In our model, we have assumed that the group size is three targets. If the number of targets is not a multiple of three, then some targets will be left ungrouped. As of now, we have considered only the flying mode of the drone in the energy equation. The proposed model does not take into account real-life constraints like the wind speed and other flight-related parameters of the drone. We have not considered the possibility that the charging station can be already occupied by a drone for recharging when another drone visits that charging station. We have allowed only one visit to a target location. If we consider multiple visits to a target location, the time at which the package is delivered would become a relevant parameter in the model.


## 4.3. Future Work and Recommendations

In future work, we can consider some parameters like the speed of the wind and other flight-related parameters of a drone to get more realistic simulations. The vertical take-off landing mode of the drone may also be considered in the energy equation. Multiple visits to a target location may be allowed to cater to a large demand of the target locations.


## 5. Conclusion

In this work, a simulation model was used to optimize the number and location of drone charging stations for deployment in a disaster-prone area. The relative priority of locations was considered, and preference was given to targets with higher priority levels. For the postdisaster phase, our model finds the optimal routes for the drones using data on the locations and the priority levels of the targets. We presented three scenarios to illustrate the use of our proposed model. In the first scenario, the number of targetsM = 12, and the area is a square with sides equal to 15 km each. We obtained the optimal grid size to be equal to 9.25 km. The optimal grid size of 9.25 km corresponds to four optimal charging stations for a given disaster-hit area. In the second scenario, we ran our simulations for the different numbers of targets. The simulations showed that the optimal grid size is the same for the different number of targets. In the third scenario, we calculated the optimal routes of drones using the optimal charging stations obtained in the first scenario. It can be concluded that the optimal G is independent of the number of targets in the disaster-hit area, and it only depends on the drone’s maximum distance capacity S. The presented research work can be applied in situations where relief supplies are needed to be provided swiftly to multiple locations hit by various kinds of disaster, including floods, earthquakes, avalanches, landslides, and storms.



---

*Source: 7329346-2022-07-31.xml*