Technical report TR-2026-01

Introduction

Routing benchmarks usually report the gap to a published record solution. Fleet operations also depend on how quickly a plan can be revised when five stops cancel, two urgent collections appear or a vehicle fails. This report measures both quantities for Elara Route: solution cost at a stated time budget, including a comparison with Google OR-Tools, and replanning time after a disturbance.

The engine

Elara Route accepts a caller-set time budget for solving a routing problem or revising an existing plan. Its mathematical framework and implementation remain proprietary. This report evaluates the returned routes and measured execution times; Section 6 describes how readers can verify feasibility and cost without access to the solver.¹

Experimental protocol

Instances

CVRP: nine Uchoa et al. X-instances [1] (X-n101-k25, X-n148-k46, X-n157-k13, X-n200-k36, X-n251-k28, X-n303-k21, X-n351-k40, X-n439-k37, X-n513-k21). VRPTW: Solomon 100-customer [2] instances C101, R101 and RC101, and Gehring–Homberger 200-customer [3] instances C1_2_1 and R1_2_1. Instances and record solutions come from the community-maintained PyVRP/Instances mirror.

Distance conventions

Official per set: integer rounded Euclidean for X (CVRPLIB EUC_2D); unrounded Euclidean with hard time windows and service times for Solomon and Gehring–Homberger.

Baseline

Google OR-Tools routing solver [4], guided local search, PATH_CHEAPEST_ARC start, slack vehicles, 15 to 20 seconds per instance (CVRP). Our time-window encoding returned infeasible on several instances, so it could not support a fair OR-Tools comparison. VRPTW results are compared with the published record only.

Budgets

Elara: five seconds or less per CVRP instance. VRPTW budgets were five seconds for C101, eight seconds each for R101 and RC101, 12 seconds for C1_2_1, and 15 seconds for R1_2_1. Runs used one thread in CPython 3.14 on a consumer Windows machine and one fixed seed. Variation across seeds remains unmeasured.

Validation

Every Elara solution is re-verified independently of the solver: each customer served once and no customer twice; vehicle capacity respected; time windows re-simulated arc by arc (wait when early, never late, depot closing respected); cost recomputed from the raw routes and required to match the reported value. The predicates are written out in Section 6.

Provable optimality: matching the Z3-certified global optimum

On instances small enough for an exact solver, optimality is decidable, and we certify it. We encoded the capacitated VRP as a satisfiability-modulo-theories problem and used the Z3 theorem prover [6] to compute the provable global optimum. With \(\mathcal{F}\) the set of feasible solutions of the instance and \(\tau^{*}\) the solution Elara returned, the certificate is the prover's verdict on the statement that a cheaper feasible tour exists,

so \(\tau^{*}\) is a global optimum. On every such instance the Elara engine reaches that proven optimum.

Elara matched the certified optimum on all five tested instances. In this setup, the exact method was practical only up to about 10 to 15 nodes. Larger instances are reported by their gap to the published record at the stated time budget.

Results, capacitated VRP

Elara returned a lower cost on all six instances tested with both solvers. The OR-Tools gap was 5.5 times Elara's gap on X-n351 and 1.7 times on X-n513 (Table 1). These comparisons apply to the configurations and budgets reported here.

Results, VRP with hard time windows

C101, R101 and C1_2_1 match the record vehicle counts, with distance gaps of 0.2%, 1.2% and 0.2%. RC101 uses 17 vehicles against the record's 15, with a 2.8% distance gap. R1_2_1 uses 22 against 23 and travels 10.9% farther. Because vehicle count is the first objective, the last two results should be read with both quantities in view; the summary distance range is not a vehicle-matched comparison.

Gap and route length

Across nine instances, the gap has little measured association with vehicle count (Pearson \(r = -0.06\), \(n = 9\), underpowered) and a positive association with customers per route (\(r = +0.76\), \(n = 9\); 95% confidence interval about \(0.20\) to \(0.94\)). Re-optimising the internal order of every route on X-n513, with 24 customers per route, recovered no distance. That result suggests examining the assignment of customers between routes; it does not prove that each route is globally optimal. The sample is too small to establish a general law linking route length and solver performance.

Verification without disclosure: solution certificates

Every solution in Tables 1 and 2 is published as an explicit route list (solution_certificates.json: 123 CVRP routes, 91 VRPTW routes). Re-verifying a certificate requires only the public instance file and arithmetic. Write \(\tau\) for a certificate, a set of routes \(r\), each an ordered sequence of customers beginning and ending at the depot; \(C\) for the instance's customer set; \(q_i\) for the demand of customer \(i\) and \(Q\) for the vehicle capacity; \(d_{ij}\) for the distance under the set's stated convention. A referee checks coverage and capacity,

replays the time windows arc by arc where the instance has them, with \(e_i\) and \(l_i\) the window, \(s_i\) the service time, \(t_{ij}\) the travel time and \(\pi(i)\) the stop before \(i\) on its route, so that a vehicle waits when early and is never late,

and recomputes the cost from the raw routes, which must equal the reported value:

Publishing route certificates allows a proprietary solver's outputs to be checked independently.

Replanning after a disturbance

The production-API test used deterministic seeds. Planning a 200-stop, 10-vehicle day took 4.6 ms. Replanning after five cancellations and three urgent insertions across five moving vehicles took about 1.2 ms. Reassigning 38 outstanding stops after a vehicle breakdown across two remaining vehicles took about 0.8 ms. These timings describe the reported run. We propose recording replanning time alongside solution quality, since both affect whether a fleet can respond to changes during the day.

Reproducibility: the public solve API

At publication, the routing API accepted CVRP and VRPTW instances at POST /v1/solve, using coordinates or a distance matrix together with demands, capacity and time windows. The response included explicit routes, cost, and verification of coverage, capacity and recomputed cost. Registered users could obtain a key through a seven-day trial at route.elara-cortex.com/developers. A comparison with another solver requires the same instance, distance convention, constraints and stated compute budget. Pickup-and-delivery, multi-depot and crew-rostering support were planned extensions at the time of this report.

Limitations

1. The tables cover nine X-instances and five time-window instances. The full X and Gehring–Homberger suites, with multiple seeds, remain further work.
2. The OR-Tools baseline is our configuration of a free solver; commercial solvers such as Hexaly and Gurobi are not yet in the comparison.
3. The record solutions took specialised solvers hours to days [5], [8]. Nothing here claims to match them outright; the claim is the gap at a stated second-scale budget.
4. All Elara timings are from single-threaded interpreted Python. Performance in a compiled deployment was not measured in this report.

Conclusion

Under the reported configurations, Elara returned lower-cost solutions than OR-Tools on all six capacitated instances tested with both solvers, using a time budget three to four times shorter. It came within 0.2% of the record distance on the clustered time-window instances while matching their vehicle counts, matched the certified optimum on five small instances, and replanned the reported disturbances in milliseconds. The results are limited to these instances, budgets and seeds. Route certificates support independent checks of feasibility and cost, using the problem conventions in the standard reference [7].

References

1. Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Vidal, T., & Subramanian, A. (2017). New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3), 845–858.
2. Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2), 254–265.
3. Gehring, H., & Homberger, J. (1999). A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. In Proc. EUROGEN'99, 57–64.
4. Perron, L., & Furnon, V. (2024). OR-Tools (v9). Google. developers.google.com/optimization
5. Helsgaun, K. (2017). An extension of the Lin–Kernighan–Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems. Technical Report, Roskilde University.
6. de Moura, L., & Bjørner, N. (2008). Z3: An efficient SMT solver. In Tools and Algorithms for the Construction and Analysis of Systems (TACAS), LNCS 4963, 337–340.
7. Toth, P., & Vigo, D. (Eds.) (2014). Vehicle Routing: Problems, Methods, and Applications (second edition). SIAM.
8. Vidal, T. (2022). Hybrid genetic search for the CVRP: open-source implementation and SWAP* neighbourhood. Computers & Operations Research, 140, 105643.

Data and receipts

Instances and record solutions: CVRPLIB, Solomon and Gehring–Homberger via the community mirror. Baseline: Google OR-Tools with guided local search. Result files: results.json, lekola_validated.json, vrptw_validated.json and solution_certificates.json. The routing framework remains proprietary; the benchmark materials support verification of its outputs. Further papers are listed on the research page.