用对抗生成流网络提升路径规划多样性与质量
Adversarial Generative Flow Network for Solving Vehicle Routing Problems
- 结合生成流网络与判别模型，交替训练以生成多样解
- 在CVRP和TSP上优于主流神经求解器，泛化能力强
- 适合需要高质量多样化解的物流与调度场景
近期针对车辆路径问题（VRPs）的研究广泛采用深度（强化）学习进行端到端解构建。然而，现有基于Transformer的构造型神经求解器存在可扩展性差、解多样性不足的问题。为此，本文提出超越Transformer的新型框架——对抗生成流网络（AGFN），将具备天然多样性生成能力的概率模型生成流网络（GFlowNet）与互补的解判别（评估）模型结合，通过对抗式交替训练提升整体解的质量，并引入混合解码方法完成最终解构建。该框架应用于容量限制车辆路径问题（CVRP）与旅行商问题（TSP），实验表明其在合成及真实世界基准实例上均优于主流构造型神经求解器，展现出强大的泛化能力。
原文摘要 · Abstract (English)
Recent research into solving vehicle routing problems (VRPs) has gained significant traction, particularly through the application of deep (reinforcement) learning for end-to-end solution construction. However, many current construction-based neural solvers predominantly utilize Transformer architectures, which can face scalability challenges and struggle to produce diverse solutions. To address these limitations, we introduce a novel framework beyond Transformer-based approaches, i.e., Adversarial Generative Flow Networks (AGFN). This framework integrates the generative flow network (GFlowNet)-a probabilistic model inherently adept at generating diverse solutions (routes)-with a complementary model for discriminating (or evaluating) the solutions. These models are trained alternately in an adversarial manner to improve the overall solution quality, followed by a proposed hybrid decoding method to construct the solution. We apply the AGFN framework to solve the capacitated vehicle routing problem (CVRP) and travelling salesman problem (TSP), and our experimental results demonstrate that AGFN surpasses the popular construction-based neural solvers, showcasing strong generalization capabilities on synthetic and real-world benchmark instances.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。