Zhang, N., Yang, J., Cao, Z., & Chi, X. (2025). Adversarial Generative Flow Network for Solving Vehicle Routing Problems. In Proceedings of the International Conference on Learning Representations (ICLR 2025).
Abstract:
Recent research into solving vehicle routing problems (VRPs) has gained significant traction, particularly through the application of deep (reinforcement) learn-ing 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 ap-proaches, 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 the 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 in-stance
License type:
Publisher Copyright
Funding Info:
This research is supported by core funding from: SIMTech
Grant Reference no. : NA
This research / project is supported by the National Research Foundation - AI Singapore Programme
Grant Reference no. : AISG3-RP-2022-031
This research / project is supported by the Ministry of Education - Academic Research Fund (AcRF) Tier 1 grant
Grant Reference no. : NA