=Paper=
{{Paper
|id=Vol-3072/paper4
|storemode=property
|title=Cooperative Truck-Drone Scheduling Approach for Last-Mile Deliveries
|pdfUrl=https://ceur-ws.org/Vol-3072/paper4.pdf
|volume=Vol-3072
|authors=Francesco Betti Sorbelli,Federico Corò,Sajal K. Das,Lorenzo Palazzetti,Cristina M. Pinotti
|dblpUrl=https://dblp.org/rec/conf/ictcs/SorbelliC0PP21
}}
==Cooperative Truck-Drone Scheduling Approach for Last-Mile Deliveries==
https://ceur-ws.org/Vol-3072/paper4.pdf
Cooperative Truck-Drone Scheduling Approach
for Last-Mile Deliveries
(Extended Abstract)
Francesco Betti Sorbelli1 , Federico Corò2 , Sajal K. Das2 , Lorenzo Palazzetti3,1 ,
and Cristina M. Pinotti1
1
University of Perugia, Perugia, Italy
{francesco.bettisorbelli,cristina.pinotti}@unipg.it
2
Missouri University of Science and Technology, Rolla, USA
{federico.coro,sdas}@mst.edu
3
University of Florence, Firenze, Italy
lorenzo.palazzetti@unifi.it
Abstract. 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 as-
sociated with a cost (drone’s energy), a profit (delivery’s priority), and
a time interval (launch and rendezvous times from and to the truck).
We aim to find an optimal scheduling for drones that maximizes the
overall profit 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 first devise an optimal
Integer Linear Programming (ILP) formulation. We then design an op-
timal 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 approx-
imation algorithm for the multiple drone case.
Keywords: drones · approximation algorithms · dynamic programming
1 Introduction
With the advent of drones, the research and industrial communities are cur-
rently 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 efficiently [19]. For instance, drones can fly over disastrous
areas hit by an earthquake or assist firefighters [6, 13], search for missing peo-
ple [5, 17], monitor fields [12, 16] or points of interest [11, 14], deliver packages to
customers [1, 2, 20], collect items for smart automated warehousing [4, 21], etc.
In this work, we study the cooperation between a truck and a fleet of drones in
the last-mile delivery scenario to improve its effectiveness and efficiency. Drones
Copyright© 2021 for this paper by its authors. Use permitted under Creative Com-
mons License Attribution 4.0 International (CC BY 4.0)
2 F. Betti Sorbelli et al.
can deliver small packages quickly as they can easily traverse difficult terrain,
often using shorter routes, which would otherwise be demanding for trucks or
robots [3]. However, significant challenges arise due to constraints such as drones’
limited energy and their current inability to serve more than one customer at a
time [8, 18]. Our scenario is as follows: a delivery company has to make several
deliveries to customers in a city by relying on a truck carrying a fleet of drones.
All the drones are identical having the same capabilities and can deliver a single
package at a time. The truck, which initially resides at the depot, traverses a
predetermined route: to serve a customer, a drone takes off from the truck with
a package, delivers it, and returns to the rendezvous point with the truck.
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 flying sub-routes to accelerate deliveries, considering not
only the energy used by the drone but also the generated profits. 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 sufficient to allow a round
trip to/from the truck. Furthermore, deliveries can have conflicts 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 profit which characterizes
its importance (e.g., higher profit means higher priority). So, given the truck’s
route, the goal is to plan an appropriate schedule for the drones to maximize
profits subject to the drone’s limited battery capacity and delivery conflicts.
2 System Model and Problem Formulation
We consider a 2-D delivery area A where m drones carried by a truck, perform a
set D = {δ1 , . . . , δn } ⊂ 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
fixed; it starts and finishes 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 off 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 . Specifically, when the truck
reaches the launching point δiL on the road, the drone detaches itself from the
truck and then flies 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 define the cost wi ∈ N≥0 in terms of drone’s energy
required (it considers the payload weight, distances δiL δi and δi δiR , external fac-
tors like wind [2, 15, 10]), and the profit pi ∈ N≥0 that characterizes its priority
(the higher is the priority, the larger is the profit). Moreover, let tL
i be the launch
time for the drone from point δiL , and let tR i be the rendezvous time at point
δiR . Since the truck travels along the predetermined road only once and in a
Title Suppressed Due to Excessive Length 3
specific direction, tL R
i < ti yields. We define the drone’s delivery interval time
L R
Ii = [ti , ti ] that determines its flying time-window. If two Ii and Ij intersect
they are said to be in conflict. It follows that I = {I1 , . . . , In } is the interval set
associated with the deliveries within the area A. A subset of deliveries whose
time interval times are conflict-free is said feasible.
P is to select a viable subset S ⊆ I of deliveries such
For a single drone, the goal
that its energy cost C(S) =P i∈S wi is no more than the drone’s battery B and
the overall profit P(S) = i∈S pi is maximized. Similarly, for multiple drones,
we aim to select a feasible subset S ∗ = {S1∗ , . . . , Sm
∗
} ⊆ I partitioned among
∗
m drones such that the overall profit P(S ) is maximized and each drone has
enough energy to accomplish its deliveries. Due to the fact that deliveries have
conflicts and drones have a limited battery capacity, it is not guaranteed that
all the deliveries will be performed. Let us now define the delivery scheduling
problem with drones.
Definition 1 (Delivery Scheduling Problem (DSP)). Let D be the set of n
deliveries, m the number of drones, and B the energy budget of each drone. The
DSP aims to find a family S ∗ = {S1∗ , . . . , Sm
∗
} ⊆ I of m feasible subsets
P with
Sp ∩ Sq = ∅, for 1 ≤ p 6= q ≤ m, such that the overall profit P(S ∗ ) = i∈S pi
∗ ∗
is maximized. Formally,
S∗ = arg max P(S) s.t. C(Si ) ≤ B ∀i = 1, . . . , m
S={S1 ,...,Sm }⊆I
As defined, DSP represents a generalization of the classic 0–1 Knapsack
Problem (KP). It follows that DSP is an NP -hard problem.
2.1 Optimal ILP Formulation
The DSP can be optimally solved using an Integer Linear Programming (ILP)
formulation. We enumerate the deliveries as N = {1, . . . , n}, and drones as
M = {1, . . . , m}. Let xij ∈ {0, 1} be a decision variable that is 1 if the delivery
j ∈ N is accomplished by the drone i ∈ M, 0 otherwise. Finally, the ILP
formulation is given by:
Pm Pn
max i=1 j=1 pj xij (1)
Pn
j=1 wj xij ≤ B, ∀i ∈ M (2)
Pm
i=1 xij ≤ 1, ∀j ∈ N (3)
xij + xik ≤ 1, ∀i ∈ M; ∀j, k ∈ N s.t. Ij ∩ Ik 6= ∅ (4)
xij ∈ {0, 1}, ∀i ∈ M, ∀j ∈ N (5)
The objective function (1) aims to maximize the overall profit 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.
4 F. Betti Sorbelli et al.
3 Proposed Solutions
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 Optimal Pseudo-polynomial Algorithm Opt-S
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 L
σ(i) < ti , and σ(i) = 0 if no interval j < i finishes before i starts. Then, for
each interval Ii , we can find the largest non-intersecting index σ(i) that precedes
i, that is, tR L
σ(i) < ti . Then, all the intervals between Iσ(i)+1 and Ii−1 intersect
with i. So, it follows that for each interval Ii , we can find the largest conflict-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 program-
ming. A table M of size n × B is created. The value M (i, b) is the maximum gain
achievable by considering the first i intervals and budget b and it is computed
as follow: M (i, b) = max{M (i − 1, b), pi + M (σ(i), b − wi )} if the budget b is
sufficient 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 profit
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 Approximation Algorithm Apx-S
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 first invoke an optimal polynomial-time graph-
coloring algorithm for chordal graphs to divide the set of intervals into several
subsets based on the minimum coloring of I [9]. Therefore, by definition of
vertex-coloring we have that all the intervals with the same color do not have any
conflict. Thus, after the coloring, for each subset Ci we find feasible solutions for
DSP by computing a subset Si ⊆ Ci with maximum profit such that C(Si ) ≤ B.
It is worth noting that finding optimal sets Si ⊆ Ci is equivalent to solving a
Knapsack Problem (KP) with budget B on elements Ci , which is a NP -hard
problem. However, it is also reasonable to rely on α-approximated solutions of
KP in polynomial-time for computing the sets Si , which also, in turn, will affect
the approximation ratio of Apx-S. To this end, a fast O(n log n) greedy strategy
for the fractional knapsack problem can be exploited which guarantees a lower
Title Suppressed Due to Excessive Length 5
bound α = 12 [7]. Finally, we return the solution with a maximum profit among
all the subsets Si .
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 Approximation Algorithm Apx-M
Apx-M solves DSP with multiple drones exploiting dynamic programming, re-
quiring 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
1
of m for multiple drones, where m denotes the number of drones.
4 Conclusion
We presented our ongoing work on the cooperation between a truck and a fleet 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.
References
1. Bartoli, L., Betti Sorbelli, F., Corò, F., Pinotti, C.M., Shende, A.: Exact and
approximate drone warehouse for a mixed landscape delivery system. In: IEEE In-
ternational Conference on Smart Computing (SMARTCOMP). pp. 266–273 (2019)
2. Betti Sorbelli, F., Corò, F., Das, S.K., Pinotti, C.M.: Energy-constrained delivery of
goods with drones under varying wind conditions. IEEE Transactions on Intelligent
Transportation Systems pp. 1–13 (2020)
3. Betti Sorbelli, F., Carpin, S., Corò, F., Navarra, A., Pinotti, C.M.: Optimal rout-
ing schedules for robots operating in aisle-structures. In: 2020 IEEE International
Conference on Robotics and Automation (ICRA). pp. 4927–4933. IEEE (2020)
4. Betti Sorbelli, F., Corò, F., Pinotti, C.M., Shende, A.: Automated picking system
employing a drone. In: 2019 15th International Conference on Distributed Com-
puting in Sensor Systems (DCOSS). pp. 633–640. IEEE (2019)
6 F. Betti Sorbelli et al.
5. Betti Sorbelli, F., Pinotti, C.M., Silvestri, S., Das, S.K.: Measurement errors in
range-based localization algorithms for uavs: Analysis and experimentation. IEEE
Transactions on Mobile Computing (TMC) (2020)
6. Calamoneri, T., Corò, F.: A realistic model for rescue operations after an earth-
quake. In: Q2SWinet ’20: Proceedings of the 16th ACM Symposium on QoS and
Security for Wireless and Mobile Networks. pp. 123–126. ACM (2020)
7. Caprara, A., Kellerer, H., Pferschy, U., Pisinger, D.: Approximation algorithms for
knapsack problems with cardinality constraints. European Journal of Operational
Research 123(2), 333–345 (2000)
8. Dayarian, I., Savelsbergh, M., Clarke, J.P.: Same-day delivery with drone resupply.
Transportation Science 54(1), 229–249 (2020)
9. Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering
by cliques, and maximum independent set of a chordal graph. SIAM Journal on
Computing 1(2), 180–187 (1972)
10. Khanda, A., Corò, F., Betti Sorbelli, F., Pinotti, C.M., Das, S.K.: Efficient route
selection for drone-based delivery under time-varying dynamics. In: 18th Interna-
tional Conference on Mobile Ad-Hoc and Smart Systems (MASS). IEEE (2021)
11. Khochare, A., Simmhan, Y., Betti Sorbelli, F., Das, S.K.: Heuristic algorithms
for co-scheduling of edge analytics and routes for uav fleet missions. In: IEEE
International Conference on Computer Communications (INFOCOM) (2021)
12. Lottes, P., Khanna, R., Pfeifer, J., Siegwart, R., Stachniss, C.: Uav-based crop
and weed classification for smart farming. In: IEEE International Conference on
Robotics and Automation, ICRA. pp. 3024–3031 (2017)
13. Mishra, B., Garg, D., Narang, P., Mishra, V.: Drone-surveillance for search and
rescue in natural disaster. Computer Communications 156, 1–10 (2020)
14. Nguyen, V.T., Jung, K., Dang, T.: Dronevr: a web virtual reality simulator for
drone operator. In: 2019 IEEE International Conference on Artificial Intelligence
and Virtual Reality (AIVR). pp. 257–2575. IEEE (2019)
15. Palazzetti, L., Pinotti, C.M., Rigoni, G.: A run in the wind: favorable winds make
the difference in drone delivery. In: 2021 17th International Conference on Dis-
tributed Computing in Sensor Systems (DCOSS). IEEE (2021)
16. Rabello, A., Brito, R.C., Favarim, F., Weitzenfeld, A., Todt, E.: Mobile system for
optimized planning to drone flight applied to the precision agriculture. In: 3rd Intl.
Conference on Information and Computer Technologies (ICICT). pp. 12–16 (2020)
17. Riehl, J.R., Collins, G.E., Hespanha, J.P.: Cooperative search by uav teams: A
model predictive approach using dynamic graphs. IEEE Transactions on Aerospace
and Electronic Systems 47(4), 2637–2656 (2011)
18. Sawadsitang, S., Niyato, D., Tan, P.S., Wang, P., Nutanong, S.: Multi-objective op-
timization for drone delivery. In: 2019 IEEE 90th Vehicular Technology Conference
(VTC2019-Fall). pp. 1–5. IEEE (2019)
19. Shi, W., Zhou, H., Li, J.e.a.: Drone assisted vehicular networks: Architecture, chal-
lenges and opportunities. IEEE Network 32(3), 130–137 (2018)
20. Torabbeigi, M., Lim, G.J., Kim, S.J.: Drone delivery scheduling optimization
considering payload-induced battery consumption rates. Journal of Intelligent &
Robotic Systems 97(3), 471–487 (2020)
21. Wawrla, L., Maghazei, O., Netland, T.: Applications of drones in warehouse oper-
ations. Whitepaper. ETH Zurich, D-MTEC (2019)