情報処理学会 第75回全国大会講演要旨

巡回セールスマン問題(Traveling Salesman Problem : TSP)は、セールスマンが複数の都市を一度ずつ訪問し出発点に戻る最短経路を求める問題である。この問題は規模(都市数)が大きくなるにつれ探索経路が指数関数的に増大し、厳密解を求めることが困難になることで知られている。TSPの解法の1つに2-opt法がある。この方法は局所探索アルゴリズムであるためしばしば局所解に陥る。そこで、大域的探索に優れた粒子群最適化(Particle Swarm Optimization : PSO)のアルゴリズムを組み合わせることで、最適解に近づけることを試みた。2-opt法にTSP向けに改良したPSOを組み合わせることにより、2-opt法のみで得られる解より短い経路を探索できることを確認した。