複数経路探索問題に対するクラスタリングを用いた近似解法

カテゴリ: 部門大会

論文No: GS9-4

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

発行日: 2013/09/04

タイトル(英語): Approximate algorithm by using Clustering for Multi-route Searching Problem

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

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

キーワード: 複数経路探索|クラスタリング|近似解法|巡回セールスマン問題|Convex Hull Insertion法|Multi-route Searching Problem|Clustering|Approximate algorithm|Traveling Salesman Problem|Convex Hull Insertion method

要約(日本語): 　本研究では，クラスタリングを用いた複数経路探索問題の近似解法について提案する．複数経路探索問題とは，利用可能な車両数及び訪問すべき都市の数や位置といった情報が与えられたとき，複数ある車両の経路の総和が最短となるような各車両に割当てる都市の組み合わせと各車両の都市の訪問順序を求める問題である．提案手法は都市の振り分けと経路決定によって構成されている．都市の振り分け方法としてクラスタリングの代表的な手法であるファジィクラスタリング法を用いて，各車両に割当てる都市を決定する．また，各車両に割当てられた都市群に対してCHI法を用いて訪問順序を決定する．その結果，提案手法は従来の手法に比べて都市の収束性が高いことがわかった．また，効率的な分割を行うことで，総走行距離も短いことがわかった．

PDFファイルサイズ: 3,412 Kバイト