[2S5-GS-2] 機械学習：

[2S5-GS-2-01] ノード分布を考慮した階層強化学習に基づく大規模巡回セールスマン問題の一解法

〇諏訪 晴哉¹、更家 崚介¹、山極 綾子¹、後藤 正幸¹ (1. 早稲田大学)

キーワード：大規模巡回セールスマン問題、階層型強化学習、リアルタイム経路探索、クラスタ性、k-NNグラフ

巡回セールスマン問題（TSP）は，与えられた都市を一度ずつ巡る最短経路を求める組合せ最適化問題である．TSPはNP困難な問題であり，問題の大規模化に伴い，現実的な時間内で最適解を求めることが難しくなる．このため近似解を探索するヒューリスティック手法が提案されているが，大規模問題では計算時間が増大するという課題は依然として残されており，特に経路探索にリアルタイム性が求められる状況で深刻である．そこで，近年，機械学習を用いた大規模TSPの高速な近似解法の研究が盛んに行われており，中でも深層強化学習を用いた手法が注目を集めている．その一つであるH-TSPは，大規模TSPを複数のサブ問題に分割することで，計算速度と精度の両立を実現したモデルである．しかし，H-TSPはノードが一様分布に従うことを前提としているため，配送拠点や店舗配置のようにクラスタ性を持つ現実の問題に対し改善の余地がある．そこで本研究では，H-TSPに対しk-NNグラフの改良及び初期解の導入を行い，クラスタ性を持つ大規模TSPに有効な深層強化学習手法を提案する．最後に，H-TSPとの比較実験を通じて，提案手法の有効性を示す．