Drone Location and Scheduling Problems in Disaster Relief Management
Pitu Mirchandani a,*, Monica Gentili b, Zabih Ghelichi ba

School of Computing and Augmented Intelligence, Arizona State University, AZ, USA
pitu@asu.edu (corresponding author)b
Department of Industrial Engineering, University of Louisville, KY, USA
monica.gentili@louisville.edu, zabih.ghelichi@louisville.edu

December 14, 2021
Keywords: Drone logistics, Location and Scheduling, Simulation Optimization, Stochastic Optimization
1. Introduction and Motivation
A growing number of natural disasters have struck several regions around the world in the recent years,
mostly related to climate and weather-related events, e.g., flooding, wildfires, and storms. For instance, theUnited States has experienced more than 290 major natural disasters since 1980, where millions of lives
have been affected, and the damages have exceeded trillions of dollars [1]. Right after a disaster strike,
immediate emergency responses are crucial to deliver urgently needed aid packages, e.g., insulin shots andblood pressure medicine, to those trapped in inaccessible regions. In such situations, transportation
networks are of great importance as they provide vital platforms for rescue teams to dispatch medical andrelief aid packages. However, many severe disasters commonly damage supply lines and transportation
infrastructures and render people stranded without access to some urgent necessities. When landtransportation modes like automobiles, trucks and trains are inoperable, at least until the road surface
infrastructures are re-established again, aid delivery can resort to above ground modes.
Unmanned Aerial Vehicles (UAVs), also referred to as drones, are remote controlled flying robots that canmake immediate delivery of aid packages to many cut-off regions by overcoming many difficulties of thetraditional surface and air delivery modes, e.g., trucks and helicopters, face. With not being restricted toestablished road networks, drones are capable of delivering urgently needed aid packages in a short time.
The advantages of UAV utilization go beyond merely having access to remote and hard-to-access areas: norequirement of on-board pilots, no necessity of complicated and expensive launching infrastructure, andability of serving multiple purposes. The unique potentials of drone systems recently attracted many
attentions to the application of drones for the delivery of aid items in disaster-affected areas.
Motivated by the challenges associated with the timely delivery of aid items in disaster-affected areas, thisresearch studies the problem of drone location and scheduling problem for the delivery of aid items in cutoff regions. In this research, we first propose two alternative location optimization problems to optimallylocate drone launching platforms in the disaster affected areas. A platform is a structure that provides
operational support for drones from which a drone starts and ends its trips and can recharge its batteries.
The first problem formulates a deterministic model for the problem of locating drone platforms in thedisaster affected areas. The second problem is a stochastic variant of the drone platform location problem
that assumes the set of demand locations is unknown. In this study, we also propose a simulation-basedevaluation model for the problem of drone-based delivery of aid items in humanitarian logistics. The goal
is to develop a simulation system that can allow us to (1) evaluate alternative solutions obtained from theplatform location problems, i.e., deterministic and stochastic, and (2) improve the solutions through asimulation-optimization procedure. The simulation model is designed to capture multiple sources ofvariabilities such as number of demands, intervals of demand realization, flight time of the drones, andbattery failure.
2. Platform Location Problems
In this section, we propose two platform location optimization models where the first model assumes theset of demand locations is definite and known beforehand, i.e., deterministic model, while the second model
considers the set of demand locations is subject to uncertainty.
2.1. Deterministic Model
Given a set of candidate drone platforms and a set of demand locations, the proposed model finds thenumber and location of drone launching facilities – referred to as platforms – schedules drone trips anddetermines the assignment between drone trips and demand points. In the proposed system, aid items, e.g.,food, medications, and insulin shots, are loaded into a capsule held by a drone. Drones depart from theirplatforms for assigned demand points. Once a drone has reached its destination, it drops off its load andreturns to its platform. We assume that the drone’s operational range is constrained with a maximum
coverage range. We assume drones’ operational range is restricted by a maximum coverage range of drones.
The main problem is to concurrently decide (1) where to locate the platforms, (2) which demand points
must be served from each platform, and (3) the schedule and sequence of serving demand points, so that all
packages are delivered within a given time period 𝑇𝑇 (e.g., one day) and the total disutility is minimized.
Associated with each demand point that occurs is a utility (disutility) value that decreases (increases) withthe delivery time. To address this problem, we formulated a timeslot formulation which discretize theplanning period T into identical timeslot with prespecified granularity [2].
2.2. Stochastic ModelIn this section, we extend a stochastic model to address the problem of locating drone platform in disaster
affected areas. The model seeks to attain timely delivery of aid packages to disaster-affected regions via afleet of drones when the set of demand locations is unknown. While the deterministic model assumes all
the demand locations are known beforehand, a major realistic challenge for this problem is the considerationthat the set of demand locations is initially unknown. The main problem is to locate a set of drone platforms
such that with a specified probability 𝛼𝛼 (a percentile level), the maximum total disutility under all
realizations of the set of demand locations is minimized, in other words the value of the 𝛼𝛼 percentile of thedisutility distribution is minimized. In this study, we use the term combination to refer to a set of drone
platforms. Therefore, among all possible combinations of drone platforms, the goal is to select thecombination whose disutility distribution has the minimum 𝛼𝛼 percentile. In this problem situation, the setof demand points is subject to uncertainty, and the uncertainty set is comprised of a collection of scenarios.
We develop a Chance Constrained Programming (CCP) formulation to find the (optimum) platform
combination whose disutility distribution has the minimum 𝛼𝛼 percentile. To obtain the disutility
distribution, we adopted the aforementioned deterministic timeslot formulation which essentially schedules
and sequences a set of trips for the given fleet of drones so that the disutility is minimized [2].
The proposed stochastic optimization formulation comprises multiple complexities and is computationallytedious. We propose a multi-stage algorithmic solution approach to efficiently address these complexities.
The first stage applies a set of criteria to filter out a collection of the preferable candidates of platform
combinations with a prespecified size. An example of such a criterion is coverage extent which measuresthe total number of demand locations that a combination of drone platforms can cover for a given maximum
coverage range. The second stage derives disutility distributions for each set of candidate combination ofplatforms by solving a drone scheduling problem for each possible scenario of a set of demand locations.
In this stage, we need to solve the scheduling model for every pair of platform combinations and scenarios.
Owing to the large number of iterations and the NP-hard nature of the drone scheduling problem, wedevelop a heuristic greedy algorithm to mitigate the computation efforts for solving larger instances of theproblem [3]. The last stage employs the properties of a Sample Average Approximation (SAA) method andCCP formulation to select the combination of platforms that produces the minimum 𝛼𝛼 percentile [4].

3. Simulation-based Performance Evaluation ModelIn this simulation-based performance evaluator, we
assume a set of drone platforms have already been locatedfrom which the drone fleet must serve the unknown
demand locations. This decisions for locating these drone
platforms are obtained through solving the deterministic or
stochastic location optimization models. After the disasterstrikes, the rescue team receives new information withinvariable time intervals. This information includes (i) thenumber of new demands and (ii) their corresponding
coordinates in the disaster-affected area. Upon receiving
the information, a scheduling model finds an optimum
schedule and assigns a set of ordered trips to each drone.
Then, the simulation model simulates the drone flights
considering the dynamics and variabilities of the realworld environment, such as variable travel time, service
Figure 1. Simulation Modeltimes, and battery failure. Then, after some random timeinterval such 𝛿𝛿, a set of information, including the information about the new demands, previously received
demands, and the current state of the drones in the system, will be fed to the system, and the schedulingmodel will update drone schedules. And the process will be continued and repeated until a stop condition,e.g., operational time, is met (see Figure 1). The proposed simulation model captures the variations indifferent system parameters including (1) Interval of updating the system after receiving new information,(2) demand parameters: the demand rate and their spatial distribution (locations), (3) service timeparameters: travel times, setup and loading times, payload drop-off times and repair times, and (4) drone
energy level: battery’s energy is impacted and requires battery change/recharging while flying. We employ
the simulation model to evaluate the performance of alternative solutions obtained from the platform
location models and improve them through a simulation-optimization procedure.

4. Simulation-Optimization Procedure
In this section, we employ the proposed simulation model to improve the solutions obtained from theplatform location optimization models through a simulation-optimization procedure. The procedure starts
with finding an optimum solution to the platform location problems. Let 𝜆𝜆∗𝑚𝑚 the set of optimum platform
locations when 𝑚𝑚 drone platforms are selected in a platform location model, e.g., deterministic model.
Now, we perform a set of analytical studies by evaluating the k-opt neighbors to 𝜆𝜆∗𝑚𝑚 . A k-opt neighbor tothe optimum solution with 𝑚𝑚 platforms is a list of 𝑚𝑚 locations which differs from 𝜆𝜆∗𝑚𝑚 in 𝑘𝑘 elements. By

𝜆𝜆𝑖𝑖𝑚𝑚 , we denote the 𝑖𝑖 𝑡𝑡ℎ neighbor in k-opt neighborhood of 𝜆𝜆∗𝑚𝑚 . Once we have explored the neighborhood to𝜆𝜆∗𝑚𝑚 and identified a set of neighbors, we run the simulation model for 𝜆𝜆∗𝑚𝑚 and all the identified neighbors
𝜆𝜆𝑖𝑖𝑚𝑚 . Given a set of performance criteria, e.g., waiting time per demand and percentage of served demands,
𝑗𝑗

if there exists an alternative solution, i.e., neighbors, such 𝜆𝜆𝑚𝑚 which can outperform the optimum solution
𝑗𝑗

𝜆𝜆∗𝑚𝑚 in terms of all the performance criteria, then we can substitute the optimum solution 𝜆𝜆∗𝑚𝑚 with 𝜆𝜆𝑚𝑚 andrepeat the procedure. If there are multiple such solutions that outperform 𝜆𝜆∗𝑚𝑚 , we can choose one of therandomly or optimize a weighted summation of measures.

5. Preliminary Results
Considering a case study of central Florida discussed in Gentili et al. [2] with 25 candidate drone platformand 100 demand locations, we solved the platform location problem by using the proposed deterministic
and stochastic models where the set of optimum locations with 𝑚𝑚 drone platfroms are denote by 𝜆𝜆∗𝑚𝑚∗(stochastic), respectively. We first employed the simulation model to evaluate the(deterministic) and 𝛾𝛾𝑚𝑚∗for differnet range of demand values. We observed thatperformance of the alternative solutions 𝜆𝜆∗𝑚𝑚 and 𝛾𝛾𝑚𝑚
when a large number of demands appear in the realization, the solution of the deterministic model
outperforms the stochastic one. On the other hand, we can observe that the only case where the solution
from the stochastic model outperforms the deterministic models is when there are a small number ofplatforms to locate, i.e., 𝑚𝑚 = 8, and a small number of potential demand locations. In another set ofexperiments, we used the proposed simulation-optimization procudere as to improve the obtained solutions
from the deterministic and stochastic models. We observed that a simple 1-opt neighborhood search could
improve the obtained results in all aspects. For example, for the deterministic model when 𝑚𝑚 = 8, we could
identify 4 nieghbor that outpeforms the optimum solution 𝜆𝜆∗8 . We also observed that with lower number ofavailable platforms, i.e., 𝑚𝑚 = 8, the difference between the optimum solution and its better neighbors ismore significant. However, as the number of platforms increases, this difference becomes smaller.
6. References[1].
NCDC, Billion-Dollar Weather and Climate Disasters: Overview. 2021, National Centers For
Environmental Information.
[2].
Gentili, M., P.B. Mirchandani, A. Agnetis, and Z. Ghelichi, Locating Platforms and Scheduling aFleet of Drones for Emergency Delivery of Perishable Items. 2021.
[3].
Ruiz, R. and T. Stützle, A simple and effective iterated greedy algorithm for the permutation
flowshop scheduling problem. European journal of operational research, 2007. 177(3): p. 20332049.
[4].
Shapiro, A., Monte Carlo sampling methods. Handbooks in operations research and management
science, 2003. 10: p. 353-425.