強化学習による時間依存巡回セールスマン問題

DOI

書誌事項

タイトル別名
  • Reinforcement learning for solving time-dependent traveling salesman problem

抄録

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

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1390848250119459456
  • NII論文ID
    130007856809
  • DOI
    10.11517/pjsai.jsai2020.0_2h4gs1305
  • 本文言語コード
    ja
  • データソース種別
    • JaLC
    • CiNii Articles
  • 抄録ライセンスフラグ
    使用不可

問題の指摘

ページトップへ