胶囊聚合注意力机制求解车辆路径规划问题  

Capsule aggregated attention for vehicle routing problems

作　　者：师瑞阳 牛凌峰[2,3,4] 戴彧虹 Ruiyang Shi;Lingfeng Niu;Yu-Hong Dai

机构地区：[1]中国科学院大学数学科学学院,北京100049 [2]中国科学院虚拟经济与数据科学研究中心,北京100190 [3]中国科学院大数据挖掘与知识管理重点实验室,北京100190 [4]中国科学院大学经济与管理学院,北京100190 [5]中国科学院数学与系统科学研究院计算数学与科学工程计算研究所,北京100190

出　　处：《中国科学:数学》2025年第4期849-874,共26页Scientia Sinica:Mathematica

基　　金：国家自然科学基金(批准号:11991021,11991020和12271503)资助项目。

摘　　要：近年来,深度学习在求解车辆路径规划问题(vehicle routing problem,VRP)中展示出巨大潜力.注意力机制在其中发挥着重要作用,已成为提高求解质量的关键模块,但其加和聚合范式不足以充分捕捉VRP实例中丰富的信息.针对该问题,本文提出一种新的胶囊聚合注意力机制.它使用胶囊存储更多的信息,应用动态路由机制进行信息聚合,利用软门控胶囊选择器来区分不同胶囊的重要性,并修改解码过程中的上下文节点向量以反映状态变化.基于上述改进,本文设计了一种强化学习框架下求解VRP的新型图注意力网络,并通过大量数值实验证明了所提出方法的有效性.Deep learning-based methods have shown great potential for solving the vehicle routing problem(VRP)in recent years.In the current learning-based models,attention mechanism plays an important role and becomes one of the key modules for improving the performance.However,the aggregate-by-summation paradigm of attention is not expressive enough to fully capture the rich information in the VRP.To solve this problem,we propose a novel capsule aggregated attention mechanism,which utilizes capsule to store more information,applies dynamic routing for information aggregation,exploits soft gated capsule selector to differentiate the importance of different capsules,and modifies the context node vector in the decoding process to reflect the state changes.Based on the above modifications,we design a new graph attention network for solving the VRP under the reinforcement learning framework in this paper,and validates the effectiveness of our proposed method through sufficient numerical experiments.

关 键 词：车辆路径规划问题 胶囊网络 注意力机制 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]