research · tech · 22 Jul 2026

Kayros: an anytime and exact solver, and the Poryos2026 benchmark family

22 Jul 2026 0nyr

Update (29 September 2026). The Kayros paper and technical report are now available. A separate paper on anytime solver evaluation and report on Hexaly thread scaling document the evaluation choices and a complementary experiment. The research overview explains how the four works fit together. The July announcement below describes the initial release.

Two pieces of my PhD work are now public and worth introducing together: Kayros, an open-source solver, and Poryos2026, a benchmark family it produces solutions for. Their names are a matched pair, borrowed from Greek: Kairos for the right moment (timing), Poros for the way or path. Kayros is about timing, Poryos is about the ways.

Kayros

Kayros is an open-source solver for duration-minimization time-dependent vehicle routing, covering both the time-window variant (TDVRPTW) and the plain TDVRP. Time-dependent means travel times change with the time of day, so the same trip can take more or less time depending on when you set out. Kayros represents this with continuous piecewise-linear arrival-time functions rather than a coarse time discretization.

To my knowledge it is the first solver that is both anytime and exact and open source for this duration-minimization time-dependent setting with a rich piecewise-linear time-dependent representation. It runs in two modes on one engine: an anytime heuristic that returns steadily improving solutions under any time budget, and an exact branch-price-and-cut mode that can certify optimality. The exact side runs on the open-source HiGHS solver, so no commercial license is required.

At the time of this announcement, Kayros was in beta at version 1.1.3. It is developed as part of my PhD and installable from PyPI:

pip install kayros

The source is on GitHub (MIT, Python 3.11+). The technical report described in the update above was forthcoming when this post was written.

Poryos2026

Poryos2026 is a new benchmark family generated to stress-test time-dependent routing on real city road networks with controlled synthetic congestion. Its road geometry comes from OpenStreetMap across five cities: Lyon, Paris, San Francisco, Hong Kong, and Tokyo. Instances come in six sizes, from 10 up to 1000 customers, under several traffic models and intensities.

The headline set is 360 time-dependent TDVRPTW instances (720 if you also count the TDVRP view), plus static CVRP and VRPTW projections on top that are directly comparable to the time-dependent ones since they share the same underlying network and customer locations. Each instance ships with a best-known Duration solution, seeded by Kayros anytime campaigns run on the Grid’5000 cluster. The benchmark data is released under ODbL 1.0, in keeping with its OpenStreetMap origin.

Poryos2026 lives in the MAMUT-routing catalog and is exposed programmatically through the mamut-routing-lib library:

pip install mamut-routing-lib

The family is available there as BenchmarkName.PORYOS_2026. You can browse the instances, their metadata, and their best-known solutions on the family page: mamut-routing.onyr.net/benchmarks/tdvrptw/poryos2026.

How they fit together

Kayros is the engine, and Poryos2026 is one of the datasets it was benchmarked on. The family combines real road geometry with reproducible, modeled traffic, so comparisons can vary time dependence while keeping the underlying customer locations fixed. The solver produces and refines the best-known solutions catalogued for the family. For more on the catalog itself, see my companion post on the MAMUT-routing mirror.

Links