In this paper we consider a problem related to deliveries assisted by an unmanned aerial vehicle, so-called drone. In particular we consider the Flying Sidekick Traveling Salesman Problem, in which a truck and a drone cooperate to deliver parcels to customers minimizing the completion time. In the following we improve the formulation found in the related literature. We propose three-indexed and two-indexed formulations and a set of inequalities that can be implemented in a branch-and-cut fashion. The methods that we propose are able to find the optimal solution for most of the literature instances. Moreover, we consider two versions of the problem: one in which the drone is allowed to wait at the customers, as in the literature, and one in which waiting is allowed only in flying mode. The solving methodologies are adapted to both versions and a comparison between the two is provided.

Drone-assisted deliveries: new formulations for the flying sidekick traveling salesman problem / Dell'Amico, M.; Montemanni, R.; Novellani, S.. - In: OPTIMIZATION LETTERS. - ISSN 1862-4472. - 15:5(2021), pp. 1617-1648. [10.1007/s11590-019-01492-z]

Drone-assisted deliveries: new formulations for the flying sidekick traveling salesman problem

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

Abstract

In this paper we consider a problem related to deliveries assisted by an unmanned aerial vehicle, so-called drone. In particular we consider the Flying Sidekick Traveling Salesman Problem, in which a truck and a drone cooperate to deliver parcels to customers minimizing the completion time. In the following we improve the formulation found in the related literature. We propose three-indexed and two-indexed formulations and a set of inequalities that can be implemented in a branch-and-cut fashion. The methods that we propose are able to find the optimal solution for most of the literature instances. Moreover, we consider two versions of the problem: one in which the drone is allowed to wait at the customers, as in the literature, and one in which waiting is allowed only in flying mode. The solving methodologies are adapted to both versions and a comparison between the two is provided.
2021
15
5
1617
1648
Drone-assisted deliveries: new formulations for the flying sidekick traveling salesman problem / Dell'Amico, M.; Montemanni, R.; Novellani, S.. - In: OPTIMIZATION LETTERS. - ISSN 1862-4472. - 15:5(2021), pp. 1617-1648. [10.1007/s11590-019-01492-z]
Dell'Amico, M.; Montemanni, R.; Novellani, S.
File in questo prodotto:
File Dimensione Formato  
s11590-019-01492-z.pdf

Accesso riservato

Tipologia: Versione pubblicata dall'editore
Dimensione 538.72 kB
Formato Adobe PDF
538.72 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
1905.13463.pdf

Open access

Tipologia: Versione originale dell'autore proposta per la pubblicazione
Dimensione 474.63 kB
Formato Adobe PDF
474.63 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/1222575
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 48
  • ???jsp.display-item.citation.isi??? 59
social impact