Algorithms based on branch and bound for the flying sidekick traveling salesman problem. (October 2021) - Dell'Amico, Mauro; Montemanni, Roberto; Novellani, Stefano
Highlights: Fast LP-free exact method for small instances. Effective LP-free heuristic method for medium/large instances. New benchmark instances. Abstract: The use of drones in urban logistics is gaining more and more interest. In this paper we consider the flying sidekick traveling salesman problem, where some customers require a delivery and they can be served either by a truck or by a drone. The aim is minimizing the total time required to service all the customers. We present a branch and bound algorithm especially designed to efficiently target small instances up to 15 customers and a heuristic algorithm, using the branch and bound as a subroutine, to attack larger instances. Extensive experimental results suggest the effectiveness of the exact solver for small instances and shows that the heuristic is able to provide state-of-the-art results for medium/large instances.