计算机应用研究2024，Vol.41Issue(11)：3245-3250,6.DOI:10.19734/j.issn.1001-3695.2024.03.0101
基于端到端深度强化学习求解有能力约束的车辆路径问题
Solving capacitated vehicle routing problems based on end to end deep reinforcement learning
摘要
Abstract
The capacitated vehicle routing problem(CVRP)is the most prevalent problem model in supply chain applications at present,and researchers often use heuristic algorithms to solve it,but the solution speed is slow and the quality of the solu-tion cannot be guaranteed.This paper proposed an end-to-end deep reinforcement learning(DRL)network framework to study the CVRP problem.Firstly,it used the edge graph attention network encoder(EGATE)to perform feature embedding enco-ding on the graph representation of VRP.Then,it designed a multi-head attention decoder(MAD)to decode the encoded graph representation.Additionally,it proposed a multi-decoding strategy to enhance the spatial diversity of the solutions.Con-tinuing with the training of the end-to-end network model using the baseline REINFORCE algorithm with a rollout baseline,the adaptive updating of the baseline was employed to enhance the effectiveness of model training.Additionally,reward function normalization and optimization using Adam optimizer were utilized to further improve the algorithm.Finally,this paper valida-ted the feasibility and effectiveness of the proposed end-to-end DRL framework through experiments on problems of different scales,comparing its performance against other algorithms.The average solution time of the trained model on the CVRPLIB public dataset is only 0.189 s to obtain a better solution.关键词
车辆路径问题/路径规划/端到端模型/深度强化学习/基线REINFORCE算法Key words
vehicle routing problem(VRP)/path planning/end-to-end model/deep reinforcement learning/baseline REIN-FORCE algorithm分类
信息技术与安全科学引用本文复制引用
葛斌,田文智,夏晨星,秦望博..基于端到端深度强化学习求解有能力约束的车辆路径问题[J].计算机应用研究,2024,41(11):3245-3250,6.基金项目
国家重点研发计划资助项目(2020YFB1314103) （2020YFB1314103）
