针对车辆路径问题的考虑难度与抑制记忆的GFlowNets模型

《Neurocomputing》：Difficulty-aware and memory-suppressed GFlowNets for vehicle routing problems

　　

摘要

近年来，基于神经网络的方法在解决车辆路径问题方面取得了显著进展。对抗生成流网络通过引入生成流网络结构，有效克服了Transformer架构存在的可扩展性瓶颈以及多样性不足的问题。然而，由于大量简单样本导致的梯度无效，以及判别器对特定节点坐标的过度拟合“记忆效应”，其训练稳定性和泛化能力受到严重限制。为解决这些问题，本文提出了难度感知且能抑制记忆的生成流网络框架——DAMS-GFN。该框架引入了分层难度感知损失函数，通过动态加权机制抑制简单样本的梯度贡献，迫使模型专注于具有高区分度的困难样本。同时，通过系统谱归一化和噪声注入机制，严格约束判别器的利普希茨连续性，并扰动输入特征，从而打破坐标依赖性，提升对拓扑结构的稳健学习能力。在车辆路径问题和旅行商问题上的大量实验表明，DAMS-GFN在处理大规模实例时显著提升了计算效率，且在解决方案质量和泛化能力方面均优于包括AGFN在内的现有方法。这项工作成功实现了大规模组合优化问题的高效求解与对抗型神经网络模型稳定训练之间的平衡，为复杂的路由任务提供了一种稳健实用的解决方案。

引言

作为现代物流和供应链管理的核心组成部分，车辆路径问题在众多实际应用中发挥着关键作用，比如城市按需配送、电子商务物流以及智能交通调度[8]、[14]、[45]。从数学角度来看，车辆路径问题属于高度复杂、属于NP难类的组合优化问题。过去几十年来，运筹学界一直在努力开发各种解决方案算法。其中，精确算法——主要是分支定界法和列生成法——能够提供理论上的最优解保证[1]、[33]。不过，这类算法的计算复杂度会随着问题规模的增大而呈指数级上升，因此无法用于处理大规模实例。于是，学术界和工业界普遍采用元启发式算法，如Lin-Kernighan-Helsgaun算法[20]、自适应大邻域搜索算法[49]以及混合遗传搜索算法[54]。尽管这些方法能够在合理时间内得到高质量的近似解，但它们严重依赖于手工设计的、针对特定领域的启发式规则。这种依赖不仅会增加开发成本，还会导致在面对具有不同分布或运营约束的车辆路径问题变体时缺乏灵活性和可扩展性[17]。

近年来，得益于深度学习的快速发展，基于学习的神经组合优化方法成为了一种极具前景的替代方案[5]、[44]。这类方法借助监督学习或强化学习技术[55]，能够以端到端的方式直接学习解决方案的构建策略，从而大幅减少对领域专家知识的依赖。早期的基于神经网络的问题求解器大多基于Transformer架构构建[9]、[29]。虽然这类模型在处理中小规模问题时表现优异，但自注意力机制所具有的二次方级计算复杂度导致了严重的可扩展性瓶颈。此外，这类模型还难以生成多样性较高的候选解。为克服这些缺陷，近期研究引入了生成流网络结构[3]，并提出了对抗生成流网络框架[62]。通过将生成流网络强大的多样性采样能力与对抗式评估机制相结合，AGFN为解决车辆路径问题提供了一种全新的思路。

尽管这种对抗式框架在理论上具有很大潜力，但在应用于复杂的组合优化任务时，现有框架仍存在若干根本性的瓶颈。在庞大的搜索空间中，高质量解极为稀少，因此模型训练往往会被大量“简单负样本”产生的无效梯度所主导。关于生成流网络的研究表明，奖励稀疏的环境常常会导致损失值出现剧烈波动、优化过程不稳定，甚至出现模式崩溃现象[34]、[35]。与这些观察结果一致，我们对AGFN基线的实证分析（第4节）也发现，其在训练过程中存在不稳定的收敛行为。此外，判别器倾向于过度拟合训练集的绝对坐标分布，而非学习通用的拓扑路由规则，从而导致“坐标记忆效应”[25]。在关于基于神经网络的问题求解器的最新研究中，也观察到了类似的脆弱性问题[15]。第4节中的零样本几何鲁棒性测试进一步证实了这种坐标依赖性：AGFN基线在坐标平移和旋转变换下，性能会出现明显下降，且最优解差距也会随之增大。因此，这些实证结果表明，过强的坐标依赖性会严重限制模型在空间分布发生变化时的泛化能力，尤其是在面对大规模的异常数据时[6]。

为解决上述问题，本文提出了难度感知且能抑制记忆的生成流网络框架DAMS-GFN，旨在突破神经网络构建型求解器在对抗式训练过程中面临的泛化能力和稳定性两大瓶颈。首先，我们在生成器端引入了分层难度感知损失函数。该函数通过构建动态加权机制，能够自适应地抑制简单样本的梯度贡献，从而帮助模型摆脱无效梯度的困扰，专注于挖掘具有高区分度的困难样本。其次，在对抗训练阶段，我们系统地采用了系统谱归一化和噪声注入机制。具体而言，系统谱归一化通过严格约束判别器网络的利普希茨连续性，为梯度变化较大的训练过程提供稳定性保障；而噪声注入机制则通过对输入端的节点特征施加随机扰动，打破模型对固定坐标模式的记忆，迫使图神经网络编码器提取更本质的拓扑不变量。通过协同优化这三种机制，我们的模型在保持构建型求解器快速推理优势的同时，大幅提升了其泛化能力。

综上所述，本文的主要贡献如下：

• •
  提出了用于解决车辆路径问题的DAMS-GFN框架。该框架通过引入分层难度感知损失函数，利用动态加权机制有效抑制了大量简单负样本带来的无效梯度，使模型能够专注于处理具有高区分度的优质样本。
• •
  设计了系统谱归一化和噪声注入机制，并将其付诸实践。这两种机制相互配合，既严格约束了判别器的利普希茨连续性，又扰动了输入特征，从而有效打破了模型对特定节点坐标的依赖，显著提升了对抗式训练的稳定性以及模型对图拓扑结构的稳健学习能力。
• •
  在车辆路径问题和旅行商问题上对所提出的框架进行了全面评估。在多尺度合成数据集及大规模真实实例上的实验结果表明，DAMS-GFN在解决方案质量以及跨尺度泛化能力方面均优于其他主流基准方法，同时还保持了较高的计算效率。

章节摘录

用于解决车辆路径问题的神经网络求解器

近年来，深度学习在组合优化领域的应用引发了范式变革[26]。用于解决车辆路径问题的神经网络求解器主要沿着两条平行技术路线发展：构建型方法和改进型方法。构建型求解器致力于以端到端的方式直接生成完整的路径序列。Kool等人率先将Transformer架构引入这一领域，并提出了注意力模型[29]；

方法论

与传统构建型神经网络求解器相比，作为新兴概率生成模型的生成流网络试图学习与奖励函数成正比的概率流策略。这一特性使得该模型天然具备生成多样化解决方案的能力，这些解决方案既包括最优解，也包括次优解，甚至是较差的解[4]。然而，尽管生成流网络在生成多样化解决方案方面具有巨大潜力，但在对抗式训练过程中却面临着诸多挑战。

实验部分

在本节中，我们首先在多种规模的车辆路径问题上开展了大量实验，以验证所提出的DAMS-GFN相较于传统方法和现有神经网络基准模型的优越性。此外，为了体现DAMS-GFN的通用性，我们还将其应用于旅行商问题的求解。

数据集配置：为确保与现有的最先进方法进行公平、标准化的比较，我们严格遵循了神经组合优化领域的常用评估规范[29]，

结论

本文提出了DAMS-GFN框架，旨在解决大规模车辆路径问题的神经组合优化方法中普遍存在的泛化瓶颈和训练稳定性问题。通过结合分层难度感知损失函数、系统谱归一化以及噪声注入机制，所提出的框架成功实现了纯构建型求解器的快速推理能力与其解决方案质量之间的最佳平衡。在大量对比实验中，

CRediT作者贡献说明

赵秀健：论文撰写——初稿撰写、验证、软件实现、方法设计。牛云云：论文撰写——审阅与编辑、研究指导、资金获取、概念构思。李金奇：数据收集与整理。

利益冲突声明

作者声明，他们不存在任何可能影响本文研究结果的已知财务利益关系或个人关系。

致谢

本研究得到了中国国家自然科学基金[项目编号62172373、61872325]以及中国中央高校基本科研业务费[项目编号2652019028]的支持。

赵秀健于2024年在中国地质大学（北京）获得计算机科学技术专业学士学位。他目前在中国地质大学（北京）人工智能学院攻读硕士学位。他的研究兴趣包括神经组合优化和机器学习领域。

赵秀健|牛云云|李金奇

中国地质大学（北京）人工智能学院，北京100083，中国