Exact models for the flying sidekick traveling salesman problem

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.

Automated summary

This paper introduces three enhanced formulations for the flying sidekick traveling salesman problem, which significantly reduce the number of constraints and improve solution efficiency compared to traditional models, as well as demonstrating how to modify the models for various problem variants.