ツリー構造を用いた緊急時の多重性のある道路網の研究

九州大学大学院 山野慶明(発表者)
新垣孝宗
外井哲志
大枝良直

概要：
道路網は災害発生時に，救助活動や緊急物資輸送のための緊急輸送路としての交通機能、避難所や延焼遮断帯としての空間機能など果たす役割は多岐に渡る．本研
究では，災害発生前から道路網は多重性を確保する必要があると着目し，道路網全体の多重性を確保する手法の提案を目的として，最小全域木を求めるために開発されたアルゴリズムであるプリム法を用いて探索法の分析を行った．その結果，プリム法を応用したシュタイナー木の探索法では，過去に熊本地震による甚大な被害を受けた熊本県における実在する規模のネットワークに対してヒューリスティクスな分析により，木による辺素な組み合わせの候補を提案できるようになった．

1

1-1.研究の背景
災害発生

道路啓開

応急復旧

本復旧

復興

図1 発災から復興の流れ

救助・救援活動、食料や薬品等の緊急物資の輸送

発災時に比べ、連結性が確保され平常時の活動に近い交通行動

連結性が求められる

時間信頼性が求められる
九州大学UIプロジェクト Kyudai Taro,2007

21-1.研究の背景
阪神淡路大震災を踏まえ緊急輸送道路が策定
・緊急輸送道路1)
各都道府県毎に設定された、災害直後の応急対策活動を円滑に行うため広域的な防災拠点を相互に連絡する耐震性などに優れた道路

・広域的な防災拠点
都道府県知事等により指定
例：地方公共団体、空港、備蓄拠点、避難所など
特徴別：指令拠点、広域交通拠点、実働的拠点、地域拠点

31-2.緊急輸送道路の現状
熊本県の緊急輸送道路
113路線のうち、28路線の50カ所が熊本地震において通行止め
・対象の幹線道路も通行止めとなり支援物資が滞る原因。
・国も県も明確な耐震基準は定めていない。

重要路線のさらなる強化や寸断された場合の備えが必要
毎日新聞(2018年5月16日）

4

1-3.研究の目的
災害発生時の影響の最小化のために、救援や物資輸送ルートとなる緊急輸送道路の確保の検討が災害発生前から求められる一部が途絶した場合であっても、代替路によって任意の拠点間を繋ぐ経路が確保されている必要がある
研究の目的
災害発生時の道路の繋がりを考慮した
複数拠点間の多重性を検討する手法の提案

5

1-4.既存研究
南ら2)２都市間に形成される道路網を対象に、代替ルートの整備水準の表現と,途絶時における最大の支障区間を指摘できる評価指標を提案した

丸山ら3)

災害時の高速道路による到達可能な経路数を算出することで、多重性の観点から道路網の評価手法について検討し、静岡県に対し有効性を検証した

宇佐美ら4)

異常気象時通行規制や過去の全面通行止め、要対策斜面数を総合化する
ことで強靭性の考え方を提示し、各道路間の途絶の起きにくさを表した

飯田ら5)

各リンクの走行可能な確率が既知であるとして、各OD間において走行が可能な確率を求めることで、道路網の信頼度を評価した

瀬戸ら6)

災害等の事象発生確率を援用せず、最悪の場合を想定した脆弱性の概念を援用し、各ODペア間の非重複経路の数から道路網の多重性評価をした

松村ら7)

将来交通量予測では四段階推定法より簡便な方法が、都市計画実務現場にて求められているとして、グラフ理論を用いた評価手法の提案をした

特定の発着点間に対する評価に留まり、道路網全体や複数拠点を同時に繋ぐ経路の多重性評価を行っている研究は少ない62-1.木の説明
ツリー構造が道路網の連結性の基本

木（ツリー）：閉路（ループ）を含まない連結なグラフ⇒任意の2点を繋ぐ経路がただ一つだけ存在する※閉路：始点と終点が同じ経路、ループ※連結グラフ：どの2点間も繋がっているグラフ

図2 ツリーの例

全域木：グラフの全ノードを含む木⇒全てのノードと一部のリンクのみで構成される木
図3 全域木の例

72-2.シュタイナー木
シュタイナー木：全域木におけるノードの部分集合を全て繋ぐ木

重要拠点間の経路を確保する必要最低限の道路網

発災直後に繋ぐべき主要拠点（重要ノード）
通過ノード
リンク
図4 シュタイナー木の例

82-3.代替路
辺素なシュタイナー木の組：共通なリンクを持たない2本のシュタイナー木

道路網の多重性の分析に有効抽出

図5 辺素な2本のシュタイナー木

図6 任意の拠点間経路の代替性の確認

93-1.整数計画法を用いた分析
目的関数①min Z = ∑𝑖𝑖 ∑𝑗𝑗≠𝑖𝑖 𝑑𝑑 𝑖𝑖, 𝑗𝑗 � （𝑋𝑋 𝑖𝑖, 𝑗𝑗 ＋𝑌𝑌(𝑖𝑖, 𝑗𝑗) ） 総走行距離の最小化

決定変数：X(I,j),Y(I,j)：ノードIからJのリンクを用いるかどうか
d(i,j)：リンク延長

代表的な制約条件②∑𝑗𝑗∈𝑆𝑆𝐴𝐴 𝑋𝑋(𝐴𝐴, 𝑗𝑗) ≥ 1 始点の設定③∑𝑖𝑖∈𝑆𝑆𝑃𝑃 𝑋𝑋 𝑖𝑖, 𝑃𝑃 = 1 重要拠点の接続の確保④∑𝑖𝑖∈𝑆𝑆𝑗𝑗 ,𝑖𝑖≠𝑘𝑘,𝑘𝑘∈𝑆𝑆𝑗𝑗 𝑋𝑋(𝑖𝑖, 𝑗𝑗) ≥ 𝑋𝑋(𝑗𝑗, 𝑘𝑘) 連結条件

⑤𝑋𝑋 𝑖𝑖, 𝑗𝑗 + 𝑋𝑋 𝑗𝑗, 𝑘𝑘 + 𝑋𝑋(𝑘𝑘, 𝑖𝑖) ≤ 2 ループの禁止

図7 得られた最短の辺素な
シュタイナー木⑥𝑋𝑋 𝑖𝑖, 𝑘𝑘 + 𝑋𝑋 𝑘𝑘, 𝑖𝑖 + 𝑌𝑌 𝑖𝑖, 𝑘𝑘 + 𝑌𝑌 𝑘𝑘, 𝑖𝑖 ≤ 1 辺素な組み合わせ⇒実在する大規模ネットワークに対する計算は不可能

104-1.プリム法を応用した分析
整数系計画法小さいネットワーク上で総走行距離か時間が最短の２組の辺素なシュタイナー木のみ、組合せをただ１つ求めることができる。
プリム法を応用したシュタイナー木の探索
ランダムなリンクを用いて求めた複数のシュタイナー木から、複数の辺素な組み合わせを提案する。
利点 複数の辺素な組み合わせを提案し、望ましい条件に近い組み合わせを求められる。計算不可能なほどの計算量の増加はない。
欠点 最短の組み合わせではない。（最短である必要もない）

114-2.プリム法を応用した分析・プリム法
始点となるノードを一つ選び、隣接したノードから最短のものを選び続け、最小全域木を求める
・プリム法を応用したシュタイナー木探索始点となる重要ノードを一つ選び、隣接したノードからランダムに選び続け、シュタイナー木を求める⇒これを繰り返し複数本のシュタイナー木を求める

124-3.プリム法①任意のノードＡを選び、隣接した距離が最も短いノードＢを採用する。
②次にＡまたはＢに最も近いノードＣを採用する。
③次にＡ、ＢまたはＣに最も近いノードを採用する。
④同様にして繰り返すことで最小全域木が得られる。

ノード

使用ノード

使用リンク
図8 最小全域木

134-4.プリム法を応用したシュタイナー木の探索①任意の重要拠点Ａを選び、隣接リンクからランダムで１つ採用する。
②次にＡまたはPの隣接リンクからランダムで１つ採用する。
③同様にして繰り返し、全ての重要拠点を採用し終えたら終了する。
④重要拠点でないノード次数が１のノードに接続したリンクを削除し完成。
JM

DG

H
L
K

N

B

重要ノード

EOI

ノード

F

図9 第一シュタイナー木

使用重要ノード144-5.プリム法を応用した分析の流れ
ネットワークデータの読み込み
プリム法を応用した複数の第一シュタイナー木の探索
選択例）走行時間が短い

プリム法を応用した複数の辺素な第二シュタイナー木の探索
選択例）交通容量が大きい

辺素な組み合わせの出力
比較・検討

155-1. 実在ネットワークに対する適用

図10 熊本県地図9)

図11 熊本県ネットワーク（ノード2188、リンク2528）

165-2.重要ノード
・広域防災拠点から災害時を想定し特徴別に設定した重要ノード①北熊本スマートＩＣ②県民総合運動公園③阿蘇くまもと空港④日赤熊本⑤熊本地方合同庁舎・熊本駅⑥熊本県庁・警察本部⑦県産業展示場・県消防学校
グランメッセ・益城熊本空港ＩＣ1324576

図12 指定重要ノード

175-3.第1シュタイナー木選択基準 (平常時優先:距離or時間)
・総走行距離だと高速道路のような幹線道路を選択しなかった。
・総走行時間にした際には、高速道路のような長距離幹線道路が選択されたため、実際の交通流に近いと考えられる。

図13 総延長が最短の第一シュタイナー木

図14 時間が最短の第一シュタイナー木

18

5-4.実在道路網における辺素な組み合わせ・平常時を考慮1

第一シュタイナー木
総走行時間が最短（200本中）
総走行時間 1.21（ｈ）
車線数平均 2.59

・災害時の強靭性を考慮
第二シュタイナー木
車線数平均が最大（64本中）
総走行時間 2.10（ｈ）
車線数平均 2.23324576

図15 辺素なシュタイナー木（時間×車線）

195-5.第二シュタイナー木の選びなおし・車線数と必要最低限の走行時間の両立
頻度

15

表１ 4指標の上位候補（各10本）

105

車線数
順位

01.7

1.75

1.8

1.85

1.9

1.95

2

2.05

2.1

2.15

2.2

2.25

車線数平均
8頻度

642061 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
車線数2以下の割合(%)
151012345678910

平均No
231450264953129427２以下

個 No
2.23 49
2.18 31
2.17 26
2.16 47
2.15 23
2.145
2.13 50
2.13 422.12 14
2.12 44%61.0
61.1
61.3
62.0
62.3
62.3
62.9
63.1
63.8
64.1

総走行時間 国道使用率No
2647
718324440
111031h No
1.85 7
1.89 26
1.95 47
1.95 50
1.98 49
1.99 121.99 23
2.01 292.01 482.01 14

頻度

4指標の上位で比較⇒４指標に唯一存在⇒No.26を選択
図16 第二シュタイナー木の3指標の頻度分布（計64本）
50

1.8 1.85 1.9 1.95

2

2.05 2.1 2.15 2.2 2.25 2.3 2.35 2.4
総走行時間(Ｈ)

%
36.51
35.46
34.7
26.77
26.49
26.34
25.58
25.47
25.12
25.02

20

5-6.2016年熊本地震を用いた有効性の検証
熊本地震通行止め（4/16～）
1・第一シュタイナー木の通行止めⒶ高速道路（植木ＩＣ-益城熊本空港ＩＣ）
期間：4/16-4/30Ⓑ県道145号
期間：4/16-4/25

・第二シュタイナー木の通行止めⒸ県道207号
期間：4/16-4/17

324576⇒通行止め箇所Ⓐの代替性を確保
通行止め箇所Ⓑ、Ⓒは代替性の確保ができな
かった
図17 選択した辺素なシュタイナー木

215-7.選択されなかった第二シュタイナー木の考察
熊本地震通行止め（4/16～）
1・第一シュタイナー木の通行止めⒶ高速道路（植木ＩＣ-益城熊本空港ＩＣ）
期間：4/16-4/30Ⓑ県道145号
期間：4/16-4/25

32

・第二シュタイナー木の通行止め

4576なし・選ばれなかった最大の原因⇒リンクの強靭性の指標が車線数では不十分だった⇒災害発生確率など直接的な脆弱性指標へ

図18 選択されなかった辺素なシュタイナー木226-1.結論と今後の課題
結論• 整数計画法とプリム法を応用した手法により、小規模ネットワークにおける辺素なシュタイナー木の組を探索し、その課題を把握した• プリム法を応用した手法は実在するネットワークに対しても辺素なシュタイナー木の組み合わせの提案ができることを確認した• 熊本県に対し、第一シュタイナー木は走行時間、第二シュタイナー木は車線数を重視した辺素な組み合わせを求め、熊本地震を例に有効性の検証を行った

23

6-2.結論と今後の課題
今後の課題• リンク脆弱性や強靭性を直接表現する指標の計算と反映（災害発生確率など）• 計算速度の短縮（未使用ノードの削除の過程を加えネットワーク縮小など）• 第二シュタイナー木を選択する指標の比較方法の検討（指標の追加、組み合わせによる提案）• 2点間最短経路との比較（ダイクストラ法の使用など）、面的被災への対応（接続リンク方向の分散、重要拠点の設置箇所など）

24

参考文献

1)国土交通省 緊急輸送道路とは
2)南正昭、高野伸栄、佐藤馨一：道路網における代替性ルートの整備水準の一評価法に関する研究、土木学会論文集No530/Ⅳ-30（1996）
3)丸山大輔、和田卓：東日本大震災を踏まえた震災時の都市間における道路のネットワーク機能、JICEREPORT vol.22（2012）4)宇佐美誠史、寺内義典、川上洋司、本多義明：災害時の道路網評価における道路の強靭性に関する研
究、土木計画学研究・論文集No.15
5)飯田恭敬、若林拓史、福島博：道路網信頼性の近似解析方法の比較研究、土木学会論文集第407号/Ⅳ11（1989）
6)瀬戸裕美子、倉内文孝、宇野伸宏：脆弱性の概念を用いた道路網接続性評価に関する研究、 土木計画
学研究・講演集vol.37（2008）
7)松村裕太、森田哲夫、藤田慎也：グラフ理論を用いた都市間計画道路ネットワークの評価手法に関する研究、土木学会論文集D3（土木計画学）、Vol67,No5（2011）8)仲井義統、沼田一道：シュタイナー問題に対する近似解法の研究
9）国土地理院

2510) 国土交通省 道路分科会第3回事業評価部会 配布資料 資料1「震災等を踏まえた今後の事業評価のあり方について」 11頁
11) 国土交通省東北地方整備局 道路部 3．11復興道路・復興支援道路情報サイト
12) 若林拓史，飯田恭敬，井上陽一：シミュレーションによる道路網の交通量変動分析とリンク信頼度推定法，土木学会論文集No458/Ⅳ-18，pp35-44，1993,113) 原田慎也，栄徳洋平，戸根智弘，三木智，若林拓史：道路の連結信頼性の実用的な評価方法の提案：
土木学会論文集D3(土木計画学)，Vol．69，No5(土木計画学研究・論文集台30巻)，2013
14) 倉内文孝，宇野伸宏，夏晧清，葉光毅：台湾道路ネットワークにおける接続脆弱性解析とその活用
15) 原田剛志，倉内文孝，高木朗義：リダンダンシーを考慮したアクセシビリティに基づく道路ネットワークの接続脆弱性評価，土木学会論文集D3(土木計画学)，Vol．70，No1，76-87，201416) 阿部翔太，有村幹治，高橋清：地方道路ネットワークの連結信頼性指標の構築に関する研究
17) 山城孝哉，阿部翔太，有村幹治，田村亨：大規模ネットワークを対象とした連結信頼性指標の解法に関する研究
18) 絹田裕一，矢部努，蛯子哲，西村巧：災害時における交通ネットワークの代替性・多重性について～交通データを活用した平常時及び災害時の所要時間の比較分析～，IBS Annual Report 研究活動報告201219) 横江れんげ：ツリーの概念を用いた道路網の多重性の評価に関する研究，九州大学卒業論文，201520) 黒瀬隆之：ツリー構造を用いた都市道路網の多重性の考察，九州大学早津行論文，201621） 関洋平，大嶽智裕、小高敏裕：シュタイナー木によるAPIとIoTデバイスの組み合わせレコメンドシステム，
ソフトウェアエンジニアリングシンポジウム201722) 外井哲志：シュタイナー木による緊急輸送道路ネットワークの構成に関する考察
23) LINGO JAPAN WebSite26

ご清聴ありがとうございました。