计算机应用研究

作者：葛斌,田文智,夏晨星,秦望博,

单位：1.安徽理工大学计算机科学与工程学院,安徽淮南232001；2.合肥综合性国家科学中心能源研究院,合肥230031；

关键词：车辆路径问题,路径规划,端到端模型,深度强化学习,基线REINFORCE算法,

基金：国家重点研发计划资助项目(2020YFB1314103)；；

有能力约束的车辆路径问题（CVRP）是现阶段供应链应用最常见的问题模型，现多采用启发式算法求解。但随着问题规模增大，启发式算法求解速度慢且无法保证解的质量。提出端到端深度强化学习（DRL）网络框架对CVRP进行研究。首先利用边聚合图注意力网络编码器（EGATE）对车辆路径规划问题的图表示进行特征嵌入编码；然后设计多头注意力解码器（MAD）进行解码，并提出多解码策略以增加解的空间多样性；接着利用带回滚基线的基线REINFORCE算法对端到端网络模型进行训练，基线可自适应性更新以提升模型训练效果，并利用奖励函数归一化和Adam优化器对算法进行优化。最后通过对不同规模问题的实验以及与其他算法进行对比，验证了所提出端到端DRL框架的可行性与有效性，经过训练的模型在CVRPLIB公共数据集上的平均求解时间仅需0.189 s即可得到较优解。

来源：2024年第11期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2024年第11期