ICAM: Rethinking Instance-Conditioned Adaptation in Neural Vehicle Routing Solver

1. As previous works have already demonstrated that integrating node-to-node distances and instance scales into neural solvers can improve generalization performance on large-scale instances, the novelty of the proposed instance-conditioned adaptation function is very limited. Meanwhile, the proposed AAFM is also a simple adaptation from previous method AFT. Given these considerations, I am concerned that this paper may not provide valuable insights to the NCO community.
2. The three-stage training scheme seems to be crucial for achieving the experimental results reported in this paper. However, it is notable that the results from competing methods are typically obtained under much simpler settings. Although the ablation studies in Table 19 demonstrate that ICAM can outperform POMO-ThreeStage, it is also evident that three-stage training significantly enhances POMO's performance on large-scale instances. This raises a concern regarding whether other competing methods might similarly benefit from a three-stage training approach. A direct comparison using consistent training settings can make the reported experimental results much more convincing.

1. According to Table 2, the proposed adaptation function can effectively improve the generalization of POMO with a small time and memory overhead. Obviously, just depending on node-to-node distances is not enough, but I am curious which has a greater effect, the scale information or the learnable parameter? It would be interesting to compare the effects if either the scale information or the learnable parameter is removed.

2. This paper uses the proposed adaptation function for the proposed AAFM and subsequent compatibility calculation. Considering that there is already some works on incorporating auxiliary information into the compatibility calculation (as shown in Table 1), it would be beneficial to evaluate the performance of this function when it is only used in AAFM.

3. This paper adopts a three-stage training scheme, what is the effect of each stage on the performance?

1. While the paper presents a new model named ICAM, its innovative contributions appear limited in scope. Specifically, the proposed modifications primarily target the adaptation function and attention mechanism, and these incremental changes might not be sufficient to demonstrate a significant advancement over existing RL-based NCO methods.
2. The term "comprehensive instance-conditioned information" is not clearly defined. The paper states that using only "node-to-node distances or scale information is insufficient." However, in the proposed adaptation function, these are the only two types of information used. There is no addition of new forms of instance-specific information beyond these, which seems to contradict the paper's claims of comprehensive information usage.
3. The design choices for both the adaptation function and the attention mechanism lack rigorous theoretical analysis. In the "Results on Benchmark Dataset" section, the performance on TSPLIB is not particularly competitive compared to some of the state-of-the-art methods. The reasons for this subpar performance should be further analyzed.
4. The writing, particularly in the contribution section and the motivation (Section 2.1), includes several redundant explanations. A more concise presentation of the contributions and key ideas would improve readability.

• In the Introduction (lines 84-91), the authors state that all the previous methods that utilize the node-to-node distances to bias the output score in the decoding phase or refine the information via a complex policy fail to achieve satisfactory generalization performance on large-scale instances. This statement appears inaccurate, as these methods, e.g., ELG [1], are known to achieve state-of-the-art generalization performance on large-scale TSP and CVRP instances.
• In the adaption function, the learnable parameter $\alpha$ plays important role in this function. This paper lacks clarity on how this parameter is learned during training, and a detailed analysis is necessary to assess its impact.
• In experiments, this paper uses a three-stage training scheme for the proposed model. Stages 1 and 2 are not new and are similar to the training techniques in DAR [2]. In stage 3, there are two additional parameters, i.e., $\beta$ and $k$. The authors claimed that there is no significant performance variation among different models with various $k$ values. This raises a concern about the impact of the best $k$ trajectories among all $N$ trajectories on the performance of the model.
• Furthermore, additional training may make the results unfair to compare the performance with other existing baseline models. The results of baseline models with expanding training should be reported and compared.
• The author only reported the results of baseline models, e.g., LEHD [3] and BQ [4], with greedy search inference for TSP and CVRP with scale <=1000 (Table 3). However, these models achieve their best performance with the RRC strategy and beam search, respectively. According to these works, the results obtained from these baselines can surpass the ICAM results. The authors should report these results for comprehensive comparisons.
• With scales >1000 (Table 5), the results of the baseline ELG are lacking, while ELG demonstrated superior performance on large-scale CVRP instances up to 7000 nodes. However, the best results obtained by ICAM do not seem much better than those obtained by LEHD with greedy inference. It makes the results of ICAM on CVRP instances with a scale range from 1000 to 5000 not persuasive.
• In the results on the benchmark dataset, this paper just evaluates the performance on a small-scale dataset of CVRPLIB Set-X (scale <=1000). The performance on larger scale datasets, such as CVRPLIB Set-XXL with larger scales (1000 to 7000 nodes) should be evaluated and analyzed.
• The same concern about results for TSPLIB, the author only reported the results on instances with scale <=1000, which limits the large-scale generalization performance on larger scales (>1000) in the TSPLIB. This evaluation is important to verify the good generalization of the proposed method on large-scale Routing problems, e.g., TSP and CVRP.
• In the ablation study on the effects of larger training scales, the authors only report the results for TSP and not for CVRP. The proposed varying scale training on CVRP should be carefully designed and investigated because CVRP has more complex features than TSP, such as varying demand at each node, which may destabilize the learning model when exposed to multiple sizes and demand distributions simultaneously.
• No code is available.

References: [1] Chengrui Gao, Haopu Shang, Ke Xue, Dong Li, and Chao Qian. Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy. In International Joint Conference on Artificial Intelligence, 2024.

[2] Yang Wang, Ya-Hui Jia, Wei-Neng Chen, and Yi Mei. Distance-aware attention reshaping: En- hance generalization of neural solver for large-scale vehicle routing problems. arXiv preprint arXiv:2401.06979, 2024.

[3] Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.

[4] Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Marc Andreoli. Bq-nco: Bisim- ulation quotienting for efficient neural combinatorial optimization. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.