2017/6/15

交通ネットワーク分析ゼミ第2回②・第8章 利用者均衡モデルの解法

朝倉研B4 小泉大哉

目次• 最短経路探索モデル
Dijkstra法(ダイクストラ法、ラベル確定法)
ラベル修正法
効率的な最短経路探索のためのデータ構造

割愛• 利用者均衡モデルの解法

Frank-Wolfe法
リンク容量制約を持つ場合のFrank-Wolfe法• 利用者均衡配分のより効率的な解法
打ち切り二次計画法
Simplicial Decomposition法• リンク間に相互干渉のある利用者均衡配分の解法
緩和法(非線型対角化法)
射影法(線形近似法)
Gap関数を利用した解法

2

交通ネットワーク分析ゼミ

第2回②

all-or-nothing配分
概要：最小交通費用を持つ経路へすべての需要を配分するもの。
以下のステップを通じて配分する。

• ステップ1：交通が発生するすべての起点に対して最短経路探索を行い、各ノードiに対する先行ポインタ𝐹𝑖 を求める。

• ステップ2：各ODペアrs間において、最短経路上のリンクを𝐹𝑖 を利用しながら列挙すると同時に、OD交通量𝑄𝑟𝑠 を列挙されたリンクに負荷していく• ステップ3：全ODペア間のOD交通量を最短経路上のすべてのリンクに負荷する→終了
3

交通ネットワーク分析ゼミ

第2回②

最適経路探索モデル-効率的な最短経路探索のためのデータ構造• forward star形式のデータ構造
１５
9

各リンクのデータを1行ごとに並べた上で、データを呼び出すための配列表を作成する。

4214２6３６４8

1 2233 1

７1
B(i)：ノードに繋がるリンクの終点ノード→リンクナンバー

4

交通ネットワーク分析ゼミ

第2回②

利用者均衡モデルの解法＜利用者均衡状態とは＞• 交通利用者は、経路に関する情報を完全に得ている• 交通利用者は、最短経路を選択する
上記2つの前提のもとで、各交通利用者が行動した結果生じる状態のこと。

• 利用者均衡状態となるような交通量配分方法を、利用者均衡配分という。

5

交通ネットワーク分析ゼミ

第2回②

利用者均衡モデルの解法• Wardropの第一原則(利用者均衡)「起終点間に存在する経路のうち、利用される経路の所要時間は皆等しく、利用されない経路の所要時間よりも小さいか、せいぜい等しい。」• Wardropの第二原則(システム最適)「交通ネットワーク上の総旅行時間(交通量×時間)が最小となる。」

6

交通ネットワーク分析ゼミ

第2回②

利用者均衡モデルの解法• 非線形最適化問題の解法→変数が少なければクーン・タッカー条件でOK→しかし、変数の数が膨大になると面倒• 考えるべきことは2つ①：最適化へ向かう降下方向ベクトルの識別②：①で求めた方向に、どれだけ進むか？

7

交通ネットワーク分析ゼミ

第2回②

利用者均衡モデルの解法
目的関数曲面𝛧 𝑥①：最適化へ向かう方向ベクトルの識別𝑥 (𝑛) ： 𝑛回計算後のリンク交通量ベクトル𝒅 = 𝑦 − 𝒙(𝒏)← 𝑦をどう置くか？

②：①で求めた方向に、どれだけ進むか？
𝛼：降下距離を表す1次パラメータ0≤𝛼≤1𝑥1𝑥平面
𝑑𝑥2𝒙(𝒏+𝟏) = 𝒙(𝒏) + 𝛼 𝑦 − 𝒙(𝒏)目的関数𝜡 𝒙(𝒏+𝟏)を最小にするもの： 最小点𝒙(𝒏+𝒎)： 降下方向ベクトル𝑑 = 𝑦 − 𝑥 𝑛： 制約条件8

交通ネットワーク分析ゼミ

第2回②最適経路探索モデル-Frank-Wolfe法• 計算プログラムの作成が非常に簡単で、利用者均衡モデルのアルゴリズムとして広く用いられている• リンク交通量ベクトルをベースとして最適解を探索するため、(列挙された)記憶容量が少なくてすむ• 収束が進むにつれて収束スピードが遅くなることが知られている

9

交通ネットワーク分析ゼミ

第2回②

最適経路探索モデル-効率的な最短経路探索のためのデータ構造• 最小ラベルの探索におけるヒープ構造
根以外の各ノードgに対して、(gの親ノードのラベル)≦(gのラベル)※ 2 をノードの根とする

10

交通ネットワーク分析ゼミ

第2回②

最適経路探索モデル-効率的な最短経路探索のためのデータ構造• 最小ラベルの探索におけるヒープ構造
根以外の各ノードgに対して、(gの親ノードのラベル)≦(gのラベル)ex) 配列順位14(配列順位7の下)に、ラベル 3 を置くことを考える

311

交通ネットワーク分析ゼミ

第2回②

最適経路探索モデル-効率的な最短経路探索のためのデータ構造• 最小ラベルの探索におけるヒープ構造
根以外の各ノードgに対して、(gの親ノードのラベル)≦(gのラベル)ex) 配列順位14(配列順位7の下)に、ラベル 3 を置くことを考える

親ノード11と3を交替させる

親ノード10と3を交替させる

312

交通ネットワーク分析ゼミ

第2回②

最適経路探索モデル-Frank-Wolfe法• ①最適化へ向かう方向ベクトルの識別→計算された𝒙𝒏 に対して適切な𝑦(補助ベクトル)を探す→目的関数を𝑦について線形近似する

𝑍𝑝 𝒚 ≈ 𝑍𝑝 𝒙𝑛 + 𝒅 = 𝑍𝑝 𝒙𝑛 + 𝛁𝑍𝑝 𝒙𝑛 𝑇 𝒚 − 𝒙𝑛
= 𝑍𝑝 𝒙𝑛 + 𝒂∈𝑨 𝒚 − 𝒙𝑛 𝜕𝑍𝑝 𝒙𝑛 𝜕𝑥𝑎 𝑛= 𝑍𝑝 𝒙𝑛 + 𝒂∈𝑨 𝒚 − 𝒙𝑛 𝑡𝑎 𝑥𝑎 𝑛
= 𝑍𝑝 𝒙𝑛 − 𝒂∈𝑨 𝑥𝑎 𝑛 𝑡𝑎 𝑥𝑎 𝑛 + 𝒂∈𝑨 𝑦𝒂 𝑡𝑎 𝑥𝑎 𝑛定数項(計測可能)変数項(𝑦𝒂 未知)

𝑡𝑎 ･･･リンクaのリンクコスト関数
𝑥𝑎 ･･･リンクaの交通量13交通ネットワーク分析ゼミ

第2回②

最適経路探索モデル-Frank-Wolfe法• ①最適化へ向かう方向ベクトルの識別
前式より、𝑚𝑖𝑛. 𝑍𝑝 𝒚 =𝒂∈𝑨 𝑦𝒂 𝑡𝑎 𝑥𝑎

Subject to𝑟𝑠𝑘 𝑓𝑘 − 𝑄𝑟𝑠 = 0𝑛∀𝑟𝑠 ∈ Ω𝑦𝑎 =𝑘𝑟𝑠 𝑟𝑠
𝑟𝑠 𝛿𝑎,𝑘 𝑓𝑘∀𝑎 ∈ 𝐴という補助問題を得る。
ここで上式は、 𝑡𝑎 𝑥𝑎𝑛 の下で総走行時間を最小にする𝑦を求めることである。 𝑡𝑎 𝑥𝑎𝑛 は定数であるから、 𝑡𝑎 𝑥𝑎𝑛 のリンク所要時間で求められる最短経路にすべてのOD交通量を流すというall-or-nothing配分をすれば、𝑍𝑝 𝒚 を最小にするような𝑦が得られる。

最小交通費用をもつ経路へすべての需要を配分するもの14

交通ネットワーク分析ゼミ

第2回②

最適経路探索モデル-Frank-Wolfe法• ①最適化へ向かう方向ベクトルの識別
𝑍𝑝 𝒚 ≈ 𝑍𝑝 𝒙𝑛 + 𝒅 = 𝑍𝑝 𝒙𝑛 + 𝛁𝑍𝑝 𝒙𝑛 𝑇 𝒚 − 𝒙𝑛 が最小→𝛁𝑍𝑝 𝒙𝑛 𝑇 𝒚 − 𝒙𝑛 が最も小さい負の値を与える→𝒅 = 𝒚 − 𝒙𝑛 は目的関数𝑍𝑝 の点𝑥 𝑛 におけるもっとも急な下り勾配に沿った方向ベクトルである

𝒅 = 𝒚 − 𝒙𝑛 を最小化へ向かう降下方向ベクトルとして利用

15

交通ネットワーク分析ゼミ

第2回②

最適経路探索モデル-Frank-Wolfe法• ②：①で求めた方向に、どれだけ進むか？
降下方向ベクトルが与えられた後は、𝒙(𝒏+𝟏) = 𝒙(𝒏) + 𝛼 𝑦 − 𝒙 𝒏⇔ 𝒙(𝒏+𝟏) = 𝛼𝑦 + 1 − 𝛼 𝒙𝒏

なる𝒙(𝒏+𝟏) を𝑍𝑝 に代入し、𝛼による一次元最適化を行う(𝛼による一次方程式を解く)ことによって、次の施行点𝒙(𝒏+𝟏) を求める。その点に対しても新たな𝑦, 𝑑が求まり…という作業を、収束判定を満たすまで繰り返し行う。
（n=1では、𝑡𝑎 0 の状態でのall-or-nothing配分を𝒙(𝒏+𝟏) とする)

16

交通ネットワーク分析ゼミ

第2回②

最適経路探索モデル-リンク容量制約を持つ場合のFlank-Wolfe法
𝒙𝒂 ≤ 𝑪𝒂 （𝑪𝒂 : 交通容量)∀𝑎 ∈ 𝐴 を定める

Flank-Wolfe法はリンクコストが無限大に向かうため、計算量が膨大である。ここで、ステップサイズ𝛼を以下のように制約すればよい。
𝛼 ≤ 𝛼𝑚𝑎𝑥 = min𝑥𝑎 <𝑦𝑎𝐶𝑎 − 𝑥𝑎 𝑛𝑦𝑎 − 𝑥𝑎 𝑛

17

交通ネットワーク分析ゼミ

第2回②

最適経路選択モデル-利用者均衡配分のより効率的な解法• 打ち切り二次計画法• Simplicial Decomposition法

Flank-Wolfe法の欠点を改善した様々な効率的解法について述べる• Flank-Wolfe法には、解の近傍に近づいているものの、収束までに極めて多数の繰り返し計算回数を要するという欠点がある→探索方向ベクトル 𝑦 − 𝑥 𝑛 が、解の近傍では目的関数の勾配方向とほぼ垂直な方向となってしまう

𝑍𝑝 を二次近似して得られる補助問題を立て、解く際はコストが増えないよう厳密には解かないようにする
18

交通ネットワーク分析ゼミ

第2回②

最適経路選択モデル-利用者均衡配分のより効率的な解法
Flank-Wolfe法の欠点を改善した様々な効率的解法について述べる• 打ち切り二次計画法• Simplicial Decomposition法• 以下の補助問題を解く
min 𝑍(𝒚) = 𝛻𝑍(𝒙(𝑛) )𝑇 𝒚 − 𝒙(𝑛) + 12 𝒚 − 𝒙(𝑛)𝑦𝑇 2
𝛻 𝑍(𝒙(𝑛) )𝒚 − 𝒙(𝑛)Subject to𝑟𝑠 𝑟𝑠
𝛿𝑎,𝑘𝑓𝑘𝑦𝑎 =𝑘𝑟𝑠

𝑔𝑘 𝑟𝑠 − 𝑞𝑛 = 0∀𝑎 ∈ 𝐴𝑔𝑘𝑛 ≥ 0∀𝑘 ∈ 𝐾𝑛 ,∀𝑟𝑠 ∈ 𝑊𝑘∈𝐾𝑛∀𝑟𝑠 ∈ 𝑊19

交通ネットワーク分析ゼミ

第2回②

最適経路選択モデル-利用者均衡配分のより効率的な解法
Flank-Wolfe法の欠点を改善した様々な効率的解法について述べる• 打ち切り二次計画法• Simplicial Decomposition法

𝑍𝑝 を二次近似して得られる補助問題を立て、解く際はコストが増えないよう厳密には解かないようにする• 代わりに以下の補助問題を解く
𝑡𝑎 𝑥𝑎𝑛min 𝑍𝑄𝑃 (𝒚) =𝑦𝑚𝑎 𝑥𝑎𝑛∙ 𝒚 − 𝒙(𝑛) + 12𝑎∈𝐴

Subject to𝑘𝑟𝑠2𝑎∈𝐴𝑟𝑠 𝑟𝑠
𝛿𝑎,𝑘𝑓𝑘𝑦𝑎 =∙ 𝒚 − 𝒙(𝑛)𝑔𝑘 𝑟𝑠 − 𝑞𝑛 = 0∀𝑎 ∈ 𝐴𝑔𝑘𝑛 ≥ 0∀𝑘 ∈ 𝐾𝑛 ,∀𝑟𝑠 ∈ 𝑊𝑘∈𝐾𝑛∀𝑟𝑠 ∈ 𝑊

初めは𝑚 = 0, 𝒚 0 = 𝒙 𝑛とする

20

交通ネットワーク分析ゼミ

第2回②

最適経路選択モデル-利用者均衡配分のより効率的な解法
Flank-Wolfe法の欠点を改善した様々な効率的解法について述べる• 打ち切り二次計画法• Simplicial Decomposition法• リンクコスト関数はリンク毎に分離可能
𝛻𝑍 𝑥 𝑛=𝑛… , 𝑡𝑎 𝑥𝑎,…

𝑇

• Hessian行列は、初めは𝑚 = 0, 𝒚 0 = 𝒙 𝑛とする

21

交通ネットワーク分析ゼミ

第2回②

最適経路選択モデル-利用者均衡配分のより効率的な解法• 打ち切り二次計画法• Simplicial Decomposition法

Flank-Wolfe法の欠点を改善した様々な効率的解法について述べる• 重み係数𝜆を未知変数として、許容領域内で解く方法• all-or-nothing配分パターンが𝑒𝑖 が所与であれば、需要固定型利用者均衡配分は、𝜆の最適化問題として表現できる

𝑚𝑖𝑛.𝜆 𝜡 𝑥

subject to 𝑥 =𝑀𝑖=1 𝜆𝑖 𝒆𝑖 ,𝑀𝑖=1 𝜆𝑖 = 1 ,𝜆𝑖 ≥ 0(𝑖 = 1,2, … , 𝑀)22

交通ネットワーク分析ゼミ

第2回②

最適経路選択モデル-利用者均衡配分のより効率的な解法• 打ち切り二次計画法• Simplicial Decomposition法

Flank-Wolfe法の欠点を改善した様々な効率的解法について述べる• 重み係数𝜆を未知変数として、許容領域内で解く方法• all-or-nothing配分パターンが𝑒𝑖 が所与であれば、需要固定型利用者均衡配分は、𝜆の最適化問題として表現できる列生成フェイズ

最適解の表現に用いられる可能性の高い端点を逐次生成
それまでに得られている端点の集合に新たな端点を追加する

限定親問題フェイズ

部分的な端点凸集合内の𝑒𝑖 凸結合により、𝜆に関する最適化問題を解く
重みが小さい最適な配分パターンを残しておく23

交通ネットワーク分析ゼミ

第2回②

最適経路選択モデル-利用者均衡配分のより効率的な解法
Flank-Wolfe法の欠点を改善した様々な効率的解法について述べる• 打ち切り二次計画法• Simplicial Decomposition法

具体的な手法(RSD法を例に)
𝑚min.
𝑡𝑎 𝑥𝑎
初期設定𝑦𝑦𝑎𝑠. 𝑡. 𝑦 ∈ Ω𝑃 (𝑎∈𝐴

フロー保存条件を満たしたリンク交通量パターン)〈端点生成削除フェイズ〉

最短経路配分問題を解く
𝒕 𝒙𝑚𝒕 𝒙𝑚

∙ 𝒚−𝒙 𝒎∙ 𝒚−𝒙 𝒎<0≥0
𝑬 𝒎 < 𝑀に含まれる端点の個数が𝑀未満

NoYes
均衡解：𝒙 𝒎

𝑬 𝒎＋1

≔𝑬𝒎

∪ 𝒚,𝐹 𝑚+1 ≔ 𝐹 𝑚

𝐹 𝑚+1 ≔ 𝒙 𝑚
𝑬 𝒎＋1 ≔ 𝑬 𝒎 ∪ 𝑭 𝒎+𝟏
24〈限定親問題フェイズ〉へ

交通ネットワーク分析ゼミ

第2回②

最適経路選択モデル-リンク間に相互干渉のある利用者均衡配分の解法• いずれも5.5節で紹介した変分方程式の解法を応用する• 打ち切り二次計画法• Simplicial Decomposition法

min. 𝜆 Z 𝒙 𝑚+1𝑦

𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑥 𝑚+1 =𝑀
𝑖=1 𝜆𝑖 𝒆𝑖 ,𝑀
𝑖=1 𝜆𝑖 = 1, 𝜆1 ≧ 0※𝑀は𝐸 𝑚+1 の要素数

〈限定親問題フェイズ〉

需要固定型利用者均衡配分におけるリンク交通量配分パターン
𝑥 𝑚+1 を𝑒𝑖 ∈ 𝐸 𝑚+1 の凸集合により表現した以下の咲いてか問
題を𝜆について解く

𝜆𝑖 = 0となっているすべての𝒆𝑖 を
𝐸 𝑚+1 及び𝐹 𝑚+1 から削除

𝑚 = 𝑚 + 1として〈端点生成削除フェイズ〉へ

25

交通ネットワーク分析ゼミ

第2回②

最適経路選択モデル-リンク間に相互干渉のある利用者均衡配分の解法①緩和法(非線型対角化法)②射影法(線形近似法)③Gap関数を利用した解法•

いずれも変分不等式問題を応用している
凸集合Ωと写像F:Ω→Ωを所与とするとき以下のように定義される問題のことをいう

𝐹𝑖𝑛𝑑 𝒙 ∈ Ω

𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 𝑭(𝒙) ∙ 𝒚 − 𝒙 ≥ 𝟎26

交通ネットワーク分析ゼミ

第2回②

最適経路選択モデル-リンク間に相互干渉のある利用者均衡配分の解法①緩和法(非線型対角化法)•②射影法(線形近似法)③Gap関数を利用した解法

各繰返し計算において、リンクコスト写像𝒕 𝒙 の相互干渉のある部分を固定して得られる「緩和問題」を解くことにより繰り返すアルゴリズム•

リンクコスト関数𝑡 𝑥 の相互干渉のある部分を固定して得られる緩和問題を解くことを繰り返す•

m回目繰返しにおけるリンク交通量パターン𝒙 𝑚 が既知の場合、以下のような近似リンクコスト写像として考える：

𝑡𝑎 𝒙, 𝒙 𝑚•

𝑚= 𝑡𝑎 𝑥1𝑚, … , 𝑥𝑎 , … , 𝑥𝐿∀𝑎 ∈ 𝐴

以下のようなリンク間に相互干渉のないコスト関数のもとでの利用者均衡配分と見なすことができる

𝑚𝑖𝑛. 𝑍 𝒙 =𝑥𝑎𝑎 0 𝑡𝑎𝑚𝑥1𝑚, … , 𝑥𝑎 , … , 𝑥𝐿

= 𝑡𝑎 𝒙∗subject to 𝑥 ∈ Ω𝑃27

交通ネットワーク分析ゼミ

第2回②

最適経路選択モデル-リンク間に相互干渉のある利用者均衡配分の解法①緩和法(非線型対角化法)②射影法(線形近似法)③Gap関数を利用した解法••

各繰返し計算において、リンクコスト写像𝒕 𝒙 の相互干渉のある部分を固定して得られる「緩和問題」を解くことにより繰り返すアルゴリズム

具体的な解法

Step0(初期許容解を求める) 繰返し回数 𝑚: = 1;初期許容解(リンク交通量パターン)𝑥 1 を想定

Step1(緩和問題を解く) Frank-Wolfe法のアルゴリズムで解き、その解を𝑥 𝑚+1 とする
Step2(収束判定) 𝒙 𝑚+1 − 𝒙 𝑚•≤ 𝜀なら終了、そうでなければ𝑚 = 𝑚 + 1とし、Step1へ繰返し計算を4回未満で打ち切るなど、計算効率を良くするためのアルゴリズムが提案されている

28

交通ネットワーク分析ゼミ

第2回②

最適経路選択モデル-リンク間に相互干渉のある利用者均衡配分の解法• ①緩和法(非線型対角化法)
打ち切り二次計画法• ②射影法(線形近似法)
Simplicial Decomposition法•

もとのリンクコスト写像を線形近似して得られる補助的な変分不等式問題を解くことを繰り返すアルゴリズム③Gap関数を利用した解法•m回目繰返しにおけるリンク交通量パターン𝒙 𝑚 が既知の場合、以下のような近似リンクコスト写像として考える：

𝑡 𝒙 =𝒕 𝒙𝑚

1+ 𝑄 𝒙−𝒙 𝑚𝜌

Q:適当な正定値行列,
𝜌:十分小さな正値のパラメータ••

近似的なリンクコスト写像による以下の補助的な変分方程式を繰りかえす

𝐹𝑖𝑛𝑑 𝑥 ∗ ∈ Ω𝑃

𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 𝒕 𝒙 ∙ 𝒙 − 𝒙∗ ≥ 𝟎５章の射影の概念より、

subject to 𝑥 ∈ Ω𝑃𝑥 ∗ = 𝑃𝑟𝑜𝑗Ω,𝑄 𝒙 𝑚 − 𝜌𝑄 −1 𝒕 𝒙 𝑚29

交通ネットワーク分析ゼミ

第2回②

最適経路選択モデル-リンク間に相互干渉のある利用者均衡配分の解法• ①緩和法(非線型対角化法)
打ち切り二次計画法• ②射影法(線形近似法)
Simplicial Decomposition法•

もとのリンクコスト写像を線形近似して得られる補助的な変分不等式問題を解くことを繰り返すアルゴリズム③Gap関数を利用した解法•

具体的な解法

Step0(初期許容解を求める) 繰返し回数 𝑚: = 1;定数𝜌, 𝑄, 初期許容解(リンク交通量パターン)𝑥 1を想定
Step1(緩和問題を解く) Frank-Wolfe法のアルゴリズムで解き、その解を𝑥 𝑚+1 とする
Step2(収束判定) 𝒙 𝑚+1 − 𝒙 𝑚•≤ 𝜀なら終了、そうでなければ𝑚 = 𝑚 + 1とし、Step1へアルゴリズムが大域的に収束するための十分条件は𝜌が十分に小さく設定されて、なおかつ均衡解への収束が保証される

30

交通ネットワーク分析ゼミ

第2回②

最適経路選択モデル-リンク間に相互干渉のある利用者均衡配分の解法•••①緩和法(非線型対角化法)
打ち切り二次計画法

Simplicial Decomposition法

ここに数式を入力します。

②射影法(線形近似法)①②の解法よりも緩い条件下で大域的収束が保証された効率的な解法 merit関数と射影演算を用いたものを説明する③Gap関数を利用した解法•••

任意の凸集合Ω上で定義された一般的な偏微分方程式は𝐹𝑖𝑛𝑑 𝑥 ∗ ∈ Ω∀𝒙 ∈ Ω

上式のアルゴリズムの基本的な枠組みは、学習したような許容降下法と同様であり、以下の改訂式によって 𝑿 𝑛 を生成することを繰り返す

𝑋 𝑛+1 ≔ 𝑋 𝑛 + 𝛼 𝑛 𝒅 𝒏Gap関数は、以下のように定義される

𝐺𝑄 𝒙

•

𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 𝑭 𝒙∗ ∙ 𝒙 − 𝒙∗ ≥ 𝟎≔ 𝑭 𝒙∗∙ 𝒙−𝑯 𝒙

ただし、

𝐻 𝒙 ≔ 𝑃𝑟𝑜𝑗Ω,𝑄 𝒙 − 𝑸−𝟏 𝑭 𝒙

𝑛 = 0,1,2, …

1− 𝑯 𝒙 −𝒙 ∙𝑸 𝑯 𝒙 −𝒙2, 𝒅𝒏=𝑯 𝒙𝒏−𝒙 𝒏31

交通ネットワーク分析ゼミ

第2回②

最適経路選択モデル-リンク間に相互干渉のある利用者均衡配分の解法••①緩和法(非線型対角化法)
打ち切り二次計画法

Simplicial Decomposition法

ここに数式を入力します。

②射影法(線形近似法)•①②の解法よりも緩い条件下で大域的収束が保証された効率的な解法 merit関数と射影演算を用いたものを説明する③Gap関数を利用した解法
merit関数に対する一次元探索によりα 𝑛 ∈ 0,1 を決定する
𝑚𝑖𝑛.𝛼 𝑛 𝐺𝑄 𝑿 𝑛 + 𝛼 𝑛 𝑑 𝑛𝑠. 𝑡. 0 ≤ 𝛼 𝑛 ≤ 1𝑟
起点別リンク交通量 𝑥𝑖𝑗
を明示的未知変数とした等価変分不等式問題を解くことを考える＜フロー保存条件＞

𝑟𝑥𝑖𝑘
−𝑖𝑟
𝑥𝑘𝑗
− 𝑞𝑟𝑘 = 0∀𝑘 ∈ 𝑁, 𝑘 ≠ 𝑟, ∀𝑟 ∈ 𝑅𝑗32

交通ネットワーク分析ゼミ

第2回②最適経路選択モデル-リンク間に相互干渉のある利用者均衡配分の解法••①緩和法(非線型対角化法)
打ち切り二次計画法

Simplicial Decomposition法•

ここに数式を入力します。

②射影法(線形近似法)①②の解法よりも緩い条件下で大域的収束が保証された効率的な解法 merit関数と射影演算を用いたものを説明する③Gap関数を利用した解法
𝑡𝑖𝑗 𝒙 + 𝜏𝑖𝑟 = 𝜏𝑗𝑟＜相補性条件＞
𝑟𝑥𝑖𝑗∙ 𝑡𝑖𝑗 𝒙 + 𝜏𝑖𝑟 − 𝜏𝑗𝑟 = 0
𝑡𝑖𝑗 𝒙 + 𝜏𝑖𝑟 − 𝜏𝑗𝑟 ≥ 0𝑟
𝑥𝑖𝑗
≥0∀𝑖𝑗 ∈ 𝐴, ∀𝑟 ∈ 𝑅

起点各々の未知変数ベクトルをまとめる𝒙 ≡ … , 𝒙𝑟 , … 𝑇 ∈𝑅𝐿 , 𝜏 𝑟 ≡ … , 𝝉𝑟 , … 𝑇 ∈𝑟∈𝑅

𝑨：起点数個の𝑨を要素に持つブロック対角行列
𝑬：起点数個のL*L単位行列を横に並べた行列

𝑅𝑁 ,𝒒 ≡ … , 𝒒𝑟 , … 𝑇𝑟∈𝑅33交通ネットワーク分析ゼミ

第2回②

最適経路選択モデル-リンク間に相互干渉のある利用者均衡配分の解法••①緩和法(非線型対角化法)
打ち切り二次計画法

Simplicial Decomposition法

ここに数式を入力します。

②射影法(線形近似法)③Gap関数を利用した解法
写像𝑭: Ω→Ωを𝑬𝑻 𝒕 𝑬𝒙
𝑭 X ≡𝒒𝑋≡ 𝑥

𝜏 𝑇 ∈ Ω,•①②の解法よりも緩い条件下で大域的収束が保証された効率的な解法 merit関数と射影演算を用いたものを説明する

𝑻 𝒙𝟎
𝑨+−𝑨 𝟎 𝝉𝑅+𝐿 × 𝑅+𝑁Ω≡𝑟∈𝑅

𝐹𝑖𝑛𝑑 𝑋 ∗ ∈ Ω𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 𝑭 𝑿∗ ∙ 𝑿 = 𝟎 , 𝑭 𝑿∗ ≥ 𝟎, 𝑿∗ ≥ 𝟎以下の変分不等式問題と等価である

𝐹𝑖𝑛𝑑 𝑋 ∗ ∈ Ω 𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 𝑭 𝑿∗ ∙ 𝑿 − 𝑿∗ ≥ 𝟎許容領域Ωが非負実数空間であるから、𝐻 𝑿 ≡ 𝑿 − 𝑄−1 𝑭 𝑿 に帰着

34

まとめ
• 利用者均衡モデルの解法の確立
変数の少ない単純なモデルではクーン・タッカー条件から直接導き出せるが、大規模な問題となると大変である。

• Flank-Wolfe法は、リンク容量に制約がある場合、計算回数が膨大になったり、リンク相互干渉などの問題が生じてしまう。

• Flank-Wolfe法を改善し効率化を図ることは、より大きな枠組、あるいはより現実的な場合を考慮する上で重要なことである。

35