acceptodds
Under review as a conference paper at ICLR 2027

Basin-guided Reinforcement Learning for Multi-task Vehicle Routing Problems

Abstract

Multitask neural constructive solvers for vehicle routing are efficient but often lag behind classical solvers in solution quality. Combining neural construction with classical refinement can balance solution quality and efficiency. We propose a basin-guided reinforcement learning framework in which a neural solver generates intermediate solutions that are converted into feasible solutions and refined through bounded local moves. The framework builds on a simple insight: distinct candidates can reach the same refined outcome, so construction-level diversity does not necessarily translate into diversity after post-processing. This many-to-one mapping induces post-processing basins that guide learning. Alongside refined solution costs, training uses two complementary signals: a Refined-Edge Prior (REP) learns customer adjacencies from refined solutions to guide construction, while Refined-Outcome Entropy (ROE) encourages rare refined outcomes at both solution and route levels. During inference, candidates are generated by the neural network and post-processed in parallel. Optional route recombination further exploits diversity across refined candidates, forming the full pipeline. Across 16 VRP variants, the full pipeline reduces macro-average gaps to PyVRP with a 60-second per-instance budget by 69.2–81.7% relative to RouteFinder, PoMtVRS, CCL, MoSES, and RL-RFCS with the same post-processing stages, at mean end-to-end latencies of 0.11 and 0.56 seconds per instance for and , respectively. After fine-tuning on randomly generated 200-customer instances, it achieves an average gap of -0.34% on CVRP200 to the same PyVRP reference at approximately 2.6 seconds per instance with a larger inference budget.

Primary area:
optimization
Keywords:
Vehicle Routing Problems, Combinatorial Optimization

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_6XmROpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes a reinforcement learning framework that trains a multitask VRP constructor using feedback from deterministic DP splitting and bounded local refinement. Its central observation is that distinct constructed candidates can produce identical refined outcomes, motivating diversity credit at the post-processing level. The framework combines refined-cost rewards with a Refined-Edge Prior (REP), which learns adjacency frequencies from refined candidates and guides decoding, and Refined-Outcome Entropy (ROE), which assigns credit using refined-solution and route-set frequencies. Optional inference-time route recombination further exploits candidate complementarity. Evaluation includes 16 VRP variants, matched-post-processing neural comparisons, component ablations, distribution shifts, unseen constraint combinations, larger instances, and CVRPLIB. The full pipeline reports macro-average gaps of 0.059% and 0.087% to PyVRP@60s at mean latencies of 0.110s and 0.560s for 50 and 100 customers, respectively.

Critical strengths

A meaningful contribution to learning from downstream optimization, supported by relevant ablations. Previous multitask methods primarily improve constraint representation, expert sharing, or transfer, while solver-feedback approaches such as RL-RFCS already learn from deterministic splitting costs. This paper adds a distinct mechanism: assigning diversity credit using the frequencies of outcomes that survive refinement. This directly addresses redundancy in the candidates used for final selection and route recombination. Table 4 provides substantial supporting evidence: adding the full ROE objective reduces the M20 gap from 0.230% to 0.117% and the DFS gap from 0.173% to 0.059%, while increasing unique refined endpoints from 72.86 to 220.07. The action-entropy comparison further supports the importance of the chosen diversity measure. Strong empirical results with comparisons that account for classical post-processing. The five main neural baselines receive the same candidate counts, DP splitting, local refinement, and route recombination settings. This makes the results informative about the learned candidate-generation strategy. Improvements are already present in the core pipeline: for example, at n=50, it achieves a 0.117% gap in 0.105s, compared with 0.265% in 0.256s for CCL with M20. The full pipeline reports the lowest neural objectives across all 32 size–variant combinations. The quality–latency curves, competitive CVRP200 results against HGS-CVRP, and matched-post-processing comparison with Scale-Net provide additional evidence of practical value.

Critical weaknesses

The comparison with action entropy does not sufficiently isolate the source of ROE’s advantage. Appendix B.6 selects the action-entropy coefficient from three values using training statistics only through epoch E4. In contrast, ROE uses per-instance RMS normalization and substantially changes its diversity weights between training stages. Consequently, Table 4 compares methods that differ in both the diversity measure and its optimization configuration. Although the results demonstrate the effectiveness of the implemented ROE objective, they do not establish how much of its advantage comes specifically from measuring diversity after refinement rather than from differences in regularization strength and scheduling. Moreover, the component ablations are restricted to n=50, leaving the corresponding mechanism insufficiently examined at n=100.

Questions for authors

Could the authors provide a validation-based sensitivity analysis of the action-entropy coefficient evaluated after the complete training schedule, particularly following the switch to stronger refinement? This would help determine whether ROE’s advantage in Table 4 persists with a baseline calibrated for the later training stage. Corresponding ROE ablations at n=100 would also clarify whether the component-level conclusions extend beyond the smaller problem size. Could the authors separate REP’s auxiliary supervision from its decoding prior and report their individual contributions? A comparison with refined-trajectory imitation using the same constructor and deterministic refiner would further clarify the value of the proposed edge-frequency targets relative to existing refinement-based supervision. Under the default K=32 and gamma=0.25, how frequently does solution-level ROE produce a nonzero advantage during training, and how does this frequency vary across tasks and problem sizes? Appendix A.5 explains that equal endpoint frequencies, including the case where all retained endpoints are distinct, yield zero solution-level advantage. Training-time statistics would help establish when this signal contributes and how its role differs from route-level credit.

2 comments

We thank the reviewer for recognizing the contribution of learning from refined outcomes and for the constructive suggestions on baseline calibration and mechanism analysis. We address these points below with additional experiments and clarifications, referring to our response to Reviewer rgbL and 5Eeb where the concerns overlap.

Response: Action-entropy coefficient sensitivity

The AE ablation tests whether a conventional action-entropy bonus can replace ROE. We retain REP and replace both ROE terms with mean action entropy added to the loss using a fixed coefficient. To extend the original early-stage screening, all three AE configurations were trained from scratch through the complete 100-epoch schedule.

Rebuttal Table 9

MetricAE = 0.001AE = 0.003AE = 0.01ROE
M12 Gap (%)0.1930.2800.8540.170
M20 Gap (%)0.1790.1940.2540.117
DFS Gap (%)0.1270.1230.1320.059
Unique endpoints110.23149.59193.91220.07

Results use n=50 and A8S50, with unique endpoints measured after M20. ROE achieves lower gaps at all three stages than every tested fixed-coefficient AE baseline.

Response: Ablations at n=100 and REP decomposition

Please see our response to Reviewer rgbL’s W1/Q2 for additional CVRP50/CVRP100 ablations, including a refined-cost-only baseline, route-level ROE comparisons, and REP decomposition across two training seeds. Full REP consistently improves M20 quality over both the prior-only and REP-disabled configurations, while its gains after DFS are smaller and inconsistent. These experiments use a common 10-epoch training-from-scratch protocol.

Response: Refined-trajectory imitation

We thank the reviewer for this suggestion. Refined-trajectory imitation is a useful alternative supervision design that could be integrated into our framework. Our current experiments focus on the contributions of REP and ROE; we leave a controlled comparison with imitation-based supervision to future work and do not claim superiority over this alternative.

Response: Frequency of nonzero ROE signals

Complementing the redundancy statistics in our response to Reviewer 5Eeb’s W4, we report nonzero ROE signal frequencies below.

Rebuttal Table 10

TaskEpochROE weightsNonzero sROE (%)Nonzero rROE (%)
CVRP5089(1, 0)84.6796.19
CVRP5090(5, 2)39.94100.00
CVRP5099(5, 2)34.18100.00
VRPTW5089(1, 0)85.6488.38
VRPTW5090(5, 2)47.4699.61
VRPTW5099(5, 2)43.2699.71
CVRP10089(1, 0)16.8099.90
CVRP10090(5, 2)1.07100.00
CVRP10099(5, 2)0.29100.00
VRPTW10089(1, 0)41.2199.90
VRPTW10090(5, 2)2.93100.00
VRPTW10099(5, 2)3.42100.00

Each checkpoint is replayed on 1,024 fixed instances per task with K=32, temperature 1, γ=0.25, and M12. Percentages count instances whose gated, centered credit vector has RMS > 10⁻⁸. Solution-level ROE becomes less frequently active as refined solutions become distinct, especially at n=100. Route-level credit remains nonzero on nearly all instances at E90/E99, providing a complementary signal even when complete solutions are unique.

Dear Reviewer 6XmR,

Thank you again for your feedback. We added AE comparisons, n=100 and REP ablations, and ROE signal statistics, and discussed imitation as future work. Revision locations are summarized in our first response. We would be happy to discuss any further questions.

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

This paper proposes a basin-guided reinforcement learning framework for solving multi-task Vehicle Routing Problems (VRPs). The framework introduces two key components, Refined-Edge Prior (REP) and Refined-Outcome Entropy (ROE). REP learns customer adjacency information from locally refined solutions to guide solution construction, while ROE encourages diversity among refined solutions and routes. Additionally, an optional route recombination mechanism is introduced to further improve solution quality during inference. Experiments across 16 VRP variants and multiple problem sizes demonstrate strong solution quality and competitive computational efficiency compared with existing neural solvers.

Critical strengths

The paper demonstrates strong experimental performance. Across 16 VRP variants and different problem sizes, the proposed full framework consistently outperforms the compared neural solvers in solution quality under the same post-processing settings, demonstrating its effectiveness and applicability to multi-task vehicle routing problems.

Critical weaknesses
  1. In Table 4, the A8S50 setting includes four ablation configurations, whereas A8Greedy1 only compares the full model with the variant without REP. The authors do not explain the reason for this difference. Or could it be that the components not ablated under A8Greedy1 are primarily effective under sampling-based inference?

  2. I noticed that in Table 1, when n=100, the inference latency of the proposed method increases from 0.190 seconds with M20 to 0.560 seconds with DFS, nearly tripling the runtime. In contrast, the additional overhead introduced by DFS is much smaller at n=50 and for the other compared methods. The paper does not sufficiently explain this difference. If the reported latency measurements are accurate, would DFS introduce even greater computational overhead on larger-scale problems?

  3. Attribution not isolated. Most of the n=100 gain (Core 0.480% to Full 0.087%) comes from shared DFS, which lifts CCL 0.685% to 0.337% on its own; Table 4 also lacks a REP-off + ROE-off row, so the net contribution of the proposed signals cannot be measured.

  4. The paper asserts many-to-one collapse and redundant construction diversity but reports no collapse rate or basin-size distribution across M/n/variant.

  5. γ=0.25 is framed as core ROE design, yet Table 14 shows γ=1 gives the best DFS objective and highest diversity; the authors admit no consistent benefit from filtering. Drop it from the contributions or provide consistent evidence.

Questions for authors

If the inference latency reported in Table 1 is accurate, could the authors provide a further analysis of how the computational overhead introduced by DFS scales with problem size, particularly for larger-scale instances?

2 comments

We thank the reviewer for recognizing our strong empirical performance and for the constructive comments on component attribution and computational overhead. We address these concerns below with additional experiments and clarifications. For brevity, we refer to the relevant parts of our response to Reviewer rgbL where the concerns overlap.

Response to W1

The A8Greedy1 comparison specifically examines REP’s quality benefit under a limited candidate budget. This complements our additional ablations, where REP consistently improves M20 quality across both sizes and seeds, while its gains after DFS are smaller. Also please refer to Rebuttal Table 6 for additional info.

Response to W2 & Q1

Our response to Reviewer rgbL’s W2/Q1 analyzes the additional DFS overhead, which depends on the route pool and its diversity. Limiting the number of admitted routes controls the quality-runtime tradeoff. In the VRPTW100 case study, our advantage over the neural baselines persists even with a 400-route cap. DFS is also anytime and can return its best incumbent without waiting for an optimality certificate. Finally, our core pipeline already achieves lower macro-average gaps before DFS, supporting a contribution beyond route recombination.

Response to W3

The refined-cost-only versus all-components ablation in our response to Reviewer rgbL’s W1/Q2 directly addresses this concern. With the same architecture and post-processing, enabling REP and ROE improves both M20 and DFS results on CVRP50 and CVRP100, demonstrating gains beyond the shared DFS stage.

Response to W4

We added checkpoint replay on CVRP and VRPTW at n=50 and n=100. Each checkpoint is evaluated on the same 1,024 instances per task with K=32 and fixed M12 refinement. The table tracks redundancy across the training-stage transition, when the ROE weights change from (1, 0) to (5, 2).

Rebuttal Table 8

TaskEpochROE weightsUnique solutions / 32Solution redundancy (%)Unique route customer setsRoute redundancy (%)
CVRP5089(1, 0)22.3630.11064.2771.05
CVRP5090(5, 2)30.873.540115.0947.88
CVRP5099(5, 2)31.023.060116.6747.17
VRPTW5089(1, 0)9.2771.02035.2989.89
VRPTW5090(5, 2)30.066.080124.6364.76
VRPTW5099(5, 2)30.614.350124.6364.52
CVRP10089(1, 0)31.34382.051165.4251.89
CVRP10090(5, 2)31.98440.049234.3931.69
CVRP10099(5, 2)31.99610.012241.8729.55
VRPTW10089(1, 0)28.661110.434129.6577.53
VRPTW10090(5, 2)31.92290.241259.5853.94
VRPTW10099(5, 2)31.93160.214264.5252.65

Redundancy varies substantially across tasks, sizes, and training stages. Complete solutions become nearly unique in the final n=100 models, yet route-level redundancy remains 29.55% on CVRP100 and 52.65% on VRPTW100. This supports considering diversity at both levels.

Response to W5: Quality gating in ROE

ROE’s core contribution is diversification based on refined outcomes. Our ablations show that quality and diversity are not always aligned; the quality gate balances them by assigning diversity credit to rare outcomes among higher-quality candidates. Table 14 shows a small advantage for γ=0.25 at M12 and M20, which may be useful under limited refinement budgets or core-only inference, whereas γ=1 performs best after DFS. We therefore describe γ=0.25 as a default implementation choice, rather than an essential contribution or a universally superior setting, and report this sensitivity analysis to inform future designs.

Dear Reviewer 5Eeb,

Thank you again for your feedback. We added ablations and diversity statistics and clarified DFS overhead and quality gating. Revision locations are summarized in our first response. We would be happy to discuss any further questions.

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

This paper proposes a basin-guided reinforcement learning framework for multi-task vehicle routing. Its motivation is that distinct constructed candidates can converge to the same outcome after deterministic post-processing. The framework combines a neural permutation policy with dynamic-programming route splitting and bounded local refinement. Alongside refined-cost rewards, it introduces a Refined-Edge Prior that learns customer adjacencies from refined solutions and guides decoding, and Refined-Outcome Entropy that rewards rare refined solutions and routes to encourage diversity after refinement. At inference, candidates are refined in parallel, with optional route recombination. Experiments cover 16 VRP variants at 50 and 100 customers, with additional evaluations on larger instances and generalization settings. The reported results show lower macro-average gaps than five neural baselines under matched candidate and post-processing configurations, supported by component ablations and diversity measurements.

Critical strengths

S1. A Coherent Framework for Learning from Refined Outcomes

The paper addresses a concrete problem: distinct constructed candidates may converge to the same outcome after deterministic post-processing, so construction-level diversity does not necessarily translate into useful final-solution diversity. Encouraging diversity based on refined outcomes is a well-motivated response. REP and ROE use structural information and outcome frequencies from post-processing, respectively, providing the constructor with feedback beyond scalar costs. The overall design is coherent.

S2. Strong Results under Matched Post-Processing Settings

The main evaluation covers 16 VRP variants at 50 and 100 customers and compares against five neural baselines with matched candidate counts, DP splitting, local refinement, and route-recombination settings. This controls an important source of variation between methods. The full pipeline achieves macro-average gaps of 0.059% and 0.087% relative to PyVRP@60s and the lowest mean objective among the compared neural methods in each of the 32 reported size–variant combinations. Its macro-average gaps are also lower at the M20 stage, showing that the advantage is not solely due to the additional route-recombination stage.

S3. Ablations Support ROE with Broader Generalization Tests

The reported ablations provide clear support for solution-level ROE. In the 50-customer experiments, adding this term while retaining REP and disabling route-level ROE reduces the DFS gap from 0.173% to 0.074% and increases the numbers of distinct refined endpoints and routes. This configuration also outperforms the tested action-entropy configuration, supporting diversification at the refined-outcome level. Additional experiments on OOD distributions, unseen constraint combinations, CVRP1000, and CVRPLIB provide useful tests of the method’s scope and limitations.

Critical weaknesses

W1. Incomplete Attribution and Unverified Robustness of Component Gains

The existing ablations support ROE within the proposed framework, but a control using the same architecture and only refined-cost rewards, with both REP and ROE disabled, is missing. This limits the assessment of the additional learning signals’ individual and joint contributions beyond cost-based feedback. Removing REP also disables both its auxiliary supervision and its decoding prior, leaving their separate contributions unclear. Furthermore, the main component ablations are limited to 50-customer instances, and variability across training seeds is not reported. This is particularly relevant for REP: under A8S50 with DFS, it reduces the gap only from 0.061% to 0.059%, so the robustness of this final-stage gain remains uncertain.

W2. Limited Evidence at Matched Runtime and Larger Scales

Matching candidate counts and post-processing settings is useful, but does not establish performance at matched actual runtime. For example, on 100-customer instances, the full pipeline takes 0.560 seconds per instance, compared with 0.199 seconds for RL-RFCS+DFS. It remains unclear whether the quality advantage persists when strong baselines receive additional computation. The CVRP1000 results also retain a substantial quality gap to PyVRP@60s, while the CVRPLIB evaluation uses a large candidate budget without comparisons against strong classical solvers at similar time budgets. These limitations constrain the scope of the efficiency evidence without negating the quality gains demonstrated in the main experiments.

Questions for authors

Q1. Does the Quality Advantage Persist at Matched Runtime?

Does the method retain its main quality advantage at similar end-to-end latency? For example, could strong neural baselines use larger sampling or post-processing budgets to approach the full pipeline’s 0.560-second latency on 100-customer instances? Representative comparisons against classical solvers at similar time budgets on larger or CVRPLIB instances, together with a stage-wise runtime breakdown or tail-latency statistics, would further clarify the computational benefits.

Q2. Can Further Ablations Isolate Contributions and Establish Robustness?

Could the authors further isolate the learning signals through a same-architecture, refined-cost-only baseline with both REP and ROE disabled, separate ablations of REP’s auxiliary supervision and decoding prior, and results across multiple training seeds? It would also be helpful to validate the key ablation findings at 100 customers and report the variability of REP’s gain after extensive sampling and DFS.

5 comments

Response to Reviewer rgbL

We thank the reviewer for the positive assessment of our framework and empirical results. We agree that more careful attribution and runtime analysis would strengthen the paper.

Response to Q1 and W2: Runtime and sampling-budget comparisons.

Our original comparisons match candidate counts and post-processing configurations, but we agree that this does not establish performance at matched end-to-end runtime. To further examine the observed latency differences, we added case studies on CVRP100 and VRPTW100. We increase the candidate budget from 800 to 6,400 for all methods and compare route-pool caps of 400 and 3,200 unique customer sets, reporting the time spent in the DFS stage separately. The following results help explain the runtime difference between the core and full pipelines.

Rebuttal Table 1 CVRP

CandidatesMethodDFS@400 Obj. (Gap %)DFS time (s)DFS@3200 Obj. (Gap %)DFS time (s)
800RL-RFCS15.619 (0.376)0.01015.594 (0.215)0.113
800RouteFinder15.640 (0.511)0.01015.622 (0.398)0.040
800PoMtVRS15.612 (0.333)0.01015.598 (0.246)0.038
800CCL15.619 (0.380)0.01015.607 (0.300)0.034
800MoSES15.642 (0.523)0.01015.628 (0.436)0.031
800Basin15.594 (0.220)0.01015.570 (0.063)0.192
6,400RL-RFCS15.588 (0.178)0.01615.565 (0.033)0.226
6,400RouteFinder15.586 (0.163)0.01615.563 (0.019)0.236
6,400PoMtVRS15.567 (0.045)0.01615.553 (−0.045)0.259
6,400CCL15.574 (0.087)0.01515.558 (−0.015)0.220
6,400MoSES15.588 (0.176)0.01615.566 (0.036)0.207
6,400Basin15.568 (0.053)0.01715.551 (−0.058)0.316

Rebuttal Table 2 VRPTW

CandidatesMethodDFS@400 Obj. (Gap %)DFS time (s)DFS@3200 Obj. (Gap %)DFS time (s)
800RL-RFCS25.534 (0.468)0.00625.532 (0.461)0.008
800RouteFinder25.527 (0.441)0.00725.526 (0.434)0.008
800PoMtVRS25.522 (0.422)0.00525.522 (0.419)0.005
800CCL25.495 (0.314)0.00625.494 (0.312)0.007
800MoSES25.508 (0.364)0.00525.507 (0.362)0.006
800Basin25.449 (0.131)0.01125.442 (0.105)0.773
6,400RL-RFCS25.495 (0.313)0.01325.488 (0.287)0.053
6,400RouteFinder25.471 (0.220)0.01425.463 (0.188)0.120
6,400PoMtVRS25.458 (0.170)0.01525.452 (0.145)0.098
6,400CCL25.459 (0.172)0.01425.453 (0.149)0.070
6,400MoSES25.468 (0.206)0.01325.464 (0.190)0.024
6,400Basin25.437 (0.084)0.01825.433 (0.069)1.624

We also report the mean and 95th-percentile (P95) DFS runtimes to characterize both average and tail latency.

Rebuttal Table 3 CVRP Time

CandidatesMethodDFS@400 Mean (s)DFS@400 P95 (s)DFS@3200 Mean (s)DFS@3200 P95 (s)
800RL-RFCS0.0100.0110.1130.264
800RouteFinder0.0100.0120.0400.079
800PoMtVRS0.0100.0110.0380.072
800CCL0.0100.0110.0340.062
800MoSES0.0100.0120.0310.061
800Basin0.0100.0110.1920.392
6,400RL-RFCS0.0160.0180.2260.508
6,400RouteFinder0.0160.0170.2360.532
6,400PoMtVRS0.0160.0170.2590.765
6,400CCL0.0150.0170.2200.582
6,400MoSES0.0160.0170.2070.481
6,400Basin0.0170.0180.3160.882

Rebuttal Table 4 VRPTW Time

CandidatesMethodDFS@400 Mean (s)DFS@400 P95 (s)DFS@3200 Mean (s)DFS@3200 P95 (s)
800RL-RFCS0.0060.0130.0080.016
800RouteFinder0.0070.0140.0080.026
800PoMtVRS0.0050.0090.0050.009
800CCL0.0060.0100.0070.017
800MoSES0.0050.0100.0060.010
800Basin0.0110.0210.7735.459
6,400RL-RFCS0.0130.0220.0530.102
6,400RouteFinder0.0140.0200.1200.403
6,400PoMtVRS0.0150.0210.0980.185
6,400CCL0.0140.0190.0700.293
6,400MoSES0.0130.0170.0240.081
6,400Basin0.0180.0271.62410.570

Overall, these results support a solution-quality advantage at comparable runtime budgets. The evidence is particularly strong on VRPTW100, where Basin with 800 candidates and a 400-route cap outperforms all evaluated baselines using 6,400 candidates and a 3,200-route cap. On CVRP100, additional sampling narrows the quality differences, with Basin remaining competitive.

The additional runtime with larger route pools reflects the cost of search, which certifies optimality within the supplied pool when completed. This search is anytime: initialized with the best refined candidate, it can return the best feasible solution found so far when interrupted. Applications can therefore impose a tighter time budget without waiting for an optimality certificate.

While our current experiments include larger instances, OOD distributions, and CVRPLIB benchmarks, a systematic study across problem scales and on out-of-distribution and real-world routing instances remains an important direction for future work.

Response to Q2 and W1: Component attribution and robustness.

We agree that further ablations would strengthen component attribution. Table 4 of the manuscript examines component removal under the full training schedule. Since a complete n=100 training run takes over 30 hours, we additionally conducted controlled experiments on CVRP50 and CVRP100, training each configuration from scratch for 10 epochs (approximately three hours per run at n=100). All experiments below use M12 during training and the original inference candidate budgets: A8S50 for CVRP50 and A8S100 for CVRP100. Results are gaps (%) to PyVRP@60s after M20 and subsequent DFS recombination.

1. Joint contribution beyond refined-cost feedback.

We added the requested same-architecture baseline with REP and both ROE terms disabled. Enabling all components improves both M20 and DFS quality at both sizes.

Rebuttal Table 5

ConfigurationCVRP50 M20CVRP50 DFSCVRP100 M20CVRP100 DFS
Refined-cost only0.3740.2300.9710.314
REP + solution- and route-level ROE0.2510.0820.8650.120

Both rows use seed 3333. The enabled configuration uses REP supervision weight 0.1, the decision prior, and solution-/route-level ROE weights of 1/2.

2. Separating REP supervision and its decision prior.

We compare disabling both REP components, retaining only the decision prior, and enabling both. Without auxiliary supervision, the retained prior remains trainable through policy gradients. The underlying architecture is preserved across settings.

Rebuttal Table 6

REP settingCVRP50 M20CVRP50 DFSCVRP100 M20CVRP100 DFS
Neither component0.328 ± 0.0210.169 ± 0.0220.980 ± 0.0020.311 ± 0.008
Decision prior only0.332 ± 0.0090.169 ± 0.0120.956 ± 0.0170.285 ± 0.037
Supervision + decision prior0.292 ± 0.0060.160 ± 0.0190.826 ± 0.0100.306 ± 0.011

Results are mean ± sample standard deviation over seeds 3333 and 4444, with solution-level ROE weight 1 and route-level ROE disabled.

Full REP improves M20 quality over both alternatives at both sizes for each seed. The decision prior alone does not consistently improve quality, highlighting the value of its auxiliary supervision. REP’s benefit after DFS is smaller and inconsistent, supporting the reviewer’s concern that its final-stage gain should not be overstated. Since DFS recombines routes across candidates, its performance depends on both route quality and complementarity, suggesting a quality–diversity tradeoff that we examine next through route-level ROE.

3. Contribution of route-level diversity.

Holding REP and solution-level ROE fixed, we enable route-level ROE to isolate its effect on recombination.

Rebuttal Table 7

Route-level ROE weightCVRP50 M20CVRP50 DFSCVRP100 M20CVRP100 DFS
00.2870.1460.8330.313
20.2510.0820.8650.120

Both rows use seed 3333, full REP, and solution-level ROE weight 1.

These experiments complement the original 16-variant ablations. They establish consistent M20 improvements from REP across two seeds and demonstrate joint and route-level benefits in paired runs, while emphasizing that quality and diversity are not entirely aligned objectives.

Comments on the paper

1 comment

Dear Reviewers and Area Chairs,

Thank you for your constructive feedback. We address the comments below through additional experiments, clarifications, or discussion of future work. Additions and substantive revisions of the manuscript are highlighted in blue.

  • Reviewer rgbL: Section 5.4 and Appendix C.6 analyze DFS runtime, tail latency, and sampling budgets (Q1/W2). Section 5.3, Table 4, and Appendix C.7 provide cost-only comparisons, REP decomposition across two seeds, and route-level diversity ablations (Q2/W1).

  • Reviewer 5Eeb: These analyses address component attribution and runtime (W1–W3/Q1). Figure 3 and Section 5.4 examine diversity evolution (W4); Section 5.3 discusses the quality–diversity tradeoff alongside the existing gate-sensitivity results in Appendix C.3 (W5).

  • Reviewer 6XmR: Appendix C.8 reports full-training action-entropy comparisons; Appendix C.7 includes n=100 ablations and REP decomposition across two seeds; Figure 3 reports ROE signal activity. We discuss refined-trajectory imitation as a future comparison, without claiming superiority over it.

Thank you again for your time and thoughtful feedback.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.