一种求解CVRP的动态图转换模型

王扬; 陈智斌

首页> 中文期刊> 《计算机工程与科学》 >一种求解CVRP的动态图转换模型

一种求解CVRP的动态图转换模型

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

带容量的车辆路径问题是组合最优化问题中的经典问题,多年以来一直被反复研究。最近,Transformer已经成为解决车辆路径问题的主流深度学习架构。然而,由于一个实例在模型不同构造步骤中会发生改变,相应的节点特征也需要更新,传统位置编码方法不适用于提取动态优化问题的位置信息。因此,现有方法在提高学习效率方面效果较差。以最小化路径长度为目标,提出一种动态图转换模型(DGTM)和动态位置编码(DPE)方法,并使用一种双重损失REINFORCE算法训练DGTM模型。此外,强化学习、图神经网络和Transformer架构相结合,提高了模型的训练效率,增强了神经网络对带约束路径问题信息的表征能力。实验结果表明,DGTM模型在此问题上的优化效果超越了目前基于深度强化学习的方法和部分传统算法,整体性能优于专业求解器的,且具有较好的泛化性能,为求解图上组合最优化问题提供了一种有效方法。

著录项

来源
《计算机工程与科学》 |2023年第5期|859-868|共10页
作者
王扬; 陈智斌;
展开▼
作者单位

昆明理工大学理学院;

展开▼
原文格式 PDF
正文语种 chi
中图分类人工智能理论;
关键词
带容量的车辆路径问题; 动态图转换模型; 动态位置编码; 深度强化学习; 图神经网络; 组合最优化问题;

相似文献

中文文献
外文文献
专利

1. 一种求解大规模CVRP的有效算法 [J] . 饶舜 ,张玉州 . 安庆师范大学学报:自然科学版 . 2022,第1期
2. 求解CVRP问题的一种改进启发式蚁群算法 [J] . 周和平 ,陈亮 . 后勤工程学院学报 . 2015,第004期
3. 面向不同目标偏好的 CVRP多目标模型及其求解方法 [J] . 王超 ,金淳 ,韩庆平 . 计算机应用研究 . 2016,第8期
4. 一种高效的动态图最大加权独立集求解算法 [J] . 祁才云 ,周军锋 ,杜明 . 新一代信息技术 . 2021,第007期
5. 一种高效的动态图最大加权独立集求解算法 [J] . 祁才云 ,周军锋 ,杜明 . 新一代信息技术 . 2021,第007期
6. 一种基于动态图的军事信息服务需求预测模型研究 [C] . 任毅 ,肖治庭 . 中国电子学会电子系统工程分会第九届军事信息系统软件与仿真学术研讨会 . 2014
7. 基于定性定量转换模型的设计问题求解方法 [A] . 郭琦 . 2007

一种求解CVRP的动态图转换模型

摘要

著录项

相似文献

相关主题

期刊订阅