- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The authors propose COMPASS, a decomposition-based method for the OCTSP. Concretely, COMPASS structures each problem as a DAG, where edges represent fixed-endpoint subTSP solutions obtained via RL subsolvers. Via a shortest path computation, COMPASS then assembles the full solution. Experimentally the authors demonstrate both scalability advantages and clear quality gains over state-of-the-art methods for the OCTSP, while also showing that the method improves with additional computation budget.
Critical strengths
- The method is principled and strong for the targeted problem, which is shown clearly through the experiments. The empirical evidence supports the claims about effectivness, efficiency and scalability. Theoretical results, although rather intuitive, also ground the work. As a study concerning the OCTSP, I think there is little to criticize.
- The presentation, writing and structure are particularly strong. For example, Section 4 is a great transition between the problem formulation and the proposed method, which makes the authors method stand out better.
Critical weaknesses
-
My main criticism concerns the scope of the paper and its relevance to the ICLR community:
- The work treats only the OCTSP rather than routing problems in general. It is unclear to me to what extent the contributions would extend to more general settings.
- Moreover, the learned component itself is only a small part of the method, and seems mostly inherited from [1], with minimal adaptation beyond enabling asymmetric instances. Again, this raises the question whether there are any deeper conclusion to be drawn for the ICLR community.
- To me, this work seems more fitting for a transportation or operations research venue, where the problem class is the target of interest, rather than a deep learning venue like ICLR, which ideally should prioritize deep learning-based methodological contributions.
-
In my opinion the learned subsolver should be ablated to a larger extent. How well is it performing? Does it train adequately and what happens if you replace it with a strong classical heuristic? I understand that GPU-accelerated batched solving is a large advantage, but this is perhaps not inherent to RL-based methods.
In summary, while the paper is strong, I do not believe its methodological contribution or depth make it suitable for ICLR. I also believe the claim about orders of magnitude larger instance sizes compared to existing ATSP work should be tempered, since the problem considered in this work is fundamentally a different variant with more structure.
[1] Greenberg et al., Reinforcement learning for initializing genetic algorithms in vehicle routing. Communications AI & Computing, 2026.
Questions for authors
- There are significantly more methods in the learning-for-routing literature that cover asymmetric instances than NeuroLKH. E.g., MatNet [1], BQ-NCO [2], GREAT [3] and GLOP [4]. Would these, and other methods, be relevant to discuss? I suppose your problem sizes are generally beyond these, but perhaps it would be relevant to mention this explicitly in the paper.
[1] Matrix Encoding Networks for Neural Combinatorial Optimization. NeurIPS 2021.
[2] BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization. NeurIPS 2023.
[3] A GREAT Architecture for Edge-Based Graph Problems Like TSP. Arxiv. 2024.
[4] GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time. AAAI 2024.
4 comments
Thank you for your response, and for the changes made to the manuscript. Many of my concerns have been addressed adequately, and my assessment that this work represents a sound contribution with strong empirical results has been reinforced.
Nevertheless, I maintain my overall score and evaluation: The work is highly useful for the OCTSP, yet its contribution beyond this problem, especially methodologically, seems limited.
All the cited works: Tree of Thoughts (NeurIPS 2023), OPRO (ICLR 2024), and Self-Refine (NeurIPS 2023), target broader problem settings. Similarly, while I agree that scaling neural routing is an active research area, this work targets scaling for the OCTSP specifically, which is inherently different compared to vanilla TSP or CVRP. Again, this leaves it unclear what general take-aways are available.
As such, I cannot recommend acceptance, in spite of the strengths of the work. Additionally, if the authors plan on updating the manuscript further, it would be helpful if changes were marked with a different color compared to the original manuscript.
Scope: solving a real-world problem via learning
Thank you for the follow-up. We are glad that many of your concerns were addressed, and that you view our contribution as sound and the empirical results as strong.
Regarding the scope:
OCTSP is a high-impact real-world problem. It arises in large-scale deliveries with ordered delivery slots, as operated by companies like Walmart, Amazon, Instacart and Ocado, whose overall annual shipping costs are over USD 100B. Like most real-world problems, it involves a specific and detailed structure that requires a dedicated solution.
We made learning applicable to OCTSP via contributions at both the framework level and the learning-architecture level.
Our improvement on this important problem is not incremental, but rather COMPASS enables what was previously impractical. On Sao Paulo 11K, for example, compared to prior methods (and excluding the baselines we developed ourselves in Section 4), COMPASS reduces the cost gap from 3.1-4.3% to 0.46% with 10-100x shorter wall time (Table 2).
Potential applications beyond OCTSP: While this work focuses on OCTSP, the framework of COMPASS may extend to other large-scale optimization problems that decompose into natural sub-problems interacting through boundary decisions. Below we list real applications that can potentially be modeled this way, and thus might benefit from an adaptation of COMPASS’s framework. Such extensions are left for future work.
Appendix: potential applications
In chip design, Place and Route (Kahng et al., 2011) involves decisions on the locations of millions of cells and the paths of the wires connecting them in silicon. Cells are naturally grouped into blocks that are placed and routed separately, but their optimizations are co-dependent through the pin positions where wires cross block boundaries.
In laser cutting of sheet metal (Dewil et al., 2016), the decisions are the cutting order of contours and the entry (pierce) point on each contour. Contours are naturally grouped into parts, and inner contours must be cut before their enclosing contour. The parts' cutting paths are co-dependent through the entry and exit points that connect consecutive parts.
I thank the authors for their engagement. Nevertheless, I maintain my score of 2, as I cannot recommend acceptance. The learned component is largely inherited from prior work, so I consider the deep learning contribution too small. I also find the framework-level novelty claims and the scalability advantage over prior distance-based neural routing somewhat overstated. Lastly, applicability to other problems remains to be demonstrated concretely.
Note to the AC: my score reflects fit and methodological depth, not necessarily the quality of the work. I consider the paper sound and well-written.
Thank you for your constructive review. We are glad that you found our presentation particularly strong, and our method principled, effective, efficient and scalable.
We have carefully addressed your comments, conducted ablation tests that isolate the RL module contribution, added relevant literature, and clarified the scope of our contribution.
The scope of the paper and its relevance to ICLR:
[1] Amazon’s 2025 Annual Report, p. 25, Cost of Sales
[2] Hou et al. Generalize Learned Heuristics to Solve Large-scale Vehicle Routing Problems in Real-time. ICLR 2023
[3] Luo et al. Boosting Neural Combinatorial Optimization for Large-Scale Vehicle Routing Problems. ICLR 2025
The learned subsolver should be ablated.
Thank you for raising this important point.
We now added an extensive ablation study with a particular focus on the contribution of the RL module. The RL agent achieves a speedup of up to 1.3x for the same cost (Figure 12), contributing 0.1-0.2% cost reduction consistently across benchmarks (Figure 11).
What happens if you replace it with a strong classical heuristic?
We now added this experiment in Figure 12, demonstrating significant speedup by the RL module as specified above.
The heuristics we used: cuOpt itself is a strong classical heuristic solver based on a genetic algorithm, so the first ablation replaces the RL warm-up by extra cuOpt time. The second ablation applies nearest-neighbor initialization, which was the strongest classical warm-up heuristic baseline in Greenberg et al. (Communications AI & Computing, 2026).
GPU-accelerated batched solving is a large advantage, but this is perhaps not inherent to RL-based methods.
We agree that GPU batching is not specific to RL. Our base solver - cuOpt - also uses GPU-accelerated batched solving. Hence, the significant gain of RL initialization (as discussed above) is evaluated over an already-GPU-accelerated cuOpt baseline.
The claim about orders of magnitude larger instance sizes compared to existing ATSP work should be tempered, since the problem considered in this work is fundamentally a different variant with more structure.
We modified the claim to clarify it is made possible by the variant’s structure.
There are more methods for learning-for-routing that cover asymmetric instances (MatNet, BQ-NCO, GREAT and GLOP) - but your problem sizes are generally beyond these.
You are right on both accounts: