Truck-Drone Collaborative Delivery with a Mobile Drone Station Trailer
提出一种带移动无人机站拖车的卡车-无人机协同配送模型，用混合整数线性规划和自适应大邻域搜索算法最小化总配送时间，实验表明算法优于商业求解器。
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.