講演名 | 2011-03-10 時変タブー期間を有するタブーサーチによるTSPの解法 栗原 拓哉, 神野 健哉, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 現実社会にはスケジューリング問題や配送計画問題といった数多くの問題が存在するが,その多くは組合せ最適化問題として定式化される.そのため,組合せ最適化問題の解法の研究は重要である.しかし,大規模な問題では主に実行時間の問題により厳密に最適解を求めることは困難である.しかし,実際には厳密に最適解を必要とする場面はあまり無く,それよりも高速で実用に堪えうる解を得ることが重要である.このような目的には,精度の保証はないが精度が高く実行の高速なヒューリスティック解法が用いられる.そのヒューリスティック解法の一つにタブーサーチが存在する.本報告ではタブー期間を解の状態に関係なく時間変化するようにしたタブーサーチを組合せ最適化問題である巡回セールスマン問題に適用し,その性能に関して検討を行う. |
抄録(英) | The most of scheduling problems and vehicle routing problems are formulated as combinatorial optimization problems. Therefore, solving the combinatorial optimization problems is important. However, it is difficult to find the exact solution. For such combinatorial optimization problems, to find feasible solution in applicative time is important. The heuristic algorithms are applied to such combinatorial optimization problems. The heuristic algorithms can find a close to the exact solution. One of such heuristic algorithms is a tabu search. In this article, we propose a tabu search with time-variant tabu tenure. Also, we confirm its performance by using traveling salesman problems. |
キーワード(和) | 巡回セールスマン問題 / タブーサーチ |
キーワード(英) | traveling salesman problems / tabu search |
資料番号 | NLP2010-163 |
発行日 |
研究会情報 | |
研究会 | NLP |
---|---|
開催期間 | 2011/3/3(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | Nonlinear Problems (NLP) |
---|---|
本文の言語 | JPN |
タイトル(和) | 時変タブー期間を有するタブーサーチによるTSPの解法 |
サブタイトル(和) | |
タイトル(英) | Solving TSP by a tabu search with time-variant tabu tenure |
サブタイトル(和) | |
キーワード(1)(和/英) | 巡回セールスマン問題 / traveling salesman problems |
キーワード(2)(和/英) | タブーサーチ / tabu search |
第 1 著者 氏名(和/英) | 栗原 拓哉 / Takuya KURIHARA |
第 1 著者 所属(和/英) | 日本工業大学 Nippon Institute of Technology |
第 2 著者 氏名(和/英) | 神野 健哉 / Kenya JIN'NO |
第 2 著者 所属(和/英) | 日本工業大学 Nippon Institute of Technology |
発表年月日 | 2011-03-10 |
資料番号 | NLP2010-163 |
巻番号(vol) | vol.110 |
号番号(no) | 465 |
ページ範囲 | pp.- |
ページ数 | 6 |
発行日 |