Algorithm for Solving Vehicle Routing Problems with Drones

As drone technology advance with the integration of Artificial Intelligence and deep learning, drones and UAV’s are becoming more and common as a topic of research in academia and industrial sector. With a number of simulations, concept designs, mechanical designs and prototypes of both UAV’s and Unmanned Aerial Systems (UAS), drones have also made their way into the logistics department where navigation through a street, a sector, a neighborhood, a town or an entire city becomes extremely important.

A technical report titled A Variable Neighborhood Search Algorithm for Solving the Vehicle Routing Problem with Drones published in Technische University by Daniel Schermer, Mahdi Moeini and Oliver Wendt explores the Vehicle Routing Problems with Drones (VRPD). The objective of the study consists of designing feasible routes with minimal mission time. The drones were to be launched from and retrieved by the vehicles and move at a velocity that might differ from the vehicle’s speed.

Due to limited performance of the solvers in addressing large-scale instances, researches addressed proposed an algorithm based on the well-known Variable Neighborhood Search (VNS) approach. In order to evaluate the performance of the introduced algorithm as well as the solver in solving the VRPD instances, they carried out extensive computational experiments through the course of their study.

In the said study, the researchers did not just apply a new algorithm with a new approach; they systematically developed an algorithm. Developing its mathematical model and iterating variable values in the model to come up with the optimum solution or a set of variables that perfectly balances efficiency, accuracy, speed etc. Design optimization with an algorithm is pretty much like distributing grocery items over a tight budget.

The researchers provided an extensive computational study that considers the impact on the objective value in a given problem instance by using multiple vehicles, multiple drones, and several different relevant factors and drone parameters such as their relative velocity and flight endurance.

Overall, through their computational study, they were able to show that significant savings in terms of mission time are possible through the combination of trucks and drones in last-mile delivery.

Future prospects

While autonomous navigation is a crucial topic of research in logistics, paramedics, traffic control and crime control; this study in itself has an immense potential for expansion. The study provides a rich research prospect for the future. As a natural extension, methods can be studied to allow drones to be retrieved and/or launched on arcs. Another extension might consider a time-dependent recharge model. On the one hand, it might be of interest to optimize cost per mile or per delivery for more feasible systems and networks. On the other hand, in the context of green VRPs or environment friendly solutions, it might also be of interest to consider reduced emissions.

Reference: Schermer, Daniel & Moeini, Mahdi & Wendt, Oliver. (2018). A Variable Neighborhood Search Algorithm for Solving the Vehicle Routing Problem with Drones. https://bisor.wiwi.uni-kl.de/fileadmin/bisor.wiwi.uni-kl.de/papers/unprotected/Technical_Report_VNS_for_VRPD_BISOR.pdf