Hybrid-Balance GFlowNet for Solving Vehicle Routing Problems

📄 arXiv: 2510.04792v1 📥 PDF

作者: Ni Zhang, Zhiguang Cao

分类: cs.AI

发布日期: 2025-10-06

备注: Accepted by NeurIPS 2025

💡 一句话要点

提出混合平衡GFlowNet，融合轨迹平衡与细节平衡求解车辆路径问题

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 车辆路径问题 GFlowNet 轨迹平衡 细节平衡 组合优化 深度学习 强化学习

📋 核心要点

  1. 现有基于GFlowNet的VRP方法侧重全局优化，忽略局部优化，而仅使用细节平衡难以解决需要全局轨迹优化的VRP问题。
  2. 提出混合平衡GFlowNet (HBG) 框架，通过原则性和自适应的方式整合轨迹平衡 (TB) 和细节平衡 (DB)，发挥二者互补优势。
  3. HBG集成到AGFN和GFACS后，在CVRP和TSP上均表现出显著改进，验证了其提升解质量和泛化能力的效果。

📝 摘要（中文）

现有的基于GFlowNet的车辆路径问题(VRP)解决方法通常采用轨迹平衡(TB)来实现全局优化，但往往忽略了局部优化的重要性。虽然细节平衡(DB)能更有效地解决局部优化问题，但它本身不足以解决VRP，因为VRP本质上需要整体的轨迹优化。为了解决这些局限性，我们引入了混合平衡GFlowNet(HBG)框架，该框架通过对齐TB和DB内在的互补优势，以一种原则性和自适应的方式独特地整合了TB和DB。此外，我们为以车场为中心的场景(如带容量约束的车辆路径问题(CVRP))提出了一种专门的推理策略，利用车场节点在选择后继节点方面的更大灵活性。尽管有这种专业化，HBG仍然保持了广泛的适用性，有效地扩展到没有明确车场的问题，如旅行商问题(TSP)。我们通过将HBG集成到两个已建立的基于GFlowNet的求解器(即AGFN和GFACS)中来评估HBG，并证明了在CVRP和TSP上的一致和显著的改进，突出了我们的方法所提供的增强的解决方案质量和泛化能力。

🔬 方法详解

问题定义：论文旨在解决车辆路径问题（VRP），包括带容量约束的车辆路径问题（CVRP）和旅行商问题（TSP）。现有基于GFlowNet的方法，如AGFN和GFACS，主要依赖轨迹平衡（TB）进行全局优化，但忽略了局部优化。而细节平衡（DB）虽然擅长局部优化，但单独使用无法有效解决需要全局轨迹优化的VRP问题。

核心思路：论文的核心思路是结合轨迹平衡（TB）和细节平衡（DB）的优势，提出混合平衡GFlowNet（HBG）。TB擅长全局探索，DB擅长局部优化，HBG通过自适应地调整TB和DB的权重，在全局和局部之间取得平衡，从而提高解的质量。这种混合策略旨在克服单一平衡方法的局限性。

技术框架：HBG框架主要包含以下几个部分：1）GFlowNet模型，用于生成车辆路径的轨迹；2）轨迹平衡（TB）损失，用于鼓励全局探索；3）细节平衡（DB）损失，用于优化局部路径；4）自适应权重调整机制，用于动态调整TB和DB损失的权重。在CVRP等以车场为中心的场景中，还设计了专门的推理策略，利用车场节点选择后继节点的灵活性。

关键创新：HBG的关键创新在于混合平衡策略，即同时利用轨迹平衡和细节平衡，并通过自适应权重调整机制动态平衡二者的贡献。与现有方法相比，HBG不是简单地选择TB或DB，而是将二者有机结合，从而在全局探索和局部优化之间取得更好的平衡。此外，针对CVRP等问题设计的depot-centric推理策略也是一个创新点。

关键设计：HBG的关键设计包括：1）TB和DB损失函数的具体形式；2）自适应权重调整机制，例如，可以根据训练过程中的性能动态调整TB和DB的权重；3）GFlowNet模型的网络结构，例如，可以使用Transformer等结构来编码车辆路径信息；4）depot-centric推理策略的具体实现，例如，可以增加车场节点被选择的概率。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，HBG在CVRP和TSP问题上均取得了显著的性能提升。例如，在CVRP问题上，HBG集成到AGFN后，解的质量平均提升了X%（具体数值未知），集成到GFACS后，解的质量平均提升了Y%（具体数值未知）。在TSP问题上，HBG也表现出类似的提升。这些结果表明，HBG能够有效地提高解的质量和泛化能力。

🎯 应用场景

该研究成果可广泛应用于物流配送、交通运输、供应链管理等领域，尤其是在需要优化车辆行驶路线、降低运输成本的场景中。通过更高效的路径规划，可以减少燃油消耗、降低碳排放，从而实现更可持续的运输模式。此外，该方法还可以扩展到其他组合优化问题，如调度问题、资源分配问题等。

📄 摘要（原文）

Existing GFlowNet-based methods for vehicle routing problems (VRPs) typically employ Trajectory Balance (TB) to achieve global optimization but often neglect important aspects of local optimization. While Detailed Balance (DB) addresses local optimization more effectively, it alone falls short in solving VRPs, which inherently require holistic trajectory optimization. To address these limitations, we introduce the Hybrid-Balance GFlowNet (HBG) framework, which uniquely integrates TB and DB in a principled and adaptive manner by aligning their intrinsically complementary strengths. Additionally, we propose a specialized inference strategy for depot-centric scenarios like the Capacitated Vehicle Routing Problem (CVRP), leveraging the depot node's greater flexibility in selecting successors. Despite this specialization, HBG maintains broad applicability, extending effectively to problems without explicit depots, such as the Traveling Salesman Problem (TSP). We evaluate HBG by integrating it into two established GFlowNet-based solvers, i.e., AGFN and GFACS, and demonstrate consistent and significant improvements across both CVRP and TSP, underscoring the enhanced solution quality and generalization afforded by our approach.