Exact solution approaches for the traveling salesman problem with a drone station

Zhiyuan Shi, Shaozhi Hong, Zeling Wang and Ang Li

European Journal of Operational Research, 2026, vol. 328, issue 3, 845-861

Abstract: The rapid growth of e-commerce has posed significant challenges for urban last-mile delivery. In this paper, we study a truck–drone collaborative delivery problem, referred to as the traveling salesman problem with a drone station (TSP-DS), which is well-suited for densely populated urban environments. The TSP-DS extends the well-known parallel drone scheduling traveling salesman problem (PDSTSP). The truck starts from the depot and can deliver packages to the drone station for drone delivery. To minimize the delivery makespan, we propose two improved formulations for the TSP-DS using mixed-integer linear programming (MILP). We then develop an exact algorithm based on the logic-based Benders decomposition approach. To evaluate the effectiveness of these approaches, we conduct extensive computational experiments using test instances generated from existing benchmarks. The numerical results confirm the improvements offered by our formulations compared to the TSP-DS formulation in the existing literature. Our Benders approach also outperforms the state-of-the-art commercial solver Gurobi, solving all instances with no more than 152 customers to the global optimum within 3600 s. We also obtain an optimal solution for an instance with 264 customers. Additionally, we perform sensitivity analyses to investigate the impact of critical model parameters, including the number, speed, and flight range of drones, as well as the location of the drone station, on the performance of the delivery system. The results offer valuable management insights from both the system planning and operational perspectives.

Keywords: Logistics; Traveling salesman problem; Drone parallel scheduling; Mixed-integer linear programming; Logic-based benders decomposition (search for similar items in EconPapers)
Date: 2026
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725005521
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:328:y:2026:i:3:p:845-861

DOI: 10.1016/j.ejor.2025.07.027

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().