Solver-Informed Evolution of Interpretable Dispatching Rules for the Stochastic Team Orienteering Problem with Time Windows

車両の艦隊が、刻々と変化する時間との戦いの中で、点在する場所を訪れていく様子を想像してみてください。それぞれの場所には異なる報酬があります。目標は単純です。時間が尽きる前に、できるだけ多くの価値を回収することです。しかし、世界はスプレッドシートのように整然とはしていません。ある地点でのタスクを完了するのにかかる時間は不確実です。ドローンを遅らせる突然の突風や、船を減速させる荒波があるかもしれません。さらに、各場所には特定の利用可能時間枠（タイムウィンドウ）があります。到着が早すぎれば待機しなければなりません。到着が遅すぎれば、その機会は永遠に失われます。これは、「チーム・オリエンテーリング問題（Team Orienteering Problem with Time Windows）」として知られる複雑なロジスティクス上の課題の本質です。現実世界では、消防士が山火事を食い止めようとしたり、オイルスピル対策チームが海岸に到達する前に油膜を封じ込めようと急いだり、あるいは医療チームが重要な時間枠内に患者を訪問しなければならないといった場面で、このシナリオが発生します。困難なのは、現在のタスクに正確にどれくらいの時間がかかるかを知ることなく、また、毎秒全体を再計算するスーパーコンピュータの贅沢も持たずに、即座に次の動きを決定しなければならないことです。

長年、研究者たちは、コンピュータに単純な意思決定ルールを進化させることを教えることで、この問題を解決しようとしてきました。これらのルールは、交通管制官のように機能し、現在の状況を見て、次にどの顧客を訪問すべきかを即座に決定します。これまで最も成功していた手法は「NS-GP」と呼ばれるもので、距離や残り時間といった11個の固定された基本特徴量に基づいて選択を行います。効果的ではありますが、このアプローチには限界があります。それは、世界を記述するための語彙が限られており、まるでわずか100語の単語だけで小説を書こうとしているようなものです。ブラジルの大学の研究者を中心とするオーガスト・メンドンサらのチームによるこの新しい研究は、大胆な問いを投げかけました。「もし、コンピュータがオフラインの専門家プランナーが解く方法を観察することで、より豊かな語彙を学ぶことができるとしたらどうだろうか？」彼らは、高品質な解に隠された論理を抽出し、それをリアルタイムで機能するシンプルで読み取り可能なルールへと変えることができるのかを確かめたかったのです。

チームは、「SI-GP（Solver-Informed Genetic Programming：ソルバー情報に基づく遺伝的プログラミング）」と呼ばれる新しい手法を開発しました。プロセスは、コンピュータが推測することからではなく、コンピュータが「観察すること」から始まります。まず、研究者たちは強力で高速なソルバーを使用して、すべてが完璧に進むと仮定した場合の40種類の異なるテスト問題に対する最適なルートを見つけ出しました。次に、これらの完璧なルートを、現実と同じように遅延がランダムに発生するシミュレーション環境の中で再生しました。完璧な計画と実際に起こったことを比較することで、チームは、完璧な計画が行っているものの、標準的なルールが見逃していた特定の操作を特定しました。例えば、最善の計画は、残された報酬がまだ到達可能かどうかを確認するために、数ステップ先を見据えていることや、現在の決定に踏み切ることで将来の機会を失うリスクを計算していることに気づきました。

これらの観察から、研究者たちは18個の新しい意思決定特徴量のライブラリを構築しました。そのうち16個は確立されたスケジューリングの概念に基づいたものであり、残りの2個は、決定のコストと潜在的な利得を天秤にかけるために設計された全く新しい組み合わせでした。この新しい語彙により、コンピュータは問題に対してより微細なニュアンスを持って理解できるようになりました。しかし、選択肢が多いことが自動的に良い結果をもたらすわけではありません。多すぎる選択肢はシステムを混乱させることがあります。これを解決するために、チームは、各問題に対して最適な特徴量のサブセットを選択するための、第二の知能層を使用しました。彼らは、異なる特徴量の組み合わせを進化させ、厳格にテストするという、トーナメントのようなプロセスを採用しました。これは、グラフィックスカード上で動作するカスタムメイドのエンジンによって可能となり、以前の1回分のテストの時間で、数千の組み合わせをテストすることを可能にしました。

結果は驚くべきものでした。40のベンチマーク問題において、新手法が旧標準を下回ることはありませんでした。38のケースにおいて、システムは以前の最高記録を上回る新しいルールを進化させました。全テストを通じて、平均して回収された報酬は1.0％向上し、改善の余地があった問題においては1.3％向上しました。10の特定のケースでは、その向上は統計的に有意であり、その特定のシナリオにおける重大なブレイクスルーと見なせるほど大きなものでした。おそらく最も重要なことは、新しいルールがシンプルで読み取りやすいままだったことです。それらは誰も理解できないブラックボックス型のアルゴリズムではなく、人間が読み、検証できるコンパクトな数学的表現でした。多くの場合、新しいルールはより安定しており、ランダムな遅延が変動しても一貫した結果を生み出しましたが、旧来のルールは時として良好な結果と悪い結果の間で激しく変動することがありました。

この研究は、なぜ改善が起こったのかについても明らかにしました。新しいルールは、ベースラインのシステムがすべての顧客を訪問することに苦戦する「未飽和（unsaturated）」なシナリオにおいて特に効果的でした。これらのシナリオでは、新しい語彙によって、システムは複雑なトレードオフ（例えば、近くの低価値な顧客をスキップしてでも、遠方の高価値な顧客を訪問するなど）をナビゲートできるようになりました。研究者たちは、新しい特徴量がシステムの探索を「正規化（regularize）」するのを助けていることを見出しました。つまり、局所的な罠に陥る可能性を減らし、より堅牢な経路を見つける可能性を高めているのです。この手法は、専門家プランナーのルートを単に模倣するのではなく、高品質な解の構造から学ぶことで機能しました。それは、専門家プランナーの正確なルートをコピーしようとしたのではなく、それらのルートを成功させている「原理」を学び、それを新しい不確実な環境に適用したのです。

この成果は、複雑なオフライン最適化と、高速なオンライン意思決定の間の溝を埋めることが可能であることを示しています。高品質なソルバーからの洞察を用いてより優れた語彙を構築し、そして各業務に対して適切なツールを慎重に選択することで、研究者たちは強力かつ透明なシステムを作り上げました。最終的な製品は、車両やドローンに直接組み込むことができる意思決定ルールであり、中央のコンピュータに接続したり複雑なシミュレーションを実行したりすることなく、マイクロ秒単位でインテリジェントな選択を行うことができます。このアプローチは、物流における人工知能への新しい道を提示しています。それは、解釈可能性と適応性を重視し、重要な決定を下す機械が、それを利用する人間によって理解されることを保証する道です。研究者たちは、コード、データ、および発見された特定のルールを公開しており、他の人々が将来の不確実な環境における課題のために、この基盤の上に構築していくことを歓迎しています。