[2H4-GS-13] AI応用: データ解析と探索

[2H4-GS-13-05] 強化学習による時間依存巡回セールスマン問題

〇中西 研介¹、宮村 祐一¹、広瀬 俊亮¹、神津 友武¹ (1. 有限責任監査法人トーマツ)

キーワード：強化学習、組合せ最適化問題、巡回セールスマン問題、Seq2Seq

近年、高い注目を集める強化学習は、seq2seqモデルと組み合わせることによって、組合せ最適化問題に対するメタな解法としても応用が可能となる。組合せ最適化問題は、様々な制約の下で、多くの組合せの中から、ある評価指標を最も良くする解（組合せ）を求める問題であり、これまで、巡回セールスマン問題をはじめ様々な問題に対して強化学習手法の有効性が示されてきた。
本稿の目的は、強化学習手法の実社会問題における応用可能性を深耕することであり、時間依存巡回セールスマン問題（Time-Dependent Traveling Salesman Problem: TDTSP）を題材として扱う。TDTSPは、時間に応じて、地点間の移動コストが変化する巡回セールスマン問題であり、より実社会における問題に近く、ルーティング問題やスケジューリング問題などのモデル化に用いられている。
本稿では、seq2seqモデルの入力を、TDTSPを表現した形で定義し、計算機シミュレーションによる評価実験を行う。本実験の結果より、強化学習手法が、評価指標の計算が時間変化する組合せ最適化問題にも適用可能であることを確認する。