编辑推荐：
提出双分支距离感知神经求解器DBDA，结合全局与局部注意力机制，融入距离感知和惩罚策略，提升跨分布VRP问题的鲁棒性和泛化能力，实验验证优于现有方法。
江一博|陶定月|陈伟杰|徐帆荣
浙江工业大学计算机科学与技术学院、软件学院，中国浙江省杭州市，310023
摘要
车辆路径问题（VRP）是一个经典的NP难问题，在物流和运输领域中占据核心地位，其特点是约束条件复杂且组合搜索空间庞大。神经组合优化（NCO）提高了求解效率和建模能力，但基于固定数据分布训练的模型在节点布局、问题规模或运营约束发生变化时往往性能下降，这在实际应用中很常见。为了解决这一限制，我们提出了基于多最优策略优化（POMO）框架的双分支距离感知神经求解器（DBDA）来处理跨分布的VRP问题。DBDA采用了两种互补的注意力分支：一种全局分支用于捕捉长距离的结构依赖性，另一种稀疏分支专注于局部关键邻域，从而实现节点交互的多尺度建模。距离感知机制通过将成对距离直接纳入注意力计算中来增强空间敏感性。此外，距离惩罚项引导学习过程朝向可行的路径，稳定收敛性。在合成数据集和TSPLIB/CVRPLIB基准测试上的实验表明，DBDA在空间模式变化的情况下始终优于现有的NCO方法，表现出更强的鲁棒性和泛化能力，同时保持了竞争力的推理效率。
引言
组合优化（CO）是运筹学和应用数学中的基础研究领域，在物流、制造和调度等领域有广泛的应用[1]。在CO问题中，车辆路径问题（VRP）既具有代表性又具有挑战性。VRP的NP难性质，加上复杂的结构约束和强烈的工业相关性，使其成为学术研究和工业实践中的长期研究课题[2]。
现有的VRP解决方法通常分为精确算法和启发式求解器。精确算法（如整数线性规划[3]）可以提供全局最优解，但随着问题规模的增加计算成本变得过高，限制了其在大规模实例中的应用。另一方面，启发式求解器（包括LKH[4]、[5]、SISR[6]和HGS[7]）虽然运行时间较短，但依赖于手工设计的组件和专家知识。当实例分布、问题规模或运营约束发生变化时，性能往往会下降。因此，在VRP研究中同时实现高推理效率和鲁棒泛化仍然是一个挑战。
深度学习的最新进展通过神经组合优化（NCO）[8]、[9]、[10]为VRP引入了一种基于学习的范式。NCO方法利用端到端神经架构直接从数据中学习路由策略，减少了对人工设计的启发式的依赖。传统的求解器（如Lin-Kernighan-Helsgaun算法[4]）依赖于精心调整的-opt搜索策略。相比之下，基于注意力的NCO模型（包括AM[11]和POMO[12]）以数据驱动的方式学习路由策略，并在标准基准测试中实现了具有竞争力的解决方案质量，同时显著降低了推理时间[13]、[14]。此外，预训练的NCO模型可以通过有限的额外训练适应新的问题实例。这些特性使得NCO成为需要快速和可扩展决策的场景中传统启发式求解器的有希望的替代方案。
尽管有这些优势，大多数现有的NCO方法假设训练和测试实例遵循相似的分布。但在实际应用中，客户位置可能表现出多样化的空间模式，包括聚集型、均匀型和边缘集中型分布。问题规模也有很大差异，客户数量从几十到数千不等。此外，不同的运营要求产生了多种VRP变体，如HCVRP[15]、VRPTW[16]和OVRP[17]。这些变化因素共同创造了异构和动态的环境，导致许多最先进的NCO模型性能下降，限制了它们的实际应用范围。
为了解决这一挑战，最近的研究探索了提高基于NCO的VRP求解器鲁棒性和泛化能力的策略。Sym-NCO[18]通过输入对称性增强来提高对节点排列的鲁棒性，而AMDKD[19]采用多教师知识蒸馏来实现不同数据分布之间的知识转移。ELG[20]结合了全局和局部注意力机制以及基于距离的惩罚项，以应对空间结构和问题规模的变化，从而提高对不同空间组织实例的适应性。DAR[21]将距离偏差直接纳入注意力计算中，以提高尺度适应性。
尽管这些方法代表了重要的进展，但仍存在几个关键挑战。首先，大多数现有模型依赖于单流注意力机制，这种结构限制了同时建模长距离结构依赖性和局部节点交互的能力。其次，空间信息通常是以隐式或间接的方式编码的，当节点分布或成对距离模式发生变化时，这种编码会降低鲁棒性。第三，辅助损失函数或惩罚项通常是单独引入的，这限制了它们在训练过程中平衡可行性和收敛性的能力。这些限制阻碍了当前基于NCO的VRP求解器在跨分布和多尺度条件下的可扩展性和适应性。
基于上述分析，我们提出了一个用于跨分布VRP的双分支距离感知神经求解器（DBDA）。DBDA遵循多最优策略优化（POMO）框架，并遵循两个原则：互补的多尺度表示和显式的空间感知。为了实现互补的多尺度表示，DBDA采用了双分支特征融合注意力结构。全局分支模拟整个实例中的长距离结构依赖性，而稀疏分支强调局部关键邻域并加强局部交互。两个分支之间的交互使得跨空间尺度的有效推理成为可能，并提高了对异构数据分布的适应性。为了实现显式的空间感知，DBDA通过距离感知机制将成对距离信息直接纳入注意力计算中，这种机制增强了几何敏感性并减少了对隐式空间信息的依赖。此外，引入了距离惩罚项作为自适应正则化器，通过引导优化过程朝向距离一致的路径模式来稳定训练并促进可行的高质量解决方案。主要贡献总结如下：
•提出了一种双分支距离感知神经求解器（DBDA）
，用于车辆路径问题，以提高在异构数据分布上的泛化能力。（第4.1节）在POMO框架内，采用了双分支特征融合架构，其中全局分支捕捉长距离结构依赖性，稀疏分支模拟局部交互，从而实现互补的多尺度表示。（第4.2节）
•结合了距离感知多头注意力机制
，将成对空间距离显式编码到注意力计算中，提高空间敏感性和对分布变化的鲁棒性。（第4.3节）•引入了惩罚增强解码模块
，以规范优化过程，加速收敛并促进可行的高质量路由解决方案。（第4.4节）•在合成数据集和TSPLIB/CVRPLIB基准测试上进行了广泛的实验，证明了所提出方法在鲁棒性和跨分布泛化能力方面优于现有的基于NCO的求解器。（第5节）
本文的其余部分组织如下：第2节回顾了车辆路径问题的相关研究。第3节介绍了问题表述和马尔可夫决策过程。第4节介绍了所提出的双分支距离感知模型，详细介绍了其关键组成部分，包括双分支架构、距离感知机制和距离惩罚策略。第5节描述了实验设置并提供了结果的全面分析。最后，第6节总结了本文并讨论了未来的研究方向。
相关研究
相关工作
在本节中，我们回顾了神经组合优化在车辆路径问题上的最新发展，重点关注基于Transformer的模型设计、神经VRP模型的泛化能力、神经VRP模型中的边缘感知增强以及用于图特征集成的多分支架构。
符号说明
在本文中，小写斜体字母（例如，）表示标量，小写粗体字母（例如，）表示向量，大写粗体字母（例如，）表示矩阵。除非另有说明，所有向量都是列向量，表示矩阵转置。的元素是，的元素是。零向量、全一向量和单位矩阵分别用、和表示。欧几里得（）范数用表示，表示
模型架构
解决大规模和跨分布的容量限制车辆路径问题需要能够同时表示全局关系结构和局部几何细节的神经架构。现有的神经组合优化模型[11]、[12]往往难以保持这种平衡。以全局注意力为主的架构通常会平滑整个图中的节点嵌入，这削弱了对短距离路由至关重要的局部空间线索的影响
数据集
本节描述了用于评估所提出的DBDA模型在TSP和CVRP学习任务上的数据集，特别关注跨分布泛化能力。考虑了两类数据集：允许控制空间结构的合成生成实例，以及反映真实路由场景的公共基准数据集。
合成数据集：遵循最近的研究[11]、[41]、[42]中介绍的生成程序，我们构建了
结论
本文提出了双分支距离感知（DBDA）框架，作为一个统一的神经求解器，用于旅行商问题（TSP）和容量限制车辆路径问题（CVRP）。DBDA结合了双分支编码器、几何感知注意力和约束感知解码器，以支持在异构空间布局下的稳健路由决策。全局-局部特征融合模块（GLFFM）整合了全局注意力分支，用于捕捉长距离结构依赖性
CRediT作者贡献声明
江一博：撰写——原始草稿、资源、方法论。陶定月：撰写——原始草稿、验证、方法论、形式分析。陈伟杰：撰写——原始草稿、监督、项目管理、资金获取。徐帆荣：验证、软件、形式分析。
利益冲突声明
作者声明他们没有已知的可能会影响本文工作的财务利益或个人关系。
致谢
作者感谢编辑和匿名审稿人的宝贵意见，这些意见极大地帮助改进了本文的表述。本工作得到了中国国家自然科学基金（编号12271131、11871183和61603338）、浙江省自然科学基金（编号LY21F030013）和浙江省教育厅（Y202455759）的支持。
江一博于2004年在浙江工业大学获得软件工程学士学位，2008年获得控制科学与工程博士学位。他目前是浙江工业大学计算机科学与技术学院的教员。他的研究兴趣包括深度学习、神经组合优化、大数据分析和智能计算。他在这些领域发表了30多篇同行评审的论文。
