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

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.