[3J4-J-1] 基礎・理論: 探索問題とその応用

[3J4-J-1-02] クラスタリング手法を用いたTSPの解法

〇内田 純平¹、穴田 一¹ (1. 東京都市大学)

キーワード：巡回セールスマン問題、クラスタリング

工業や経済の問題の多くは, 最も効率が良い組み合わせを求める組み合わせ最適化問題に帰着することができる. その中に, 与えられた全ての都市を巡る最短経路を求める巡回セールスマン問題(Traveling Salesman Problem, TSP)がある.

本研究では, TSPに適した新しいクラスタリングのアルゴリズムであるClustering in clusters(以下CIC)を提案し, CICによって構成したクラスタに対してNN法と2-opt法, Or-opt法を用いることにより, 経路生成を行うアルゴリズムを構築した. そして, TSPLIBに掲載されているベンチマーク問題を用いて提案手法の評価実験を行い, その有効性を確認した.