災害時における避難経路選択モデル

(1)

中央大学大学院理工学研究科情報工学専攻修士論文

災害時における避難経路選択モデル

An Evacuation Route Choice Model in Case of Disaster

入学年度2004年学籍番号 04N8100003J

芦邉修一 Shuichi ASHIBE

指導教員田口東教授

2006年3月

(2)

概要

本研究では，大地震が発生してから，人々が避難所に向かうまでの避難行動をモデル化する．大地震が発生すると，人々は，対象となる避難所への避難を開始する．しかしながら，すべての住民が避難所の位置や避難所までの経路を知っているわけではないため，避難することのできない人々が少なからず存在する．

このような状況下において，避難が困難な人々を避難所まで誘導するリーダーのような存在が必要とされる．リーダーの例として，自治会や町内会のスタッフなどが挙げられる．彼らが地区内を巡回しながら住民を連れて避難所まで向かうことにより，住民は安全に避難をすることが可能となる．ここで問題となるのは，リーダーを地区内のどの位置に配置するのが適切であるか，また，何人配置すればよいか，さらに，彼らはどのような経路を選択するのが適切であるか，ということである．

本研究では，避難所までの行き方を知っていて他の避難者を引き連れていく人（以

下，Leader と呼ぶ）と，避難所までの行き方を知らないために自力で避難できない人

（以下，Followerと呼ぶ）の2 種類の人を考える．Leader は各地点でFollowerを拾

いながら避難所に向かう．このとき，各 Leader が連れて行くことのできる Follower の人数には上限があるとする．このとき，Follower の避難時間をできる限り短くすることを目的にする．このような設定において，Leader が通る経路及び，引き連れてい

くFollowerの人数を決定する問題を考える．

本研究では，この問題を 3 段階に分けた問題を考える．まず，Leader が担当する

Followerの割り当てを決定する．その後，各Leader毎に割り当てられたすべての点を

通るような最短経路を求める．最後に，各 Leader の経路が決定した後に，Follower の配分を変更してより最適な解を求める．

この解法で求められた解の精度を検証するために，ネットワークを時間方向に拡張した時空間ネットワークを構築し，厳密解を求める．3段階に分けた問題から得られた解と，時空間ネットワークから得られた解を比較し，検証する．

キーワード：整数計画問題，時空間ネットワーク

(3)

第1章序論････････････････････････････････････････････････1 1.1 研究の背景･･････････････････････････････････････････････････････････1 1.2 研究の目的･･････････････････････････････････････････････････････････1 1.3 本論文の構成････････････････････････････････････････････････････････2

第2章避難行動のモデル化･･････････････････････････････････3 2.1 問題と定義･･････････････････････････････････････････････････････････3 2.2 仮定････････････････････････････････････････････････････････････････3 2.3 配送計画問題････････････････････････････････････････････････････････4 2.4 問題の分割･･････････････････････････････････････････････････････････4 2.5 Leader が訪問するノードの決定(phase 1) ･････････････････････････････6 2.6 Leader が訪問する順序の決定(phase 2) ･･･････････････････････････････8 2.6.1 定式化･････････････････････････････････････････････････････････8 2.6.2 分枝限定法･･･････････････････････････････････････････････････10 2.7 Followerの人数の再決定(phase 3) ･･･････････････････････････････････12 2.8 Leaderが避難所を通過する際の処理･･････････････････････････････････13

第3章モデルの適用･･･････････････････････････････････････14 3.1 対象ネットワーク･･････････････････････････････････････････････････14 3.2 初期設定･･････････････････････････････････････････････････････････15 3.3 Phase1 の結果･････････････････････････････････････････････････････16 3.4 Phase2 の結果･････････････････････････････････････････････････････18 3.5 Phase3 の結果･････････････････････････････････････････････････････20 3.6 Leaderの初期配置の変更････････････････････････････････････････････22 3.7 Leaderの人数と平均避難完了時間の関係･･････････････････････････････23 3.8 最適な Leader の配置の考察･････････････････････････････････････････24

第4章時空間ネットワークの構築と評価･････････････････････26 4.1 時空間ネットワークの概要･･････････････････････････････････････････26 4.2 時空間ネットワークの構築･･････････････････････････････････････････26 4.2.1 移動リンク･･･････････････････････････････････････････････････26 4.2.2 待ちリンク･･･････････････････････････････････････････････････27

(4)

4.2.3 終点接続リンク･･･････････････････････････････････････････････28

4.2.4 時空間ネットワークにおける避難者の動き･･･････････････････････28

4.2.5 ノード数及びリンク数･････････････････････････････････････････31 4.3 定式化････････････････････････････････････････････････････････････31 4.4 例題と計算結果････････････････････････････････････････････････････32 4.4.1 例題･････････････････････････････････････････････････････････32 4.4.2 計算結果･････････････････････････････････････････････････････33 4.5 3 段階の解法による解と時空間ネットワークによる解の比較･････････････34

第5章結論･･･････････････････････････････････････････････42 5.1 まとめ････････････････････････････････････････････････････････････42 5.2 今後の課題････････････････････････････････････････････････････････42

謝辞･････････････････････････････････････････････････････････････････････43

参考文献････････････････････････････････････････････････････････････････44

(5)

第 1 章序論

1.1 研究の背景

近年，大地震に関する人々の関心が高まっている．地震に弱い地域を表した地図や，

大地震が起きた場合の帰宅を支援する地図なども書店でよく見かけるようになった．

本研究で対象とするのは，大地震が発生してから，人々が避難所に向かうまでの避難行動である．大地震が発生すると，人々は，対象となる避難所への避難を開始する．しかしながら，すべての住民が避難所の位置や避難所までの経路を知っているわけではないため，避難することのできない人々が少なからず存在する．

このような状況下において，避難が困難な人々を避難所まで誘導するリーダーのような存在が必要とされる．リーダーの例として，自治会や町内会のスタッフなどが挙げられる．彼らが地区内を巡回しながら住民を連れて避難所まで向かうことにより，住民は安全に避難をすることが可能となる．ここで問題となるのは，リーダーを地区内のどの位置に配置するのが適切であるか，また，何人配置すればよいか，さらに，彼らはどのような経路を選択するのが適切であるか，ということである．

この事象と似た問題に，配送計画問題がある．配送計画問題とは，供給点と需要点が任意の位置に配置されており，供給点を出発したトラックが車両の積載容量を超えないように，すべての需要点に配送するときに，最短の巡回路を見つける問題である．この問題はNP困難な問題として知られている．本研究の問題は，言い換えれば，この配送計画問題の逆のパターンである．トラックに相当するものはリーダーであり，需要点に相当する地点で避難者を拾いながら避難所へ向かう問題となる．細かな違いとしては，

配送計画問題がすべての需要点を回り，元の位置に戻ってくる巡回路を求める問題であるのに対し，本研究で扱う問題は，すべての需要点を回った後，避難所に到着するまでの最短経路を求める問題であることである．

1.2 研究の目的

本研究では，避難所までの行き方を知っていて他の避難者を引き連れていく人（以下，

Leader と呼ぶ）と，避難所までの行き方を知らないために自力で避難できない人（以

下，Followerと呼ぶ）の2 種類の人を考える．Leader は各地点でFollowerを拾いな

がら避難所に向かう．このとき，各 Leader が連れて行くことのできる Follower の人

(6)

数には上限があるとする．このとき，Follower の避難時間をできる限り短くすることを目的にする．このような設定において，Leader が通る経路及び，引き連れていく

Follower の人数を決定する問題を考える．ただし，この問題は前述した配送計画問題

と同じく，NP 困難な問題である．そのため，厳密解を求めるのは非常に困難である．

本研究では，この問題を3つの問題に分割し，近似解を求めることにする．

まず，Leaderが担当するFollowerの割当てを決定する．その後，各Leader毎に割当てられたすべての点を通るような最短経路を求める．最後に，各Leaderの経路が決定した後に，Followerの配分を変更してより最適な解を求める．

1.3 本論文の構成

まず，第2章において，避難行動のモデル化を行い，問題を3段階の整数計画問題として定式化する．第3章では，第2章で定式化された問題を解き，最適解を求める．第 4章では，平面ネットワークを時間方向に拡張した時空間ネットワークを構築し，厳密解を求める．さらに，第2章で提案した手法が，厳密解と比較してどの程度近似されているかを考察する．最後に，第5章では，本論文のまとめと今後の課題を述べる．

(7)

第 2 章

避難行動のモデル化

本章では，避難行動のモデル化について述べる．まず，2.1節で解くべき問題を示す．

2.2 節において，問題を考える際の仮定を定め，2.3 節では，本モデルと類似した問題である配送計画問題について述べる．

2.4節以降では，本研究で扱う避難モデルを整数計画問題として定式化し，その解法について述べる．

2.1 問題と定義

ネットワーク上に 1 ヶ所の避難所が存在する．このネットワーク上には Leader と

Followerの2種類の人間が存在する．

Followerは，避難所までの行き方を知らない避難者である．

Leader は，Follower を誘導し，ともに避難所へ向かう避難者である． Leader は，

すべてのFollowerを誘導し，避難所へ向かう．このとき，Followerの総避難時間を最

小にするような経路を求めたい．

2.2 仮定

ここで，以下の仮定を設ける．

・Leaderは，地区の地理をすべて把握し，どんな経路も選択することができる．

・Followerの発生地点と人数は，あらかじめ与えられている．

・各地点に発生したFollower は Leader が到着するまでは，その場を動くことができ

ず，Leaderが到着して初めてその場を動くことができる．FollowerはLeader と同

じ経路を通り避難所へ向かう．

・同じ地点を複数のLeaderが通過する場合は，FollowerはどちらのLeaderにも付いていくことが可能である．

・1人のLeaderが連れて行けるFollowerの人数には上限がある．

(8)

2.3 配送計画問題

配送計画問題（Vehicle Routing Problem）は，デポと呼ばれる配送拠点から配送先のノードに商品等を配送する最小コストのルートを求める問題である．ここで，ルートとは，配送車両がデポを出発し，再びデポに戻るまでの経路である．配送計画問題では，

積載量が車両の容量を超えないという制約がある．この問題は，整数計画問題で定式化されるが，NP困難な問題として知られており，研究がさかんに行われている．その主な研究として，[1]，[2]などが挙げられる．

配送計画問題がデポから需要点に対して商品の配送を行う問題であるのに対して，本研究では，配送車両に相当する Leader が，商品に相当するFollower を，配るのではなく逆に拾っていき，デポに相当する避難所へ向かうという問題になる．また，配送計画問題が車両の容量に上限があるのと同様に，本研究においても，Leader が連れて行

けるFollowerの人数に上限がある．

本研究では，この問題を[1]の研究を元に，問題を 3 つの小問題に分割し，解を求めることを目的とする．

2.4 問題の分割

本研究では，この問題を以下の3つの問題に分けて考える．

1. 各Leaderが担当するノードを決定する問題(phase 1)．

2. 決定したノードをすべて通るときの，訪問順序を決定する問題(phase 2)．

3. Leader の経路を固定し，Followerの割り当てを変更して総避難時間を最小化す

る問題(phase 3)．

phase1とphase2のイメージを図2.1，図2.2に示す．先に，図2.1のように各Leader が担当するノードを決定し，その後，図2.2のように，訪問順序を決定する問題を解く．

2.5節以降において，各問題の定式化と解法について述べる．以後，この解法を「3 段階の解法」と呼ぶことにする．

(9)

● Leader発生ノード

○ Follower発生ノード

□ 避難所図2.1 Leaderの割り当て(Phase1)

(10)

図2.2 訪問順序の決定(phase2)

2.5 Leaderが訪問するノードの決定(phase 1)

まずは，各Leaderが担当するノードを決定する．このとき，同じ地点を複数のLeader

が担当することも認めることにする．このとき，仮にLeaderがあるノードを担当するとしたら，その分だけ距離は増加する．

図2.4のようなネットワーク上で最小費用流問題を考える．この問題は以下の整数計画問題として定式化される．

目的関数（最小化）： ( ) {

∑

}

∈A j i

ij ijx c

,

(2.1) 制約条件：

{ ( ) } {j( )ji A} ⁱ

ij A

j i j

ij x s

x −

∑

=

∑

, ∈ , ∈

∀i∈N (2.2)

d xij ≤

≤

0 ∀( )i, j ∈A，xijは整数 (2.3) cij：(2.4)式で定義されるリンクのコストij

xij：図2.4で流れるリンクの流量ij si：ノードiから発生するFollowerの数

d：1人のLeaderが引率できるFollowerの数の上限 N：ノードの集合 A：リンクの集合

(11)

なお，は，初期位置がiであるLeaderがノードにいるFollowerを助けるとき，

直接避難所に向かうときと比較して増加するコストとして定義する(図2.3)．ここで，，

，はそれぞれdijkstra法で求められた2点間の最短距離である．

cij j

dij

dio djo

io jo ij

ij d d d

c = + − (2.4)

図2.3 c_ijの定義

図2.4 最小費用流問題

整数条件を除いた線形計画問題をsimplex法を用いて解く．この結果得られた解はす

=0 cij

=0 si

=250 si

−6 i = s

−3 i = s

−5 i = s

−3 i = s

Leader Follower

起点 i

Leader初期位置

j dij

Follower発生地点

djo

dio

o(避難所)

(12)

べて整数となった．

2.6 Leaderが訪問する順序の決定(phase 2)

始点，避難所を終点とし，(phase 1)で求まった担当ノードをすべ

ートとゴールの他に，訪問するノードが5点の場合の図である．

各

と表し

最小化を表す．(2.6)及び(2.7)は始点，終点からは１本の枝

は，例えば図2.8のような

であることを表す制約である．

目的関数（最小化）：

=

i j

ij ijx c

1 1

(2.5)

制約条件：

2.6.1 定式化

Leaderの初期地点を

て通るような経路を求める．始点，担当ノード，終点のすべての2点間は最短距離となる経路を選択するとし，終点に到着するまでの距離が最短になるように担当ノードの訪問順序を決定する．

図2.6は訪問するスタ

枝には，ノード間の最短距離がコストとして与えられている．このネットワークで以下の 0-1整数計画問題を解く．変数は_x_ij(i> j)であり 0 または 1 の値をとる．値が 1

ならば，Leaderがそのリンクを通るこを，値が0であれば，Leaderはそのリン

クを通らないことを表す．

(2.5)はリンクコストの和の

が，それ以外の点からは2本の枝が出ていることを表す．

次に，(2.8)について説明する．(2.6)，(2.7)の制約条件のみで

例も条件を満たしてしまう．そこで，(2.8)の条件を加えることにより，図2.8のような部分巡回路ができてしまう例を除去する．

最後に，(2.9)は変数の値が0か1のいずれか

∑∑

=

− n i 1

1 1

= +

∑

⁻

= +

=

i j

ij n

i j

ji x

x i=1,n (2.6)

2

1 1 1

= +

∑

⁻

= +

=

i j

ij n

i j

ji x

x i=2,3,4,…,n−1 (2.7)

1

, ,

−

∑

≤

>

∈

S x

j i S j i

ij ^S^⊂{¹^,²^,^…^,ⁿ}, 2≤ S ≤n−1 (2.8) or (2.9)

=0

xij x_ij =1

(13)

始点終点

図2.6 始点と終点が与えられた巡回セールスマン問題

始点終点

図2.7 解の一例

始点終点

図2.8 部分巡回路ができる例

まずは，整数条件を緩めた緩和問題をsimplex法を用いて解く．得られた解がすべて 0か1になっていれば計算は終了となる．解に小数が現れた場合は，次節で述べる分枝限定法を用いて，小数解になった変数のうちの1つの値を 0に固定した問題と 1 に固

(14)

定した問題の，2つの部分問題に分け，厳密な最適解を求める．

2.6.2 分枝限定法

与えられた最適化問題の問題例を直接解くことが困難である場合に，をいくつかの部分問題に分解して解くことを試みる．分解された部分問題が簡単に解けなければ，

さらに再帰的に部分問題への分解が行われる．その結果，

P0 P0

P0は図のように数多くの部分問題P_iに分解されていき，葉節点にあたるすべての部分問題が解かれたとき，その中の最良の解が原問題P₀の最適解を与える．一つの部分問題(原問題も含む)をいくつかの部分問題に分解することを分解操作あるいは分枝操作という．

しかし，可能な部分問題をすべて生成するのであれば単なる列挙法であって，大規模な問題を解くことはできない．そのため，生成された部分問題に限定操作と呼ばれるテストを加え，の最適解が求まるか，あるいは，を除いても原問題の最適解が失われないことがわかれば，をそこで終端することができる．限定操作が効果的に動作すれば，全部分問題のごく一部分を生成するだけで計算を終えることが可能である．

Pi

Pi Pi P0

Pi

部分問題の最適解をと記す．一般に，が，，…，に分解されるとき，

Pi f( )Pi Pi Pi1 Pi2 Pik

( ) ( )ij k

i j f P

P

f min1,2, ,

…

= =

が成立する（そうなるように分枝操作を定める）．の限定操作は，通常その制約条件を緩和した問題

Pi

Piを解くことで実行される．P_iの最適値を g( )Pi と記すと，一般に

( ) ( )Pi f Pi である．

g ≤ Piが以下の条件のいずれかをみたすとP_iを終端することができる．

１．P_iの最適解が制約条件を満たす．

２．P_iは可能解をもたない．

３．分枝限定法のそれまでの計算で得られている最良の解の値に対し，が成立する．

z g( )Pi ≥z

これらのどれも成立しなければ限定操作は失敗し，に分枝操作を適用することになる．分枝限定法のアルゴリズムのフローチャートを図2.10に示す．

Pi

(15)

原問題→活性

図2.10 分枝限定法のフローチャート min = ∞

活性な問題があるか

問題→不活性

いくつかの子問題を作成問題→不活性

子問題→活性

simplex法による求解

minの更新

終了(minの値が解となる) 解がminより大きい

すべての変数が整数

問題→不活性 yes

yes

no no

no

活性な問題のうちの1つを選択

(16)

2.7 Follower 人数の再決定(phase 3)

と，すべてのFollowerがどのLeader に

る．図中の矢印はLeaderの通る経路を表している．ここ

phase2までの計算により，各Leaderが通る経路

引率されるかが決定した．

ここで，図2.11の場合を考え

で，a点にいるFollowerはLeader1に付いて行くことしかできないが，b点にいる

Followerは，Leader1と Leader2のうち，付いて行くLeaderを選択することが可能

である．このように，複数の Leader が訪れるノードにおいては，より早く到着する

Leader に付いていくほうが総避難完了時間を短くすることができる．そこで，各

Leaderが通る経路を調べ，さらに，そのLeaderが引率できるFollowerの数にどれだ

けの余裕があるかを調べる．もし，より早く避難所に到着するLeaderに付いて行くことが可能であれば，より早く到着するLeaderに付いて行くことにする．このような考え方で以下の整数計画問題を解く．(2.10)は Follower の総避難時間の最小化を表す．

(2.11)は各ノードにおいて Leader が引率する人数の和が，その地点で発生する

Followerの数に等しいことを表す．(2.12)は Leaderが，複数の Leaderが通過するノ

ードにおいて拾うことのできる Follower の人数の最大数は，Leader が連れて行ける

Followerの数のうち，上で述べたLeaderが1人しか訪れない地点で拾う人数を引いた

人数であることを示す．

避難所

a b

Leader 2 Leader 1

図2.11 Followerの再割り当て

(17)

目的関数（最小化）： (2.10) 制約条件：

∑∑

i k

ik ix t

k i

ik ikx =s

∑

^δ ^∀^k (2.11)

f

k

ik d

x ≤

≤

∑

0 ∀i，は整数 (2.12)

：複数のLeaderが通過するノード

erの数

：通らないとき 0

i δik

：Leader の避難完了時間

か werの数

限から，必ず拾わなくてはいけないノード

Leaderが避難所を通過する際の処理

際には，Followerは避難所に

残

xik

k

ik：Leader iがノードkで拾うFollow x

⎩⎨

=⎧：Leader1 がノードkを通るとき

ti i

：ノードk ら発生するFollo sk

f ：1 人の Leader が引率できる人数の上

d

（Leaderが1人しか通らないノード）で拾う人数を引いた数

2.8

例えば，図2.12のようにLeaderが避難所を通過する

していくのが妥当だと考えられる．Leader の経路を調べ，避難所ノードを通過している場合には，その時点で引き連れているFollowerをすべて避難所に置いていくことにする．

図2.12 Leaderが避難所を通過する場合

避難所

(18)

第 3 章

モデルの適用

3.1 対象ネットワーク

ネットワークである．本研究では，東京都北区立王子第

pple2500 のルーティングデータ(歩行者

ネ

図3.1は，本研究で対象とする

三小学校を中心とした2km四方の地域を対象とする．避難所となる王子第三小学校の付近には，環七通りが東西に走っている．

ネットワークの構築には，(株)昭文社の Ma

ットワーク)を使用した．このデータで扱っている道路は，歩行者が通行できる道路であり，道路の両側に歩行者の通行する歩道がある道路では，歩行者が通行できる歩道にリンクが張られている．また，横断歩道や歩道橋などのリンクも存在する．本ネットワークの概要を表3.1に示す．

王子第三小学校 N

500m 0

環七通り

図3.1 対象地域

(19)

表3.1 ネットワークの概要

ノード数 903

リンク数 1191

3.2 初期設定

のノード上に10人のLeaderを配置した．また，Followerの発生

rを引率できるものとする．

さ

このネットワーク

地点は50箇所あり，各地点から最小で2人，最大で8人の避難者が発生し，Follower の発生人数の合計は250人である． LeaderとFollowerの初期配置を図3.2に示す．

図中において，青色がLeader，赤色がFollowerの発生地点を表している．また，各地点において発生数Followerの数の分布を表3.2 に示す．

本研究においては1人のLeaderは最大で30人のFollowe らに，LeaderとFollowerの歩行速度を1.0m/sと仮定する．

Leader Follower

図3.2 LeaderとFollowerの初期配置

避難所

(20)

表3.2 Followerの人数分布

発生人数地点数

8 人 4

7 人 5

6 人 8

5 人 16

4 人 8

3 人 5

2 人 4

.3 phase1の結果

phase1を行った結果を図3.3に示す．10人のLeaderが

3

本ネットワークにおいて，

担当する地点を，同色の四角形で表す．すなわち，円で囲まれた四角形がLeaderであ

り，Leader と同色の四角形のある地点が，その Leader が担当するノードとなる．10

人のLeaderは，各々が担当する地点をすべて通り，避難所へ向かうことになる．

(21)

Leader 6

Leader 1 ● 避難所

Leader の初期位置

Leader 2 Leader 7

Leader 3 Leader 8

Leader 4 Leader 9

Leader 5 Leader 10

図3.3 phase1の結果

(22)

3.4 phase2の結果

求められた各Leaderの巡回経路を図3.4に示す．図中の赤い線がLeaderの通った経路である．また，各Leaderが避難所に到達するまでに要した時間を図中の括弧内に示す．最も時間のかかったLeaderは避難完了までに2410秒かかり，一方，最も早く

到着したLeaderの避難完了時間は416秒であった．

Leader1の経路(1630秒) Leader2の経路(1559秒)

(23)

(24)

Leader9の経路(1266秒) Leader10の経路(2018秒) 図3.4 各Leaderの経路

3.5 phase3の結果

Leaderの経路を確定し，Followerの人数の配分を変更して解の改良を行う．ここで，

Followerの発生する50ノードのうち，複数のLeaderが通過するノードを図3.5に示

す．このようなノードは 10 箇所あった．これらの箇所において，2.6 節で述べた線形

計画問題phase3を適用する．計算の結果を表3.3に示す．ノードA，B，C，D，E，

H，J，Kにおいて各Leaderに付いて行くFollowerの人数が変化した．また，phase2 終了時点の各 Leader の引率人数と，phase3 によって再配分された後の引率人数を表 3.4に示す．避難時間の長いLeader１，2，5，8についていくFollowerの人数は減少し，避難時間の短いLeader3，4，7についていくFollowerの人数は増加した．この結

果，phase3 の平均避難完了時間は，1444 秒となり，phase2 で得られた値よりも 63

秒減少した(表3.5)．

(25)

図3.5 複数のLeaderが通過するFollower発生ノード表3.3 Followerの人数の再配分結果

ノード Leader 番号人数の変化ノード Leader 番号人数の変化

2 5 → 0 5 1 → 1

A 3 3 → 8 G

6 4 → 4

1 2 → 0 7 2 → 4

B 4 4 → 6 H

8 2 → 0

1 5 → 0 7 6 → 6

C 4 0 → 5 I

8 0 → 0

2 3 → 3 5 1 → 0

D 5 0 → 0 J

9 4 → 5

2 4 → 5 5 0 → 1

E 5 1 → 0 K

9 2 → 1

5 0 → 0 1 6 → 6

F 6 7 → 7 L

10 0 → 0

A

H I

F

K J

L

C E

B D

G

(26)

図3.4 Followerの人数の変化

Leader 番号避難完了時間（秒） phase2 人数（人） phase3 人数（人）差（人）

1 1630 30 23 -7

2 1559 30 26 -4

3 467 8 13 5

4 416 6 13 7

5 2410 30 29 -1

6 680 30 30 0

7 1246 26 28 2

8 1708 30 28 -2

9 1266 30 30 0

10 2018 30 30 0

表3.5 平均避難完了時間の変化 phase2（秒） phase3（秒）

1507 1444

3.6 Leaderの初期配置の変更

Leaderの初期配置を変更して，実験を行った．Leaderは避難所以外のノードのうち

ランダムに選ばれた10地点に配置する．この実験を2000回行った．Leaderが10人のとき，各リンクに対してLeaderが通った回数を数え，その回数を高さで表現したものを図3.6に示す．最も利用頻度が高いリンクは，地図上の東西方向へ伸びる環七通りを横断する横断歩道のリンクであり，図中で赤く示されている．

(27)

図3.6 Leaderが通りやすい経路

3.7 Leaderの人数と平均避難完了時間の関係

Leaderの人数を9人から14人の間で変化させて，実験を行う．それぞれLeader

の初期配置をランダムで与え 2000 回の実験を行った．各 Leader の人数に対する，

Followerの1人当たりの平均避難時間の最大値，最小値，平均値を図3.7に示す．Leader

の人数が増加すると，Followerの平均避難時間が減少することがわかる．

ただし，Leader が14 人のときであっても，Leaderの配置によっては1500秒以上かかる場合がある．一方，Leader が 9 人の場合でも，その配置の仕方によっては，

Followerの平均避難時間を1200秒以下にすることも可能であった．このことから，最

適な避難計画を考えるときには，Leader の人数だけでなく，その配置が重要であることがわかる．

(28)

0 500 1000 1500 2000 2500

9 10 11 12 13 14 Leaderの人数(人)

F ol lo w e rの平均避難時間( 秒)

平均値最大値最小値

図3.7 Leaderの人数と平均避難完了時間

3.8 最適な Leaderの配置の考察

本節では，避難時間が短くなるような Leader の初期配置を考える．Leader の人数を10人とし，前節で得られた結果のうち，最も平均避難時間が短くなるときのLeader の初期配置を図3.8に示す．同様に，最も平均時間が長くなるときのLeaderの初期配置を図3.9に示す．

図3.8 より，平均避難時間が短くなるときは，Leader は地区内の外側に位置していることが多いことがわかる．これは，避難所が中心にあるため，外側のFollower を助ける際には，Leaderはあらかじめ外側から出発すれば，効率が良いことを表している．

また，図 3.9では，Leader が，地図上の南側に偏ってしまっている．このような配置の場合，多くのLeader が北側のFollower を助けに行くために，遠回りとなる経路を選択するため，避難時間が長くかかってしまう．

(29)

図3.8 実験で得られた最小避難時間のLeader初期配置(Leader=10人)

図3.9 実験で得られた最大避難時間のLeader初期配置(Leader=10人)

(30)

第 4 章

時空間ネットワークの構築と評価

本章では，ネットワークを時間方向に拡張した時空間ネットワークを構築する．時空間ネットワークに拡張することによって，通常のネットワーク上と同じ扱い方で，時間の経過を表現することができる．ただし，時間方向にリンクを積み重ねていく構造のため，ノード数及びリンク数が大幅に増加する．そのため，大規模な問題に適用することは難しいが，厳密な解を求めることができる．本章では，時空間ネットワークの構築について説明し，第2章で提案した3段階の解法との比較を行い，提案手法がどの程度の精度をもっているかを考察する．

4.1 時空間ネットワークの概要

避難者の移動を表現するために，道路網上の移動にともなう時間の進行を考える必要がある．通常，時間の進行を考える場合，動的に問題を解く必要があるが，大規模なネットワークで動的な問題を解くことは困難である．

動的な問題を解く代わりに，より簡単な方法として，ネットワークを時間方向に拡張して問題を静的に解く方法がある．ここで，拡張したネットワークを時空間ネットワークと呼ぶ．時間方向に拡張することによってノード数及びリンク数は非常に大きくなるが，動的な問題を解くことに比べて，遥かに簡単に解を得ることができる．

時空間ネットワークによる解法と，提案手法との比較を表4.1に示す．

表4.1 両手法の比較

3段階の解法時空間ネットワークノード数，リンク数少ない非常に多い

解ける問題の規模大きい小さい

得られる解近似解厳密解

4.2 時空間ネットワークの構築 4.2.1 移動リンク

2点のノード間の移動で用いられるリンクを移動リンクと定義する．接続している2 点のノードに対して双方向にリンクを張る．移動リンクの構築の様子を図4.1に示す．

災害時における避難経路選択モデル