ピックアップ・デリバリ問題のクラスタ認識型アテンションベース深層強化学習

Abstract: PDP は Vehicle Routing Problem の基本的かつ難解な変種であり、密接に結合したピックアップ–デリバリペア、前後関係制約、しばしばクラスタリングを示す空間配置によって特徴づけられる。既存の深層強化学習（DRL）アプローチは、すべてのノードをフラットなグラフとしてモデル化し、制約を課すことを暗黙的学習に依存するか、推論時の協調探索によって強力な性能を達成するが、顕著な待ち時間が生じる。本論文では、CAADRL（Cluster-Aware Attention-based Deep Reinforcement Learning）と呼ばれる DRL フレームワークを提案する。PDPインスタンスのマルチスケール構造を、クラスタ認識エンコーディングと階層的デコーディングを用いて明示的に活用する。エンコーダは Transformer を基盤に、グローバル自己注意とデポ、ピックアップ、デリバリノードに対するクラスタ内注意を組み合わせ、グローバルに情報量が高く局所的な役割を意識した埋め込みを生成する。これらの埋め込みに基づき、各ステップでクラスタ内ルーティングとクラスタ間遷移のバランスを取る学習可能ゲートを備えた Dynamic Dual-Decoder を導入する。方策は、各インスタンスに対して複数の対称ロールアウトを用いた POMO 風の方策勾配方式でエンドツーエンドに訓練される。合成のクラスタ化および均一な PDP ベンチマークでの実験は、CAADRL がクラスタ化したインスタンスで強力な最先端のベースラインと同等またはそれを上回る性能を示すとともに、均一なインスタンスでも高い競争力を維持し、特に問題サイズの拡大に伴ってその効果が顕著になる。重要なのは、ニューラル協調探索ベースラインよりも推論時間を大幅に低減しており、クラスタ構造を明示的にモデル化することがニューラルPDPソルバーに対して効果的かつ効率的な帰納的バイアスを提供することを示唆している。