Exact methods for the traveling salesman problem with multiple drones

Sara Cavani, Manuel Iori, Roberto Roberti*

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

Drone delivery is drawing increasing attention in last-mile delivery. Effective solution methods to solve decision-making problems arising in drone delivery allow to run and assess drone delivery systems. In this paper, we focus on delivery systems with a single traditional vehicle and multiple drones working in tandem to fulfill customer requests. We address the Traveling Salesman Problem with Multiple Drones (TSP-MD) and investigate the modeling challenges posed by the presence of multiple drones, which have proven to be hard to handle in the literature. We propose a compact Mixed-Integer Linear Programming (MILP) model to formulate the TSP-MD and several families of valid inequalities. Moreover, we illustrate an exact decomposition approach based on the compact MILP and a branch-and-cut algorithm. We show that this exact approach can solve instances with up to 24 customers to proven optimality, improving upon existing exact methods that can solve similar problems with up to ten customers only.

Original languageEnglish
Article number103280
Pages (from-to)1-26
Number of pages26
JournalTransportation Research Part C: Emerging Technologies
Volume130
Early online date10 Jul 2021
DOIs
Publication statusPublished - Sept 2021

Bibliographical note

Funding Information:
The authors are grateful to the anonymous Associate Editor and the two Referees for their valuable comments.

Publisher Copyright:
© 2021 The Authors

Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.

Keywords

  • Branch-and-cut
  • Drone
  • Exact method
  • Mixed integer linear programming
  • Traveling salesman

Fingerprint

Dive into the research topics of 'Exact methods for the traveling salesman problem with multiple drones'. Together they form a unique fingerprint.

Cite this