災害時の代替経路の確保を考慮した道路ネットワーク構築法
M2010MM045 山崎諭
指導教員：鈴木敦夫∑す．特に，経路 P の長さ e∈P le を l(P ) で表す．OD ペアの集合を OD と書き，OD ペア p ∈ OD に対する最短
東日本大震災を受け，主要経路が寸断されたときに代経路を Sp と表す．また，p = (s, t) のときには，S(s,t) とわりとなる経路 (代替経路) の重要性が見直されている．
も表す．実際の道路ネットワークにおいては，最短経路が資料 [2] によれば，国土交通省でも，現在，代替経路を評複数存在することは稀であると考えられるので，最短経価する方法が議論されている．災害で主要経路が通行で路は一意的であると仮定する．経路 P に対する経路 Q のきないとき，代替経路が大きく迂回するものでは，救援重複率を，l(P ∩ Q)/l(P ) と定める．また，P と Q の端点活動に遅れが生じてしまう．したがって，救援活動を迅が同じであるとき，P に対する Q の伸長率を l(Q)/l(P )速に行うためには，主要経路と同じくらいの所要時間で，と定義する．
主要経路との重複が少ない経路を予め用意することが有効であると考える．しかし，国あるいは地方自治体にとっ 3 代替経路の定義て，災害時に主要経路の代わりとなる経路が確保された
3.1 Abraham et al．よる代替経路の定義
道路網を実現するために，どの道路を改良すればよいか
次は文献 [1] における代替経路の定義である．OD ペアは難しい問題である．本研究では，この様な状況を踏まp= (s, t) に対して，経路 Ap を s を始点，t を終点とすえて，上記の問題に対して，一つの指針を示すような数理モデルを提案する．一般に，目的地への主要経路は最 る経路のひとつとする．ただし，Ap は最短経路 Sp では短経路であると考えられるため，本稿では，最短経路に ないとする．このとき，Ap が OD ペア p に関する代替経路であるとは，以下の三つの条件を満たすことをいう．
対する代替経路を考える．
l(Ap ∩ Sp )我々はこれまでにも，交通量の分散や代替経路の確保≤ r1 を満たす．
条件 1. 経路 Ap はl(Sp )を目的とした道路網整備計画について研究を行ってきた1

はじめに[5][6]．それらの研究では，最短経路と同じくらいの所要時間である経路を作ることで，交通量の分散や代替経路の確保が実現できるとしていた．本研究では，その考えを発展させ，災害に対して，より頑健な道路網を構築するために，どの道路を改良すべきかという問題に取り組む．そのために，まず，代替経路の厳密な定義を文献 [1]を参考に与えた．新たな定義は，災害時における道路寸断に対する耐性に着目した定義になっており，そのような代替経路を増加させることで，災害に備えた道路網の実現を図る．実現される道路網が，平時において交通量を分散させる道路網であるという特徴は，本稿のモデルにおいても継承される．提案する数理モデルでは，改良するべき道路を，ある線型計画問題の解として提案される．その線形計画問題は，最短経路問題の感度分析により得られる情報と，最短経路と代替経路の候補となる経路の重複率を用いて定式化される．また，連続型ナップサック問題への書き換えることができ，それにより，改良する道路の優先順位も明確になる．計算機実験によれば，愛知県庁から大阪府庁への代替経路を増加させることができた．

2記号の定義道路ネットワークを，N を頂点集合，E を枝集合とする有向グラフ G = (N, E) で表す．頂点数と枝数はそれぞれ |N | = n, |E| = m する．また，各枝 e ∈ E には道路長を表す長さ le が与えられている．本稿では，グラフの有向道（枝の部分集合）を経路と呼び，経路 P の始点と終点をそれぞれ sP , tP で表す．枝集合 E の部分集合 F につ∑いて，F に含まれる枝の枝長の総和 e∈F le を l(F ) で表

条件 2. 経路 Ap は T -局所最適である．
条件 3. 経路 Ap は (1 + ϵ)-一様伸長である．
条件 1 の r1 (0 ≤ r1 ≤ 1) は，重複率の上限を表すパラメータで，限界重複率と呼ぶ．
条件 2 の経路 Ap が T -局所最適であるとは，経路 Ap の部分経路 A′ のうち，l(A′ ) > T かつ l(A′′ ) < T であるものはすべて最短経路 S(sA′ ,tA′ ) に等しいことをいう．ここで，A′′ は A′ の最初の枝，または最後の枝を除いた部分経路を表す．文献 [1] では，T をパラメータ α (0 < α < 1)を用いて，T = αl(Sp ) としている．
条件 3 の経路 Ap が (1+ϵ)-一様伸長であるとは，経路 Apのすべての部分経路 A′（経路 Ap を含む）は，それと始点終点を同じくする最短経路 S(sA′ ,tA′ ) に対して，(1+ϵ) 以下のl(A′ )伸長率であることをいう．すなわち，≤ (1+ϵ)l(S(sA′ ,tA′ ) )である．ここで，ϵ は ϵ ≥ 0 のパラメータである．図 1 は(1+ϵ)-一様伸長を満たさない例である．下の経路は最短経路 S(s,t) を表しており，上の経路は二つの最短経路 S(s,v)と S(v,t) をつなぎ合わせた経路 S(s,v) ∪ S(v,t) を表す．上の経路が条件 1 と 2 を満たしたとしても，頂点 i, j 間にショートカットが存在した場合，(1 + ϵ)-一様伸長になるとは限らない．条件 3 によって，このようなショートカットが存在するものは代替経路としない．
上記の定義を満たす経路は，指数オーダの個数となり得るため，Abraham et al. は，一つの頂点 v を節点に二つの最短経路 S(s,v) と S(v,t) を接続することで得られる経路（単一頂点経由最短経路）Pv = S(s,v) ∪ S(v,t) から代替経路を見つける方法を提案している．最短経路が一意的であるという仮定の下で，単一頂点経由最短経路は，最短経路と代替経路
愛知県庁
東京都庁

50km

図 1 (1 + ϵ)-一様伸長を満たさない例

図 2 愛知県庁・東京都庁間の最短経路と代替経路
大阪府庁
山口県庁
最短経路と代替経路

多項式オーダの個数に収まる．さらに，単一頂点経由最短経路を対象とした場合，条件 2 は頂点 v の周辺で，条件を満たすかを調べればよいため，効率よく代替経路かどうかを判定することができる．

3.2

本稿における代替経路の定義

100km

文献 [1] を参考に，代替経路を以下のように定義する．
l(Ap ∩ Sp )重複条件 経路 Ap は
≤ r1 を満たす．
l(Sp )
伸長条件 経路 Ap は (1 + ϵ(l(·)))-伸長である．

図 3 大阪府庁・山口県庁間の最短経路と代替経路

4.1

枝長下限 αe,p値 αe,p は，各 OD ペア p ∈ OD と各枝 e ∈ E に対し重複条件は Abraham et al．の条件 1 と同じである．伸て，次のようにして定まる値である．枝 e の長さを短縮
長条件は Abraham et al. の条件 3 に対応するもので，条し，ある値になったとき，それまでの最短経路 Sp の他に件にある，関数 ϵ(z) は z に関して単調減少な関数である．
新たな最短経路が生じたとする．そのときの値を αe,p と経路 Ap は (1+ϵ(l(·)))-伸長であるとは，経路 Ap のすべてする．ただし，枝の長さを 0 としても新たな最短経路がの部分経路 A′（経路 Ap を含む）が，それと始点終点を同生じない場合は，αe,p = 0 と定める．値 αe,p は最短経路じくする最短経路 S(sA′ ,tA′ ) に対して，(1+ϵ(l(S(sA′ ,tA′ ) )))問題の感度分析によって求めることができる．具体的に，以下の伸長率であることをいう．伸長条件を採用した理
αe,p は e = (i, j) のとき，式 (2) によって与えられる．た由は，次のような考察による．一般的に，距離が長い ODだし，γ = min{l(Sp ), l(S(s,i) ) + l(S(j,t) )} である．
間の代替経路の場合，その経路長は最短経路長に近いこ{とが望まれる．一方で，距離が短い OD 間の代替経路の0(e ∈ Sp ),場合，道路の状況や，運転者の好みなどが優先され，必(2)αe,p =l(Sp ) − γ (e ∈/ Sp ).
ずしも最短経路長に近いわけではない．このような経路選択の傾向を考慮して，伸長率の上限を経路長 l(·) に対
最短経路問題の感度分析は，Ramaswamy et al. [4] のして，単調減少な関数 (1 + ϵ(l(·))) で与えることとした．
アルゴリズムを用いて効率的に計算できる．
具体的には，ϵ(z) は，式 (1) のような区分線形で与え4.2 伸長制限付き重複率 βe,pた．本稿では，枝長 le を時間 (秒) で与えている．

43
 10 − 100 z
ϵ(z) =29
190 − 450 z 19 − 1 z
180

1000

(0 ≤ z < 900),(900 ≤ z < 9000),(1)

まず，潜在的代替経路を定義する．枝 e = (i, j) と OD
ペア p = (s, t) に関する潜在的代替経路 Te,p を，式 (3) のように定める．

(9000 ≤ z ≤ 90000).

Te,p = S(s,i) ∪ {(i, j)} ∪ S(j,t)(3)
この代替経路の定義が妥当性を検証するために，既存の定義との比較を行った．図 2 は，愛知県庁から東京都 潜在的代替経路 Te,p を用いて，値 βe,p を，式 (4) のよう庁への最短経路 (東名高速道路) と，本稿の代替経路の定 に定める．
義を満たす経路（中央自動車道）を表している．図 3 は，
1(δ > (1 + ϵ(l(Sp )))l(Sp )),大阪府庁から山口県庁への最短経路（中国自動車道）と，
βe,p = l(Sp ∩ Te,p )(4)(δ ≤ (1 + ϵ(l(Sp )))l(Sp )).
本稿の代替経路の定義を満たす経路（山陽自動車道）を
l(Sp )表している．既存の定義では，どちらも代替経路は得られなかった．得られた代替経路は，どちらも一般に認知 ここで，δ = l(Sp ∩ Te,p ) + (1 − r2 )l(Te,p \ Sp ) である．まされている代替経路であることから，本稿で扱う代替経 た，r2 (0 < r2 ≤ 1) は，短縮率の上限を表すパラメータ路の定義は妥当なものであると考える．
で，限界短縮率と呼ぶ．δ は，Sp と Te,p に共通しない Te,pの枝をすべて上限まで改良したときの Te,p の経路長を表す．伸長条件おいて，1 + ϵ(l(Sp )) は，最短経路 l(Sp ) に
提案モデルでは，各 OD ペア p と各枝 e に対して，次に 対して，代替経路が満たすべき伸長率の上限である．よっ定義される値 αe,p , βe,p を予め計算しておく必要がある． て，δ > (1 + ϵ(l(Sp )))l(Sp ) である潜在的代替経路 Te,p4

提案モデルの準備

は，Sp と Te,p に共通しない Te,p の枝をすべて上限まで短縮しても伸長条件を満たさないため，代替経路になり得ない．あとで詳しく説明するが，このとき，βe,p = 1とすることで，OD ペア p に関して，枝 e が短縮の候補となることを予め除外する．

4.3αe,p と βe,p の求め方件を満たす経路の増加が期待できる．さらに，限界重複率 r1 により，和を取る OD ペア p を制限することで，重複条件を満たす経路が増加し易いようにする．制約式と合わせて，提案モデルは次のように定式化される．
∑∑{(le − xe ) − αe,p }(5)min.
e∈F p∈OD:βe,p ≤r1αe,p と βe,p は，与えられたネットワーク G において，すべての OD ペア p = (s, t) ∈ OD に対して，以下のアルゴリズムを実行することで求められる．

αe,p , βe,p を求めるアルゴリズム

sub. to∑be xe ≤ B ，(6)le − xe ≥ αe,pe ∈ F ，p ∈ OD， (7)e∈F

Step1. ペア p における最短経路 Sp を求める．
Step2. e ∈ Sp ならば，αe,p := 0, βe,p := 1．

xe ≤ r2 lee ∈ F，(8)xe ≥ 0e ∈ F．

(9)

Step3. 各頂点 i ∈ N に対し，始点 s からの最短経路S(s,i) と最短経路長 l(S(s,i) ) を求める．同様に，各頂点 j ∈ N から終点 t への S(j,t) と l(S(j,t) )を求める．

式 (6) は，枝 e を xe だけ短縮したときの費用 be xe の総和が，総予算 B を越えないという制約である．式 (7) は，枝 e の短縮後の長さ (le − xe ) が，αe,p よりも小さくならないという制約である．枝 e の短縮後の長さ (le − xe ) が，αe,p よりも小さくなると，主要経路である最短経路が変Step4. 各頂点 i ∈ N に対して，わってしまう．そのような場合をなるべく避けるために，a(i) := l(S(s,i) ∩ Sp )，b(i) := l(S(i,t) ∩ Sp )．
短縮可能な長さを制限する．式 (8) は，枝 e を短縮する長Step5. e ∈/ Sp ならば，さ xe が，r2 le を越えないという制約である．道路を改良
αe,p := l(Sp ) − min{l(Sp ), l(S(s,i) ) + l(S(j,t) )}．
する方法として，拡幅，舗装，直線化，高速化を想定して
Step6. e ∈/ Sp ならば，いる．したがって，短縮する長さ xe には限界があり，現状の道路を大幅に短くすることは，十分に予算があった
l(Sp ∩ Te,p ) + (1 − r2 )l(Te,p \ Sp ) ≤ (1 +a(i) + b(j)としても，物理的に不可能であると考える．そこで，限ϵ(l(Sp )))l(Sp ) のとき，βe,p :=;l(Sp )界短縮率 r2 を用いて，各枝 e の短縮可能な長さ xe を元の枝長 le の r2 倍に制限する．式 (9) は，短縮する枝の長そうでなければ，βe,p := 1.
さは非負でなければならないという制約である．

次に，上のモデルを書き換えることで得られる，最大今回実装したプログラムでは，Step3 に最も多くの計算量を要す．Step3 ではヒープによる Dijkstra 法を用いる 化問題として定式化されたモデルを紹介する．この書きので，一つの OD ペア p に対し，O((m + n) log n) で αe,p 換えにより，短縮する枝の選択順序が明確になる．各枝e ∈ F に対して，βe,p が r1 以下となる OD ペアの個数をと βe,p を求めることができる．
#{p ∈ OD : βe,p ≤ r1 } で表す．le , αe,p が定数であるこ
5 提案モデルとに注意すれば，目的関数 (5) は，次のように書き換え
この節では，道路改良箇所の選定を支援するための数 ることができる．
理モデル (提案モデル) について説明する．短縮の候補と∑max.
(#{p ∈ OD : βe,p ≤ r1 }xe ) + 定数． (10)なる枝（道路）の集合を F ⊆ E とする．各枝 e ∈ F に対して，単位長さあたりの短縮費用を be とし，短縮するための総予算を B で表す．決定変数は，枝 e を短縮する長さ xe である．
提案する線型計画問題の目的関数は二通りの表現形式を持つ．初めに，制約式と合わせて，最小化問題として表現されるモデルを紹介する．
最小化問題として定式化する場合，最小化する目的関数は式 (5) のような短縮後の枝長 (le − xe ) と αe,p の差の総和である．ただし，和は各枝 e ∈ F と βe,p ≤ r1 である
すべての OD ペア p ∈ OD に対して取られる．第 4 節の定義によると，αe,p は，枝 e の長さ le が αe,p まで短縮されたとき，OD ペア p に対する最短経路が少なくとも一つ増加するという値である．つまり，枝 e の短縮後の長さ (le − xe ) が αe,p に近づくほど，枝 e に対応する潜在的代替経路 Te,p の長さは，最短経路長 l(Sp ) に近づく．この性質に基づき，目的関数 (5) を最小化すれば，伸長条e∈F

この書き換えにより，提案モデルは連続型ナップサック問題であることが分かる．したがって，提案モデルの最適解は，貪欲算法を用いて求められる．つまり，#{p ∈ OD : βe,p ≤ r1 }be(11)の大きい順に，制約条件 (6)(7)(8)(9) を満たす範囲で，変数 xe を可能な限り大きくしたものが最適解となる．式(11) の分子には r1 が入るので，最適解が限界重複率 r1によって影響を受けることに注意する．
短縮する枝の選択順を与える式 (11) は，次のようにして，枝 e の費用対効果を表していると解釈することができる．まず，βe,p ≤ r1 を満たすような潜在的代替経路 Te,pは，重複条件をみたすことに注目する．さらに，r1 < 1 なので，βe,p の定義により，βe,p ≤ r1 であるような潜在的代替経路 Te,p は，枝の短縮により，伸長条件を満たし得る経路である．したがって，各枝 e ∈ F について，式 (11)の分子 #{p ∈ OD : βe,p ≤ r1 } は，潜在的代替経路 Te,pが代替経路になり得る OD ペア p の個数を表していると言える．よって，#{p ∈ OD : βe,p ≤ r1 } が大きい枝ほど，その枝 e を短縮することで，多くの OD ペアに対して，代替経路をもたらすと考えられる．代替経路の増加が枝 e の短縮による効果であるから，#{p ∈ OD : βe,p ≤ r1 } は，その効果の度合いを表すものと理解できる．一方，分母
be は，枝の単位長さあたりの短縮費用である．したがって，式 (11) は，代替経路の確保に関して，枝 e の短縮の費用対効果を表していると解釈できる．このような解釈により，提案モデルは，費用対効果の高い道路から改良箇所として選定するモデルであると理解することができる．

6

選定された枝50km

図 5 選定された枝計算機実験

草津JCT
近年，東海地震の発生が危惧されている．そこで，愛亀山JCT
50km
知県を中心とする広域圏において，代替経路を確保するための改良道路区間の選定を提案モデルを用いて行う．
図 6 最短経路と改良により得られた代替経路
使用する道路ネットワークは国土数値情報の道路デー
タ (平成 7 年)[2] を元に作成した．対象とする道路は高速道路，一般国道，主要地方道とし，頂点数は 1981，枝数 名神高速道路の亀山 JCT と草津 JCT である．NEXCOは 6672 である．枝の長さは，高速道路を時速 80km/h， 西日本の資料 [3] によれば，新名神高速道路の設備効果の一般国道と主要地方道を時速 40km/h としたときの移動 一つとして，代替経路の確保が挙げられている．実験に
時間 (秒) とした．OD は愛知県庁から大阪府庁への一 より得られた代替経路が，現在の新名神高速道路と同じつを考え，すべての枝を短縮の対象とする．枝の短縮費 ような経路であることは，今回導入した代替経路の定義
用を 100∼200(万円/秒) の一様乱数で与え，総予算 B は の妥当性と，提案モデルの有効性を示していると考えら
30, 000(万円) とする．限界重複率 r1 は 0.4，限界短縮率 れる．
r2 は 0.1 とする．図 4 は，使用した道路ネットワーク上 7 おわりにに，黒い点で OD の愛知県庁と大阪府庁を示し，灰色の実験により，代替経路の定義の妥当性と，提案モデル太線で愛知県庁から大阪府庁への最短経路を表したものの有効性を示すことが出来た．今後はより新しいデータである．使用した道路データが平成 7 年のものであるたと，様々な道路ネットワークに対して，実験を行いたい．
め，新名神高速道路は存在しない．そのため，最短経路には名神高速道路が選ばれた．
参考文献[1] I. Abraham，D. Delling, A. V．Goldberg，R. F．
Werneck: Alternative routes in road networks．
Proceedings of 9th International Symposium on Experimental Algorithms, pp. 23–34, 2010.
[2] 国土交通省，http://www.mlit.go.jp/.

最短経路
大阪府庁
愛知県庁

[3] NEXCO 西日本，http://www.w-nexco.co.jp/.
50km

図 4 OD ペアの位置と県庁から府庁への最短経路モデルの計算時間は次のようになった．OD ペア p ∈OD，枝 e ∈ E に対して，第 4.3 節のアルゴリズムを用いて，αe,p と βe,p を同時に求めたところ，計算時間は，約0.15 秒であった．また，提案モデルを連続型ナップサック問題として解いたところ，計算時間は約 0.02 秒であった．
実験により選ばれた 16 本の枝を短くすると，代替経路が現れた．図 5 の太線は選択された枝を示しており，図6 は最短経路と代替経路を示している． 図 6 にあるように，短縮後に代替経路と判定された経路は，現在の新名神高速道路と同じような経路となった．図 6 の太丸は新[4] R. Ramaswamy, J. B. Orlin, N. Chakravarti: Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs.
Math. Program., Ser. A 120: pp. 355–369, 2005.
[5] 山崎諭，小市俊悟，鈴木敦夫：交通量の分散化を目指した工事計画決定のモデル化，日本オペレーションズ・リサーチ学会 2011 年春季研究発表会，pp. 44–45,
2011.
[6] 山崎諭，小市俊悟，鈴木敦夫：災害発生時における代替経路の確保を考慮した新しい工事区画選定法，日本オペレーションズ・リサーチ学会 2011 年秋季研究発表会，pp. 10–11, 2011.