摘要
随着交通运输与物流配送行业的快速发展，物流企业面对的挑战和机遇并存。特别是在电子商务和即时配送服务日益普及的背景下，如何高效、经济地完成货物配送成为了物流企业亟需解决的问题。在学术研究中，此类物流配送问题被定义为车辆路径问题（VehicleRoutingProblem，VRP）。VRP问题的传统求解方法主要分为精确算法和启发式算法。然而，随着实际应用场景中问题规模的扩大，传统求解方法面临巨大的计算压力。特别是当问题的约束条件发生变化时，传统算法需要重新进行搜索，不仅增加了时间开销，同时也造成了计算资源的大量浪费。近年来，深度强化学习（DeepReinforcementLearning，DRL）因其在计算机视觉、自然语言处理等领域展现出强大的计算和序列决策能力，已被广泛应用于VRP问题的求解中，为这类问题开创全新的求解模式。 本文围绕车辆路径问题的高效优化策略开展研究，结合深度强化学习和局部搜索来求解VRP问题。主要研究工作如下： （1）针对现有DRL方法在学习VRP特征时存在局限，并且在求解质量方面与传统算法相比仍存在差距的问题。提出联合学习节点和边特征的图注意力模型（GraphAttentionnetworkforNodeandEdge，GAT-NE），采用基于图注意力的编码器整合求解过程中生成的边信息来优化节点嵌入，提升VRP求解的准确性。此外，提出将基于展开基线策略改进的REINFORCE算法应用于模型的训练，旨在冻结策略网络参数并降低训练过程中的方差，进而稳定训练并提高模型性能。为了充分探索GAT-NE的求解上限，在测试阶段采用贪婪和随机采样两种解码策略，实现速度与精度的权衡。实验结果表明，相比现有的DRL方法，GAT-NE在公共基准数据集和随机生成的数据集上展示出更优的求解质量和更强的泛化能力。 （2）针对传统大邻域搜索（LargeNeighborhoodSearch，LNS）算法在求解VRP时需要引入大量领域知识，但求解质量仍然不高的问题。提出基于LNS的深度强化学习算法来求解较大规模的VRP问题，称之为带有路径重构策略的动作序列算法（ActionSequenceAlgorithmbasedonPathReconstructionStrategy，AS-PRS）。将AS-PRS重构解决方案的过程定义为一个马尔可夫决策过程，并采用强化学习算法来指导智能体在特定状态下选择最优动作，以构造完整解序列并最大化长期奖励。此外，采用两阶段求解框架，基于GAT-NE为AS-PRS算法提供一个多样化的初始解集，旨在为AS-PRS算法的初始阶段提供一个平衡优化与探索的解集，增强算法的全局搜索能力，避免其早期收敛于局部最优。两阶段求解框架不仅提高解决方案的质量，也降低了AS-PRS算法所需的求解时间，显示出AS-PRS算法求解大规模VRP问题的潜力。在随机生成的测试数据集以及CVRPLIB的聚类数据集上的实验结果表明，AS-PRS算法和两阶段框架在求解质量和求解时间上均有一定的提升。
NETL