- 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
- 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.
- 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
- 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.
- All experiments fix and , leaving sensitivity to replanning frequency and the advance-commitment horizon unexplored.
- 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
- Could the authors vary on fixed test instances while keeping , and report distance, feasibility, and runtime?
- Could the authors report results without aug-8, using matched multi-start widths for static/NPR pairs?
- Could the authors assess whether adding a response-time term to the training objective better captures the needs of dynamic routing?
- Could the authors provide the details of the ALNS reference?
8 comments
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:
| ALNS | POMO | NPR(POMO) | ReLD | NPR(ReLD) | ||
|---|---|---|---|---|---|---|
| 20 | 0.2H | 17.77 (15.2h) | 21.06 (1.1m) | 17.26 (1.0m) | 19.86 (1.2m) | 17.25 (1.1m) |
| 40 | 0.2H | 17.91 (19.3h) | 21.92 (2.1m) | 17.33 (1.9m) | 20.65 (2.6m) | 17.34 (2.3m) |
| 80 | 0.2H | 18.08 (44.5h) | 22.61 (3.8m) | 17.42 (3.4m) | 21.35 (3.9m) | 17.46 (3.9m) |
| 40 | 0.1H | 17.61 (19.6h) | 23.11 (2.2m) | 17.00 (1.8m) | 19.97 (2.3m) | 17.01 (2.2m) |
| 40 | 0.3H | 18.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 while fixing the commitment horizon at . NPR consistently reduces distance relative to static training across the three configurations.
- Robustness to commitment horizon. With , we varied the commitment horizon from to . 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 , 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.
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 , where is the actual service-start time and 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.
| Method | N=100 (obj.) | N=100 () | N=200 (obj.) | N=200 () | N=500 (obj.) | N=500 () | N=1000 (obj.) | N=1000 () |
|---|---|---|---|---|---|---|---|---|
| POMO | 21.92 | 3.92 | 33.76 | 4.07 | 78.77 | 4.29 | 187.76 | 4.42 |
| NPR(POMO) | 17.33 | 3.92 | 26.1 | 4.08 | 59.46 | 4.31 | 121.08 | 4.37 |
| ReLD | 20.65 | 3.83 | 30.83 | 4.03 | 64.67 | 4.30 | 129.15 | 4.39 |
| NPR(ReLD) | 17.34 | 3.91 | 25.65 | 4.07 | 54.64 | 4.30 | 103.42 | 4.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 to , where . We calibrated using multiple trajectories sampled by the original NPR(POMO) model on randomly generated U-U100 instances. Specifically, we took the median across instances of , obtaining . We then evaluated and , without updating model parameters. The results show that for most model variants, as 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 .
| Method | (obj.) | () | (obj.) | () | (obj.) | () |
|---|---|---|---|---|---|---|
| POMO | 21.92 | 3.92 | 21.84 (-0.46%) | 3.90 (-0.51%) | 22.49 (+2.60%) | 3.94 (+0.51%) |
| NPR(POMO) | 17.33 | 3.92 | 17.56 (+1.33%) | 3.83 (-2.30%) | 17.96 (+3.64%) | 3.81 (-2.81%) |
| ReLD | 20.65 | 3.83 | 20.71 (+0.29%) | 3.71 (-3.13%) | 21.26 (+2.95%) | 3.64 (-4.96%) |
| NPR(ReLD) | 17.34 | 3.91 | 17.56 (+1.27%) | 3.83 (-2.05%) | 17.95 (+3.52%) | 3.80 (-2.81%) |
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 H, 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:
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: