多行程多投递模式下带无人机车辆路径问题的两阶段启发式算法研究

《Journal of Systems Engineering and Electronics》：Two-Phase Heuristic for Vehicle Routing Problem with Drones in Multi-Trip and Multi-Drop Mode

本文研究多行程多投递模式下的带无人机车辆路径问题(VRP-mmD)，针对传统物流配送中最后一公里时效性差的痛点，提出并行路径构建启发式算法(PRCH)与自适应邻域搜索启发式算法(ANSH)相结合的两阶段优化方法。通过基准数据集验证，该算法在求解质量上显著优于CPLEX求解器和现有先进算法，平均求解时间缩短60%以上，为无人机-卡车协同配送提供了高效稳定的解决方案。

　　

随着电商物流对时效性要求的不断提升，最后一公里配送已成为影响客户体验的关键环节。各大物流企业纷纷推出次日达、当日达甚至半小时达服务，传统卡车配送模式面临严峻挑战。无人机配送凭借其时效性强、成本低、不受交通拥堵影响等优势，近年来成为传统卡车配送的重要补充。由此催生了卡车与无人机协同配送的新模式，也带动了对两者路径调度问题的深入研究。

在无人机续航能力和载重能力不断提升的背景下，物流无人机已能够携带更多包裹进行长距离配送，多投递模式逐渐成为现实。这使得卡车-无人机协同配送模式更加灵活。本文研究的VRP-mmD问题正是针对这一趋势，允许每架无人机执行多次配送行程，并在每次行程中服务多个客户节点。与传统的单次单点配送模式相比，这种模式能更好地发挥无人机的配送优势，提高整体配送效率。

为了求解这一复杂问题，MA Huawei等人提出了一种创新的两阶段启发式算法。第一阶段采用并行路径构建启发式算法(PRCH)，通过同步为卡车-无人机对分配尽可能多的节点，逐步减少在汇合节点的等待时间，快速生成初始解。第二阶段采用自适应邻域搜索启发式算法(ANSH)，通过自适应探索邻域结构对初始解进行改进。该算法特别设计了基于轮盘赌规则的自适应机制，根据邻域结构的搜索效果动态调整其选择概率。

关键技术方法包括：建立VRP-mmD的混合整数规划模型(MIP)；设计并行路径构建机制实现卡车路径与无人机子路径的同步生成；开发包含组间操作符和组内操作符的邻域结构；采用模拟退火机制避免陷入局部最优。实验基于Augerat和Christofides等经典CVRP基准数据集，对比CPLEX求解器和现有算法验证性能。

计算实验结果分析

在小规模问题测试中，ANSH算法在10个实例上平均与最优解的差距仅为0.8%，求解时间不足0.5秒，显著优于PRCH的7.2%差距。在32-1000节点的大规模问题测试中，该算法相比CPLEX求解器获得平均61.3%的改进效果，且求解时间随问题规模增长缓慢。在VRP-smD模式下的对比实验中，PRCH和ANSH分别以2.03%和5.37%的优势超越DTRC和LNS算法，同时计算时间减少80%以上。稳定性测试表明，算法在100-1000节点的大规模问题上相对方差均值低于0.03，表现出良好的鲁棒性。

研究结论与意义

本研究首次系统性地提出了针对多行程多投递模式的带无人机车辆路径问题建模与求解框架。所建立混合整数规划模型完整刻画了无人机多次起降、多客户服务、时间同步等实际约束条件。两阶段启发式算法通过并行路径构建和自适应邻域搜索的有机结合，在求解质量和计算效率间实现了良好平衡。实验证明该算法在不同规模问题上均能稳定获得优质解，为实际物流场景中的无人机-卡车协同配送提供了可靠的技术支持。未来研究方向包括异构车队调度、动态环境适应以及深度学习与启发式算法的融合应用。

该研究成果发表于《Journal of Systems Engineering and Electronics》2025年第36卷第4期，为智能物流领域的路径优化问题提供了创新性的解决方案，对推动无人机在商业配送领域的实际应用具有重要理论价值和实践意义。