Yamakawa Recent site activity jsaisigsai

確率的障害下での

Contraction Hierarchy _{の適応について}

Contraction Hierarchy on stochastic failure

山川 宏隆

泉 泰介

伊藤 暢浩

岩田 員典

Yamakawa Hirotaka

Izumi Taisuke

Ito Nobuhiro

Iwata Kazunori

1

_{名古屋工業大学}

1

Nagoya Institute of Technology

2

_{愛知工業大学}

2

Aichi Institute of Technology

3

_愛知大学

Aichi University

Abstract: 近年，自然災害等による障害下でも効率の良い経路探索アルゴリズムが注目されてい る．既存の経路探索手法，Contraction Hierarchy は，障害による再探索を考慮しておらず，障害下 では効率が悪い．そこで， Contraction Hierarchy の事前計算に影響がある箇所のみを変更する方法 により，再探索時の効率を改善した．実際の地図に確率的な障害を設定した実験の結果，既存手法よ りも高速に計算でき，提案手法有効であることを確認した．

1 _はじめに

グラフの最短経路探索は基本的かつ重要な問題の一 つであり，多くの効率的なアルゴリズムが提案されて いる．古典的な最短経路問題ではすべての通行可能な 道路（グラフでは辺に相当）が入力として与えられ，そ の上の解を計算するという枠組みでアルゴリズムが設 計されるが，大規模な道路ネットワークに対する最短 経路問題では，そのような手法では各問い合わせ毎に グラフの全探索が行われてしまうため効率が著しく悪 くなる．そこで，入力として与えられるグラフを事前 に前処理しておくことで，以降の問い合わせに対して 高速に処理を行えるようにするというアプローチが近 年のトレンドである．Contraction Hierarchy[1] は，そ のようなアプローチにおける有力な手法の一つであり， 数十万頂点のグラフ上の最短経路に対して，ほぼ待ち 時間ゼロで最適解を計算することができる．

今，災害下においてリアルタイムに避難経路を探索 する状況を考える．大規模災害下においては，障害の発 生ににより道路の通行可能性が時々刻々と変化するた め，避難用の最短経路を逐一環境変化に応じて更新し ていく必要がある．しかしながら，前述の Contraction Hieararchyは障害による最探索を考慮しておらず，障

∗連絡先： 名古屋工業大学

       愛知県名古屋市昭和区御器所町        E-mail: [email protected]

害下では効率が悪い．そこで， Contraction Hierarchy に影響がある箇所のみを変更する方法により，再探索 時の効率を改善した．実際の地図に確率的な障害を設 定した実験の結果，既存手法よりも高速に計算でき，提 案手法が有効であることを確認した．

2 _諸定義

この章では，経路探索問題に共通して用いられるデー タ構造などの定義をおこなう．

グラフ経路探索がおこなわれる重み付きグラフ G を以下の ように定義する．

G = (V, E, C)

ここで V はノードの集合であり，E はノードとノー ドをつなぐ辺の集合である．今，ノードの数と辺の数 をそれぞれ |V | = n，|E| = m とすると，V と E を次 のように表現できる．

V = {1, 2, . . . , n} E = {e1, e2, . . . , em} また，特にノード i，j 間の辺を ei,jと表現すること にする．このとき，任意のノード i, j ∈ V について ei,j

と ej,iを同一視し，また ei,jはただ 1 つに定まるとする． また辺にコストを与える関数 C を以下のように定義 する．

C : E → R+

経路本稿では，任意の辺 e に関して，集合 vertex(e) が 異なるふたつの要素（ノード）を持つとする．このと き，辺 ei,j に対して，vertex(ei,j) = {i, j}と書くと き，辺 e1, e2, ..., ek ∈ E(k ≥ 1)の各 i = {1, 2, ....k − 1}に関して，vertex(ei) ∩ vertex(ei+1) ̸= ∅のとき， (e1, e2, ..., ek)を経路と呼ぶ．

また経路 (e1, e2, ..., ek)に対し，k ≥ 2 のとき， i ∈ vertex(e1)かつ j ∈ vertex(ek)かつ i ̸∈ vertex(e2) かつ j ̸∈ vertex(ek−1)のとき，経路 (e1, e2, ..., ek)は ノード i からノード j への経路と呼ぶ．k = 1 ならば vertex(e1) = i, jのとき e1を頂点 i から j への経路と いう．

経路のコスト

ノード i からノード j への経路 (e1, e2, ..., ek)のコス トは次のようになる．

C(e1, e2, ..., ek) =

∑k l=1

C(el)

最短経路ノード i から j へのすべての経路の集合を P ath(i, j) と書く．ノード i 及び j に関して，p ∈ P ath(i, j) か つ ∀p^′ ∈ P ath(i, j)で C(p) ≤ C(p^′)であるとき，p を ノード i から j への最短経路と呼ぶ．またこのときの C(p)を最短経路コストと呼ぶ．

エージェント

探索を開始するノード (開始ノード) から目的地とな るノード (目的地ノード) へ移動する対象をエージェン トと呼ぶ．

エージェントは，与えられたアルゴリズムにしたがっ て，移動先ノードを決定する．

障害情報辺（もしくはノード）に何らかの問題が発生し，エー ジェントが通過できなくなる状態を，辺（もしくはノー ド）に障害が有ると呼ぶ．また，各辺（もしくは各ノー ド）の障害の有無に関する情報を障害情報と呼ぶ． 最短経路探索問題

最短経路探索問題は，エージェントが探索を開始す るノード (開始ノード) から目的地となるノード (目的 地ノード) までの最短経路を探索する問題とする．

3 最短経路探索問題の既存研究

3.1 AdaptiveA

_{アルゴリズム}

AdaptiveA^∗ アルゴリズム [2] は，2006 年に Sven らによって提案された経路探索アルゴリズムである． AdaptiveA^∗ アルゴリズムでは，A∗ アルゴリズムの推 定値を更新しながら探索を進める．通行可能な辺の数 が減少する場合に，A^∗アルゴリズムによる探索を繰り

返すよりも短い計算時間で迂回経路を求めることがで きる．

3.2 Highway Node Routing _{アルゴリズ}

ム

Highway Node Routingアルゴリズム [3] は 2005 年 に Sanders らによって開発されたアルゴリズムである． Highway Node Routingアルゴリズムは事前計算段階 と最短経路計算段階の 2 段階に分かれている．事前計 算によって，入力グラフの頂点を階層に所属させる．こ のとき，ひとつの階層に複数の頂点を所属させる．所 属する階層にしたがって，ノード間の最短経路を保持 するショートカットを入力グラフに追加する．次に事前 計算結果をもとに最短経路探索をおこなうことで，最 短経路を求める．

事前計算に時間が必要となるが，ダイクストラアル ゴリズムよりも高速に最短経路を求めることができる． 事前計算の結果は入力グラフの情報を持つ．したがっ て，入力グラフに変更があった際に，変更に伴って事前 計算結果を変更させることが容易であり，変更に伴っ て事前計算結果を変更させるアルゴリズムが提案され ている [4]．

3.3 Contraction Hierarchy _{アルゴリズム}

Contraction Hierarchyアルゴリズム [1] は 2008 年に Geisbergerらによって開発されたアルゴリズムである． Contraction Hierarchyアルゴリズムは事前計算段階と 最短経路計算段階の 2 段階に分かれている．以下グラ フ G = (V, E, C) が与えられており，|V | = n とする． 事前計算段階

これから事前計算段階の方法を示す．

1. グラフ G^′= (V^′, E^′, C^′)とし，V^′= V，E^′= E， C^′ = Cとする．

2. ノードの重要度を求める

重要度の定め方によって，事前計算と経路探索の 時間に増減がある．重要度はいくつかの項を足 し合わせて決定する．重要度を定める項は Edge differenceや Original dges，Voronoi region など がある [1]．

3. 最も重要度が小さいノード v をグラフ V^′から取 り除き，ノード v を (1, ..., n) の階層の中からど のノードも所属していない最も数字が小さい階 層に所属させる (階層とノードは 1 対 1 に対応す る)．

ここで，自ノードより上の階層のノードを上位

ノードと呼び，自ノードより下の階層のノードを 下位ノードと呼ぶ．

4. ノード u ∈ V^′, w ∈ V^′間の最短経路が (eu,v, ev,w) の場合においてのみ，ノード u，w 間に最短経路 長 C(eu,v) + C(ev,w)を持つ辺 eu,wをグラフ E^′ に加える．C(eu,w) = C(eu,v) + C(ev,w)とし， C(eu,w)を C^′に加える．

5. 2∼4を V^′= ∅になるまで繰り返す．

このとき加えた辺をショートカットと呼び，ショー トカットも階層に所属する．ノード v を V^′から取り除 いたときにできたショートカット eu,w ∈ E^′ はノード vの所属する階層と等しいとし，ノード v はショート カット eu,wの中間ノードとする．ショートカットが加 えられる場合の詳細を図 1 に示す．実線を辺とし，点 線をショートカットとする．数字を辺またはショート カットのコストとする．

1

2 3 u

v

w

上位ノード

図 1: ショートカットの追加

G^′′= (V, E^′, C^′)を事前計算結果とする．このとき， (v, ..., n)の階層に所属するノード間の最短経路におい て，(1, ..., v−1) の階層に所属するノードを経路として持 つ最短経路は E^′が保持している．したがって，(v, ..., n) の階層に所属するノード間における最短経路は保持さ れている．

次にノードの重要度に関して説明する．ここの説明で 用いる V, V^′, C^′は事前計算過程での V, V^′, C^′とする． Voronoi region

ノード v を v ∈ V^′とし，ノード u を (u ∈ V ∧u ∈/V^′) とする．このとき C^′(ev,u)が他のどのノード w ∈ V^′ の C^′(ew,u)の値よりも小さいとき，ノード u はノード vのボロノイ領域に含まれるノードとする．ノード v の Voronoi regionの値は，ノード v のボロノイ領域に含 まれるノードの数の平方根となる．ノード v の Voronoi regionの例を図 2 に示す．実線を辺とし，コストは全 て 1 とする．また，小さい丸を V の要素とし，大きい 丸を V^′の要素とする．曲線は Voronoi region の範囲 とする．

v

Voronoi region = ^{√4 = 2}

図 2: Voronoi region

Edge difference

ノード v の Edge difference の値は，ノード v と同じ 階層に所属するショートカットの数とノード v に接続し ている辺の数の差である．ノード v の Edge difference の例を図 3 に示す．実線を辺とし，点線をノード v と 同じ階層に所属するショートカットとする．また，数 字を辺またはショートカットのコストとする．

3 1

2 1 v

3

2

Edge difference = 2 - 3 = -1

図 3: Edge difference

Original edges

ノード v の Original edges の値は，ノード v と同じ 階層に所属するショートカットが含むノード v の辺の 数の和である．ノード v の Original edges の例を図 4 に示す．実線を辺とし，点線をノード v と同じ階層に 所属するショートカット，二重線をノード v とは異なる 階層に所属するショートカットとする．辺及びショート カットの近くに書かれた数字及び括弧内の数字のうち， 数字の部分をまた，数字を辺またはショートカットの コストとする．括弧に括られている数字を本来ショー トカットがなかったら経由しなければならない辺の数 とする．

2[3]

2[4]

1 1

1[2]

1[3] 1

v

Original edges = 3 + 4 = 7

図 4: Original edges

最短経路探索段階

uに対する上位グラフ G^′′_u↑を以下のように定義する． ただし u < v はノード u よりもノード v の方が上位 ノードであることを示す．

• G^′′_u↑:= (Vu↑, E_u↑^′ )ここで Vu↑:= {v ∈ V |u < v}, E_u↑^′ := {(u, v) ∈ E^′|u < v}

開始ノードに対する G^′′_↑，目的地ノードに対する G^′′_↑ を探索範囲とする．開始ノード，目的地ノードから交互 におこなう．最短経路が存在する場合，双方向からの探 索はいくつかの共通したノード w をたどる．このとき， uから w までの経路長と w から v までの経路長の和が 最小となる経路が最短経路となる．開始ノードの探索 範囲である G^′′_↑，目的地ノードの探索範囲である G^′′_↑を 示した 2 つの例を図 5 に示す．実線を辺とし，点線を ショートカットとする．また，数字を辺またはショー トカットのコストとする．矢印を経路探索で求まった 経路とする．フレームを上位グラフを構成するノード と辺とする．(a) では開始ノードを u，目的地ノードを yとした G↑の例を示し，(b) では開始ノードを u，目 的地ノードを z とした G↑の例を示している．

上位ノード u G_u↑^’’ v

G_y↑^’’ w

x

y 8 z

5 3

2 3 2

2

1

(a) u → y

上位ノード u

v G_u↑^’’

G_z↑^’’ w

x y

z 8

5

3 ₂ 2

3 2

1

(b) u → z

図 5: 最短経路探索

この探索によって，ショートカットを含む最短経路 探索がおこなわれる．次に入力グラフが持つ辺のみの 最短経路を求める．

ショートカット eu,wは中間ノード v を持つとする． ショートカット eu,wをふたつの辺またはショートカッ ト eu,v, ev,wにわける．同様にして，すべてのショート カットが辺にわけられるまで繰り返しおこなう．ショー トカットを辺にわける図を図 6 に示す．実線を辺とし， 点線をショートカットとする．また，数字を辺または ショートカットのコストとする．

8

3 5

1 2 5

3 2 1 2

わ け る 順 番

図 6: ショートカットを辺にわける

このように Contraction Hierarchy アルゴリズムは 事前計算段階と最短経路計算段階の二つに分けられる． そして，事前計算に時間が必要となるが，ダイクストラ アルゴリズムよりも高速に最短経路を求めることがで きる．事前計算の結果は入力グラフの情報を持つ．した がって，入力グラフに変更があった際に，変更に伴って 事前計算結果を変更させることが容易である．Project Open Source Routing Machine[5]などに用いられて いる．

3.4 既存アルゴリズムに対する検討

本章では，最短経路探索問題の既存研究について述 べた．

本章で述べたように，事前計算に時間がかかってし まうが，高速に最短経路を求めることができるアルゴ リズムが提案されている．しかし，通行不能な障害へ 到達してしまうと，事前計算の結果を変更させなけれ ばならず, もう一度事前計算のやり直しが必要になり, かえって計算時間がかかってしまう．

そこで，本論文では拡張性のある Contraction Hier- archyアルゴリズムに注目し，環境 (道路情報) に関す る情報が変更された場合, 変更に伴って事前計算の結 果を効率よく変更させるアルゴリズムを，次章で提案 する．

4 _提案手法

本章では，本論文が提案する経路探索手法について 説明する．まずは本論文が対象とする問題設定につい て説明し，次に本論文の提案手法について説明する．

4.1 _問題設定

本節では，本論文が対象とする問題の環境とエージェ ントについて説明する．

4.1.1 _{既存研究との相違点}

既存研究では，入力グラフに移動障害が発生するこ とを考慮していない [1]．しかし，地震災害等で道路に 障害が発生した場合，障害を考慮していない経路探索 は効率的でない．そこで，本論文では，入力グラフの 辺に障害が発生するような問題設定をおこなう．

4.1.2 _環境

本論文では，経路探索がおこなわれる重み付きグラ フ G^′を以下のように定義する．

• G^′ = (V, E, C, B)

V, E, Cは 2.1 節の諸定義と同じものである．

また，辺に障害発生率を与える関数 B を以下のように 定義する．

• B : E→ {0 ≤ x ≤ 1}

つまり，辺の障害発生率は 0 以上 1 以下の実数と なる．

ここで，辺 ei,jに与えられた障害発生率は bi,jとする． 本論文で扱う経路障害はシミュレーション開始時に，

「障害発生率」に基づいて各辺に発生する．これ以降， 経路障害が発生した辺を障害辺と呼ぶ．また，経路障 害はシミュレーション開始時点で決定され，シミュレー ション中に増減することはない．なお, 本研究では障害 は辺のみに発生し, ノードには発生しないものとする.

4.2 _{エージェント}

本論文では，エージェントの能力および動作を以下 のように定義する．

• エージェントは，与えられたアルゴリズムにした がって，移動先ノードを決定する．

• エージェントは，初期状態で障害情報を含まない グラフに関する情報を取得できる．

• エージェントは，障害辺を移動先辺として決定す るまで，経路障害を発見できない．

4.3 _{アルゴリズム}

本論文では，Contraction Hierarchy アルゴリズムを 基にアルゴリズムを提案する．

3章で述べたように，Contraction Hierarchy アルゴ リズムは事前計算に時間がかかってしまうが，高速に 最短経路を求めることができる．しかし，経路障害が ある辺に到達してしまうと，事前計算の結果を変更さ せなければならないため, もう一度事前計算のやり直し が必要になり, かえって計算時間がかかってしまう．

そこで，本論文では環境 (道路情報) に関する情報が 変更された場合，変更に伴って事前計算の結果を効率 よく変更させることによって，Contraction Hierarchy アルゴリズムを改良し，この問題の解決を目指す．こ こで，変更に伴って事前計算の結果を変更することに かかる時間を変更時間とする．

4.3.1 Contraction Hierarchy_{アルゴリズムの改良} 本論文では，経路に障害が発生した場合，障害が発 生した辺を含むショートカットの消去と新しく必要に なったショートカットを追加する方法を提案する．

4.3.2 _{ショートカットの削除}

これからショートカットの削除方法を提案する． 1. 障害が発生した辺または無効になったショート

カットを eu,wとし，階層は u < w とする

2. uに隣接した上位ノードを調べる

3. 隣接した上位ノードが w へのショートカットを 持ち，ショートカットが eu,wを経路として持つ とき消去する

4. 削除したショートカットに対して 1∼3 を削除す るショートカットがなくなるまで繰り返す これにより，障害が発生した辺を含むショートカッ トの削除がおこなえる．辺 eu,w ∈ Eに障害が発生し たとき，辺 eu,w∈ Eを含むショートカットの消去を示 した図を図 7 に示す．実線を辺とし，点線をショート カットとする．

辺の障害に関連した ショートカットの削除 上位ノード ^s

t 障害発生

削除されたショートカットに関連した ショートカットの削除

s t

上位ノード

障害発生

図 7: 経路障害が発生した辺を含むショートカットの 消去

4.3.3 新しいショートカットの追加

まず障害が発生した辺を構成する 2 つのノードより も，下位ノードを中間ノードとする新しいショートカッ トを追加する．辺 eu,w ∈ Eに障害が発生したとし， ノード w はノード u の上位ノードであり，ノード u は k番目の階層であるとする．このとき新しく追加する ショートカットは 1, ..., k − 1 の階層において，以下の ようにおこなう．

• すべてのノードにおいて，隣接する上位ノード間 の最短経路のホップ数が 2 ホップ以下，または， 自ノードを通る場合においてのみ，隣接する上位 ノード間に最短経路長を持つショートカットを加 える．

このとき追加されるショートカットは最短経路では ないときがあるが，上位の階層は下位の階層の最短経 路を持つため，既存手法と同じ方法で，最短経路探索 をおこなうことができる．

次に，消去されたショートカットに代わる新しいシ ョートカットの追加方法について述べる．

1. 無効となったショートカットの中から，中間ノー ドの階層がもっとも低いショートカットを es,tと する

2. ノード s, t に共通して隣接する下位ノード u が存 在し，s, t 間の最短経路が u を経由するとき u を 中間ノードとするショートカットを追加する 3. 1∼2をすべての無効になったショートカットに適

用する

これにより，障害が発生した辺 es,t(階層は s < t) を 構成するノード s の階層よりも高いノード間に正しく ショートカットが追加される．辺 ev,t∈ Eに障害が発 生したとき，無効になったショートカット es,tが削除 され，ショートカット eu,tを新しく追加する方法を示 した図を図 8 に示す．実線を辺とし，点線をショート カットとする．また，数字を辺またはショートカット のコストとする．

1

2 s 3

v

t

上位ノード 4

6

障害発生 新しく追加された ショートカット u

図 8: 無効になったショートカットを削除し，新しい ショートカットを追加

5 _{提案手法の評価}

5.1 _実験目的

本論文で提案した経路探索手法が，既存の Contrac- tion Hierarchyアルゴリズムやダイクストラアルゴリ

ズムと比べて，以下の 4 点がどの程度になるかを確認 するために実験をおこなう．

• 総計算時間

• シミュレーション後に追加されるショートカット 数 (以降ショートカット数とする)

• 経路探索時間

• 変更時間

経路障害を発見するたびに事前計算結果を変更して 経路探索をおこなう．ダイクストラアルゴリズムは経 路探索時間を総計算時間とし，提案手法と既存の Con- traction Hierarchyアルゴリズムは変更時間と経路探 索時間を足し合わせたものを総計算時間とする．提案 手法と既存手法の事前計算は，あらかじめ情報が与え られており，災害が発生する前に計算されていること は妥当であるため，総計算時間に含めない．また，既 存手法の事前計算変更のショートカットは事前計算の ショートカットの追加方法と異なり，提案方法と同じ 方法で追加した．つまり，すべてのノードにおいて，隣 接する上位ノード間の最短経路のホップ数が 2 ホップ 以下，または，自ノードを通る場合においてのみ，隣 接する上位ノード間に最短経路長を持つ辺を加える．， 最短経路探索の時間が増えてしまうが，事前計算変更 時間に関して，提案手法と同じ方法を用いるためにこ の方法とした．

5.2 _実験環境

実験には 1 台の計算機を使用した．計算機の実験環境 は表 1 の通りである．また，プログラム言語には C++ を使用し，コンパイラには gcc 4.2.1 を使用した．

表 1: 計算機の実験環境 OS Mac OS X 10.6.8

CPU Intel Core i7-2620M CPU 2.70GHz

Memory 8GB

6 _{シミュレーション}

シミュレーションは，実際の地図データから作成し たグラフにおいて効果があるか確認する．

本論文では，国土地理院の発行している 2003 年度 版地図データ [6] から入力グラフ G^′ = (V, E, C, B)を 生成した．ここでは，V は交差点の集合，E は交差点 を繋ぐ道路の集合，C は交差点と交差点の距離の集合，

Bは道路の障害発生率とした．また，道路の障害発生 率は名古屋市が発行している「あなたの街の地震マッ プ」[7] の液状化危険度を基に設定した．各実験の詳細 を表 2 に示す．エージェントの開始位置と目的地はシ ミュレーションごとにランダムに配置し，実験回数は 10,000回ずつおこなった．

表 2: 各実験の設定

地図 ノード数 辺の数 実験 1 熱田区 1,760 2,609 実験 4 港区 4,892 7,127

6.1 _実験結果

各実験におけるホップ数と障害発見数の平均・標準 偏差を表 3 に示す．

表 3: 各実験の平均・標準偏差

ホップ数 障害発見数 平均 標準偏差 平均 標準偏差 実験 1(熱田区) 37.45 18.38 0.33 0.61 実験 2(港区) 72.71 39.86 0.58 0.89

6.1.1 _{実験 1}

総計算時間 (ms) と事前計算変更によって計算した ショートカット数の平均・標準偏差を表 4 に示す．

表 4: 総計算時間とショートカット数の平均・標準偏差 総計算時間 ショートカット数 平均 標準偏差 平均 標準偏差 ダイクストラ 8.95 6.81 - - 既存手法 9.94 14.47 1,548.38 2,848.63 提案手法 3.94 3.40 75.05 169.47

経路探索時間 (ms) と変更時間 (ms) の平均・標準偏 差を表 5 に示す．

提案手法はダイクストラと比べて総計算時間平均が 0.44倍，既存手法と比べて総計算時間平均が 0.40 倍 である．提案手法は既存手法と比べて変更時間平均が 0.06倍である．したがって，提案手法の方が効率的な 経路探索をおこなえている．

表 5: 経路探索時間と変更時間の平均・標準偏差 経路探索時間 変更時間 平均 標準偏差 平均 標準偏差 既存手法 5.16 6.31 4.78 8.76 提案手法 3.58 2.57 0.35 1.23

6.1.2 _{実験 2}

総計算時間 (ms) と事前計算変更によって計算した ショートカット数の平均・標準偏差を表 6 に示す．

表 6: 総計算時間とショートカット数の平均・標準偏差 総計算時間 ショートカット数 平均 標準偏差 平均 標準偏差 既存手法 28.89 42.09 7,141.74 10,964.30 提案手法 7.43 7.84 317.64 541.85

経路探索時間 (ms) と変更時間 (ms) の平均・標準偏 差を表 7 に示す．

表 7: 経路探索時間と変更時間の平均・標準偏差 経路探索時間 変更時間 平均 標準偏差 平均 標準偏差 既存手法 11.95 15.76 17.84 27.36 提案手法 5.53 4.29 1.90 4.35

提案手法はダイクストラと比べて総計算時間平均が 0.22倍，既存手法と比べて総計算時間平均が 0.26 倍で ある．また，提案手法は既存手法と比べて変更時間平 均が 0.11 倍である．また，提案手法は既存手法と比べ てショートカット数が 0.04 倍である．したがって，提 案手法の方が効率的な経路探索をおこなえている．

6.2 _考察

実験の結果より，提案手法は既存手法と比べて効率 的に探索がおこなえていることがわかった．これは，既 存手法に比べて，提案手法は経路障害によって追加を しなければならないショートカットの数が 20 分の 1 以 下になり，変更時間が少なくなるからである．

7 _{まとめと今後の課題}

7.1 _まとめ

Contraction Hierarchyの事前計算に影響がある箇所 のみを変更する方法により，再探索時の効率を改善し た．実際の地図に確率的な障害を設定した実験の結果， 既存手法よりも高速に計算でき，提案手法が有効であ ることを確認した．

このことから，本論文で提案した手法は，障害下でも 効率の良い経路探索アルゴリズムであることがわかっ た．したがって本手法は，地震災害を想定した道路ネッ トワークにおいて有効な手法であると考えられる.

7.2 _{今後の課題}

本論文では，複数体のエージェントを考慮していな い．しかし，地震災害を想定した場合，複数体で行う 経路探索が必要であると考えられる．

参考文献

[1] Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. Contraction hier- archies: Faster and simpler hierarchical routing in road networks. In Experimental Algorithms, pages 319–333. Springer, 2008.

[2] S. Koenig and M. Likhachev. A new principle for incremental heuristic search: Theoretical results. In Proceedings of the International Conference on Automated Planning and Scheduling, pages 410– 413, 2006.

[3] Peter Sanders and Dominik Schultes. Highway hi- erarchies hasten exact shortest path queries. In Algorithms–Esa 2005, pages 568–579. Springer, 2005.

[4] Dominik Schultes and Peter Sanders. Dynamic highway-node routing. In Experimental Algo- rithms, pages 66–79. Springer, 2007.

[5] Open source routing machine. urlhttp://project- osrm.org/.

[6] 国土地理院. 数値地図 25000.

[7] あ な た の 街 の 地 震 マップ. http://www.city.nagoya.jp/kurashi/category/20- 2-5-6-0-0-0-0-0-0.html.