Deep Reinforcement Learning solution for pickup and delivery routing problems with time window and capacity constraints
本論文は、修正されたJAMPRモデルに基づき、容量および時間枠制約を持つ中規模の集荷・配送問題（CPDPTW）をリアルタイムで効果的に解決し、かつ200ノードを超える大規模なインスタンスに対して高速な準最適解を提供する、新しい深層強化学習手法を提示するものである。
原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。 免責事項の全文を読む
あなたは、活気にあふれ、絶えず成長し続ける都市で、配送トラックの艦隊を率いるキャプテンであると想像してください。あなたの仕事は、何百人もの顧客に荷物を届け、返品を受け取ることですが、そこには厳格なルールがあります。トラックに積める荷物の量には限りがあり、さらに、各顧客には荷物を受け取れる特定の時間帯が決まっているのです。もし到着が早すぎたり遅すぎたりすれば、あるいは、バンの後ろに箱を詰め込みすぎれば、計画は失敗します。これが「ピックアップ・アンド・デリバリー問題（集荷・配送問題）」であり、顧客が増えるほど難易度が上がる巨大なパズルです。
何十年もの間、コンピュータはこの問題を解決するために、超高速の計算機として振る舞い、何百万もの可能なルートを一つずつテストしてきました。しかし、都市が成長し、停車数の数が爆発的に増えるにつれ、これらの計算機は行き詰まってしまいます。彼らは、人間が数分でスケッチできるようなルートを見つけるのに何時間も費やしたり、最悪の場合、「解けません」と言って完全に諦めてしまったりするのです。ここで、新しい種類の「コンピュータの脳」が登場します。それが「深層強化学習」です。これは、計算機というよりも、ゲームをプレイすることによって学習するビデオゲームのキャラクターのようなものです。あらゆる可能性を計算する代わりに、このAIは配送ゲームを何千回もプレイし、一回ごとにどんどん速く、賢くなっていきます。すべての選択肢を確認する必要なく、最善の手を見つけ出す方法を学ぶのです。
この論文において、モスクワ国立大学およびロシア科学アカデミー宇宙研究所のアンドリュー・ソロカ氏とそのチームは、この「ビデオゲームの脳」に対し、トラックの積載容量制限や厳格な時間枠といった、現実世界の複雑なルールを扱う方法を教えることに決めました。彼らは、JAMPRと呼ばれる既存のスマートなモデルを取り上げ、トラックがどこかで荷物を集め、別の場所でそれを届けるという「ピックアップ・アンド・デリバリー」のルールを理解できるように、特別なアップグレードを施しました。これにより、容量制限を管理しながら、荷物の集荷と配送を同時にこなせるようにしたのです。
研究者たちは、彼らがアップグレードしたモデルが、中小規模の都市（停車数50〜200）において、スピードの怪物であることを発見しました。これらのシナリオでは、AIは最初の数秒間でほぼ完璧なルートを吐き出し、計算を開始するまでに長い時間を要する従来の「計算機」的な手法を打ち負かします。それはまるで、従来のコンピュータがまだ地図を読もうとしている間に、街の構造を熟知している配送ドライバーが、即座に最適なルートを叫ぶようなものです。
しかし、街が巨大になると（停車数400〜1,000）、物語は少し複雑になります。巨大な都市においては、AIは依然としてスピードのレースで勝利し、ほぼ瞬時に「十分に良い」解決策を提示しますが、従来の方式は最初の1分間、有効なルートすら見つけるのに苦戦します。とはいえ、AIはまだ完璧ではありません。これらの巨大な都市に対して絶対的な最善のルートを得るためには、AIは数日間「訓練」を行う必要があり、これは長い時間を要します。訓練後であっても、最大規模の問題に対して、AIが導き出す最終的なルートは、無限の時間が与えられた場合に従来の方式が見つけ出すであろう最高の結果と比較して、距離の面で約20%高くなってしまいます。実際、最適化の時間がわずか数分経過すると、従来の方式がAIを追い抜き、AIが（より大幅な訓練なしには）到達できないレベルのより優れたルートを見つけ出します。
チームはまた、ルールが変わったときにこのAIがどれほどタフであるかもテストしました。彼らは、AIが使用された特定のテスト条件下においては非常に信頼性が高いことを発見しました。つまり、同じ問題の分布に対して従来のコンピュータが「不可能」と諦めてしまった場合でも、AIは決して失敗することなく、何らかの解を提供したのです。しかし、もし街のレイアウトが劇的に変化した場合（例えば、家々がランダムに広がっている状態から、全員が狭い円の中に住んでいるパターンへ変わる場合など）、AIのパフォーマンスは少し低下しますが、それでも最初の1時間は従来の方式を上回り続けます。
要するに、この論文は、深層学習のアプローチがリアルタイムのロジスティクスにおける強力な新しいツールであることを示唆しています。これは、最も大きく複雑なパズルにおいて絶対的な正解が必要な場合に、従来の方式を完全に置き換えるものではありません。しかし、交通状況への対応や注文の急増への対応など、今すぐ迅速で信頼できる答えが必要な状況においては、このAIはゲームチェンジャーとなります。従来のツールが停滞したり失敗したりする場面で、堅牢かつ迅速な解決策を提供してくれるのです。
自分の分野の論文に埋もれていませんか？
研究キーワードに一致する最新の論文のダイジェストを毎日受け取りましょう——技術要約付き、あなたの言語で。