13D8104028G 鴫原遼人

(1)

卒業研究論文

地方都市における歩行者避難モデル

学籍番号

13D8104028G 鴫原遼人

中央大学理工学部情報工学科田口研究室

2017

年

3

月

(2)

あらまし

本研究では、地方都市において大規模な災害が起きた際に、できるだけ早くすべての人が避難完了できるような歩行者の避難モデルを考察する。

移動時間を考慮した動的フロー問題を、時間拡大ネットワークを利用することによって解く。

キーワード：時間拡大ネットワーク、最大フロー問題、最速避難

(3)

第１章序論

第

2

章最大フロー問題

2.1

ダイクストラ法

2.2

最大フロー問題

2.3

フォードファルカーソン法

第

3

章時間拡大ネットワーク

3.1

動的ネットワーク

3.2

時間拡大ネットワーク

3.3

時間拡大ネットワーク上のフロー

3.4

最速避難の種類

第

4

章計算結果

4.1

グラフのデータ

4.2

計算結果

第

5

章おわりに謝辞

参考文献

(4)

第１章序論

災害発生時において迅速に避難することは災害の犠牲者を減らすうえで最も重要な手段の一つである。

本研究では大槌町を対象としてネットワークモデルを考察した。避難者をそのネットワーク上に流し、すべての人が避難できるような避難経路と避難時間を求める問題をネットワークフロー問題として扱った。

(5)

第

2

章最大フロー

2.1 ダイクストラ法

各枝の長さが非負でありかつどの点からも全ての点への経路が存在するネットワーク上において、１点からネットワークの全ての点への最短距離を求める際に使用されるアルゴリズム。

◎定義

入力：有向グラフ

G=(V,E)

各枝(i,j)∈Eに移動距離

tau(i,j)

(1)

始点の距離

lbl[s]=0、それ以外を未定義(今回は 0),VP=∅

(2)

すべての点を探索する(VP=V)まで以下のループを繰り返す

1.確定されていない点(V-VP)のうち lbl

が最小の点

w

を求める。

2.点 w

を確定(VP=VP∪{w})し、wを始点とする枝

e=(w,v)において lbl[v]>lbl[w]+tau(e)ならば

lbl[v]=lbl[w]+tau(e)に更新する。

(6)

ダイクストラ法の使用例

図１

(1)点 0

を出発点とする。点０の距離を０、他の点の０までの距離を∞にする。

(2)点 0

への最短経路が確定したので赤くする。確定した点０とつながる点との最短距離を解の候補として青くする。

(7)

(3)青の点から点０までの距離が最短の点を選ぶ。この場合は点 1

となる。

点１を最短距離が確定した点として赤くする。

(4)今度は点 1

を始点とし、点

1

までの経路と点１からつながっている点への

枝の距離を点０からの最短距離の候補として青くする。

ここで、点０から点

4

への最短距離は

4

だったが、点

1

を経由することでより短く行けるので点４の値を３に書き換える。

(8)

(5)青の枝の中で最短の枝は 03

となり、点３への経路が確定。

点

4

までの距離を計算するが、0→1→4の経路の方が短いので更新しない。

(6)次の候補の枝のうち点 0

からの距離が短い

14

を選び、点４への経路が確定。

点２への距離は点４経由の方が短いので更新されて４になる。

(7)最小の枝 42

を通って点２への経路が確定し、全点への最短経路が確定する。

(9)

2.2

最大フロー問題

入力有向グラフ

G=(V,E)

出発点

s∈V,到達点 t∈V

各枝

e∈E

の容量

cap(e)≥0

目的：出発点から到達点に以下の

2

つの制約を満たし、一度に「もの」送ることができる量の最大値を求める問題。

ネットワーク問題においては、送る「もの」をフローf(i,j)、

「もの」が流れる量を流量という。

(1)

容量条件

0≤ f(e) ≤ cap(e)

各枝を流れるフローは最大でも枝の容量だけ流すことができる。

(2)

流量保存則

∑

𝑒=(𝑖,𝑗)∈𝛿+(𝑗)

𝑓(𝑒) =∑

𝑒=(𝑗,𝑘)∈𝛿−(𝑘)

𝑓(𝑒)

ある点

x

において

(点 x

から流れ出す量)＝(点

x

に流れ込む量)

→f(a,x)=f(x,b)+f(x,c)

が成り立つことを表している。

a x

c

b

(10)

2.3

フォードファルカーソン法

静的ネットワーク

N

における最大フローを求めるアルゴリズムである。

◎残余ネットワーク

元のネットワークの枝と同じ向き(正の向き)の各枝に「あとどれだけの量を流すことができるか」を表した残余容量(枝の容量から枝に流れているフローの流量を引いた差)を与え、元のネットワークの枝と反対向き

(負の向き)の枝に現在流れているフローの流量を与えてできるネットワ

ーク。

定義：有向グラフ

G’=(V,E’)

E’={e∈E|f(e)<cap(e)}∪{e

^R∈E^R

|f(e)>0}

E

^R

:逆向きな仮想的な辺集合 cap

f

(e)=cap(e)-f(e) (残余容量)

cap

f

(e)=f(e) (現在流れているフロー)

◎アルゴリズム

1.

すべての枝

e∈E

についてフローf(e)←0

2.

残余ネットワーク

N(f)を作る。

3.始点 s

から終点

t

までの経路

P

を見つける。

4.経路 P

において容量

cap(P)=min{cap(e)|cap(e)∈P}を求める。

e∈P

である各枝に対し

(1) f(e)←f(e)+cap(P) (e∈P) (2) f(e)←f(e)-cap(P) (e

^R∈P)

5.s

から

t

へフローが流せなくなるまで

1~3

の作業を続ける。

・容量が整数の場合、実行時間の上限は

O(Ef)となる。

E

は枝の数、fはグラフの最大フローである。ただし、容量が無理数の場合無限に実行されてしまう。

・本研究では、始点

s

から終点

t

までの経路を求める際にダイクストラ法を用いる。

(11)

実行例

図２のフローネットワークを利用して最大フローを求める。

図２

ルート

S A B T

に沿って最小の容量の

6

だけフローを流す。

(12)

ルート

SACT

に沿って４のフローを流す。

ルート

SCT

に沿って１だけフローを流す。

残余ネットワークにおいて

S

から

T

へのルートが存在しなくなった。

よってこれが最大フローとなる。

(13)

第

3

章時間拡大ネットワーク

3.1

動的ネットワークの定義

動的ネットワークは点の集合

V

とそれらの点を結ぶ枝の集合

E

からなる有向グラフ

G=(V,E)と以下の関数によって構成される。

・枝上に容量関数

c,移動時間関数λ

・出発点集合

X⊂V,到達点集合 Y⊂V＼S

・Xに初期の人数

sup,Y

に到達点の容量

cap

この形のままだと移動時間も考慮するため最大フロー問題を解くのが困難である。したがって、時間拡大ネットワークを用いて静的ネットワークと

して問題を解く。

図

3：部屋を動的ネットワークしたもの

(14)

3.2

動的ネットワークを離散時間ずつ進めたコピーを積み上げて、枝上の移動を平面上の移動と時間軸上の移動を合わせて静的ネットワークの移動として表現できるネットワークである。

動的ネットワーク

N

と期間

T

から構成するには以下の操作を行う。

1. V

に含まれる点を

T

回複製。各時刻での点に相当する。

2.

ある時刻

t

における点

v

を出発する辺

e

は時刻

t+λ(e)に接続

3.

超出発点

ss,超到達点 st

と呼ばれる２つの点を追加し、容量∞,移動時

間

0

の辺を追加。

・サイズ：点数が|V|×(T+1)+2,枝数が(|E|+|X|+|Y|)×(T+1)となる。

したがって入力するネットワークのサイズまたは期間Ｔが大きくなると、時間拡大ネットワークのサイズが非常に大きくなる。

図

4：図 3

の動的ネットワーク(左図)の時間拡大ネットワーク

(15)

3.3

時間拡大ネットワークにおけるフロー

N

が与えられたとき、フローの定義は

∀e∈E,θ

∈{0,1,…,T}において以下の条件を満たす関数

f(e)

・容量制約

各枝のフローは容量以下の流量でないといけない。

f(e)≤c(e)

・流量保存側

時間

θ

である点

v

において、時間

θ-λ(e)の点からフローの量と

点

v

から出ていくフローの量は等しい。(λ(e):枝の移動時間)

∑

_{𝑒∈𝑣−}

∑

^{𝜃−𝜆(𝑒)}_𝑡=0

𝑓(𝑒, 𝑡) -∑

_𝑒∈𝑣+

∑

^𝜃_𝑡=0

𝑓(𝑒, 𝑡) =0 ∀v∈V＼(X∪Y)

・端子点制約

出発点から時間拡大した点に流れたフローの流量は初期の人数と等しい。また、時間拡大した点から到達点に流れたフローの流量は到達点の容量以下である。

∑

_𝑒∈𝑆

∑

^𝑇_𝑡=0

𝑓(𝑒, 𝑡) =sup(s) ∑

_𝑒∈𝑇

∑

^𝑇_𝑡=0

𝑓(𝑒, 𝑡) ≤cap(t)

図

5

時間拡大ネットワークにフローを流している。

(16)

3.4

最速避難

1.最早完了避難

・最も避難に時間のかかる人が避難所に到達する時間を最小になる避難・超出発点から超到達点への最大流が端子点制約を満たす

最小の期間Ｔが避難完了時刻となる。

・時間拡大ネットワーク上で超出発点から超到達点までの最大フローを求めてその分だけ避難者を流す。この作業を避難者が避難完了するまで行い、期間Ｔを求める。

2.最小移動時間最早完了避難

・避難完了が最小の避難のうち、避難者の移動時間の総和が最小の避難・移動時間を費用とした最小費用最大流を求める。

・移動時間の総和は「避難完了時間最小」という条件を考慮しない場合に比べ、大きくなってしまう可能性がある。

3.前方優先避難

・時刻の昇順にその時刻での避難完了者数を最大化する操作を行うことで求める避難

・避難の初期段階では避難完了者が最大となる。

この研究では

1

の最速避難を求める。

(17)

第

4

章計算結果

4.1

使用するデータ ◎大槌町の以下の要素

点：点番号、座標

枝：枝番号、始点、終点、距離、容量避難者の人数

11836

人

出発点の数

1118

箇所避難者の歩行速度

1.0m/s

避難所の設定５つ

時間制限：3600秒

本研究の時間拡大ネットワークは元のネットワークの各点を

z

軸方向に時間拡大することで得ている。また、前章の時間拡大ネットワークでは１秒おきに点をコピーしているが、本研究では計算量を減らすために時間の間隔を

6

としているため(時間制限)/(時間の間隔)=3600/6=600点を

z

軸上に積み上げている。

図

6

は元の大槌町のネットワークであり、図

7

は図

6

のネットワークの各点を

z

軸方向に

600

個の点を積み上げた時間拡大ネットワークである。

図

6 大槌町のデータを用いたネットワーク

(18)

図

7:大槌町の時間拡大ネットワーク Z

軸方向に時間が進んでいる。

4.2

計算結果

下の５枚の図は５箇所の避難所付近を表したものである。

大きい円が避難所、小さい円が避難開始点となっており、色が青に近づくほど避難完了時間が早く、赤に近づくほど避難完了時間が遅いことを表している。

下図から避難所から離れるにつれて避難完了時間が遅れることがわかる。

図８

(19)

図９

図

10

(20)

図

11

図

12

(21)

図

13:各時刻での避難完了者数の推移

避難完了時間:3086秒

避難完了時間は約

51

分となった。東日本大震災において地震発生から津波が到達する時間は

30~50

分である。そのことを参考にすると安全な避難ができる

30

分以内に避難者の

90%が避難完了できている。その一方で残りの避難者が避

難完了するまで

20

分以上かかっている。現状の避難所の配置だと迅速な避難ができているとは言い難い.すべての避難者が

30

分以内に避難完了できるようにする場合、30 分以降に避難完了した避難者の避難開始地点をカバーできるような避難所の設置を考慮すべきである。

0 2000 4000 6000 8000 10000 12000 14000

0 500 1000 1500 2000 2500 3000 3500

避難者

時間

(22)

第

5

章おわりに

本研究では、地方における災害発生時の歩行者避難モデルを考察した。計算結果より、今回の最速避難では最も遅い人の避難完了時間を最小にするようにしたが、それぞれの用途においてどの最速避難を求めるか異なるためその結果の違いも考察したい。

今後の課題として今回の実験では移動時間は一定であったが、実際には避難者の密度によって移動時間は変化する。より精密な避難モデルを作成するためには移動時間を密度に依存する関数として定義する必要がある。

(23)

謝辞

この研究を進めるにあたって、大槌町のデータの提供及びプログラムの修正等について多くのご指導,ご助言を頂きました田口東教授及山形浩一助教に深く感謝いたします。また、多くのご協力をいただいた田口研究室の皆さまにも深く感謝いたします。

(24)

参考文献

[1]

著者瀧澤重志他

「No.415:普遍的最速フロー型緊急避難モデルの大規模計算への拡張と大阪市の津波避難ビルの立地評価への応用」

2013

年度

CSIS

共同研究報告書

pp.4-13

2014

年

5

月

[2]

著者

H.W. Hamacher,S.A.Tjandra

「Mathmatical Modelling of Evacuation Problems:A State of the Art」

Berichte des Fraunhofer-Instituts für Techno- und Wirtschaftsmathematik (ITWMReport)(24)

pp240 January 2002

[3]http://even-eko.hatenablog.com/entry/2013/08/08/195120

図２で使用