CHI法を用いた複数経路探索問題の一解法

カテゴリ: 全国大会

論文No: 3-023

グループ名: 【全国大会】平成24年電気学会全国大会論文集

発行日: 2012/03/05

タイトル(英語): An Algorithm by Convex hull insertion for the Multi-route searching Problem

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

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

キーワード: 複数経路探索|凸包|遠近率|巡回セールスマン問題|CHI法

要約(日本語): 本研究では，組合せ最適化問題の一つである複数経路探索問題を対象とする。複数経路探索問題とは，複数の車両によって与えられた都市すべてを通過する経路の組合せの中から最短経路を求める問題である。このような組合せ最適化問題において，最適解の導出に要する時間は都市数の増加に伴い長くなる。本研究では近似解法として，経路決定には凸包の性質を利用したCHI法を用い，車両に対する都市の割当てには，遠近率という指標を用いた解法を提案する。提案手法の有効性を検討するために，都市をランダムに配置した問題に対して，組合せ最適化問題の解法として知られている遺伝的アルゴリズと提案手法を適用し，距離と計算時間の比較を行う。

原稿種別: 日本語

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