Exact models for the flying sidekick traveling salesman problem. (6th July 2021)

• Record Type: Journal Article
• Authors: Dell'Amico, Mauro; Montemanni, Roberto; Novellani, Stefano
• Is Part Of: International transactions in operational research. Volume 29:Number 3(2022)
• Page Start: 1360
• Page End: 1393
• Publication Date: 2021-07-06
• Subjects: aerial drones -- routing -- parcel deliveries -- mixed integer linear programming (formulations) -- branch and cut; Operations research -- Periodicals; 003
• DOI: 10.1111/itor.13030
• Languages: English
• ISSNs: 0969-6016

Abstract

Abstract: This paper presents three enhanced formulations for the flying sidekick traveling salesman problem, where a truck and a drone cooperate to deliver parcels to customers minimizing the completion time. The drone can leave and must return to the truck after visiting one customer, performing flights not exceeding its battery endurance while the truck can serve other customers. The new formulations allow to decrease the number of "big‐M" constraints with respect to literature models and improve previous results by solving to optimality several benchmark instances for which an optimal solution was previously unknown. This paper also shows how to modify the new models to include several variants of the problem from the literature.