Exact methods for the traveling salesman problem with multiple drones
| Autor: | Roberto Roberti, Sara Cavani, Manuel Iori |
|---|---|
| Přispěvatelé: | Amsterdam Business Research Institute |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Mathematical optimization
SDG 16 - Peace Linear programming Exact method Computer science SDG 16 - Peace Justice and Strong Institutions Transportation Travelling salesman problem Drone Justice and Strong Institutions Computer Science Applications Effective solution Traveling salesman Branch-and-cut Mixed integer linear programming Automotive Engineering Decomposition (computer science) Focus (optics) Branch and cut Civil and Structural Engineering |
| Zdroj: | Transportation Research Part C: Emerging Technologies, 130:103280, 1-26. Elsevier Limited Cavani, S, Iori, M & Roberti, R 2021, ' Exact methods for the traveling salesman problem with multiple drones ', Transportation Research Part C: Emerging Technologies, vol. 130, 103280, pp. 1-26 . https://doi.org/10.1016/j.trc.2021.103280 |
| ISSN: | 0968-090X |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect