Publication Type
Conference Proceeding Article
Version
submittedVersion
Publication Date
1-2025
Abstract
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.
Keywords
vehicle routing problem, generative flow networks, adversarial learning, deep reinforcement learning, solution diversity, Transformer alternatives, capacitated VRP, traveling salesman problem, neural solvers, generalization
Discipline
Artificial Intelligence and Robotics
Research Areas
Intelligent Systems and Optimization
Publication
Proceedings of the 13th International Conference on Learning Representations
First Page
80824
Last Page
80838
ISBN
9798331320850
Identifier
10.48550/arXiv.2503.01931
Publisher
International Conference on Learning Representations, ICLR
City or Country
Singapore
Citation
ZHANG, Ni; YANG, Jingfeng; CAO, Zhiguang; and CHI, Xu.
Adversarial generative flow network for solving vehicle routing problems. (2025). Proceedings of the 13th International Conference on Learning Representations. 80824-80838.
Available at: https://ink.library.smu.edu.sg/sis_research/10551
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.48550/arXiv.2503.01931