A Speculative Verification and Expert Repair Framework for Dynamic Vehicle Routing

ラストワンマイル配送システムは、決して静止することのない世界の中で稼働しています。トラックがすでに走行している最中に注文が入ることもあれば、交通状況が変化したり、配送時間枠（タイムウィンドウ）が非常に厳しかったりすることも珍しくありません。このような環境では、一日の始まりに一度だけ計算された「静的な計画」では到底足りません。ディスパッチャー（配車担当者）は常に計画を更新し、既存のルートに新しい立ち寄り先を挿入したり、キャンセルや車両故障が発生した際にルートを組み替えたりする必要があります。この絶え間ない再最適化の必要性は、困難な計算上の課題を生み出します。すなわち、システムは数秒以内に、新たな有効な停止地点の配置を見つけ出さなければならないのです。もしコンピュータが考えるのに時間をかけすぎてしまえば、配送時間の期限が過ぎてしまうか、ドライバーが何もできず待機することになります。また、もしコンピュータがルールを逸脱したルート（例えば、積載重量オーバーや到着遅延など）を提示してしまった場合、計画全体が崩壊し、最初からやり直しにならざるを得ません。目標は単に最短経路を見つけることではなく、「実行可能な経路」を即座に見つけることです。

湖北交通学院の研究者たちは、これらの瞬時の判断をより信頼性の高いものにするために、人工知能の世界の戦略を借りた新しいアプローチを開発しました。彼らはそのシステムを「SRI-ECR-balanced」と呼んでいます。新しく注文が入るたびにゼロから完璧なルートを計算しようとするのではなく、このシステムは、優れた文章を下書きし、誤りをチェックし、良い部分を残し、悪い部分をすぐに修正する熟練のエディターのように機能します。「投機的実行（speculative execution）」として知られるこの手法により、システムは複数の将来の立ち寄り先を同時に提案し、それらが安全であることを検証した上で、問題を引き起こす前に残りの要素を破棄することができます。これにより、従来の方式よりもはるかに速くコンフリクト（衝突・矛盾）から回復することができ、状況が急速に変化する場合でも、配送計画の実現可能性を維持できます。

この新しいフレームワークの中核となるのは、「ドラフト作成」「検証」「修復」というサイクルです。新しい注文が入ると、「ドラフト生成器」がトラックのルートに追加すべき顧客の短いシーケンスを提案します。かつてのシステムでは、顧客を一人ずつ追加しようとして速度が落ちるか、あるいは長いリストを一気に投入してミスを招くことがよくありました。この新システムはそのバランスを取っています。例えば一度に5件程度の小さなグループを提案するのです。次に、独立した「検証器」が、トラックの重量制限や顧客の時間枠といった道路のルールに対して、そのグループを照合します。システムは、ルールの範囲内に収まる提案グループのうち最も長い区間を受け入れ、残りは直ちに破棄します。もし提案されたグループの最初の3軒目は問題なくても、4軒目が重すぎた場合、システムは最初の3軒を保持し、4軒目をロールバック（差し戻し）します。プラン全体を捨て去るのではなく、ルールに抵触した部分のみを取り除くのです。

無効となった立ち寄り先のロールバックが終わると、専門の「修理エキスパート」が登場して問題を解決します。これは汎用的な修正プログラムではありません。システムは具体的に何が悪かったのかを診断します。もし原因がトラックの容量不足であれば、エキスパートは空きスペースのある別のトラックを探すことを優先します。もし時間がタイトで顧客への訪問が間に合わないことが原因であれば、エキスパートはもっと早く到着できるルートを探します。このターゲットを絞ったアプローチこそが極めて重要です。研究者によれば、この特定のコンフリクトを意識した修復ステップがない場合、ストレスの高い状況下でシステムは有効なルートを見つけられなくなることが分かりました。システムがエキスパートによるものではなくランダムな修復方法を使用せざるを得なかったとき、発生した問題の約3分の1程度しか修正できず、多くの注文が未対応となってしまいました。しかし、エキパート・ルーターを用いることで、テストにおいてすべてのコンフリクトを正常に修復することに成功し、実現可能な計画におけるパーフェクトな記録を維持しました。

このプロセスをリアルタイムで使用できるほど高速化するために、システムは「ルート・プレフィックス・キャッシュ」と呼ばれるメモリ形式も使用しています。動的な環境においては、トラックのルートの大部分は次の瞬間まで変わりませんが、末尾の部分だけが変わります。従来のシステムは、わずかな変更が行われるたびに旅路全体を再計算するため、変化していない部分に対しても時間を浪費していました。この新システムは、すでに確定しているルート部分の計算結果を記憶しておく仕組みを持っています。新しい立ち寄り先を確認する必要がある際、既にあるデータの部分はそのまま再利用し、新しい部分のみを計算します。この単純な工夫によって、潜在的なルートの評価速度が3倍以上に向上しました。標準的な100人の顧客を用いたテストでは、このキャッシングにより、ゼロから開始した場合と比較して3.12倍速くルートを評価できました。さらに大規模な200人の顧客を用いたテストでも、3.08倍のスピードアップを実現しました。

研究者たちは、物流企業で使用されているOR-ToolsやPyVRPといった強力なソルバーを含む既存のツールと自らのシステムを比較検討しました。これらは絶対的な最短ルートを見出すように設計された強力なツールです。彼らは、新しい注文が絶えず入り込み、時間枠が人為的に厳しく設定されるようなシミュレーションを行い、負荷を与えました。こうした困難な条件下では、伝統的なソルバーは一つの決定を行うために許容されたほぼ全時間の3秒間を使い切り、それでもなお、（距離的には）わずかに短いものの計算には時間がかかるルートを作成してしまうことがありました。対照的に、本システムは平均して0.5秒未満で有効な解を見つけ出しました。同システムが生成するルートは、強力なソルバーが見つけた総移動距離よりも約7.8%長くなりましたが、このトレードオフは意図的なものです。現実世界の配送シナリオにおいては、完全に完璧だが到着するのが遅すぎるルートよりも、少し長くても即座に準備ができるルートの方が価値が高いことが多いからです。システムは、最後の1マイルの効率性を絞り出すことよりも、実行可能なプランを迅速に出力することを優先しました。

また、研究では異なるリスクレベルの下でのシステムの挙動についても調査されました。新しい立ち寄り先を追加するリスクを慎重に天秤にかける「バランス型」のアプローチと、確認を行う前にできるだけ多くの立ち寄り先を追加しようとする「積極型」のアプローチを比較しました。積極型のメソッドでは、多くの方策がエラーとなり、それがロールバックされるため大幅に減速してしまいました。一方、リスクの高い動きを提案する前に対処するバランス型のメソッドは、ミスの数を減少させ、スムーズな進行を維持しました。これにより、注意深く予測を進めつつ、事前に厳格にチェックすることでシステムが最も効果的に機能することが裏付けられました。

研究者たちは、時間が要因とならない静的な世界において、最短ルートを見つける能力については、自分たちのシステムが最高であるとは主張していません。むしろ、距離の最小化のみを目的とし、コンピュータが数秒間の思考時間を確保できるような問題においては、依然として従来のソルバーが優位であると明言しています。この新しいフレームワークの真価は、まさにダイナミックな配車業務のような、混沌とした時間制約のある世界の中にあります。そのような場面では、コンフリクトから瞬時に回復し、妥当な計画を維持する能力が、距離の僅かな改善よりも重要なのです。実験の結果、最も過酷なテストシナリオにおいても、拒否された注文なしで100%の顧客に対応し続け、レスポンスタイムを低く抑えることで、ライブ配車センターでの実用性を示しました。

たとえ予期せぬ交通渋滞を模倣するためのランダムなノイズが導入されても、システムは耐え抜きました。全ての顧客に対応し、コンフリクトを正常に修復し続け、その手法が現実世界の不確実性を扱うのに十分な堅牢性を備えていることを示しました。また、実際のドロップオフ座標を使用した大手物流会社の実際の実データを用いてテストを行いました。システムはこの実データ上でも正常に動作し、テストセット内の80箇所のストップすべてに対応しました。ただし、研究者は現在の設計の限界にも注意深く言及しています。400人の顧客を含むより大規模なシナリオでテストを行ったところ、時間制限内に完全な解を見つけることはできず、注文のおよそ4分の3しか処理できませんでした。これは、中規模の艦隊には適していますが、より大規模な運用には、問題を小さく分割するためのさらなる戦略が必要であることを示唆しています。

結局のところ、この研究はルーティング問題に対する考え方の転換を提示しています。コンピュータを「唯一の正解を見つけ出すための計算機」として捉えるのではなく、「素早い回答を見つけ出す意思決定者」として扱っているのです。現代の人工知能で用いられている投機的なパターン――ドラフト作成、検証、そしてキャッシング――を採用することで、システムは動的な配送に伴う不確実性を乗り越えていくことができます。今回の発見は、現実世界のロジスティクスにおける多くの課題にとって、数学的に完璧であることよりも、即座に適応できる能力こそが、成功するシステムの真の尺度であることを示唆しています。このシステムは、あらゆる遅延を排除したり毎回必ず最短経路を見つけたりすることを約束するものではありません。しかし、新しい注文が入ったときに、実行可能なプランがすぐさま用意され、配送ネットワークの歯車を回し続けることを約束してくれるのです。