arXiv cs.AI· Florian Rascoussier, Romain Billot, Lina Fahed, Christine Solnon·· 12 小时前AI 评分26
KAYROS：开源且可随时给出精确解的时间依赖车辆路径最短时长求解器
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
AI 导读
KAYROS 是一个开源的时间依赖车辆路径最短时长求解器，在同一校验一致引擎上提供两种模式：迭代局部搜索可流式输出改进解，Branch-Price-and-Cut 可在明确的算术与搜索假设下给出计算最优性证书。
正文 · 原文
Abstract: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.
| Comments: | v3: 31 pages, 7 figures, 4 tables. Updated authorship, affiliations and acknowledgements. Clarified binary64 checker consistency and pinned KAYROS 1.6.1 with mamut-routing-lib 0.11.0. Technical report accompanying KAYROS and Poryos2026. No new experiments |
| Subjects: | Optimization and Control (math.OC); Artificial Intelligence (cs.AI); Mathematical Software (cs.MS) |
| MSC classes: | 90B06 (Primary) 90C27, 90C57, 90C59, 90-04, 90-11 (Secondary) |
| ACM classes: | G.1.6; F.2.2; G.2.2 |
| Cite as: | arXiv:2607.23116 [math.OC] |
| (or arXiv:2607.23116v3 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2607.23116 arXiv-issued DOI via DataCite |
Submission history
From: Florian Rascoussier [view email]
[v1]
Sat, 25 Jul 2026 09:16:40 UTC (145 KB)
[v2]
Tue, 11 Aug 2026 17:41:16 UTC (141 KB)
[v3]
Fri, 16 Oct 2026 14:55:58 UTC (141 KB)
来源：arXiv cs.AI · arxiv.org