第９回 基礎ゼミ
ネットワークの表現と経路探索

福田研 修士1年

小川晃平

本日の内容2第２章 ネットワークの表現とリンクコスト関数
第３章 ネットワークフローが満足すべき条件

第８章 利用者均衡モデルの解法
8.1 最短経路探索アルゴリズムとデータ構造

Fundamental Seminar 2018/05/31

第２章 ネットワークの表現とリンクコスト関数
1節 交通ネットワークの構成要素と交通網のネットワーク表現• 交通ネットワークの基本的な構成要素と交通網のネットワーク表現法• 少し複雑な交通網のネットワーク表現

2節 リンクパフォーマンス関数• 代表的なリンクパフォーマンス関数• 均衡交通量配分計算方法との対応関係

Fundamental Seminar 2018/05/31

3

第２章 ネットワークの表現とリンクコスト関数

1節 交通ネットワークの構成要素と交通網のネットワーク表現
物理的ネットワーク

概念的ネットワーク

いずれにせよ，ネットワークは“点の集合”と“線の集合”から成り立っている• 点→交差点，接点• 線→道路，情報の流れ
数学的表現

点の集合・・・ノード集合𝑁
線の集合・・・リンク集合𝐴

有向グラフ𝐺 𝑁, 𝐴 で表すことができる

Fundamental Seminar 2018/05/31

4

第２章 ネットワークの表現とリンクコスト関数

1節 交通ネットワークの構成要素と交通網のネットワーク表現
交通ネットワークにおいては・・・
ノード集合𝑁

リンク集合𝐴• 交通需要の発生ノード集合𝑅• 実際の道路区間• 交通需要の集中ノード集合𝑆• 状況に応じた仮想的な道路区間• それ以外のノード集合＊各ノード𝑛は正の整数で対応する＊リンクの要素𝑎は正の整数で対応する

通常，交通需要分析は分析対象地域をゾーンに分割して行われる⇒ゾーンの中心にあるノードを“セントロイド”と呼ぶ

Fundamental Seminar 2018/05/31

5

第２章 ネットワークの表現とリンクコスト関数

1節 交通ネットワークの構成要素と交通網のネットワーク表現

3

5発生量

190130220

25070120

集中量

140200340

OD

1 → 3の分布交通量

図1 道路網のネットワーク表現

ノード

リンク

総生成交通量

図1のネットワークは1～6のノードと1～11のリンクで構成されている
リンク1～10は固有のリンク抵抗値𝑡𝑎 を持つ
リンク11は仮想的リンクで抵抗値は定数
ノード6は料金ゲートを表現した仮想ノード

Fundamental Seminar 2018/05/31

6

第２章 ネットワークの表現とリンクコスト関数

1節 交通ネットワークの構成要素と交通網のネットワーク表現

交差点内に方向別リンクを設定

右・左折，直進別の交差点遅れが表現可能（1つのノードだけでは表現できない）
また，東西の道路から南北への右折が規制されている状況をモデル
図2 平面交差点のネットワーク＊右折するリンクが存在しない

Fundamental Seminar 2018/05/31

7

第２章 ネットワークの表現とリンクコスト関数

1節 交通ネットワークの構成要素と交通網のネットワーク表現
降車リンク

路線B

（抵抗値＝0）

路線A
乗車リンク（抵抗値＝当該交通機関の平均待ち時間）

停留所ノード図3 公共交通輸送網のネットワーク

路線Aから路線Bへ乗り換えをする場合
分析の対象となる実際の交通網は，分析の目的・求められる精度・
抵抗値は降車リンク1と乗車リンク4を組み合わせて表現することができる
予算などに応じて適切に表現されなければならない
Fundamental Seminar 2018/05/31

8

第２章 ネットワークの表現とリンクコスト関数

1節 交通ネットワークの構成要素と交通網のネットワーク表現
詳細（ミクロ）な都市交通需要分析⇒街路網ネットワーク（city street network）が最適•

リンク→すべての道路区間•

ノード→すべての交差点・交通施設

図4 都市街路網ネットワーク
Fundamental Seminar 2018/05/31

9

第２章 ネットワークの表現とリンクコスト関数

1節 交通ネットワークの構成要素と交通網のネットワーク表現10

大都市圏（マクロ）での交通需要分析

分析対象地域をゾーン分割（ゾーン中心にセントロイドを想定）

主要道路で構成されるネットワークを設定

ゾーン間で交通需要分析を行う

図5 主要道路網ネットワーク
Fundamental Seminar 2018/05/31

第２章 ネットワークの表現とリンクコスト関数

1節 交通ネットワークの構成要素と交通網のネットワーク表現
時間・空間を同時に表現するネットワーク⇒タイムテーブルにしたがって運行される列車ダイヤと輸送網を表現する

横軸・・・時間（時刻）縦軸・・・空間（駅・駅間）

図6 列車ダイヤの時間・空間的ネットワーク表現
Fundamental Seminar 2018/05/31

11

第２章 ネットワークの表現とリンクコスト関数

1節 交通ネットワークの構成要素と交通網のネットワーク表現
移動滞在B
A

時刻 𝑡 + 1

B
A

時刻 𝑡

A

時刻 𝑡 − 1B
図7 時間・空間的ネットワーク表現（3次元）
Fundamental Seminar 2018/05/31

12

第２章 ネットワークの表現とリンクコスト関数

2節 リンクパフォーマンス関数

13

交通ネットワーク上の各リンクは特有の抵抗を持つ
抵抗を構成する要因• 旅行時間• 走行費用• 安全性• 快適性…etc

人の経路選択において最も主要な要因は“目的地までの所要時間”

ゆえに所要時間がリンク抵抗の単一の測度として用いられる場合が多い
しかし，公共交通輸送ネットワークへのパーソントリップの配分問題では…

リンク抵抗

Fundamental Seminar 2018/05/31

第２章 ネットワークの表現とリンクコスト関数

2節 リンクパフォーマンス関数
𝑡𝑎 = 𝑡𝑎 (𝑥𝑎・・・ リンクパフォーマンス関数（𝑡𝑎 を表す関数）

リンク抵抗𝑡𝑎 は定数ではなく，当該リンクの交通量𝑥𝑎 の関数と考えられる⇒ 𝑥𝑎 が増加すると，所要時間は増加し安全性は低下する
リンクパフォーマンス関数≒リンクコスト関数，リンク抵抗関数，リンク旅行時間関数

交通流理論におけるリンクパフォーマンス関数
リンクパフォーマンス関数①
交通混雑による交通流の停止はあり・信号停止なし

リンクパフォーマンス関数②
交通混雑による交通流の停止はあり・信号停止あり
Fundamental Seminar 2018/05/31

14

第２章 ネットワークの表現とリンクコスト関数

2節 リンクパフォーマンス関数

15

リンクパフォーマンス関数①
交通混雑による交通流の停止はあり・信号停止なし
リンクa上での速度𝑉𝑎 (km/h)と交通量𝑥𝑎 (pcu/h)，密度𝐷𝑎 (pcu/km)の関係
𝑥𝑎 = 𝐷𝑎 ∗ 𝑉𝑎
＊passenger car unit（車両一台を自動車交通量に換算した自動車換算交通量）

速度𝑉𝑎 と密度𝐷𝑎 は近似的に線形関係にある

𝑉𝑎𝑓
𝑉𝑎 = 𝑉𝑎𝑓 −
∗ 𝐷𝑎
𝐷𝑎𝑗

𝑉𝑎𝑓 ：ゼロフロー時の速度（自由速度）
𝐷𝑎𝑗 ：速度がゼロのときの密度（飽和密度）

上記2式より， 𝐷𝑎 を削除すると…
𝑉𝑎2 − 𝑉𝑎𝑓 ∗ 𝑉𝑎 +𝑉𝑎𝑓
∗ 𝑥𝑎 = 0 ⋯ 式𝑋
𝐷𝑎𝑗

Fundamental Seminar 2018/05/31

第２章 ネットワークの表現とリンクコスト関数

2節 リンクパフォーマンス関数

16式𝑋は速度に関する2次関数
この式からリンク𝑎を通過可能な最大交通量𝐶𝑎 （＝可能交通量）を求める
12𝑑𝑋= 2𝑉𝑎 − 𝑉𝑎𝑓 = 0𝑑𝑉𝑎1
𝑉𝑎 = 𝑉𝑎𝑓
2𝑉𝑎 = 𝑉𝑎𝑓 を式𝑋に代入すると
𝑉𝑎𝑓
𝐶𝑎 = 𝐷𝑎𝑗 ∗4

リンク𝑎の単位距離当たりの所要時間𝑡𝑎 は速度𝑉𝑎 の逆数であるから，
式𝑋は以下のようになる

1𝑡𝑎

2

11−
∗+𝑡𝑎0𝑡𝑎1𝑡𝑎0
𝐷𝑎𝑗

𝑥𝑎 = 0Fundamental Seminar 2018/05/31

𝑡𝑎0 ：ゼロフロー時の所要時間

第２章 ネットワークの表現とリンクコスト関数

2節 リンクパフォーマンス関数

17• ひとつの交通量の値に対して２つの所要時間の値を持つ二値関数•1

交通量𝐶が最大のとき，𝑉𝑎 = 𝑉𝑎𝑓
2
ゆえに𝑡 = 2𝑡𝑎0

図 停止のない場合の交通量と旅行時間

Fundamental Seminar 2018/05/31

第２章 ネットワークの表現とリンクコスト関数

2節 リンクパフォーマンス関数

18
一方，当該リンクの下端で信号停止を余儀なくされる場合
所要時間＝走行時間＋信号遅れ時間

交通量が信号交差点容量に近づくにつれ信号遅れ時間が急速に増加

交通流がストップ

図 停止のある場合の交通量と旅行時間ゆえに交通容量に漸近するような関数

Fundamental Seminar 2018/05/31

第２章 ネットワークの表現とリンクコスト関数

2節 リンクパフォーマンス関数

19Davidson関数・・・待ち行列理論により導出された関数

𝑡𝑎 𝑥𝑎

𝐽𝑥𝑎
= 𝑡𝑎0 1 +𝐶𝑎 − 𝑥𝑎

𝑥𝑎 ：リンク交通量
𝑡𝑎0 ：交通量ゼロのときの所要時間
𝐶𝑎 ：交通容量
𝐽：遅れパラメータ（リンク特性に依存）
図 Davidson関数

Fundamental Seminar 2018/05/31

未知数第２章 ネットワークの表現とリンクコスト関数

2節 リンクパフォーマンス関数

20BPR関数・・・米国道路局が考案したモデル

𝑡𝑎 𝑥𝑎𝑥𝑎= 𝑡𝑎0 1 + 𝛼
𝐶𝑎𝛽𝛼, 𝛽:パラメータ
米国（𝛼 = 0.15, 𝛽 = 4）↓（日本の道路規格に適用）
日本（𝛼 = 2.62, 𝛽 = 5 ）図 BPR型リンクパフォーマンス関数
Fundamental Seminar 2018/05/31

第３章 ネットワークフローが満足すべき条件
1節 パス―リンクインシデンスマトリックス• 交通ネットワークを数学的に記述する術

2節 ネットワークフローの保存条件• 均衡フローを求める際にネットワークが満たすべき条件

Fundamental Seminar 2018/05/31

21

第３章 ネットワークフローが満足すべき条件

1節 パス―リンクインシデンスマトリックス

22• 任意の𝑂𝐷ペア𝑟𝑠間には利用可能な経路は沢山存在する
しかし，全ての経路が利用されているわけではない
利用可能経路集合

有効経路集合Fundamental Seminar 2018/05/31

第３章 ネットワークフローが満足すべき条件

1節 パス―リンクインシデンスマトリックス•

有効経路集合𝐾𝑟𝑠 を数学的に記述する
パス―リンクインシデンスマトリクス∆24

ネットワーク図𝑶𝑫24
𝛿𝑎,𝑘=１（経路𝑘中にリンク𝑎が存在する）
０（経路𝑘中にリンク𝑎が存在しない）

Fundamental Seminar 2018/05/31

23

第３章 ネットワークフローが満足すべき条件

2節 ネットワークフローの保存条件

24

ネットワーク上のフローを表す基本的な変数•

𝑂𝐷交通量（ 𝑂𝐷 フロー）𝑄𝑟𝑠 𝑟𝑠 ∈ Ω•

経路交通量（経路フロー）

𝑓𝑘𝑟𝑠 𝑘 ∈ 𝐾𝑟𝑠 , 𝑟𝑠 ∈ Ω•

リンク交通量（リンクフロー）

𝑥𝑎 𝑎 ∈ 𝐴◆ フローの保存条件

1. 𝑥𝑎 =
2.

𝑟𝑠

𝑟𝑠 𝑟𝑠
𝑘 𝛿𝑎,𝑘 𝑓𝑘𝑟𝑠
𝑓𝑘 𝑘 = 𝑄𝑟𝑠

3. 𝑓𝑘𝑟𝑠 ≥ 0𝑎∈𝐴𝑟𝑠𝑂𝐷間のパス―リンクインシデンスマトリックスの 𝑎, 𝑘 要素𝑟𝑠 ∈ Ω

𝑂𝐷交通量の保存式

𝑘 ∈ 𝐾𝑟𝑠 , 𝑟𝑠 ∈ Ω

経路交通量についての非負条件

Fundamental Seminar 2018/05/31

第３章 ネットワークフローが満足すべき条件

2節 ネットワークフローの保存条件
1. 𝑥𝑎 =
2.

𝑟𝑠

𝑟𝑠 𝑟𝑠𝑘 𝛿𝑎,𝑘 𝑓𝑘𝑟𝑠𝑘 𝑓𝑘 = 𝑄𝑟𝑠

3. 𝑓𝑘𝑟𝑠 ≥ 025𝑎∈𝐴𝑟𝑠 ∈ Ω𝑘 ∈ 𝐾𝑟𝑠 , 𝑟𝑠 ∈ Ω

フローの保存条件は経路交通量𝑓𝑘𝑟𝑠 を変数としている⇒𝑓𝑘𝑟𝑠 が交通需要者の経路選択を直接的に表現することができるため

しかし実際の経路交通量は道路区間上では観測できないモデルによる推定結果の適合性• １式により交通量𝑥𝑎 を算出し，観測値と比較する
Fundamental Seminar 2018/05/31

ネットワークの作成について

26

R を活用したネットワークの作成

左にあるネットワークをR を活用して表現する

パッケージ“igraph”を使用

Fundamental Seminar 2018/05/31

ネットワークの作成について27

 コード#ネットワークの表現（可視化）#初回だけ，以下の行を実行してパッケージをインストールしてください
install.packages("igraph")#パッケージ
library(igraph)p<-as.matrix(read.csv("matrix.csv",header=F)) #隣接行列（matrix.csvの中身）の読み込み
g<-graph.adjacency(p,weighted=TRUE) #グラフオブジェクトの作成
V(g)$name<-c("1","2","3","4","5","6","7") #ノード番号
lay<-rbind(c(1,3),c(1,2),c(1,1),c(2,2),c(3,3),c(3,2),c(3,1)) #グラフレイアウト(座標の指定)#データ，レイアウト，ノードのラベル，点の大きさ，リンクのラベル
plot(g, layout=lay,vertex.label=V(g)$name,vertex.size=20,edge.label=E(g)$weight)

目的地ノード出発地ノー
ド00000002000000080000346001009004020000010
100
120
30

ノード２からノード３へのリンクコスト

Fundamental Seminar 2018/05/31

ネットワークの作成について
 結果

今回作成したネットワーク

Fundamental Seminar 2018/05/31

28

pythonにおけるネットワークの表現• pythonにはとても便利なNetworkXというパッケージが存在する。

• これを使うと様々なネットワークの表現が可能となる。
• まず、importする。(pyplotも)• とりあえず空のグラフを作る。

• ノードを追加する、そして描画する

Fundamental Seminar 2018/05/31

29

pythonにおけるネットワークの表現• 一度にたくさん追加もできる。

• ノードの名前を振ったりもできる••••

posは位置関係などをいじる項
plt.axis(‘off’)をしないと軸が表示される
色は頭文字で表せられるやつもある
ここからは魔法を使ってこれらをdrawで表す

Fundamental Seminar 2018/05/31

30

pythonにおけるネットワークの表現• ノードの追加は.add_edge• 同様に一度に追加もできる• 思った通りの配置にならないためposをいじる• posを円形のように配置するように設定する• いい感じになる

Fundamental Seminar 2018/05/31

31

pythonにおけるネットワークの表現• ノードの名前は文字列にもできる• こんなこともできる• 切羽詰まっているときにこれに20分かけた• 他にも隣接行列やcsvファイルからそのまま読み取る方法があるが、それは追って紹介する

Fundamental Seminar 2018/05/31

32

発展的内容 ラプラシアン行列とリンクの脆弱性

33

 通常のネットワークノード2に繋がるリンクの本数

ノード1とノード2を結ぶリンクが存在する

𝐿 =𝐷−𝐴
1 0 0 00= 0 3 0 0 − 10 0 2 000 0 0 201 −10 0= −1 3 −1 −10−1 2 −10−1 −1 2101101010110

𝐿：ラプラシアン行列

𝐷：次数行列
𝐴：隣接行列Fundamental Seminar 2018/05/31

発展的内容 ラプラシアン行列とリンクの脆弱性

34

 ネットワークに対応する一次元バネ・質点系• バネ・質点系の運動方程式𝑢1
1 −10 0𝑢𝑚 2 + 𝑘 −1 3 −1 −1𝑢30−1 2 −10−1 −1 2𝑢4𝑢10𝑢20=𝑢30𝑢40∵ 𝑢𝑖 = −𝜔2 𝑢𝑖
1 −10 0−1 3 −1 −10−1 2 −10−1 −1 2𝑢1𝑢2𝑚𝜔2𝑢3 = 𝑘𝑢4𝑘：バネ定数𝑚：質量𝑢𝑖 ：質点の変位

𝑢1𝑢2𝑢3𝑢4

Fundamental Seminar 2018/05/31

𝜔：角速度

発展的内容 ラプラシアン行列とリンクの脆弱性

35

 ノード固定条件付き一次元バネ・質点系＊ノード1が固定されているため𝑢1 = 0• バネ・質点系の運動方程式
𝑢11+𝑀
𝑢𝑚 2 + 𝑘 −1
𝑢300
𝑢4−10 03 −1 −1−1 2 −1−1 −1 2

𝑢10
𝑢20
=𝑢30
𝑢40

Fundamental Seminar 2018/05/31

𝑀：ペナルティー定数↓

十分に大きな正の数

発展的内容 ラプラシアン行列とリンクの脆弱性

36

固有値・固有ベクトルの算出
 ネットワークに対応する一次元バネ・質点系
𝜆3 + 𝜆2 − 2𝜆 = 0∴ 𝜆1 = −2,𝜆2 = 0,𝜆3 = 1＊ラプラシアン行列の固有値は必ず正となる → 第2最小固有値は1となる
0 −10 0−1 2 −1 −10−1 1 −10−1 −1 1𝑥1𝑥2𝑥3𝑥4=0∴ 0.82 , 0.2𝐸 −15 , −0.41 , −0.41

固有ベクトルで最大の成分は“0.82”⇒バネ張力の最大値はリンク（１，２）に生じるリンク（１，２）が脆弱性が高い
Fundamental Seminar 2018/05/31

発展的内容 ラプラシアン行列とリンクの脆弱性
 ノード固定条件付き一次元バネ・質点系＊中央集権的に物資や情報が伝達される状況
固有値
固有ベクトル𝜆 = 0.27
0 , −0.46 , −0.63 , −0.63

固有ベクトルで最大の成分は“0”⇒バネ張力の最大値はリンク（１，２）に生じるリンク（１，２）が脆弱性が高い
Fundamental Seminar 2018/05/31

37

参考文献

38

交通ネットワークの均衡分析 –最新の理論と解法–

積荷の均衡配分による海上貿易の港の混雑分析
http://www.ise.chuo-u.ac.jp/ise-labs/taguchi-lab/pdf/r01d8101025.pdf

小林俊一，中山昌一郎，松井千里，若林桂汰：道路ネットワークのラプラシアン行列による脆弱性解析，第55回土木計画学研究発表会・講演集

Fundamental Seminar 2018/05/31