acceptodds
Under review as a conference paper at ICLR 2027

Rethinking Positional Encoding for Neural Vehicle Routing

Abstract

Transformer-based models have become the dominant paradigm for neural combinatorial optimization (NCO) of vehicle routing problems (VRPs), yet the role of positional encoding (PE) in these architectures remains largely unexplored. Unlike natural language, where tokens are uniformly spaced on a line, routing solutions exhibit several properties that render standard NLP positional encodings inadequate. In this work, we formalize three such structural properties that a routing-aware PE should respect, namely anisometric node distances, cyclic and direction-aware topology, and hierarchical depot-anchored global multi-route structure, combining them with a unifying design principle of geometric grounding. Guided by these criteria, we analyze and compare PE methods spanning NLP, graph-transformer, and routing-specific families and propose a hierarchical anisometric PE that combines a distance-indexed, circularly consistent in-route encoding with a depot-anchored angular cross-route encoding. Extensive experiments across diverse VRP variants demonstrate that geometry-grounded PE consistently outperforms index-based alternatives, with gains that transfer across problem variants, model architectures, and distribution shifts.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Neural Combinatorial Optimization, Vehicle Routing Problem, Positional Encoding, Transformers

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_Zu7dOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies positional encoding for neural vehicle routing, with a particular focus on improvement-based solvers that repeatedly encode a complete current solution. The paper argues that conventional index-based positional encodings do not adequately reflect three properties of routing solutions: non-uniform along-route distance, cyclic and direction-dependent route topology, and the multi-route structure around the depot. Based on these observations, the authors propose a hierarchical encoding composed of an in-route positional encoding (IPE), which represents normalized cumulative travel distance using periodic Fourier features, and a cross-route positional encoding (XPE), which represents the depot-relative polar angle of each customer.

The empirical study is organized in three stages. First, the proposed encoding is compared with NLP, graph-transformer, and routing-specific positional encodings under DACT on CVRP, VRPTW, and PDTSP. Second, IPE+XPE replaces the native positional component of NDS and is evaluated on CVRP, VRPTW, and PCVRP with up to 2,000 customers. Third, the same encoding is inserted into N2S for PDTSP and evaluated under several distribution shifts and on CVRPLib. The controlled experiments generally favor IPE+XPE, while the improvements over NDS at large scale are modest.

Critical strengths
  1. The paper provides a systematic and controlled evaluation of positional encodings for neural routing. Under a fixed DACT backbone, it compares NLP-based, graph-based, and routing-specific encodings, with additional probing and ablation studies to separate the effects of cumulative distance, Fourier mapping, and cross-route geometric information.

  2. The proposed encoding is evaluated beyond the initial backbone, including NDS on CVRP, VRPTW, and PCVRP with up to 2,000 customers, and N2S on PDTSP. The experiments also examine distribution shifts and report results under matched computational budgets. Although the large-scale gains are modest, the cross-backbone results provide useful evidence that the benefits are not limited to a single solver architecture.

Critical weaknesses
  1. The interpretation of the proposed hierarchical positional encoding remains debatable. XPE encodes the depot-relative angle of each customer and remains unchanged when that customer is reassigned to another route; it therefore provides a static geometric cue rather than explicit route-membership information. Although the paper acknowledges this distinction and includes additional analyses, the evidence supports the usefulness of depot-centered geometric information more directly than it supports the broader claim of encoding cross-route hierarchy.

  2. The large-scale improvements over NDS are small (0.07–0.34 percentage points in eight of nine settings), and the experiments use only three independent training seeds. The paired bootstrap intervals quantify test-instance variability conditional on the trained models, rather than fully accounting for training variability. Given the small margins, stronger evidence across independent training runs would increase confidence in the robustness of the reported gains. In addition, the validation is restricted to solution-conditioned improvement/search methods, so the conclusions should not be generalized to constructive neural routing solvers.

Questions for authors
  1. Section 3 defines D1 in terms of cumulative travel distance, but Table 2 classifies SPD as partially satisfying D1, while Appendix F states that SPD is computed on an unweighted route graph and therefore measures hop distance rather than travel distance. How is this classification consistent with the paper's own definition of D1?

  2. In Table 3, the D3 correlation is 0.396 for XPE alone but 0.384 for IPE+XPE. Given that XPE is static and does not explicitly encode route membership, what exactly does the D3 probe validate: route-membership information or a geometric proxy correlated with it? How should this result be reconciled with the claim that the downstream ranking broadly tracks the probing results?

  3. The improvements over NDS are only 0.07–0.34 percentage points in the eight settings reported as statistically distinguishable. Since the paired bootstrap intervals are conditional on the trained models and only three training seeds are used, can the authors provide paired seed-level differences or a seed-aware uncertainty analysis to better establish the robustness of these gains?

  4. DACT (Ma et al., 2021) already introduced cyclic positional encoding for routing. What is the precise methodological contribution beyond replacing discrete indices with cumulative-distance encoding and adding depot-relative angular features? Which aspect establishes a general design principle rather than a problem-specific combination of handcrafted features?

  5. Table 3 uses “NoPE,” Table 4 uses “No PE,” and the main text also uses “no-PE baseline.” Similarly, “IPE + XPE” and “IPE+XPE” are used in different places. Please standardize these forms throughout the paper.

4 comments
AuthorsOpenReview ↗

Authors response (1/3)

We thank the reviewer for the careful reading and the detailed questions. We address each point below.

TL;DR.

  • W1 Hierarchy. We agree with the reviewer and narrow the claim: "hierarchical" now means a solution-conditioned within-route position (IPE) plus a depot-anchored frame shared by all routes (XPE), and D3 is renamed "depot-anchored multi-route structure". Explicit, dynamic membership signals were weaker than XPE in our tests (Tables 12, 14), and we list them as complementary future work.
  • W2 & Q3 Seed-aware uncertainty. We add a seed-aware analysis for all nine Layer 2 cells (cross-seed pairs and a hierarchical bootstrap over training seeds and test instances; Table 20, Appendix X). Cells where three seeds do not separate the encodings are now reported as such in the main text.
  • W3 Scope. The empirical claims are limited to improvement-based solvers. We removed re-encoding construction methods from the scope in Section 2, and Section 1 now states the scope before the contributions.
  • Q1 SPD and D1. We correct Table 2, Section 3, and Appendix E. No conclusion changes.
  • Q2 D3 probe. The probe measures agreement with route structure in near-optimal solutions, not the current assignment. We state this in Section 5.2 and Appendix F, and replace "broadly tracks" with a family-level statement.
  • Q4 Beyond DACT's CPE. We encode travel distance rather than the index (from 3.85% to 1.48% with the mapping fixed, Table 11), and we choose reversal symmetry per problem by construction (Table 13). Both choices are ablated separately, and Section 2 credits earlier uses of the depot.
  • Q5 Terminology. We now use "No PE" and "IPE+XPE" throughout and have unified "Laplacian PE".

W1 Interpretation of the hierarchical encoding.

We agree with the reviewer: XPE depends only on the instance, does not encode route membership, and does not change when a customer is reassigned. What it encodes is a depot-anchored geometric prior for how routes are organized, and we have narrowed the claim to exactly that.

  • The depot-anchored angle is the classical structural prior for how routes are organized, not an arbitrary geometric cue. Sweep [1] and petal methods [2] build routes as angular sectors around the depot, and the measured HGS solutions largely follow this structure: the customer angularly nearest to a given customer is on the same route for 82% of customers on CVRP-100 and 76% on VRPTW-100 (Appendix Q). XPE encodes this structure directly, i.e., the cross-route organization that good solutions converge to.
  • We tested explicit route membership: as a replacement for XPE it is weaker, and as an addition to IPE+XPE it gives only a small further gain. Membership signals that are recomputed after every move (a same-route attention bias and route pooling, both invariant to route renumbering) improve on IPE alone but are weaker than XPE, and adding the same-route bias on top of IPE+XPE helps only marginally (from 1.16% to 1.12% on CVRP-100, in Table 14). Per-route angular aggregates, which inject the current assignment, are also worse than the per-node static angle (Table 12). For the downstream task, the static depot-anchored frame is the more useful representation of cross-route structure.
  • XPE behaves like a route-structure prior should. Its gain is largest when routes occupy separated angular sectors and shrinks, but stays positive, as routes overlap (from 0.41 to 0.23 pp from the lowest to the highest overlap tercile, in Table 14).

We agree the paper should make this precise, so the claim matches the evidence exactly:

  • We define "hierarchical" explicitly as the two levels of the encoding: a solution-conditioned within-route position (IPE) and a depot-anchored global frame shared by all routes (XPE).
  • D3 is stated as "depot-anchored multi-route structure", and Section 4.2 explains the sweep/petal motivation above.
  • Limitations note that explicit, dynamic membership encoding is complementary (Table 14 shows a small further gain) and left for future work.

[1] B. E. Gillett and L. R. Miller. A heuristic algorithm for the vehicle-dispatch problem. Operations Research, 22(2):340–349, 1974.

[2] B. A. Foster and D. M. Ryan. An integer programming approach to the vehicle scheduling problem. Operational Research Quarterly, 27(2):367–384, 1976.

AuthorsOpenReview ↗

Authors response (2/3)

W2 & Q3 About margins and seed-aware uncertainty.

We agree with the reviewer that the current results do not fully capture the training variability. We now do a seed-aware analysis for all Layer 2 cells.

We compare IPE+XPE against SPD, on average the strongest alternative PE inside NDS (Table 16). The question our paper asks is which encoding works best inside the same backbone, and SPD is trained and evaluated with exactly the same pipeline, the same 3 training seeds, the same 1,000 test instances, and the same evaluation seeds.

This makes the seed-level comparison clean, and it is also the harder test in most cells: in 7 of the 9 cells, the margins over SPD are smaller than those over native NDS.

What we report:

  1. Seed-level differences. Δ\Delta = mean over training seeds of the test-set mean gap of SPD, minus the same quantity for IPE+XPE. Positive favors IPE+XPE.
  2. Cross-seed pairs. Since training seeds are independent across methods, we compare every IPE+XPE seed with every SPD seed.
  3. Seed-aware 95% CI. A hierarchical bootstrap that resamples training seeds first and then test instances, although with three seeds the seed-level resampling is coarse.
Cellmean Δ\Delta (pp)pairs favoring IPE+XPEseed-aware 95% CI
CVRP-500+0.046/9[−0.04, +0.12]
CVRP-1000+0.099/9[+0.02, +0.16]
CVRP-2000+0.129/9[+0.04, +0.20]
VRPTW-500+0.058/9[+0.01, +0.09]
VRPTW-1000+0.046/9[−0.05, +0.13]
VRPTW-2000+0.189/9[+0.09, +0.27]
PCVRP-500−0.013/9[−0.08, +0.06]
PCVRP-1000+0.099/9[+0.03, +0.15]
PCVRP-2000+0.199/9[+0.10, +0.28]

With training variability included, the seed-aware interval excludes zero in 6 of the 9 cells, including all three cells at N=2000N=2000. In the other three (CVRP-500, VRPTW-1000, PCVRP-500), three seeds do not separate the two encodings, and we now report them as such in the main text.

In Layer 1, small margins are not an issue: the margin over SPD is 0.64–0.91 pp, several times the seed SD (Table 15, Appendix R).

W3 Improvement-based vs. construction-based solvers.

Agreed. The abstract, contribution 4 and Section 6 already limited the empirical claims to improvement methods, but Section 2 of the submitted version also listed re-encoding construction methods in the scope. We removed that, and Section 1 now states the scope before the contributions. Improvement solvers encode a complete, ordered solution at every step, so positional representation is an explicit design choice there, while construction encoders mostly need no PE at the encoding stage (Section 2). The evaluated IPE assumes a complete current route (Appendix T).

Q1 SPD and D1.

Thanks for catching this, and the reviewer is right. Our criteria in Appendix E are: ✓\checkmark = a function of travel distance; ∼\sim = a graph or hop distance that correlates with travel distance through the solution structure; ×\times = indices only. Our route graph is unweighted and all routes share the depot, so for two customers on the same route, which is what D1 is about, the SPD hop distance is exactly the cyclic index offset. By our own criterion, SPD should therefore be ×\times on D1.

We correct Table 2 and Section 3 accordingly, and move the full criterion into Section 3. SPD still scores high on the D1 probe (Table 3) because hop count correlates with travel distance on near-uniform instances, but its input carries no edge lengths.

Our conclusions do not depend on this label. IPE is still the only encoding that satisfies D1. And we test the distance signal directly: with the Fourier mapping fixed, replacing index with cumulative distance cuts the gap from 3.85% to 1.48% on CVRP-100 (Table 11).

AuthorsOpenReview ↗

Authors response (3/3)

Q2 What the D3 probe measures.

The D3 probe checks whether an encoding separates node pairs that end up on different routes in a near-optimal solution. It does not read the current route assignment. So for XPE, a positive value means that, in good solutions, customers on different routes lie further apart in angle than customers on the same route, which is the cross-route structure discussed in W1. We now state this in Section 5.2 and Appendix F.

The small drop for IPE+XPE comes from how the probe works: it uses the distance between the concatenated vectors, and the IPE half carries little D3 signal, so it dilutes the XPE part. Downstream, IPE+XPE beats XPE alone in all three Layer 1 settings (Table 4: 1.16% vs. 1.67%, 2.97% vs. 3.33%, 1.87% vs. 2.30%).

On the probe vs. downstream results, we agree "broadly tracks" was too strong. The probe tells which families of encodings carry which signal, not an exact ranking: NLP-style index encodings (SIN, APE, RoPE, RPE, ALiBi) are the weakest downstream, graph-transformer and cyclic encodings lie in between, and IPE+XPE, at or near the top on all three, is the best. We revise the sentence accordingly.

Q4 Contribution beyond DACT's cyclic PE.

DACT's CPE makes the index cyclic. Our main point is that the index is not the best signal to begin with. There are three differences:

  1. What is encoded. With the cyclic mapping held fixed, simply replacing the index with the normalized cumulative distance cuts the CVRP-100 gap from 3.85% to 1.48% (Table 11), while DACT's CPE reaches 2.37%. Feeding the same distance through a linear map instead gives 2.50%, so both the distance signal and the periodic mapping matter. This is the general principle we argue for: a routing PE should be built from geometric quantities of the solution (travel distance, depot angle), not from indices. We restore the paragraph stating it in Section 3.
  2. Symmetry by construction. Integer harmonics make every band close exactly for any route length, and reversing a route just flips the sign of the sine channels. This gives a principled, per-problem choice between a direction-aware and a direction-invariant variant. The prediction holds: invariance is fine on CVRP but hurts on VRPTW (2.97% → 4.04%) and PDTSP (1.87% → 3.71%) (Table 13).
  3. The desiderata, taxonomy, probe, and controlled comparison of 13 encodings form, to our knowledge, the first systematic study of PE for routing, and the same module works unchanged in DACT, N2S, and NDS.

About "handcrafted": every PE, learned or not, builds in an inductive bias, including sinusoidal PE and DACT's CPE. The real question is which invariances it encodes. Ours follow from stated properties, and each is ablated separately. Section 2 credits earlier related uses of the depot (a depot-aware, rotation-based route-level PE in DPN; depot angles as input features in GLOP, ELG, L2C-Insert) and the Fourier-feature map. Our claim is the per-node angle combined with a distance-normalized within-route phase recomputed after every move, the reversal-symmetry switch, and the controlled tests of both (Tables 11–14).

Q5 Terminology.

Thank you. We now use "No PE" and "IPE+XPE" (without spaces) throughout the text, tables, and captions, and we also unified "Lap. PE" / "Laplacian PE".


We have also updated the manuscript. Changes are marked in blue in the revised PDF.

We are grateful for these detailed questions. We hope the revisions resolve the concerns and would welcome any further questions.

Hi, Reviewer Zu7d,

Thanks again for your hard work on paper review and constructive comments. As the rebuttal period is ending, if you have unsolved concerns, further questions, or just interesting points to share, please let we know. We are happy to have a discussion.

Best,

Authors

Reviewer_fNnKOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This paper studies positional encoding (PE) for neural vehicle routing problems. The authors argue that existing PEs do not fully capture three important properties of routing solutions: uneven distances between consecutive nodes, circular and direction-aware routes, and hierarchical structure across multiple routes. Based on these observations, they propose a dedicated PE with two components. The in-route positional encoding (IPE) uses cumulative travel distance and Fourier features, while the cross-route positional encoding (XPE) captures each customer's angular position relative to the depot. The paper also provides a taxonomy of existing PE methods and evaluates the proposed encoding on four VRP variants and three neural solver methods (DACT, NDS, and N2S). The results show improvements over existing PEs, although the gains on large-scale instances are relatively small.

Critical strengths
  1. The paper addresses an interesting question that has received relatively little attention in neural combinatorial optimization. I appreciate that the authors go beyond proposing another encoding and provide a taxonomy based on three structural properties of routing solutions. The proposed IPE+XPE is intuitive and closely follows these design principles. Overall, the paper offers a useful perspective on how positional information should be represented in neural routing models.

  2. The paper compares a wide range of positional encodings across different VRP variants and neural solver architectures. I particularly appreciate the ablation studies, which help isolate the effects of cumulative distance, Fourier mapping, directional symmetry, and cross-route information. The authors also report results across multiple training seeds, conduct statistical tests, and evaluate generalization under distribution shifts. These experiments provide sufficient evidence that the proposed encoding is effective in the settings considered.

Critical weaknesses
  1. While the proposed encoding improves solution quality in most settings, the gains over the original NDS method are relatively small. This raises questions about its practical impact. In addition, Table 4 does not report inference runtimes. HGS/LKH achieve better objective values than all neural methods in this table, but it is difficult to assess the quality-efficiency trade-off without timing information. Although the paper focuses on positional encoding rather than developing a new solver, a more complete runtime comparison would strengthen the experimental results.
Questions for authors

1.Could the authors report inference runtimes for the methods in Table 4, including HGS/LKH? Since the neural methods are evaluated with fixed improvement-step budgets, it would be helpful to understand their actual computational costs and whether the performance differences persist under the same wall-clock budgets.

4 comments
AuthorsOpenReview ↗

Authors response (1/2)

We thank the reviewer for the positive assessment of the taxonomy, the breadth of the comparison, and the ablations. We address the concerns below.

W1 Practical impact of the gains over NDS.

We agree, the in-distribution margins over NDS at scale are not significant enough. But we would like to put them in context.

  • Under a fixed backbone (Table 4), IPE+XPE reduces the gap of the strongest prior PE (SPD) on CVRP / VRPTW / PDTSP at 23–36% relative, and that of DACT's native cyclic PE by 34–51% relative. In N2S on PDTSP-101, replacing only the PE reduces the gap to LKH from 4.44% to 2.89% (Table 6).
  • The gain depends on the regime, and we now state where it is largest. It is largest on heterogeneous benchmarks such as CVRPLib X. In distribution, the largest Layer 2 margins are at N=2000N=2000 on VRPTW and PCVRP (0.34 pp each). The gain is smallest where search alone already closes most of the gap: in Layer 1 the margin over SPD shrinks from 0.64 to 0.37 pp with 5× more search steps, though the ranking is unchanged (Table 8). We add this characterization to the Discussion.
  • The gain comes at negligible cost. IPE is a cumulative sum along each route (O(N)O(N) per step) and XPE an angle computed once per instance. On CVRP-2000, they take < 1% of the per-step time, and the number of search steps within the budget changes by < 1% (Appendix G). The module is a drop-in replacement; architecture and training are unchanged.
  • On heterogeneous benchmarks, the gains are larger. On CVRPLib X, the CVRP-500 checkpoints reduce the average gap to the BKS from 4.13% (native NDS) to 2.84%, improving on 82 of 84 instances, against 3.28% for the best alternative PE (SPD).
AuthorsOpenReview ↗

Authors response (2/2)

W2 & Q1 Inference runtimes and wall-clock-matched comparison.

Thank you for raising this. Table 4 compares encodings at a fixed number of improvement steps, because its purpose is to isolate the representation. The wall-clock-matched comparison is Table 5, which follows the NDS protocol: the same per-instance budget for all methods, with neural methods on one GPU and HGS on one CPU core.

We do not claim that neural search beats HGS in general. These budgets are short by OR standards, and HGS keeps improving with more time. But we do agree that the step-matched comparison of Table 4 should come with inference times, and that its ranking should be checked under equal wall-clock time.

We add the following results in a new Table 19 (Appendix W), referenced from Section 5.2 next to Table 4:

  1. Per-instance inference time under DACT of six encodings from Table 4 that cover every family (the 1,000 test instances batched on one GPU; the timer covers the full search, including PE computation and the 8× augmentation for CVRP and VRPTW, divided by the number of instances), and the runtime of HGS (PyVRP) and LKH-3 under their reference settings, with the hardware of each method stated (GPU vs. CPU cores).
  2. A wall-clock-matched comparison in which every DACT variant gets the time IPE+XPE needs for its step budget, so slower encodings complete fewer steps.
MethodCVRP-100 timegap (step-matched)gap (time-matched)VRPTW-100 timegap (time-matched)PDTSP-51 timegap (time-matched)
HGS / LKH (reference setting)20.0 s (1 CPU)––20.0 s (1 CPU)–15.0 s (1 CPU)–
No PE0.40 s11.81%11.79%0.45 s17.93%0.20 s15.84%
SIN0.40 s5.58%5.56%0.45 s7.52%0.22 s5.94%
DACT CPE0.41 s2.37%2.37%0.46 s4.55%0.21 s2.84%
Laplacian PE0.57 s2.12%2.47%0.63 s4.89%0.27 s3.41%
SPD0.52 s1.80%2.06%0.58 s4.21%0.25 s3.05%
IPE+XPE0.42 s1.16%1.16%0.47 s2.97%0.21 s1.87%

Under equal wall-clock time IPE+XPE stays first, and its margin over the graph-based encodings widens (over SPD: from 0.64 to 0.90 pp on CVRP-100), because SPD and Laplacian PE spend 19–36% more time per step.

At N=100, the goal of Layer 1 is not to compete with HGS; as the reviewer observes, HGS / LKH achieve better objective values than every DACT variant. Our claims about practical solution quality rest on Layer 2, where time is matched.


We have also updated the manuscript. Changes are marked in blue in the revised PDF.

We hope our response resolves your concerns, and we are open to any further discussions.

Thanks for the detailed response and additional experiments. The runtime results address my main concern. While I still think the gains over NDS at scale are relatively small, the overall contribution is worthwhile. I'll keep my score at 3.

Hi Reviewer fNnK,

Thank you! Happy to know that the extra information could resolve your main concern.

About the NDS, yes we understand, it is a quite powerful based model, the closer to the optimal, the harder to get improved. It's lucky that with our method we could still pushing the performance further. And this method is general, as you said, we hope our insights could be worthwhile for other community members.

Thanks again for the hard work on paper review.

Best,

Authors

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

This paper presents a systematic study of positional encoding (PE) for transformer-based neural vehicle routing. It formalizes three structural properties that routing solutions exhibit — varying distances between consecutive nodes, cyclic and direction-aware route topology, and a hierarchical depot-anchored multi-route structure — shows through measurement and probing that existing NLP, graph-transformer, and routing-specific encodings fail to capture them, and proposes a hierarchical PE combining a distance-indexed circular in-route encoding with a depot-anchored angular cross-route encoding. Across four VRP variants and three improvement-based backbones, the encoding outperforms thirteen alternatives, with gaps to classical references (HGS, LKH, best-known solutions) reported throughout; margins over the strongest baseline shrink at large scale but are resolved by paired per-instance tests in eight of nine settings.

Critical strengths

The first strength is the study design: a desiderata-driven taxonomy, parameter-free probing that verifies the taxonomy empirically, and controlled retraining of all 13 encodings with only the PE module varied, followed by deployment into the strongest available backbone with paired per-instance significance tests. This is close to a model of how an architectural component should be evaluated, and the honest reporting (small margins, PCVRP-500 exception, budget sensitivity) increases confidence.

The second strength is that the component-level conclusion is actionable and falsifiable: the index-vs-distance ablation (3.85% vs 1.48% with mapping held fixed) isolates the distance signal as the causal driver, and the direction-variant switch behaves exactly as the symmetry analysis predicts (harmless on CVRP, damaging on VRPTW/PDTSP), which is rare vindication of an inductive-bias argument in this literature.

Critical weaknesses

The main weakness of this paper concerns the evaluation of absolute solution quality. The only real-world evaluation is on 84 of the 100 CVRPLIB X instances, reporting gap-to-BKS — which for many X instances is itself heuristic. The XML100 set (10,000 instances of 100 customers, all with known (near) optimal solutions) exists precisely so that ML-oriented VRP methods can be evaluated against best known solutions, and it matches the paper's N=100 regime exactly. Not evaluating on XML100 leaves two gaps: (a) no optimality gap is ever reported for multiple distributions and their combinations; (b) the paired per-instance tests that carry the main Layer 1 conclusions rest on 1,000 synthetic instances, whereas XML100 offers an order of magnitude more real-benchmark instances at the same scale, which would sharpen exactly the small margins (0.3–0.9 pp) on which the central claims rest. This is an inexpensive experiment — the trained checkpoints exist — and its absence is the clearest fixable hole in the evaluation.

Questions for authors

Q1. The XML100 set on CVRPLIB (10,000 instances, 100 customers, all with best known solutions) is the standard ML-oriented CVRP benchmark and matches your Layer 1 scale exactly. Could you run your already-trained checkpoints, and ideally the NDS CVRP-500 checkpoints applied zero-shot — on XML100 and report the relative gap to the best known solutions? This would allow you to test OOD generalization ability. Q2. On the synthetic distribution shifts (low capacity, clustered), the margin over the strongest alternative PE is 0.03 pp and your own text says most of the benefit over native NDS is shared by non-native encodings. Is the accurate conclusion "IPE+XPE is the best of the tested encodings, but encoding choice matters less than backbone on shifted distributions"? If so, would you consider reframing the claims so readers do not over-generalize the CVRPLIB X margins?

6 comments
AuthorsOpenReview ↗

Authors response (1/3)

We thank the reviewer for the thoughtful review, and for recognizing both the study design and the falsifiable component-level conclusions. We address the points below.

TL;DR. On XML100, IPE+XPE has the lowest optimality gap among the tested encodings in both backbones and at every attribute level, with the margin growing with route length. We now separate single-factor synthetic shifts (small margins) from heterogeneous benchmarks (larger separation) in the abstract, Section 5.2 and the conclusion.

W1 & Q1 Evaluation on XML100.

We agree that this is the most informative additional experiment, and we thank the reviewer for the concrete suggestion. We especially appreciate that the reviewer provided a clear and detailed motivation for adding this test set, and we are happy to include it.

We evaluate our trained models and the baselines on XML100 and obtain the following results (gap to the proven optimal solutions):

MethodDACT trained on CVRP-100NDS trained on CVRP-500
Proven optimum0.00%0.00%
HGS-CVRP0.01%0.01%
AILS-II0.03%0.03%
SIN7.89 ± 0.29%1.41 ± 0.07%
Laplacian PE3.66 ± 0.21%1.21 ± 0.06%
SPD3.20 ± 0.19%1.19 ± 0.05%
Native PE of the backbone3.97 ± 0.22%1.48 ± 0.06%
IPE+XPE (ours)2.26 ± 0.15%1.01 ± 0.05%

Experimental setting:

  1. We directly apply the two trained models without any retraining or tuning. DACT uses the Layer 1 inference setting, and NDS gets 5 s per instance.
  2. The standard deviation is computed over 3 training seeds, as in Appendix R.
  3. Native PE: DACT's cyclic PE (CPE) for DACT, and the index-based PE for NDS.
  4. HGS-CVRP and AILS-II run for 10 s per instance on one CPU core. Costs follow the CVRPLib convention (each edge rounded to the nearest integer).
  5. For the learned models, the 0–1000 grid coordinates are divided by 1000 and demands are normalized by the vehicle capacity. IPE uses the continuous distances of these rescaled coordinates, and every final solution is re-scored with the CVRPLib convention.

The results show:

  1. We now report true optimality gaps. Every XML100 instance has a proven optimal solution, and IPE+XPE achieves the lowest gap among the five encodings we evaluate, in both backbones.
  2. Strong heuristics are near-optimal at N=100: HGS-CVRP has a mean gap of 0.011% (optimal on 88.6% of the instances) and AILS-II 0.026%. This suggests, but does not verify, that the Layer 1 CVRP gaps (relative to PyVRP-HGS on uniform instances) are close to optimality gaps.
  3. On 10 times more instances than our synthetic test set, the margin over the strongest alternative (SPD) remains clear in both backbones, conditional on the trained models: a paired per-instance test gives +0.94 pp (95% CI [+0.89, +0.99]) for DACT and +0.18 pp ([+0.16, +0.20]) for NDS-500.
  4. IPE+XPE has the lowest mean gap under both a multi-attribute distribution shift at fixed size (DACT) and a joint size-and-distribution shift (NDS-500).
AuthorsOpenReview ↗

Authors response (2/3)

To further validate the advantage of the proposed method across the different instance distributions, we report the following results:

AttributeLevelNumber of inst.DACT: SPDDACT: IPE+XPENDS-500: SPDNDS-500: IPE+XPE
Route sizevery short (3–5)1,6671.85%1.61%0.64%0.59%
short (5–8)1,6672.22%1.77%0.77%0.68%
medium (8–12)1,6672.60%1.94%0.95%0.82%
long (12–16)1,6673.15%2.20%1.18%0.99%
very long (16–25)1,6664.10%2.70%1.51%1.24%
ultra long (25–50)1,6665.28%3.34%2.09%1.74%
Customer positioningrandom3,3602.89%2.08%1.04%0.89%
clustered3,3223.57%2.47%1.38%1.16%
random-clustered3,3183.14%2.23%1.15%0.98%
Demandunitary1,4322.37%1.70%0.80%0.68%
small, large CV1,4283.35%2.37%1.24%1.05%
small, small CV1,4283.19%2.28%1.19%1.01%
large, large CV1,4283.40%2.40%1.29%1.09%
large, small CV1,4283.27%2.32%1.22%1.03%
depending on quadrant1,4283.58%2.51%1.36%1.15%
many small, few large1,4283.24%2.24%1.23%1.06%
Depotrandom3,4023.21%2.28%1.20%1.02%
centered3,3223.00%2.13%1.11%0.95%
cornered3,2763.39%2.37%1.26%1.06%
All10,0003.20%2.26%1.19%1.01%

IPE+XPE has a lower mean gap than SPD at every level of every attribute, in both backbones. The improvement is not uniform: it grows with route size and, among customer layouts, is largest for clustered customers. Route size is the attribute along which XML100 departs most from the DACT training distribution, and this trend is consistent with our design, though these marginal breakdowns do not isolate causes: IPE encodes the normalized cumulative distance, which does not depend on the number of nodes in a route, whereas index- and hop-based encodings change with it.

Overall, XML100 provides more solid evidence for the effectiveness of IPE+XPE on a larger, more diverse, and optimally solved test set.

AuthorsOpenReview ↗

Authors response (3/3)

Q2 About the distribution shift conclusion.

We agree with the reviewer's reading and adopt it. We revise the text accordingly:

  • Abstract, Section 5.2, Conclusion. We separate the two regimes: on the synthetic shifts, IPE+XPE remains the best tested encoding, but the margins among structure-aware PEs are small; on heterogeneous benchmarks, the separation is larger.
  • Appendix N. We state explicitly that the CVRPLib margin should not be extrapolated to any single synthetic shift, because the X set changes size, layout, demand, and route length at the same time.

One thing that we believe is consistent with this framing: the separation on heterogeneous benchmarks is not driven by a few instances. On CVRPLib X, the average gap of IPE+XPE is 2.84%, against 3.28% for SPD, the best alternative PE. It also improves on native NDS on 82 of 84 instances (the set was fixed before results were inspected, Appendix O) and ties on the remaining two, with the largest improvements on the largest instances.

The XML100 slices are not single-factor shifts: each level pools instances that vary in the other attributes, and for NDS every slice also changes size. They do show the margin growing with route length.


We have also updated the manuscript. Changes are marked in blue in the revised PDF.

We hope our response resolves your concerns, and we are open to any further discussions.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the rebuttal

Dear Reviewers, ACs, SACs, and PCs,

Thank you for handling our submission. We appreciate the reviewers' thoughtful feedback and have addressed concerns in our responses and the revised PDF.

In this paper, we present the first systematic study of positional encoding for neural vehicle routing. We formalize three structural desiderata of routing solutions, use them to build a taxonomy of existing PEs, and propose a geometry-grounded drop-in encoding. Controlled comparisons across NLP, graph-transformer, and routing-specific encodings, and integration into three improvement-based solvers, show that our method consistently outperforms existing PEs, with the largest gains on heterogeneous real-world benchmarks, at negligible extra cost.

We are happy that reviewers recognized the study design and falsifiable conclusions (j72S), the taxonomy and ablations (fNnK), and the controlled, cross-backbone evaluation (Zu7d).

Summary of the rebuttal.

  1. j72S New evaluation dataset. On XML100's 10,000 instances with proven optima, Our method has the lowest gap among the evaluated encodings in both backbones, and the margin grows with route length.
  2. j72S Claims on distribution shift. We now separate single-factor synthetic shifts (small margins) from heterogeneous benchmarks (larger separation).
  3. fNnK Runtime. We added inference times and a wall-clock-matched comparison. Our method stays first.
  4. Zu7d Hierarchy. We narrowed the claim: XPE is a depot-anchored frame, not a membership label. Explicit membership signals were weaker in our tests.
  5. Zu7d Seed-aware uncertainty . We added a seed-aware analysis for all nine Layer 2 cells.
  6. Zu7d Clarifications. We corrected the SPD label, clarified the D3 probe, the scope, and the difference from DACT's cyclic PE, and unified the terminology.

We thank the reviewers for the constructive comments, and we hope this study offers the community a principled basis for designing positional encodings in neural routing solvers.

Thank you again for your time.

Best,

Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.