Algorithms based on branch and bound for the flying sidekick traveling salesman problem. (October 2021)

• Record Type: Journal Article
• Authors: Dell'Amico, Mauro; Montemanni, Roberto; Novellani, Stefano
• Is Part Of: Omega. Volume 104(2021)
• Publication Date: 2021-10
• Subjects: Traveling salesman problem -- Drone-assisted deliveries -- Branch and bound -- Heuristic algorithms; Management -- Periodicals; 658.4005
• DOI: 10.1016/j.omega.2021.102493
• Languages: English
• ISSNs: 0305-0483

Abstract

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.