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

Title: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

Abstract:KAYROS is an open-source solver for duration-minimization time-dependent vehicle routing problems, with or without time windows (TDVRPTW, TDVRP). In these variants, travel times change with departure time, and each route's dispatch time is a decision. To the best of the author's knowledge, it is the first openly available solver that is both anytime, streaming improving solutions from the first seconds, and exact, proving optimality with publicly verifiable certificates, for these problems over rich piecewise-linear travel- time functions rather than a time discretization. It has no proprietary dependency and installs with one command. It builds on the state of the art for time-dependent function composition and exact solving, extending the open-source branch-price-and-cut solver of Lera-Romero, Miranda Bront and Soulignac (2020) with an open LP backend, anytime and warm- start behavior, checker-exact pricing, and exact treatment of stepwise travel times. On the MAMUT-routing benchmark collection, KAYROS stands behind 468 published optimality certificates, each requiring agreement among four independent solves, and five certificates strictly improve published reference values. The report also introduces Poryos2026, a benchmark family designed and generated by the author from real OpenStreetMap city road networks. Its 1,080 paired CVRP, VRPTW, TDVRP and TDVRPTW instances combine real road geometries with controlled synthetic demands, time windows and congestion. Every instance carries a checker-validated best-known solution. This report presents the solver, its certification protocol, the benchmark's generation and feasibility guarantees, and their experimental connection for a broad technical audience. It is also a case study in the intensive human-AI collaboration that made this body of work feasible while keeping its claims independently verifiable.

30 pages, 7 figures, 3 tables. Technical report accompanying the KAYROS solver and Poryos2026 benchmark family

Optimization and Control (math.OC); Artificial Intelligence (cs.AI); Mathematical Software (cs.MS)

G.1.6; F.2.2; G.2.2

arXiv:2607.23116 [math.OC]

(or arXiv:2607.23116v1 [math.OC] for this version)

https://doi.org/10.48550/arXiv.2607.23116 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.