- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This paper introduces CoRE, a shared representation of simulated constraint consequences, to enable zero‑shot generalization in neural routing solvers. We embed CoRE within a Guided Construction and Refinement (GCR) framework, where a single learned edge‑cost scorer drives both the construction and refinement phases. Experiments across 110 Vehicle Routing Problem (VRP) variants demonstrate that CoRE generalizes robustly to unseen combinations of constraints, entirely new constraints, and large‑scale instances.
Critical strengths
- By describing constraints through their consequences rather than fixed attributes, CoRE allows the model to handle new types of constraints without changing or fine-tuning parameters. This makes the approach more flexible.
- The GNN-based framework shares learned edge scores between construction and refinement, providing a useful way to combine neural predictions with local search.
Critical weaknesses
- The refinement procedure is not explained clearly enough. Although Appendix C.2 lists the local search operators and describes how moves are evaluated, it is still unclear how the sampled perturbation edges are used to define the search region and how the operators are applied within that region. More details would make the method easier to understand and reproduce.
- CoRE is trained on 22 VRP variants and also uses local search. The CoRE-UDR controls are useful, but the paper does not report results for GCR without refinement or for constructive baselines with similar local search. This makes it hard to tell how much of the gain comes from the representation, broader training coverage, or refinement.
Despite the impressive results, I remain unsure how much of the improvement is attributable to the proposed representation, and several methodological details remain unclear, making it difficult for me to support acceptance at this stage.
Questions for authors
- Could the authors explain more clearly how the sampled perturbation edges determine the local search region and how the different local search operators are applied?
- Could the author report the results of CoRE-GCR without refinement, as well as the results of the baselines under the same local search and a similar inference budget?
- Could the authors also compare baselines under the same training variants and comparable training budgets? This would help make the comparison more convincing.
- Since construction and refinement share learned edge scores, why use PPO to optimize only refinement perturbations instead of training both stages jointly?
4 comments
Response to Reviewer f9x6 (2/3)
[W2/Q2 - Refinement, and baselines with the same local search] We noted that our GCR application is designed to constraint-conditionally guide the fixed local search to any new constraints (please see our response to Reviewer 9gU4, W1). Thus, additionally we trained a "heatmap greedy" model, with the same GNN architecture, and report both results.
Pretrained method without refinement. One greedy pass of CoRE-GCR's construction reaches a 50.11% gap on all 110 variants, against 54.89% with travel distance in place of . Unlike a heatmap of edges likely to be optimal, ranks the moves of expert-designed local search, and GCR recomputes it whenever refinement improves the incumbent. The start therefore matters little: on the new constraint sets, URS's solutions start 23 points closer to the reference than this pass (25.35% against 48.76%), yet the same guided search ends within 0.6 points from either (5.23% against 5.83%, second table below).
Heatmap-based non-refinement training. As noted, our CoRE-GCR was designed and trained to guide and transfer the fixed refinement operators. To test consequences in the construction-only scenario alone, we train a heatmap on CVRPBLTW (25,600 instances) and evaluate it in the setting of Table 1. A GNN scores each edge once per instance, and each step CoRE-Heatmap adds the consequence bias of Section 4.4, computed from the checks that the feasibility mask already runs on the current candidates, so decoding costs for starts, steps and candidates, the same order as in masked heatmap decoding instead of attention over all nodes as in autoregressive decoder. UDR-Heatmap instead reads the attributes and live state. Each solution is the best of 100 greedy starts:
| Method | Obj. ↓ | Gap ↓ | Time ↓ |
|---|---|---|---|
| URS | 26.086 | 10.47% | 48s |
| RF-POMO | 28.971 | 22.69% | 45s |
| MVMoE | 29.879 | 26.53% | 64s |
| UDR-Heatmap | 34.286 | 45.20% | 12s |
| CoRE-Heatmap | 29.822 | 26.29% | 21s |
Results show that:
- Without refinement, CoRE-Heatmap reaches the level of the released constructive generalists in less time (26.29% in 21 s, against 26.53% in 64 s for MVMoE).
- This level depends on the consequences. With attributes, the model sees each customer's attributes and a shared live state, but not how each move would change that state. Consequences add each candidate's margin to its score, the path that also carries the effect in CoRE-POMO* (please see our response to Reviewer UUvF, Q4).
Same local search. Since URS can supply GCR's initial solution, we start our search from it, guided by travel distance (URS+LS) or by (URS+CoRE-GCR). The same two guides also run from CoRE-GCR's construction (CoRE+LS, CoRE-GCR), beside Distance GCR, and we tested this on the 40 new constraint sets:
| Method | Obj. ↓ | Gap ↓ | Time ↓ |
|---|---|---|---|
| URS | 11.313 | 25.35% | 23s |
| URS+LS | 9.832 | 7.09% | 33s |
| URS+CoRE-GCR | 9.692 | 5.23% | 41s |
| Distance GCR | 9.950 | 8.28% | 17s |
| CoRE+LS | 9.876 | 7.27% | 8.6s |
| CoRE-GCR | 9.753 | 5.83% | 25s |
Results show that the guidance carries most of the learned gain:
- On the new constraint sets, it lowers the gap by 1.86 points from URS's solutions and by 1.44 points from CoRE-GCR's construction, whichever construction starts the search.
- On the 98 variants with a distance objective, the learned construction lowers the gap from 5.86% to 5.42%, and the guidance lowers it further to 4.16%.
In short, under the same refinement, consequences lower the gap by 0.81 points over attributes (4.49% to 3.68% on all 110 variants); without refinement, they take a heatmap from 45.20% to 26.29%; and broader training coverage accounts for at most 0.4 points (Q3 below).
Response to Reviewer f9x6 (3/3)
[Q3 - Same training variants and comparable budgets] To clarify this, we match URS's training in the direction that is harder for us: we retrain CoRE-GCR and UDR-GCR (CoRE-UDR in the paper) on URS's 11 tasks, so that route limits, ordered backhauls and multiple depots all become new to them.
| Variant | URS | CoRE-GCR (11) | UDR-GCR (11) | CoRE-GCR (22) |
|---|---|---|---|---|
| CVRP | 1.14% | 2.52% | 2.72% | 1.93% |
| CVRPL | 1.06% | 1.94% | 2.44% | 1.57% |
| CVRPBP | 13.73% | 2.77% | 3.39% | 2.08% |
| CVRPTW | 4.43% | 3.87% | 4.46% | 3.80% |
| URS's 11 tasks | -1.47% | 0.70% | 1.15% | 0.09% |
| Other 99 variants | 23.62% | 4.44% | 5.49% | 4.08% |
| All 110 variants | 21.11% | 4.06% | 5.05% | 3.68% |
Results show that training coverage explains little of the gain:
- On the 99 variants URS never trained on, CoRE-GCR trained on URS's 11 tasks stays within 0.4 points of our 22-task model, far below URS and below UDR-GCR trained on the same tasks. On URS's own tasks, URS remains lower.
- The training budgets remain unequal, in URS's favour: URS keeps its published 1,000,000 batches of 128 (about 95 hours on an RTX 4090), while CoRE-GCR trains on 5,000 instances (2.6 hours on an A100).
[Q4 - Why PPO only on refinement?] We clarify that this is an empirical choice rather than a derived one: construction reads the same learned cost but lies outside the PPO batch, because training on it gave worse results. To analyze this, we retrain CoRE-GCR with both stages trained jointly:
| Method | Obj. ↓ | Gap ↓ |
|---|---|---|
| CoRE-GCR (joint PPO, retrained) | 8.614 | 4.14% |
| CoRE-GCR (retrained) | 8.601 | 3.82% |
Results show that joint training raises the gap on every population: from 0.82% to 1.10% on the training variants, from 4.53% to 4.86% held-out, and from 6.06% to 6.52% on the new constraint sets. We attribute this to the same observation in prior works that also trained on local searched tour, e.g. NLS in DeepACO (Ye el. al), and SRR in DyNACO (Tran et. al.), thus keeping the rollout's reward attributable to the choices that produced it.
We included those additional results in the revised paper. Hope these help address your remaining questions/concerns.
Thank you for the clarifications and additional experiments. They address some methodological questions, but my concern about performance attribution remains.
- Although CoRE-GCR is retrained on URS’s 11 tasks, the comparison still uses URS without refinement and CoRE-GCR with refinement, leaving CoRE-GCR’s advantage unclear.
- CoRE-GCR achieves a lower gap than CoRE+LS but takes 25s versus 8.6s. A comparison under a similar inference budget is therefore needed to establish the benefit of using the learned cost to guide the same local search.
- The authors also acknowledge that one greedy pass of CoRE-GCR’s construction performs substantially worse than URS, suggesting no clear advantage of the proposed method over existing baselines.
- Starting refinement from URS’s solutions yields better results than the original CoRE-GCR method. This further suggests that the performance gain mainly comes from refinement rather than the proposed model itself.
Therefore, I remain unsure how much of the improvement is attributable to the proposed representation and maintain my original score.
Response to Reviewer f9x6 (1/3)
We sincerely thank the reviewer for the valuable feedback, and for acknowledging that our method handles new constraints without fine-tuning, with impressive results. Please see our response below.
[W1/Q1 - Search region and operators] Sorry for the confusion. Appendix C.2 lists the operators without walking through how they are applied, so we give the complete procedure below. GCR follows Iterated Local Search: construction gives the initial solution, and each iteration runs 10 rollouts from the incumbent, each with four steps guided by the learned cost cθ of Eq. (5).
We gave this as an algorithm in Appendix C.2 of the revision.