講演抄録/キーワード |
講演名 |
2015-05-22 14:35
多目的ネットワークにおける最適経路の探索法 ○高橋奈津美・山本久志(首都大東京)・秋葉知昭(千葉工大)・肖 霄(首都大東京)・新行内康慈(十文字学園女子大) R2015-5 |
抄録 |
(和) |
最適な通信ルーティング探索システムや生産・物流管理計画システムなど,現代社会において,ネットワークシステムは幅広く存在している.これらのネットワークは,複数の評価尺度を持つ多目的ネットワークと して定式化される.本研究は,このような多目的ネットワークにおいて最適経路の探索法を考察する.多目的ネットワークの最適経路探索問題の有効な解法としては拡張ダイクストラ法がある.しかし拡張ダイクストラ法におい ても,評価尺度が複数の場合は,経路探索過程で多くの記憶領域を要し計算負荷が膨大となる問題があった.本研 究では,最適経路が満たす探索空間の制限に有効な性質を用いて経路の探索空間を制限し,拡張ダイクストラ法より狭い空間で経路探索を行うアルゴリズムを提案する.そして,数値実験により提案アルゴリズムの効率性を評価する. |
(英) |
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 / / / / |
文献情報 |
信学技報, vol. 115, no. 47, R2015-5, pp. 25-30, 2015年5月. |
資料番号 |
R2015-5 |
発行日 |
2015-05-15 (R) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
R2015-5 |