A Route Planning Strategy
for Commercial Deliveries Using Drones
Soumen Manna and Anand Narasimhamurthy
Abstract In this work, we address the problem of route planning in the scenario of
using drones for commercial deliveries. One main difference in such a scenario as
compared to traditional truck-based deliveries is due to the limited weight capacity
of the delivery vehicles, i.e. the drones. This necessitates solving the routing and
scheduling together unlike many vehicle routing problems studied in the literature. Also, a practical solution must be scalable and must take into account the
complexities of the real-world scenario (e.g. orders get updated dynamically and
frequently). Accordingly, we propose a heuristics-based greedy approach which
entails low computation overhead and is easily scalable. We show simulation results
demonstrating the efficacy of the approach.
Keywords Drone scheduling · Vehicle routing problems · Greedy approach ·
Heuristic algorithm · Route planning
1 Introduction
Vehicle Routing Problems (VRPs) have a long history dating back to at least Dantzig
et al. [1], several variants have been studied in the literature (e.g. [2, 8]). With the
advancement of online shopping, we can anticipate significant usage of drones for
commercial deliveries, once regulatory challenges are overcome. According to an
ARK Investment report [10] the cost to deliver a package within 30 min using Amazon
PrimeAir (a service proposed by Amazon in 2014, with the intended aim of delivering
packages up to five pounds in 30 min or less using small drones) would work out
S. Manna · A. Narasimhamurthy (B)
International School of Engineering, Bengaluru, India
e-mail: anand.narasimhamurthy@insofe.edu.in
S. Manna
e-mail: manna.soumen@gmail.com
© The Editor(s) (if applicable) and The Author(s), under exclusive license
to Springer Nature Singapore Pte Ltd. 2021
N. Gascoin and E. Balasubramanian (eds.), Innovative Design, Analysis
and Development Practices in Aerospace and Automotive Engineering, Lecture Notes
in Mechanical Engineering, https://doi.org/10.1007/978-981-15-6619-6_34
317
for Commercial Deliveries Using Drones
Soumen Manna and Anand Narasimhamurthy
Abstract In this work, we address the problem of route planning in the scenario of
using drones for commercial deliveries. One main difference in such a scenario as
compared to traditional truck-based deliveries is due to the limited weight capacity
of the delivery vehicles, i.e. the drones. This necessitates solving the routing and
scheduling together unlike many vehicle routing problems studied in the literature. Also, a practical solution must be scalable and must take into account the
complexities of the real-world scenario (e.g. orders get updated dynamically and
frequently). Accordingly, we propose a heuristics-based greedy approach which
entails low computation overhead and is easily scalable. We show simulation results
demonstrating the efficacy of the approach.
Keywords Drone scheduling · Vehicle routing problems · Greedy approach ·
Heuristic algorithm · Route planning
1 Introduction
Vehicle Routing Problems (VRPs) have a long history dating back to at least Dantzig
et al. [1], several variants have been studied in the literature (e.g. [2, 8]). With the
advancement of online shopping, we can anticipate significant usage of drones for
commercial deliveries, once regulatory challenges are overcome. According to an
ARK Investment report [10] the cost to deliver a package within 30 min using Amazon
PrimeAir (a service proposed by Amazon in 2014, with the intended aim of delivering
packages up to five pounds in 30 min or less using small drones) would work out
S. Manna · A. Narasimhamurthy (B)
International School of Engineering, Bengaluru, India
e-mail: anand.narasimhamurthy@insofe.edu.in
S. Manna
e-mail: manna.soumen@gmail.com
© The Editor(s) (if applicable) and The Author(s), under exclusive license
to Springer Nature Singapore Pte Ltd. 2021
N. Gascoin and E. Balasubramanian (eds.), Innovative Design, Analysis
and Development Practices in Aerospace and Automotive Engineering, Lecture Notes
in Mechanical Engineering, https://doi.org/10.1007/978-981-15-6619-6_34
317