EUVIMEDScopri EUVIMED
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 ↗

At a glance

Journal article in Networks, published online on 2025-04-26. Written by Danilo Amitrano and 3 co-authors. Cited 7 times so far (Crossref); 27 references. The full text is freely available (open access, CC BY 4.0).

AbstractDati bibliograficiCiteRelated studies

Abstract (original language)

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.

Cite

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}
}
Start for free →