EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A New Formulation for the Traveling Salesman Problem With Drone and Lockers

Danilo Amitrano, Maurizio Boccia, Adriano Masone, Claudio Sterle

Networks · 2025-09 · 86 (2) · 112-143

DOI: 10.1002/net.22280 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Networks, online erschienen am 26.04.2025. Verfasst von Danilo Amitrano und 3 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 27 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Nowadays, driven by factors such as the rapid growth of online sales, different delivery methods are being explored to improve last‐mile logistics processes. Among these, the combined use of trucks and drones and the option of utilizing parcel lockers as an alternative to home delivery have led to the definition of new optimization problems. In this work, we study the Traveling Salesman Problem with Drone and Lockers ( TSP‐DL ), the first optimization problem to integrate both of these innovative delivery methods. The goal is to determine the optimal route for a tandem consisting of a truck and a drone to serve a set of customers. Each customer can either be served at home or retrieve their package from a parcel locker where the tandem has delivered it. The objective is to minimize total delivery costs, which depend on the total delivery time and compensation provided by the delivery company to customers served via parcel lockers. We propose a new formulation for the TSP‐DL, strengthened by additional valid inequalities and solved using a Branch‐and‐Cut algorithm. Unlike other formulations in the literature, our approach does not use time variables. Computational experiments on benchmark instances demonstrate that the proposed approach outperforms the current state of the art for the TSP‐DL , providing either optimal solutions or improved bounds for several previously unsolved instances. Additionally, we introduce a new set of benchmark instances to evaluate the scalability of the proposed approach. Finally, we provide managerial insights derived from an analysis of different coordination policies between the truck and the drone.

Zitieren

APA

Amitrano, D., Boccia, M., Masone, A., & Sterle, C. (2025). A New Formulation for the Traveling Salesman Problem With Drone and Lockers. Networks, 86(2), 112-143. https://doi.org/10.1002/net.22280

Vancouver

Amitrano D, Boccia M, Masone A, Sterle C. A New Formulation for the Traveling Salesman Problem With Drone and Lockers. Networks. 2025;86(2):112-143. doi:10.1002/net.22280

BibTeX
@article{Amitrano2025,
  author = {Amitrano, Danilo and Boccia, Maurizio and Masone, Adriano and Sterle, Claudio},
  title = {A New Formulation for the Traveling Salesman Problem With Drone and Lockers},
  journal = {Networks},
  year = {2025},
  volume = {86},
  number = {2},
  pages = {112--143},
  doi = {10.1002/net.22280}
}
Kostenlos starten →