文献

J-GLOBAL ID：201602275124459470   整理番号：16A1110213

動的ネットワークにおける総避難時間最小化基準の下での最適施設配置問題のアルゴリズム

An algorithm for an optimal sink location problem in dynamic tree networks on condition that minimize the total evacuation time

著者 (6件)： 高橋直暉 (関西学院大 院理工学研究科) ,  高橋直暉 (CREST JAPAN) ,  加藤直樹 (関西学院大 院理工学研究科) ,  加藤直樹 (CREST JAPAN) ,  東川雄哉 (中央大 理工) ,  東川雄哉 (CREST JAPAN)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 116  号： 211(COMP2016 14-22)  ページ： 37-44  発行年： 2016年08月30日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 道路ネットワークにおける避難者の動きをグラフで表現するために,辺の移動にかかる時間の概念を含む動的ネットワークを用いる。本文では動的木ネットワークを扱う。各点は供給点であり,避難者数が割り当てられている。また,一つの頂点を需要点つまり避難所(シンク)と考えるとき,シンクの需要量は無限である。各辺の向きはシンクへ向かう方向へと向き付けされており,避難者はシンクへ近づく方向へ移動する。各辺には移動にかかる時間を表す関数τ,辺容量を表す関数cが定義されている。本研究では,全ての辺容量は同じ値cをとるものと仮定する。もちろん各辺を単位時間当たりに移動する避難者数は辺容量以下でなければならない。したがって,ある点の避難者が他の点に到着したとき,到着した点に避難者がまだ残っており到着した避難者が先に進めないことがある。これが渋滞であり,渋滞を考慮しつつ全ての避難者がシンクまで移動するのにかかる時間の総和を最小にするようなシンクの最適配置を見つける。これが総避難時間最小化基準の下での最適施設配置問題であり,この問題を解くO(n²)時間,O(n²)スペースアルゴリズムを提案する。(著者抄録)

シソーラス用語： 頂点 ,  *木【グラフ】 ,  *配置問題 ,  クラスタ ,  最小化問題 ,  動特性 ,  *アルゴリズム ,  避難 ,  *道路網 ,  端部 ,  マージング ,  順路問題
準シソーラス用語： 動的パスネットワーク ,  動的木ネットワーク ,  総避難時間最小化 ,  道路ネットワーク ,  辺 ,  パス問題

分類 (2件)： ネットワーク法  (KA03040X) ,  計算理論  (JB02000A)

タイトルに関連する用語 (5件)： 動的ネットワーク ,  避難時間 ,  最小化 ,  施設配置問題 ,  アルゴリズム