巡回順序制約付きTSPに対するGAの提案

カテゴリ: 部門大会

論文No: MC2-3

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

発行日: 2005/09/06

タイトル(英語): A Proposal of Genetic Algorithm for TSP with a Constraint on Visiting Orders

著者名: 遠山宏明 (前橋工科大学),井田憲一 (前橋工科大学),阿部直子 (前橋工科大学)

著者名(英語): Tohyama／Hiroaki (Graduate School of Engineering,Maebashi Institute of Technology),Ida／Kenichi (Graduate School of Engineering,Maebashi Institute of Technology),Abe／Naoko (Graduate School of Engineering,Maebashi Institute of Technology)

キーワード: 巡回順序制約|巡回セールスマン問題|遺伝的アルゴリズム遺伝的アルゴリズム|Constraint on Visiting Orders|Traveling Salesman Problem (TSP)|Genetic Algorithm (GA)

要約(日本語): 巡回セールスマン問題（TSP）はNP困難であることが知られている典型的な組合せ最適化問題である．そのため，TSPに関してさまざまな近似アルゴリズムが研究されている．中でも，遺伝的アルゴリズムは短時間かつ比較的高い確率で良い解を得られることから，TSPに良く適用されている．

TSPは与えられた都市をいかに効率的に巡回するかを追及する問題であるが，実際には，いくつかの制約が課されることが多い．

本論文で扱う問題は巡回順序に関する制約をもつTSP（Traveling Salesman Problem with Visiting Order, TSPVO）である．すなわち，特定の都市間に対して，巡回の順番が定められている．本論文では，このような制約をもつTSPに対し，効率的な遺伝的アルゴリズムを提案し，数値実験により，その有効性を検証した．

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