| 講演名 | 2009-05-15 空間閾値モデルと近傍情報を用いた巡回セールスマン問題の解探索空間削減法 河村 裕介, 松浦 隆文, 池口 徹, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 巡回セールスマン問題(TSP)は,NP困難なクラスに属する代表的な組合せ最適化問題である.TSPの最適解には,近くの都市に接続する辺が多く含まれるため,物理的距離が近い2都市間に張られる辺のみを残すことで,近似解法を適用する際の解探索空間を削減する手法が用いられる.一方,現実の地理的空間上のネットワークの複雑さを解析するために,様々な複雑ネットワークモデルが提案されている.これらのモデルを用いて構築されるネットワークは,TSPの最適解を構成する辺の特徴と類似している.そこで本報では,これらの複雑ネットワークモデルの1つである空間閾値モデルに近傍情報を導入することでTSPの解探索空間を削減する手法を提案する.その結果,提案手法を用いた場合,従来法と比べてより少ない辺で最適解を構成する辺を網羅できることがわかった. |
| 抄録(英) | Traveling Salesman Problem (TSP) is one of the most typical combinatorial optimization problems which belong to a class of NP-hard. Each edge in an optimal tour tends to connect two cities locally. Thus, to reduce the solution-space of the TSP, the nearest neighbor method is used for constructing a short tour. On the other hand, to analyze the characteristics of real networks, many geographical complex network models are proposed recently. These networks have similar properties with optimal tours of the TSP: long-range edges are restricted and intersection of edges occurs rarely. In this report, we proposed a reduction method for the solution-space of the TSP using geographical threshold graph with near neighbor information. As a result, the proposed method can include all edges in the optimal tour with less edges than the conventional methods. |
| キーワード(和) | 巡回セールスマン問題 / 解探索空間 / 複雑ネットワーク / 空間閾値モデル |
| キーワード(英) | Traveling Salesman Problem (TSP) / Solution-Space / Complex Network / Geographical Threshold Graph |
| 資料番号 | NLP2009-12 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NLP |
|---|---|
| 開催期間 | 2009/5/8(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Nonlinear Problems (NLP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 空間閾値モデルと近傍情報を用いた巡回セールスマン問題の解探索空間削減法 |
| サブタイトル（和） | |
| タイトル（英） | A Solution-Space Reduction Method for Traveling Salesman Problem Using Geographical Threshold Graph with Neighbor Information |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 巡回セールスマン問題 / Traveling Salesman Problem (TSP) |
| キーワード(2)（和/英） | 解探索空間 / Solution-Space |
| キーワード(3)（和/英） | 複雑ネットワーク / Complex Network |
| キーワード(4)（和/英） | 空間閾値モデル / Geographical Threshold Graph |
| 第 1 著者 氏名（和/英） | 河村 裕介 / Yusuke KAWAMURA |
| 第 1 著者 所属（和/英） | 埼玉大学大学院理工学研究科数理電子情報系専攻 Graduate School of Science and Engineering, Saitama University |
| 第 2 著者 氏名（和/英） | 松浦 隆文 / Takafumi MATSUURA |
| 第 2 著者 所属（和/英） | 埼玉大学大学院理工学研究科理工学専攻 Graduate School of Science and Engineering, Saitama University |
| 第 3 著者 氏名（和/英） | 池口 徹 / Tohru IKEGUCHI |
| 第 3 著者 所属（和/英） | 埼玉大学大学院理工学研究科研究部数理電子情報部門 Graduate School of Science and Engineering, Saitama University |
| 発表年月日 | 2009-05-15 |
| 資料番号 | NLP2009-12 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | 30 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |