Exact and heuristic approaches for the Truck–Drone Team Logistics Problem

Truck-and-drone routing problems are a topic of increasing interest due to advancements in drone technology. Initially, drones were thought to serve only one customer per flight; however, recent improvements in drone technology have led to the definition of multi-visit truck-and-drone routing problems, where a drone can serve multiple customers in each flight. These routing problems, which require a careful synchronization between the truck and the drone, are challenging to solve, even with a small number of customers. In this work, we address a multi-visit, single-truck, single-drone routing problem also known in the literature as the Truck–Drone Team Logistics Problem ( TDTLP ). In particular, we study two versions of the TDTLP arising from the possibility for the drone to land or hover at the recollection points. Our study proposes a novel mixed-integer linear programming formulation for the TDTLP , solved by a Branch-and-Cut ( B&C ) algorithm. Then, we introduce a matheuristic approach that incorporates our B&C algorithm to solve medium- and large-size instances. Computational results on benchmark instances demonstrate the robustness and efficacy of the proposed methods. • We study the Truck–Drone Team Logistics Problem (TDTLP). • The impact of the drone hovering on the TDTLP solution is evaluated. • A new MILP formulation for the TDTLP is proposed. • Exact and matheuristic approaches have been developed to tackle the TDTLP. • Computational results demonstrate the effectiveness of our approaches.