動的ネットワークにおける総避難時間最小化基準の 下での最適施設配置問題のアルゴリズム
著者 高橋 直暉
URL http://hdl.handle.net/10236/00026523
2016年度 修士論文要旨
動的ネットワークにおける総避難時間最小化基準の下での 最適施設配置問題のアルゴリズム
関西学院大学大学院理工学研究科 情報科学専攻 加藤研究室 高橋 直暉
道路ネットワークにおける避難者の動きをグラフで表現するために，辺の移動にかかる時間の概念 を含む動的ネットワークを用いる．本研究では動的木ネットワークおよび動的パスネットワークを扱 う．各点は供給点であり，避難者数が割り当てられている．また，一つの頂点を需要点つまり避難所
(シンク)と考えるとき，シンクの需要量は無限である．各辺の向きはシンクへ向かう方向へと向き付
けされており，避難者はシンクへ近づく方向へ移動する．各辺には移動にかかる時間を表す関数τ， 辺容量を表す関数cが定義されている．本研究では，全ての辺容量は同じ値cをとるものと仮定する．
もちろん各辺を単位時間当たりに移動する避難者数は辺容量以下でなければならない．したがって，
ある点の避難者が他の点に到着したとき，到着した点に避難者がまだ残っており到着した避難者が先 に進めないことがある．これが渋滞であり，渋滞を考慮しつつ全ての避難者がシンクまで移動するの にかかる時間の総和を最小にするようなシンクの最適配置を見つける．これが総避難時間最小化基準 の下での最適施設配置問題であり，この問題を木およびパスに対して解くアルゴリズムを提案する．
1
