A efficient heuristic for multi-drop Truck-Drone routing problems

Pedro Luis González-R, David Canca, José Luis Andrade-Pineda, Marcos Calle y José Miguel León

The practical application and use of UAVs presents a number of problems that are of a different nature to the specific technology of the components involved. Among them, the most relevant problem deriving from the use of UAVs in logistics distribution tasks is the so-called “last mile” delivery. In the present work, we focus on the resolution of the truck-drone team logistics problem. The problems of tandem routing have a complex structure and have only been partially addressed in the scientific literature. The use of UAVs raises a series of restrictions and considerations that did not appear previously in routing problems; most notably, aspects such as the limited power-life of the batteries used by the UAVs and the definition of replacement or charging points. These difficulties have until now limited the mathematical formulation of truck-drone routing problems and their resolution to mainly small- size cases.

We present a novel truck-drone team logistic (TDTL) mathematical formulation, allowing multi-drop routes for the drone. Under the assumption
of infinite travel autonomy for the truck and a limited battery life for the
drone, we plan the synchronization events –namely, the sites wherein the
drone will gain a fully-charged new battery- with the objective of minimizing the makespan. We assume that the truck-drone team starts from an
origin (depot) to serve a set of locations (customers), each one reachable
by one of both vehicles, the truck or drone and, without pre-established
routes (open) neither for the truck nor for drone. We propose an iterated greedy heuristic based on the iterative process of destruction and reconstruction of solutions. This process is orchestrated by a global optimization scheme using a simulated annealing (SA) algorithm.

We test our approach in a large set of instances of different sizes taken from literature. The developed heuristic allows its transfer to real-life cases, since it is able to obtain solutions of relatively good quality for large-size problems
in short computation time.