arXiv cs.AI· Florian Rascoussier, Romain Billot, Lina Fahed, Christine Solnon·· 11 小时前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 可在明确的算术与搜索假设下给出计算最优性证书。
正文 · AI 翻译
摘要：时间相关路由认识到，同一段行程的耗时取决于出发时间。在时长最小化目标下，每辆车的出发时间也成为决策变量。文献中已有针对该情形的精确方法，但研究人员和从业者一直缺少一个可直接使用的开源求解器，能够同时结合丰富的分段线性行驶时间、早期可行解和最优性声明。KAYROS 填补了这一空白：它在同一个校验器一致的引擎上提供两种模式：一种迭代局部搜索，可流式输出不断改进的解；一种分支定价割方法，可在明确的算术和搜索假设下给出计算最优性证书。它只需一条命令即可安装，且没有专有依赖。公开的 MAMUT-routing 存储库目前包含 704 份 KAYROS 证书，遵循四求解发布协议，该协议还促成了此前无效声明的撤回和修复。本报告为 MAMUT-routing 提出两项互补的基准贡献。第一项整合了 Blauth2024，这是文献中的一个基准，其行驶时间源自实测的 Uber 速度，KAYROS 在其中全部 40 个实例上给出了新的已知最优解。第二项提出了 Poryos2026，这是一个包含 1,080 个配对静态和时间相关实例的新基准，基于 OpenStreetMap 道路网络和受控合成交通构建。最后，本报告描述了这项工作背后密集的人机协作，以及使输出保持可独立验证的验证实践。
| 评论： | v3：31 页，7 幅图，4 张表。更新了作者信息、所属机构和致谢。澄清了 binary64 校验器一致性，并固定使用 KAYROS 1.6.1 与 mamut-routing-lib 0.11.0。随 KAYROS 和 Poryos2026 发布的技术报告。无新实验 |
| 主题： | 优化与控制（math.OC）；人工智能（cs.AI）；数学软件（cs.MS） |
| MSC 分类： | 90B06（主分类）90C27、90C57、90C59、90-04、90-11（次分类） |
| ACM 分类： | G.1.6；F.2.2；G.2.2 |
| 引用为： | arXiv:2607.23116 [math.OC] |
| （或 arXiv:2607.23116v3 [math.OC] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2607.23116 由 DataCite 颁发的 arXiv DOI |
提交历史
来自：Florian Rascoussier [查看电子邮件]
[v1]
2026年7月25日星期六 09:16:40 UTC（145 KB）
[v2]
2026年8月11日星期二 17:41:16 UTC（141 KB）
[v3]
2026年10月16日星期五 14:55:58 UTC（141 KB）
来源：arXiv cs.AI · arxiv.org