渋滞を考慮した避難経路の探索
森 加奈恵(指導教員：工藤和恵)

はじめに

1

ノード vi に対して容量を Ca(i) = (1 + α)bi とする。
ここで、α(≥ 0) は容量の余裕を表している。

2011 年 3 月 11 日の東日本大震災以来、震災への様々な対策が考えられている。その 1 つとして安全な避難経路の確保が挙げられる。しかし、震源地や人の流れ、経過時間等によって通行可能な経路は時事刻々と変化する。本研究は、震源地や人の位置情報、経過時間から動的に変化する避難経路を探索することを目的とする。

2.2

ここで本研究で考慮の対象となる媒介中心性について詳しく述べる。ノード vi が流れを橋渡ししたり、制御したりする度合いを意味しており次のように定義される。
i∑Ns −1∑gi (is it )N is itis =1;is ̸=i it =1;it ̸=ibi ≡(N − 1)(N − 2)2gi (is it ) は始点 vis から終点 vit へ行く最短路の中で viを通るものの数を表しており、Nis it は vis から vit へ行く最短路の総数を表している。分子全体としては visから vit へ行く最短路の総数のうち始点 vis から終点vit へ行く最短路の中で vi を通るものの数の割合を、全ての始点と終点の組み合わせの場合について求めている (ただし、vi が始点、もしくは終点になる場合は除く)。分母は規格化定数で is と it の組み合わせの数を表している。

連鎖的なネットワークの故障

2

媒介中心性

以下のようなネットワークを考える。(図 1)• ノード:建物や交差点• リンク:道• 負荷:人の流れ• ネットワーク:地理データ

2.3

ダイナミクス

カスケード故障のダイナミクスは次のようになる。
図 1: ネットワークの例

1. あるノード v を除去する。

図 1 のようなネットワーク上において地震が起きたとする。地震に伴う人の移動によって、建物や交差点が通行不可となることがある。そうすると震源地ではなくとも通行できない建物や交差点といった場所が発生する、安全に避難するためにはそのような渋滞を回避しつつ避難しなければならない。震災時にはこのようなことが連鎖的に起こると考えられ、それを考慮した最短路探索を行いたい。

2.1

2. v を通っていた流れは迂回しなけばならない。vを除去したネットワークにおいて各ノードの媒介中心性 bi を再計算する。
3. bi ≥ Ca(i)(容量を超えた) となるノードをすべて除去する。
4. 除去したネットワークにおいて各ノードの媒介中心性 bi を再計算する。

カスケード故障とモデル

5. 容量超過のノードがなくなるまで 3 と 4 を繰り返す。

交差点や建物をノード、道をリンク、人の流れを負荷として見てみると、あるノードが壊れ (通行不可となり)、このノードから負荷が周囲に流失し、別のノードを壊してしまい、この動きはノードが全て壊れるか収束するまで連鎖的に続くものと考えられる。このような現象はカスケード故障に似ている。よってカスケード故障のモデルを参考に考える。
カスケード故障の概要とモデル、ダイナミクスについて以下に述べる [1]。カスケード故障とは、あるノードが故障したとき、このノードにかかっていた負荷 (流れ) が迂回し、迂回路上の頂点が過負荷状態に陥り、連鎖 (カスケード) 的に故障していくというものである。
まず、仮定としてネットワーク内において各ノードから各ノードへと何らかの流れがあり、その流れは最短路を通るものとする。この各ノードを通る流量、つまり負荷を媒介中心性に等しいとする。各ノード vi に対する媒介中心性 bi とする。また、過負荷状態かどうかの判断をするために各ノードの容量を定義する。各3探索方法

現在地から避難場所への避難経路を探索するとして、探索結果に従い避難経路を移動する者を探索者とする。
地理ネットワークは無向グラフとし、その情報は枝 (リンク) リストで与える。ノードの容量は建物、交差点等の定員を意味しており、過負荷状態つまり容量を超えることは渋滞していることを意味している。本研究では容量の余裕は全て統一し、容量超過の状態を媒介中心性の 120%と考え α = 0.2 とする。探索実行における成功の基準は、現在地のノードから指定した避難場所のノードに到達することができるか否かである。
探索者が移動中に避難場所ノードへのリンクを失った場合、あるいは過負荷ノードに探索者が存在する場合を避難失敗とする。カスケード故障のダイナミクスを踏まえ、媒介中心性を考慮した探索のアルゴリズムを以下に述べる。

59

(1) 与えられた枝リストを読み込む。
(2) 各ノードの媒介中心性 bi を計算し、各ノードの容量 Ca(i) を決定する。
(3) 時刻 t = 0 における現在地 (本研究では v1 に固定) を出力し、避難場所 (あらかじめ指定) 以外から震源地を選択して枝リストから除去する。
(4) t を 1 つ進める。
図 3: 大ネットワーク(5) 新たなネットワークにおいて、現在地から避難場所までの最短路探索を行う。
(6) その結果に従って探索者は 1 つリンクを移動し、現在地を更新する。
(7) 再び各ノードの媒介中心性を計算し、渋滞しているかどうか判断する。渋滞しているノード (bi ≥Ca(i)) があれば枝リストから除去する。
(8) t = 1 以降は (4)〜(7) を繰り返し、現在地と避難場所が一致すれば避難成功となる。

4

媒介中心性を考慮することの効果

図 4: 避難成功確率の比較結果

本研究で行った探索方法の効果を検証するべく、通常の最短路探索との比較を行う。ここで述べる通常の最短路探索とは現在地から避難場所までの最短路探索を 1 度だけ行い、その結果に従って探索者が移動するものである。媒介中心性を考慮する探索方法では、渋滞によって通行不可となったノードが除去されるたびに最短路を探索し直し、避難経路を変更することができた。それに対し、通常の最短路探索では経路の変更は行われず、初期のネットワークにおける最短路探索で求めた経路が断たれると避難失敗となる。
大小 2 つのネットワークを用いてそれぞれについて避難成功回数を比較する。小ネットワークとしてノード数 13 のお茶の水女子大学付近の地理を模したネットワーク (図 2) を用いる。出発点を 1 とし、震源地を2 から 13 までの 1 つに設定する。それぞれの震源地の場合にに対して、避難場所を 2 から 13 まで変更して探索を行い、避難成功回数を数える。大ネットワークとしては、ノード数 100 のランダムネットワーク (図 3)を用いる。大ネットワークについても同様に探索を行い、避難成功回数を数える。ただし、実世界の地理に近づけるためにランダムネットワークの次数分布は次数 1 と 5 を 5%、次数 2 と 4 を 35%、次数 3 を 20%とし、傾斜をつけることとする。

5考察

避難成功率の向上は小ネットワークにおいては見られなかった。ノード数が少ないため、成功率の差が出にくいと考えられる。対して、大ネットワークでは平均して 2.2%向上し、最大で 13.3%の向上が見られた。
最大の向上が見られた場合は、t = 0 における現在地(v1 ) から避難場所が遠かったことがわかった。この場合は中継するノードが多く、通常の探索では途中で経路が断たれ避難成功回数が減るため、媒介中心性を考慮した探索の避難成功率が上がったと考えられる。
次に大小ネットワーク共に避難成功率の向上が平均的には小さいことに注目したい。これは渋滞している場所から移動する人の流れと渋滞していない場所にいる探索者の移動の速さを等しく扱っているためだと考えられる。媒介中心性を考慮した探索では探索者は空いている場所を通るため、速く移動できるはずである。
移動の速さに差をつければ結果も変わると予測できる。

6

まとめと今後の課題

本研究では、震災発生時に動的に変化する避難経路の探索を可能にするべく、渋滞を回避するために媒介中心性を考慮した経路の探索方法の提案、また媒介中心性を考慮することの効果を検証した。
今後は媒介中心性を考慮した探索と考慮しない通常の最短路探索の処理の進め方の細かい設定や、震源地から人が避難する流れの速さ (負荷の迂回する速さ) と本研究の探索を利用する人の移動の速さの設定を行い、媒介中心性を考慮することの効果の検証を深めたい。
そして実世界のネットワークを用いて考察することで、より現実的な避難経路探索を可能にしたい。

参考文献[1] 増田直樹, 今野紀雄「複雑ネットワーク 基礎から応用まで」 近代科学社 (2010)
図 2: 小ネットワーク[2] 小田垣孝, パーコレーションの科学, 裳華房 (1993)
60