Abstract: The collaborative delivery problem involving multiple vehicles and multiple drones, which is closely aligned with real-world scenarios, has become a key challenge in path optimization due to its complexity. This paper proposes a collaborative delivery problem that considers multiple drones carried by each truck, the possibility of multiple deliveries within a single flight range of drones, and customer time window constraints. A mixed-integer programming model is established with the objective of minimizing total delivery cost. To solve this problem, a hybrid heuristic algorithm combining Adaptive Large Neighborhood Search (ALNS) and Simulated Annealing (SA) is designed. The double-chain encoding structure is proposed to separate the delivery sequence of customers and delivery tools, which not only visually displays the collaborative delivery paths of trucks and drones but also facilitates the quick generation of new solutions through destruction and repair operators. Numerical analysis validates the effectiveness of the algorithm and the adaptability of the double-chain encoding structure to this complex scenario. The results show that the algorithm generates high-quality solutions quickly for small, medium, and large-scale instances. Specifically, the computational time for small-scale instances is reduced by an average of 94.34% compared to the Gurobi solver, and the total cost for large-scale instances is reduced by an average of 9.11% compared to the Variable Neighborhood Search (VNS) algorithm. Furthermore, sensitivity analysis indicates that the number of drones carried by trucks and the cost of drones are key factors affecting both total delivery costs and the formulation of path plans, providing a theoretical basis for enterprises to design and optimize collaborative distribution paths.

摘要： 贴合现实场景的多车多无人机协同配送问题由于其复杂性，成为路径优化问题的关键挑战。综合考虑每辆卡车可携带多架无人机、无人机在单航程内可多次配送以及客户存在配送时间要求等约束，提出带时间窗的多车多无人机协同配送问题，并以最小化总配送成本目标建立混合整数规划模型。为求解该问题，设计了一种结合自适应大邻域搜索算法和模拟退火算法的双链混合启发式算法。其中，双链编码结构通过分离客户配送顺序和配送工具，直观展示卡车和无人机协同配送路径，便于计算对应客户的时间窗约束，还有利于破坏算子与修复算子快速生成新解。最后，通过算例分析验证了算法的有效性和双链编码结构对该复杂场景的适应性。结果表明该算法在小、中、大规模算例中均能快速生成高质量解，小规模算例中相较于Gurobi求解器计算时间平均缩短94.34%，大规模算例中比可变邻域搜索算法总成本平均减少9.11%。此外，灵敏度分析进一步表明，卡车携带无人机数量和无人机成本是影响总配送成本和路径方案制定的关键因素。