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

Mauro Dell’Amico, Roberto Montemanni, Stefano Novellani

Research output: Contribution to journalArticlepeer-review

44 Scopus citations

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.

Original languageEnglish
Pages (from-to)1617-1648
Number of pages32
JournalOptimization Letters
Volume15
Issue number5
DOIs
StatePublished - Jul 2021
Externally publishedYes

Keywords

  • Aerial drones
  • Branch-and-cut
  • Formulations
  • Parcel deliveries
  • Routing

Fingerprint

Dive into the research topics of 'Drone-assisted deliveries: new formulations for the flying sidekick traveling salesman problem'. Together they form a unique fingerprint.

Cite this