KAYROS: An Anytime and Exact Solver for the Time-Dependent Vehicle Routing Problem with Time Windows - Extended Version
Abstract
The Time-Dependent Vehicle Routing Problem with Time Windows (TDVRPTW) captures a central difficulty of urban logistics: travel times vary with the time of day, so the cost of a route depends on when it is driven. This paper introduces KAYROS, an open-source solver for the duration-minimization TDVRPTW that is both anytime and exact. It returns improving valid solutions throughout its time budget and can close instances with conditional computational optimality certificates through an integrated branch-price-and-cut component. We extend the composition of continuous arrival-time functions from the literature, previously described only at proof or proposition level, to the left-continuous functions that stepwise benchmarks require. We prove that the composition routine shipped in the checker computes that operation exactly. We analyze when its evaluation and breakpoint normalization are exact in IEEE-754 double-precision arithmetic, and argue that a canonical, epsilon-free checker must define the objective. The anytime layer combines greedy construction, granular time-dependent local search over balanced route trees, and iterated local search, with a fleet-aware descent for a fleet-cost objective. We further propose an anytime evaluation methodology based on a normalized signed primal integral under a pre-committed statistical design. On 212 instances from five families at a one-hour single-threaded budget, KAYROS achieves a pooled anytime score 63.3% lower than the strongest of three available contenders (Timefold, Hexaly, jsprit). All three contrasts are significant under Holm correction. KAYROS improves all 30 high-effort references of Blauth et al. and 10 literature best-known solutions, and publishes 704 such certificates. The solver, benchmarks and campaign data are openly released.
Related
- KAYROS: An Anytime and Exact Open-Source Solver for Duration-Minimization Time-Dependent Vehicle Routing. A Technical Report and a Case Study in Human-AI Engineering
- RELAGRAM: Recursive Latent Graph Model for the Capacitated Vehicle Routing Problem
- Quantum Vehicle Routing Problem: a smart initialization strategy for ill-conditioned optimization landscapes
- Carbon-Aware Electric Vehicle Routing Problem with Decision-Focused Learning
- An Exact Branch-Price-and-Cut Algorithm for a Truck-as-Hub Vehicle Routing Problem with Drones
BibTeX
@misc{rascoussier2026kayros,
title = {{KAYROS: An Anytime and Exact Solver for the Time-Dependent Vehicle Routing Problem with Time Windows - Extended Version}},
author = {Florian Rascoussier and Romain Billot and Lina Fahed and Christine Solnon},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.29597},
eprint = {2609.29597},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29597},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - KAYROS: An Anytime and Exact Solver for the Time-Dependent Vehicle Routing Problem with Time Windows - Extended Version
AU - Florian Rascoussier
AU - Romain Billot
AU - Lina Fahed
AU - Christine Solnon
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2609.29597
UR - https://arxiv.org/abs/2609.29597
AB - The Time-Dependent Vehicle Routing Problem with Time Windows (TDVRPTW) captures a central difficulty of urban logistics: travel times vary with the time of day, so the cost of a route depends on when it is driven. This paper introduces KAYROS, an open-source solver for the duration-minimization TDVRPTW that is both anytime and exact. It returns improving valid solutions throughout its time budget and can close instances with conditional computational optimality certificates through an integrated branch-price-and-cut component. We extend the composition of continuous arrival-time functions from the literature, previously described only at proof or proposition level, to the left-continuous functions that stepwise benchmarks require. We prove that the composition routine shipped in the checker computes that operation exactly. We analyze when its evaluation and breakpoint normalization are exact in IEEE-754 double-precision arithmetic, and argue that a canonical, epsilon-free checker must define the objective. The anytime layer combines greedy construction, granular time-dependent local search over balanced route trees, and iterated local search, with a fleet-aware descent for a fleet-cost objective. We further propose an anytime evaluation methodology based on a normalized signed primal integral under a pre-committed statistical design. On 212 instances from five families at a one-hour single-threaded budget, KAYROS achieves a pooled anytime score 63.3% lower than the strongest of three available contenders (Timefold, Hexaly, jsprit). All three contrasts are significant under Holm correction. KAYROS improves all 30 high-effort references of Blauth et al. and 10 literature best-known solutions, and publishes 704 such certificates. The solver, benchmarks and campaign data are openly released.
ER -