- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper introduces DVRPTW-Bench, a benchmark for the dynamic vehicle routing problem with time windows, where requests are revealed during operation and solvers must decide when to plan, which requests to dispatch, and how to route them. The authors argue that existing benchmarks either study problem difficulty with a few solvers or compare methods under fixed demand settings, and therefore do not show how the relative strengths of methods change across demand conditions. To address this, they build a controllable instance generator that separately varies problem scale, degree of dynamism, temporal arrival patterns, and spatial demand evolution, together with a unified online evaluation protocol. Under this protocol, they evaluate a broad set of approaches covering planning triggers, search-based and neural routing solvers, and learned and anticipatory dispatch policies. The experiments characterize how demand conditions shape the relative performance of these methods, for example how dynamism, bursty arrivals, and shifting hotspots affect search-based versus neural solvers, and show that adaptive decision timing can improve various routing methods without retraining.
Critical strengths
- The experiments are extensive and detailed, covering a large instance grid and many method configurations, with comprehensive per-slice results in the appendix.
- The paper is clearly written and well organized, making the benchmark design and evaluation protocol easy to follow.
- The authors make a clear effort to make the evaluation as complete as possible, including training-distribution variants, trigger sweeps, and search-budget studies.
- The controlled generator, which varies each demand factor independently, enables clean attribution of performance changes to specific demand conditions.
Critical weaknesses
1. Limited advancement over prior work. Most components of the benchmark come from existing work. The problem setting closely follows the EURO–NeurIPS dynamic VRPTW, each demand factor has been studied in prior benchmarks (as Table 1 shows), and all evaluated methods and the offline reference are existing implementations. The main contribution is therefore combining these elements into a larger factorial grid under one protocol. Such a contribution can be valuable, but only if it yields insights that prior work could not provide. However, most findings are consistent with established intuitions, and the mechanisms proposed to explain them are not directly tested. Closely related resources such as dvrpsim and SVRPBench are also not included in Table 1, so the claimed gap is not fully established. I would encourage the authors to clarify which conclusions could not have been obtained from existing benchmarks.
2. Lack of real-world data and calibration. All instances are synthetic, and the generator’s settings, such as four narrow burst peaks, a fixed hotspot strength, clustered Gaussian customer locations with a central depot, and the ranges of lead times and window widths, are not calibrated against real data. A real-world delivery dataset is cited only to justify placing time windows after request creation. As a result, it is unclear whether the chosen configurations span realistic demand regimes, or whether conclusions drawn from them would hold in practice. This is a missed opportunity: calibrating the generator against real operational data, or including real-data-derived instances such as those used in the EURO–NeurIPS competition, would let the benchmark show how closely its scenarios reflect reality, which would be a valuable contribution in its own right.
3. Questionable evaluation of neural baselines. The neural constructors are trained on static VRPTW instances from the RL4CO generator, whose spatial and temporal distributions differ substantially from those of the benchmark. Moreover, the “scale-matched” setting matches the nominal daily number of customers, whereas the actual planning pools contain only a few to around a dozen requests per call, so the models are applied far outside their training sizes. The models are also used without the post-optimization (for example, local search) or inference-time augmentation that is standard in the neural combinatorial optimization literature, and key details such as the decoding strategy and how departure times are chosen are not reported. Consequently, the large gap to HGS cannot be attributed to the limitations of neural construction itself rather than to distribution shift or the specific usage protocol. Training on planning-pool snapshots collected from the benchmark, or adding a simple post-optimization step, would help disentangle these factors.
4. Some scenarios and combinations are not covered. This is a minor point, but several practically relevant settings are not considered: limited fleet capacity (which the authors note as a limitation), stochastic or time-dependent travel times, request cancellations, and reassignment of vehicles en route. In addition, although the introduction emphasizes the coupling between decision timing, dispatch, and routing, the trigger study pairs triggers only with HGS and neural constructors, and not with the dispatch policies. Including these settings and combinations in future versions would make the benchmark more comprehensive.
After rebuttal
I'd thank the authors 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.
3 comments
Response (2/2): Response to W2-4/Q2-4
W2 We evaluate Meituan food-delivery orders from the 2025 INFORMS TSL Data Challenge (Wang et al., 2025) and Cainiao’s LaDe-P pickup data (Wu et al., 2023), fitting on earlier dates and testing on held-out days.
(1) Real demand supports controllable hotspots. Permutation tests with 500 spatial-label shuffles, preserving order times, detect significant adjacent-period spatial drift on all seven held-out days in Shanghai and Hangzhou, one of two Meituan days, and none in Jilin. These differences support both V and S scenarios. Fitted mean hotspot intensity ranges from 0.11 to 0.42 across six datasets; R was fitted to Meituan, while B and provide stress settings.
(2) The same equations fit temporal and spatial demand. Staged fitting isolates release times (G1), lead times and windows (G2), static clusters (G3-S), and evolving hotspots (G3), retaining defaults for unfitted components. Across six datasets, mean held-out Wasserstein errors are 8.74/10.08/0.52 minutes for release times/lead times/window widths. Selected results are:
| Dataset | Significant hotspot days | Mean α | (min): release / lead / window | Spatial-drift error: G3-S → G3 |
|---|---|---|---|---|
| Meituan | 1/2 | 0.11 | 6.36 / 0.77 / 0.65 | 0.00097 → 0.00081 |
| Shanghai | 7/7 | 0.42 | 17.92 / 10.01 / 0.49 | 0.00658 → 0.00170 |
| Hangzhou | 7/7 | 0.20 | 7.04 / 16.10 / 0.52 | 0.00561 → 0.00132 |
| Jilin | 0/7 | 0.18 | 8.77 / 12.45 / 0.26 | 0.00606 → 0.00545 |
Hotspot modeling reduces spatial-drift error by 74.1%/76.5% in Shanghai/Hangzhou, versus 10.2% in Jilin, consistent with the significance tests.
(3) Calibrated data reproduce real-stream method rankings. We evaluate 21 paired real/generated instances from Hangzhou region 80: three replicas per day over June 24–30. All five methods achieve 100% service, with matching rankings across all pairs. ML-CO reduces DPC relative to HGS by 13.88%/17.46% on real/generated streams, and ICD-history by 28.85%/31.16%. Details appear in Appendix J.
W3 We separately evaluate snapshot fine-tuning for distribution and scale mismatch, followed by PyVRP local search. DPC gaps to rolling HGS across 1,350 instances are:
| Model | Original | Fine-tuned | Fine-tuned + local search |
|---|---|---|---|
| PolyNet | +15.10% | +7.66% | +1.64% |
| SymNCO | +15.32% | +12.50% | +1.73% |
| POMO | +16.84% | +12.64% | +1.70% |
Fine-tuning removes 2.82–7.44 percentage points, but pure constructors still trail HGS, OR-Tools, ALNS, and both dispatch methods. Local search reduces gaps to 1.64–1.73%, outperforming OR-Tools and ALNS for an additional 0.075–0.153 s/instance.
HGS still benefits more from concentrated demand: after fine-tuning and local search, constructor OG decreases by 7.20–7.31 points under US → BS and 3.82–3.89 under US → UV, versus 8.32 and 4.54 for HGS. Under hotspot shifts, fine-tuning alone benefits PolyNet; POMO and SymNCO improve mainly through local search.
Models use one greedy decode without augmentation or multistart, followed by exact capacity/time-window feasibility projection; infeasible visits return to the pending pool. Routes depart at the latest feasible time at or after the current time. Local search accepts feasible improvements under a 0.05 s soft budget per call. These rules will be documented in Appendix C.1.
W4
The benchmark assumes ample vehicles, deterministic travel, and routes fixed after departure. Undispatched cancellations require only pending-pool updates; dispatched-order changes, diversion, and limited fleets require extended execution states and resource constraints and will be acknowledged as limitations.
On the 1,500 dynamic instances, replacing Fix-30 with Urgency-10 reduces ML-CO's paired DPC by 1.89% and approximately halves both its planning calls and solver time. This reduction is accompanied by a decrease in service rate from 99.25% to 95.29%, indicating a computation--quality--service trade-off rather than an unqualified improvement. One possible explanation is that the evaluated ML-CO policy was trained from online states generated under Fix-30; changing the trigger alters the timing and distribution of the states encountered at inference. Identifying an effective trigger for ML-CO may therefore require jointly designing the trigger and dispatch policy, or retraining the policy on states generated by the target trigger.
We will incorporate the additional experiments and key findings into the revised manuscript. We hope these clarifications and additional results address your concerns, and we would appreciate your reconsideration in light of this evidence. Thank you again for your constructive feedback.
Thank you for the detailed responses. They have addressed most of my concerns, and I have accordingly raised my score to 3.
Response (1/2): Response to W1/Q1
Thank you for the detailed suggestions. Below we set out three advances over existing parameterized models and the real-data evidence.
W1 We agree that demand factors are not new: van Lon et al. (2016) generate multi-peak arrivals and Zhang et al. (2023) generate time-varying hotspots. Our contribution lies in the following three advances.
Advance 1: a more realistic and flexible demand model. Our parameterized family independently controls temporal peaks and spatial hotspots, supports asymmetric demand patterns, and can be fitted directly to real orders.
Advance 2: calibration to real cities, for testing and for training. Meituan resembles R with weak hotspots (α=0.11), Shanghai resembles B with stronger hotspots (α=0.42), and Jilin resembles B without significant hotspots. Our staged calibration fits release times, lead times, windows, clusters, and hotspot dynamics (W2). The calibrated generator reproduces method rankings across all 21 paired Hangzhou real/generated instances and can supply additional test and training data. Matching training to benchmark snapshots already narrows neural gaps by 2.82–7.44 percentage points.
Advance 3: method rankings that change with demand conditions. Across 120 dynamic configurations, 22 of 36 method pairs reverse order at least once. These results identify where each method performs well or fails. The open-source code supports further targeted evaluation (https://anonymous.4open.science/r/iclr-dvrptw0925).
Which conclusions could not be obtained from existing benchmarks. The following results require varying factors or interactions that existing benchmark settings leave unexamined:
We will add SVRPBench and dvrpsim to Table 1. The reason that we didn't put these two research into Table1 is that SVRPBench studies robustness under stochastic, time-varying travel; dvrpsim provides general dynamic-routing simulation. DVRPTW-Bench complements these tools through controlled demand generation and systematic evaluation of planning timing, dispatch, and routing. The focus and conclusions of these three researches are different.