acceptodds
Under review as a conference paper at ICLR 2027

COMPASS: Ordered Clustered Routing at 100K Scale

Abstract

Large-scale routing often requires visiting clusters of nodes in a prescribed order, giving rise to the Ordered Clustered Traveling Salesman Problem (OCTSP). Optimizing each cluster independently seems natural, but misses non-local dependencies. We introduce the COMPASS algorithm for OCTSP, which orchestrates sub-solvers accelerated by reinforcement learning over an attention-enhanced GNN model. COMPASS has no quality ceiling and its solutions keep improving with compute. It exploits the clustered structure, and can reach exact solutions in time exponential in cluster size rather than instance size. Empirically, COMPASS consistently outperforms alternative methods. Unlike common large-scale routing solvers, COMPASS consumes general distance matrices and is not limited to coordinate inputs. We demonstrate scaling to 100K synthetic nodes and to 28.5K real e-commerce nodes. To our knowledge, the latter is the largest reported routing solution over asymmetric distances, 9× beyond established ATSP benchmarks.

Primary area:
optimization
Keywords:
neural combinatorial optimization, reinforcement learning, large-scale optimization, clustered TSP

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_DmJuOpenReview ↗
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 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:

  • Methodological relevance: Our methodological contribution is a search framework that integrates learned local solvers through global endpoint optimization. This reduces the learning problem from the instance size to the cluster size, making it applicable in scale. Indeed, as in Tree of Thoughts (NeurIPS 2023), OPRO (ICLR 2024), and Self-Refine (NeurIPS 2023), the core innovation lies in how the learned agents are orchestrated. Hence, COMPASS's novelty should be assessed at the framework level. On top of this core framework contribution, we also adapt the RL module to distance-matrix inputs.
  • Application significance: We introduce a new application of deep learning to the OCTSP problem arising in large-scale industrial routing. Reported shipping costs reach USD 102.7B per year for a single e-commerce operator [1]. Illustratively, cutting 0.1% from USD 10B of routing-sensitive spending would save USD 10M/year.
  • Novelty within learned routing: Scaling learned routing up is an active research field at ICLR [2,3]. COMPASS advances this field by exploiting ordered clustered structure to scale learned routing.

[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:

  • Other works address asymmetric instances and are relevant to mention explicitly. We now added them to Section 2.
  • Their evaluation scale on asymmetric problems is up to 1K, whereas we focused on baselines that are either large-scale (10K-100K) or dedicated to the OCTSP setting.

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.

AuthorsOpenReview ↗

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.

Reviewer_xVAYOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

The paper proposes a solver (COMPASS) for the clustered routing problem, where traveling salesman problem is broken down into clusters, where all nodes in a cluster must be visited first before moving to another cluster. The paper shows that existing approximations (boiling down to greedy or heuristic approaches) can be suboptimal and provide concrete examples of their suboptimality. Instead, the paper formulates a DAG of this problem that has subproblems corresponding to standard TSP problems, and then uses RL solvers along with GNN embeddings to solve these subproblems and stitch together. The approach is evaluated on a large-scale benchmark, where COMPASS scales favorably at inference time compared to existing methods.

Critical strengths
  1. The paper is written well, being rather easy to follow. The suboptimality of greedy-type approaches is clear from the provided visual examples.
  2. The experimental evaluation shows promising scaling performance, and the benchmarks represent a nice evaluation of existing methods in the large-scale regime.
Critical weaknesses
  1. Proposition 1 seems uninformative and its value overstated. Specifically, once the optimal boundary states are represented and the corresponding subproblems are solved optimally, recovering the global optimum through dynamic programming follows directly from the principle of optimal substructure. The paper does not convincingly establish how this proposition goes beyond the standard DP properties or existing decomposition approaches for clustered routing. Similarly, the claim that the algorithm has "no quality ceiling" appears relatively weak as a theoretical contribution, since exhaustive enumeration with exact subproblem solvers can recover the optimum for any finite combinatorial optimization problem. Proposition 1 does not, for example, provide an approximation guarantee for the practical algorithm, characterize the error introduced by approximate subproblem solvers, or establish a convergence rate as computational resources increase.
  2. The algorithmic novelty of this approach seems limited to me, from the perspective that the main technical optimization for the subproblem is delegated to an existing RL-based solver. There is a proposed extension in Line 310 that uses a GNN model with attention, but there is little discussion about this in the main paper.
Questions for authors
  1. See weaknesses above. These two weaknesses are the main reason for my score. To me, the proposed approach does not meet the technical bar of ICLR.
  2. How much of the improvement comes from the proposed RL/GNN extension, compared with using the original subsolver within the same DAG-based optimization framework?
3 comments

Thank you for your constructive review. We are glad that you found our paper well-written with promising scaling performance.

We have carefully addressed your suggestions: we added ablation tests for evaluation of the RL agent; extended the theoretical analysis for non-exact subsolvers; and clarified the scope of our novelty.

The algorithmic novelty of this approach seems limited to me… the main technical optimization for the subproblem is delegated to an existing RL-based solver.

Our main algorithmic novelty is the COMPASS framework (Algorithm 1), which integrates learned cluster solvers using global coordination, and by that reduces the learning problem from a global size (e.g. 10K-100K) to a local size (e.g. 20-200). This algorithm was not proposed in previous works that addressed OCTSP (Section 2), despite its significant benefits demonstrated in Section 6.

Frameworks around existing learned modules are established methodological contributions: Tree of Thoughts (NeurIPS 2023), OPRO (ICLR 2024), and Self-Refine (NeurIPS 2023) contribute inference/search procedures without changing the underlying model training. Similarly, COMPASS's novelty should be assessed at the framework level.

On top of this core framework contribution, we also adapt the RL module to distance-matrix inputs.

How much of the improvement comes from the proposed RL/GNN extension, compared with using the original subsolver?

Thank you for suggesting this comparison.

Baseline for comparison: The original EARLI subsolver (Greenberg et al. 2026) takes coordinates and is not directly applicable to general distance-matrix inputs. Our extension enables these inputs. The base cuOpt subsolver does handle distances, and the new ablation in Figure 11 now compares to it directly. Figure 12 extends the ablation further and compares our RL initialization to two applicable alternatives: cuOpt itself (with the warm-start budget re-allocated to it), and nearest-neighbor initialization, which was the most competitive warm-up baseline in Greenberg et al. (2026).

Results: Evidently, the RL warm-up provides up to 1.3x speedup for the same solution cost (Figure 12), and reduces costs by 0.1-0.2% across benchmarks (Figure 11). For scale, reported shipping costs reach USD 102.7B per year for a single e-commerce operator [1]. Illustratively, cutting 0.1% from USD 10B of routing-sensitive spending would save USD 10M/year.

[1] Amazon’s 2025 Annual Report, p. 25, Cost of Sales

Uses a GNN model with attention, but there is little discussion about this in the main paper.

Thank you for pointing to this. We now elaborated further on our architecture in Appendix C1, referred from Section 5.

Proposition 1 seems uninformative.

Proposition 1 is indeed mathematically simple, but serves several purposes:

  • Core distinction from prior work: As you observed, exhaustive enumeration can recover any finite optimum. However, COMPASS exploits the OCTSP structure to make the exhaustive enumeration exponential in n (cluster size). Alternative OCTSP baselines (Sections 2, 4) scale exponentially with N (instance size), restrict the search space, or do not provide guarantees.
  • On small scale: Proposition 1 provides solution certification (Section 6).
  • On large scale: Proposition 1 aims to provide a formal grounding to the intuition that we systematically cover the search space, helping to interpret why COMPASS keeps improving when other baselines plateau (Section 6).
  • Proposition 1 also provides some insight for the roles of the budget hparams: K for endpoint coverage vs t1,t2 for subproblem accuracy (also see below the extended Proposition 1 for the effect of subproblem errors).

We now clarify these motivations in Section 5.

Proposition 1 does not characterize the error introduced by approximate subproblem solvers.

By your proposal, we now extended Proposition 1 to accept approximate subsolvers instead of exact ones.

Assuming that subsolver errors are bounded by ε, and that the endpoints (s*,t*) are covered by the candidate set, the overall OCTSP sub-optimality is at most m*ε (for m clusters). This bound already includes not only the subsolver errors themselves, but also any endpoint selection errors caused by them.

The significance of this result comes from the practicality of the sub-solvers: achieving near-optimal TSP solutions for size n=100 is practically plausible, whereas for size N=10K the practical solutions are much more limited.

Thank you for suggesting this contribution to the paper.

I thank the authors for their response. My question 2 is addressed in the rebuttal. While I appreciate that this should be judged at the framework level, I am not convinced about the breadth of the methodological contribution similar to Reviewer DmJu and my concerns about Proposition 1 being uninformative still remain. I will maintain my score.

Thank you for the follow-up. We are glad that your question about the RL contribution was addressed.

  • Breadth of contribution: Please see our response to Reviewer DmJu.
  • Proposition 1 “being uninformative”: This is not a theory paper, and our primary contributions are methodological and empirical. Having said that, we demonstrate a direct application of Proposition 1 for solution certification, newly certifying 9 instances of Ahmed et al. (2014). Thus, we respectfully believe that the term “uninformative” does not match the contribution.
Reviewer_pP9POpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes COMPASS, a scalable algorithm for the Ordered Clustered Traveling Salesman Problem (OCTSP), where nodes must be visited according to a prescribed cluster order. COMPASS represents candidate intra-cluster routes and inter-cluster bridges as a layered directed acyclic graph (DAG), uses RL-accelerated sub-solvers to estimate fixed-endpoint route costs, and applies global shortest-path dynamic programming to coordinate endpoint selections. The framework provides a conditional exactness guarantee and supports general, potentially asymmetric distance matrices. Experiments demonstrate scalability to 100K synthetic Euclidean nodes and 28.5K real-world e-commerce nodes with asymmetric driving-time costs, along with the reported exact certification of nine previously uncertified benchmark instances.

Critical strengths

S1. Effective Structure-Aware Global Optimization

The layered-DAG formulation cleanly coordinates intra-cluster routes and inter-cluster bridges while exploiting the prescribed cluster order. Unlike approaches that commit to local endpoint decisions, COMPASS enables global coordination and avoids a fixed quality ceiling under its conditional exactness guarantee.

S2. Strong Scalability and Empirical Validation

COMPASS demonstrates strong scalability on new benchmarks with up to 100K Euclidean nodes and 28.5K nodes with asymmetric driving-time costs. The evaluation also includes the competitive Pairwise Slider baseline and reports exact certification of nine previously uncertified instances from Ahmed (2014).

Critical weaknesses

W1. Insufficient Ablations and Model Details

COMPASS combines heuristic endpoint selection, RL warm-start, cuOpt, global DP, post-optimization, and bridge repair without component-level ablations. In particular, the absence of a cuOpt-only comparison makes it difficult to isolate the contribution of RL warm-start. Additionally, the attention-enhanced GNN is described only at a high level, leaving architectural details and the handling of asymmetric distances and fixed-endpoint constraints insufficiently specified.

W2. Modest Improvements Relative to Computational Cost

The final cost improvements over Pairwise Slider are modest (0.11–0.23 percentage points in BKS gap), while COMPASS uses up to 16 H100 GPUs compared with a single H100 for Slider. Although Figure 5 includes single-GPU COMPASS results, a more explicit comparison of solution quality against total computational cost (e.g., GPU-hours), alongside wall-clock time, would help clarify the practical benefit of the additional parallel resources.

Questions for authors

Q1. Contribution of Individual Components

How does COMPASS perform without the RL warm-start (using cuOpt alone under the same computational budget), and how much additional improvement comes from post-optimization and bridge repair?

Q2. Consistency of the Exact Certification Benchmark

Section 3 defines an open-path OCTSP, whereas Ahmed (2014) considers depot-based closed tours. How are the depot-to-first-cluster and last-cluster-to-depot costs incorporated into the DAG and exact solver when certifying the instances in Table 3?

2 comments

Thank you for your constructive review. We are glad that you found our method effective and strongly scalable. Please see our responses to your comments below.

[W1, Q1] Insufficient Ablations (RL, post-optimization, bridge-repair) / difficult to isolate the contribution of RL warm-start.

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. Specifically, 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). Post-optimization and bridge repair also present consistent cost reduction, whereas the effect of the bridge-selection components is benchmark-dependent (Figure 11).

[W1] The attention-enhanced GNN is described only at a high level.

We now added a detailed description of the attention-enhanced GNN architecture in Appendix C1, referred from Section 5.

[W2] Modest Improvements Relative to Computational Cost / an explicit comparison against GPU-hours would help.

We now plot solution quality against computational cost explicitly in Figure 10. Evidently, COMPASS outperforms the baselines per compute budget and not only per wall time. The advantage increases with compute: for example, COMPASS reaches the same cost as extended-budget Slider in 3x-9x fewer GPU-hours across benchmarks.

Note that the two methods we present - COMPASS and Slider - are both competitive at low budgets (e.g. 0.46% vs 0.44% cost gaps on short compute budgets in SP data), but only COMPASS scales well for a more thorough search (achieving the best known solutions, whereas Slider still lags 0.22% behind after 63 minutes). We now clarified this in the manuscript.

To provide some scale for the solution cost vs computational cost: reported shipping costs reach USD 102.7B per year for a single e-commerce operator [1]. Illustratively, cutting 0.1% from USD 10B of routing-sensitive spending would save USD 10M/year.

[1] Amazon’s 2025 Annual Report, p. 25, Cost of Sales

[Q2] Consistency of the Exact Certification Benchmark: open-tours vs closed-tours.

Thank you for catching this missing explanation. We now updated it in Section 6.

The explanation: We duplicate the depot, placing one copy as a singleton first cluster and the other as a singleton last cluster. The resulting open path corresponds to the original closed tour and has the same cost.

Thanks for the response and additional experiments. The ablations clarify the contributions of RL and post-processing, and the architecture details and depot explanation address my earlier questions. The GPU-hour comparison also substantially alleviates my efficiency concern. I remain at weak acceptance.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.