Adversarial Generative Flow Network for Solving Vehicle Routing Problems
Authors: Ni Zhang
Jingfeng Yang
Zhiguang Cao
Xu Chi
Venue: ICLR 2025 Poster (2025)
Keywords: Generative Flow Network
Adversarial Training
Vehicle Routing Problem
Primary area: optimization

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.

Published as a conference paper at ICLR 2025
ADVERSARIAL GENERATIVE FLOW NETWORK FOR SOLVING VEHICLE ROUTING PROBLEMS
Ni Zhang', Jingfeng Yang", Zhiguang Cao' Xu Chi
Singapore Management University. Singapore
2 Singapore Institute of Manufacturing Technology (SIMTech).
Agency of Science, Technology and Research (A*STAR), Singapore
changni0128@out cxu@simtech. a-star edu.sq zgcao www.:uwwweedeaeeeeemeee.aee....e
com, Yang.Jingfenge wennggiiimechh..mmmmm att.tttehhaaa............ sg
ABSTRACT
Recent research into solving vehicle routing problems (VRPs) has gained signif- icant 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-bases ap- proaches, i.e., Adversarial Generative Flow Networks (AGFN). This framework integrates the generative flow network (GFlowNet) probabilistic model inher- ently adept at generating diverse solutions (routes)- with complementary model for discriminating (or evaluating) the solutions. These models are trained alter- nately 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, showcas- ing strong generalization capabilities on synthetic and real-world benchmark in- stances. Our code is available at hattps://// //gi/ hiiguuu..... com ZHANG NIIGGFN
INTRODUCTION
The vehicle routing problem (VRP) represents a fundamental and intricate combinatorial optimiza- tion challenge with extensive real-world implications (Toth & Vigo 2014), including supply chain management (Lee al., 2006), last-mile delivery services (Koç al., 2020), and public trans- portation (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 com- plex optimization problems including VRPs. Exact methods, such as branch-and- mand-ound (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. Consequently, heuristic approaches like tabu search (Osman 1993), adaptive large neigh- borhood search (Ropke & Pisinger (0066), and hybrid genetic search (Vidall 2022) have gained prominence for their ability to efficiently produce near-optimal solutions.
While these traditional methods continue to play vital role, recent years have seen the rise of learning-based Neural Combinatorial Optimization (NCO) approaches that can learn solution struction policies directly through supervised or reinforcement learning. without relying on much problem-specific heuristic design. However, these neural constructive solvers encounter substantial challenges concerning scalability. Typically based on Transformer architectures, their training be- comes increasingly difficult as problem sizes grow. Consequently, while these approaches exhibit strong performance small-scale problems, they often struggle to generalize effectively to larger and more complex weal-wrlld instances. To address these generalization issues, recent studies have
corresponding author

---

Published as a conference paper at ICLR 2025
proposed several innovative approaches. Luo al. 2023) introduced the Light Encoder and Heavy Decoder (LEHD) Transformer- model via supervised learning, which enhances the model's generalization abiliity. Xin et al. (2022) proposed to enhance the generalization by generating adver- sarial instance distributions specifically designed to be challenging for neural constructive models to solve. However, both methods still rely on the existing Transformer-basee architecture, which remains difficult to be trained directly on (relatively) large instances due to limited device memory.
In this paper, we aim develop new constructive neural solver that does not rely on the Trans- former architecture. Inspired by recent advancements in Generative Flow Networks (GFlowNets) (Bengio et al., 202T, |023] Zhang et al. 2024) for solving COPs, we propose a novel GFlowNet- based neural VRP solver with adversarial training. Specifically, we leverage the GFlowNet to act as a generator, with the objective of constructing diverse solutions using a forward sampling policy, and discriminative network classifier to evaluate the quality of the generated solutions. The GelowNet and the discriminative network are trained alternately in an adversarial manner. In particular, the GFlowNet is trained by minimizing the trajectory balance objective function (Malkin et al. 2022) while the discriminative classifier is trained to distinguish between the original solutions produced by the GFlowNet and the enhanced solutions obtained through local search. This iterative process enables the GFlowNet to progressively generate higher-quality solutions based on feedback from the discriminator. Moreover, to further leverage the inherent diversity of GelowNet, we propose hybrid decoding method that combines greedy and sampling schemes to construct the routes more effectively. In summary, our contributions are outlined as follows:
We propose a constructive Adversarial Generative Flow Networks (AGFN) framework for solving vehicle routing problems including CVRP and TSP in an end-to-end manner.
We introduce simple yet effective hybrid decoding method that significantly improves the solution quality with a modest increases in inference time.
We perform comprehensive evaluation of our AGFN, and experimental results on both synthetic and benchmark instances confirm its competitiveness against traditional and neu- ral baselines, with effective generalization varying problem sizes and distributions.
2 RELATED WORKS
Neural Solvers for VRPs. The literature on neural solvers for vehicle routing problems (VRPs) can be broadly categorized into two main approaches: (I) the construction-basse method, and (2) the improvement-baseee method. Kool et al. (2019) first introduced an Attention Model (AM) using a Transformer architecture to solve VRPs. The Policy Optimization with Multiple Optima (POMO) proposed by Kwon et al. (2020) further enhanced the AM model by employing a more advanced learning and inference strategy that leverages multiple optimal policies. Building upon AM and POMO, numerous other construction-based solvers have been developed (Kwon et al.) 2021; Li
et al. 2021a| Xin et al. 2020 2021a Chalumeau et al. 2023 Luo et al.) 2023). Compared to tradi- tional handerafted heuristics, these neural solvers employing Transformer architectures can generate solutions quickly. However, these methods often face scalability challenges due to the quadratic complexity of the self-attention mechanism, which makes them resource-intensive for training and limits their generalizability to large problem instances. On the other hand, improvement- neural solvers iteratively refine solutions by combining with traditional heuristic search algorithms, such as beam search (Choo et al. (0022), ant colony optimization (Ye et al. 2024), local search (Hud- son et al.) 2022), and dynamic programming (Kool et al. 2022). Other notable works include Li
et al. (2018); Chen & Tian (2019): Lu et al. (2019); Hottung et al. (202T). Generally, improvement-
based methods can produce superior results when given additional inference time compared their
construction-based counterparts, but also suffer from scalability issue.
GFlowNets for Combinatorial Optimization. Gelow (Bengio et al., 2021) are probabilistic models designed to generate diverse solutions (structures or sequences) by modeling distribu- tion proportional to a specified reward function. The first notable application of GFlowNets was in molecular design for drug discovery, problem often approached as black-box optimization challenge. Very recent studies have applied GFlowNets to various combinatorial optimization prob- lems (COPs), such the maximum independent set (Zhang et al., 2023), job scheduling (Zhang jet al.),, and vehicle routing problems (Kim et al, 2024b), due to their strong capability to effec- tively explore vast, discrete solution spaces while balancing exploration and exploitation. While
2

---

Published as a conference paper at ICLR 2025
GFlowNet is highly capable of generating diverse solutions, it often results in over-exploration, leading to being trapped in numerous locally optimal solutions with low-reward. To overcome this issue, Kim et al. 2023) proposed local search GFlowNets (LS-GFN) to enhance the training ef- fectiveness by encouraging the exploitation of high-rewarded solution spaces. Similarly, Kim et al.) (2024b) integrated GelowNets with ant colony optimization, using local search operator manage the trade-off between exploration and exploitation in solving combinatorial optimization problems.
To the best of our knowledge, the most closely related work utilizing GelowNet for solving VRPs is Kim et al. (2024b), where GFlowNet is trained to learn a constructive policy that provides an informed prior distribution over the edges of routes, guiding the search of the ant colony optimization (ACO). In contrast, our proposed framework enables GFlowNet to directly generate high-quality solutions, without relying on additional heuristic algorithms like ACO during inference.
ADVERSARIAL GFLOWNET
One of the distinctive features of GFlowNet, compared to traditional models for learning to con- struct solutions, is its ability to generate diverse range of solutions-not only optimal ones but also suboptimal and even inferior ones. Previous research has primarily focused on training models to produce highly diverse solutions by incorporating diversity reward functions and other techniques (Nica et al. 2022, Jain et al. 2022). However, there has been relatively little exploration of how the multiple solutions generated by GFlowNet during training can be utilized enhance performance beyond merely increasing diversity. In solving COPs with GFlowNet, most existing studies have em- phasized high-reward solutions while paying insufficient attention to low-reward ones (Zhang al., 2023 Shen et al. 2023 Kim et al.) [023 2024b a) to avoid over-exploration. This imbalance, how- ever, can cause certain edges in the graph of a VRP instance be overestimated by the Get, increasing the risk of local optima traps, which ultimately affects the overall performance.
To address this issue, we propose Adversarial GFlowNet (AGFN) for solving VRPs. It leverages the inherent diversity brought by GelowNet and incorporates adversarial training to evaluate the quality of the generated solutions, further balaneing exploration and exploitation. With the adversarial scoring mechanism, provide more nuanced feedback to GFlowNet, which refines the training process. This approach directs the model to conduct a more precise evaluation of each edge while promoting balanced representation of the entire graph for a VRP instance, thus enhancing its overall performance and generalization capabilities. Consequently, AGFN not only preserves the desired diversity brought by GFlowNet but also systematically integrates it into the optimization process. To facilitate better understanding of our AGEN framework, we include section that provides the preliminaries of GelowNet in the Appendix A
3.1 GENERATOR
In the GFlowNet based generator, to reduce the computational complexity, the model employs sparsification technique the input instance. Taking CVRP an example, we use graph (V,E) to represent it, where V (Vo, uI,..., J denotes the locations of all nodes, with Vo representing the depot and {ur l representing customers. The set & includes each edge esja associated with a travel cost Cjj (e.g., distance). Drawing inspiration from NeuroLKH (Xin et al. 2021b), we acknowledge that handling a fully connected graph for large-scale VRP instances is com- putationally prohibitive. To overcome this challenge, the underlying graph is reformulated where each node is constrained to retain only k of its shortest outgoing edges. In doing so, it helps reduce the computational burden while preserving the core structural features, allowing the method to scale effectively to larger problem sizes. The resulting sparse graph G", consisting of the node set V and the sparse edge set E", is then encoded into sigher-dimensional space by linearly projecting the node coordinates x, E 2 and edge distances x E into node feature vectors hς E Rd and edge feature vectors e,, E IR for V and (i.j) e E., where d is the feature dimension. The selection probabilities for each edge are then computed using a Graph Neural Network (GNN) model. The I+1 based on the features from the tt GNN updates the node features h/#1 and the edge features e
layer, hy and e/y respectively. The GNN operates as follows:
3

---

Published as a conference paper at ICLR 2025
h+1 <- h/+ ACT(BN(U'L) + (oees o v'hj)),, 1+1 + bi + ACT((N((P' e' Q'h + R'h,)).
(2)
Here, U Vi, Q', R' Rdxd trainable parameters, ACT denotes the activation function, BN stands for batch normalization, AJEN' represents the aggregation operation over the neighbors of node i, is the sigmoid function, and @ indicates the Hadamard product. The activation function (ACT) used for all layers is SiLU (Elrwing et al. 2018), while the aggregation function A is defined as mean pooling. To produce the edge probability distribution (heatmap) 17(9,, 009".0gemeren generator) using GFlowNet, the node and edge embeddings from the final layer are passed through a fully connected multi-layer perceptron (MLP), where SiLUU is applied as the activation function for all layers except the last one, which employs a sigmoid function to yield normalized outputs.
Note that, the GNN used here efficiently handles the complex relationship between node and edge, and its low computational complexity makes our GFlowNet based model more effective than the Transformer one. Furthermore, this GNN has fewer parameters compared to the classic GCN (Joshi et al. 2020), allowing it to be directly trained on large problems. Later, multiple paths, represented as 7 To: Ti....: JK }, are generated through sampling and evaluated by a discriminator to obtain scores. These scores are then incorporated into the reward function follows,
K
- log R(Tx) = (1 - S((T)) + R(TE)
Σ R(T.).
(3)
K
where R(T,) represents the total length of the path tr and a lower R value indicates a higher path quality (since we aim minimize the route length in VRPs); The scores, S E [0, 1]. reflect the discriminator's ' assessment of path quality, with values closer to indicating higher quality paths and values approaching 0 indicating lower quality paths. As training progresses, the quality of the generated paths steadily improves, the R distribution shifts towards smaller values, and the deviation of each solution's length from the mean becomes increasingly smaller. Furthermore, the solutions align more closely with the discriminator's decision criteria. Consequently, - log R(TT) will tend to approach smaller values.
Integrating the score as a factor into the reward function guides the generator to better utilize solu- tions of varying quality to train the model. Additionally, using the score regulator also enables the model to account for suboptimal solutions while avoiding excessive bias toward the current op- timal solution, thereby enhancing the exploration capability for global optima. Finally, the gradient loss, which aims at optimizing the training process of the GFlowNet is described as follows,
1 K
K
Zo * (Ti Ogenerator R(Tx) * (TT generator)
CT:(T: generator
log
(4)
Here, (T< 0 generator) in Eq. represents the forward probability of the trajectory т = (sp > 81 + + sn) This probability is calculated using the edge probabilities PP which is selected from heatmap n(g generator)) defined as follows,
PF(TE; Ogenerator)
II (icellssi::geeerattto
(5)
Po(TE; O Ogenerator) in Eq. represents the backward probability of the trajectory The calculated from the instance, defined as follows,
n
PT(Te; O generator)
II PB P7(ss-1l820 ggenerator)
(6)
Generally, the GFlowNet focuses accurately evaluating the edge probabilities during training for solving VRPs. This enables the generator to more precisely assess edge probabilities and capture more nuanced graph features, leading to deeper understanding of the underlying structure. As result, the generator can better handle complex relationships within the graph, which significantly enhances its generalization across wider range of tasks and diverse graph structures.
4

---

Published as a conference paper at ICLR 2025
Input Instance
Casonar
Cartarte
Catarr
GRownee with prenne
Local Search
with Patrrinkaie
(7/4)
in (4,57)
Original Soluttone
Sernch Sonthene
Genarabor with ose Furction:
Discriminator with loss Purction: Cit (eaesesedee
Adiersarial with Thenttors
Figure 1: Illustration for the Overall Framework of Adversarial Generative Flow Network (AGFN).
3.2 DISCRIMINATOR
In the discriminator, the model receives two types of paths as input: the original paths Tyatse (To: TI..... ... JN), created directly by the generator and labeled as "false", and the paths Terue (To. .1..... JMJ. which are enhanced or optimized by local search and labeled as "true". The discriminator then generates scores S for these paths and compares the differences between the scores and their corresponding labels. For Tirue, the training objective is to bring the scores closer I, while for Taalses the goal is push the scores closer to O. The loss function described as:
L(T discrimenntor
1 M+N
Σ (1-
S(Tx) TRET
Σ
Tea ETore
By doing so, the discriminator learns to differentiate between the raw generated paths and the op- timized paths of higher quality, thereby enhancing its capability evaluate the generator's output. This design not only allows the discriminator to more accurately assess the quality of the generated paths but also provides more informative feedback the generator, leading further improvement in the model's 's overall performance.
3.3 OVERALL FRAMEWORK
The overall framework, depicted Figure operates as closed-loop system for adversarial learn- ing. The generator iteratively produces new solutions based heatmap generated from the current model parameters and input instances, which are then evaluated by the discriminator, The discrimi- nator assigns quality scores that integrated into the generator's 's loss function, serving feedback for backpropagation. Meanwhile, the discriminator continuously learns to distinguish subtle differ- ences between the generated paths and the optimized paths.
The discriminator's 's score not only evaluates the quality of each path solution in path set T but also assists the generator in exploring the global optimum within the solution space. At the beginning of training, the generated paths exhibit broad spectrum of quality, ranging from high-quality to suboptimal and lower-quality solutions. By considering this diverse set of paths, the model converges more rapidly. As training progresses, the generator refines its ability to produce higher- quality paths, guided by the discriminator's feedback. This mechanism helps the generator focus on generating paths that increasingly align with the target distribution. The generator updates its internal parameters by minimizing the loss, further enhances its capability to produce optimal paths.
Remarks: In the discriminator, we employ a local search to refine the path by iteratively performing destruction, reconstruction, and top-K selection over fixed number of rounds. it worth noting that the local search used in the discriminator is generic, and, as shown in our subsequent experiments, alternative local search methods perform equally well. Conversely, during inference, the local search unnecessary, only the generator is used to construct the route.
3.4
HYBRID DECODING
To solve vehicle routing problems like the CVRP, traditional neural models (Li ct al. 2021b Kwon
al. 2020 Hu et al. 2020) Nazari et al. 2018 often converge to locally optimal solutions by
5

---

Published as a conference paper at ICLR 2025
assigning disproportionately high selection probabilities to the optimal edges while evaluating sub- optimal edges with low probabilities. Such imbalance causes these models to predominantly rely on greedy strategies for path generation, the high evaluation bias towards optimal edges restricts the exploration of alternative paths. Hence, incorporating sampling methods may not significantly improve the performance, they lack the flexibility effectively explore broader solution space.
However, GFlowNet (Bengio et al., 2023) offers a more balanced probabilistic evaluation, enabling nuanced representation of the solution space by appropriately considering both optimal and sub- optimal edges during path generation. To fully exploit this capability, we further propose a hy- brid decoding method, which combines the original sampling with greedy strategies. Specifically, GFlowNet, acting as the generator, constructs each path in path set T by selecting the next node, 81+1, each step with a probability P. This probability used to sample the edge distribution probability Pr(s++1|s: 81; generator)) derived from the heatmap and representing the likelihood of transitioning from node 8, to St+1- With P serving as a hyperparameter, our model also selects the next node based on the distribution using greedy strategy with probability of 1 P during inference. The selection process is stated as follows,
8, with probability P with probability - P
S++1
(8)
where 8t denotes the current node in the trajectory, 8 ~ PF(8241185 I generator). and 8* arg max, PF O ggeeerator). This means that with probability P the next node St+1 chosen by sampling from the edge distribution probability PF($t+1|s:) O @enerraoor) while with probability 1 P. the next node st-1 is selected based on the highest edge probability. On the one hand, the sampling mechanism enables the model to explore wider range of possible paths, increasing so- lution diversity. On the other hand, the greedy selection ensures path quality and guides the model toward better solutions. Building on the balanced and naunced probabilistic evaluation inherent to GFlowNet, this integration allows our model to effectively utilize the strengths of both schemes, which not only expands the search space but also enhances its ability to discover higher-quality solutions by avoiding premature convergence to suboptimal regions.
4 EXPERIMENTS
In this section, we first conduct extensive experiments the CVRP of various sizes to demonstrate the effectiveness of our AGFN against the traditional and neural baseline methods. Additionally, to highlight the generality of our AGFN, we also apply to solving the TSP.
Dataset: Following previous works (Kim et al. 2024b Kwon et al. 2020), we perform CVRP experiments using synthetic datasets for both training and testing. Each CVRP instance consists of a set of customer nodes, a single depot node, and a vehicle with a fixed capacity C. The customer nodes are characterized by their positions (2D coordinates) and demands, while the depot is defined solely by its location. To generate a random CVRP instance, the coordinates of both customers and the depot are sampled from unit square [0, 1j2, and the customer demands are drawn from predefined uniform distribution [a, bj. In our experiments, we set = 1 and b = 9, with fixed vehicle capacity of C 50 for all problem sizes: 200, 500, and 000 customers. Each synthetic test dataset, corresponding to 200, 500, and 1, 000 nodes, contains 128 instances.
The number of directed edges, k. originating from single node in the sparse edge set, |8"), is set to /V//4. For training the model, we only employ the sampling decoding (without greedy selection) for route generation, with the number of sampled routes per instance, N, set to 20. The ratio of training rounds between the generator and the discriminator is maintained at 4: 1. During testing. hybrid decoding is used for route generation, with A set to 100 and the P in Eq. set to 0.05 (see Appendix [B for more details the selection of P). All experiments were conducted on a server equipped with an NVIDIA Tesla V100-32G GPU and an Intel Xeon Gold 6148 CPU. Our code is available wtthttss:/// http:://ggttttuucco
Hyperparameters:
ZHANG-NT/AAN

---

Published as a conference paper at ICLR 2025
Overall performance comparison on the synthetic CVRP dataset. The 'Obj.' indicates the average total travel distance, while "Time' denotes the average time to solve single instance.
Table I:
[V] = 200
V 500
[V] 1000 Gap (%)
Method
Obj-
Gap (5)
Time
Obj
Gap (%)
Time (s)
Obj.
Time (8)
LKH-3(100)
28.833135
1.65
66. 16.902511
5.86
131.795858
19.30
LKH-3
28. 27.278838
-1.92
10.72
64. 14.387969
-3.76
23:55
124.575469
-5,48
66.57
LKH-3(10000)
28.041563
-2.75
59.81
63.320078
-5.35
233.72
120.53
-8.55
433.90
29.178707
1.20
0.33
79.785673
19.26
0.88
192.78563
46.28
3.20
POMO
29,424647
2.05
0.26
83. 83,079016
24.19
0.62
233.093524
76.86
1.62
NeuOpt
38. 478677
33.45
17.34
187 887.818 12195
180.73
39.41
GANCO
29.978K34
71.258016
6.51
145 142.40277
10.32
4.88
AGFN-100
31.260145
8.41
0.17
71.051099
6,20
0.45
133.96624
1.65
0.72
ACO
71.5753186
143.24
3.50
187. 187.616745
179.88
11.36
383. 960999
191.11
25,08
GFACS
45.357657
57.31
4.82
76.771554
14.75
13.27
158. 1658
20.26
28.52
AGFN-200
30,35164
5.27
0.17
99.599289
4.03
0,46
132.477417
0.52
0.72
AGEN-500
31.826736
10.38
0.17
69.375366
3,70
0.46
129.017488
-2.11
0.72
AGFN-1000
32.235001
11.80
0.17
69.8 69.873100
4.44
0.46
129.624237
-1.65
0.73
4.1 COMPARATIVE STUDY ON CVRP
4.1.1 COMPARISON OF MODEL TRAINING AT THE SAME SCALE
Baselines: We use LKH-3 (Helsgaun 2000), heuristic solver, POMO (Kwon et al. 2020 a classical construction model, NeuOpt (Ma et al. 2024), recent improvement model, and GANCO (Xin et al., 2022). which combines adversarial training and POMO, as baselines for comparing the model trained at the same scale. All neural models, including POMO, NeuOpt, GANCO, and ours, were trained on synthetic instances with 100 nodes (since those baselines are hard to train on more than 100 nodes), and tested on 200, 500, and 1,000 nodes. For heuristic baseline LKH-3, we provide the results on 100, 1,000, 10,000 iterations, where the ones with 100 iterations are used to calculate the gaps for all other methods. Additionally, AGFN was also trained on 200, 500, and 1,000 nodes for further evaluation.
Result: As shown in the upper half of Table T. our algorithm significantly outperforms POMO, NeuOpt, and GANCO in terms of computation time, For instances with 200 nodes, our method reduces computation time by 34.62%, 99.01%, and 66.00%, respectively, compared to POMO, NeuOpt, and GANCO. For 500 nodes, the reductions are 27.22%. 98 86%, and 65.65%. On 1,000- node instances, our method achieves reduction of 55.55% and 85.25% in computation time com- pared to POMO and GANCO. Importantly, while NeuOpt demonstrates much longer computational times, both POMO and GANCO-althor between runtime and solution quality that AGFN offers. For example, AGFN's computation time on instances of 1,000 nodes is only 0.72 seconds, compared to GANCO's s 4.88 seconds and POMO's 1.62 seconds. This highlights AGFN's advantage in scaling to larger instances while maintaining efficiency. In terms of objective value, our model performs 16% better than NeuOpt on 200- node instances, but is 7.13% and 4.27% worse than POMO( and GANCO, respectively. On 500-node instances, our model outperforms POMO(*8), NeuOpt, and GANCO by 8.90%, 67.17% and 0.29%. For 1, 000 nodes, our model shows 30.51% and 7.86% improvement over POMO(*8) and GANCO, respectively. Although the generalization of our model trained on 100-node instances slightly limited for 200-node cases, excels both 500 and 000 nodes, surpassing POMO, NeuOpt, and GANCO in terms of both computation time and objective value.
computationally efficient Canciott-cannot achieve the balance
4.1.2 COMPARISON ON TRAINING SIZES
Baselines: For comparisons across different training sizes, include the heuristic method ACO and the GFACS model (Kim et al.) 2024b), which combines GFlowNet with ACO. To ensure a fair comparison of route generation capabilities between AGFN and other neural baselines, none of them in our experiments utilize local search to further refine the solution after the route is generated.
Result: We evaluated AGEN instances with 200, 500, and 1, 000 nodes, which are trained on datasets of corresponding sizes. The results are presented in the lower half of Table [ In terms of computation time, our model surpasses ACO by 95.1 14%, 95.95%, and 97.09%. and GFACS by
7

---

Published as a conference paper at ICLR 2025
96.47%. 96.53%, and 97.44% 200, 500, and 1000 nodes, respectively. This substantial duction in runtime demonstrates the scalability of AGFN and its ability to efficiently handle larger problem instances without requiring additional heuristic search refinements during inference. Re- garding objective values, our model shows improvements of 57.59% and 33.08% over ACO and GFACS on 200 nodes, 62.95% and 9.63% on 500 nodes, and 66.21% % and 18.46% on 1, 000 nodes. Overall, AGFN significantly outperforms both ACO and GFACS in terms of computation time and objective value all three tested scales of the training ones. These results highlight the desirable generalization capability of our model across various problem sizes, along with its computational efficiency, making it potentially suitable for practical applications involving large-scale VRPs.
4.2 EXPERIMENTS ON OTHER ROUTING PROBLEM
Table 2: Overall performance comparison on the synthetic TSP dataset. The 'Obj.' indicates the av- crage total travel distance, while 'Time' denotes the average time required to solve a single instance.
[V| 200
500
1000 [V]
Method
Obj.
Gap (%)
Time (6)
Obj.
Gup (%)
Time (8)
Obj.
Gap (%)
Time (s)
LKH-3(100)
10.719512
0,57
16.547770
1.90
23.123401
4.42
LKH-3(1000
.0.88
164364766
-0.99
7.19
22.845391
-1.20
32.81
LKH-3(1000))
10.626953
-0,86
40.19
16. 16.304531
-1.47
78.43
22,678438
-1.92
255.05
POMO(*8)
10.894811
1.64
0.225
20.310184
22.74
0.59
32,783411
41.78
3.47
POMO
10.969289
2.33
20.753397
25.42
0.42
33,237161
43.74
1.04
NeuOpt
190998
23.05
6.43
137 858551
733.09
14.63
325. 764008
1308.81 81
27.96
GANCO
11.281924
5.25
0,12
19.361128
17.00
0.38
29.9 989326
29.69
0.90
AGEN-100
11.84754
10.52
0.10
19.076220
15.28
0.30
27. 17.144802
17.39
0.75
ACO
48,3356921
350,91
1.82
151 4268301
815.09
5,99
317 4939855
1273.04
13.48
GFACS
13.448596
25.46
3.21
23.301532
40.81
9.86
36.784744
59.08
21.68
AGFN-200
11,923518
11.23
0.10
18.663813
12.78
0.30
26.572329
14.92
0.77
AGEN-500 121921
13.08
0.10
18.8 8555522
13.95
0.30
26.529234
14.73
0.75
AGEN-1000
12.353358
15.24
0.10
19.301237
16.64
27.144802
17.39
0.75
We also evaluate the performance of AGFN on the Traveling Salesman Problem (TSP). Similar to the CVRP experiments, et al. 2024). and GANCO (Xin et al. 2022) as baselines for model training with 100 nodes, and ACO and GFACS (Kim al.) 2024b) as baselines for comparisons across different training sizes. The test datasets consist of synthetic instances at scales of 200, 500, and 1, 000 nodes, with each dataset containing 128 TSP instances. Each instance comprises set of nodes represented by 2D coordinates, which are randomly sampled from a unit square [0, 1)?.
LKH-3 (Helsgaun 2000). POMO (Kwon et al. 2020). NeuOpt (Mal
As shown in the upper half of Table [] AGFN achieves significant reductions in computation time and improvements in objective value compared to POMO, NeuOpt, and GANCO on 500-node in- stances. Specifically, it reduces computation time by 49.15%. 97 97.95%, and 11. 11,44, while improv- ing the objective value by 8.08%, 86.16%, and 1.47%, respectively. For 1, 000-node instances, our model further reduces computation time by 27. 27.88%, 97. 97.32%, and 16.67%, and enhances the ob- jective value by 18.33%, 99.87%, and 9.49% compared to the baselines. This indicates that our model performs better than POMO, NeuOpt, and GANCO in both computation time and objective value at larger scales (500 and 000 nodes). However, for 200-node instances, while model achieves time reductions of 23.08%, 98.44%, and 16.67% slightly underperforms POMO and GANCO in terms of objective value. When comparing the performance of the three training sizes, as shown in the lower half of Table []] AGFN consistently outperforms both ACO and GFACS. On 200 nodes, it reduces computation time by 94.51% and 96.88%, and improves the objective value by 75.33% and 11.34%, respectively. On 500 nodes, the reductions in computation time are 94.99% and 96.96%, with objective value improvements of 87.55% and 19.08%. On 1, 000 nodes, our model reduces computation time by 94.43% and 96.54%, and improves the objective value by 91. 01.45% and 26.21%. Overall, AGFN demonstrates superior performance compared to ACO and GFACS in computation time and objective value on all the three tested scales of the training ones.
4.3 GENERALIZATION ANALYSIS
We assess the generalization performance of models trained on 200, 500, and 1, 000 nodes, and tested sizes different from the training one on synthetic datasets. Additionally, we also evaluate
8

---

Published as a conference paper at ICLR 2025
the performance of AGEN trained synthetic datasets with 100 nodes, well the POMO and GFACS models, on the CVRPLib (Uchoa et al. 2017) and TSPLib (Reinelt 1991) benchmarks.
The results of cross-size evaluation synthetic datasets also included in the lower half of Table Tand T Models trained on respective sizes demonstrate strong generalization across different scales, without significant performance degradation. For real-world benchmark datasets, detailed results are shown in Table 3 On TSPLib, our model achieves an improvement in performance by 15.10% and 36.96% while reducing computation time by 82.61% 61% and 77.78% compared to POMO and GFACS, respectively. On CVRPLib, our model shows a 12.61 % and 39.34% enhancement in performance and 73.06% and 89.64% reduction in computation time. Overall, AGFN significantly outperforms POMO and GFACS across the TSPLib and CVRPLib datasets. In the Appendix [C] we further show that AGEN substantially outperforms other construction-uee baaod neural methods on much larger instances with to 10,000 nodes.
Table 3: Overall performance comparison on the CVRPLib and TSPLib. The 'Obj.' indicates the average total travel distance, while 'Time' denotes the average time solve single instance.
CVRPLib
Optimal
AGFN-100
POMO("8)
GFACS
TSPLib
Optimal
AGEN-100
POMO(*8)
GFACS
Obj. Time (6)
63107.01
74437,39
85178.56
122718.46
Obj.
32488.72
41375.67
48738.61
65628.95
0.58
2.19
5.60
Time (s)
0.04
0.23
0.18
Gap (%)
17.95
34.97
94.46
Gap
27.36
50.02
102.01
4.4
ABLATION STUDY
CVRP200
CVRP500
CVRP1000
Samale Greety
Goo (96)
Gap (96)
Gri (96)
Hybrid
100
203
510
1000
405
500
1000
150
203
300
1000
Model Size
Model Size
Modal Sire
TSP200
TSP500
TSP1000
60
30
50-
20
10
Model Size
Model Size
Model Size
Figure 2: Comparison of the performance of greedy, sampling, and hybrid sampling strategies.
Hybrid decoding. We demonstrate the effectiveness of the hybrid decoding algorithm in our AGFN by comparing its performance against the pure sampling and greedy approaches. The results, pre- sented in Figure 2] highlight the comparative advantages of the hybrid strategy across various sce- narios. As shown, our hybrid method consistently achieves lower gap percentages than the other two methods across different problems and model sizes. These comparisons reveal that the hybrid method not only excels in generalization but also adapts more effectively to datasets of varying scales. Notably, in cases like CVRP1000 and TSP1000, the hybrid method significantly reduces the performance gap, demonstrating its robustness and versatility. These findings confirm that our hybrid models, trained on different node counts, outperform the individual sampling and greedy strategies, particularly when tested large-scale instances.
Local search in discriminator. To train the discriminator in our AGFN, we employ local search to generate samples labeled "true" for the diseriminator. Here, investigate the impacts of 1) using alternative methods for generating such true samples, and 2) removing the adversarial component. As illustrated for the scenario of CVRP200 in Figure 3 exhibit the effects of using our local

---

Published as a conference paper at ICLR 2025
search against the LKH (Lin- Meeemighan-Helgeeee Helsgaun (2000)) heuristic generate true sam- ples during training. The results indicate that these two different search methods in the discriminator have almost equal impact the performance. Regardless of the search method used, the genera- tor converges in a similar yet satisfactory manner, indicating the robustness of the training process. Furthermore, we observe that incorporating the adversarial component into our AGFN significantly accelerates the convergence of the training curve and leads to superior overall performance. This evident from the sharper decline in the average objective value when the adversarial component is included, compared to training without it. Note that, without the adversarial scheme, our model can viewed as a simplified version of GFACS. The faster convergence and better results high- light the effectiveness of integrating adversarial training in our AGFN, making it a powerful tool for enhancing solution quality complex optimization tasks such as CVRP.
55
CVRP200 local
CVRP200 _u0
WWWP2200_on-adveerte
08.
45
Avg.
40
30
500
1000
1500
2500
evaluation
Figure Training Performance Comparison of our model with different settings.
5 CONCLUSION
In this paper, we propose AGFN, a novel constructive framework for solving vehicle routing prob- lems (VRPs). By leveraging GelowNet and an adversarial training strategy, our approach provides high-quality solutions with strong generalization capabilities as a purely constructive neural solver. Extensive experimental comparisons with other representative Transformer- improvement methods, as well existing GFlowNet-based solvers, on both synthetic and real-world instances demonstrate the promise of AGFN in solving VRPs. We believe that AGFN can provide valuable insights and pave the way for further exploration of GelowNets in solving more VRP vari- ants and other combinatorial optimization problems. A limitation of AGFN that its performance heavily relies the generator's ability to produce diverse, high-quality solutions, which may count for its slightly lower test performance on 200-node CVRP and TSP instances. A potential future direction is to incorporate more advanced graph neural network (GNN) architectures with improved representation capability for VRPs, and more ad advanced adversarial training schemes. We will also compare AGFN against a broader range of robust neural VRP solvers on larger instances.
constructive and
LEKNOWLEDGEMENT
This work is supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No. MISG3-RP-2022-0311 and the Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier I grant.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Cynthia Barnhart, Ellis L Johnson, George L Nemhauser, Martin WP Savelsbergh, and Pamela H Vance. Branch-and-price Column generation for solving huge integer programs. Operations research, 46(3):316-38) 1-9999 1998.
Emmanuel Bengio, Moksh Jain, Maksym Korablyov, Doina Precup, and Yoshua Bengio. Flow network based generative models for non-iterative diverse candidate generation. Advances in Neural Information Processing Systems, 34:27381-27394, 2021.
Yoshua Bengio, Salem Lahlou, Tristan Deleu, Edward J Hu, Mo Tiwari, and Emmanuel Bengio. Gflownet foundations. The Journal of Machine Learning Research, 24(1):10006-100) 10060, 2023.
Felix Chalumeau, Shikha Surana, Clément Bonnet, Nathan Grinsztajn, Arnu Pretorius, Alexandre Laterre, and Tom Barrett. Combinatorial optimization with policy adaptation using latent space search. Advances in Neural Information Processing Systems, 36:7947-7959, 2023.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimiza- tion, Advances in neural information processing systems, 32, 2019.
Jinho Choo, Yeong-Dac Kwon, Jihoon Kim, Jeongwoo Jac, André Hottung, Kevin Tiemny, and Youngjune Gwon. Simulation-guided beam search for neural combinatorial optimization. Ad- vances in Neural Information P Processing Systems, 35:8760-87777 2022.
Stefan Elfwing, Eiji Uchibe, and Kenji Doya. Siggoid-weighted linear units for neural network function approximation in reinforcement learning. Neural networks, 107:3-11, 2018.
Stephan Hassold and Avishai Avi Ceder. Public transport vehicle scheduling featuring multiple vehicle types. Transportation Research Part B: Methodological, 67:129-143, 2014.
Keld Helsgaun. An effective implementation of the lin-kernighan traveling salesman heuristic. European journaal of operational research, 126(1): 1066))00013,,, 2000.
André Hottung, Bhanu Bhandari. and Kevin Tiemeyy Learning latent search space for routing prob- lems using variational autoencoders. In International Conference on Learning Representations, 2021.
Yujiao Hu, Yuan Yao, and Wee Sun Lee. A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs. Knowledge-Baud Systems, 204:10624: 106244, 2020.
Benjamin Hudson, Qingbiao Li. Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. In The Tenth International Conference Learning Representattinns ICLR 2022, Viriual Event, April 25-29, 2022. OpenReview.net, ew net. wort/foootm/eeeeeeooo www.mmmdadaaraeee.e..mmmmm 92oRosBTg
2022. httptttt////peeeee
Moksh Jain, Emmanuel Bengio, Alex Hernandez-Gareia, Jarrid Rector-Brooks, Bonaventure FP Dossou, Chanakya Ajit Ekbote, Jie Fu, Tianyu Zhang, Michael Kilgour, Dinghuai Zhang, et al. Biological sequence design with gflownets. In International Conference on Machine Learning, pp. 9786-9801. PMLR, 2022.
Chaitanya K Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learn- ing the travelling salesperson problem requires rethinking generalization. arXiv preprint arXiv:2006. 20XY::2006.07044. 07054, 2020.
Hyeonah Kim. Minsu Kim, Sanghyeok Choi, and Jinkyoo Park. Cenetic-guides gflownets: Advanc- ing in practical molecular optimization benchmark. arXiv preprint arXiv:2402.05961, 2024a.
Minsu Kim, Taeyoung Yun, Emmanuel Bengio, Dinghuai Zhang, Yoshua Bengio, Sungsoo Ahn, and Jinkyoo Park. Local search gflownets. arXiv preprint arXiv:2310.02710, 2023.
Minsu Kim, Sanghyeok Choi, Jiwoo Son, Hyeonah Kim, Jinkyoo Park, and Yoshua Ben- gio. Ant colony sampling with gflownets for combinatorial optimization. arXiv preprint arXiv:2403.07041, 2024b.
11

---

Published as a conference paper at ICLR 2025
Çağr Kog, Gilbert Laporte, and ilknur Tükenmez. A review of vehicle routing with simultaneous pickup and delivery. Computers & Operations Research, 122:104987, 2020.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL http:::///pperevieeeee net www.:eettorrum// forum? did= SyxBFsRqYn
Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic pro- gramming for vehicle routing problems. In International conference integration of constraint programming, artificial intelligence, and operations research, pp. 190-213. Springer, 2022.
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21 188-188-111 88181188 2020.
Yeong-Dat Kwon, Jinho Choo, I1joo Yoon, Minah Park, Duwon Park, and Youngjune Gwon, Ma- trix encoding networks for neural combinatorial optimization. Advances in Neural Information Processing Systems, 34:5138-5144 2021.
Eugene L Lawler and David E Wood. Branch-and aaahh--nd--uuudd methods: A survey. Operations research, 14(4):699-719, 1966.
Young Hae Lee, Jung Woo Jung, and Kyong Min Lee. Vehicle routing scheduling for cross-docking in the supply chain. Computers & industrial engineering, 51(2):447-266, 2006.
Jingwen Li, Liang Xin, Zhiguang Cao, Andrew Lim, Wen Song, and Jie Zhang. Heterogencous attentions for solving pickup and delivery problem via deep reinforcement learning. IEEE Trans- actions on Intelligent Transportation Systems, 23(3):2306 2315, 2021a.
Kaiwen Li, Tao Zhang, Rui Wang, Yuheng Wang. Yi Han, and Ling Wang. Deep reinforcement learning for combinatorial optimization: Covering salesman problems. IEEE transactions cybernetics, 52(12):13142-13155 2021b.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. Advances neural information processing systems, 31, 2018.
Shuchang Liu, Qingpeng Cai, Zhankui He, Bowen Sun, Julian McAuley, Dong Zheng, Peng Jiang, and Kun Gai. Generative flow network for listwise recommendation. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1524-1534, 2023.
Hao Lu, Xingwen Zhang, and Shuang Yang. A leaaning-basee based iterative method for solving vehicle routing problems. In International conference on learning representations, 2019.
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. Advances in Neural Information Processing Systems, -8648 2023.
Yining Ma, Zhiguang Cao, and Yeow Meng Chee. Learning to search feasible and infeasible gions of routing problems with flexible neural k-opt. Advances in Neural Information Processing Systems, 36, 2024.
Nikolay Malkin, Moksh Jain, Emmanuel Bengio, Chen Sun, and Yoshua Bengio. Trajectory balance: Improved credit assignment in gflownets. Advances in Neural Information Processing Systems, 35:5955-5967, 2022.
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takáe. Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
Andrei Cristian Nica, Moksh Jain, Emmanuel Bengio, Cheng-Hao Liu, Maksym Korablyov, Michael M Bronstein, and Yoshua Bengio. Evaluating generalization in gflownets for molecule design. In ICIR2022 Machine Learning for Drug Discovery, 2022.
12

---

Published as a conference paper at ICLR 2025
Ibrahim Hassan Osman. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of operations research, 41:421-451, 1993.
Ling Pan, Moksh Jain, Kanika Madan, and Yoshua Bengio. Pre-training and fine-tuning generative flow networks. In The Twelfth International Conference on Learning Representations.
Gerhard Reinelt. Tsplib traveling salesman problem library. ORSA journal on computing, 3(4): 376-384, 1991.
Stefan Ropke and David Pisinger. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation science, 40(4))455-472 2006.
Max W Shen, Emmanuel Bengio, Ehsan Hajiramezanali, Andreas Loukas, Kyunghyun Cho, and Tommaso Biancalani. Towards understanding and improving gflownet training. In International Conference on Machine Learning, pp. 30956-30975. PMLR, 2023.
Mohit Tawarmalani and Nikolaos V Sahinidis. A polyhedral branch-and-cur approach to global optimization. Mathematical programming. 103(2):225 (112),222-29,, 2005.
Paolo Toth and Daniele Vigo. Vehicle routing: problems, methods, and applications. SIAM, 2014.
Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, Thibaut Vidal, and Anand Subramanian. New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3):845-88) 858, 2017.
Thibaut Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap" neigh- borhood. Computers & Operations Research, 140:105643, 2022.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Step-wise deep learning models for solving routing problems. IEEE Transactions Industrial Informatics, 17(7):4811-477 2020.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 12042-12049, 2021a.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Neurolkh: Combining deep learning model with lin lin- seemighan-helsgaan heuristic for solving the traveling salesman problem. Advances in Neural Information Processing Systems, 34:7472-7483 2021b.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Generative adversarial training for neural combinatorial optimization models. 2022.
Haoran Ye, Jiarui Wang. Zhiguang Cao, Helan Liang, and Yong Li. Deepaco: neural-enhanced ant systems for combinatorial optimization. Advances in Neural Information Processing Systems, 36, 2024.
David W Zhang, Corrado Rainone, Markus Peschl, and Roberto Bondesan. Robust scheduling with gflownets. In The Eleventh International Conference on Learning Representations.
Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron C Courville, Yoshua Bengio, and Ling Pan. Let the flows tell: Solving graph combinatorial problems with gflownets. Advances in neural information processing systems, 36:1 1952-11969, 2023.
Dinghuai Zhang, Hanjun Dai. Nikolay Malkin, Aaron C Courville, Yoshua Bengio, and Ling Pan. Let the flows tell: Solving graph combinatorial problems with gflownets. Advances in Neural Information Processing Systems, 36, 2024.
13

---

Published as a conference paper at ICLR 2025
A PRELIMINARIES ON GFLOWNET
GFlowNet (Bengio et al. 2021) is a probabilistic framework designed to generate diverse structures sequences by learning distribution over set of possible states S, which represented as a directed acyclic graph. GetowNets have shown remarkable versatility across various challenging domains, including molecular discovery (Pan et al.), combinatorial optimization (Zhang et al.. 2024), and recommendation systems (Liu et al. 2023). Let 8o denote the initial state. A sequence of states,
(80 + 81 + - 8n). is generated via policy that defines probability distribution over actions at each state. The fundamental concept involves sampling sequences of actions that transition from an initial state so terminal state Sn, with each sequence uniquely corresponding to an object I E X. In the context of VRP, 9; represents the current partial route, covering total of t customers visited, while each x corresponds to a unique, complete route that visits every customer exactly once and returns to the starting point.
The transition from state 8t to its child state $t41 is determined by an action as, sampled from a dis- tribution
referred to as the forward policy, Conversely, the buckward policy, denoted as (8 1e+1), captures the transition probability from child state 8t++1 back its parent state 8t- object X' is defined (x(x) -Eretira Pp(T), where т - x denotes a complete trajectory т terminating at object and Pr(r) represents the forward probability of complete trajectory т. The principal aim of GFlowNet is ensure that this marginal likelihood is proportional to the reward of the generated object while preserving the diversity of sequences: (r(x) x R(x).
The marginal likelihood of sampling
Trajectory Balance (TB) (Malkin et al. 2022) is a widely adopted objective for training GFlowNets, designed to minimize the following loss function:
Zo I Pr(s se
Crb(T:0) = log
R(x) I PB(S S1+1:
The TB objective ensures that the product of forward transition probabilities aligns with the product of backward transition probabilities, thereby promoting consistent flow across all paths leading to the same outcome. The trajectory balance loss, LTB. comprises three key components: the source flow Zo. representing the initial state flow F(s)), which computed as Zo ΣTET F(T); the forward policy PF (F($+41|a 1|6 0); and the backward policy (B(st (1(((55+11:))
B HYPERPARAMETER HYBRID DECODING
As mentioned in Section 3.4 hyperparameter P is used to sample the node with the edge distribution
probability ( St; (eenerator). ). Here, we evaluate the model performance under different value
of P. Based on the results shown in Table 4 and Table 5
We set the hyperparameter P 0.05 to
achieve the highest solution quality.
Table Sensitivity analyses of hyperparameters P in Hybrid Decoding on synthetic CVRP dataset.
P/Node
V 200
Gap(%)
V 500
Gap(%)
V 1000
Gap(%)
LKH-3(100)
28.833135
66.902511
131,795858
0.01
31.555902
9.44
71.622154
7.05
134.074051
1.73
0.03
31.377661
8.83
71.111671
6.29
133.875488
1.58
0.05
31.260145
8.41
71.051109
6.20
133.966240
1.65
0.07
31.363468
8.78
71.092043
6.26
134.133682
1.77
0.10
31.347300
8.72
71.101418
6.28
134.436279
2.00
C GENERALIZATION ANALYSIS ON LARGER INSTANCES
To further evaluate the scalability of AGEN, we conducted experiments using the AGFN model trained on synthetic instances with 100 nodes and tested it larger instances comprising 2,000,
14

---

Published as a conference paper at ICLR 2025
Table 5: Sensitivity analyses of hyperparameters P in Hybrid Decoding on synthetic TSP dataset.
P/Node
V 200
Gap(%)
[V] 500
Gap(%)
[V] 1000
Gap(%)
LKH-3(100)
10.719512
16.547770
23.123401
0.01
11.873071
10.76
19.172634
15.86
27.760757
20.05
0.03
11.854967
10.59
19.140463
15.67
27.882353
20.58
0.05
11.847540
10.52
19.076220
15.28
27.144802
17.39
0.07
11,867495
10.71
19.212893
16.11
27.231346
17.77
0.10
11.898133
11.00
19.295887
16.61
27.562878
19.20
Table 6: Comparative results on much larger synthetic CVRP dataset with up to 10,000 nodes. The 'Obj." indicates the average total travel distance, while 'Time' denotes the average time to solve single instance.
CYRP
I - 2000
[V] - 3000
[V] 3100
[V] - 10000
Obj
Cup (96
Time (5)
Obj.
Cap (56
Time (5)
Okj
Gap (16
Time
Okl.
Gap (%6 Time
1089)
256/631793
234.08 05
363 870625
462.06
AGEN-1000
259.536438
1.13
2.61
369. 9989999996
-3.60
4.03
607.2990827
7.13
1146.165161
14,60
GANCO 100
291.826452
13:71
6.39
GRACS-200
254,539154
10.87
77.44
405, 368347
5,61
139. 31
663 644-988
280 69
POMO-100 100
637.439657
144.49
3.87
1134 976861
193009
7.27
1507, 168600
19.65
1000X
4:1.348147
60:48
8.67
753 698417
91.16
20.33
1456.01 1573
45.
3,000, 5,000, and 10,000 nodes. The 2,000 and 3,000 node scales contain 128 instances each, while the 5,000 and 10,000 node scales contain 64 instances each. For the baseline heuristic LKH-3, we limited its runtime to 30 minutes instance. to time constraints, we were only able to provide LKH-3 results for 1,000 iterations and could not complete 10,000 iterations, as running 10,000 iterations for just 18 instances took more than 24 hours. The results, summarized in Table larger problem sizes, main-
demonstrate that our AGEN framework generalizes effectively taining high solution quality and outperforming other baselines by substantial margin across all CVRP instances. AGFN achieved the best objective values among neural models, showing gaps of 1.13% and -3.60% compared to LKH-3 on instances with 2,000 and 3,000 nodes, respectively. For larger instances with 5,000 and 10,000 nodes, AGFN completed each instance in just 14.60 seconds, whereas other baselines, including LKH-3, failed to produce results at this scale due to computa- tional constraints. is worth noting that our model, trained on 100-node instances, outperforms GFACS, which is pretrained on 200-node wonnnnennnntnnnee instances, with much shorter computation time. Notably, on the largest instance with 10,000 nodes, AGFN completed in just 14.60 seconds for each instance, whereas other baselines including LKH-3 were unable to produce results for this scale due com- putational constraints. These findings underscore the strong generalization ability and scalability of our approach, making well-suited for solving real-wor real-world large-scale scale VRPs.
We use the GFACS-200 because its pretrained model based 100-node instances is unavailat lable.
15


Reviews:
[{"review_id": "8SJ2XjWVmk", "reviewer": "Reviewer_opH2", "summary": "This paper introduces a novel neural solver for vehicle routing problems, specifically CVRP and TSP. It employs a generative flow network (GFlowNet) to learn a diverse set of potential solution trajectories to address the common challenge in VRP solvers of falling into locally optimal solution. The GFlowNet is trained in an adversarial manner where a discriminator is used to distinguish between the raw outputs of the network and their corresponding optimized trajectories obtained via local search techniques. To further balance the exploration and exploitation, the method uses a hybrid decoding strategy, similar to $\\epsilon$-greedy. Experimental results show that the proposed method generally outperforms existing baselines, especially on larger problem instances with higher numbers of nodes.", "questions": "Please see Weaknesses", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Leveraging GFLowNet and the proposed hybrid decoding strategy is well-suited for generating a diverse set of trajectories, which could help to avoid local optima trajectories.\n- The proposed method shows good performance and scalability. It works especially well in larger instances with more nodes compared with the baselines.", "weaknesses": "- The paper primarily integrates existing components such as the GFlowNet, adversarial training, and $\\epsilon$-greedy, into a coherent system for solving vehicle routing problems.\n- A more detailed explanation and discussion could be beneficial. For example, how to generate the sparse edge set? How to pick the optimal value of $\\mathcal{P}$ for the hybrid decoding?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9IOenQT1Ka", "reviewer": "Reviewer_bQyX", "summary": "The article mainly uses the idea of ​​GFlowNet in CVRP problem that the solution can be inferred by probability. In order to prevent convergence to the local optimum, the author also introduced a discriminator to form an adversarial model. By alternately training the generator and the discriminator, GFlowNet can infer a high-level solution. In the experiment, the data sets of 200, 500, and 1000 were tested and good results were achieved.", "questions": "From the experiment, the method in this paper is better than the traditional reinforcement learning autoregressive method in solving path planning problems, but how is the effect on a larger scale?(like 5000, 10000) Whether the algorithm will fail on larger datasets？\nThe design of ​​gflownet makes this method well adapted to problems with multiple optimal solutions, but for problems such as CVRP, the optimal solution is unique, so what is the advantage of using gflownet?\nBecause adversarial learning is the core of this paper, we hope that the author can show from a theoretical or experimental perspective that it has advantages over other methods of generating diverse samples. Or the author can prove the novelty of this paper by showing that they have made improvements to the adversarial learning framework.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "GFlowNet was introduced in the CVRP problem to verify its feasibility and advantages in combinatorial optimization problems. In addition, adversarial training was added during the training phase, allowing the network to explore a wider area. Experiments have verified that this method can surpass some methods. \nAvoiding local optima in the solution of combinatorial optimization problems is an important issue and the method given in the article is a good solution.\nVery detailed experiments are carried out in the text and the results of these experiments are explained in detail, which will help to refer to future work.", "weaknesses": "The article mainly applies GFlowNet to the CVRP problem, but the corresponding improvements and innovations are slightly insufficient. In addition, the article does not go into details when describing the method, such as the explanation of the reward function and the meaning of the loss function.\nThe article mentions that generating high-quality diverse samples is the key to the effectiveness of the algorithm. Using adversarial learning to solve this problem is a common idea. We do not see that the author has made any significant improvements to this framework to improve its ability to generate diverse samples.\nThe code is currently not open-source and cannot be evaluated for the reproducibility of the experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JZVXjc9Drv", "reviewer": "Reviewer_ToYi", "summary": "The paper titled \"Adversarial Generative Flow Network for Solving Vehicle Routing Problems\" introduces a novel framework, Adversarial Generative Flow Networks (AGFN), which leverages the capabilities of Generative Flow Networks (GFlowNets) and adversarial training to address the vehicle routing problem (VRP). The AGFN framework combines a generative model for constructing diverse solutions with a discriminative model for evaluating these solutions. The models are trained in an adversarial manner to enhance the overall solution quality. The authors apply AGFN to solve the capacitated vehicle routing problem (CVRP) and the traveling salesman problem (TSP), demonstrating its effectiveness against popular neural solvers and showcasing its strong generalization capabilities on both synthetic and real-world instances.", "questions": "Hyperparameter Sensitivity: How sensitive is AGFN to hyperparameter tuning, particularly for the hybrid decoding method? Are there any guidelines or methods used to select these parameters?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1） The paper presents a novel approach to VRPs by combining GFlowNets with adversarial training, which is a creative extension of existing methods.\n\n2） The proposed AGFN framework addresses the scalability challenges faced by current neural solvers for VRPs.\n\n3） The paper is well-written, with clear explanations of the AGFN framework and its components.", "weaknesses": "More analysis on the computational efficiency, especially in terms of scalability, would be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)