# 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

arXiv: https://arxiv.org/abs/2607.23116 · HTML: https://mlsanity.com/paper/2607.23116/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 16 references that are in the map.
- First posted on arXiv 25 Jul 2026.

## Builds on (most cited first, 3 of 3)

- [Arc Routing with Time-Dependent Travel Times and Paths](https://mlsanity.com/paper/2004.14473/) (2020)
- [Vehicle Routing with Time-Dependent Travel Times: Theory, Practice, and Benchmarks](https://mlsanity.com/paper/2205.00889/) (2022)
- [Impact of Scaling and Rounding on Metaheuristic Performance for the Vehicle Routing Problem with Time Windows](https://mlsanity.com/paper/2606.09196/) (2026)

## Abstract (arXiv)

Time-dependent routing recognizes that the same journey can take a different time depending on when it begins. Under duration minimization, even the departure time of each vehicle becomes a decision. Exact methods for this setting exist in the literature, but researchers and practitioners have lacked a ready-to-use open solver that combines rich piecewise-linear travel times, early feasible solutions and optimality claims. KAYROS fills this gap with two modes on one checker-consistent engine: an Iterated Local Search that streams improving solutions and a Branch-Price-and-Cut method that can issue computational optimality certificates under explicit arithmetic and search assumptions. It installs with one command and has no proprietary dependency. The public MAMUT-routing store currently contains 704 KAYROS certificates under a four-solve publication protocol, which has also led to the retraction and repair of invalid earlier claims. The report presents two complementary benchmark contributions to MAMUT-routing. The first integrates Blauth2024, a benchmark from the literature whose travel times derive from measured Uber speeds, for which KAYROS provides new best-known solutions on all 40 instances. The second proposes Poryos2026, a new benchmark of 1,080 paired static and time-dependent instances built from OpenStreetMap road networks and controlled synthetic traffic. Finally, the report describes the intensive human-AI collaboration behind this work and the verification practices that kept its outputs independently verifiable.