Truck-drone team logistics: A heuristic approach to multi-drop route planning

• Published in: Transportation research. Part C, Emerging technologies Emerging technologies, 2020-05, Vol.114, p.657-680
• Main Authors: Gonzalez-R, Pedro L., Canca, David, Andrade-Pineda, Jose L., Calle, Marcos, Leon-Blanco, Jose M.
• Format: Article
• Language: English
• Subjects: Delivery; Drones; Heuristic; Optimization; Tandem truck-drone
• ISSN: 0968-090X; 1879-2359
• DOI: 10.1016/j.trc.2020.02.030

•Truck-drone delivery problem coded as a sequence.•Mathematical modelling of a tandem formed by one truck and one drone.•Battery capacity constraints and multiple customers’ visits per flight allowed.•Design of a heuristic approach to solve the problem.•Performance of the heuristic approach outperforms the exact resolution. Recently there have been significant developments and applications in the field of unmanned aerial vehicles (UAVs). In a few years, these applications will be fully integrated into our lives. The practical application and use of UAVs presents several 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 batteries used by the UAVs and the determination of rendezvous points where they are replaced by fully-charged new batteries. These difficulties have until now limited the mathematical formulation of truck-drone routing problems and their resolution to mainly small-size cases. To overcome these limitations 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 obtained results are quite promising, even for large-size scenarios.