Algorithms based on branch and bound for the flying sidekick traveling salesman problem

Mauro Dell'Amico, Roberto Montemanni, Stefano Novellani

Research output: Contribution to journalArticlepeer-review

48 Scopus citations

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.

Original languageEnglish
Article number102493
JournalOmega (United Kingdom)
Volume104
DOIs
StatePublished - Oct 2021
Externally publishedYes

Keywords

  • Branch and bound
  • Drone-assisted deliveries
  • Heuristic algorithms
  • Traveling salesman problem

Fingerprint

Dive into the research topics of 'Algorithms based on branch and bound for the flying sidekick traveling salesman problem'. Together they form a unique fingerprint.

Cite this