acceptodds
Under review as a conference paper at ICLR 2027

Neural Cluster First, Route Second: Capacitated Vehicle Routing via Differentiable Optimal Transport

Abstract

The Capacitated Vehicle Routing Problem (CVRP) underpins modern last-mile logistics, where routing decisions recur over the *same fixed service area*, like a city. In this setting, routing problems share a fixed set of potential customer locations, while active customers and demands vary between instances. We study how this spatial support can be exploited through reusable learned representations and design our method around three symmetries of the symmetric Euclidean CVRP: transformations, vehicle-route permutations, and tour reversal. We introduce Neural Cluster-First–Route-Second (CFRS), a neural extension of the Fisher–Jaikumar framework that predicts seed-selection scores and customer-to-cluster assignment costs non-autoregressively and respects the three symmetries. A differentiable entropic optimal transport layer provides capacity-aware supervision and guides discrete capacitated assignment, followed by independent traveling salesman subproblems for route recovery. Component ablations show consistent benefits from learned seed selection, while learned assignment costs perform best near the training size and classical FJ costs perform better at larger sizes under exact decoding. On the fixed-support distribution with constant capacity, a model trained on achieves a routing gap relative to HGS at without retraining. A shallow variant with one attention layer in each transformer achieves a gap at this scale, with spatial embeddings consistently improving routing quality over raw coordinates. Embedding interpolation further accommodates entirely unseen customer locations without retraining. On standard CVRP benchmarks, a separately trained model achieves a routing gap relative to LKH-3 at .

Primary area:
optimization
Keywords:
neural combinatorial optimization, capacitated vehicle routing, differentiable optimal transport, cluster-first route-second, non-autoregressive learning, spatial support

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_GkLDOpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. 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
  1. 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?
  2. Why do learned assignment costs and pretrained spatial embeddings become less effective on larger instances?
  3. 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
AuthorsOpenReview ↗

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)(x,y) coordinates (breaking E(2)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,1000N=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% →\to 4.27% (N=100N=100), 6.28% →\to 4.42% (N=200N=200), 7.56% →\to 3.62% (N=500N=500), and 7.77% →\to 2.78% (N=1000N=1000).

OT Ablation. Please see Global Response G2.

W2 and Q2: Performance of Learned Costs and Spatial Embeddings at N=1000N=1000.

Why FJ costs are better than learned costs at N=1000.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.

Ψ\Psi 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: Ψ\Psi and LBCE\mathcal{L}_{BCE}. We directly address from Line 1141 onwards in the Appendix "Apparent Phase Transition for Ψ\Psi and LBCE\mathcal{L}_{BCE}".

We would like to draw the reviewer to another result in Table 4, where we isolate the representational power of Ψ\Psi. Here, we see that the lowest gaps are obtained using Ψ\Psi. This demonstrates the usefulness of Ψ\Psi, and we are excited to see this applied to existing autoregressive methods.

AuthorsOpenReview ↗

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 E(2)E(2) 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 N=100N=100 instances under 3 hours. The pretraining of Ψ\Psi 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 4×4\times larger batch size.) Ψ\Psi 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.

Reviewer_R6p9OpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies repeated instances of the Euclidean CVRP drawn from a fixed pool of customer locations. It pretrains reusable spatial embeddings, learns seed selection and assignment costs, and uses a differentiable optimal-transport surrogate for capacity-aware supervision. A capacitated assignment MIP and independent TSP solvers recover routes. Experiments cover the fixed-support distribution, component ablations, unseen locations, and standard random CVRP benchmarks.

Critical strengths
  1. The CFRS decomposition provides a clear integration of learned clustering with capacity-feasible optimization.
  2. The learned-seed/FJ-cost ablation is informative and shows a consistent benefit from learned seed selection.
Critical weaknesses
  1. The strongest results depend on fixed spatial support and constant vehicle capacity. On standard CVRP1000, the best gap is 27.87% (LEHD: 4.91%; Fisher–Jaikumar: 3.75%). This leaves the model's overall routing effectiveness unconvincing.
  2. Table 5 reports TAM-LKH3 at -0.215%, which reproduces TAM's own CVRP1000 result with Q=200 and 100 test instances. This paper's standard CVRP1000 uses Q=250 and 128 LEHD instances. The TAM runtime (6.2 s here versus 1.82 s in TAM Table 1) also needs explanation. These discrepancies materially weaken confidence in the benchmark table.
  3. The primary benchmark uses one synthetic 3,000-location support; evaluation on several independent supports would strengthen the claim of reusable geography.
  4. At N=1000 with exact decoding, learned seeds with FJ costs obtain 2.78%, whereas learned seeds with learned costs obtain 7.63% (Table 1).
  5. Trying Kmin+1 improves the N=1000 exact gap from 7.63% to 4.31% (Table 7), indicating substantial sensitivity to fleet size.
Questions for authors
  1. Can the authors evaluate TAM-LKH3 on the same LEHD CVRP1000 instances (Q=250) and reconcile its runtime with Table 5?
  2. What is the gain from differentiable OT over directly supervised assignment costs with the same CAP decoder?
3 comments
AuthorsOpenReview ↗

Response to Reviewer R6p9 (Part 1/2)

Thank you for the close reading of our experimental tables and for recognizing the strengths of our work. We address each weakness and question directly below.

W1: Routing Effectiveness, Fixed Support, and Constant Vehicle Capacity.

We agree that 27.87% on standard CVRP1000 (Q=250Q=250) is a clear limitation of our method. It is reported transparently in Table 5. We also mentioned this in Line 472 in the conclusion. We will add a detailed limitations section in the final manuscript to highlight this. However, concluding from this single result that the model's routing effectiveness is unconvincing overlooks two results. First, the unseen node generalization results. Second, a possible architectural reason for the Q=250Q=250 drop in performance. Specifically, two modifications to our architecture, that can be pursued in future work, could potentially yield competitive results on standard CVRP1000.

  1. Unseen Node Generalization Results. The fixed spatial support generalizes to 100% unseen customers (see Table 1 and Appendix J). This indicates that the interpolation of the embeddings for unseen nodes is effective, and what we observe here could translate into the standard setting.
  2. Attention Neighborhood Size. Neural CFRS uses an attention neighborhood of size 2020 (see Appendix B and F). Given the demand distribution and the fixed capacity of Q=50Q=50 in our setup, a cluster would have 10 customers on average, which is smaller than the attention neighborhood. In contrast, at Q=250Q=250, a cluster would have 50 customers on average, which is larger than the attention neighborhood, and thus potentially explains the poor performance here.

Incorporating these two modifications into Neural CFRS could lead to higher performance in standard CVRP1000, but it is beyond the scope of this paper.

Furthermore, we would like to reiterate what already works today: (1) on standard CVRP100 (Q=50Q=50), Neural CFRS achieves 2.73%, beating greedy BQ-NCO (2.99%), POMO (3.16%), and LEHD (3.65%); (2) under constant capacity (Q=50Q=50), it generalizes zero-shot to N=1000N=1000 with 3.26%–3.77% gap (and 4.08% on 100% unseen customers); and (3) the 27.87% degradation on Table 5 CVRP1000 is specifically a capacity-shift artifact driven by kattn=20k_{\text{attn}}=20 vs. ∼50\sim 50 customers/cluster at Q=250Q=250.

Please also see G1 for a more comprehensive response.

W2 and Q1: Reconciling TAM's Protocol and Runtime

Response to Q1a: As stated in Appendix K (Line 1340), the official code and pretrained weights for TAM were not publicly available. Therefore, we cited their published numbers rather than running TAM on LEHD's instances.

Reconciling Q1b: Thank you for your detailed study of Table 5. You are completely right on both counts.

Table 1 from the TAM paper reports raw tour lengths, rather than percentage gaps. We computed the gaps relative to their reported LKH-3 baseline (16.08 vs. 15.58 on CVRP100, and 46.34 vs. 46.44 on CVRP1000). However, when transcribing the CVRP1000 runtime, we inadvertently copied LKH-3's per-instance runtime of 6.2s from GLOP (with one-decimal rounding in Table 1 of GLOP (Ye et al., 2024b)) rather than TAM-LKH3's reported per-instance runtime of 1.82s. Indeed, TAM and GLOP both report per-instance runtimes. We will identify TAM as a cited result under a different protocol—(Q=200Q=200), 100 instances, and add a clear footnote. This correction does not affect our fixed-support experiments or component ablations. We respectfully push back on the conclusion that this single cited literature value materially weakens confidence in our evaluations. We urge the reviewer to look at the bigger picture in Table 5:

  1. Every other baseline in Table 5 was either executed directly on the exact same 128 LEHD instances, or cited directly from LEHD's results. None of our primary ablations involve TAM.
  2. More importantly, once the mismatched TAM row is set aside, it turns out that classical Fisher-Jaikumar (FJ) with LKH-3 achieves 3.7493.749% and outperforms the evaluated neural configuration in Table 5 on LEHD CVRP1000. On LEHD CVRP1000, FJ beating modern autoregressive solvers on CVRP1000 strongly validates the classical CFRS foundation that our paper modernizes.
AuthorsOpenReview ↗

Response to Reviewer R6p9 (Part 2/2)

W3: Evaluation on One 3,000-Location Support

Our unseen location experiment (Table 1 and Appendix J) demonstrates generalization beyond the fixed spatial support - nodes outside of this support have their embeddings computed through interpolation without retraining. Specifically, we draw 10,000 completely independent locations and evaluate instances with 100% unseen customers with interpolated embeddings. This provides strong evidence for generalization to the standard CVRP benchmark under the i.i.d. setting, which would also be applicable to your specific question on this method working on independent supports. Regardless, if we were to take a more practical approach as suggested by Bengio et al., (2021), we indeed want to focus only on solving TSPs for Montreal and no other city. If one were interested in another city, a separate model on that support could be trained. We reiterate that this is indeed the setting that we study, and we also show that our method can potentially be generalized to the standard CVRP i.i.d. setting. Nonetheless, we will highlight this as a limitation. Please also see Global Response G3.

W4: Learned Seeds and FJ Costs Performs Better

We highlighted this prominently in our abstract, as well as in Section 3 (Line 366 onwards). This is actually a valuable insight and future research direction, and not a weakness of the framework. Our current results show that learned costs work best at smaller instance sizes (N=100,200N=100, 200), but FJ costs work better at larger instance sizes (N=500,1000N=500, 1000). FJ costs explicitly encode depot-dependent insertion costs, whereas our learned costs are distances between customer and seed embeddings. The depot is indeed included as an input token but we do not explicitly build in our architecture the depot insertion cost. This difference is one possible explanation for the different generalization behavior - as the number of tokens grows, it is hard for the depot token to have a significant effect. Interesting future work could perhaps compute an FJ cost but in the embedding space.

W5: Fleet-Size Sensitivity

Please see Global Response G5.

Q2: Gain from Differentiable OT

Please see Global Response G2.

Thank you for taking the time to respond in your own words. I will raise my score from 1 to 2. My main concern remains generalization to larger instances on the standard CVRP benchmark, where vehicle capacity increases with instance size.

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

This paper focuses on a specially formulated CVRP where customers are selected from a fixed set of locations. Neural CFRS is proposed to employ neural networks to accomplish the clustering task within the "cluster-first, route-second" framework of the classical Fisher-Jaikumar algorithm, thereby decomposing the CVRP  into several TSP subproblems. The method first trains and freezes the spatial priors (embeddings) of all candidate customers. During inference, these embeddings are reused based on the indices of activated customers, or interpolated to generate spatial embeddings for unseen customers.  Then, based on this spatial encoding, two networks are trained to perform seed selection and output assignment costs in sequence. Finally, Then, based on this spatial encoding, two networks are trained to perform seed selection and output assignment costs in sequence. Extensive experiments verify the effectiveness of spatial priors as well as learnable seeds and assignment costs.

Critical strengths

The method is reasonable and intuitive. It formulates clustering as a Capacitated Assignment Problem defined by assignment costs, and the approach of using neural networks to estimate assignment costs is relatively novel. Ablation experiments demonstrate that the main components, such as spatial priors, learnable seed selection and assignment costs, indeed yield certain advantages over non-learning counterparts.

Critical weaknesses
  1. Most results in the experiments are based on sampling with 3000 points. How do other neural solvers perform under such data? Besides, the neural methods compared on the standard benchmarks are relatively outdated (mainly from 2020, 2023 and 2024). Table 2 and Table 5 also show that the model suffers from poor generalization ability.

  2. Although the main structure of the paper is well organized, the logic of some sentences is disjointed. For example, after listing existing methods in the Introduction, there is an abrupt statement: "Joint partition prediction therefore removes these arbitrary orderings from the neural prediction task." which lacks a clear logical connection with the surrounding context. Propositions 1–3 are first mentioned on Page 3 without indicating where they appear, and they do not show up until Page 6. In addition, this paper does not include a dedicated related work section.

Questions for authors
  1. As suggested in W1, please provide the results of other neural solvers under the current settings and add updated comparison baselines. This is my main concern.

  2. Could you present the time and proportion of each stage of the method during inference (phase 1, 2, 3, and solving the TSP subproblem), and identify which part accounts for the major computational overhead?

2 comments
AuthorsOpenReview ↗

Response to Reviewer mwjx

Thank you for your constructive review and for highlighting the intuitiveness and novelty of Neural CFRS. We address each of your points below.

W1 and Q1: Fixed 3,000-point Support, Other Neural Solvers, Baseline Recency, Generalization

Our goal is not to propose an incremental modification to sequential autoregressive solvers and to further push SOTA results. Instead, we focused on an orthogonal, non-autoregressive paradigm that resembles real-world logistics more closely. Modeling the fixed spatial support X\mathcal{X} is a deliberate design decision and gives us two benefits. First, it is a better represenation of real-world logistics. Second, it enables to learn Ψ\Psi, which can be reused across problem instances. Ψ\Psi also enables us to achieve E(2)E(2) invariance. When combined with non-autoregressive decoding of clusters, the model is able to achieve E(2)E(2) invariance, route permutation invariance, and tour-reversal invariance by construction - removing the need for data augmentation. This enables us to train our models under 3 hours with 30 epochs, as well as the single layer model. In addition, we have shown in Table 1 that Ψ\Psi generalizes to 100% unseen customer nodes. These results in itself are promising, and we look forward to testing these ideas in existing autoregressive solvers and enabling these methods to be E(2)E(2) invariant. We indeed alluded to this on Line 475.

With regards to your note on other neural solvers on this data, we already test Neural CFRS in the standard CVRP setting, and show that Neural CFRS with raw coordinates (no Ψ\Psi) achieves 2.73%, outperforming greedy POMO (3.16%), BQ-NCO (2.99%), and greedy LEHD (3.65%). We selected these baselines alongside NCC, TAM, and GLOP as the canonical representatives of greedy autoregressive and neural clustering solvers that match Neural CFRS (single forward pass, non-autoregressive inference). We do not claim universal SOTA over recent search-heavy i.i.d. solvers. In the revision, we will expand our Related Work section to better contextualize recent 2025–2026 NCO solvers alongside our orthogonal fixed-support, symmetry-abstracted paradigm.

Furthermore, our unseen nodes experiment provides evidence that Neural CFRS can be generalized to the standard setting, and this would make interesting future work and thus enable an apples-to-apples comparison of Neural CFRS with contemporary methods.

On outdated baselines and SOTA comparisons, we respectfully push back on treating standard benchmark instances as the sole bar for contribution, as explicitly noted in the ICLR Reviewer Guidelines. Neural CFRS takes an orthogonal research path and is a method that abstracts the three symmetries of the Symmetric Euclidean CVRP - we believe that this is something worth discussing in this field.

On generalization, we have two points to make. First, in Table 2, Neural CFRS does actually generalize to larger instances in our setting, where the capacity is fixed. For our full model, all gaps are below 5%. For the single layer model, all gaps are below 8%. Second, in Table 5, Neural CFRS has poor generalization when the capacity changes on larger instances. We hypothesize that this is due to the kk-NN attention that we use in our models Specifically, Neural CFRS uses an attention neighborhood of size 2020 (see Appendix B and F). Given the demand distribution and the fixed capacity of Q=50Q=50 in our setup, a cluster would have 10 customers on average, which is smaller than the attention neighborhood. In contrast, at Q=250Q=250, a cluster would have 50 customers on average, which is larger than the attention neighborhood, and thus potentially explains the poor performance here. Future work should explore how to address this limitation, which we point out in Line 472.

Q2: Inference Runtime Breakdown Across Stages

Please see Global Response G4.

W2: Logical Flow, Proposition Placement, and Related Work Section

Thank you for flagging these presentation points:

  1. Introduction transition. Agree. We will add a connecting sentence to bridge that gap you pointed out.
  2. Placement of Propositions 1-3. Placing Lemmas 1-2 on p. 3 and Propositions 1-3 on p. 6 was deliberate. We start by stating two obvious Lemmas for the Symmetric Euclidean CVRP that motivate Neural CFRS. We then state Propositions 1-3 later, which proves the invariance for our specific Neural CFRS method, which must be defined in Sections 2.1 to 2.4 before their properties can be stated. To avoid any disconnect, we will add a note on p. 3, directing readers to Section 2.4 and Appendix D.
  3. Dedicated Related Work Section. We decided to integrate the literature into the introduction to motivate the CFRS formulation directly. We can reorganize this into a standalone Related Work section in the final manuscript.

Thank you for your reply. I understand that on standard CVRP datasets, CFRS may not outperform the state-of-the-art recent search-heavy i.i.d. solvers. What I want to know is whether CFRS can still show advantages when these pre-trained SOTA models are tested directly under your setting with 3000 fixed nodes. For a specific scenario, if a pre-trained neural solver can achieve excellent results without any fine-tuning, then I would question the rationale and significance of training CFRS specifically for this fixed point set.

Comments on the paper

4 comments
AuthorsOpenReview ↗

Global Response (Part 1/3)

We sincerely thank all three reviewers for their detailed feedback. Several concerns evaluate Neural CFRS primarily through the lens of general-purpose i.i.d. CVRP benchmarks, whereas our paper investigates a distinct recurring-geography paradigm and symmetry-abstracted non-autoregressive decomposition. Below, we clarify our scope and training/parameter efficiency (G1), report the requested OT ablation (G2) and per-stage inference runtime breakdown (G4), synthesize existing evidence on unseen-node generalization (G3) and fleet-size sensitivity (G5), and summarize our planned manuscript revisions (G6).

G1: A New Paradigm for Recurring Routing and Training Efficiency (mwjx, GkLD)

Most NCO solvers for the CVRP have some sort of sequential element to it - this was discussed in our introduction. Specifically, the routes are constructed either node-by-node (POMO, BQ-NCO, LEHD) or cluster-by-cluster (TAM, GLOP), on CVRP instances that have coordinates that are sampled i.i.d. However, in real-world logistics, operators route over the same city and depot every day with a fleet of vehicles that likely have the same fixed capacity. What changes on a day to day basis is the active customers and the demand of each customer. We do not claim that our method directly solves real-world logistics problems. Rather, it takes a principled first step toward this recurring operational setting.

Neural CFRS explores an orthogonal research direction compared to existing NCO solvers through three perspectives:

  1. Reusable spatial representations for recurring routing. This is the first contribution we state in our manuscript. Ψ\Psi is learned once and then reused across all instances.
  2. A non-autoregressive Fisher–Jaikumar framework with joint symmetry abstraction. This is the second contribution we state in our manuscript. Neural CFRS by design inherits the three symmetries of the CVRP - which allows us to train with zero data augmentation.
  3. Learning capacity constraints via Differentiable OT. Existing methods handle capacity primarily through masking infeasible nodes. In contrast, our differentiable OT layer enables a model that provides capacity-aware supervision and can be trained in an end-to-end manner.

As emphasized in the ICLR Reviewer Guidelines, SOTA results are not required for a valuable contribution, and universal SOTA is not our claim, though our model indeed shows outperformance on standard CVRP100 when compared to BQ-NCO, LEHD, and POMO, under the greedy setting. Rather, we start with the three symmetries of the Symmetric Euclidean CVRP, and build from the ground up a method that respects these symmetries. Neural CFRS abstracts E(2)E(2) transformations (if Ψ\Psi is used), inter-route vehicle permutations, and intra-route tour reversals entirely by construction. This yields major computational benefits:

  1. Zero symmetric data augmentation and fast training: Pretraining Ψ\Psi takes under 30 minutes (Appendix B), and end-to-end routing training on 1M N=100N=100 instances takes just 30 epochs (batch size 256) in under 3 hours (Appendix F) - requiring substantially fewer epochs than autoregressive baselines such as BQ-NCO (500 epochs, batch size 1024) or GLOP (4 hours for 30 epochs on the same hardware, Appendix K, Line 1363).
  2. Extreme parameter efficiency: Offloading geometry properties of the routing environment (i.e. the city) into Ψ\Psi allows a 1-layer model with just 682K parameters (one layer each in ST and CT) to maintain ∼5%\sim 5\% routing gaps up to N=1000N=1000 (Table 2a, Table 4).

We hope the reviewers and AC will evaluate our work from this perspective.

G2: Ablation: Differentiable OT vs Direct Supervision (R6p9, GkLD)

Following the suggestion of reviewers R6p9 and GkLD, we ablated the OT layer on the model with Ψ\Psi and LBCE\mathcal{L}_\text{BCE}. We removed LOT\mathcal{L}_\text{OT} only while keeping everything else identical:

  • On the validation data, we found that the performance is virtually unchanged for N=100N=100.
  • However, the performance at N=1000N=1000 is drops from ≈3−4%\approx 3-4\% to ≈6−8%\approx 6-8\% across all epochs during training. Removing OT supervision worsens size generalization in these validation runs, while performance at the training size remains similar.
AuthorsOpenReview ↗

Global Response (Part 2/3)

G3: Fixed Spatial Support Generalizes to 100%100\% Unseen Nodes (mwjx, R6p9)

Using a 3,000-node support does not restrict Neural CFRS to only solving instances that are sampled from this fixed support. In a real-world setting, it is easy to see how a business may acquire a new customer, and thus may need to route the fleet on certain nodes outside of this support. In the unseen nodes experiments (Table 1 and Appendix J), we sample 10,000 independent locations outside of the support and evaluate instances where 100%100\% of test customers are completely unseen locations. The node embeddings for these unseen customers are computed via using 5-nearest neighbors in the original 2D coordinates, with a inverse distance weighted average. The performance is relatively maintained without retraining (see Table 1). These are promising results that suggest that the spatial support can be extended to the standard CVRP test setting and would be interesting future work.

G4: Per-Stage Inference Runtime Breakdown (mwjx, GkLD)

Reviewers mwjx (Q2) and GkLD (Q3) asked for the breakdown of runtimes of each stage during inference. Below is the breakdown for our primary model (Ψ+LBCE\Psi + \mathcal{L}_{\mathrm{BCE}}, corresponding to the first block of Table 3, evaluated across 10,000 instances at N=100N=100 and 128 instances at N∈{200,500,1000}N \in \{200, 500, 1000\} with 16-core CPU parallelism for CAP/LKH-3, GPU for the neural + OT parts):

Size (# inst.)DecodingGap (%)Neural + OT (s / %)Gurobi CAP (s / %)LKH-3 (s / %)Total (s)
N=100 (10,000)Exact3.030%14.63 s (18.9%)16.41 s (21.1%)46.56 s (60.0%)77.60 s
Sparsified3.239%14.40 s (19.6%)12.30 s (16.8%)46.73 s (63.6%)73.44 s
Hard Assign.3.759%14.63 s (19.4%)14.91 s (19.8%)45.76 s (60.8%)75.30 s
N=200 (128)Exact3.877%1.18 s (21.7%)2.01 s (37.2%)2.23 s (41.1%)5.41 s
Sparsified3.787%1.17 s (23.0%)1.63 s (31.9%)2.31 s (45.1%)5.12 s
Hard Assign.4.866%1.19 s (30.3%)0.75 s (19.0%)1.99 s (50.7%)3.92 s
N=500 (128)Exact4.540%3.04 s (12.2%)18.44 s (74.2%)3.36 s (13.5%)24.83 s
Sparsified4.458%3.02 s (8.6%)28.86 s (82.0%)3.33 s (9.5%)35.21 s
Hard Assign.4.788%2.72 s (5.5%)43.32 s (87.9%)3.23 s (6.5%)49.27 s
N=1000 (128)Exact7.630%11.13 s (3.1%)338.55 s (94.2%)9.82 s (2.7%)359.49 s
Sparsified9.555%10.89 s (2.7%)389.88 s (95.0%)9.46 s (2.3%)410.24 s
Hard Assign.3.768%10.72 s (1.8%)590.15 s (96.8%)8.99 s (1.5%)609.85 s

In general, the solve time for the CAP increases from N=100N=100 to N=1000N=1000. Specifically, LKH-3 dominates at N∈{100,200}N \in \{100, 200\} (41%–64%), while Gurobi CAP dominates at N∈{500,1000}N \in \{500, 1000\} (74%–97%), with Neural+OT staying under 11.2s (<3.1%) even at N=1000N=1000. We expect the runtime breakdown be generally similar across our ablations, with some exceptions. For example, in Table 3, the best result of 3.26%3.26\% on N=1000N=1000 had a runtime of 1240s, which we discuss in Appendix H, Line 1177 under "Iterative Fallback". We will include this breakdown and revise Appendix F in the final manuscript.

G5: Flexible Fleet-Size Selection and Low Sensitivity (R6p9, GkLD)

In Appendix L and Table 7, we already evaluate a flexible fleet-size policy. We solve at both Kmin⁡=⌈∑idi/Q⌉K_{\min} = \lceil \sum_i d_i / Q \rceil and Kmin⁡+1K_{\min}+1, retaining the shorter tour (denoted as "BB" in Table 7). Zooming out across all 96 configurations in Table 7 shows that Neural CFRS is largely insensitive to fleet size. In the constant capacity configuration alone, 40 of 48 configurations (83.3%83.3\%) change by <0.4%<0.4\% when adding Kmin⁡+1K_{\min}+1. Under Standard Capacity, all 48 of 48 change by <0.4%<0.4\% (and at N=1000N=1000, all 12 change by 0.00%0.00\%). We chose to focus on analyzing the worst performing instances of N=100,200N=100, 200, and this was discussed in Line 1519. While adding an extra vehicle and taking the best does improve overall performance at N=1000N=1000, it is an open question as to whether or not running Gurobi CAP with a longer time limit can improve performance. Comparing BB against a 2x Gurobi time limit on KminK_\text{min} is left for future work.

AuthorsOpenReview ↗

Global Response (Part 3/3)

G6: Summary of Planned Manuscript Updates

  1. The OT ablation (G2) and runtime breakdown (G4) will be added to additional appendices. Appendix F will also be revised based on the runtime breakdown.
  2. We will correct the transcribed TAM-LKH3 per-instance runtime (1.82 s1.82\text{ s} vs. LKH-3's 6.2 s6.2\text{ s}) and add a clear footnote distinguishing TAM's cited protocol (Q=200Q=200, 100 instances, per-instance runtime) from the standard 128-instance Q=250Q=250 LEHD rows - where classical FJ + LKH-3 (3.749%3.749\%) outperforms every evaluated neural baseline on LEHD CVRP1000.
  3. Add the logical bridge sentence in Section 1, add forward pointers on p. 3 to Section 2.4 and Appendix D for Propositions 1–3, reorganize literature into a dedicated Related Work section, and expand our Limitations section.
AuthorsOpenReview ↗

Human Written Rebuttals

We thank the AC and the reviewers for their time in reviewing our submission. We apologize for not submitting rebuttals earlier - as you can see from what we posted, there was indeed a lot of content to go through. We tried our very best to write the rebuttals on our own, using AI as a tool to help instead of write entirely. We hope these human rebuttals are an enjoyable read, in the age of AI.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.