Research/Software
A quarter of published routing records run late in double precision
82 of the 300 best-known solutions to the Homberger vehicle-routing benchmarks reach a customer after its time window closes when travel times are not truncated, although all are valid under the rules they were found with; 87 of the 90 late solutions across the benchmark sets can be repaired without an extra vehicle.
Oct 30, 2026 · 6 min read

Vehicle routing with time windows asks for the fewest, shortest delivery routes that reach every customer inside an allowed time slot. Researchers compare methods against best-known solutions published on CVRPLib. We re-checked all 300 best-known solutions for the Homberger instances using exact travel times instead of the truncated ones they were found with. 82 of them (27.3%) reach at least one customer after its window has closed. None of this is an error: every solution is feasible under the DIMACS rules it was found with. But a solver or checker that works in double precision cannot start from, or compare against, about a quarter of the published records, and we list which ones.
82 of 300
Homberger best-known solutions late in double precision
87 of 90
late solutions repaired with no extra route
31.7%
above the fleet bound K* for plain PyVRP on XLTW-Test
The question
Two conventions are in use for these benchmarks. Under the DIMACS rules, each arc's travel time is truncated to one decimal place, so every leg is up to 0.1 time units shorter than the true distance. SINTEF's long-standing records use double precision with no truncation. Along a route the difference adds up, up to 0.1 per arc, until the vehicle waits for a window to open. A solution that arrives exactly on time under one convention can be late under the other. We wanted to know how often that happens in the published files, and whether it matters for anyone comparing results.
What we did
We wrote a checker that recomputes every route under both conventions and lists every late arrival with the number of arcs driven before it. For each study we wrote down the expected outcome before it ran and scored it afterwards. We first checked the 56 Solomon instances and six 1,000-customer instances, confirmed the results with a second, separately written checker using exact 50-digit decimal arithmetic, and then ran the unchanged checker on all 300 Homberger instances, 60 at each of five sizes from 200 to 1,000 customers.
What we found
All 300 Homberger solutions are feasible under DIMACS, with costs equal to their files. In double precision 82 are late: 20 of the 100 in the clustered C families and 62 of the 200 in the R and RC families. Every one of the 169 late arrivals is within what truncation can remove, 0.1 per arc driven, so there is no other error hiding underneath. Another 36 of the 218 on-time solutions come within 0.1 of a due time. We had predicted that no C-family solution would be late; that prediction failed.
Homberger best-known solutions late in double precision, by size
The late routes have a shape. Following every route of every solution, we found 141 late routes on the 90 late solutions across the Solomon and Homberger sets. Late routes in the C2 family are long chains that rarely or never wait, so nothing resets the drift: 15 of 22 never wait at all. A simple count of exposed visits, those with less slack than the drift that could build up before them, separates late from on-time solutions with an AUC of 0.865.
Most are easy to fix. Starting PyVRP from each of the 90 late solutions, with the fleet capped at the solution's own route count and travel times rounded up so that nothing undercuts the exact values, gave on-time solutions for 87. The median distance cost of the repair was +0.43%. A separate exact-arithmetic check confirmed all 87.
Late solutions repaired without an extra route, by family
| Family | Late in double precision | Repaired |
|---|---|---|
| C1 | 5 | 5 |
| C2 | 15 | 15 |
| R1 | 20 | 17 |
| R2 | 15 | 15 |
| RC1 | 15 | 15 |
| RC2 | 20 | 20 |
The three that were not repaired are in the tightest-window family. For two of them, a classical lower bound computed in double precision is above the published route count (59 against 58 for R1_6_1, and 100 against 95 for R1_10_1), so no solution with that many routes can be on time without truncation. When we re-read all 356 files on 2026-11-02, after CVRPLib switched to automatic publishing, the count of late solutions had risen from 90 to 92.
Calibrating a baseline for the new challenge
CVRPLib's VRPTW challenge, with 1,000 to 10,000 customers, ranks fewest routes first and uses nearest-integer rounding, a third convention. To give later methods a floor to compare against, we ran plain PyVRP on all 100 instances of the XLTW-Test set under the challenge's protocol, at one thirtieth of its time limit. All 100 runs stopped by themselves and counted. The fleet search is the weak spot: only 6 runs reached the simple bound K, and none of them is among the 33 instances where capacity never binds.
Vehicles on XLTW-Test against two lower bounds
What it means
A vehicle count or distance found under one rounding convention cannot be compared directly with a record kept under another. Anyone building a double-precision solver or checker should treat about a quarter of the Homberger records as infeasible starting points, or use the repaired versions we publish. For the challenge, the bound gap of 31.7% on the baseline is still open: a dedicated route minimiser did one vehicle worse on each of four instances, and a path-cover bound never tightened K*, so we cannot yet say whether the gap lies in the search or in the bound.


