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

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.
2021
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 38
  • ???jsp.display-item.citation.isi??? 33
social impact