| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2009-05-15 17:10 空間閾値モデルと近傍情報を用いた巡回セールスマン問題の解探索空間削減法 ○河村裕介・松浦隆文・池口 徹（埼玉大）  NLP2009-12 |
|
| 抄録 | （和） | 巡回セールスマン問題(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 $\mathcal{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 / / / / | |
| 文献情報 | 信学技報, vol. 109, no. 30, NLP2009-12, pp. 57-62, 2009年5月. | |
| 資料番号 | NLP2009-12 | |
| 発行日 | 2009-05-08 (NLP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | NLP2009-12 |
|
| 研究会情報 | |
| 研究会 | NLP |
| 開催期間 | 2009-05-15 - 2009-05-15 |
| 開催地（和） | 立命館大学 びわこ・くさつキャンパス |
| 開催地（英） | Ritsumeikan University |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | NLP |
| 会議コード | 2009-05-NLP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 空間閾値モデルと近傍情報を用いた巡回セールスマン問題の解探索空間削減法 |
| サブタイトル（和） | |
| タイトル（英） | 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 |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 河村 裕介 / Yusuke Kawamura / カワムラ ユウスケ |
| 第1著者 所属（和/英） | 埼玉大学 (略称： 埼玉大) Saitama University (略称： Saitama Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 松浦 隆文 / Takafumi Matsuura / マツウラ タカフミ |
| 第2著者 所属（和/英） | 埼玉大学 (略称： 埼玉大) Saitama University (略称： Saitama Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 池口 徹 / Tohru Ikeguchi / イケグチ トオル |
| 第3著者 所属（和/英） | 埼玉大学 (略称： 埼玉大) Saitama University (略称： Saitama Univ.) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2009-05-15 17:10:00 |
| 発表時間 | 25分 |
| 申込先研究会 | NLP |
| 資料番号 | NLP2009-12 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | no.30 |
| ページ範囲 | pp.57-62 |
| ページ数 | 6 |
| 発行日 | 2009-05-08 (NLP) |
[研究会発表申込システムのトップページに戻る]