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)