【作者】 刘畅；

【导师】 张永刚；

【作者基本信息】 吉林大学 ， 计算机科学与技术， 2024， 硕士

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

【Abstract】 With the rapid development of the transportation and logistics industry,logistics companies are faced with concurrent challenges and opportunities.Particularly with the growing popularity of e-commerce and instant delivery services,efficiently and economically completing cargo delivery has become an urgent issue for logistics companies.In academic research,such logistics distribution problems are defined as the Vehicle Routing Problem(VRP).Traditional methods for solving the VRP mainly divide into exact algorithms and heuristic algorithms.However,as problem sizes in actual application scenarios increase,traditional solving methods are under significant computational pressure.Especially when the constraints of the problem change,traditional algorithms need to be rerun,increasing time expenditure and leading to considerable waste of computational resources.In recent years,Deep Reinforcement Learning(DRL)has been widely applied to solve VRP issues due to its powerful computation and sequential decision-making capabilities demonstrated in fields such as computer vision and natural language processing,introducing a new solution paradigm for these types of problems.This paper focuses on efficient optimization strategies for the Vehicle Routing Problem,integrating deep reinforcement learning and local search to solve the VRP.The main research works are as follows:(1)Addressing the limitations of existing DRL methods in learning VRP features and the existing gaps in solution quality compared to traditional algorithms.We propose a Graph Attention Network for Node and Edge(GAT-NE),employing a graph attention-based encoder to integrate edge information generated during the solving process to optimize node embeddings,thereby enhancing the accuracy of VRP solutions.Additionally,we propose the use of an improved REINFORCE algorithm based on the rollout baseline strategy for model training,aimed at freezing policy network parameters and reducing variance during training to stabilize training and improve model performance.To fully explore the upper solving limit of GAT-NE,we employ both greedy and random sampling decoding strategies during the testing phase to balance speed and accuracy.Experimental results indicate that compared to existing DRL methods,GAT-NE demonstrates superior solution quality,stronger generalization capability,and faster solving speed on public benchmark datasets and randomly generated datasets.(2)In response to the traditional Large Neighborhood Search(LNS)algorithms,which require extensive domain knowledge yet still result in suboptimal solution quality when solving VRP,we propose a Deep Reinforcement Learning algorithm based on Large Neighborhood Search to solve larger-scale VRP issues,termed the Action Sequence Algorithm based on Path Reconstruction Strategy(AS-PRS).The process of reconstructing solutions in AS-PRS is defined as a Markov Decision Process,and reinforcement learning algorithms are used to guide agents in selecting optimal actions in specific states to construct complete solution sequences and maximize long-term rewards.Moreover,a two-stage solving framework is adopted.Based on GAT-NE,we provide a diverse initial solution set for the AS-PRS algorithm,aimed at providing a balanced set for optimization and exploration during the initial phase of the AS-PRS algorithm,enhancing the global search capability of the algorithm and avoiding early convergence to local optima.The two-stage solving framework not only improves the quality of the solutions but also reduces the solving time required by the LNS algorithm,demonstrating the potential of the AS-PRS algorithm in solving large-scale VRP problems.Experimental results on randomly generated test datasets and clustered datasets from CVRPLIB indicate that both the AS-PRS algorithm and the two-stage framework show improvements in solution quality and solving time.更多还原