acceptodds
Under review as a conference paper at ICLR 2027

Neural Periodic Reoptimization for Dynamic Vehicle Routing

Abstract

Dynamic vehicle routing requires repeated route revision as new requests arrive during vehicle execution. Neural construction solvers offer a fast alternative to repeated combinatorial search, but static training does not account for the residual routing states encountered at deployment, which depend jointly on request arrivals, past routing decisions, and irrevocable dispatch commitments. We propose Neural Periodic Reoptimization (NPR), a framework that aligns neural routing solvers with a prescribed periodic execution protocol. NPR represents execution histories as residual routing problems and trains the solver on states encountered during its own protocol-constrained reoptimization rollouts. Its Commitment-Consistent Decoding intersects a commitment mask with the solver's native feasibility mask to preserve committed route prefixes, enabling reoptimization without external search or repair. Experiments with POMO and ReLD on problems with 100-1,000 customers show consistent improvements over static training. For clustered demand with Poisson arrivals at 1,000 customers, NPR reduces ReLD's gap to ALNS from 40.77% to 3.92%. On 122 public DVRP instances, NPR achieves a mean gap of 1.78%. Further experiments demonstrate compatibility with pairwise preference training, transfer across spatial and temporal distributions and degrees of dynamism, and applicability to customer time windows.

Primary area:
applications to robotics, autonomy, planning
Keywords:
Dynamic Vehicle Routing Problem, Neural 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_NFomOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Neural Periodic Reoptimization (NPR) adapts autoregressive routing solvers to periodic DVRP and DVRPTW by training on rollout-induced residual states. Commitment-Consistent Decoding (CCD) preserves irrevocable route prefixes during replanning. Experiments with POMO and ReLD on synthetic and public benchmarks report consistent improvements over matched static-training baselines.

Critical strengths
  1. The residual-state interface and CCD address concrete obstacles in transferring static neural solvers to dynamic execution. They preserve execution commitments within route construction without requiring external search or repair.
  2. Static/NPR pairs share architectures, decoding masks, training update counts, and inference budgets. Improvements across both backbones and, for POMO, both training objectives provide useful evidence that the benefit is not tied to a single model or local loss.
Critical weaknesses
  1. DVRP is a special case of DVRPTW without customer-specific time windows. With a distance-only objective, dynamic replanning is unnecessary if the distance-optimal static routes remain feasible when dispatched after all requests are revealed.
  2. All experiments fix K=40K=40 and Tac=8T_{\mathrm{ac}}=8, leaving sensitivity to replanning frequency and the advance-commitment horizon unexplored.
  3. Both DVRP and DVRPTW optimize distance alone, although the timing of decisions is a defining aspect of dynamic routing. This leaves a modeling gap in how the objective captures the temporal nature of the problem.
Questions for authors
  1. Could the authors vary KK on fixed test instances while keeping TacΔ=0.2HT_{\mathrm{ac}}\Delta=0.2H, and report distance, feasibility, and runtime?
  2. Could the authors report results without aug-8, using matched multi-start widths for static/NPR pairs?
  3. Could the authors assess whether adding a response-time term to the training objective better captures the needs of dynamic routing?
  4. Could the authors provide the details of the ALNS reference?
8 comments
AuthorsOpenReview ↗

W1: Necessity of Dynamic Reoptimization

Thank you for recognizing that our framework mechanism is effective and that the evaluation evidence is rich and robust. Thank you for your careful and thorough review. We have noted your concerns regarding the necessity of the dynamic planning, the experimental setup, and the training objectives. We have made corresponding clarifications and conducted additional experiments, and our response is as follows:


W1: Necessity of Dynamic Reoptimization

Thank you for raising the concern. It is true that dynamic replanning may be unnecessary if distance-optimal static routes remain feasible after all requests are revealed. However, this condition does not necessarily hold under the working-day deadline HH, as delaying dispatch reduces the time available for route execution.

To illustrate this issue, we conduct two experiments on 100 U–U DVRP100 instances, leading to the following findings:

  • Offline static routes cannot simply be postponed until all requests are revealed. We use HGS [1] to solve the static problem with full knowledge of all requests and their release times, subject to the original temporal constraints. We then check whether these routes remain feasible if dispatched at Tco=0.5HT_{\mathrm{co}}=0.5H. All 100 instances contain at least one infeasible route, and 82.49% of routes exceed the remaining travel-time budget H−TcoH-T_{\mathrm{co}}, even without accounting for service durations.
  • Solving the problem until all requests revealed leads to longer routes and more vehicles. We introduce an All-Revealed HGS baseline that starts dispatching at Tco=0.5HT_{\mathrm{co}}=0.5H and optimizes routes within the remaining time budget. HGS is run once per instance and the neural methods are evaluated without aug-8.
MetricAll Revealed HGSNPR(POMO)NPR(ReLD)
Distance20.8617.7017.76
Vehicles15.1511.2211.30

These results demonstrate that waiting until all requests are revealed can compromise both route feasibility and solution quality. Therefore, dynamic replanning is necessary in out setting.

References:

  1. Vidal, Thibaut. "Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood." Computers & Operations Research 140 (2022): 105643.
AuthorsOpenReview ↗

W2/Q1: Sensitivity to Replanning Frequency and Advanced-Commentment Horizon

W2/Q1: Sensitivity to Replanning Frequency and Advanced-Commentment Horizon

Thank you for your comments and suggestions for additional experiments.

As reviewer g3uw also noted, you both raised concerns about the sensitivity of NPR to the choice of replanning frequency and commitment horizon. We conducted experitmens using the same 1,000 U–U test instances and original model checkpoints, without any retraining or fine-tuning.

The results are summarized below, with inference times reported in parentheses:

KKTacΔT_{ac}\DeltaALNSPOMONPR(POMO)ReLDNPR(ReLD)
200.2H17.77 (15.2h)21.06 (1.1m)17.26 (1.0m)19.86 (1.2m)17.25 (1.1m)
400.2H17.91 (19.3h)21.92 (2.1m)17.33 (1.9m)20.65 (2.6m)17.34 (2.3m)
800.2H18.08 (44.5h)22.61 (3.8m)17.42 (3.4m)21.35 (3.9m)17.46 (3.9m)
400.1H17.61 (19.6h)23.11 (2.2m)17.00 (1.8m)19.97 (2.3m)17.01 (2.2m)
400.3H18.25 (20.3h)22.54 (1.8m)17.80 (1.6m)21.29 (2.1m)17.81 (1.9m)
  • Robustness to replanning frequency. We varied K∈20,40,80K\in \\{20,40,80\\} while fixing the commitment horizon at 0.2H0.2H. NPR consistently reduces distance relative to static training across the three configurations.
  • Robustness to commitment horizon. With K=40K=40, we varied the commitment horizon from 0.1H0.1H to 0.3H0.3H. NPR again consistently improves both neural backbones across all tested horizons.
  • Feasibility and Runtime. All methods achieve 100% feasibility across all configurations. NPR also maintains runtime comparable to static training.

These results demonstrate that NPR's gains are not specific to the default configuration K=40K=40, Tac=8T_{\mathrm{ac}}=8 epochs and generalize to different execution protocols without retraining. We will include these results in the revised manuscript. Thank you again for this valuable suggestion.

AuthorsOpenReview ↗

W3/Q3: Temporal Objective and Response-Time Optimization - Part 1

W3/Q3: Temporal Objective and Response-Time Optimization - Part 1

Thank you for raising the issue that dynamic routing needs to consider the timing of decisions. In fact, in our problem denifition, the timing of decision is jointly determined by the working day, the route generated by the neural solver, and the execution protocol. Even for a distance-only objective, the generated route can indirectly affect the timing of decison, capturing the temporal nature of problem. Therefore, in many studies on dynamic routing, distance is used as the only evaluation metric [1, 2].

The response time you mentioned is also a metric for quantifying dynamic problems, so we conducted experiments and added response time as an evaluation metric, as an additional point of discussion.

In the experiments, we found that NPR optimizes route distance without sacrificing response time, and the currently trained model can support a trade-off between route distance and response time:

  • NPR improves routing efficiency without substantially compromising response time. We evaluated the original distance-only models using average customer response time, defined as RT‾=1n∑i(Ti−ri)\overline{RT}=\frac{1}{n}\sum_i(T_i-r_i), where TiT_i is the actual service-start time and rir_i is the original request release time. Across all problem size, NPR reduces travel distance while the absolute differences in average response time between static and NPR models remain within 0.08. This suggests that NPR's distance improvements do not come at the expense of response time, although response time is not explicitly optimized by the original objective.
MethodN=100 (obj.)N=100 (RT‾\overline{RT})N=200 (obj.)N=200 (RT‾\overline{RT})N=500 (obj.)N=500 (RT‾\overline{RT})N=1000 (obj.)N=1000 (RT‾\overline{RT})
POMO21.923.9233.764.0778.774.29187.764.42
NPR(POMO)17.333.9226.14.0859.464.31121.084.37
ReLD20.653.8330.834.0364.674.30129.154.39
NPR(ReLD)17.343.9125.654.0754.644.30103.424.35
  • At inference, accounting for response time enables a tradeoff between distance and response time. We next investigated whether response time could be incorporated into candidate selection during inference without retraining the models. We modified candidate selection from R=−LR=-L to R=−(L+λRTtotal)R=-(L+\lambda RT_{\mathrm{total}}), where RTtotal=∑i(Ti−ri)RT_{\mathrm{total}}=\sum_i(T_i-r_i). We calibrated λ\lambda using multiple trajectories sampled by the original λ=0\lambda=0 NPR(POMO) model on randomly generated U-U100 instances. Specifically, we took the median across instances of Std⁡(L)/Std⁡(RTtotal)\operatorname{Std}(L)/\operatorname{Std}(RT_{\mathrm{total}}), obtaining λref=0.09\lambda_{\mathrm{ref}}=0.09. We then evaluated λ=0.5λref=0.045\lambda=0.5\lambda_{\mathrm{ref}}=0.045 and λ=λref=0.09\lambda=\lambda_{\mathrm{ref}}=0.09, without updating model parameters. The results show that for most model variants, as λ\lambda increases, the route distance increases while the response time decreases. This indicates that our existing models can provide a trade-off between route distance optimization and customer response time.

The results are summarized as follows, with the values in parentheses representing the percentage increase or decrease relative to λ=0\lambda=0.

Methodλ=0\lambda=0 (obj.)λ=0\lambda=0 (RT‾\overline{RT})λ=0.5λref\lambda=0.5\lambda_{ref} (obj.)λ=0.5λref\lambda=0.5\lambda_{ref} (RT‾\overline{RT})λ=λref\lambda=\lambda_{ref} (obj.)λ=λref\lambda=\lambda_{ref} (RT‾\overline{RT})
POMO21.923.9221.84 (-0.46%)3.90 (-0.51%)22.49 (+2.60%)3.94 (+0.51%)
NPR(POMO)17.333.9217.56 (+1.33%)3.83 (-2.30%)17.96 (+3.64%)3.81 (-2.81%)
ReLD20.653.8320.71 (+0.29%)3.71 (-3.13%)21.26 (+2.95%)3.64 (-4.96%)
NPR(ReLD)17.343.9117.56 (+1.27%)3.83 (-2.05%)17.95 (+3.52%)3.80 (-2.81%)
Reviewer_YSZ4OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies how to extend autoregressive neural routing solvers, primarily developed for static problems, to dynamic vehicle routing. The proposed Neural Periodic Reoptimization (NPR) framework represents execution history through a residual-state interface, preserves irrevocable route prefixes through Commitment-Consistent Decoding (CCD), and trains on residual states generated by the model's own planning and execution. Its main contribution is a framework for adapting existing neural backbones to dynamic execution, rather than a new backbone architecture. The evaluation covers POMO and ReLD, synthetic instances with 100–1,000 customers, 122 public benchmark instances with dynamically generated request releases, and extensions involving time windows, alternative training objectives, and different proportions of dynamic requests. Under shared dynamic inference pipelines and budgets, NPR consistently improves upon static training. For example, on 1,000-customer Cluster–Poisson instances, ReLD's gap to ALNS decreases from 40.77% to 3.92%, while its mean gap on the public benchmarks decreases from 12.52% to 1.78%.

Critical strengths
  1. A reusable framework for transferring static neural routing solvers to dynamic execution settings. The paper's important contribution is enabling neural construction solvers such as POMO and ReLD, primarily designed for static problems, to perform dynamic replanning under progressively revealed requests and irrevocable execution decisions. Through the residual-state interface, commitment-consistent decoding, and rollout-based training, the framework connects these existing backbones to dynamic execution while retaining their main architectures and construction-based inference procedures. This provides a concrete path for reusing existing capabilities and future advances in static neural combinatorial optimization, and is a major reason for supporting acceptance.
  2. Substantial and consistent empirical improvements under matched comparisons. The statically trained baselines also use the dynamic inference interface and CCD, allowing the main experiments to assess the benefit of changing the training procedure relatively directly. Improvements occur across two backbones, multiple problem sizes, and both synthetic and public benchmarks with dynamic request releases. They also persist with pairwise preference training and customer time windows. The improvements achieved by ReLD on large instances and public benchmarks demonstrate practical effectiveness beyond a conceptual adaptation framework.
Critical weaknesses
  1. The architectural novelty at the backbone level is relatively limited. The main contributions concern the dynamic adaptation framework: residual-state representation, commitment-consistent decoding, and training on dynamic trajectories. Although these components have practical value, the work largely retains the POMO and ReLD backbones. Architectural modifications are mainly confined to input and context projections and decoding constraints, without introducing a substantial new backbone design. I therefore recognize the framework's effectiveness and reusability, while considering its architectural contribution relatively incremental. This is the main reason I favor weak acceptance rather than a stronger recommendation.
  2. The comparability of training data exposure and actual computational budgets requires further clarification. The authors report 450,000 updates and the same batch size for static and NPR training, which controls the number of optimization steps and nominal sample presentations. However, dynamic training generates multiple correlated residual states from the execution of a base instance, whereas static training uses independently generated complete instances. The number of independent base instances, the cumulative number of effective nodes and decoding decisions processed, and actual training time may therefore differ. This does not establish that the comparison is unfair, nor does repeatedly replanning a dynamic instance necessarily imply that NPR receives more training data. Reporting these quantities would help distinguish the benefits of adapting the training-state distribution from the effects of differences in training resources.
Questions for authors

Clarification and additional validation regarding training-budget comparability: Beyond matching the number of updates and batch size, how do static and NPR training compare in terms of independent base instances, effective training states, cumulative nodes or decoding decisions processed, and actual training time? Could the authors report these statistics and indicate whether the main performance advantage persists under matched training compute?

3 comments
AuthorsOpenReview ↗

W1: Novelty of Backbone Architecture

First, we thank the reviewer for recognizing the reusability and practical effectiveness of the framework we proposed. Thank you for your careful and thorough review. We have noted your concerns regarding the novelty of the backbone architecture in our method and the computational resources fairness. Our clarifications and responses are as follows:


W1: Novelty of Backbone Architecture

Thank you for recognizing the practical value of the components we proposed, as well as the effectiveness and reusability of the framework. Regarding the concern about the lack of backbone architecture novelty, we would like to emphasize that our main contribution is not to design a new neural backbone, but to develop a framework that effectively adapts existing static neural construction solvers to dynamic routing, where requests are progressively revealed and execution decisions become irrevocable.

First, this is an important and relatively underexplored problem. As reviewer g3uw mentioned in the strengths, most neural routing solvers have been developed for static problems, while their adaptation to dynamic settings has received comparatively less attention. Directly applying static solvers to dynamic routing is nontrivial, as the routing decisions at each replanning epoch must account for not only newly revealed requests but also the consequences of previous decisions and existing execution commitments. Our work addresses this gap by adapting static neural construction solvers to dynamic routing.

Second, we propose three complementary mechanisms to address the key challenges in this adaptation: residual-state representation, Commitment-Consistent Decoding (CCD), and rollout-induced residual-state training. As reviewers g3uw and NFom noted in the strengths, the residual-state representation formulates the dynamic process as a sequence of residual routing subproblems, while CCD is a simple and clean yet effective and reusable mechanism without requiring external search or repair. Furthermore, dynamic training uses residual states generated by the solver during its own rollouts, reducing the gap between static training data and the states encountered in dynamic environments. Together, these mechanisms address concrete challenges in transferring static neural construction solvers to dynamic routing.

Finally, our focus is on enabling different neural backbones to perform effectively in dynamic environments, rather than redesigning the backbones themselves. As all reviewers also recognized, the framework and its mechanisms are reusable and not tied to a specific backbone. We believe this framework-level contribution has practical value because it enables existing neural construction solvers to be extended to dynamic routing without requiring the development of new backbone architectures.

We hope these clarifications address your concerns.

AuthorsOpenReview ↗

W2/Q: Training-Budget Comparability

W2/Q: Training-Budget Comparability

Thank you for raising the concern about computational resource fairness.

First, we clarify that NPR performs one optimizer update per residual-state batch, rather than per complete dynamic trajectory. Therefore, under the same number of optimizer updates, the total number of effective training states is identical.

Using POMO as the backbone, we report the relevant training statistics below:

Training statisticsPOMONPR(POMO)
Optimizer updates450K450K
Effective training states54M54M
Independent base instances54M1.8M
States per base instance129.3
Cumulative effective nodes3.8B4.4B
Cumulative decoding steps320B231B
Training time18h20h

These statistics show that NPR introduces only modest computational overhead compared with static training, despite generating multiple residual states from each base dynamic instance.

For clarity, cumulative effective nodes count the number of valid customer nodes encountered during decoding, without multiplying by the multi-start width. In contrast, cumulative decoding steps account for the multi-start width.

Although NPR has a higher cumulative effective-node count, it requires fewer cumulative decoding steps. This is because NPR dynamically determines the multi-start width at each decoding step based on the minimum number of available customers across the batch. Consequently, fewer POMO trajectories are expanded, resulting in fewer overall decoding steps.

To further examine whether NPR’s advantage comes from longer training time, we conducted an additional experiment under a matched wall-clock budget of 18 hours. Under this budget, NPR completes 400K optimizer updates:

MethodN=100N=200N=500N=1000
POMO (18h)21.9233.7678.77187.76
NPR (POMO, 18h)17.3426.0959.48120.69

As shown, NPR still outperforms static training across all four problem sizes, even under the same wall-clock training budget.


We thank you for your insightful and professional feedback. By clarification of our contribution, providing the detailed training statistics, and additional expertiment under matched wall-clock budget, we believe we have addressed your concerns the novelty of backbone architecture and the fairness of the computational resource comparison.

We hope that these clarifications and additional results have satisfactorily addressed your concerns. If so, we would greatly appreciate it if you would consider raise your score. We would be happy to continue the discussion if any questions remain. We will upload the revised version before the rebuttal deadline, with the following changes to the PDF: 1. add the training statistics to the Appendix; 2. add the experiment under a matched wall-clock budget to the Appendix.

Dear Reviewer,

I hope this message finds you well.

We would like to kindly follow up on our rebuttal and ensure that we have adequately addressed your concerns. Based on your valuable feedback, we have added Appendix B.4 (Training-Budget Comparability), including the requested training statistics and experiments under matched wall-clock training budgets. We have also further clarified the training configurations of static training and NPR in Section 5 (Training and Inference) and Appendix B.1.

We would greatly appreciate it if you could review these updates and let us know if any concerns remain.

Thank you very much for your time and thoughtful feedback.

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

This paper proposes Neural Periodic Reoptimization (NPR), a framework for applying autoregressive neural routing solvers such as POMO and ReLD to dynamic vehicle routing under a fixed periodic execution protocol. At each decision epoch, the execution history is encoded as a residual routing problem, and a commitment-consistent decoding mask preserves route prefixes that have already been committed. Instead of training on static instances, the solver is trained on the residual states it encounters during its own reoptimization rollouts, using an epoch-local route-length objective. Experiments on synthetic DVRP instances with up to 1,000 customers, public benchmark instances, and a time-window variant show that NPR consistently improves over statically trained counterparts and runs much faster than metaheuristic baselines.

Critical strengths
  • The paper addresses a practically relevant gap, as most neural routing solvers are developed for static problems and their use in dynamic settings has received less attention.
  • Commitment-consistent decoding is a simple and clean way to preserve committed route prefixes, requiring no additional parameters and integrating easily with existing backbones.
  • The improvements over static training are consistent across two backbones, two training objectives, several problem sizes and distributions, and the public benchmark instances.
  • The problem setting and execution protocol are formalized carefully, which makes the method and its assumptions easy to follow.
Critical weaknesses
  1. The main concern for me is the scope of what is actually learned. Most of the key dynamic decisions, such as when a vehicle is dispatched, which parts of a route become fixed, and how often replanning happens, are governed by a hand-designed execution protocol that is fixed throughout the paper (40 decision epochs, an advanced-commit horizon of 8 epochs, a request cut-off at 0.5H, and a rule that dispatches a route only when its projected return falls within the last 20% of the day). The neural solver only replaces the route-construction step inside this protocol, which is a relatively small part of the overall decision process. The paper does not justify why this particular protocol is chosen, and it is not clear that it is a reasonable or near-optimal choice. More importantly, since the core idea of NPR is to train on states induced by the protocol, it is natural to ask whether the method works under other protocols as well. All experiments use the same protocol, and the transfer experiments in Appendix F only change the data distribution, not the rules. Showing that NPR can be trained and remains effective across a range of protocols, for example different numbers of epochs, commitment horizons, or dispatch rules, and whether a model trained under one protocol transfers to another, would make the contribution much more general and impactful. Could the authors comment on how sensitive NPR is to the choice of protocol?
  2. The evaluation protocol does not seem valid for a dynamic problem. According to Section 5 and Appendix B.1–B.2, every reported result is the minimum final distance over eight independently executed dynamic trajectories per instance (eight augmentation branches for the neural methods and eight runs for ALNS and ContDVRP). Although each trajectory is non-anticipative on its own, choosing the best one after the whole day has been executed relies on information that is only available in hindsight. In practice, only one trajectory can be carried out, and there is no way to know which branch will end up being the best before the requests are realized. The reported numbers therefore correspond to an oracle best-of-eight outcome that cannot be achieved in deployment, which undermines the main claims, including the small or even negative gaps to ALNS. Since methods may also differ in their run-to-run variance, this selection could change the relative comparisons as well. A more appropriate protocol would be to execute a single trajectory per run, repeat it multiple times, and report the mean together with the variance. How do the main results in Tables 1–5 change under such an evaluation?
  3. The training objective does not account for the future consequences of each decision. As defined in Equation (8), the reward at each epoch is only the length of the current completion plan over the requests revealed so far, and the authors explicitly note in Section 4.3 that this does not optimize the online objective through credit assignment across epochs. I appreciate that training on the residual states produced by the model’s own rollouts exposes it to the consequences of its earlier plans, and that the residual-state design keeps the input close to what the model sees at deployment. However, the learning signal itself still treats each epoch as an essentially static problem: a plan that is short now but leaves the fleet poorly positioned for later requests is rewarded in the same way as one that does not. This seems at odds with the paper’s own motivation in the introduction, which highlights exactly this issue as what makes dynamic routing difficult. It would be helpful to compare against a variant trained with a longer-horizon objective, such as the total distance actually traveled over the day, or to explain why the epoch-local objective is sufficient. This might also relate to the remaining gap to ALNS at DoD 0.25 (Table 8), which is not discussed.
  4. The methodological novelty seems somewhat limited. Training on states visited by the current policy is a standard idea in reinforcement learning and imitation learning, and commitment-consistent decoding is essentially an additional mask that forces committed prefixes to be decoded in order. Both components are sensible and well executed, but the paper could make it clearer what is fundamentally new beyond carefully adapting existing neural solvers to a fixed periodic reoptimization protocol.
  5. Several relevant lines of work are neither discussed nor compared against. The related work focuses mainly on metaheuristics and learning-guided optimizers, but does not cover end-to-end reinforcement learning approaches that model dynamic routing as a sequential decision problem with returns accumulated over the whole episode (e.g., Bono et al., MARDAM; Joe & Lau, 2020), or anticipatory methods that decide when to dispatch and when to wait, such as scenario-based approaches (e.g., Bent & Van Hentenryck, 2004) and methods developed around the EURO–NeurIPS dynamic VRPTW competition, including ML-CO (Baty et al., 2024), which is cited but not compared. In addition, a rolling-horizon baseline using a strong static solver such as HGS would give a clearer picture of how strong the reported ALNS reference is, especially since NPR and even ContDVRP outperform ALNS at n = 100. Including some of these comparisons would make it easier to judge where NPR stands relative to the state of the art in dynamic routing.

After rebuttal

I want to thank the reviewers for the detailed responses. They have addressed most of my concerns, and I have accordingly raised my score to 3.

Questions for authors

See the weaknesses.

7 comments
AuthorsOpenReview ↗

W1: Scope of Learning and Protocol Sensitivity

Thank you for recognizing that "our research addresses a practically relevant gap, CCD is a simple and clean yet effective and reusable approach, the evaluation evidence is rich, and the problem setting is well-structured". Thank you for your careful and thorough review. We have noted your concerns regarding evaluation protocol, execution protocol sensitivity, and long-horizon credit assignment. We have made corresponding clarifications and conducted relevant experiments. Our response is as follows:


W1: Scope of Learning and Protocol Sensitivity

Thank you for your insightful comment. We would like to clarify the role of route construction in dynamic replanning and provide additional experiments to examine the sensitivity of NPR to the execution protocol.

First, NPR learns to construct routes for dynamic replanning, which plays an important role in dynamic decision-making. Although the dispatch and commitment rules are prescribed, the actual execution cost depends on the constructed routes at each step. Specifically, the constructed routes determine the return times of vehicles, which affects whether to dispatch vehicles, which customers are committed, and the residual state encountered in subsequent epochs. Therefore, route construction directly influences not only the current routing plan but also the subsequent execution process.

Second, our default configuration of 40 decision epochs and an advanced-commit horizon of 8 epochs (equivalent to 0.2H) follows the settings used in ContDVRP [1]. We adopt this configuration to maintain consistency with established DVRP benchmark settings, rather than to favor NPR through protocol-specific tuning. We do not claim that this protocol is optimal.

As reviewer NFom also noted, you both are concerned about the sensitivity of the execution protocol. To directly address this concern, we conducted additional experiments by varying the number of decision epochs K∈20,40,80K\in\\{20,40,80\\} and the advanced-commit horizon TacΔ∈0.1H,0.2H,0.3HT_{ac}\Delta\in\\{0.1H,0.2H,0.3H\\}, while keeping the other settings unchanged.

We evaluate two variants of NPR(POMO): (i) NPR(Retrain) retrained under each target protocol and (ii) NPR(Zero-shot) trained under the default protocol K=40,TacΔ=0.2HK=40,T_{ac}\Delta=0.2H, directly transferred to the target protocols without any fine-tuning. The results are summarized below (lower is better).

KKTacΔT_{ac}\DeltaALNSPOMONPR(Retrained)NPR(Zero-shot)
200.2H17.7721.0617.2517.26
400.2H17.9121.9217.3317.33
800.2H18.0822.6117.4817.42
400.1H17.6123.1117.0317.00
400.3H18.2522.5417.7817.80
  • NPR remains effective across different protocols. NPR (Retrained) consistently outperforms both static POMO and ALNS across all five protocols. This demonstrates that the benefits of residual-state training is not limited to the original execution protocol.
  • NPR exhibits strong zero-shot transfer across protocols. NPR (Zero-shot) achieves nearly identical to protocol-specific retraining across all tested settings, with a maximum absolute distance difference of only 0.06. In some settings, the zero-shot model even slightly outperforms the retrained counterpart. These results suggest that the learned routing policy transfers effectively across changes in replanning frequency and commitment horizon, without requiring protocol-specific retraining.

We hope that these results and clarifications adequately address your concerns.

Reference:

  1. Okulewicz et al. "A metaheuristic approach to solve dynamic vehicle routing problem in continuous search space." Swarm and Evolutionary Computation 48 (2019): 44-61.
AuthorsOpenReview ↗

W2: Evaluation Protocol

W2: Evaluation Protocol

Thank you for raising concerns about the validity of the evaluation protocol.

We would like to clarify that the best-of-eight evaluation scheme adopted in our paper has also been used in previous studies on dynamic vehicle routing problems [1, 2] and neural solvers for static vehicle routing problems [3]. This evaluation protocol measures the quality of the best solution an algorithm can obtain under a fixed inference budget. However, we agree that the mean and standard deviation (std) metrics mentioned by the reviewer are also very important, as they can provide a better understanding of an algorithm's practical performance.

To address this concern, we have additionally conducted experiments and report the mean ±\pm std results for the settings in Tables 1, 2, and 4, as well as the mean instance-wise gaps for the settings in Tables 3 and 5. The results are summarized below:

Table 1. Uniform-Uniform

MethodN=100N=200N=500N=1000
ALNS18.73±0.6018.73\pm 0.6025.97±0.6425.97\pm 0.6453.77±0.7353.77\pm 0.7398.23±0.8198.23\pm 0.81
POMO25.36±3.0125.36\pm 3.0137.32±2.4937.32\pm 2.4987.48±6.3287.48\pm 6.32187.76±22.62187.76\pm 22.62
NPR(POMO)17.98±0.4417.98\pm 0.4427.10±0.6727.10\pm 0.6761.08±1.0261.08\pm 1.02125.07±2.66125.07\pm 2.66
ReLD22.40±1.1722.40\pm 1.1733.04±1.5733.04\pm 1.5768.94±3.2968.94\pm 3.29149.28±13.91149.28\pm 13.91
NPR(ReLD)17.99±0.4417.99\pm 0.4426.51±0.5926.51\pm 0.5956.03±0.9956.03\pm 0.99106.50±1.87106.50\pm 1.87

Table 2. Cluster-Poisson

MethodN=100N=200N=500N=1000
ALNS16.81±0.5516.81\pm 0.5522.31±0.5222.31\pm 0.5249.71±0.7449.71\pm 0.7493.92±0.8493.92\pm 0.84
POMO23.76±2.9623.76\pm 2.9634.07±3.6434.07\pm 3.6490.31±10.9090.31\pm 10.90216.12±36.99216.12\pm 36.99
NPR(POMO)16.46±0.4416.46\pm 0.4423.72±0.5423.72\pm 0.5457.24±1.1257.24\pm 1.12119.61±4.20119.61\pm 4.20
ReLD20.09±1.3020.09\pm 1.3028.42±1.8228.42\pm 1.8266.68±5.3066.68\pm 5.30156.29±18.83156.29\pm 18.83
NPR(ReLD)16.48±0.4416.48\pm 0.4423.16±0.5423.16\pm 0.5451.75±0.8951.75\pm 0.8999.01±1.7699.01\pm 1.76

Table 3. DVRP Public Benchmark

MethodN ≤ 200N ≤ 500N ≤ 1000Total
ALNS****
POMO26.55%41.90%63.95%42.27%
NPR + POMO13.77%13.21%18.18%14.71%
ReLD15.57%18.94%26.25%19.67%
NPR + ReLD1.92%8.67%2.77%4.74%

Table 4. DVRPTW Benchmark

MethodN=100N=200N=500N=1000
ALNS24.31±0.3924.31\pm 0.3941.40±0.9041.40\pm 0.9097.41±1.8697.41\pm 1.86172.98±2.35172.98\pm 2.35
POMO31.37±1.9331.37\pm 1.9347.97±2.0247.97\pm 2.02109.20±3.46109.20\pm 3.46217.89±6.24217.89\pm 6.24
NPR(POMO)25.74±0.7525.74\pm 0.7543.99±1.0843.99\pm 1.08101.94±1.88101.94\pm 1.88193.61±3.34193.61\pm 3.34
ReLD29.74±1.4629.74\pm 1.4647.99±2.0147.99\pm 2.01105.04±3.57105.04\pm 3.57183.89±5.09183.89\pm 5.09
NPR(ReLD)25.82±0.7725.82\pm 0.7743.66±1.0943.66\pm 1.0998.14±1.9798.14\pm 1.97172.53±2.50172.53\pm 2.50

Table 5. Different Training Objective

ObjectiveTrainingN ≤ 200N ≤ 500N ≤ 1000Total
Policy GradientStatic26.55%41.90%63.95%42.27%
Policy GradientNPR13.77%13.21%18.18%14.71%
Preference LossStatic23.15%19.90%26.46%22.77%
Preference LossNPR9.04%11.03%13.03%10.85%

The experimental results demonstrate that NPR consistently outperforms static training across the evaluated problem sizes and distributions when mean performance is used as the evaluation metric. Moreover, NPR substantially reduces the std compared with static training, indicating that our method achieves more consistent performance across independent runs.

We will included these additional experimental results and the corresponding discussion in the Appendix of the revised manuscript. We hope that these results address your concern.

References:

  1. Okulewicz et al. "A metaheuristic approach to solve dynamic vehicle routing problem in continuous search space." Swarm and Evolutionary Computation, 2019.
  2. Wang et al. "An adaptive large neighborhood search for the multi-depot dynamic vehicle routing problem with time windows." Computers & Industrial Engineering, 2024.
  3. Huang et al. "Rethinking light decoder-based solvers for vehicle routing problems." ICLR, 2025.
AuthorsOpenReview ↗

W3: Long-Horizon Credit Assignment

W3: Long-Horizon Credit Assignment

Thank you for raising this important concern regarding our training objective. In our earlier experiments, we also investigated a long-horizon training objective, but found that it did not perform as well as the epoch-local objective. This was one of the reasons we adopted the epoch-local objective in our final method. To provide further clarification, we report below the implementation details and experimental results of our investigation.

The long-horizon implementation works as follows:

  • After each rollout is complete, we obtain the final route distance. We then use this distance to construct return-to-go estimates for every subroute generated at each decision epoch, thereby assigning credit to earlier decisions. Let Cb,kC_{b,k} denote the distance executed before decision kk for instance bb, and let DbD_b denote its final total execution cost. The return is: Gb,k=−(Db−Cb,k)G_{b,k}=-(D_b-C_{b,k}).
  • Training currently uses a leave-one-out baseline across the other instances in the batch: Gˉ−b,k=1B−1∑j=1,j≠bBGj,k\bar{G}_{-b,k}=\frac{1}{B-1}\sum_{\substack{j=1, j\ne b}}^{B}G_{j,k}. The advantage is Ab,k=Gb,k−Gˉ−b,kA_{b,k}=G_{b,k}-\bar{G}_{-b,k}.

The results of epoch-local (EL) and long-horizon (LH) is below:

Method1002005001000
POMO21.9233.7678.77187.76
NPR(POMO)-EL17.3326.1059.46121.08
NPR(POMO)-LH21.1637.5698.67209.66

The results indicate that the long-horizon objective does not yield improvements over the epoch-local objective. We attribute this observation to two possible factors.

First, at each epoch, only one candidate plan is selected for execution. Therefore, the final reward reflects only the quality of the executed plan. It cannot directly evaluate the other candidate plans generated at that epoch. In contrast, the epoch-local objective allows multiple candidate plans to be evaluated at every epoch, and all of them can contribute to training. This provides more training signals from the same state.

Second, although the leave-one-out baseline helps reduce the variance of policy updates, it may be less stable than POMO's shared multi-start baseline in our setting.

These results suggest that the epoch-local objective provides a more effective training signal and makes better use of sampled candidate plans than the long-horizon objective in our settings.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.