講演情報
[4L4-GS-1a-05]時間枠制約付き配送経路問題に対するNeural-LNSとMILPのハイブリッド最適化
〇山本 藍生1、松井 藤五郎1 (1. 中部大学)
キーワード：
制約充足問題、探索、ニューラルネットワーク
時間枠制約付き配送経路問題 (VRPTW) は，各顧客に指定された時間帯内に配送を完了する必要がある組合せ最適化問題であり，NP困難に分類される．深層学習を用いたNeural Large Neighborhood Search (Neural-LNS) は効率的な近傍探索を可能にする一方，大規模問題において局所最適解に留まる場合がある．一方，混合整数線形計画法 (MILP) は厳密解を保証するが，計算時間が問題規模に対して指数関数的に増大する．本研究では，両手法の長所を組み合わせたハイブリッド最適化手法ANMH-VRPTW (Adaptive Neural-LNS MILP Hybrid-VRPTW) を提案する．提案手法は，貪欲法による初期解生成，Neural-LNSによる広域探索，MILPによる部分問題の厳密最適化の3フェーズから構成され，これらを交互に適用することで解品質を段階的に向上させる．Solomonベンチマークを用いた実験の結果，提案手法はNeural-LNS単体に対して約21%，MILP単体に対して約30%の改善を達成し，複数のインスタンスで既知最良解に到達した．これらの結果から，学習型探索と厳密最適化を組み合わせたアプローチの有効性が確認された．