第10回基礎ゼミ
Exercising UE with Python
平成30年6月1日（金）朝倉研究室 修士1年 小池卓武

利用者均衡配分とベクトル・リンクコスト関数

1

プログラミングに移る前に…

今までは..リンクコストはそのリンク交通量のみに依存すると仮定..

しかし…！！

𝑡𝑎 = 𝑡𝑎 𝑥𝑎

リンクコストは他のリンク交通量にも影響を受けるのでは？
(例えば交差点遅れ，バスと乗用車が混在する車線等..)

𝑡𝑎 = 𝑡𝑎 𝑥1 , … 𝑥𝑎 , … 𝑥𝐿 ∀a ∊ 𝐴↓一般化すると

𝒕 𝒙 : 𝑅+𝐿 → 𝑅+𝐿𝑅+𝐿 : 非負実数空間

上記のようなベクトル・リンクコスト関数(リンクコスト写像)を持つネットワーク上での利用者均衡を議論したい…！

利用者均衡配分とベクトル・リンクコスト関数2

リンクコストが複数の交通量に影響を受ける..
いきなり難しい…
→経路コストと経路交通量に限定して考えてみる．

①非線形相補性問題(𝑈𝐸/𝐹𝐷 − 𝑁𝐶𝑃)
利用者均衡条件
𝑓𝑘𝑟𝑠 ・ 𝐶𝑘𝑟𝑠 𝒇 − 𝑢𝑟𝑠 = 0𝐶𝑘𝑟𝑠 𝒇 − 𝑢𝑟𝑠 = 0 ↔ 𝑓𝑘𝑟𝑠 > 0𝐶𝑘𝑟𝑠 𝒇 − 𝑢𝑟𝑠 > 0 ↔ 𝑓𝑘𝑟𝑠 = 0フロー保存条件
𝑢𝑟𝑠 ・෍ 𝑓𝑘𝑟𝑠 − 𝑞𝑟𝑠 = 0𝑘∊𝐾𝑟𝑠

෍ 𝑓𝑘𝑟𝑠 − 𝑞𝑟𝑠 = 0 ↔ 𝑢𝑟𝑠 > 0𝑘 ∊ 𝐾𝑟𝑠 ∀rs ∊ 𝑊

𝐶𝑘𝑟𝑠 𝒇 − 𝑢𝑟𝑠 ≧ 0 𝑓𝑘𝑟𝑠 ≧ 0 (1)(1)(2)は相補性形式&変数 𝒇, 𝒖 の許容領域が非負実数空間𝑅+𝐾 × 𝑅+𝑀 (要は負にならない)𝑘∊𝐾𝑟𝑠

෍ 𝑓𝑘𝑟𝑠 − 𝑞𝑟𝑠 ≧ 0

෍ 𝑓𝑘𝑟𝑠 − 𝑞𝑟𝑠 > 0 ↔ 𝑢𝑟𝑠 = 0𝑘∊𝐾𝑟𝑠𝑘∊𝐾𝑟𝑠𝑢𝑟𝑠 ≧ 0 (2)(𝑈𝐸/𝐹𝐷 − 𝑁𝐶𝑃)
𝐹𝑖𝑛𝑑 𝑿 = 𝒇, 𝒖 ∊ 𝑅+𝐾 × 𝑅+𝑀𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 𝑿・F 𝐗 = 0, 𝑿 ≧ 0 F(𝑿) ≧ 0

利用者均衡配分とベクトル・リンクコスト関数②変分不等式問題(𝑈𝐸/𝐹𝐷 − 𝑉𝐼𝑃)
𝐹𝑖𝑛𝑑 𝒙 ∊ Ω 𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 F 𝒙 ・ 𝒚 − 𝒙 = 0, ∀𝒚 ∊ 𝛺Ω → 𝑅+𝑛 とすれば，
𝑉𝐼𝑃は𝑁𝐶𝑃と等価問題となる(𝑅+𝑛 ：非負実数空間)

𝑥2

𝐹(𝑿∗ ) Ω= 𝑅2+𝑿∗ 𝑥1
𝑿∗ − 𝐹(𝑿∗ )ベクトル場Fと凸集合Ωが直行する点を求める問題に同義(𝑉𝐼𝑃は𝑁𝐶𝑃を特殊ケースとして含んだ一般的枠組みと言える)(𝑈𝐸/𝐹𝐷 − 𝑉𝐼𝑃)
𝐹𝑖𝑛𝑑 𝑿∗ = 𝒇∗ , 𝒖∗ ∊ 𝑅+𝐾 × 𝑅+𝑀
𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 F(𝑿∗ )・(𝑿 − 𝑿∗ ) ≧ 0, ∀𝑿 ∊ Ω
詳しく書くと…
∗ )(𝑓 𝑟𝑠 − 𝑓 𝑟𝑠∗ ) + ෍(෍ 𝑓 𝑟𝑠∗ − 𝑞 )・(𝑢 − 𝑢 ∗ ) ≧ 0෍ ෍(𝐶𝑘𝑟𝑠 𝒇∗ − 𝑢𝑟𝑠𝑟𝑠𝑟𝑠𝑟𝑠𝑘𝑘𝑘𝑟𝑠 𝑘𝑟𝑠𝑘∀ 𝒇, 𝒖 ∊ 𝑅+𝐾 × 𝑅+𝑀3

利用者均衡配分とベクトル・リンクコスト関数

4③不動点問題(𝑈𝐸/𝐹𝐷 − 𝐹𝑃𝑃)
𝐹𝑖𝑛𝑑 𝒙 ∊ Ω

𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 𝒙 = 𝑃𝑟𝑜𝑗Ω,𝑄 (𝒙 − 𝑄−1 𝐹(𝒙))※𝑃𝑟𝑜𝑗Ω,𝑄 𝒙 = 𝑎𝑟𝑔. 𝑚𝑖𝑛𝑧 . 𝑧 − 𝑥 ・𝑄 𝑧 − 𝑥𝑠. 𝑡 . 𝑧 ∊ Ω𝑥2→凸集合Ω上への𝒙の正射影

𝐹𝑃𝑃(𝐹, Ω)と𝐹(𝑿)がΩに直交している点を求める問題であり，𝑉𝐼𝑃(𝐹, Ω)と等価である．
𝑃𝑟𝑜𝑗Ω 𝑿 − 𝐹(𝑿

利用者均衡問題は集合𝛺が非負実数空間𝑅+𝐾 × 𝑅+𝑀 なので集合Ωへの射影は，以下のような演算子に帰着する
𝑃𝑟𝑜𝑗𝑅+𝐾 ×𝑅+𝑀,𝑄 𝒙 − 𝐹 𝒙= [𝒙 − 𝑄−1 𝐹(𝒙)](𝑈𝐸/𝐹𝐷 − 𝐹𝑃𝑃)
𝐹𝑖𝑛𝑑𝑿 = 𝒇, 𝒖 ∊ 𝑅+𝐾 × 𝑅+𝑀
𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 𝑿 = [𝑿 − 𝑄 −1 𝐹(𝑿)]

𝐹(𝑿)𝐹(𝑿∗ )𝑿𝑿∗
𝑥1

𝑿 − 𝐹(𝑿) 𝑿∗ − 𝐹(𝑿∗ )例えば非負実数空間Ω= 𝑅+2
においてVIPと𝐹𝑃𝑃は等価リンク間相互干渉のある利用者均衡問題

5

不等変分式問題(VIP)としての表現方法
𝒇および𝒇∗ がフロー保存条件と非負条件を満たした凸領域Ω𝑝0 に属するとする

෍ 𝑓𝑘𝑟𝑠 − 𝑞𝑟𝑠 = 0 ∀rs ∊ 𝑊𝑘∊𝐾𝑟𝑠
𝑓𝑘𝑟𝑠 > 0𝑘 ∊ 𝐾𝑟𝑠 ∀rs ∊ 𝑊

𝑈𝐸/𝐹𝐷 − 𝑉𝐼𝑃より，下記の𝑉𝐼𝑃式の第２項が消去され，0∗ )(𝑓 𝑟𝑠 − 𝑓 𝑟𝑠∗ ) + ෍(෍ 𝑓 𝑟𝑠∗ − 𝑞 )・ 𝑢 − 𝑢 ∗෍ ෍(𝐶𝑘𝑟𝑠 𝒇∗ − 𝑢𝑟𝑠
𝑟𝑠𝑟𝑠𝑟𝑠 ≧ 0𝑘𝑘𝑘𝑟𝑠𝑘𝑟𝑠𝑘∗ 𝑓 𝑟𝑠 − 𝑓 𝑟𝑠∗ = ෍ 𝑢 (𝑞 − 𝑞 ) = 0
෍ ෍ 𝑢𝑟𝑠
𝑟𝑠 𝑟𝑠
𝑟𝑠𝑘𝑘
𝑟𝑠𝑘𝑟𝑠

したがって，経路交通量パターン𝑓𝑘𝑟𝑠∗ が𝑈𝐸/𝐹𝐷 − 𝑉𝐼𝑃の解ならば下記が成立
෍ ෍ 𝐶𝑘𝑟𝑠 𝒇∗ (𝑓𝑘𝑟𝑠 − 𝑓𝑘𝑟𝑠∗ ) ≧ 0
𝑟𝑠𝑘𝒇, 𝒇∗ ∊ Ω𝑝0𝒇∗ がこの式の解ならば𝒇∗ は利用者均衡解！

リンク間相互干渉のある利用者均衡問題

6

ここで，𝒇∗ が利用者均衡解ではないと仮定してみると..
𝑓𝑘𝑟𝑠∗ > 0, 𝐶𝑘𝑟𝑠 𝒇∗ > 𝐶𝑙𝑟𝑠 𝒇∗となる経路k, 𝑙が存在する．経路kの交通量を経路𝑙に移すと，コストは𝐶𝑘𝑟𝑠 𝒇∗ − 𝐶𝑙𝑟𝑠 𝒇∗ > 0だけ小さくなり，下記の式が成り立つ．
෍ ෍ 𝐶𝑘𝑟𝑠 𝒇∗ ・𝑓𝑘𝑟𝑠∗ < ෍ ෍ 𝐶𝑘𝑟𝑠 𝒇∗ 𝑓𝑘𝑟𝑠∗
𝑟𝑠𝑘𝑟𝑠𝑘∗ )(𝑓 𝑟𝑠 − 𝑓 𝑟𝑠∗ ) ≧ 0が成立しないため，↑ σ𝑟𝑠 σ𝑘(𝐶𝑘𝑟𝑠 𝒇∗ − 𝑢𝑟𝑠𝑘𝑘
利用者均衡配分問題は変分不等式問題𝑉𝐼𝑃(𝑐, Ω𝑝0 )と等価できる．

リンク間相互干渉のある利用者均衡問題
経路コストからリンクコストへの適用例
𝐶𝑘𝑟𝑠 = ෍ 𝑡𝑎 δ𝑟𝑠𝑎,𝑘𝑎∊𝐴

経路コストがリンクコストと加算的関係の時，ネットワーク総所要費用は全経路についての足し合わせなので෍ ෍ 𝐶𝑘𝑟𝑠 𝒇 ・𝑓𝑘𝑟𝑠 = ෍ 𝑡𝑎 (𝑥)・𝑥𝑎
𝑟𝑠𝑘𝑎∊𝐴

この関係を変分不等式問題𝑉𝐼𝑃(𝑐, Ω𝑝0 )に適応すれば，以下の𝑉𝐼𝑃が得られる．

(𝑈𝐸/𝐹𝐷 − 𝑉𝐼 −𝑃𝑟𝑖𝑚𝑖𝑛𝑎𝑙)
𝐹𝑖𝑛𝑑 𝒙∗ 𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 ෍ 𝑡𝑎 𝒙∗ ・(𝑥𝑎 −𝑥𝑎∗ ) ≧ 0𝑎∊𝐴𝒙 ∊ Ω𝑝※Ω𝑝 は経路コストとリンクコストの関係式，フロー保存条件，非負条件を満足したリンク交通量ベクトルの集合

7ここからが確定的UEのプログラミングになります！
Jupyter notebook を起動してください！
(※先ほどまでのベクトル・リンクコストではなく，今回はノーマルなリンクコストでコードを作っています)使用データの概要

8

ネットワークデータは𝑐𝑠𝑣ファイルとして配布
1254

入ノード 出ノード

6

交通容量𝐶𝑎𝑝𝑎
37

形状パラメータα, β

自由走行時間𝑡𝑎0↓BPR関数の定数として用いられる
𝑥𝑎 β0𝑡𝑎 𝑥𝑎 = 𝑡𝑎 1 + α()
𝐶𝑎𝑝𝑎※入ノード，出ノードはODではなくリンクの入口，出口の意味！

使用データの概要

出発地

9

目的地 𝑂𝐷交通量← 𝑂𝐷データも𝐶𝑆𝑉ファイルとして配布
1235467

UEコード10
コードで用いるモジュールを事前にインポート
𝑐𝑠𝑣 ： 𝑐𝑠𝑣ファイルの読み書きに必要
𝑐𝑜𝑝𝑦 ：データをコピーする関数を内蔵
𝑛𝑒𝑡𝑤𝑜𝑟𝑘𝑥 ：ネットワークを扱う際に便利

𝑐𝑠𝑣ファイル(ネットワークデータ， 𝑂𝐷データ)を読み込む関数

𝑈𝐸の配分結果をファイルに出力する関数
𝑑𝑒𝑓 ␣関数名(引数):自身で関数を定義！

算術式(引数)は()でも実行可能..関数のタイプによる．

𝑟𝑒𝑡𝑢𝑟𝑛 ␣返り値

多くの関数は𝑟𝑒𝑡𝑢𝑟𝑛で目的関数値を返す．

UEコード

11
UEの配分結果の出力先を設定．
各リンクを構成する入ノード𝑥 0 ,出ノード𝑥[1]を設定！
ネットワークデータから𝑛𝑒𝑡𝑤𝑜𝑟𝑘𝑥モジュールを用いてネットワークを作成！

今回はこっち！

. 𝐷𝑖𝐺𝑟𝑎𝑝ℎ ：有向リンク(行ったり来たり..向きのあるリンク). 𝐺𝑟𝑎𝑝ℎ ：無向リンク

UEコード12

ダイクストラ法で最短経路探索！
𝑛𝑒𝑡𝑤𝑜𝑟𝑘𝑥モジュールにはダイクストラ法を実行する関数(. 𝑑𝑖𝑗𝑘𝑠𝑡𝑟𝑎_𝑝𝑎𝑡ℎ)が内蔵されている

最短経路に𝐴𝑙𝑙 𝑜𝑟 𝑁𝑜𝑡ℎ𝑖𝑛𝑔配分を実行し，各リンクの交通量𝑥𝑎 を算出！
→リンクコスト(所要時間)の更新に用いる
𝑡𝑎 𝑥𝑎= 𝑡𝑎0𝑥𝑎 β
1 + α()
𝐶𝑎𝑝𝑎

毎度おなじみ𝐵𝑃𝑅

UEコード13𝐴𝑙𝑙 𝑜𝑟 𝑁𝑜𝑡ℎ𝑖𝑛𝑔配分の結果を用いてリンクコストを更新する関数

所要時間最小化問題を解く際に用いる
探索方向ベクトル𝑑𝑎𝑛 を算出
𝑑𝑎𝑛 = 𝑦𝑎𝑛 − 𝑥𝑎𝑛𝑦𝑎𝑛 はリンクコスト更新後のリンクaの交通量
𝑥𝑎𝑛 はリンクコスト更新前のリンクaの交通量
𝑛は繰り返し計算回数の添え字(𝑛ループ目)

UEコード14

下式の最適化問題を満足するようなステップ幅ξ𝑛 (読みはクサイ，グザイ)を直線探索により求める！
𝑛+1 =𝑥 𝑛 +ξ𝑛 𝑑 𝑛𝑥𝑎𝑎𝑎𝑚𝑖𝑛𝑍 𝑥 = 𝑚𝑖𝑛 ෍ 𝑡𝑎 𝑥𝑎 = 𝑚𝑖𝑛 ෍ න𝑎𝑎0𝑡𝑎 𝑤 𝑑𝑤

UEコード15下式のようにリンク交通量を更新
𝑥𝑎𝑛+1 = 𝑥𝑎𝑛 + ξ𝑛 𝑑𝑎𝑛※𝑥𝑎𝑛+1 − 𝑥𝑎𝑛 < εとなるまで(繰り返し計算前後で交通量の差がεより小さくなるまで繰り返し計算)
なお，εは自身で設定する収束判定値
ε小さい=判定厳しい↔収束しにくいUEコード16
事前に作った関数を組み合わせてに𝑈𝐸を実行する関数を作成
ネットワーク内のリンクデータ&に𝑂𝐷データ作成
ノードを繋いでネットワークに配分結果の出力先を作成
𝐴𝑂𝑁配分&配分結果𝑥𝑎𝑛 よりリンクコストを更新更新したコストをネットワークに反映
補助解𝑦𝑎𝑛 を算出
降下方向ベクトル，ステップ幅を算出
リンク交通量を更新→𝑥𝑎𝑛+1
収束？Yes→結果を出力，No→コスト更新へ戻る(にするとノートブック上に出力)

UEコード17
総所要時間を計算！
リンク情報の取得(入出ノード，交通容量，自由走行時間，形状パラメータ)

𝑈𝐸を実行

𝑈𝐸の結果からリンク交通量𝑥𝑎 を得る
リンク交通量𝑥𝑎 をBPR関数に入力し，リンクコスト𝑡𝑎(リンク所要時間)を得る
リンクコスト𝑡𝑎 を合計し，総所要時間を得る

演習課題118

𝐶𝑆𝑉ファイルを操作してネットワーク構造を変更してみよう！
1

23

45

162

735

4

6

7

𝑈𝐸を実行し，リンク交通量の変化を見てみよう！

演習課題219

𝐶𝑆𝑉ファイルを操作して𝑂𝐷交通量， 𝑂𝐷パターンを変更してみよう！
↑例えば×OD_𝑣𝑜𝑙100倍とか，1→6のODを追加してみるとか..

出発地

目的地 𝑂𝐷交通量？
𝑈𝐸を実行し，収束までの時間の違いを体感しよう！

演習課題320

スーフォールズネットワークを𝑈𝐸に適応してみよう！
アメリカ，サウスダコタ州のとある町のネットワーク．交通量配分のベンチマークとして広く用いられる．

𝑆𝑖𝑜𝑢𝑥𝐹𝑎𝑙𝑙𝑠_𝑛𝑒𝑡𝑤𝑜𝑟𝑘.𝑐𝑠𝑣
𝑆𝑖𝑜𝑢𝑥𝐹𝑎𝑙𝑙𝑠_𝑜𝑑.𝑐𝑠𝑣※𝑈𝐸の収束に時間がかかるので実行は各自に任せます！

参考文献
参考文献：

1)土木学会：交通ネットワークの均衡分析-最新の理論と解法2) 小池卓武，柳沼秀樹：道路階層化を念頭に置いたネットワーク設計モデルの構築
3) SiouxFalls Network：https://github.com/bstabler/TransportationNetworks/tree/master/SiouxFalls

21