混合平衡流生成网络提升车辆路径问题求解质量
Hybrid-Balance GFlowNet for Solving Vehicle Routing Problems
- 融合轨迹平衡与详细平衡，兼顾全局与局部优化
- 在CVRP和TSP上均显著提升解的质量与泛化能力
- 适合需要高效路径规划的物流、调度场景
现有基于流生成网络（GFlowNet）的车辆路径问题（VRP）求解方法通常采用轨迹平衡（TB）实现全局优化，但忽视了局部优化的重要性。尽管详细平衡（DB）更擅长局部优化，但单独使用难以解决需整体路径优化的VRP问题。为此，我们提出混合平衡流生成网络（HBG）框架，通过原则性且自适应的方式融合TB与DB的互补优势。此外，针对以枢纽节点为中心的场景（如带容量约束的车辆路径问题，CVRP），我们设计了一种专用推理策略，利用枢纽节点在选择后继节点上的更高灵活性。尽管该策略具针对性，HBG仍具备广泛适用性，可有效拓展至无显式枢纽节点的问题，如旅行商问题（TSP）。我们将HBG集成到两个成熟的GFlowNet求解器（AGFN与GFACS）中进行评估，在CVRP与TSP上均实现持续且显著的性能提升，验证了该方法在解质量与泛化性方面的优势。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。