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 language | English |
---|---|
Article number | 103280 |
Pages (from-to) | 1-26 |
Number of pages | 26 |
Journal | Transportation Research Part C: Emerging Technologies |
Volume | 130 |
Early online date | 10 Jul 2021 |
DOIs | |
Publication status | Published - 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