巡回セールスマン問題におけるしきい値を用いた一構築法

カテゴリ: 部門大会

論文No: GS5-2

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

発行日: 2011/09/07

タイトル(英語): A Construction Method with Using a Threshold in TSP

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

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

キーワード: 巡回セールスマン問題|Convex Hull Insertion 法|しきい値しきい値|Traveling Salesman Problem|Convex Hull Insertion|Threshold

要約(日本語): 本研究では，Traveling Salesman Problem(TSP)における巡回路の構築手法の一つであるConvex Hull Insertion(CHI)法を基にした解法の提案を行う。CHI法および提案手法は，部分巡回路に対して，部分巡回路内部の都市を何らかの方法で追加していくことにより巡回路を構築する。提案する手法では，追加する都市と部分巡回路上の都市とのなす角にしきい値を設け，これにより追加方法を変更する。CHI法と提案手法の求解精度を比較し，提案した手法の有用性を検討する。

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