318
S. Manna and A. Narasimhamurthy
to $1 in contrast with $12.92 by UPS ground next-day service. Existing delivery
services that use drones include DHL’s parcel service to the island of Juist in the
North Sea and Zipline’s service using fixed-wing drones started in Rwanda in 2016
[9].
Many innovative solutions for deliveries using drones have been proposed [3–7]
Many proposed route planning approaches formulate an optimization problem, often
making restrictive assumptions, in most cases these optimization problems are NPhard or require significant computation. A solution that is intended to be deployed
online should be lightweight and must be able to easily deal with dynamic updates
of orders. In this work, we mostly focus on the scenario of a single warehouse and
one drone servicing orders of multiple customers. This would be directly applicable
in scenarios such as where a drone is used along with trucks (e.g. [3]), also this can
be considered as a sub-routine when solving the more general cases.
2 Description and Notation
The general problem being addressed may be stated as follows:
Given a list of warehouses (locations and inventory of items), a set of customer
orders (locations, product ID and quantity of each item ordered), and the initial
locations of a set of drones, determine a delivery schedule so as to service all orders
and minimize the total distance covered.
We introduce some notation that will be used in the rest of the paper. We assume
there is a warehouse H with a sufficient quantity of each product to fulfill all orders
and that the weight of a single unit of each product is less than the capacity M of the
drone. All locations are specified using a 2D coordinate system, with the warehouse
located at the origin (0,0). All customer locations are assumed to be under the drone
flying area.
A trip starts from the warehouse H, visits certain customers and ends at the warehouse H (e.g. H → c i → c j → H). We define a schedule to be a sequence of such
trips such that all orders that could be serviced are fulfilled.
Let d HC be the list of customers sorted according to increasing distance from the
warehouse (refer example in Table 3(a)).
Additionally, the following supporting data structures are computed in the
beginning and updated repeatedly.
• A list D, where the i th element of D is the list of other customers sorted according
to distance from c i (refer example in Table 3(b)).
• A list/array R, which stores status of each order (Order Serviced: True/False).
S. Manna and A. Narasimhamurthy
to $1 in contrast with $12.92 by UPS ground next-day service. Existing delivery
services that use drones include DHL’s parcel service to the island of Juist in the
North Sea and Zipline’s service using fixed-wing drones started in Rwanda in 2016
[9].
Many innovative solutions for deliveries using drones have been proposed [3–7]
Many proposed route planning approaches formulate an optimization problem, often
making restrictive assumptions, in most cases these optimization problems are NPhard or require significant computation. A solution that is intended to be deployed
online should be lightweight and must be able to easily deal with dynamic updates
of orders. In this work, we mostly focus on the scenario of a single warehouse and
one drone servicing orders of multiple customers. This would be directly applicable
in scenarios such as where a drone is used along with trucks (e.g. [3]), also this can
be considered as a sub-routine when solving the more general cases.
2 Description and Notation
The general problem being addressed may be stated as follows:
Given a list of warehouses (locations and inventory of items), a set of customer
orders (locations, product ID and quantity of each item ordered), and the initial
locations of a set of drones, determine a delivery schedule so as to service all orders
and minimize the total distance covered.
We introduce some notation that will be used in the rest of the paper. We assume
there is a warehouse H with a sufficient quantity of each product to fulfill all orders
and that the weight of a single unit of each product is less than the capacity M of the
drone. All locations are specified using a 2D coordinate system, with the warehouse
located at the origin (0,0). All customer locations are assumed to be under the drone
flying area.
A trip starts from the warehouse H, visits certain customers and ends at the warehouse H (e.g. H → c i → c j → H). We define a schedule to be a sequence of such
trips such that all orders that could be serviced are fulfilled.
Let d HC be the list of customers sorted according to increasing distance from the
warehouse (refer example in Table 3(a)).
Additionally, the following supporting data structures are computed in the
beginning and updated repeatedly.
• A list D, where the i th element of D is the list of other customers sorted according
to distance from c i (refer example in Table 3(b)).
• A list/array R, which stores status of each order (Order Serviced: True/False).