We present our ongoing work on the cooperation between a truck and drones in a last-mile package delivery scenario. We model this application as an optimization problem where each delivery is associated with a cost (drone's energy), a pro t (delivery's priority), and a time interval (launch and rendezvous times from and to the truck). We aim to nd an optimal scheduling for drones that maximizes the overall pro t subject to the energy constraints while ensuring that the same drone performs deliveries whose time intervals do not intersect. After seeing that this problem is NP -hard, we rst devise an optimal Integer Linear Programming (ILP) formulation. We then design an optimal pseudo-polynomial algorithm using dynamic programming and a polynomial-time approximation algorithm that exploits optimal coloring on interval graphs for the single drone case. We also provide an approximation algorithm for the multiple drone case.
With the advent of drones, the research and industrial communities are
currently seeking to exploit this new technology in many civilian applications. The
growing interest in such applications is due to the fact that drones can perform
challenging tasks very e ciently [
In this work, we study the cooperation between a truck and a eet of drones in
the last-mile delivery scenario to improve its e ectiveness and e ciency. Drones
Copyright© 2021 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0)
can deliver small packages quickly as they can easily traverse di cult terrain,
often using shorter routes, which would otherwise be demanding for trucks or
robots [
We assume that the location of the customers and the associated truck's route are known before starting the deliveries. Therefore, before leaving the depot, the delivery company entrusts the deliveries to the drone and designs a plan for the drone's ying sub-routes to accelerate deliveries, considering not only the energy used by the drone but also the generated pro ts. Since drones are energy-constrained, a delivery has a cost in terms of required energy, and can be only performed if the drone's residual energy is su cient to allow a round trip to/from the truck. Furthermore, deliveries can have con icts if they cannot be performed by the same drone, i.e., if the corresponding sub-routes intersect with each other. Also, each delivery has an associated pro t which characterizes its importance (e.g., higher pro t means higher priority). So, given the truck's route, the goal is to plan an appropriate schedule for the drones to maximize pro ts subject to the drone's limited battery capacity and delivery con icts. 2
We consider a 2-D delivery area A where m drones carried by a truck, perform a set D = f 1; : : : ; ng A of n deliveries. The truck does not perform deliveries; it only carries the drones within A. The truck's tour is given in input and is xed; it starts and nishes at the depot from where the deliveries start.
Due to payload constraints, we assume that each drone can deliver a single package at a time. A drone takes o from the truck along a road with a package, delivers that package to customer i, and returns to the rendezvous location to rejoin the truck. Hence, a launch point iL and a rendezvous point iR on the truck's path are associated to each delivery i. Speci cally, when the truck reaches the launching point iL on the road, the drone detaches itself from the truck and then ies towards the delivery. While the drone moves towards i, the truck continues to move along its route until it reaches the rendezvous point where it will meet up again with the drone.
For each delivery i, we de ne the cost wi 2 N 0 in terms of drone's energy
required (it considers the payload weight, distances iL i and i iR, external
factors like wind [
For a single drone, the goal is to select a viable subset S I of deliveries such that its energy cost C(S) = Pi2S wi is no more than the drone's battery B and the overall pro t P(S) = Pi2S pi is maximized. Similarly, for multiple drones, we aim to select a feasible subset S = fS1 ; : : : ; Smg I partitioned among m drones such that the overall pro t P(S ) is maximized and each drone has enough energy to accomplish its deliveries. Due to the fact that deliveries have con icts and drones have a limited battery capacity, it is not guaranteed that all the deliveries will be performed. Let us now de ne the delivery scheduling problem with drones.
deliveries, m the number of drones, and B the energy budget of each drone. The DSP aims to nd a family S = fS1 ; : : : ; Smg I of m feasible subsets with Sp \ Sq = ?, for 1 p 6= q m, such that the overall pro t P(S ) = Pi2S pi is maximized. Formally,
S =
arg max S=fS1;:::;Smg I
P(S) s.t. C(Si)
B 8i = 1; : : : ; m
As de ned, DSP represents a generalization of the classic 0{1 Knapsack Problem (KP). It follows that DSP is an NP -hard problem. 2.1
The DSP can be optimally solved using an Integer Linear Programming (ILP) formulation. We enumerate the deliveries as N = f1; : : : ; ng, and drones as M = f1; : : : ; mg. Let xij 2 f0; 1g be a decision variable that is 1 if the delivery j 2 N is accomplished by the drone i 2 M, 0 otherwise. Finally, the ILP formulation is given by: max Pm i=1
Pn
j=1 pj xij Pn
j=1 wj xij Pm
i=1 xij xij + xik xij 2 f0; 1g; 1; 1;
B; 8i 2 M 8j 2 N 8i 2 M; 8j; k 2 N s:t: Ij \ Ik 6= ? 8i 2 M; 8j 2 N (1) (2) (3) (4) (5)
The objective function (1) aims to maximize the overall pro t using m drones. About the constraints, (2) states that each drone has an energy budget B; (3) forces deliveries to be executed by at most one drone; and (4) avoids the fact that two incompatible deliveries are performed by the same drone. This section proposes three novel algorithms for DSP, in particular, an optimal (Opt-S) and an approximation (Apx-S) algorithm for the single drone case, and an approximation (Apx-M) algorithm for multiple drones case. 3.1
Opt-S optimally solves the special case of DSP that uses a single drone, i.e., m = 1. It requires O(n log n + nB) time and O(nB) space, where B is an integer.
Before proceeding, let the set of intervals be sorted in non-decreasing order of the rendezvous times. Let (i) be the largest index 1 j i 1 such that tR(i) < tiL, and (i) = 0 if no interval j < i nishes before i starts. Then, for each interval Ii, we can nd the largest non-intersecting index (i) that precedes i, that is, tR(i) < tiL. Then, all the intervals between I (i)+1 and Ii 1 intersect with i. So, it follows that for each interval Ii, we can nd the largest con ict-free interval (i) that precedes i. The values (i) for 1 i n can be computed in linear time in a preprocessing phase.
Now, we can introduce our algorithm for DSP based on dynamic programming. A table M of size n B is created. The value M (i; b) is the maximum gain achievable by considering the rst i intervals and budget b and it is computed as follow: M (i; b) = maxfM (i 1; b); pi + M ( (i); b wi)g if the budget b is su cient to serve Ii whose cost is wi; or M (i; b) = M (i 1; b) if the drone does not have enough budget to make the delivery, i.e., wi > b. Then, as a base case, M (i; b) = 0 if i = 0 or b = 0. This algorithm will give us the maximum pro t achievable with a single drone in cell M [n; B] in pseudo-polynomial time. Theorem 1. Opt-S optimally solves DSP with a single drone in O(n log n + nB) time and O(nB) space. 3.2
Apx-S solves DSP with a single drone. It requires O(n log n + h(n)) time and
O(n) space, where h(n) is the time required by a subroutine used in it. The
main idea of Apx-S is that we rst invoke an optimal polynomial-time
graphcoloring algorithm for chordal graphs to divide the set of intervals into several
subsets based on the minimum coloring of I [
Theorem 2. Apx-S provides a solution for DSP with an approximation ratio of for a single drone, where denotes the chromatic number of the interval graph induced from the deliveries in I, and is the approximation ratio of an algorithm that maximizes KP. 3.3
Apx-M solves DSP with multiple drones exploiting dynamic programming, requiring O(m(n log n + nB)) time and O(nB) space.
The strategy behind Apx-M is that we sequentially perform the optimal algorithm Opt-S on the current residual not assigned deliveries for each drone, starting from the entire set I. In fact, by merging all the computed single-drone solutions, we get the global solution.
Theorem 3. Apx-M provides a solution for DSP with an approximation ratio of m1 for multiple drones, where m denotes the number of drones. 4
We presented our ongoing work on the cooperation between a truck and a eet of drones in the context of last-mile package deliveries. We formalized the Delivery Scheduling Problem (DSP), devising an optimal ILP formulation, and providing three novel algorithms for the single and multiple drone scenario. As future research directions, we would like to improve the problem setting taking into account also the fuel consumption of the truck while studying its optimal path. It is also worth analyzing last-mile deliveries considering a drone that can carry more than one package at a time. Finally, it would be interesting to study this problem in an adaptive stochastic optimization problem where either the travel costs or the energy consumption are dynamic.