凸包を用いたクラスタリングによるTSPの解法

カテゴリ: 部門大会

論文No: OS3-6

グループ名: 【C】平成17年電気学会電子・情報・システム部門大会講演論文集

発行日: 2005/09/06

タイトル(英語): A Clustering Method Based on Convex Hull for the Traveling Salesman Problems

著者名: 川島 明彦(千葉大学),荒井 幸代(千葉大学),須貝 康雄(千葉大学)

著者名(英語): Akihiko Kawashima(Chiba University),Sachiyo Arai(Chiba University),Yasuo Sugai(Chiba University)

キーワード: 巡回セールスマン問題|凸包|クラスタリングクラスタリング|traveling salesman problems|convex hull|clustering

要約(日本語): 本研究では最適解の特徴に関係する凸包を用いたクラスタリング手法によるTSPの解法を提案する。TSPでは凸包上の都市が(反)時計回りの順番で最適解中にあらわれるため、凸包上の都市を訪れる順序を求める必要はない。そこで凸包上の都市以外の都市について、凸包上のどの隣接する都市間の道に含まれるかをクラスタリングにより決定する。得られた各クラスタは都市の集合であり、各クラスタの都市の分布に対しても同じように凸包が存在するため、このクラスタリング操作の繰り返しにより巡回路を求めることができる。クラスタリングに用いる関数が提案手法の重要な点であり、どのような関数を用いればよいかをTSPのベンチマーク問題で既に求められている最適解との比較により検討する。

PDFファイルサイズ: 1,419 Kバイト