Exact models for the flying sidekick traveling salesman problem

Mauro Dell'Amico, Roberto Montemanni, Stefano Novellani

Research output: Contribution to journalArticlepeer-review

35 Scopus citations

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.

Original languageEnglish
Pages (from-to)1360-1393
Number of pages34
JournalInternational Transactions in Operational Research
Volume29
Issue number3
DOIs
StatePublished - May 2022
Externally publishedYes

Keywords

  • aerial drones
  • branch and cut
  • mixed integer linear programming (formulations)
  • parcel deliveries
  • routing

Fingerprint

Dive into the research topics of 'Exact models for the flying sidekick traveling salesman problem'. Together they form a unique fingerprint.

Cite this