Zhiyuan Shi, Shaozhi Hong, Ang Li
Truck–drone collaborative delivery systems have garnered significant interest in recent years. This paper introduces a novel model, called the Parallel Drone Scheduling Traveling Salesman Problem with a Mobile Drone Station Trailer (PDSTSP-MDST). The model integrates a truck and multiple drones that collaborate through a Mobile Drone Station Trailer (MDST). The proposed MDST is a trailer transported by a truck and deployed at designated sites to serve as a temporary drone station. Once deployed, the site is activated, and drones can pick up packages from the MDST to serve customers. While drones are in service, the truck may either remain on-site or continue independently to serve other customers. We formulate the PDSTSP-MDST as a mixed-integer linear programming (MILP) model to minimize the total delivery makespan. To enhance computational efficiency, especially for large-scale cases, we design a customized metaheuristic algorithm based on the Adaptive Large Neighborhood Search (ALNS) framework. We introduce a problem-specific destroy operator with a perturbation mechanism in the repair phase, which enables the ALNS to explore neighborhoods under different activated sites. Numerical experiments validate the effectiveness of both the MILP formulation and the proposed ALNS algorithm. These tests show that our ALNS consistently outperforms the state-of-the-art commercial solver, Gurobi, in both solution quality and runtime. The algorithm also remains robust for large-scale instances where exact approaches struggle. Comparative analyses against benchmark models highlight the operational advantages of this novel truck-drone collaborative delivery approach, while sensitivity analyses yield managerial insights for practical implementation.