| 講演名 | 2015-05-22 多目的ネットワークにおける最適経路の探索法 高橋 奈津美(首都大東京), 山本 久志(首都大東京), 秋葉 知昭(千葉工大), 肖 霄(首都大東京), 新行内 康慈(十文字学園女子大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 最適な通信ルーティング探索システムや生産・物流管理計画システムなど，現代社会において，ネットワークシステムは幅広く存在している．これらのネットワークは，複数の評価尺度を持つ多目的ネットワークと して定式化される．本研究は，このような多目的ネットワークにおいて最適経路の探索法を考察する．多目的ネットワークの最適経路探索問題の有効な解法としては拡張ダイクストラ法がある．しかし拡張ダイクストラ法におい ても，評価尺度が複数の場合は，経路探索過程で多くの記憶領域を要し計算負荷が膨大となる問題があった．本研 究では，最適経路が満たす探索空間の制限に有効な性質を用いて経路の探索空間を制限し，拡張ダイクストラ法より狭い空間で経路探索を行うアルゴリズムを提案する．そして，数値実験により提案アルゴリズムの効率性を評価する． |
| 抄録(英) | Many networks have been applied extensively in the real world, for example, scheduling of a production and distribution management system and search system for optimal routes in the Internet services etc.. These networks are formulated as a multi-objective network which has multi-criteria. In this paper, we obtain optimal paths for such a multi-objective network. Extended Dijkstra’s algorithm is effective in obtaining optimal path of multi-objective network. Even if we use this algorithm, it takes large memory area to obtain optimal paths of large networks which have multi-criteria. We consider effective properties in reducing search space, and propose a new algorithm which has less search space than extended Dijkstra’s algorithm. By numerical experiments, we show our proposed algorithm to be more efficient than the extended Dijkstra’s algorithm. |
| キーワード(和) | 多目的ネットワーク / 拡張ダイクストラ法 / 最適経路問題 / パレート解 |
| キーワード(英) | Multi-objective Network / Extended Dijkstra’s Algorithm / Optimal Path Problem / Pareto Solutions |
| 資料番号 | R2015-5 |
| 発行日 | 2015-05-15 (R) |
| 研究会情報 | |
| 研究会 | R |
|---|---|
| 開催期間 | 2015/5/22(から1日開催) |
| 開催地（和） | 隠岐島文化会館 |
| 開催地（英） | Okinoshima-Bunka-Kaikan |
| テーマ（和） | ソフトウェアの信頼性，信頼性一般 |
| テーマ（英） | |
| 委員長氏名（和） | 木村 光宏(法政大) |
| 委員長氏名（英） | Mitsuhiro Kimura(Hosei Univ.) |
| 副委員長氏名（和） | 馬渡 宏泰(NTT) |
| 副委員長氏名（英） | Hiroyasu Mawatari(NTT) |
| 幹事氏名（和） | 安里 彰(富士通) / 岡村 寛之(広島大) |
| 幹事氏名（英） | Akira Asato(Fujitsu) / Hiroyuki Okamura(Hiroshima Univ.) |
| 幹事補佐氏名（和） | マラット ザニケエフ(九工大) / 田村 信幸(法政大) |
| 幹事補佐氏名（英） | Maratt Zanikef(Kyushu Inst. of Tech.) / Nobuyuki Tamura(Hosei Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Reliability |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 多目的ネットワークにおける最適経路の探索法 |
| サブタイトル（和） | |
| タイトル（英） | Search process for optimal paths in multi-objective network |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 多目的ネットワーク / Multi-objective Network |
| キーワード(2)（和/英） | 拡張ダイクストラ法 / Extended Dijkstra’s Algorithm |
| キーワード(3)（和/英） | 最適経路問題 / Optimal Path Problem |
| キーワード(4)（和/英） | パレート解 / Pareto Solutions |
| 第 1 著者 氏名（和/英） | 高橋 奈津美 / Natsumi Takahashi |
| 第 1 著者 所属（和/英） | 首都大学東京(略称：首都大東京) Tokyo Metropolitan University(略称：Tokyo Met. Univ.) |
| 第 2 著者 氏名（和/英） | 山本 久志 / Hisashi Yamamoto |
| 第 2 著者 所属（和/英） | 首都大学東京(略称：首都大東京) Tokyo Metropolitan University(略称：Tokyo Met. Univ.) |
| 第 3 著者 氏名（和/英） | 秋葉 知昭 / Tomoaki Akiba |
| 第 3 著者 所属（和/英） | 千葉工業大学(略称：千葉工大) Chiba Institute of Technology(略称：Chiba Inst. of Tech.) |
| 第 4 著者 氏名（和/英） | 肖 霄 / Xiao Xiao |
| 第 4 著者 所属（和/英） | 首都大学東京(略称：首都大東京) Tokyo Metropolitan University(略称：Tokyo Met. Univ.) |
| 第 5 著者 氏名（和/英） | 新行内 康慈 / Koji Shingyochi |
| 第 5 著者 所属（和/英） | 十文字学園女子大学(略称：十文字学園女子大) Jumonji University(略称：Jumonji Univ.) |
| 発表年月日 | 2015-05-22 |
| 資料番号 | R2015-5 |
| 巻番号（vol） | vol.115 |
| 号番号（no） | R-47 |
| ページ範囲 | pp.25-30(R), |
| ページ数 | 6 |
| 発行日 | 2015-05-15 (R) |