计算机工程与科学

作者：王扬, 陈智斌

单位：（昆明理工大学理学院，云南 昆明 650000）

关键词：带容量的车辆路径问题,动态图转换模型,动态位置编码,深度强化学习,图神经网络,组合最优化问题,

基金：国家自然科学基金(11761042)

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

来源：2023年第5期

《计算机工程与科学》期刊编辑部

查看计算机工程与科学杂志2023年第5期