講演抄録/キーワード |
講演名 |
2016-09-06 15:20
動的ネットワークにおける総避難時間最小化基準の下での最適施設配置問題のアルゴリズム ○高橋直暉・加藤直樹(関西学院大)・東川雄哉(中大) COMP2016-20 |
抄録 |
(和) |
道路ネットワークにおける避難者の動きをグラフで表現するために,辺の移動にかかる時間の概念を
含む動的ネットワークを用いる.
本文では動的木ネットワークを扱う.各点は供給点であり,
避難者数が割り当てられている.
また,一つの頂点を需要点つまり避難所(シンク)と考えるとき,シンクの需要量は無限である.
各辺の向きはシンクへ向かう方向へと向き付けされており,避難者はシンクへ近づく方向へ移動する.
各辺には移動にかかる時間を表す関数$tau$,辺容量を表す関数$c$が定義されている.
本研究では,全ての辺容量は同じ値$c$をとるものと仮定する.
もちろん各辺を単位時間当たりに移動する避難者数は辺容量以下でなければならない.
したがって,ある点の避難者が他の点に到着したとき,到着した点に避難者がまだ残っており
到着した避難者が先に進めないことがある.これが渋滞であり,渋滞を
考慮しつつ全ての避難者が
シンクまで移動するのにかかる時間の総和を最小にするようなシンクの最適配置を見つける.
これが総避難時間最小化基準の下での最適施設配置問題であり,この問題を解く$O(n^2)$時間,
O($n^2$)スペースアルゴリズムを提案する. |
(英) |
We study dynamic tree network to represent evacuation of
evacuees originally at vertices by using a road network
to a safety place called a sink.
In dynamic tree $T=(V,E)$, a supply (a number of evacuees)
is associated with each vertex $vin V$, each edge $ein E$ is
associated with a transit time and a capacity $c$.
The capacity limits the maximum number of evacuees that can
enter $e$ per unit time We assume $c$ takes the same
value for all edges. In addition, one vertex $v$ is designated
as a sink $s$ which represents a safety place to which
all evacuees evacuate to.
The problem is to find an optimal location of
a sink that minimized the sum of evacuation time
for all evacuees.
We propose an $O(n^2)$ time an $O(n^2)$ space
algorithm to find an optimal sink location. |
キーワード |
(和) |
動的木ネットワーク / 動的パスネットワーク / クラスタ / 総避難時間最小化 / / / / |
(英) |
Dynamic tree network / Dynamic path network / cluster / minimization of total evacuation time / / / / |
文献情報 |
信学技報, vol. 116, no. 211, COMP2016-20, pp. 37-44, 2016年9月. |
資料番号 |
COMP2016-20 |
発行日 |
2016-08-30 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2016-20 |
研究会情報 |
研究会 |
COMP |
開催期間 |
2016-09-06 - 2016-09-06 |
開催地(和) |
富山県立大学 |
開催地(英) |
Toyama Prefectural University |
テーマ(和) |
|
テーマ(英) |
|
講演論文情報の詳細 |
申込み研究会 |
COMP |
会議コード |
2016-09-COMP |
本文の言語 |
日本語 |
タイトル(和) |
動的ネットワークにおける総避難時間最小化基準の下での最適施設配置問題のアルゴリズム |
サブタイトル(和) |
|
タイトル(英) |
An algorithm for an optimal sink location problem in dynamic tree networks on condition that minimize the total evacuation time |
サブタイトル(英) |
|
キーワード(1)(和/英) |
動的木ネットワーク / Dynamic tree network |
キーワード(2)(和/英) |
動的パスネットワーク / Dynamic path network |
キーワード(3)(和/英) |
クラスタ / cluster |
キーワード(4)(和/英) |
総避難時間最小化 / minimization of total evacuation time |
キーワード(5)(和/英) |
/ |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
高橋 直暉 / Naoki Takahashi / タカハシ ナオキ |
第1著者 所属(和/英) |
関西学院大学 (略称: 関西学院大)
Kwansei Gakuin University (略称: Kwansei Gakuin Univ) |
第2著者 氏名(和/英/ヨミ) |
加藤 直樹 / Naoki Katoh / カトウ ナオキ |
第2著者 所属(和/英) |
関西学院大学 (略称: 関西学院大)
Kwansei Gakuin University (略称: Kwansei Gakuin Univ) |
第3著者 氏名(和/英/ヨミ) |
東川 雄哉 / Yuya Higashikawa / |
第3著者 所属(和/英) |
中央大学 (略称: 中大)
Chuo University (略称: Chuo 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著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2016-09-06 15:20:00 |
発表時間 |
30分 |
申込先研究会 |
COMP |
資料番号 |
COMP2016-20 |
巻番号(vol) |
vol.116 |
号番号(no) |
no.211 |
ページ範囲 |
pp.37-44 |
ページ数 |
8 |
発行日 |
2016-08-30 (COMP) |