acceptodds
Under review as a conference paper at ICLR 2027

LPACR: Local Policy with Augmented Contextual Representations for Enhancing OOD Generalization in VRPs

Abstract

Practical vehicle routing problem (VRP) instances exhibit significant variations in problem scale and intrinsic distribution, posing fundamental challenges to cross-scale and cross-distribution generalization capabilities of neural solvers. Although local policies are effective for cross-scale generalization, their restricted receptive fields lack global awareness. Meanwhile, we reveal that homogeneous training samples fail to cover diverse local topological structures that are crucial for cross-distribution generalization. In terms of learning paradigms, supervised learning (SL) suffers from objective misalignment, whereas reinforcement learning (RL) faces convergence instability. To overcome these limitations, we propose LPACR (Local Policy with Augmented Contextual Representations). We introduce a grid-based distribution compression method that leverages the spatial locality of VRP to encode grid-wise statistical information, thereby augmenting the contextual representation of the local policy. To enhance cross-distribution adaptability, we employ a multi-distribution training strategy that can encompass heterogeneous local topological structures. Furthermore, we train LPACR through a two-stage learning paradigm that synergizes SL and RL. Extensive experimental results on synthetic datasets and real-world benchmarks with diverse scales and distributions demonstrate LPACR's robust generalization capabilities.

Primary area:
optimization
Keywords:
Neural Combinatorial Optimization, Vehicle Routing Problem, Out-of-Distribution Generalization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_wR92OpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes LPACR, a local-policy neural solver for TSP and CVRP that targets cross-scale and cross-distribution generalization. It adds grid-based statistical tokens for global context, trains on multiple distributions, and uses supervised initialization followed by RL fine-tuning. It outperforms the compared neural baselines.

Critical strengths
  1. Considers both cross-distribution and cross-size generalization in a single framework.
  2. The performance is strong, and the results on real-world benchmarks are particularly impressive.
Critical weaknesses
  1. This paper is more of an engineering work. Its design choices (grid resolution, sub-problem sizes, mixing ratio of training distributions) are set empirically, and the paper offers limited insight into why the method works.
  2. The novelty is limited. Each component is a small revision of a common technique.
  3. The comparison in the main table is unfair. Most other neural baselines are used as released checkpoints trained only on the uniform distribution.
Questions for authors

I appreciate the strong results of this paper, especially on real-world benchmarks. However, I hesitate to give a higher score because the comparison in the main table is not fair, and the work is largely engineering-driven with limited novelty. I would raise my score if the authors provide persuasive results.

  1. Could the authors ablate the small architectural modifications (SwiGLU, RMSNorm, the start-node embedding and span token), and train the main baselines (e.g., TTPL, LEHD) with the same multi-distribution data with these small modifications? This would show whether the gains come from the proposed components or from the training data and modern architectural tweaks.
  2. Why do the grid statistics remain effective at such scales, and why does the dynamic-grid variant perform worse on synthetic datasets?
  3. In the real-world table, some baselines fail on large instances and are averaged over fewer instances, which makes the averages not directly comparable.
  4. Several design choices are hand-crafted: the grid resolution (6×6), the mixing ratio of training distributions (3:3:4), and the sub-problem sizes (K=50 in training, 100 for TSP and 65 for CVRP at inference). How sensitive is the method to these choices, and were they selected on the test sets?
3 comments
AuthorsOpenReview ↗

Follow-up on Our Response

Dear Reviewer wR92,

Thank you again for your careful reading and thoughtful feedback. We hope our response and the additional experiments have helped address your questions. As the discussion period draws to a close, we would be happy to answer any remaining questions or provide further clarification.

Best regards,

The authors

Thank you for the response and the additional experiments. They address most of my concerns. I will raise my score.

AuthorsOpenReview ↗

Thank you for raising the score

Thank you for raising the score! We are glad that our response has addressed your concerns, and we sincerely appreciate your insightful feedback, which has helped us substantially improve the paper. We are also grateful for the time and expertise you have devoted to reviewing our work.

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

This paper proposes LPACR, a constructive neural solver aimed at improving cross-scale and cross-distribution generalization for the traveling salesman problem (TSP) and capacitated vehicle routing problem (CVRP). The method augments a local autoregressive policy with Grid-based Distribution Compression (GDC), which turns grid-level density, spatial statistics, and visitation state into compact global-context tokens. It also employs multi-distribution training (MDT) using uniform, clustered, and mixed instances, followed by supervised-learning initialization and reinforcement-learning fine-tuning. Experiments cover seven synthetic distributions at six problem scales for each task, plus nine groups of real-world benchmarks. The reported results show strong solution quality on large and shifted instances, while ablations support the effectiveness of the proposed components within the LPACR framework.

Critical strengths
  1. Well-motivated integration of local decisions and global context.

  2. Broad evaluation and promising large-scale performance.

  3. SL init + RL refinement exploits fast warm-start and objective alignment; RL yields large CVRP gains.

Critical weaknesses
  1. LEHD rows are duplicated verbatim across the small TSP (Table 4) and CVRP (Table 5) tables.
  2. Baselines run original uniform-only checkpoints while LPACR also changes the distribution, adds RL, and modifies the backbone; in-model ablations are non-additive.
  3. App. E derives O(N²) total decoding, while the main text claims near-linear scaling.
  4. Proportion, centroid, and std are static; only visit ratio/flags update — GDC mostly carries fixed spatial priors like GELD.
  5. MDT fails on its own training distribution: cluster TSP worsens with scale (2.99%@1K to 7.16%@10K); heatmaps are correlational, not causal.
Questions for authors

See Weaknesses.

1 comment
AuthorsOpenReview ↗

Follow-up on Our Response

Dear Reviewer NUyy,

Thank you again for your careful reading and thoughtful feedback. We hope our response and the additional experiments have helped address your questions. As the discussion period draws to a close, we would be happy to answer any remaining questions or provide further clarification.

Best regards,

The authors

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

This paper proposes LPACR, a neural routing method designed to generalize across problem sizes and spatial distributions. It combines a local routing policy with a compact global representation built from grid-level statistics, including node density, spatial layout, and visit progress. The model is trained on several distributions to cover more diverse local structures. Training first uses supervised learning from expert solutions, followed by reinforcement learning to improve overall route quality. Experiments on TSP and CVRP include synthetic instances and public benchmarks, and report improved generalization across scales and distributions compared with the tested neural baselines.

Critical strengths
  1. The proposed method is generally solid and well-designed for the specific VRP generalization setting.
  2. The presentation is good and easy-to-follow.
Critical weaknesses
  1. My key concern is the problem-level versatility of the proposed method when handling different combinatorial optimization problems. The geometric patterns studied in this paper is clearly limited to the Euclidean routing problem, which can not be genelized to other problem types. If routing problem is the specific application, I recommend the authors to emphasize several important indusrial applications, like wire routing for chips, which can make the paper more interesting for the broad optimization community.
  2. The idea of introducing global context by abstracting non-local nodes is relatively simple. The proposed grid-based feature design for global context is also a heuristic implementation.
  3. The two-stage training paradigm is interesting, but the transition between the two stages is tricky and should be clearly explained in the method section.
Questions for authors

I am particularly interested in the real-world benchmark and want to know what kinds of real problems can be solved by current neural solvers? And how are the solvers are adapted to solve new problems? However, I can not find a detailed description of the benchmarks in Table 2 and 3.

Comments on the paper

1 comment

Dear reviewers,

We have now received the author responses to your raised questions and concerns. Please go through them. Also, have they answered your questions appropriately? Please also look other reviewers' strengths / concerns. Have they changed your perception of the paper? In all cases, please communicate with the authors. It is important that we let them know what relevant issues still exist or have been answered. Please remember we have limited time to get any further responses from them.

Regards,

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.