With e-commerce expanding rapidly, last-mile delivery challenges have been exacerbated, necessitating innovative logistics to reduce operational costs and improve delivery speed.
This paper investigates a traveling salesman problem with drone stations, where a truck collaborates with multiple drones docked at candidate drone stations to serve customers. In contrast to existing studies that typically assume fixed drone speeds, this work treats drone speeds as decision variables and introduces a comprehensive energy consumption model that accounts for all phases of drone flight. The objective is to jointly optimize truck routing, station selection, drone–customer assignment, and drone speed to minimize the total delivery cost. Through a speed-discretion method, we formulate the problem as a mixed-integer linear programming model and develop a tailored adaptive large neighborhood search (ALNS) algorithm. Computational experiments indicate that for large-sized instances with 80–100 customers and 16–20 candidate stations, ALNS produces solutions within 50 seconds, with average optimality gaps below 1.8% compared to Gurobi’s solutions obtained under a 5000-second time limit. The results also show that the speed optimization strategy consistently outperforms fixed-speed approaches across multiple performance metrics, including total cost, service completion time, energy consumption, and service coverage.