Adversarial Generative Flow Network for Solving Vehicle Routing Problems

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). 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 instances. Our code is available at https://github.com/ZHANG-NI/AGFN . The vehicle routing problem (VRP) represents a fundamental and intricate combinatorial optimization challenge with extensive real-world implications (Toth & Vigo, 2014), including supply chain management (Lee et al., 2006), last-mile delivery services (Koc et al., 2020), and public transportation (Hassold & Ceder, 2014). Given its widespread occurrence across numerous domains, the VRPs have been the subject of extensive research for decades within the Operations Research (OR) community. Particularly, practitioners employ both exact and heuristic methods to tackle complex optimization problems including VRPs. Exact methods, such as branch-and-bound (Lawler & Wood, 1966), branch-and-cut (Tawarmalani & Sahinidis, 2005), and column generation (Barnhart et al., 1998), guarantee optimal solutions but often face computational limitations for large-scale instances.