The use of drones in urban logistics is gaining more and more interest. In this paper we consider the flying sidekick traveling salesman problem, where some customers require a delivery and they can be served either by a truck or by a drone. The aim is minimizing the total time required to service all the customers. We present a branch and bound algorithm especially designed to efficiently target small instances up to 15 customers and a heuristic algorithm, using the branch and bound as a subroutine, to attack larger instances. Extensive experimental results suggest the effectiveness of the exact solver for small instances and shows that the heuristic is able to provide state-of-the-art results for medium/large instances.

Algorithms based on Branch and Bound for the Flying Sidekick Traveling Salesman Problem / Dell'Amico, Mauro; Montemanni, Roberto; Novellani, Stefano. - In: OMEGA. - ISSN 0305-0483. - 104:(2021), pp. 1-11. [10.1016/j.omega.2021.102493]

Algorithms based on Branch and Bound for the Flying Sidekick Traveling Salesman Problem

Mauro Dell'Amico;Roberto Montemanni;Stefano Novellani
2021-01-01

Abstract

The use of drones in urban logistics is gaining more and more interest. In this paper we consider the flying sidekick traveling salesman problem, where some customers require a delivery and they can be served either by a truck or by a drone. The aim is minimizing the total time required to service all the customers. We present a branch and bound algorithm especially designed to efficiently target small instances up to 15 customers and a heuristic algorithm, using the branch and bound as a subroutine, to attack larger instances. Extensive experimental results suggest the effectiveness of the exact solver for small instances and shows that the heuristic is able to provide state-of-the-art results for medium/large instances.
104
1
11
Algorithms based on Branch and Bound for the Flying Sidekick Traveling Salesman Problem / Dell'Amico, Mauro; Montemanni, Roberto; Novellani, Stefano. - In: OMEGA. - ISSN 0305-0483. - 104:(2021), pp. 1-11. [10.1016/j.omega.2021.102493]
Dell'Amico, Mauro; Montemanni, Roberto; Novellani, Stefano
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S030504832100102X-main.pdf

Accesso riservato

Tipologia: Versione pubblicata dall'editore
Dimensione 1.07 MB
Formato Adobe PDF
1.07 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
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/1245337
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 8
social impact