’

# Drone Deployment Optimization for Direct Delivery with Time Windows and
Battery Replacements

Tanveer Hossain Bhuiyan* a,b, Mohammad Roni, a and Victor Walkera

###### Abstract

Aerial drones offer a distinct potential to reduce the delivery time and
energy consumption for the delivery of time-sensitive and small products.
However, there is still a need in the relevant industry to understand the
performance of drone-based delivery under different business needs and drone
operating conditions. We studied a drone deployment optimization problem for
direct delivery of goods to customers maintaining a specified time window.
This paper presents a new mathematical optimization-based decision-making
methodology to help business owners optimally route their drone fleet
minimizing the total energy consumption, required fleet size, and the required
number of additional batteries. A realistic feature of the optimization method
is that instead of replacing the drone battery after each return to the depot,
it keeps track of the remaining energy in the drone battery and decides on
battery replacements accounting for the drone routing and the user-specified
minimum required battery energy. Numerical results based on real drone flight
tests and delivery data provide insights into the effect of different drone
operating parameters on the energy consumption, required fleet size, and the
required number of battery replacements. Results from a case study show that
the total energy consumption, required fleet size, and the required number of
battery replacements increase by 72.22%, 22.2%, and 200%, respectively, as the
drones fly over the road networks compared to flying in a straight path.
Additionally, results show that using a mixed fleet of hexacopter and
quadcopter drones reduces the total energy consumption by 48.52% compared to
using a homogeneous fleet of only hexacopters.

a Energy and Environment Science & Technology Department, Idaho National
Laboratory, Idaho, USA

b Department of Mechanical Engineering, The University of Texas at San
Antonio, TX, USA

*Corresponding author email<EMAIL_ADDRESS>
Keywords: Drone routing, Drone energy consumption, Mixed-integer program,
Minimum required battery energy, Mixed fleet of drones

##  1 Introduction

This paper studies a drone deployment optimization problem for direct delivery
of goods from a retail business location (e.g., store) to customer locations.
The objective of the decision-maker (i.e., business owner) is to find the
optimal routing of drones that minimizes the investment (e.g., drone fleet and
battery costs) and operating (e.g., energy, labor, and maintenance costs)
costs in delivering customer orders within a specified time window.
Specifically, the goal of this study is to (1) develop a mathematical
optimization-based decision-making model that retail business owners can use
to optimally deploy a fleet of drones in delivering customer orders with a
minimum required fleet size (i.e., number of drones), required number of
additional batteries, and total energy consumption; (2) understand the effect
of different business and drone operating conditions on total energy
consumption, required fleet size, and required number of additional batteries;
and (3) provide numerical results and managerial insights based on real drone
flight test data to help business owners better understand the potential of
drones in goods delivery and evaluate alternative decisions.

###  1.1 Motivation

Unmanned aerial vehicles (UAVs), also known as drones, have gained abundant
attention from businesses and consumers. For instance, Amazon and several
other companies (e.g., Google, DHL) have developed their own drone delivery
systems [1]. Drones possess several advantages compared to other vehicles,
such as low capital and operating costs, the capability of taking off and
landing in a limited space without requiring expensive infrastructure, and
eliminating the necessity of an operator on board [2]. Due to these
advantages, drones offer a great benefit in numerous transportation and
logistics activities including but not limited to traffic surveillance [3],
consumer product delivery [4], emergency medical supplies [2], and agriculture
and forest fire surveillance [5].

Specifically, drones offer a distinct potential to improve the delivery of
goods in the last-mile, especially for time-sensitive, small, and localized
deliveries. In recent years, general e-commerce and retail online deliveries
are growing, and in some areas they are approaching a critical stage, such as
in New York City, where over 1.5 million daily deliveries are putting a strain
on the road networks and curb resources [6]. In addition, local business-to-
consumer deliveries are growing quickly for time-sensitive products, such as
prepared food, medicine, and groceries. With the growing online retail
business, cost-efficient and timely delivery of products from stores to the
customers’ homes is becoming a challenge for business owners, especially in a
densely populated urban environment due to congestion in the road networks.
Moreover, current delivery services are also expensive, costing restaurants up
to 30% of each order’s value for food delivery [7]. In these circumstances,
drone-based delivery can significantly reduce traffic congestion by avoiding
the use of road networks, as well as increase the delivery range, market
reach, and sales volume for the retail business owners by reducing the cost
and delivery time of the current system of using ground vehicles. Moreover,
McKinsey has suggested that 80% of last-mile deliveries will be done by
autonomous vehicles within 8 years [8], and that drones will likely be the
chosen method for a very large segment of the population, especially for
suburban and rural consumers needing same-day and speedy deliveries.

Despite the great potential and benefit, drone-based delivery suffers from a
major limitation—limited battery capacity—that limits the drone delivery
range. Therefore, in a drone routing problem, battery capacity, energy
consumption, and battery replacement decisions (i.e., swapping the depleted
battery with a fully-charged one) need to be incorporated to ensure safe
deliveries of products. Most research studies on drone deployment and
operations assume a fixed flight duration to reflect the battery capacity [1],
whereas some studies consider the drone energy consumption to be a function of
only drone speed, or package weight. But, in practice, drone energy
consumption, and thus, the battery capacity is affected by several drone
operating factors—speed, package weight, battery weight, distance traveled,
and duration of flight components (e.g., ascend, descend, hover). Therefore,
all these factors need to be accounted for while computing the drone energy
consumption and in the drone routing decisions. Also, depending on the type of
products, delivery locations, and customer preferences, business owners may
need to use different delivery methods, such as landing with the package on
the ground, or hovering above the ground and delivering the product through a
winch. Different delivery methods cause different amounts of energy
consumption, which can also affect the drone range. Therefore, practitioners
(e.g., business owners) need to get insight into the question: how much do the
package weight, drone speed, and delivery method affect the drone energy
consumption, required fleet size (i.e., number of drones), and the required
number of battery replacements?

In the drone routing literature on direct delivery from business to customers,
all the studies assume that drones always fly in a straight path. However, in
some areas, especially in densely populated urban areas, drones may not be
able to fly in a straight path due to the presence of no-fly zones in the
flight path, such as schools, large buildings, and restricted private
property. To avoid these no-fly zones, flying over the road networks is a
viable option as they are public property, resulting in a higher amount of
energy consumption and delivery time. Therefore, how does the drone flight
path (e.g., straight vs. over the road networks) affect the drone delivery
range, energy consumption, required fleet size, and the required number of
battery replacements in delivering all customer orders?

Also, all existing studies on direct delivery from business to customer
consider that each drone delivers packages to multiple customers in a single
trip before returning to the depot, which is not always possible, especially
for rotary drones, such as quadcopters and hexacopters. Moreover, in current
drone-delivery systems, such as Amazon Prime Air press releases [9]
demonstrate drones delivering packages to a single customer on each trip. In
case of delivering a single customer order on each trip, replacing the drone
battery after each return to the depot is not practical. Because it is likely
that there is a sufficient amount of energy remaining in the drone battery to
make an additional delivery to another customer. Therefore, replacing the
battery after each return can lead to an unnecessarily large number of battery
replacements and less drone utilization, causing the business owner to have a
large number of additional batteries and battery charging infrastructure, as
well as a larger number of drones in the fleet to maintain a desired delivery
time window for customers. Therefore, the question remains on how the drones
be routed to minimize the required fleet size? How should drones be routed to
minimize the required number of battery replacements?

Most studies assume a homogeneous fleet of drones, where all drones are
identical. But, customers are usually located at different distances from the
business location (e.g., store) and their orders have different weights.
Therefore, different drones may be suitable for different customer orders in
terms of energy-efficiency. Therefore, how much is the benefit of using a
mixed (heterogeneous) fleet of drones compared to using a homogeneous fleet?

The above-mentioned questions need to be answered quantitatively using real
data for the retail business owners to demonstrate the potential of drones in
the direct delivery of products to customers. Motivated by these needs, we
study a drone routing problem for direct delivery of goods and proposed a
mathematical optimization-based approach that incorporates realistic drone
operating conditions and provides insights to the questions based on real
drone flight test data. Specifically, our proposed mathematical optimization
approach can provide insights into the effect of different operating
parameters—drone speed, package weight, flight path, delivery method, fleet
type—on the delivery range, required fleet size, required number of battery
replacements, and energy consumption.

###  1.2 Related Literature

Drone routing optimization has been gaining a lot of attention to researchers
recently. Several research teams have conducted comprehensive review of the
recent studies on drone delivery and operations. Rojas et al. [10] and Marcina
et al. [11] provide a review of the research on generic drone routing problems
and for parcel delivery, respectively. Boysen et al. [12] provides a review of
the operations research methods used for solving the last-mile delivery
problems with drones. Otto et al. [13], Coutinho et al. [14], and Chung et al.
[15] provide comprehensive reviews of the optimization approaches—models and
algorithms—used for drone routing problems, where Chung et al. [15] focuses on
drone and drone-truck combined routing applications, and Otto et al. [13]
focuses on the civilian applications (e.g., medical supplies and disaster
management) of drones. Meanwhile, Barmpounakis et al. [16] provides a review
of the studies on using drones for surveillance in transportation and traffic
engineering.

In the drone-based product delivery literature, combined drone and ground
vehicle routing problems have been mostly studied, where ground vehicles
(e.g., trucks, delivery van) carry one or multiple drones to perform localized
deliveries. Researchers have studied a different variants of this combined
drone-truck delivery problem: (1) drone and truck both deliver packages to
customers [17, 18]; and (2) packages are delivered by drone only, whereas the
trucks act as a mobile depot to carry drones to a longer distance [19] and
provide drone battery recharging/replacement services [20]. Wang et al. [18]
were the first to model a combined drone-truck parcel delivery problem seeking
to reduce the total delivery time, where drones are carried by trucks. This
proposed model ignores several realistic features of the problems, including
the limitation of drone battery life, cost, and different distance metrics for
drones and trucks. However, this study presents a comparison of the delivery
time between a truck-only fleet and a drone-truck combined fleet. The Wang et
al. [18] study was extended by Poikonen et al. [17] by incorporating the
limited drone battery life and distance metrics for trucks and drones. Di
Puglia Pugliese and Guerriero [21] extended the work of Wang et al. [18] and
Poikonen et al. [17] by incorporating delivery time windows for customers in a
parcel delivery problem aiming to minimize the overall travel cost. These
authors made numerical comparisons between the use of a combined drone-truck
fleet and a truck-only fleet in terms of transportation cost and total
delivery time for last-mile delivery.

Murray and Chu [4] were the first to introduce two different variations of the
drone-truck delivery problem, where in one variant, truck and drones work
synchronously in delivering the package, whereas in the second variant, both
the truck and drones independently deliver packages to the customers. However,
in this routing problem, the authors only considered a single truck with
multiple drones. Ham [22] and Murray and Raj [23] extended the drone-truck
routing model of Murray and Chu [4] by introducing multiple drones and trucks.
These studies were further extended in [24], where the drones can fly from a
delivery truck and land on another truck, adding more flexibility to the
delivery problem. Heimfarth et al. [25] extended the independent drone truck
delivery problem accounting for the customer preferences in delivering the
parcel either using a truck or a drone. The authors considered a less strict
delivery time window requirement for each delivery, where the customer is
provided a rebate if the time window is violated. There also exist studies
where ground vehicles are used only as a carrier for drones (e.g., [26, 2]).
Huang et al. [26] proposed a drone routing model for parcel delivery utilizing
public transportation to carry drones to a longer distance.

However, none of the above-mentioned studies modeled drone battery
replacements or charging phenomena, rather they made a limiting assumption
that a drone battery is enough to complete each trip. Also, these studies
mostly considered identical drones in the fleet. However, using a mixed fleet
of drones is beneficial in making energy-efficient delivery. Gentili et al.
[2] studied the problem of locating mobile depots (e.g., ground vehicles) and
routing drones for providing emergency medical supplies to disaster-affected
areas aiming to minimize the total disutility of the demand locations. The
authors considered a mixed fleet, consisting of two types of drones—short-
range and long-range. In their routing problem, each drone carries a single
package to the demand point and returns back to the mobile depot. The authors
did not explicitly model the battery replacement and resuming of the drone
energy level, rather just added a fixed amount of time for package loading and
battery replacement each time a drone returned to the depot. However,
replacing the drone battery at each return is not realistic as there may be
energy remaining in the drone battery to make the next trip. Therefore, this
solution can lead to a larger number of unnecessary battery replacements,
which results in a larger number of additional batteries and battery charging
infrastructure. In the drone-truck hybrid delivery literature, none of the
above studies explicitly modeled the drone battery replacement to minimize the
required number of battery replacements, neither did they evaluate the impact
of no-fly zones on fleet sizing decisions, delivery time, and energy
consumptions. Only Jeong et al. [27] incorporated no-fly zones in the drone
flight path in a drone-truck hybrid parcel delivery problem and evaluated the
effect of no-fly zones on delivery time. However, these authors did not model
the battery replacements and mixed fleet of drones.

Compared to truck-drone hybrid delivery, relatively less work has been done on
deploying drones for the direct delivery of products to customers. Yadav and
Narasimhamurthy [28] studied a UAV routing problem seeking to minimize the
total time for delivery of all customer orders, where multiple drones can be
used to deliver the demand of a single customer. However, the authors made an
impractical assumption that drones can fly indefinitely in delivering customer
orders. But, in practice, battery energy capacity is the major limitation of
the drone-based deliveries that limits the drone delivery range. A Genetic
algorithm-based procedure was presented by San et al. [29] for assigning
drones to deliver packages to customer locations. Later, Song et al. [30]
modeled the UAV delivery problem as a mixed-integer program and solved using a
heuristics algorithm. Unlike Yadav and Narasimhamurthy [28] and San et al.
[29], the authors considered the effect of package weight on the flight time
of UAVs to reflect the limited battery capacity. However, they did not account
for the other factors (e.g., drone speed, flight path) in computing the energy
consumption, neither did they explicitly model battery energy consumption or
battery replacements.

Dorling et al. [31] modeled the battery energy consumption as a function of
drone battery and package weight. The authors proposed mixed-integer linear
programming formulations for two variants of a drone routing problem with the
objective functions of minimizing the total delivery time and the total cost,
respectively. The model assumes that each drone can deliver multiple packages
to different customers in a single trip and ensures that the battery capacity
is enough to make a trip before the trip starts. The drone battery is replaced
after each trip. However, this study does not explicitly model the minimum
energy requirement to determine battery replacement, neither does it seek to
minimize the number of battery replacements. Rabta et al. [32] modeled a drone
routing problem in addition to drone battery charging location decisions for
delivering disaster relief packages as a mixed-integer program. Like Dorling
et al. [31], each drone can deliver multiple packages in a single trip and
battery consumption is a function of package weight. Their model tracks the
remaining drone battery energy in the model using a variable to determine the
charging need. But the battery charging was not modeled explicitly accounting
for the charging time or rate.

Some studies incorporated a time window for customer deliveries in the drone
routing problem and optimize the fleet size in delivering customer orders.
Troudi et al. [33] modeled a capacitated vehicle routing problem with time
windows as a mixed-integer program to minimize the required number of drones
and batteries. Similar to Dorling et al. [31], the authors assumed that each
drone carries multiple packages in a single trip, and that the battery is
replaced after each trip. Exploiting these assumptions, the authors minimized
the number of batteries used by minimizing the number of trips. Cheng et al.
[1] studied another multi-trip (i.e., each drone performs multiple trips
starting and ending at the depot) drone routing problem with time windows
aiming to minimize the travel cost and electricity consumption cost related to
the drone battery. The authors considered drone energy consumption as a
function of package weight and distance traveled. However, they used
theoretical power consumption during hovering to approximate the forward
flight energy consumption, which is not realistic. Another multi-trip drone
delivery problem with time windows was studied by Kong et al. [34] to minimize
the total routing distance in delivering all parcels to customers. Considering
energy consumption as a function of package weight, Choi and Schonfeld [35]
studied an automated drone delivery system to minimize the total cost by
optimizing fleet size. The authors demonstrated the sensitivity of the drone
speed and battery capacity on the system cost and fleet size, respectively.
All the above-mentioned studies assume the drone fleet is homogeneous.

Coelho et al. [36] studied a drone routing problem for a mixed fleet of
drones, containing six different types of drones, with the objectives of
minimizing the total distance, total delivery time, and the number of drones
used. However, the authors considered drone energy consumption as a function
of drone speed only. But the drone energy consumption is affected by several
other operating parameters—package weight, drone body and battery weight,
distance traveled, and duration of different flight segments (e.g., ascend,
descend, hover). In addition to Coelho et al. [36], all the above-mentioned
studies on drone-only delivery modeled the drone routing problem assuming each
drone delivers packages to multiple customers in a single trip, and that the
battery is replaced after each trip. Under this assumption, the routing
problem is modeled just to ensure the battery energy is enough to complete
each trip in visiting the customers. But, in practice, many drones—especially
rotary drones—are designed to carry a single package on a trip. In this case
when a drone visits only a single customer on each trip, replacing the drone
battery after each return to the depot will lead to an unnecessarily large
number of battery replacements and less drone utilization, which can
eventually result in a large number of additional batteries or charging
infrastructure and the larger number of drones to maintain the same delivery
time window. Additionally, all the above studies on drone routing assume
drones fly in a straight path, which may not be always possible, especially in
a dense urban environment.

There exist other studies on drone routing focused on the effect of drone
delivery on carbon emission (e.g., [37, 38]) and locating drone deployment and
charging facilities to improve demand coverage (e.g., [39, 40]).

###  1.3 Contributions

In summary, existing studies have not simultaneously considered the different
factors (e.g., drone speed, package weight, distance traveled, duration of
ascend, descend, hover) affecting drone energy consumption and delivery range.
A lack of studies exist analyzing the improvement in the energy-efficiency of
the drone fleet due to using a mixed fleet of drones compared to a homogeneous
fleet. In the direct delivery of goods from business to customers, no research
has explicitly modeled the drone battery replacement decisions accounting for
the remaining energy in drone battery, user-specified minimum required energy
in drone battery, and drone routing when each drone visits a single customer
on each trip. Existing studies assume that each drone visits multiple
customers in a single trip before returning to the depot and replaces the
drone battery after each return to the depot, which can lead to an
unnecessarily large number of battery replacements when each drone visits a
single customer in each trip, eventually necessitating a large number of
additional batteries and drones. Additionally, no research has analyzed the
effect of routing drones over the road networks—due to avoiding restricted and
no-fly zones—on total energy consumption, required fleet size (i.e., number of
drones), and the required number of battery replacements.

Therefore, to fill the gaps in the literature, we studied a drone deployment
optimization problem for direct delivery of goods that accounts for the
different factors (e.g., drone speed, package weight, distance traveled,
duration of ascend, descend, hover) affecting drone energy consumption, pickup
time window for customer orders, and battery replacement decisions to evaluate
the performance of drone-based delivery under different drone operating
parameters—speed, flight path (e.g., straight vs. over the road networks),
fleet type (e.g., homogeneous vs. mixed fleet), and package delivery method
(e.g., landing vs. package dropping). This is the first study to (1) model the
drone routing problem where the drone battery is not replaced after each
return to the depot, rather a battery replacement is decided by the
optimization model accounting for the remaining battery energy, minimum
required energy for safe operation, and drone routing to minimize the number
of battery replacements needed; and (2) evaluate the effect of several key
drone operating parameters—flight path, fleet type, and minimum required
energy in the drone battery—on the delivery range, energy consumption,
required fleet size, and the number of times battery needs to be replaced.

Our paper extends the drone routing literature by introducing a new
mathematical optimization approach that incorporates real-life drone operating
characteristics and presents new insights based on real drone flight test
data. Specifically, in this paper, we made the following contributions: (1)
developed new mathematical optimization models that incorporate the business
limitations and drone operating conditions and seek to optimally route the
drones to minimize the total energy consumption, required fleet size, and the
required number of battery replacements in delivering a set of customer
orders; (2) proposed two valid inequalities to improve the computational
efficiency of the mathematical model; and (3) provided numerical results and
new insights based on real data into the effect of drone speed, package
weight, flight path, minimum required energy, delivery method, fleet type, and
pickup time window on the drone delivery range, total energy consumption,
required fleet size, and the required number of battery replacements.

##  2 Problem Description

In this paper, we study the problem of a retail business owner (e.g., grocery
stores, restaurants) seeking to efficiently deploy drones to directly deliver
goods to a set of customer locations that minimizes the total energy
consumption, the required fleet size, and the required number of battery
replacements. We assume that the business owner owns the drone fleet and that
all drones are stationed at the business location that acts as a central depot
for the drones. The drone fleet may consists of the same type (i.e.,
homogeneous fleet) or different types (i.e., mixed fleet) of drones. The
customers are geographically located around the central depot. The business
owner knows the geographic location (i.e., latitude and longitude) from where
each customer order originates, as well as the time stamp of order placement.
In this business scenario (see Figure 1), each drone carries a single package
in a flight from the depot to a delivery (i.e., customer) location and then
returns to the depot before flying to the next delivery location.

Figure 1: Business scenario.

Depending on the business and product types, customers may have different
preferences on the time window (e.g., 2 minutes for Starbucks coffee vs. 30
minutes for a grocery item) they are willing to allow for drones to pick up
the products once they are ready for delivery. To account for this realistic
customer preference criterion in retail business, we consider a pickup time
window for each customer order within which a drone must pick up the product
from the depot. This time window for each customer order is defined by the
package ready time (i.e., earliest possible pickup time) and the maximum
permissible delayed pickup time. The travel time of a drone from the depot to
a delivery location consists of the time required to ascend to the flying
height, forward flight time to reach the delivery location, short hovering
duration required to ensure the correct landing location, and the time
required to descend to the ground. We also consider the time required to load
and unload the packages to/from the drone at the depot and the delivery
locations, respectively, as these package loading and unloading times affect
drone operation and satisfying the customer order pickup time windows.

We consider that each drone starts with a fully-charged battery at the
beginning of the planning horizon. As the drones continue to deliver packages
to the customer locations, energy in the drone battery gets consumed, and
thus, the remaining energy in the drone battery gradually decreases. The
energy consumption during drone operation depends on several operating
parameters, such as drone speed, package weight, distance traveled, duration
of flight segments (i.e., ascend, descend, hover), and delivery method. To
ensure safe operation of the drones, prior to leaving the depot for the next
delivery location, we need to ensure that the drone battery would have at
least a minimum required amount of energy remaining after returning from that
delivery location. Therefore, before leaving the depot for the next delivery
location, we need to compute the potential remaining energy in the drone
battery after returning from the next location. If the potential remaining
energy is less than the minimum required energy, the current battery needs to
be replaced with one that is fully-charged before leaving for the next
delivery location.

However, despite starting with a fully-charged battery to deliver a package to
a delivery location, if the potential remaining energy in the drone battery
drops below the minimum required energy, then it is not possible for the
drones to deliver a package to that particular location. We refer this
particular delivery location to be outside the delivery range of the drone.
This delivery range of a drone varies with different operating
parameters—drone speed, package weight, drone flight path, delivery method,
and minimum required energy. A drone cannot be assigned to serve a location
that is outside its delivery range. In addition, each drone has a maximum
weight carrying capacity that cannot be exceeded, meaning that the drone
cannot be used to deliver a package that weighs more than the maximum
allowable weight.

##  3 Methods

To solve the drone deployment problem discussed in Section 2, we formulate the
problem as a mixed-integer program. In this section, we present the
mathematical formulations of the drone deployment problem for both homogeneous
and mixed fleets of drones. We lists the necessary sets, parameters, and
variables that support the mathematical formulations in Table 1.

Table 1: Notation.

Sets | Description
---|---
$\mathcal{I}$ | Set of delivery locations $i$
$\mathcal{I^{\prime}}$ | Set of delivery locations including the dummy source $0$ and sink $S$
$\mathcal{D}$ | Set of drone types $d$
(a) Sets

Parameters |  Description
---|---
$C_{d}$ |  Amortized cost of the drone type $d$
$C_{bat}^{d}$ |  Amortized cost of the battery of drone type $d$
$v$ |  Drone speed
$C_{E}$ |  Cost of per unit of energy
$C_{L}$ |  Wage of a drone operator
$n_{d}$ |  Number of drones of type $d$ a drone operator can operate simultaneously
$C_{d}^{M}$ |  Maintenance cost of a drone of type $d$
$L_{i}$ |  Distance of delivery location $i$ from depot
$t_{Hi}=\frac{L_{i}}{v}$ |  Time required for drone to arrive at delivery location $i$ from depot
$t_{iH}=\frac{L_{i}}{v}$ |  Time required for drone to return from delivery location $i$ to depot
$t_{d}^{bat}$ |  Time required to replace the battery of drone type $d$
$e_{i}$ |  Earliest possible pickup time
$\Delta$ |  Maximum permissible delay
$\mathit{ch_{d}^{0}}$ |  Initial energy in the battery of drone type $d$
$\mathit{ch_{d}^{min}}$ |  Minimum remaining energy required in the battery of drone type $d$
$E_{dHi}$ |  Energy consumption by a drone of type $d$ to arrive at delivery location $i$ from depot with a package
$E_{diH}$ |  Energy consumption by drone of type $d$ to return empty from delivery location $i$ to the depot
$c_{ij}^{d}$ |  Energy consumption by a drone of type $d$ to fly from location $i$ to $j$, i.e., $c_{ij}^{d}=E_{diH}+E_{dHj}$
$M_{d}^{max}$ |  Maximum package weight carrying capacity of drone type $d$
$M_{i}$ |  Package weight for delivery location $i$
(b) Parameters

Variables |  Description
---|---
$z_{ij}$ |  1 if delivery location $i$ is served immediately before $j$ by a drone, 0 otherwise
$y_{i}$ |  1 if drone battery is replaced after returning from delivery location $i$, 0 otherwise
$g_{i}$ |  Remaining battery energy of a drone after returning from delivery location $i$
$g_{i}^{\prime}$ |  Auxiliary variable storing the remaining battery energy after returning from delivery location $i$
$f_{i}$ |  Timing of when a drone picks-up the package for delivery location $i$ at depot
$x_{di}$ |  1 if drone type $d$ is assigned to deliver a package to location $i$, 0 otherwise
(c) Variables

###  3.1 Model for Homogeneous Fleet of Drones

In this subsection, we assume that the drone fleet is homogeneous, meaning
that the drones are identical. Taking advantage of this assumption, we can
develop the drone deployment model as a two-index formulation, similar to the
vehicle routing literature (e.g., [41]). As mentioned in Section 2, in the
retail business scenario studied in this paper, each drone directly flies from
the depot to a delivery location and returns to the depot before flying to the
next location. To model this drone routing problem as a network optimization
problem (an example network is shown in Figure 2), we add a dummy source ($0$)
and a sink ($S$) to the set of delivery locations $\mathcal{I}$, resulting in
a new set $\mathcal{I^{\prime}}$. In Figure 2, the path $0-1-2-4-S$ indicates
that a drone starts with delivering a package to location 1 and returns to the
depot, then visits location 2 and returns to the depot again, before making
its last delivery to location 4. We define a variable $z_{ij}$ that represents
whether a drone visits location $j$ after returning from location $i$ or not.
The corresponding parameter to this variable, $c_{ij}^{d}$, denotes the energy
consumed by the drone to return empty to the depot from location $i$ and then
arrive at location $j$ with the package. The variable $z_{0j}$ represents an
outgoing arc from the dummy source ($0$), as well as the beginning of a
sequence of delivery locations visited by a drone. Therefore, adding a large
penalty to the corresponding energy consumption parameter, $c_{oj}$, we can
minimize the number of outgoing arcs (i.e., routes) from the source, and thus
minimize the required fleet size, which is the number of drones used to
deliver packages to all locations.

Figure 2: An example network representation of the original problem.

The mixed-integer programming (MIP) formulation of the drone deployment
optimization problem is presented below.

#### Objective Function

The goal of our drone deployment optimization problem is to find the optimal
drone routing that minimizes both investment and operating costs in delivering
all customer orders within a specified planning horizon. The investment cost
includes the drone and battery costs, whereas the operating cost includes the
energy consumption, drone operator, and maintenance costs.

$\displaystyle\textnormal{min}\,\,C_{E}\left(\sum_{i\in\mathcal{I^{\prime}}}\sum_{j\in\mathcal{I}^{\prime}}c_{ij}^{d}z_{ij}\right)+\left(C_{d}+\frac{C_{L}}{n_{d}}+C_{d}^{M}\right)\sum_{j\in\mathcal{I}^{\prime}}z_{0j}+C_{bat}^{d}\left(\sum_{i\in\mathcal{I^{\prime}}}y_{i}\right)$
(1)

The objective function (1) seeks to minimize the total energy consumption cost
(component 1), total investment and operating costs of the drones (component
2), and investment costs of the batteries (component 3) in delivering all
customer orders maintaining the specified pickup time windows within the
planning horizon. As the costs of drones and batteries are functions of the
number of drones required and the number of times battery needs to be
replaced, respectively, an optimal solution to this drone routing MIP model
provides the minimum required fleet size (i.e., required number of drones) and
the minimum required number of battery replacements, which is also the minimum
required additional batteries, to deliver all customer orders satisfying the
specified time windows.

#### Assignment and Flow Balance Constraints

As mentioned earlier, in this drone routing problem, each customer order is
delivered once by only one drone and the drones return to the depot after
delivering a package to each location before visiting the next location.

$\displaystyle\sum_{i\in\mathcal{I}^{\prime}}z_{ij}=1\qquad\forall
j\in\mathcal{I}$ (2)
$\displaystyle\sum_{j\in\mathcal{I}^{\prime}}z_{ij}=1\qquad\forall
i\in\mathcal{I}$ (3)
$\displaystyle\sum_{i\in\mathcal{I^{\prime}}}z_{ij}=\sum_{i\in\mathcal{I}^{\prime}}z_{ji}\qquad\forall
j\in\mathcal{I}$ (4)
$\displaystyle\sum_{j\in\mathcal{I}}z_{0j}=\sum_{j\in\mathcal{I}}z_{jS}$ (5)

Constraints (2)–(3) ensure that each customer order is delivered once by only
one drone. Constraints (4) and (5) are the flow balance constraints for the
customer locations, and dummy source-sink pair, respectively, ensuring that if
a drone visits a location $i$, it must return to depot from that location to
visit the next location in the delivery sequence until the drone completes its
route.

#### Package Weight and Delivery Range Constraints

As mentioned in Section 2, a drone cannot be used to deliver a package to a
location that is out of its delivery range. Constraints (6) represent this
delivery range limitation. In addition, a drone cannot be used to deliver a
customer order if the package weight exceeds the maximum weight carrying
capacity, which is enforced by constraints (7).

$\displaystyle\sum_{i\in\mathcal{I}^{\prime}}\left(E_{dHj}+E_{djH}\right)z_{ij}\leq\left(ch_{d}^{0}-ch_{d}^{min}\right)\qquad\forall
j\in\mathcal{I}$ (6) $\displaystyle
M_{j}\sum_{i\in\mathcal{I}^{\prime}}z_{ij}\leq M_{d}^{max}\qquad\forall
j\in\mathcal{I}$ (7)

#### Pickup Time Window Constraints

Constraints (8) ensure that the pickup time of the packages for the delivery
locations are computed consistently accounting for the sequence in which each
drone visits the locations. Constraints (9) enforce the time windows within
which each package must be picked-up for the delivery locations by the drones.

$\displaystyle f_{j}\geq
f_{i}+\left(t_{\ell}+t_{Hi}+t_{u}+t_{iH}\right)+t_{d}^{bat}y_{i}-M(1-z_{ij})\qquad\forall
i,j\in\mathcal{I^{\prime}},i\neq j$ (8) $\displaystyle e_{i}\leq
f_{i}\leq\ell_{i}\qquad\forall i\in\mathcal{I}$ (9)

Here, $\ell_{i}=e_{i}+\Delta$ is the maximum permissible delayed pickup time
for delivery location $i$ and $M$ is a large positive number.

#### Battery Replacement Constraints

To ensure safe operation of the drones, before visiting the next location, we
need to compute how much energy would be remaining in the drone’s battery
after returning to the depot from its delivery location and replace the
battery if needed. Constraints (10) compute the potential remaining energy in
the drones’ batteries after returning from the first delivery location in each
delivery sequence (i.e., route). Each constraint (11) computes the potential
remaining energy in the drone’s battery after returning from each delivery
location except for the first location in each delivery sequence. This
constraint ensures the potential remaining energy in the drone’s battery is
computed consistently accounting for the sequence in which the delivery
locations are visited by the drone. For example, if location $4$ is visited
after location $3$ (i.e., $z_{34}=1$), then the potential remaining energy
after returning from delivery location $4$, $g_{4}^{\prime}$, is computed by
subtracting the total energy required to arrive and return from location $4$
($E_{dH4}+E_{d4H}$) from the remaining energy after returning from location
$3$ ($g_{3}$), i.e., $g_{4}^{\prime}\leq g_{3}-\left(E_{dH4}+E_{d4H}\right).$

$\displaystyle g_{j}^{\prime}\leq
ch_{d}^{0}-\left(E_{dHj}+E_{djH}\right)+M(1-z_{0j})\qquad\forall
j\in\mathcal{I^{\prime}}$ (10) $\displaystyle g_{j}^{\prime}\leq
g_{i}-\left(E_{dHj}+E_{djH}\right)+M(1-z_{ij})\qquad\forall
i,j\in\mathcal{I^{\prime}},i\neq j$ (11)

If the potential remaining energy after returning from a delivery location $j$
is less than the minimum required energy (i.e.,
$g_{j}^{\prime}<ch_{d}^{min}$), then we need to replace the current battery
with a fully-charged one (i.e., $y_{i}=1$) before the drone leaves the depot
to visit location $j$. This condition is represented by constraints (12). But,
if the potential remaining energy after returning from delivery location $j$
is higher than the minimum required energy (i.e., $g_{j}^{\prime}\geq
ch_{d}^{min}$), then the battery must not be replaced before visiting $j$, and
thus, the drone should continue its operation with the remaining energy
($g_{i}$) after returning from its previous location $i$. Constraints (13)
enforce this condition. Here, $M_{u}$ and $M_{\ell}$ are the upper and lower
bounds of $\left(g_{j}^{\prime}-ch_{d}^{min}\right)$, respectively.

$\displaystyle g_{j}^{\prime}-ch_{d}^{min}\geq
M_{\ell}y_{i}+M(z_{ij}-1)\quad\forall
i\in\mathcal{I^{\prime}},j\in\mathcal{I^{\prime}\setminus\mathit{\\{0\\}}},i\neq
j$ (12) $\displaystyle g_{j}^{\prime}-ch_{d}^{min}\leq
M_{u}(1-y_{i})+M(1-z_{ij})\quad\forall
i\in\mathcal{I^{\prime}},j\in\mathcal{I^{\prime}\setminus\mathit{\\{0\\}}},i\neq
j$ (13)

Depending on whether the battery is replaced or not before visiting the next
location $j$, we need to compute the actual energy remaining after returning
from location $j$. If the current battery is replaced with a fully-charged one
after returning from location $i$ (or before visiting location $j$), then the
battery energy is resumed to the initial energy level $ch_{d}^{0}$. Therefore,
if the battery is replaced before visiting location $j$ (i.e., $y_{i}=1$),
then the energy remaining after returning from location $j$ is computed by
subtracting the total energy consumption due to round-trip travel to location
$j$ from the initial battery energy, i.e., $g_{j}\leq
ch_{d}^{0}-\left(E_{dHj}+E_{djH}\right)$. Constraints (14) represent this
condition. If the drone’s battery is not replaced before visiting location $j$
(i.e., $y_{i}=0$), the energy remaining after returning from location $j$ is
computed based on the remaining energy ($g_{i}$) after returning from its
previous location $i$ as $g_{j}\leq g_{i}-\left(E_{dHj}+E_{djH}\right)$. This
condition is represented by constraints (15). Each constraint (16) computes
the actual energy remaining after returning from the first location in each
delivery sequence. Here, $Q_{u}$ is the upper of
$\left(ch_{d}^{0}-g_{j}\right)$.

$\displaystyle g_{j}\leq
ch_{d}^{0}-\left(E_{dHj}+E_{djH}\right)+Q_{u}(1-y_{i})+M(1-z_{ij})\quad\forall
i,j\in\mathcal{I^{\prime}},i\neq j$ (14) $\displaystyle g_{j}\leq
g_{i}-\left(E_{dHj}+E_{djH}\right)+Q_{u}y_{i}+M(1-z_{ij})\quad\forall
i\in\mathcal{I}^{\prime}\setminus\mathit{\\{0\\}},j\in\mathcal{I^{\prime}},i\neq
j$ (15) $\displaystyle g_{j}\leq
ch_{d}^{0}-\left(E_{dHj}+E_{djH}\right)+Q_{u}y_{0}+M(1-z_{0j})\quad\forall
j\in\mathcal{I^{\prime}}$ (16)

#### Sign Restriction Constraints

Constraints (17)–(20) represent the binary nature and sign restrictions of the
variables.

$\displaystyle z_{ij}\in\\{0,1\\}\qquad\forall
i,j\in\mathcal{I^{\prime}},i\neq j$ (17) $\displaystyle g_{i}\geq
0\qquad\forall i\in\mathcal{I^{\prime}}$ (18) $\displaystyle
g_{i}^{\prime}\geq-ch_{d}^{min}\qquad\forall i\in\mathcal{I^{\prime}}$ (19)
$\displaystyle f_{i}\geq 0\qquad\forall i\in\mathcal{I^{\prime}}$ (20)

###  3.2 Model for Mixed Fleet of Drones

We propose a two-phase modeling approach to solve the drone deployment
optimization problem for a mixed fleet of drones, which contains different
types of drones in the fleet. In the first phase, we develop an integer
programming model to find the energy-efficient assignment of the different
types of drones to deliver packages to the delivery locations. This drone
assignment model (3.2) accounts for the limitations of battery energy and
package weight carrying capacity for different types of drones and provides
the optimal assignment of drone types to the delivery locations.

min
$\displaystyle\sum_{i\in\mathcal{I}}\sum_{d\in\mathcal{D}}\left(E_{dHi}+E_{diH}\right)x_{di}$
(21a) s.t., $\displaystyle\sum_{d\in\mathcal{D}}x_{di}=1\qquad\forall
i\in\mathcal{I}$ (21e)
$\displaystyle\left(E_{dHi}+E_{diH}\right)x_{di}\leq\left(ch_{d}^{0}-ch_{d}^{min}\right)\qquad\forall
d\in\mathcal{D,}i\in\mathcal{I}$ $\displaystyle M_{i}x_{di}\leq
M_{d}^{max}\qquad\forall i\in\mathcal{I},d\in\mathcal{D}$ $\displaystyle
x_{di}\in\\{0,1\\}\qquad\forall i\in\mathcal{I},d\in\mathcal{D}$

The objective function (21a) seeks to optimally assign drone types to the
delivery locations that minimizes the total energy consumption in delivering
packages to all locations. Each constraint (21e) ensures that only one type of
drone can be assigned to deliver a package to a location. A drone type $d$
cannot be assigned to deliver a package to a location $i$ if that drone type
consumes more energy than the maximum allowable energy consumption (i.e.,
$ch_{d}^{0}-ch_{d}^{min}$) in delivering the package to that location.
Constraints (21e) enforce this battery energy limitations for the drone types.
Each constraint (21e) represents that a drone type $d$ cannot be assigned to
deliver a package to a location $i$ if the package weight for that delivery,
$M_{i}$, exceeds the maximum weight carrying capacity, $M_{d}^{max}$, of that
drone type. Constraints (21e) represent the binary nature of the assignment
decision variables.

The output of this first-phase modeling is the subsets of delivery locations
and their corresponding drone types. We use the MIP model for homogeneous
fleet of drones presented in Section (3.1) for each subset of delivery
locations and the corresponding drone type $d$ to obtain the required number
of drones of type $d$, the total energy consumption in delivering packages to
the locations in that subset, and the required number of battery replacements.
Combining the results from each subset and drone type, we obtain the minimum
total number of drones of different types required in the fleet, which is the
required fleet size, and the total energy consumption by all drones in
delivering all packages. A flowchart of this two-phase modeling approach is
demonstrated in Figure A.1 (see Appendix A) to clarify the modeling concept.

###  3.3 Acceleration Techniques

We observed that the number of $z_{ij}$ variables in the developed drone
deployment MIP model increases by $|\mathcal{I}^{\prime}|$ for each additional
delivery location in the data. A large number of constraints are also added in
the model for each additional delivery location. Therefore, as the number of
delivery locations in our drone deployment problem increases, the
computational complexity of the MIP model increases exponentially. To
alleviate the computational burden in solving the MIP model, we implement two
problem-specific valid inequalities that substantially reduce the number of
$z_{ij}$ variables. We observed that in the optimal solution, most of the
$z_{ij}$ variables are zero. Therefore, we implement the following two valid
inequalities to remove those unnecessary $z_{ij}$ variables from the candidate
solutions:

  1. 1.

A drone cannot pick up the package for delivery location $j$ immediately after
serving location $i$, if the maximum permissible delayed pickup time for $j$
($\ell_{j}$) is earlier than the earliest time the drone can return to the
depot after serving location $i$. Each constraint (22) removes the $z_{ij}$
variables from the candidate solutions for which this condition holds.

$\displaystyle\mathnormal{\textnormal{if\,\,}}\,e_{i}+t_{\ell}+t_{Hi}+t_{u}+t_{iH}>\ell_{j}$
$\displaystyle\qquad\textnormal{then\,\,\,\,}z_{ij}=0\quad\forall
i,j\in\mathcal{I}$ (22)

  2. 2.

If the time difference between the maximum delayed pickup time for delivery
location $j$ and returning from location $i$ is longer than the time required
for a drone to serve the furthest location, then the drone will not wait for
such a long duration to pick up the package for location $j$ after returning
from location $i$. This is because, the objective of our model is to minimize
the total number of drones required to deliver packages to all customer
orders. Therefore, the drone will deliver a package to another location $k$
after returning from location $i$, meaning $z_{ij}=0$. Constraints (23) remove
the $z_{ij}$ variables from the candidate solutions for which this condition
holds.

$\displaystyle\mathnormal{\textnormal{if}}\,\,\,\ell_{j}>\ell_{i}+t_{Hi}+t_{iH}+2(t_{\ell}+t_{u}+2t_{Range})$
$\displaystyle\qquad\textnormal{then\,\,\,}z_{ij}=0\quad\forall
i,j\in\mathcal{I}$ (23)

##  4 Case Study Results and Managerial Insights

We used our mathematical models described in Section 3 to provide insights
into the following questions:

  1. 1.

How do the drone operating parameters—speed, package weight, flight path,
minimum required energy in the battery—affect the delivery range?

  2. 2.

How does the drone speed, package weight, delivery method, flight path affect
the total and average energy consumption in delivering packages to customer
locations?

  3. 3.

How does the required fleet size (i.e., number of drones required) changes
with the drone speed, package weight, and flight path?

  4. 4.

How sensitive is the required fleet size to changes in the pickup time window?

  5. 5.

How frequently do batteries needs to be replaced as the drone speed, package
weight, flight path, and minimum required energy change?

  6. 6.

How does the use of a mixture of drones in the fleet affect the delivery
range, total energy consumption, and the required fleet size?

###  4.1 Experimental Setup

We implemented the drone deployment optimization models described in Section 3
using Python 3.7 with Cplex optimizer 12.10 [42]. We conducted numerical
experiments using a one-hour Spatio-temporal prepared food delivery data from
the San Francisco Bay Area in California. This delivery data contains the
business provider and 126 customers’ geographic locations (i.e., latitude and
longitude) and the timing of when a package is ready for pick up. We
synthetically generated the package weight for each customer order or delivery
location. We conducted drone flight tests using two rotary drones—DJI Matrice
600 Pro and Tarot 650—for different operating conditions—drone speed, flight
path (e.g., straight, over the road networks), and package weight. DJI Matrice
600 Pro is a rotary hexacopter that has higher package weight carrying
capacity at a longer distance than the Tarot 650, which is a rotary
quadcopter. Table 2 lists the parameters and their values that are kept fixed
in all numerical experiments. While designing and conducting the drone flight
tests, we used United States Customery System (USCS) units. Therefore, in
Tables 2 and 3, we provided the parameter values both in USCS and SI units. We
used the amortized hourly costs of the drones and batteries to run our
numerical experiments.

Table 2: Fixed parameter values. Parameters | DJI Matrice 600 Pro Values | Tarot 650 Values
---|---|---
|  USCS Unit |  SI Unit |  USCS Unit |  SI Unit
Initial battery energy (fully-charged), $ch^{0}$ |  600 watt-hour |  2.16 Mega-Joule (MJ) |  177.6 watt-hour |  0.639 Mega-Joule (MJ)
Package loading time, $t_{\ell}$ |  5 minutes |  5 minutes |  5 minutes |  5 minutes
Package unloading time (landing), $t_{u}$ |  30 seconds |  30 seconds |  30 seconds |  30 seconds
Battery replacement time, $t_{d}^{bat}$ |  5 minutes |  5 minutes |  5 minutes |  5 minutes
Flying height |  200 feet |  60.96 meters |  200 feet |  60.96 meters
Hovering duration while delivering package (landing) |  5 seconds |  5 seconds |  5 seconds |  5 seconds
Hovering duration while returning to depot |  5 seconds |  5 seconds |  5 seconds |  5 seconds
Cost of a drone |  $8000 |  $8000 |  $4000 |  $4000
Cost of a drone battery |  $1200 |  $1200 |  $200 |  $200
Labor (drone operator) cost |  $60/hour |  $60/hour |  $60/hour |  $60/hour
Number of drones operated by an operator |  5 |  5 |  5 |  5

We conducted numerical experiments for different combinations of the
parameters shown in Table 3 to analyze the effects these parameters on total
and average energy consumption, the required number of drones, and the
required number of battery replacements. It is to be noted that we used the
same package weight for all customer orders in each model run to demonstrate
the individual effect of package weight on the delivery range, energy
consumption, required number of drones, and battery replacements.

Table 3: Parameters for sensitivity analysis. Parameters | Values
---|---
|  USCS Unit |  SI Unit
Drone speed |  15, 30 (mph) |  6.71, 13.41 (m/s)
Package delivery method |  Landing, Package dropping |  Landing, Package dropping
Minimum required battery energy, $ch^{min}$ (% of initial battery energy) |  10, 15, 20, 25 |  10, 15, 20, 25
Package weight |  2.5, 5.0, 10.0 (lb) |  1.13, 2.27, 4.54 (Kg)
Hovering duration in package dropping |  30, 60, 90, 120 (seconds) |  30, 60, 90, 120 (seconds)
Pick up time window |  1, 5, 10, 15, 20, 25, 30, 35 (minutes) |  1, 5, 10, 15, 20, 25, 30, 35 (minutes)

In the numerical experiments, we used the power consumption and flight time
data from our drone flight tests. The power consumption and flight time data
of the DJI Matrice 600 Pro drone corresponding to the flight segments—ascend,
forward flight, hover, and descend—for different package weights and drone
speeds are provided in Table B.1 and B.2, respectively in Appendix B. Tables
B.3 and B.4 in Appendix B show the power consumption and flight time data of
the Tarot 650 drone, respectively. Using these power consumption and flight
time data, we computed the energy consumption for each flight segment to use
in the numerical experiments. To obtain the total time required and energy
consumed by a drone to arrive with a package at a customer location $(i)$ from
the depot ($H$), we used the time and energy of the flight segments as shown
in Figure 3a. Taking summation of the time of these flight segments, we
obtained the model parameter $t_{Hi}$, whereas the summation of the energy of
these segments provides the parameter $E_{dHi}$. Figure 3b demonstrates the
flight segments when the drone returns to depot ($H$) from the delivery
location $(i)$. Combining the time and energy consumption of these segments
provides the parameters $t_{iH}$ and $E_{diH}$, respectively. Figure 3
demonstrates the flight segments when the drone is delivering packages by
landing to the ground. Another delivery method is package dropping, when the
drones hover at 20 feet (6.096 meters) above the ground and drops the package
via a winch.

(a) Drone flight segments when delivering the package to a customer location
(b) Drone flight segments when returning to the depot

Figure 3: Drone flight segments.

###  4.2 Effect of Drone Speed and Package Weight on Delivery Range, Energy
Consumption, Required Fleet Size, and Battery Replacements

The delivery range of a drone is limited by the drone’s battery energy and the
fact that we need to ensure a minimum required energy remains in the drone
battery upon returning to the depot for its safe operation. We conducted
numerical experiments to evaluate the effect of drone speed and package weight
on the delivery range. In this analysis, we used the DJI Matrice 600 Pro drone
for which we used the minimum required battery energy as 324 Kilo-Joule (KJ),
which is 15% of the initial battery energy of 2.16 Mega-Joule (MJ). Therefore,
the delivery locations for which the DJI drone consumes more energy than 1.836
MJ ($=2.16-0.324$) to deliver the package and return, are considered to be
outside the drone delivery range. As mentioned earlier, the delivery range is
defined by the number of locations that are outside the range of drone
delivery. Table 4 demonstrates the number of locations that are outside the
drone range for two different drone speeds and three different package
weights.

Table 4: Number of locations outside drone delivery range. Drone Speed (m/s) | Package Weight (Kg)
---|---
|  1.13 |  2.27 |  4.54
13.41 |  0 |  0 |  0
6.71 |  27 |  29 |  45

We see from Table 4 that the DJI Matrice 600 Pro can deliver packages to all
126 customer locations when flying at 13.41 meter per second (m/s) speed.
However, the drone cannot deliver packages to all locations when flying at
6.71 m/s. This is because, despite the average power consumption is less at a
slower speed (6.71 m/s), the drone stays in the air for a much longer duration
at 6.71 m/s speed to travel the same distance, resulting in a much larger
total energy consumption as compared to 13.41 m/s speed in delivering a
package. Due to this much larger consumption of energy, it is not possible for
the drone to safely deliver packages to far away locations and return to the
depot while flying at 6.71 m/s speed. The drone energy consumption increases
as the package weight increases. Therefore, we see from Table 4 that more
locations fall outside the delivery range when the weights of all customer
orders increases from 1.13 Kg to 2.27 Kg and 4.54 Kg. As we see that 45
locations are outside the delivery range of the DJI drones with 6.71 m/s
speed, we excluded these 45 locations for the other analysis in this
subsection to ensure a fair comparison in the required fleet size (i.e.,
required number of drones), required number of battery replacements, and the
total and average energy consumption between these two speeds.

Figure 4 demonstrates the variation in the required number of drones to
deliver all customer orders as the speed changes from 13.41 m/s to 6.71 m/s.
In this experiments, we used the pickup time window to be 15 minutes for the
customer orders. We see that across all three package weights, more drones are
needed with 6.71 m/s speed as compared to 13.41 m/s. The percentage increase
in the required number of drones are 22.2%, 27.7%, and 20% corresponding to
package weights of 1.13 Kg, 2.27 Kg, and 4.54 Kg, respectively, as the drone
speed reduces from 13.41 m/s to 6.71 m/s. This is because, with a slower speed
(i.e., 6.71 m/s), it is not possible to maintain the same pickup time window
with the same number of drones as in 13.41 m/s. However, we see that the
package weight does not have much impact on the required number of drones.
This is because, drone speed and travel time are not affected by the package
weight. One or two additional drones are required as the package weight
increases from 1.13 Kg due to the fact that a higher number of battery
replacements are needed with a larger package weight. Due to this additional
battery replacement time, additional drones are needed to maintain the same
time window.

Figure 4: Effect of drone speed and package weight on the required number of
drones.

Figures 5a and 5b demonstrate the effect of drone speed and package weight on
the total energy consumption in delivering all customer orders and on the
average energy consumption per delivery, respectively. We see that the total
and average energy consumption increases as the drone speed reduces from 13.41
m/s to 6.71 m/s across all three package weights. As mentioned earlier, the
average power consumption by a drone is lower at a slower speed, but the drone
stays in the air for a longer duration to travel the same distance at a slower
speed. Therefore, compared to the 13.41 m/s speed, flying at 6.71 m/s results
in a much larger energy consumption in delivering each customer order,
eventually increasing the total and average energy consumption. We have
observed that the total energy consumption increases by 47.96%, 45.78%, and
53.82% corresponding to the package weights of 1.13 Kg, 2.27 Kg, and 4.54 Kg,
respectively, as the drone speed reduces from 13.41 m/s to 6.71 m/s. The
percentage changes in the average energy consumption per delivery also
demonstrates the same trend and magnitude. It is evident from Figures 5a and
5b that the energy consumption increases as the drones carry larger package
weight at both speed levels, which is very intuitive. The percentage increase
in total energy consumption are 10.03% and 23.45% as the package weight of all
customer orders increases from 1.13 Kg to 2.27 Kg and 4.54 Kg, respectively,
at 13.41 m/s drone speed. We see a similar effect with an increase in the
package weight on energy consumption when the drone speed is 6.71 m/s.

(a) Total energy consumption. (b) Average energy consumption.

Figure 5: Effect of drone speed and package weight on energy consumption.

Figure 6 demonstrates the effect of drone speed and package weight on the
required number of battery replacements in delivering all 81 customer orders.
We see that the drone battery needs to be replaced a substantially larger
number of times in delivering all customer orders at 6.71 m/s speed as
compared to 13.41 m/s speed. This is due to an increased energy consumption at
6.71 m/s speed as discussed earlier. As the energy consumption at 6.71 m/s
speed is higher than at 13.41 m/s speed in delivering a customer order, the
minimum required battery energy is reached more frequently at a slower speed,
thus necessitating more battery replacements.

Figure 6: Effect of drone speed and package weight on the required number of
battery replacements.

The required number of battery replacements also increases as the package
weight increases at the same speed level. Table 5 demonstrates the percentage
increase in the number of battery replacements as the package weight of all
customer orders increases from 1.13 kg for the two speed levels.

Table 5: Effect of package weight on the number of battery replacements. Package Weight (Kg) | Percentage Increase in Number of Battery Replacements
---|---
|  Speed: 13.41 m/s |  Speed: 6.71 m/s
2.27 |  25.0 |  23.33
4.54 |  56.25 |  56.67

###  4.3 Effect of Delivery Method on Energy Consumption

While delivering a package to a customer location, the drone can either land
on the ground, as shown in Figure 3 or hover 20 feet (6.096 meters) above the
ground and drop the package via a winch. As the hovering operation is energy-
intensive, we compare the energy consumption between these two delivery
methods—package dropping and landing with a package to the ground. Depending
on the type of product, the hovering duration while package dropping can be
different, ranging from 30 seconds to several minutes. Therefore, we compared
the total energy consumption in delivering all customer orders via landing
with four different package dropping methods where the hovering durations are
30 seconds, 1 minute, 1.5 minutes, and 2 minutes. In this analysis, we used
the data for the DJI Matrice 600 Pro drone flying at a speed of 13.41 m/s
while carrying a package weight of 1.13 Kg.

We would like to note that compared to landing, the drones save some amount of
ascend and descend energy while package dropping by not descending to the
ground, as well as not ascending from the ground while returning. Table 6
demonstrates the percentage increase in the total energy consumption for using
the different package dropping methods as compared to landing. We see that
when the hovering duration in package dropping is short (e.g., 30 seconds),
the percentage increase in the total energy consumption is not significant
compared to energy consumption in landing. As such, the package dropping also
saves some energy by avoiding to land and ascend from the ground. However, as
the hover duration becomes longer, drones consume a much higher amount of
energy while delivering a package via dropping as compared to landing.

Table 6: Comparison of energy consumption between landing and package dropping. Delivery Method |  Hovering Duration |  % Increase in Energy Consumption
---|---|---
|  |
Package dropping 1 |  30 seconds |  1.45
Package dropping 2 |  1 minute |  6.0
Package dropping 3 |  1.5 minutes |  12.48
Package dropping 4 |  2 minutes |  14.98

###  4.4 Effect of Minimum Required Battery Energy on Delivery Range and
Battery Replacements

We mentioned earlier that a minimum specified amount of energy should be
remaining in the drone battery each time a drone returns to the depot to
ensure the safe operation of the drones. This is because, if the remaining
energy in the drone battery drops below a critical level, the drone will be
grounded while flying. This critical minimum required amount of energy for our
DJI Matrice 600 Pro is 10% of the initial battery energy of 2.16 MJ. However,
business owners may choose a larger value of this minimum required energy than
10% to ensure the safe operation of the drones under adverse conditions, such
as flying in the opposite direction of strong wind. Different business owners
can have different levels of risk preferences and set the minimum required
amount of energy to different levels. Therefore, we analyzed the effect of
different values of this minimum required energy on the delivery range and the
required number of battery replacements in delivering all customer orders.

Table 7 demonstrates the number of delivery locations out of drone range for
four different values of minimum required levels of battery energy—10%, 15%,
20%, and 25% of the initial battery energy—and three different package
weights—1.13 Kg, 2.27 Kg, and 4.54 Kg. We see that more locations fall outside
the delivery range as the minimum required battery energy increases with the
same package weight. This is because as the requirement for remaining energy
in the drone battery after returning from each delivery location increases,
this increased threshold cannot be met for a higher number of locations.
Therefore, with this increased minimum required amount of energy, the number
of customer locations that drones cannot safely deliver packages to increases.
In addition, the number of locations outside the delivery range increases as
the package weight increases within the same minimum required battery energy
level. This is because the energy consumption increases with the package
weight; thus, the minimum required energy threshold cannot be met for a larger
number of locations and fall outside the delivery range.

Table 7: Effect of minimum required battery energy on delivery range. $\mathbf{m}$ denotes the package weight. Minimum Required Battery Energy (KJ) | Number of Locations Outside Delivery Range
---|---
|  $\mathbf{m=1.13}$ Kg |  $\mathbf{m=2.27}$ Kg |  $\mathbf{m=4.54}$ Kg
216 (10%) |  0 |  0 |  6
324 (15%) |  0 |  0 |  10
432 (20%) |  0 |  7 |  12
540 (25%) |  2 |  10 |  14

This minimum required amount of battery energy also affects the required
number of battery replacements in delivering packages to customer locations.
To demonstrate this effect, we conducted numerical analysis for the four
different values of minimum required battery energy with 1.13 Kg package
weight and excluding the two locations outside the delivery range, as shown in
Table 7. Figure 7 demonstrates that the required number of battery
replacements in delivering packages to all 124 customer locations increases as
the minimum required battery energy increases. As the minimum required battery
energy is set to a higher level, the minimum threshold is reached more quickly
during drone operations, which increases the frequency of replacing the drone
batteries. We see from Figure 7 that the required number of battery
replacements increases substantially (i.e., 34%) as the minimum required
energy increases from 10% to 25% of the initial battery energy.

Figure 7: Effect of minimum required battery energy on the required number of
battery replacements.

###  4.5 Effect of Time Window on the Required Fleet Size

We analyzed the impact of a pickup time window requirement of customer orders
on the minimum required drone fleet size (i.e., required number of drones) to
deliver all customer orders. As mentioned in Section 2, we considered a pickup
time window in which a customer wants a drone to pick the product up for
delivery to them. This time window requirement is different for different
products and business types (e.g., 2 minutes for Starbucks coffee vs. 30
minutes for grocery items from Walmart). Our drone deployment optimization
model accounts for this time window preference of customers while finding the
optimal solution—minimum required fleet size, required number of battery
replacements, and energy consumption.

Figure 8 demonstrates the variation in the required number of drones as the
pickup time window increases from 1 to 35 minutes. We see that the required
number of drones in delivering all customer orders decreases as the time
window increases. In a real-life business environment, multiple customer
orders are placed at the same time or their order placement times very close
to each other, which is reflected in the real-life delivery data we used in
our case study. In this real-life business environment, with a more flexible
pickup time window, the same drone can be used to deliver packages to a larger
number of customer orders by meeting the time window. But, while satisfying a
very short time window, it is not possible for a drone to pick up the packages
for multiple customer orders having order placement time close to each other.
Therefore, the required number of drones to deliver all customer orders
increases as the pickup time window decreases. For instance, the required
number of drones (i.e., fleet size) increases by 48% as the time window
reduces from 35 minutes to 1 minute.

Figure 8: Effect of time window on the required number of drones.

Therefore, depending on the business and product type, the minimum required
drone fleet size can vary. Business owners can use our model on their delivery
data to determine the minimum required drone fleet size based on the time
window requirements of their business and product types.

###  4.6 Effect of Drone Flight Path on the Delivery Range, Energy
Consumption, Fleet Size, and Battery Replacements

In real-life operations of drones, it may not always be possible to fly the
drones in a straight path from the business provider’s location to customer
locations due to the presence of no-fly zones (e.g., schools, large buildings,
and restricted private property) in the flight path. Flying over the road
networks is a viable option to avoid these no-fly zones. But, as compared to a
straight path, flying over the road networks requires the drones to travel
longer distances and consume higher amounts of energy in delivering customer
orders. Our hypothesis is that this increased distance and energy consumption
affects drone delivery range, as well as the required fleet size (i.e., number
of drones) and the number of battery replacements. Therefore, using our drone
deployment optimization model, we evaluated the impact of drone flight path
(i.e., straight vs. over the road networks) on the delivery range, minimum
number of drones and battery replacements needed.

To incorporate the road network flight path of the drones in our optimization
model, we used the Open Source Routing Machine (OSRM) API [43] to obtain the
road distance traveled and the number of turns a drone makes to change
direction while traveling to each customer location. Based on our DJI Matrice
600 Pro drone flight test, we consider that a drone hovers 7 seconds on
average to change direction (including the time for deceleration and
acceleration) while flying over the road networks. Using these road distances
and turns, we compute the energy consumed by the DJI Matrice 600 Pro drones
and travel times for all customer locations that are used in the optimization
model. We used the minimum required battery energy as 324 Kilo-Joule (KJ),
which is 15% of the initial battery energy of 2.16 Mega-Joule (MJ) in all the
analyses presented in this subsection, where we used a 15 minute pickup time
window.

Table 8 shows the number of locations out of delivery range of the DJI Matrice
600 Pro for two different flight paths (i.e., straight and over the road
networks), two different speed levels (i.e., 6.71 m/s and 13.41 m/s), and
three different package weights (i.e., 1.13 Kg, 2.27 Kg, and 4.54 Kg). We see
that within the same package weight and speed level, a larger number of
customer locations are out of the drone delivery range as the drones fly over
the road networks as compared to the straight path. This is because the drones
consume substantially higher energy while flying over the road networks.
Therefore, given the battery energy limitation, it is not possible for the
drones to safely deliver packages and return to the depot for a larger number
of locations. Compared to 13.41 m/s, flying over the road networks at the
slower speed (i.e., 6.71 m/s) substantially limits the drone delivery range.
For instance, 82 of the 126 locations fall outside the delivery range when
drones fly over the road networks at 6.71 m/s speed. Therefore, in the
remaining analysis in this subsection, we excluded these 82 locations from the
delivery data to compare the results for both speed levels and flight paths.

Table 8: Effect of flight path on delivery range. $\mathbf{m}$ denotes the package weight. Drone Speed (m/s) |  Flight Path | Number of Locations Outside Delivery Range
---|---|---
|  |  $\mathbf{m=1.13}$ Kg |  $\mathbf{m=2.27}$ Kg |  $\mathbf{m=4.54}$ Kg
13.41 |  Straight |  0 |  0 |  10
|  Over Road Network |  15 |  23 |  37
6.71 |  Straight |  27 |  29 |  45
|  Over Road Network |  49 |  57 |  82

Figures 9a and 9b demonstrate the effect of flight path and package weight on
the required fleet size (i.e., required number of drones) to deliver packages
to all customer locations with drone speeds of 13.41 m/s and 6.71 m/s,
respectively. We see that a larger number of drones are needed as the drones
fly over the road networks as compared to the straight path at both speed
levels. This is because, as compared to the straight path, while flying over
the road networks, drones travel much longer distances to deliver packages to
customer locations, increasing the travel time. With this increased travel
time over the road networks for each delivery, it is not possible to meet the
pickup time window with the same number of drones as in flying in the straight
path with shorter distance and travel time. Therefore, a larger number of
drones are needed to deliver the packages meeting the time window requirement
while flying over the road networks. When the DJI Matrice 600 Pro drones are
flying over the road networks at 13.41 m/s speed, the percentage increase in
the required number of drones across the three different package weights are
22.2%, 22.2%, and 33.3% as compared to flying in the straight path. For the
6.71 m/s drone speed, the percentage increase in the required number of drones
are 40.0%, 27.3%, and 25.0% as compared to flying in the straight path
corresponding to the three different package weights. However, it is evident
from Figures 9a and 9b that the package weight does not have much noticeable
impact on the number of drones as the package weight does not affect drone
speed and travel time.

(a) Required number of drones for drone speed of 13.41 m/s (b) Required number
of drones for drone speed of 6.71 m/s

Figure 9: Effect of flight path and package weight on the required number of
drones.

Figures 10a and 10b demonstrate the effect of flight path and package weight
on the total energy consumption in delivering all customer orders at the drone
speeds of 13.41 m/s and 6.71 m/s, respectively. We see that the total energy
consumption increases substantially as the drones fly over the road networks
as compared to flying in a straight path at both speed levels across all three
package weights. This is because flying over the road networks requires the
drones to travel a longer distance and stay in the air for a longer amount of
time, resulting in an increased energy consumption. We have observed that the
total energy consumption increases by 72.22%, 71.24%, and 70.54% corresponding
to the package weights of 1.13 Kg, 2.27 Kg, and 4.54 Kg, respectively, as the
drones fly over the road networks than in the straight paths at 13.41 m/s
speed. The percentage increase in the total energy consumption due to flying
over the road networks at 6.71 m/s speed are 64.85%, 64.14%, and 64.87% across
three different package weights. The average energy consumption per delivery
also demonstrate the same trend and magnitude (see Figure C.2 in Appendix C).
It is evident from Figures 10a and 10b that the energy consumption increases
as the drones carry larger package weight at both speed levels, which is very
intuitive.

(a) Total energy consumption for drone speed of 13.41 m/s (b) Total energy
consumption for drone speed of 6.71 m/s

Figure 10: Effect of flight path and package weight on total energy
consumption.

Figures 11a and 11b demonstrate that the required number of battery
replacements increases substantially as the drones fly over the road networks
as compared to a straight path for both speed levels. For instance, the
required number of battery replacements increases by 200% as the drones fly
over the road networks compared to flying in a straight path at 13.41 m/s
speed and all customer orders weigh 1.13 Kg. This is due to the increased
energy consumption while flying over the road networks as explained earlier.
As more energy is consumed in delivering each customer order, the minimum
required battery energy is reached more frequently, resulting in a larger
number of battery replacements.

(a) Required number of battery replacements for drone speed of 13.41 m/s. (b)
Required number of battery replacements for drone speed of 6.71 m/s.

Figure 11: Effect of flight path and package weight on the required number of
battery replacements.

###  4.7 Effect of Mixed Drone Fleet on Energy Consumption and Required Number
of Drones

We observed that due to its small size and limited battery capacity, the
delivery range and package weight carrying capacity of the Tarot 650 drone
(rotary quadcopter) is much smaller compared to the DJI Matrice 600 Pro
(rotary hexacopter). But our drone flight test data shows that the Tarot 650
drone is more energy-efficient than the DJI Matrice 600 Pro drone while
carrying the same package weight for the same distance. Therefore, our
assumption is that business owners can substantially reduce energy consumption
by using a mixed fleet of drones consisting of these both types of drones such
that the Tarot 650 drones are used to deliver smaller packages to shorter
distances whereas larger packages are delivered longer distances using the DJI
Matrice 600 Pro drones.

Using the modeling approach presented in Section 3.2, we evaluated the effect
of using both Tarot and DJI drones in a mixed fleet on the number of locations
served, energy consumption, and the required number of drones of each type. As
the maximum weight carrying capacity of the Tarot 650 drone is 1.13 Kg, we
used the package weight of 1.13 Kg for both types of drones in the analysis.
Table 9 demonstrates that 113 of the 126 locations are served using the Tarot
drones, whereas only 13 locations are served using DJI drones when all drones
are operated at 13.41 m/s speed. We see that the Tarot drones contribute
61.95% to the total energy consumption in delivering packages to 113
locations, whereas the DJI drones contribute 38.05% despite delivering
packages to only 13 locations. DJI drones are only used to deliver packages to
locations outside the delivery range of Tarot. We see a similar pattern in the
number of locations served and total energy consumption by the mixed fleet of
drones when the drones are operated at 6.71 m/s speed, as shown in Table 9,
which also demonstrates the optimal number of drones required for each type of
drone in the mixed fleet.

Table 9: Number of locations served, percentage of total energy consumption, and the required number of drones for different drone types in a mixed fleet. Drone Speed (m/s) | DJI Matrice 600 Pro | Tarot 650
---|---|---
|  Number of Locations Served |  % of Total Energy Consumption |  Required Numbers of Drones |  Number of Locations Served |  % of Total Energy Consumption |  Required Numbers of Drones
13.41 |  13 |  38.05 |  5 |  113 |  61.95 |  30
6.71 |  21 |  53.74 |  9 |  77 |  46.26 |  21

We analyzed how much does total energy consumption decreased due to using a
mixed fleet of drones compared to using a homogeneous fleet with only DJI
drones. Figure 12 demonstrates the total energy consumption by the mixed fleet
of drones and the homogeneous fleet with only DJI drones when all drones are
operated at 13.41 m/s speed. We see that using a mixed fleet with both Tarot
and DJI drones substantially reduces the energy consumption in delivering
customer orders compared to the homogeneous fleet with only DJI drones. For
instance, when the drones are operated at 13.41 m/s speed, using a mixed fleet
of drones reduces the total energy consumption by 48.52% compared to the
homogeneous fleet with only DJI drones.

Figure 12: Comparison of total energy consumption between different fleet
types.

##  5 Conclusion

We studied a drone deployment optimization problem for direct delivery of
goods from a retail business location that acts as the central depot to
customer locations, where each drone visits a single customer location on each
trip and returns to the depot before visiting the next customer. In this
problem, the goal of the business owner is to optimally route the drones that
minimizes the total energy consumption, the required fleet size (i.e.,
required number of drones), and the required number of battery replacements in
delivering customer orders maintaining a specified pickup time window. We
proposed a new mathematical optimization approach to solve the problem for
both homogeneous and mixed fleets of drones. The mathematical model
incorporates the specified time window, factors affecting the drone energy
consumption, and the drone operating parameters (e.g., drone speed, package
weight, flight path, the minimum required battery energy, and fleet type) and
optimally decides the routing of drones so that the minimum number of drones
are used, the number of times drone battery is replaced is minimum and the
total energy consumption is minimum in delivering customer orders. We also
proposed two valid inequalities to improve the computational efficiency of the
mathematical optimization models.

We conducted numerical experiments using real drone flight test data to
provide new insights into the effect of different drone operating conditions
on the performance of drone-based delivery. Results demonstrate that the total
and average energy consumption increases as the drones fly at a slower speed
due to staying in the air for a longer time. For instance, the total energy
consumption for DJI drones (i.e., rotary hexacopter) increases by 47.96% as
the drone speed reduces from 13.41 m/s to 6.71 m/s when all customer orders
weigh 1.13 Kg. Energy consumption increases substantially as the drones fly
over the road network as compared to a straight path; the total energy
consumption for DJI drones increases by 72.22% as the drones fly over the road
networks compared to the straight path with all customers weighing 1.13 Kg.
Drone energy consumption also increases with package weight and package
dropping delivery method that requires a longer hover duration. Results
demonstrate that using a mixed fleet of drones (i.e., a fleet containing both
rotary hexacopters and quadcopters) reduces the total energy consumption by
48.52% compared to the homogeneous fleet with only hexacopter drones when all
drones are operated at 13.41 m/s speed. The delivery range of drones decreases
as the package weight increases, drone speed decreases, and the minimum
required battery energy increases.

The required fleet size increases as the pickup time window of the customer
orders decreases, as a higher number of drones are needed to pick up the
products within a shorter time window. The number of drones required increases
by 48% as the time window reduces from 35 minutes to 1 minute. The required
number of drones increases as the drone speed decreases, as a higher number of
drones are required to maintain the same pickup time window when the drones
are flying at a slower speed. A higher number of drones are needed when the
drones fly over the road networks compared to flying in a straight path; the
required number of drones increases by 22.2% as the drones fly over the road
networks as compared to flying in a straight path.

The required number of battery replacements increases as the package weight
and minimum required battery energy increases and speed decreases. As the
drones fly over the road networks, the drone battery needs to be replaced a
substantially larger number of times as compared to flying in a straight path.
This is mainly because of the higher energy consumption due to traveling long
distances over the road network. The required number of battery replacements
increases by 200% as the drones fly over the road network compared to flying
in a straight path when all customer orders weigh 1.13 Kg and drones fly at
13.41 m/s speed. Therefore, business owners need to have a substantially
larger number of additional drone batteries when their drones need to be flown
over the road networks as compared to flying in a straight path.

The managerial insights drawn from the numerical results based on real drone
flight tests and delivery data will help retail business owners better
understand the potential of drones under different conditions. Another
practical implication of our research is that retail business owners can use
our proposed optimization method to make investment and operating decisions in
using their drones to deliver customer orders. Specifically, a retail business
owner can use our optimization method with their drone energy profile and
delivery data to decide on the minimum required fleet size (i.e., the required
number of drones) and the number of drones in each type for a mixed fleet
under different conditions (e.g., time window requirement, flight path, drone
speed). The business owners can compute the number of additional batteries
they need to have to operate the drone fleet depending on their drone
operating conditions. Additionally, business owners can evaluate how different
drone operating parameters specific to their business and products affect the
total energy consumption.

## Acknowledgments

We thank the U.S. Department of Energy Vehicle Technology Office (VTO) for
funding and supporting this work. This work is supported by the U.S.
Department of Energy under Department of Energy Idaho Operations Office
Contract No. DE-AC07-05ID14517.

## References

  * [1] Chun Cheng, Yossiri Adulyasak, and Louis-Martin Rousseau.  Drone routing with energy function: Formulation and exact algorithm.  Transportation Research Part B: Methodological, 139:364–387, 2020\.
  * [2] Monica Gentili, Pitu B Mirchandani, Alessandro Agnetis, and Zabih Ghelichi.  Locating platforms and scheduling a fleet of drones for emergency delivery of perishable items.  Computers & Industrial Engineering, 168:108057, 2022.
  * [3] Joseph YJ Chow.  Dynamic uav-based traffic monitoring under uncertainty as a stochastic arc-inventory routing policy.  International Journal of Transportation Science and Technology, 5(3):167–185, 2016.
  * [4] Chase C Murray and Amanda G Chu.  The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery.  Transportation Research Part C: Emerging Technologies, 54:86–109, 2015.
  * [5] Roger Clarke.  Understanding the drone epidemic.  Computer Law & Security Review, 30(3):230–246, 2014.
  * [6] New York Times.  1.5 Million Packages a Day: The Internet Brings Chaos to N.Y. Streets, 2019.  Accessed 7/21/2019.
  * [7] Accenture.  Faster, saferand greener.  https://storage.googleapis.com/wing-static-us/us/DallasFebruary 2021.
  * [8] McKinsey and Company.  Parcel Delivery: The future of last mile, 2019.  Accessed 7/21/2019.
  * [9] Amazon.com Inc.  Amazon prime air prepares for drone deliveries.  https://www.aboutamazon.com/news/transportation/amazon-prime-air-prepares-for-drone-deliveries, June 2022.
  * [10] Daniela Rojas Viloria, Elyn L Solano-Charris, Andrés Muñoz-Villamizar, and Jairo R Montoya-Torres.  Unmanned aerial vehicles/drones in vehicle routing problems: a literature review.  International Transactions in Operational Research, 28(4):1626–1657, 2021.
  * [11] Giusy Macrina, Luigi Di Puglia Pugliese, Francesca Guerriero, and Gilbert Laporte.  Drone-aided routing: A literature review.  Transportation Research Part C: Emerging Technologies, 120:102762, 2020.
  * [12] Nils Boysen, Stefan Fedtke, and Stefan Schwerdfeger.  Last-mile delivery concepts: a survey from an operational research perspective.  OR Spectrum, 43(1):1–58, 2021.
  * [13] Alena Otto, Niels Agatz, James Campbell, Bruce Golden, and Erwin Pesch.  Optimization approaches for civil applications of unmanned aerial vehicles (uavs) or aerial drones: A survey.  Networks, 72(4):411–458, 2018.
  * [14] Walton Pereira Coutinho, Maria Battarra, and Jörg Fliege.  The unmanned aerial vehicle routing and trajectory optimisation problem, a taxonomic review.  Computers & Industrial Engineering, 120:116–128, 2018.
  * [15] Sung Hoon Chung, Bhawesh Sah, and Jinkun Lee.  Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions.  Computers & Operations Research, 123:105004, 2020.
  * [16] Emmanouil N Barmpounakis, Eleni I Vlahogianni, and John C Golias.  Unmanned aerial aircraft systems for transportation engineering: Current practice and future challenges.  International Journal of Transportation Science and Technology, 5(3):111–122, 2016.
  * [17] Stefan Poikonen, Xingyin Wang, and Bruce Golden.  The vehicle routing problem with drones: Extended models and connections.  Networks, 70(1):34–43, 2017.
  * [18] Xingyin Wang, Stefan Poikonen, and Bruce Golden.  The vehicle routing problem with drones: several worst-case results.  Optimization Letters, 11(4):679–697, 2017.
  * [19] Neil Mathew, Stephen L Smith, and Steven L Waslander.  Planning paths for package delivery in heterogeneous multirobot teams.  IEEE Transactions on Automation Science and Engineering, 12(4):1298–1308, 2015.
  * [20] Pratap Tokekar, Joshua Vander Hook, David Mulla, and Volkan Isler.  Sensor planning for a symbiotic uav and ugv system for precision agriculture.  IEEE Transactions on Robotics, 32(6):1498–1511, 2016.
  * [21] Luigi Di Puglia Pugliese and Francesca Guerriero.  Last-mile deliveries by using drones and classical vehicles.  In A. Sforza and C. Sterle, editors, International Conference on Optimization and Decision Science, volume 217, pages 557–565, 2017.
  * [22] Andy M Ham.  Integrated scheduling of m-truck, m-drone, and m-depot constrained by time-window, drop-pickup, and m-visit using constraint programming.  Transportation Research Part C: Emerging Technologies, 91:1–14, 2018.
  * [23] Chase C Murray and Ritwik Raj.  The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones.  Transportation Research Part C: Emerging Technologies, 110:368–398, 2020.
  * [24] Patchara Kitjacharoenchai, Mario Ventresca, Mohammad Moshref-Javadi, Seokcheon Lee, Jose MA Tanchoco, and Patrick A Brunese.  Multiple traveling salesman problem with drones: Mathematical model and heuristic approach.  Computers & Industrial Engineering, 129:14–30, 2019.
  * [25] Andreas Heimfarth, Manuel Ostermeier, and Alexander Hübner.  A mixed truck and robot delivery approach for the daily supply of customers.  European Journal of Operational Research, In Press, 2022.
  * [26] Hailong Huang, Andrey V Savkin, and Chao Huang.  Round trip routing for energy-efficient drone delivery based on a public transportation network.  IEEE Transactions on Transportation Electrification, 6(3):1368–1376, 2020.
  * [27] Ho Young Jeong, Byung Duk Song, and Seokcheon Lee.  Truck-drone hybrid delivery routing: Payload-energy dependency and no-fly zones.  International Journal of Production Economics, 214:220–233, 2019\.
  * [28] Vivek Yadav and Anand Narasimhamurthy.  A heuristics based approach for optimizing delivery schedule of an unmanned aerial vehicle (drone) based delivery system.  In 2017 Ninth International Conference on Advances in Pattern Recognition (ICAPR), pages 1–6. IEEE, 2017.
  * [29] Khin Thida San, Eun Young Lee, and Yoon Seok Chang.  The delivery assignment solution for swarms of uavs dealing with multi-dimensional chromosome representation of genetic algorithm.  In 2016 IEEE 7th Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON), pages 1–7. IEEE, 2016.
  * [30] Byung Duk Song, Kyungsu Park, and Jonghoe Kim.  Persistent uav delivery logistics: Milp formulation and efficient heuristic.  Computers & Industrial Engineering, 120:418–428, 2018.
  * [31] Kevin Dorling, Jordan Heinrichs, Geoffrey G Messier, and Sebastian Magierowski.  Vehicle routing problems for drone delivery.  IEEE Transactions on Systems, Man, and Cybernetics: Systems, 47(1):70–85, 2016.
  * [32] Boualem Rabta, Christian Wankmüller, and Gerald Reiner.  A drone fleet model for last-mile distribution in disaster relief operations.  International Journal of Disaster Risk Reduction, 28:107–112, 2018\.
  * [33] Asma Troudi, Sid-Ali Addouche, Sofiene Dellagi, and Abderrahman El Mhamedi.  Sizing of the drone delivery fleet considering energy autonomy.  Sustainability, 10(9):3344, 2018.
  * [34] Fanhui Kong, Jianqiang Li, Bin Jiang, Huihui Wang, and Houbing Song.  Trajectory optimization for drone logistics delivery via attention-based pointer network.  IEEE Transactions on Intelligent Transportation Systems, pages 1 – 13, 2022.
  * [35] Youngmin Choi and Paul M Schonfeld.  Optimization of multi-package drone deliveries considering battery capacity.  In Proceedings of the 96th Annual Meeting of the Transportation Research Board, Washington, DC, USA, pages 8–12, 2017.
  * [36] Bruno N Coelho, Vitor N Coelho, Igor M Coelho, Luiz S Ochi, Roozbeh Haghnazar, Demetrius Zuidema, Milton SF Lima, and Adilson R da Costa.  A multi-objective green uav routing problem.  Computers & Operations Research, 88:306–315, 2017.
  * [37] Wen-Chyuan Chiang, Yuyu Li, Jennifer Shang, and Timothy L Urban.  Impact of drone delivery on sustainability and cost: Realizing the uav potential through vehicle routing optimization.  Applied Energy, 242:1164–1175, 2019.
  * [38] Miguel A Figliozzi.  Lifecycle modeling and assessment of unmanned aerial vehicles (drones) co2e emissions.  Transportation Research Part D: Transport and Environment, 57:251–261, 2017.
  * [39] Darshan Chauhan, Avinash Unnikrishnan, and Miguel Figliozzi.  Maximum coverage capacitated facility location problem with range constrained drones.  Transportation Research Part C: Emerging Technologies, 99:1–18, 2019.
  * [40] Angelo Trotta, Marco Di Felice, Federico Montori, Kaushik R Chowdhury, and Luciano Bononi.  Joint coverage, connectivity, and charging strategies for distributed uav networks.  IEEE Transactions on Robotics, 34(4):883–900, 2018.
  * [41] Maria Gabriela S Furtado, Pedro Munari, and Reinaldo Morabito.  Pickup and delivery problem with time windows: a new compact two-index formulation.  Operations Research Letters, 45(4):334–341, 2017.
  * [42] IBM.  Ilog cplex optimization studio.  http://www.ibm.com/software/commerce/optimization/cplex-optimizer/, December 2019.
  * [43] Vaclav Dekanovsky.  Driving distance between two or more places in python.  https://towardsdatascience.com/driving-distance-between-two-or-more-places-in-python-89779d691def, December 2020.

## Appendices

##  Appendix A Flowchart of the Mixed Fleet of Drones Modeling

Figure A.1 demonstrates the two-phase modeling approach proposed to solve the
drone deployment optimization problem for a mixed fleet of drones.

Figure A.1: Two-phase modeling approach for mixed fleet of drones.

##  Appendix B Energy Consumption and Flight Time Data

Table B.1 presents the average power consumption data for different flight
segments of our DJI Matrice 600 Pro drone at two different speed levels and
four different package weights.

Table B.1: Power consumption of the DJI Matrice 600 Pro drone for the flight segments. Drone Speed (m/s) |  Package Weight (Kg) | Average Power (Joule per Second) in Flight Segments
---|---|---
|  |  Ascend |  Descend |  Forward Flight |  Hover
13.41 |  0 |  1351.4456 |  1023.8680 |  1186.5048 |  1039.2542
|  1.13 |  1487.3006 |  1104.4719 |  1479.2276 |  1211.6308
|  2.27 |  1746.2067 |  1422.7263 |  1718.7145 |  1406.6182
|  4.54 |  2233.5910 |  1738.2538 |  2044.0478 |  1759.3900
6.71 |  0 |  1351.4456 |  1023.8680 |  1052.5789 |  1039.2542
|  1.13 |  1487.3006 |  1104.4719 |  1232.8998 |  1211.6308
|  2.27 |  1746.2067 |  1422.7263 |  1401.8190 |  1406.6182
|  4.54 |  2233.5910 |  1738.2538 |  1878.1490 |  1759.3900

Table B.2 presents the flight time of different flight segments of our DJI
Matrice 600 Pro drone test at two different speed levels. Flight durations are
the same for different package weights at the same speed level.

Table B.2: Flight time of the DJI Matrice 600 Pro drone for the flight segments. Drone Speed (m/s) | Duration (Seconds) of Flight Segments
---|---
|  Ascend |  Descend | Forward Flight |  Hover
|  |  |  Time/mile |  Time/kilometer |
13.41 |  24.6 |  41.80 |  125.0 |  78.125 |  5.0
6.71 |  24.6 |  41.80 |  245.0 |  153.125 |  5.0

Table B.3 presents the average power consumption data for different flight
segments of our Tarot 650 drone test at two different speed levels and two
different package weights.

Table B.3: Power consumption of the Tarot 650 drone for the flight segments. Drone Speed (m/s) |  Package Weight (Kg) | Average Power (Joule per Second) in Flight Segments
---|---|---
|  |  Ascend |  Descend |  Forward Flight |  Hover
13.41 |  0 |  419.9395 |  370.3456 |  389.3249 |  369.2475
|  1.13 |  638.3887 |  589.3817 |  596.6649 |  564.6385
6.71 |  0 |  419.9395 |  370.3456 |  381.6552 |  369.2475
|  1.13 |  638.3887 |  589.3817 |  580.4716 |  564.6385

Table B.4 presents the flight time of different flight segments of our Tarot
650 drone test at two different speed levels. Flight durations are the same
for different package weights at the same speed level.

Table B.4: Flight time of the Tarot 650 drone for the flight segments. Drone Speed (m/s) | Duration (Seconds) of Flight Segments
---|---
|  Ascend |  Descend | Forward Flight |  Hover
|  |  |  Time/mile |  Time/kilometer |
13.41 |  32.56 |  38.31 |  130.0 |  80.78 |  5.0
6.71 |  32.56 |  38.31 |  250.0 |  155.34 |  5.0

##  Appendix C Effect of Drone Flight Path on Average Energy Consumption

Figures C.2a and C.2b demonstrate the effect of flight path and package weight
on the average energy consumption per delivery of the DJI Matrice 600 Pro
drone at drone speeds of 13.41 m/s and 6.71 m/s, respectively. The average
energy consumption increases by 72.22%, 71.25%, and 70.54% corresponding to
the package weights of 1.13 Kg, 2.27 Kg, and 4.54 Kg, respectively, as the
drones fly over the road networks than the straight paths at 13.41 m/s speed.
The percentage increase in the average energy consumption due to flying over
the road networks at 6.71 m/s speed are 64.48%, 64.13%, and 64.87% across
three different package weights.

(a) Average energy consumption for drone speed of 13.41 m/s.

(b) Average energy consumption for drone speed of 6.71 m/s.

Figure C.2: Effect of flight path and package weight on the average energy
consumption per delivery.