- 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
-
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.
-
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
-
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.
-
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
-
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?
-
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?
-
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?
-
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?
-
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
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:
- Seed-level differences. = mean over training seeds of the test-set mean gap of SPD, minus the same quantity for IPE+XPE. Positive favors IPE+XPE.
- Cross-seed pairs. Since training seeds are independent across methods, we compare every IPE+XPE seed with every SPD seed.
- 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.
| Cell | mean (pp) | pairs favoring IPE+XPE | seed-aware 95% CI |
|---|---|---|---|
| CVRP-500 | +0.04 | 6/9 | [−0.04, +0.12] |
| CVRP-1000 | +0.09 | 9/9 | [+0.02, +0.16] |
| CVRP-2000 | +0.12 | 9/9 | [+0.04, +0.20] |
| VRPTW-500 | +0.05 | 8/9 | [+0.01, +0.09] |
| VRPTW-1000 | +0.04 | 6/9 | [−0.05, +0.13] |
| VRPTW-2000 | +0.18 | 9/9 | [+0.09, +0.27] |
| PCVRP-500 | −0.01 | 3/9 | [−0.08, +0.06] |
| PCVRP-1000 | +0.09 | 9/9 | [+0.03, +0.15] |
| PCVRP-2000 | +0.19 | 9/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 . 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: = a function of travel distance; = a graph or hop distance that correlates with travel distance through the solution structure; = 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 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).
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:
- 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.
- 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).
- 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
Authors response (1/3)
We thank the reviewer for the careful reading and the detailed questions. We address each point below.
TL;DR.
W1Hierarchy. 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 & Q3Seed-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.W3Scope. 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.Q1SPD and D1. We correct Table 2, Section 3, and Appendix E. No conclusion changes.Q2D3 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.Q4Beyond 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.Q5Terminology. We now use "No PE" and "IPE+XPE" throughout and have unified "Laplacian PE".W1Interpretation 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.
We agree the paper should make this precise, so the claim matches the evidence exactly:
[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.