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
- 采用迭代局部搜索与分支定价切割双模式求解,兼顾效率与最优性证明
- 在40个真实交通数据集上均获得新最优解,1080对静态/动态实例用于测试
- 适合交通规划、物流优化及人机协作研究者使用
时间依赖路径问题中,相同行程耗时随出发时间变化。在最小化行程时长的目标下,每辆车的出发时间也成为决策变量。现有精确方法虽存在,但缺乏可直接使用的开源求解器,无法同时支持分段线性行程时间、早期可行解生成与计算最优性证明。KAYROS通过一个检查一致的引擎,提供两种模式:流式输出改进解的迭代局部搜索,以及在明确算术与搜索假设下可生成最优性证书的分支定价切割法。安装仅需一条命令,无专有依赖。目前公共MAMUT-routing库已收录704份由KAYROS生成的验证证书,按四次求解发布协议,促使多项先前错误结论被撤回并修正。报告贡献了两项互补基准:其一整合文献中的Blauth2024基准(基于实测Uber速度),在全部40个实例上取得新最佳解;其二提出Poryos2026基准,基于OpenStreetMap道路网络与可控合成交通构建的1080对静态与时间依赖实例。最后,报告详述了本工作的高强度人机协作过程与确保结果独立可验证的验证实践。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。