2019年度 人工知能学会全国大会(第33回)

講演情報

一般セッション

一般セッション » [GS] J-1基礎・理論

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

2019年6月6日(木) 15:50 〜 17:10 J会場 (201B 中会議室)

座長:瀧川 一学(理化学研究所) 評者:佐々木 耀一(日本電気株式会社)

16:10 〜 16:30

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

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

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

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

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