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.

Exact models for the flying sidekick traveling salesman problem / Dell'Amico, M.; Montemanni, R.; Novellani, S.. - In: INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH. - ISSN 0969-6016. - 29:3(2022), pp. 1360-1393. [10.1111/itor.13030]

Exact models for the flying sidekick traveling salesman problem

Dell'Amico M.;Montemanni R.;Novellani S.
2022

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.
2022
29
3
1360
1393
Exact models for the flying sidekick traveling salesman problem / Dell'Amico, M.; Montemanni, R.; Novellani, S.. - In: INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH. - ISSN 0969-6016. - 29:3(2022), pp. 1360-1393. [10.1111/itor.13030]
Dell'Amico, M.; Montemanni, R.; Novellani, S.
File in questo prodotto:
File Dimensione Formato  
Int Trans Operational Res - 2021 - Dell Amico - Exact models for the flying sidekick traveling salesman problem.pdf

Open access

Tipologia: Versione pubblicata dall'editore
Dimensione 375.67 kB
Formato Adobe PDF
375.67 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1249874
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 25
  • ???jsp.display-item.citation.isi??? 26
social impact