| 講演名 | 2003/1/27 巡回セールスマン問題の近似解法の比較 村野 剛教, 松本 直樹, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 組合せ最適化問題には,多項式時間アルゴリズムを持つ問題(クラスP)と持たないと考えられている問題(クラスNP)がある.クラスNPの中でも最も困難とされるクラスの問題(NP困難)に巡回セールスマン問題がある.近年,巡回セールスマン問題の近似解の探索が盛んに行われ,様々な都市数の問題と現時点での最良解がインターネット上で公開されている.本報告では, greedy法,nearest neighbor法,saving法により初期解を構成しそれらの結果に2-opt法,3-opt法を用いて解を改善した結果を報告する.特に都市数の多い問題は2-opt法,3-opt法を行う枝の候補の組合せを,領域分割法により絞り込むことで,より少ない手数で良い近似解が得られることを,いくつかの例で示す. |
| 抄録(英) | The traveling salesman problem (TSP) is known to he a combinatorial optimization problem which belongs to NP-hard (a class of problems which does not allow polynomial time solution). Recently, various types of TSP are studied on the Web and the best solutions up to date are open to the public. The initial solution for a given TSP can be easily obtained by the well-known methods such as greedy, nearest neighbor, and saving method. In this paper, it is discussed how to improve these initial solutions of TSP with less computation time, and the domain division method for 2-opt and 3-opt methods is proposed. The proposed methods remarkably reduce the number of the candidate edges for trials. By executing appropriate domain division, we can save more than 90 percent computation time for 2-opt and 3-opt methods, and can obtain good solution which is comparative to those obtained by without doing the domain division method and with much more computation time. |
| キーワード(和) | 巡回セールスマン問題 / greedy法 / nearest neighbor法 / saving法 / 2-opt法 / 3-opt法 / 領域分割法 |
| キーワード(英) | traveling salesman problem / greedy method / nearest neighbor method / saving method / 2-opt method / 3-opt method / domain division method |
| 資料番号 | NLP2002-93 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NLP |
|---|---|
| 開催期間 | 2003/1/27(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Nonlinear Problems (NLP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 巡回セールスマン問題の近似解法の比較 |
| サブタイトル（和） | |
| タイトル（英） | Comparison of Approximate Methods for Traveling Salesman Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 巡回セールスマン問題 / traveling salesman problem |
| キーワード(2)（和/英） | greedy法 / greedy method |
| キーワード(3)（和/英） | nearest neighbor法 / nearest neighbor method |
| キーワード(4)（和/英） | saving法 / saving method |
| キーワード(5)（和/英） | 2-opt法 / 2-opt method |
| キーワード(6)（和/英） | 3-opt法 / 3-opt method |
| キーワード(7)（和/英） | 領域分割法 / domain division method |
| 第 1 著者 氏名（和/英） | 村野 剛教 / Takenori Murano |
| 第 1 著者 所属（和/英） | 明冶大学理工学部電子通信工学科 Department of Electronics and Communications, Meiji University |
| 第 2 著者 氏名（和/英） | 松本 直樹 / Naoki Matsumoto |
| 第 2 著者 所属（和/英） | 明冶大学理工学部電子通信工学科 Department of Electronics and Communications, Meiji University |
| 発表年月日 | 2003/1/27 |
| 資料番号 | NLP2002-93 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 625 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |