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

あなたは、活気ある都市における配送トラックの配車担当者だと想像してください。あなたの目標はシンプルです。荷物を顧客に届け、ドライバーをできるだけ早く帰宅させて、賃金を節約することです。しかし、一つ問題があります。街は生きているのです。午前8時の一本道が、午前9時にはラッシュアワーのせいで10分から40分かかるようになるかもしれません。これが「時間依存型車両ルート最適化問題（Time-Dependent Vehicle Routing）」の世界です。これは、限られたリソースと複雑なルールの中でいかに最善の意思決定を行うかという科学である、オペレーションズ・リサーチ（経営科学）における古典的なパズルです。

何十年もの間、コンピュータはこのパズルを解くのが得意でしたが、通常は大きな簡略化を行ってきました。つまり、道路が変化しない地図のように、交通状況は静的であると仮定するのです。しかし、現実の世界は、静止した池ではなく、流れる川です。このパズルを完璧に解くには、トラックがいつデポ（配送拠点）を出発するかを正確に知る必要があります。なぜなら、出発を5分遅らせるだけで、渋滞に巻き込まれて移動時間が1時間増えてしまうこともあれば、信号待ちを回避できて10分節約できることもあるからです。すべてのトラックの「完璧な」出発時刻を、顧客の指定時間枠や交通パターンを遵守しながら計算するのは、非常に困難な課題です。それは、側面を回すたびに色が変化するルービックキューブを解くようなものです。

ここで、KAYROSと呼ばれる新しいツールが登場します。KAYROSを、単に推測するだけでなく、絶対的な最善のスケジュールを計算する、非常に賢く疲れを知らない「交通の魔法使い」だと考えてください。しかし、ここには手品のような仕組みがあります。それは、1時間待ってから「そこそこの答え」を出すのではなく、考え始めた最初の瞬間から、どんどん優れた答えを出し始めるということです。もし途中で停止しても、それまでに発見した中で最高の解を提示してくれます。さらに素晴らしいことに、その解が単なるラッキーな推測ではなく、数学的に完璧であることを証明することもできます。また、この論文では、これらの「魔法使い」が本当に仕事ができるかどうかをテストするために、実際の都市の地図から構築された、大規模で新しい練習用パズル集であるPoryos2026を紹介しています。

KAYROSの魔法：眠らないソルバー

この論文は、「時間依存型車両ルート最適化問題」を解くために設計されたオープンソースのソフトウェアツール、KAYROSを紹介しています。配送ドライバーの艦隊のためにロードトリップを計画しているところを想像してください。立ち寄る場所のリストがあり、各地点には顧客が家にいる特定の時間枠（例：「午後2時から午後4時の間に荷物を届けてください」）があります。厄介なのは、地点間の移動にかかる時間が、出発する時刻によって変化するという点です。

KAYROSが特別な理由は、コンピュータ・ソルバーの世界では珍しい「二つのことを同時に行う」点にあります。

1. 「エニタイム（Anytime）」であること： KAYROSを実行しても、何時間も黙って待ち続けることはありません。すぐに解を出し始めます。最初のものは普通かもしれませんが、次はより良く、その次はさらに良くなります。これは、シェフがスープを味見しながら絶えずスパイスを加えるようなものです。調理をいつでも中断でき、中断した時点での時間に対して、可能な限り最高のスープを手に入れることができます。
2. 「厳密（Exact）」であること： 十分に長く実行させれば、単に答えを推測するのではなく、それが「最善の答えである」と証明します。それは「証明書（certificate）」を生成します。これは、他のどのルートもこれより速くなることはあり得ないと、誰でも検証できる数学的な領収書のようなものです。

著者らは、このツールを完全に無料かつオープンなものとして構築しました。コマンド一つで自分のコンピュータにインストールでき、大企業の高価で秘密めいたソフトウェアを必要としません。これは、移動時間を単一の数値としてではなく、時間の経過とともに上下する「関数（ライン）」として扱う巧妙なエンジンを使用しています。これにより、特定の分に道路が突然渋滞するといった、複雑で現実的な交通パターンを扱うことができます。

「自己反駁」の物語：どのように自分たちの間違いを見つけたか

この論文の最も興味深い部分の一つは、誠実さに関する物語です。著者らは、自分たちの「完璧な」証明書が本当に完璧であることを確認したいと考えました。そこで、4つの異なるコンピュータ実行がすべて全く同じ答えに同意しなければならないという厳格なルールを設定しました。

テスト中に、ある問題が見つかりました。KAYROSは、特定のルートが最高であると主張する160個の「証明書」を発行していました。しかしその後、彼ら自身の「エニタイム」ソルバー（改善を続けるもの）が、それらの「完璧な」証明書よりも実際に速いルートを見つけ出したのです！これは衝撃でした。原因は、KAYROSが交通データの急激な変化（道路が瞬時に駐車場状態になるような現象）を処理するために、「スムージング（平滑化）」のテクニックを使用していたことにありました。このテクニックにわずかな誤りがあり、コンピュータが時間を誤計算していたのです。

著者らはこの事実を隠しませんでした。彼らは160個の証明書をすべて公に撤回し、これらの「ジャンプ」を正確に処理するようにコードを修正し、テストを再実行しました。この物語がここに含まれているのは、彼らのシステムが堅牢であることを示すためです。たとえAIが間違いを犯しても、検証ルールがそれを捉え、真実が勝つのです。

新しい遊び場：Poryos2026

KAYROSが本当に機能するかをテストするために、著者らは現実の世界のような「遊び場」を必要としました。彼らは、1,080個の新しいテスト・パズル群であるPoryos2026を作成しました。架空の作られたマップを使う代わりに、OpenStreetMap（無料のコミュニティ構築型マップ）を使用して、リヨン、パリ、サンフランシスコ、香港、東京の5つの主要都市から実際の道路ネットワークを取り出しました。

次に、これらの実際の地図に、合成的（架空だが現実的）な交通量、顧客需要、および時間枠を追加しました。これにより、実際の地理と制御された交通シナリオを組み合わせた、大規模な挑戦状が作成されました。これら1,080個のパズルのそれぞれについて、彼らは独自のソルバーを使用して「既知の最善解」を生成しました。これにより、他の研究者が、抽象的な数学問題ではなく、実際の都市走行を反映した標準に対して、自身のツールを公平かつ現実的にテストできる環境を提供しています。

人間とAIのチームアップ

この論文の最もユニークな部分は、その書き方にあるかもしれません。著者の博士課程の学生は、AIエージェント（大規模言語モデル）と約2週間にわたる集中的なコラボレーションを行いました。人間が目標を設定し、大きな決定を下し、作業をチェックし、一方でAIはコードの記述、数千回のコンピュータ実験の実行、エラーのデバッグといった重労働を担当しました。

著者は、この2週間のコラボレーションが、一人で行えば2年以上かかったであろう作業を行ったと見積もっています。しかし、論文はこれが単に「タイピングを速くした」のではないことを強調しています。人間は、適切なコンテキスト（文脈）をAIに準備させ、その仕事をチェックし、結果が科学的に妥当であることを確認するために、多くの時間を費やす必要がありました。論文は、このようなパートナーシップこそが研究の未来であるが、それはAIが事実を捏造したり、結果を幻覚（ハルシネーション）したりしないことを検証するための厳格なルール（「証明書」システムのようなもの）がある場合に限られる、と論じています。

これが未来に意味すること

この論文は、KAYROSが世界最速のソルバーであると主張しているわけではありません（まだ他のツールとの直接的な比較は行っていません）。また、あらゆる可能なルーティング問題を解決したとも主張していません。その代わりに、複雑で時間依存的な交通問題に対して、「厳密」かつ「エニタイム」な解決を実現する、検証済みで信頼できる無料のツールを提供しています。

強力な新しいソルバー、大規模で新しい実世界のテストケース、そして人間とAIがいかに責任を持って協力できるかという透明性のある物語を組み合わせることで、著者らは物流の新しい基盤を提供しました。ピザの配達であれ、ゴミ収集車の管理であれ、あるいは緊急対応ルートの計画であれ、いつでも良い答えを得られると分かった上で、出発する「完璧な」時間を計算できる能力は、私たちの忙しい世界を動かす科学における重要な前進なのです。