research · tech · 22 Jul 2026

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

22 Jul 2026 0nyr

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.

It is beta (currently version 1.1.3), developed as part of my PhD, and installable from PyPI:

pip install kayros

The source is on GitHub (MIT, Python 3.11+). A technical report describing the method and the engineering behind it is forthcoming.

Poryos2026

Poryos2026 is a benchmark family I generated to stress-test time-dependent routing on realistic congestion. Instead of the usual synthetic traffic constructions, its congestion is derived from real city road networks taken 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; Poryos2026 is one of the datasets it works on, and the only modern time-dependent benchmark family with real road geometry and congestion that I know of. The solver produces and refines the best-known solutions catalogued for the family, and the family gives the solver a realistic, reproducible testbed. For more on the catalog itself, see my companion post on the MAMUT-routing mirror.