巡回セールスマン問題

巡回セールスマン問題(Traveling Salesman Problem, TSP)とは,与えられた都市をすべて訪れる経路の中で,その距離が最も短くなる経路を探す問題です.
この問題の最も簡単な解き方として,都市の訪問順のすべてのパターンを列挙し,その中から最も経路の短くなる訪問順を探す方法があります.
しかし,TSPは訪れる都市の数が大きくなると解候補が爆発的に増えてしまうため,上記の方法では現実的な時間で最適な訪問順を探すことは困難です.
このため,一般的には,定めた時間内でより経路の小さい解を探索します.
 
本研究では,群知能を基にしたTSPの近似解法の開発を行っています.
群知能とは,複数の自律的な個体が相互に影響を与えながら系全体として目的を達成するシステムであり,1個体だけでは表現できない複雑な振る舞いをすることが可能です.
具体的には,提案手法は群知能の一種である粒子群最適化(Particle Swarm Optimization, PSO)をTSP向けに改良し,数値計算実験の結果から他の近似解法より高速に良い解を発見できることがわかりました.
 
init
 
done