- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper introduces Neural Cluster-First–Route-Second (Neural CFRS), a hybrid learning and optimization framework for CVRP, focusing on recurring routing instances over fixed customer locations. The method learns reusable spatial embeddings, predicts cluster seeds and customer-to-cluster assignment costs, and employs a differentiable optimal transport layer for capacity-aware supervision. Feasible clusters are then recovered via mixed-integer optimization, followed by independent TSP solvers. Experimental results show competitive solution quality under the fixed-support setting and demonstrate the benefits of learned seed selection and spatial pretraining. However, the learned assignment costs generalize poorly to larger instances, and the method remains computationally dependent on classical optimization solvers.
Critical strengths
- The paper investigates recurring CVRP instances over fixed customer locations, which is a practically relevant setting not explicitly addressed by standard CVRP benchmarks. Reusing spatial representations across instances provides an interesting direction for neural routing optimization.
- The proposed framework combines learned clustering guidance with capacity-constrained assignment and TSP solvers, which is reasonable and shows effectiveness over experimental results.
Critical weaknesses
- The method mainly combines existing techniques, including Fisher–Jaikumar clustering, Transformers, Sinkhorn OT, and classical solvers. The claimed symmetry properties also largely follow from the CFRS formulation. More importantly, the paper lacks comparisons with simpler alternatives, e.g., stronger classical seed-selection heuristics or learning assignment costs without OT, making it difficult to assess the necessity of the proposed components.
- Experimental results show limited benefits from the proposed components. In Table 1, replacing learned assignment costs with classical FJ costs improves the CVRP1000 gap from 7.63% to 2.78%. Similarly, raw coordinates outperform pretrained spatial embeddings in the full-depth model at N=1000 (3.26% vs. 3.77%). These results raise concerns about the effectiveness of the two main learning components, particularly on larger instances.
Questions for authors
- Since learned seed selection appears to provide most of the performance improvement, could the authors compare it against stronger classical seed-selection heuristics, and evaluate whether the OT layer offers additional benefits over directly supervised assignment costs followed by CAP decoding?
- Why do learned assignment costs and pretrained spatial embeddings become less effective on larger instances?
- Could the authors clarify the practical computational benefits of the framework, including the runtime contributions of Gurobi and LKH-3, and evaluate a more flexible fleet-size selection strategy under matched computational budgets?
2 comments
Response to Reviewer GkLD (Part 2/2)
Q3a: Practical Computational Benefits of the Framework.
Neural CFRS respects the three studied symmetries of the Symmetric Euclidean CVRP. It inherits invariance, intra-route traversal invariance and inter-route permutation invariance. Therefore, by design, Neural CFRS needs no symmetric data augmentation and trains in just 30 epochs on 1M instances under 3 hours. The pretraining of can be completed in less than 30 minutes. Appendices B and F contain the details of this. We require substantially fewer epochs than BQ-NCO (500 epochs) or LEHD (40 epochs at larger batch size.) can also be used to train an extremely parameter efficient model, with only 682K parameters, with minimal performance degration (see Table 2). This enables a lightweight neural prediction stage and future research can look into methods that do not include CAP solving, which can enable cluster prediction to be fully run on GPUs, followed by paralle TSP solves on CPUs.
Q3b: Runtime Contributions of Gurobi and LKH-3.
Please see Global Response G4.
Q3c: A Flexible Fleet Size Selection Strategy
Please see Global Response G5.
Response to Reviewer GkLD (Part 1/2)
Thank you for the clear, constructive review and for recognizing the practical importance of recurring routing over fixed geography as well as the effectiveness of pairing learned clustering with capacity-constrained optimization. We address each of your points below.
W1: Novelty, Symmetry Properties, and Component Ablations
Indeed, it is true that Neural CFRS builds on established primitives, such as Fisher-Jaikumar, Transformers, Sinkhorn OT, MIP/TSP solvers. The neural components are trained jointly through differentiable OT supervision, followed by discrete CAP and TSP decoding. One contribution that we would like to highlight, is the fact that differentiable OT enables the model to learn capacity constraints - something that existing autoregressive methods do not have as masking of infeasible nodes is generally utilized.
The symmetry properties are indeed obvious to state, but it is something that the community has overlooked. It is not true that it largely follows from the CFRS formulation. Even when route recovery uses an undirected TSP solver, autoregressive cluster construction as in TAM and GLOP still consumes raw (x,y) coordinates (breaking E(2) invariance) and outputs clusters sequentially (breaking inter-route permutation invariance).
As to the general idea of trying different costs, we conducted an ablation across seed selection (Grid, FJ, Learned) and assignment costs (Euclidean, FJ, Learned) (see Table 1). Interestingly, it turns out that a simple FJ cost actually performs better when the instance size increases (N=500,1000) (mentioned in Abstract and Section 3). A discussion on the OT ablation can be found in our next point.
Q1: Stronger Classical Seed Heuristics and OT Ablation
Stronger Classical Seed Heuristics. Within the FJ / classical CFRS literature, FJ's geometric approach to selecting seeds is the standard seed selection method. Sweep and Petal, which we also benchmark in Table 1, are considered CFRS methods but do not involve a seed selection heuristic. Within the Fisher–Jaikumar framework, FJ's geometric seed selection is the canonical classical heuristic, and we additionally benchmark Sweep, Petal, and uniform Grid seeds in Table 1. With reference to Table 1, adding learned seeds on top of classic FJ improves over FJ seeds at every single scale. These improvements are as follows: 6.58% → 4.27% (N=100), 6.28% → 4.42% (N=200), 7.56% → 3.62% (N=500), and 7.77% → 2.78% (N=1000).
OT Ablation. Please see Global Response G2.
W2 and Q2: Performance of Learned Costs and Spatial Embeddings at N=1000.
Why FJ costs are better than learned costs at N=1000. Classical FJ explicitly computes the assignment costs, taking into account the distance from the depot - it directly measures the extra distance from inserting a customer into a depot-seed-depot tour. In contrast, our latent cost head is simply a customer-to-seed Euclidean distance, relying on self-attention with the depot token to encode depot geometry implicitly. With the problem size increasing, the interaction with the depot token becomes a more noisy signal and could result in poorer performance. This is a limitation of our existing method and future work should exploit this finding. Our results still show a clear improvement with learned seeds, though the learned assignment costs benefits are limited at this point.
Ψ not effective on large instances. We first need to clarify that the results cited of N=1000 (3.26% vs. 3.77%) in Table 2(a) change two variables simultaneously: Ψ and LBCE. We directly address from Line 1141 onwards in the Appendix "Apparent Phase Transition for Ψ and LBCE".
We would like to draw the reviewer to another result in Table 4, where we isolate the representational power of Ψ. Here, we see that the lowest gaps are obtained using Ψ. This demonstrates the usefulness of Ψ, and we are excited to see this applied to existing autoregressive methods.