方向角を考慮した複数経路探索問題の一解法

カテゴリ: 全国大会

論文No: 3-051

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

発行日: 2013/03/05

タイトル(英語): An Algorithm for the Multi-route Searching Problem Consideration of Vectorial Angle

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

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

キーワード: 複数経路探索|巡回セールスマン問題|CHI法|方向角

要約(日本語): 本研究では複数経路探索問題を対象とする。複数経路探索問題とは，利用可能な車両数及び訪問すべき都市の数とその位置情報が与えられたとき，複数の車両の経路の総和が最短となるような各車両の経路を求める問題である。このような組合せ最適化問題において，最適解の導出に要する時間は都市数の増加に伴い長くなる。本研究では近似解法として，車両に対する都市の割当てには，出発地点または目的地点に対する角度を用いる。また，経路決定には凸包の性質を利用したCHI法を用いる。提案手法の有効性を検討するために，都市をランダムに配置した問題に対して，遺伝的アルゴリズと提案手法を適用し，解の精度および計算時間の比較を行う。

原稿種別: 日本語

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