複数巡回セールスマン問題に対するクラスタリングを用いた近似解法

カテゴリ: 部門大会

論文No: GS4-1

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

発行日: 2014/09/03

タイトル(英語): Approximate algorithm by using Clustering\nfor Multiple Traveling Salesman Problem

著者名: 田 川(日本大学),星野 貴弘(日本大学),浜松 芳夫(日本大学)

著者名(英語): Tian Chuan(Nihon University),Hoshino Takahiro(Nihon University),Hamamatsu Yoshio(Nihon University)

キーワード: 複数巡回セールスマン問題|クラスタリング手法|近似解法|最適化|CHI法|Multiple Traveling Salesman Problem|Clustering|Approximate algorithm|Optimization|Convex hull insertion

要約(日本語): 組合せ最適化問題の一つである複数巡回セールスマン問題（Multiple Traveling Salesman Problem：mTSP）とは，セールスマン人数及び訪問すべき都市の数や位置といった情報が与えられたとき，複数であるセールスマンの移動距離の総和が最短となるような各セールスマンに割当てる都市の組み合わせと各セールスマンの都市の訪問順序を求める問題である。本研究では，全てのセールスマンが担当する都市数が等しいという制約条件を加えたmTSPを対象とする。提案手法はファジィクラスタリング法による都市の振り分けと構築法の１つであるConvex Hull Insertion法(CHI法)による経路構築によって構成されている。その結果，提案手法は角度による都市の割り当てと経路構築にCHI法を用いた比較対象に比べて都市の収束性が高いことがわかった。また，効率的な分割を行うことで，総走行距離も短いことがわかった。

PDFファイルサイズ: 362 Kバイト