# 利用者均衡交通配分モデルのおさらい
## 記号の定義
交通ネットワーク：
- $\mathcal{N}$: ノード集合
- $\mathcal{L}$: リンク集合
- $\mathcal{W}$: 起終点ペア集合（以下では主に1対の起終点ペア$(r, s)$を想定）
- $Q^{rs}$: 起終点ペア$(r, s)$の**交通需要**
- $\mathcal{K}^{rs}$: 起終点ペア$(r, s)$間の経路集合
- $\Delta^{rs} = \left[\delta_{k, a}^{rs}\right]$: 起終点ペア$(r, s)$の経路-リンク接続行列．$\delta_{k, a}^{rs}$は起終点ペア$(r, s)$の経路$k$がリンク$a$を含むなら1, そうでなければ0．

以下，簡単のため起終点ペアを1つとし，$(r, s)$についての表記を省略．

経路/リンク交通量とリンク/経路所要時間
- $\boldsymbol{x} = (x_{k}: k \in \mathcal{K})$: **経路**交通量
- $\boldsymbol{v} = (v_{a}): a \in \mathcal{L})$: **リンク**交通量
- あるリンクの交通量は，そのリンクを通過する経路交通量の和：
$$v_{a}(\boldsymbol{x}) = \sum_{k \in \mathcal{K}} \delta_{k, a} x_{k} \Leftrightarrow \boldsymbol{v}(\boldsymbol{x}) = \Delta^{\top} \boldsymbol{x}$$
- $\boldsymbol{t} = (t_{a}: a \in \mathcal{L})$: **リンク**所要時間
- $\boldsymbol{C} = (C_{k}: k \in \mathcal{K})$: **経路**所要時間
- ある経路の所要時間は，その経路上のリンク所要時間の和：
$$C_{k} = \sum_{a \in \mathcal{L}} \delta_{k, a} t_{a} \Leftrightarrow \boldsymbol{C} = \Delta \boldsymbol{t}$$
- $\boldsymbol{t}(\boldsymbol{v}) = (t_{a}(v_{a}): a \in \mathcal{L})$: リンク所要時間関数
- $\boldsymbol{C}(\boldsymbol{x}) = (C_{k}(\boldsymbol{x}): k \in \mathcal{K})$: 経路所要時間関数
- 経路交通量$\boldsymbol{x}$に対応するリンク所要時間：
$$
\boldsymbol{t}(\boldsymbol{v}(\boldsymbol{x})) = \boldsymbol{t}\left(\Delta^{\top} \boldsymbol{x}\right)
$$経路交通量$\boldsymbol{x}$に対応する経路所要時間：
$$\begin{align}
\boldsymbol{C}(\boldsymbol{x}) &= \Delta \boldsymbol{t}(\boldsymbol{v}(\boldsymbol{x}))\\
&= \Delta \boldsymbol{t}\left(\boldsymbol{\Delta}^{\top} \boldsymbol{x}\right)
\end{align}$$

## 利用者均衡配分モデルと等価最適化問題
利用者均衡では「利用されている経路の所要時間は全て等しく，それよりも所要時間の大きい経路は利用されない」という Wardrop第1原則が成立する．この条件は，以下の**相補性条件**として記述できる：
$$\begin{cases}
x_{k} > 0 & \rightarrow C_{k}(\boldsymbol{x}) = \rho\\
x_{k} = 0 &\leftarrow C_{k}(\boldsymbol{x}) > \rho
\end{cases}\quad \forall k \in \mathcal{K}
$$これにフロー保存則：
$$
\sum_{k \in \mathcal{K}} x_{k} = Q
$$を加えたものが**利用者均衡条件**である．

この利用者均衡条件は，以下の**非線形最適化問題**の最適性条件と等価である：
$$\begin{align}
\text{[UE-path]} \quad
\min_{\boldsymbol{x}} f(\boldsymbol{x}) &= \sum_{a \in L} \int_{0}^{v_{a}(\boldsymbol{x})} t_{a}(\omega)\mathrm{d}{\omega} \\
\text{s.t.} \quad &
\sum_{k \in K} x_{k} = Q\\
&x_{k} \geq 0, \quad \forall k \in K
\end{align}$$

$\text{[UE-path]}$の目的関数$f(\boldsymbol{x})$の勾配は， 目的関数がリンク所要時間の積分の和であることから得られる関係：
$$
\frac{\partial }{\partial v_{a}} f(\boldsymbol{x}) = t_{a}(\boldsymbol{v}(\boldsymbol{x}))
$$と微分の連鎖則を用いれば，
$$\begin{align}
\frac{\partial f}{\partial x_{k}}(\boldsymbol{x}) &=
\sum_{a \in \mathcal{L}}
\frac{\partial v_{a}}{\partial x_{k}} \frac{\partial f}{\partial v_{a}}(\boldsymbol{x})
\\
&= \sum_{a \in \mathcal{L}} \delta_{k, a} t_{a}(\boldsymbol{v}(\boldsymbol{x}))\\
&= C_{k}(\boldsymbol{x})
\end{align}$$と求められる． ベクトルで表現すれば
$$
\nabla f(\boldsymbol{x}) = \boldsymbol{C}(\boldsymbol{x})
$$となる．すなわち， 目的関数の経路交通量についての勾配は経路所要時間に一致する．

# Frank-Wolf法のおさらい
線形等式制約および非負制約つきの非線形最適化問題:
$$\begin{align}
\text{[P]}\quad \min_{\boldsymbol{x}} &f(\boldsymbol{x})\\
\text{s.t.} \quad &\boldsymbol{A} \boldsymbol{x} = \boldsymbol{b}\\
&\boldsymbol{x} \geq \boldsymbol{0}
\end{align}
$$を考える．ここで，$\boldsymbol{x} = (x_{1}, \cdots, x_{N})$は$N$次元の未知変数で，等式制約の数は$M$本とする(i.e. $\boldsymbol{A}$と$\boldsymbol{b}$の行数はいずれも$M$)とする．

問題$\text{[P]}$に対する Frank-Wolf 法は，$n$回目繰り返しにおいて求められた暫定解$\boldsymbol{x}^{(n)}$の周りで目的関数を一次近似：
$$\begin{align}
f(\boldsymbol{y}) &\approx f(\boldsymbol{x}^{(n)}) + \nabla f(\boldsymbol{x}^{(n)})^{\top}\left(\boldsymbol{y}-\boldsymbol{x}^{(n)}\right)\\
&= \nabla f(\boldsymbol{x}^{(n)})^{\top} \boldsymbol{y} + \text{const.}
\end{align}$$
したものを最小化する問題（**補助問題**）：
$$
\begin{align}
\text{[Aux]} \quad
\min_{\boldsymbol{y}} \hat{f}(\boldsymbol{y}) &= \nabla f(\boldsymbol{x}^{(n)}) \boldsymbol{y}\\
\text{s.t. } \quad & \boldsymbol{A} \boldsymbol{y} = \boldsymbol{b}\\
&\boldsymbol{y} \geq \boldsymbol{0}
\end{align}
$$
を解き，その解$\boldsymbol{y}^{(n)}$と現在の暫定解$\boldsymbol{x}^{(n)}$の**凸結合**を次の暫定解$\boldsymbol{x}^{(n+1)}$とする：
$$
\boldsymbol{x}^{(n+1)} := (1-\alpha) \boldsymbol{x}^{(n)} +\alpha \boldsymbol{y}^{(n)} \quad 0 \leq \alpha \leq 1
$$ここで，$\alpha$はステップサイズであり，以下の**範囲つき直線探索問題**を解いて求められる：
$$\text{[LS]} \quad
\min_{0 \leq \alpha \leq 1} g(\alpha) = f\left((1-\alpha) \boldsymbol{x}^{(n)} + \alpha \boldsymbol{y}^{(n)}\right)
$$

なお，解の改訂および線形探索問題の目的関数は，解の**降下方向**：
$$
\boldsymbol{d}^{(n)} := \boldsymbol{y}^{(n)} - \boldsymbol{x}^{(n)}
$$を用いて以下のようにも表される：
$$\begin{align}
\boldsymbol{x}^{(n+1)} &:= \boldsymbol{x}^{(n)} + \alpha \boldsymbol{d}^{(n)}, &
g(\alpha) &= f\left(\boldsymbol{x}^{(n)} + \alpha \boldsymbol{d}^{(n)}\right)
\end{align}
$$

問題$\text{[P]}$に対する Frank-Wolfe法のアルゴリズムは以下のように整理される：
- [Step 0] 初期実効可能解$\boldsymbol{x}^{(0)}$を選ぶ．$n:=0$とする．
- [Step 1] $\boldsymbol{x}^{(n)}$が最適解と判断できるなら終了(収束判定)．
- [Step 2] 補助問題 $\text{[Aux]} \displaystyle\min_{\boldsymbol{y}}\left\{\left.(\nabla f(\boldsymbol{x}^{(n)}))^{\top} \boldsymbol{y} \right| \boldsymbol{A} \boldsymbol{y} = \boldsymbol{b}, \boldsymbol{y} \geq \boldsymbol{0}\right\}$を解き，補助解$\boldsymbol{y}^{(n)}$を求める． 解の改訂方向を$\boldsymbol{d}^{(n)}:= \boldsymbol{y}^{(n)}-\boldsymbol{x}^{(n)}$とする．
- [Step 3] 範囲つき直線探索問題$\displaystyle\min_{0\leq \alpha \leq 1} g(\alpha) = f\left( \boldsymbol{x}^{(n)} + \alpha \boldsymbol{d}^{(n)}\right)$ を問いてステップ・サイズ$\alpha^{(n)}$を決定する．
- [Step 4] 解を$\boldsymbol{x}^{(n+1)} := \boldsymbol{x}^{(n)} + \alpha^{(n)} \boldsymbol{d}^{(n)}$と改訂する．
- [Step 5] $n:=n+1$として [Step 1]へ．

# 利用者均衡モデルに対する Frank-Wolfe 法
利用者均衡モデル$\text{[UE-path]}$に対して Frank-Wolfe法を適用する場合， Step 2 で解くべき補助問題$\text{[Aux-path]}$は，暫定解$\boldsymbol{x}^{(n)}$における目的関数の勾配が$\boldsymbol{x}^{(n)}$の下での経路費用：
$$
\nabla f(\boldsymbol{x}^{(n)}) = \boldsymbol{C}(\boldsymbol{x}^{(n)})
=: \boldsymbol{C}^{(n)}$$であることに注意すれば，
$$\begin{align}
\text{[Aux-UE-path]} \quad \min_{\boldsymbol{y}} \, &
\sum_{k \in \mathcal{K}} C_{k}^{(n)} y_{k}\\
\text{s.t.} \quad & \sum_{k \in \mathcal{K}} y_{k} = Q\\
& y_{k} \geq 0 \quad \forall k \in \mathcal{K}
\end{align}
$$と定式化できる． この問題の解は**自明**である：
:::success
利用者均衡モデルに対する補助問題$\text{[Aux-UE-path]}$の解$\boldsymbol{y}^{(n)} = (y_{k}^{(n)}: k \in \mathcal{K})$は，**費用が最小となる経路（最短経路）**：
$$
k^{(n)} := \arg\min_{k \in \mathcal{K}} C_{k}^{(n)}
$$**に全ての交通量$Q$を配分したもの**:$$
y_{k}^{(n)} := \begin{cases}
Q & \text{if } k = k^{(n)}\\
0 & \text{otherwise}
\end{cases}
$$である． ただし，最短経路が複数ある場合は，何らかの基準（e.g. 添字が最小のものを選ぶなど）で1つだけを選択する．

最短経路に全ての交通需要を配分することを**AoN (All-or-Nothing)配分**と呼ぶ．
:::

従って，利用者均衡モデル$\text{[UE-path]}$に対する Frank-Wolfe法は，以下のように整理できる：
- [Step 0] 実行可能な初期経路交通量$\boldsymbol{x}^{(0)}$を選ぶ．$n:=0$とする．
- [Step 1] $\boldsymbol{x}^{(n)}$が最適解と判断できるなら終了(収束判定)．
- [Step 2] 経路所要時間$\boldsymbol{C}^{(n)} = \boldsymbol{C}(\boldsymbol{x}^{(n)})$を求め， All-or-Nothing 配分：
$$
y_{k}^{(n)} = \begin{cases} Q & \text{if } k=\arg\min_{k\in\mathcal{K}} C_{k}^{(n)}\\0&\text{otherwise}
\end{cases}
$$により補助解$\boldsymbol{y}^{(n)}$を求める． 解の改訂方向を$\boldsymbol{d}^{(n)}:= \boldsymbol{y}^{(n)}-\boldsymbol{x}^{(n)}$とする．
- [Step 3] 範囲つき直線探索問題
$$\displaystyle\min_{0\leq \alpha \leq 1} g(\alpha) = f\left( \boldsymbol{x}^{(n)} + \alpha \boldsymbol{d}^{(n)}\right)
$$を問いてステップ・サイズ$\alpha^{(n)}$を決定する．
- [Step 4] 解を$\boldsymbol{x}^{(n+1)} := \boldsymbol{x}^{(n)} + \alpha^{(n)} \boldsymbol{d}^{(n)}$ と改訂する．
- [Step 5] $n:=n+1$として [Step 1]へ．

# 経路が極めて多い場合:リンク変数表示
一般的なネットワークでは経路が極めて多く，経路交通量$\boldsymbol{x}$や経路-リンク接続行列$\boldsymbol{\Delta}$を用いた分析が著しく困難となり得る．例えば，下図はテキサス州オースティンを模した道路ネットワークで 7,388個のノード，18,961本のリンクで構成されており， 起終点ペアが1,081,717個ある．
<div style="text-align:center; padding:20pt">
<img src="https://hackmd.io/_uploads/SJOaQA4Yn.png" width="600">
</div>

このようなネットワークに対して，全ての起終点について経路を列挙することは極めて困難である．そこで，利用者均衡問題$\text{
}$を**経路変数** $\boldsymbol{x}$ではなく**リンク変数** $\boldsymbol{v}$ で記述することを考えよう．

## 目的関数のリンク変数表示
まず，目的関数$f(\boldsymbol{x})$は，もともと「各リンクの所要時間を$[0,v]$まで積分したものの総和」だから，
$$
f(\boldsymbol{v})= \sum_{a \in \mathcal{L}} \int_{0}^{v_{a}} t_{a}(\omega) \mathrm{d} \omega
$$とすれば良い．

## 交通量保存則のリンク変数表示
次に，各起終点についての交通量保存則$\sum_{k \in \mathcal{K}} x_{k} = Q$は，下図のような（起終点を含む）各ノード$n \in \mathcal{N}$ についての交通量保存則で置き換えられる．以下では，必要に応じて，各リンクを通し番号ではなく，先頭と末尾のノードのペアで表すことがある（例えば，ノード$i$からノード$j$へのリンク交通量は$v_{i, j}$もしくは$v_{ij}$と表す）．
<div style="text-align:center; padding:20pt">
<table><tr><td>
<img src="https://hackmd.io/_uploads/B1tJ-yrKn.png" width=200></td><td>
<img src="https://hackmd.io/_uploads/rJK7-1HF3.png" width=200></td><td>
<img src="https://hackmd.io/_uploads/HkL4ZJrF2.png" width=200></td>
</tr><tr><td>

$n$が起点でも終点でもない
$$
\sum_{i} v_{in} = \sum_{j} v_{nj}
$$
</td><td>

$n$が起点
$$
\sum_{i} v_{in} + Q = \sum_{j} v_{nj}
$$
</td><td>

$n$が終点
$$
\sum_{i} v_{in} = \sum_{j} v_{nj} + Q
$$
</td></tr>
</table>
</div>

あるノード$n$が起点でも終点でもなければ，「$n$へ流入するリンク交通量の総和」と「$n$から流出するリンク交通量の総和」は等しくなければならない．この制約は以下の等式で記述できる：
$$
\sum_{i} v_{in} = \sum_{j} v_{nj}
$$次に，$n$が起点$r$であるなら「$n$から流出するリンク交通量の総和」は「$n$へ流入するリンク交通量の総和」に「ノード$n$から出発する（湧き出す）交通量」の和に等しい：
$$
\sum_{i} v_{in} + Q = \sum_{j} v_{nj}
$$逆に，$n$が終点$s$であるなら「$n$へ流入するリンク交通量の総和」は「$n$から流出するリンク交通量の総和」と「ノード$n$へ到着する（吸収される）交通量」の和に等しい：
$$
\sum_{i} v_{in} = \sum_{j} v_{nj}+ Q
$$
これらを整理すると，ノードごとの交通量保存則は次の式で表される：
$$
\sum_{i} v_{in} - \sum_{j} v_{nj} = \begin{cases}
-Q &\text{if } n = r\\
Q & \text{if } n = s\\
0 & \text{otherwise}
\end{cases}
$$

例えば，下図のネットワーク：

<div style="text-align:center;padding:20pt">
<img src="https://hackmd.io/_uploads/rk2l7-7Y2.png" width=300>
</div>

において，起終点ペアが$(1, 4)$のみであり，その交通需要が$Q$であるとき，各ノードでのリンク交通量保存則は，それぞれ，以下のように記述できる：
$$\begin{array}{rrrrrlr}
-v_{a}& -v_{b}& & & &= -Q&\text{(node 1)}\\
v_{a}& & -v_{c}& - v_{d} & & = 0&\text{(node 2)}\\
& v_{b}&+v_{c}& & -v_{e} &=0&\text{(node 3)}\\
& & & v_{d} &+v_{e} &= Q &\text{(node 4)}
\end{array}$$
この式は，行列とベクトルを用いて
$$\begin{align}
\begin{bmatrix}-1 & -1 & 0 & 0 & 0\\
1 & 0& -1&-1&0\\
0 & 1 & 1 & 0& -1\\
0 & 0 & 0 & 1 & 1
\end{bmatrix}\begin{bmatrix}v_{a}\\v_{b}\\v_{c}\\v_{d}\\v_{e}
\end{bmatrix} &= \begin{bmatrix}
-Q \\ 0 \\ 0 \\ Q
\end{bmatrix}
\end{align}$$と表せる． この方程式は，各ノードにおいて成立すべき**交通量保存則**を表している．

一般に，$N$個のノード，$L$本の有向リンクで構成される有向グラフ（ネットワーク）に対して，
$N$行$L$列の行列$\boldsymbol{A}$で，その$n$行$l$列要素が
$$
a_{n, l} = \begin{cases}
-1 & \text{if link $l$ is from node $n$}\\
1& \text{if link $l$ is to node $n$}\\
0 & \text{otherwise}
\end{cases}
$$であるものを**ノード-リンク接続行列**と呼ぶ． $N$次元の列ベクトル$\boldsymbol{b}$でその$n$番目要素が
$$
b_{n} = \begin{cases} -Q &\text{if $n$ is origin $r$}\\
Q&\text{if $n$ is destination $s$}\\
0&\text{otherwise}\end{cases}
$$となるものを定義し，$\boldsymbol{v} = (v_{a}: a \in \mathcal{L})$とすれば， ノードごとの交通量保存則は，以下の$N$次元線形方程式で表せる：
$$
\boldsymbol{A} \boldsymbol{v} = \boldsymbol{b}
$$
:::success
ノードごとの交通量保存則は$N$個の方程式であるが，そのうちの1つは必ず**線形従属**である．
このことは，$\boldsymbol{A}$の全ての列（リンク）が，一対のみの$(-1, 1)$と$0$のみで構成されており，$\boldsymbol{A}$の行を全て足し合わせると，全ての要素がゼロとなる行ベクトルが得られることからも明らかである．

このため，$\boldsymbol{A}\boldsymbol{v}=\boldsymbol{b}$ のうち1本は冗長であり，1つのノードに対応する方程式を除外しても問題ない．例えば，上述の5リンク・ネットワークの例では，交通量保存則を
$$\begin{align}
\begin{bmatrix}
1 & 0& -1&-1&0\\
0 & 1 & 1 & 0& -1\\
0 & 0 & 0 & 1 & 1
\end{bmatrix}\begin{bmatrix}v_{a}\\v_{b}\\v_{c}\\v_{d}\\v_{e}
\end{bmatrix} &= \begin{bmatrix}
0 \\ 0 \\ Q
\end{bmatrix}
\end{align}$$で置き換えても問題ない．
:::

## 利用者均衡問題のリンク変数表示
以上のことから，利用者均衡問題と等価な最適化問題$\text{[UE-path]}$は，リンク交通量$\boldsymbol{v}$を明示的な未知変数とした下記の問題に帰着する：
$$\begin{align}
\text{[UE-link]} \quad
\min_{\boldsymbol{v}} f(\boldsymbol{v}) &= \sum_{a \in L} \int_{0}^{v_{a}} t_{a}(\omega)\mathrm{d}{\omega} \\
\text{s.t.} \quad &
\boldsymbol{A} \boldsymbol{v} = \boldsymbol{b}\\
&\boldsymbol{v} \geq \boldsymbol{0}
\end{align}$$

この問題の最適性条件から，リンク変数表示された利用者均衡条件を導ける．まず，ノードごとの交通量保存則($N$本の等式制約)$$
\boldsymbol{g}(\boldsymbol{v}) = \boldsymbol{A} \boldsymbol{v} - \boldsymbol{b}
$$に対する Lagrange 乗数を
$$\boldsymbol{\tau} = (\tau_{n}: n \in \mathcal{N})
$$と定義し， Lagrangian を
$$
L(\boldsymbol{v}, \boldsymbol{\tau})
= f(\boldsymbol{v}) - \tau^{\top} (\boldsymbol{A} \boldsymbol{v} - \boldsymbol{b})
$$と定義する． このとき
$$\begin{align}
\nabla_{v} L(\boldsymbol{v}, \boldsymbol{\tau})
&= \nabla f(\boldsymbol{v}) - \nabla \boldsymbol{g}(\boldsymbol{v})^{\top}\boldsymbol{\tau}\\
&= \boldsymbol{t}(\boldsymbol{v}) - \boldsymbol{A}^{\top} \boldsymbol{\tau}\\
\nabla_{\boldsymbol{\tau}} L(\boldsymbol{v}, \boldsymbol{\tau})
&= \boldsymbol{A} \boldsymbol{x} - \boldsymbol{b}
\end{align}$$であることに注意すれば，最適性条件(KKL条件)は，
$$\begin{align}
&\begin{cases}
\boldsymbol{v}^{\top} \left\{\boldsymbol{t}(\boldsymbol{v}) - \boldsymbol{A}^{\top} \boldsymbol{\tau}\right\} = 0\\
\boldsymbol{v} \geq \boldsymbol{0},
\quad \boldsymbol{t}(\boldsymbol{v}) - \boldsymbol{A}^{\top} \boldsymbol{\tau} \geq \boldsymbol{0}
\end{cases}\\
& \boldsymbol{A} \boldsymbol{v} - \boldsymbol{b} = \boldsymbol{0}
\end{align}$$と表される．

この式のうち，後者はノードごとの交通量保存則を表す．前者の相補性条件は何を表しているだろうか．まず，これを要素表示すれば
$$\begin{cases}
v_{ij} > 0 \rightarrow t_{ij}(\boldsymbol{v}) + \tau_{i} - \tau_{j} = 0\\
v_{ij} = 0 \leftarrow t_{ij}(\boldsymbol{v}) + \tau_{i} - \tau_{j} > 0
\end{cases}\quad (i, j) \in \mathcal{L}
$$となる．この式は$\tau_{i}$を「起点$r$からノード$i$までの均衡状態における最短所要時間」と見なすと， 以下のように解釈できる：
- リンク$(i, j)$が利用される（$v_{ij} > 0$）時には，$\tau_{j} = \tau_{i} + t_{ij}$ が成立する． すなわち，$v_{ij}>0$ならば，ノード$j$までの最短所要時間は，ノード$i$までの最短所要時間にリンク所要時間$t_{ij}$を加えたものになる（i.e, 起点からノード$j$までの最短経路がリンク$(i, j)$を通過する）．従って，この式は「リンク$(i, j)$が利用されているならば，そのリンクは起終点$(r,s)$の最短経路上に存在する」ことを意味する．
- $\tau_{j} < \tau_{i} + t_{ij}$である時には，リンク$(i, j)$は利用されない．つまり，起点からノード$j$までには，リンク$(i,j)$を通らない別の最短経路が存在する．従って，この式は「リンク$(i,j)$が起終点$(r,s)$の最短経路上に存在しないなら，そのリンクは利用されない」ことを意味する．
<div style="text-align:center; padding:20pt">
<img src="https://hackmd.io/_uploads/BypfdadFn.png">
</div>

以上の条件が全てのリンクについて成立することから，$\text{[UE-link]}$の最適性条件は **「利用される全てのリンクは最短経路上に存在し，最短経路上にないリンクは利用されない」** と解釈できる．これは **「利用される全ての経路は最短経路であり，最短ではない経路は利用されない」** という利用者均衡状態で成立する条件をリンクごとで成立する条件として読み替えたものに他ならない．

# 均衡配分問題に Frank-Wolfe 法を適用する際のヒント
## リンク変数表示での All-or-Nothing配分
リンク変数表示の問題$\text{[UE-link]}$に対する補助問題は，$\boldsymbol{v}^{(n)}$におけるリンク所要時間
$$
\boldsymbol{t}^{(n)} = \boldsymbol{t}(\boldsymbol{v}^{(n)})
$$を与件とした以下の線形計画問題：
$$\begin{align}
\text{[Aux-UE-link]} \quad
\min_{\boldsymbol{u}} \quad &{\boldsymbol{t}^{(n)}}^{\top} \boldsymbol{u} \\
\text{s.t.} \quad &
\boldsymbol{A} \boldsymbol{u} = \boldsymbol{b}\\
&\boldsymbol{u} \geq \boldsymbol{0}
\end{align}
$$として定式化される．この問題は，各ノードでの交通量保存則の下で，与えられたリンク所要時間$\boldsymbol{t}^{(n)} = (t_{a}^{(n)})$とリンク交通量$\boldsymbol{u} = (u_{a})$の積の総和を最小化する問題である．こう書くと複雑に思えるが「線形計画問題の解は**許容領域の端点**である」ことを考えれば，この補助問題の解は「最短経路に全ての交通需要$Q$を流す All-or-Nothing配分」となることが自明である．

一般に，全てのリンク所要時間が非負であるような有向グラフ（ネットワーク）上で，ある起点から**他の全てのノードへの最短経路** を求めるアルゴリズムとして [Dijkstra法](https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.dijkstra.html)が知られている．このアルゴリズムは 起点ノードを**根(root)** として，それ以外のノードへの枝を持つ**最短経路木(shortest path tree)** が求められる． この構造を利用することで**一起点多終点**の All-or-Nothing 配分を効率的に求められることが知られている（その詳細は本講義の範疇を超えるので割愛）．

## 初期許容解の導出法
[Step 0]で与える初期経路交通量$\boldsymbol{x}^{(0)}$ もまた All-or-Nothing 配分で与えてよい． 例えば， 道路上に一切車両が存在しない（$\boldsymbol{x}=\boldsymbol{0}$）状態での経路交通量$\boldsymbol{C}(\boldsymbol{0})$ を考え， これを用いた All-or-Nothing 配分の解を$\boldsymbol{x}^{(0)}$ としてよい．

### リンク所要時間関数が線形関数の場合の最適ステップ・サイズ
リンク所要時間が以下の線形関数：
$$
\boldsymbol{t}(\boldsymbol{v}) = \boldsymbol{D} \boldsymbol{v} + \boldsymbol{e}
$$（ただし，$\boldsymbol{D} \in \mathcal{R}^{L\times L}$かつ$\boldsymbol{e} \in \mathcal{R}^{L}$は所与の定数）で与えられる場合，[Step 3]の範囲つき直線探索問題は解析的に解くことができる．

まず，リンク変数表示の問題$\text{[UE-link]}$の場合，目的関数は
$$
f(\boldsymbol{v}) = \frac{1}{2} \boldsymbol{v}^{\top} \boldsymbol{D} \boldsymbol{v} + \boldsymbol{v}^{\top} \boldsymbol{e}
$$である．現在の暫定解を$\boldsymbol{v}$，補助解を$\boldsymbol{u}$，降下方向を$\boldsymbol{d} = \boldsymbol{u}-\boldsymbol{v}$とすれば，一次元探索で解くべき問題の目的関数は：
$$\begin{align}
g(\alpha) &= f(\boldsymbol{v} + \alpha \boldsymbol{d}) = (\boldsymbol{v} + \alpha \boldsymbol{d})^{\top} \boldsymbol{t}(\boldsymbol{v}+\alpha\boldsymbol{d})\\
&= (\boldsymbol{v} + \alpha \boldsymbol{d})^{\top} \left\{\frac{1}{2}\boldsymbol{D} (\boldsymbol{v} + \alpha \boldsymbol{d}) + \boldsymbol{e}\right\}\\
&= \frac{1}{2}\alpha^{2} \boldsymbol{d}^{\top} \boldsymbol{D} \boldsymbol{d} + \alpha\boldsymbol{d}^{\top}(\boldsymbol{D} \boldsymbol{v} + \boldsymbol{e}) + \boldsymbol{v}^{\top} (\boldsymbol{D} \boldsymbol{v} + \boldsymbol{e})
\end{align}$$より，
$$\begin{align}
\kappa_{1} &= \boldsymbol{d}^{\top} \boldsymbol{D} \boldsymbol{d}, &
\kappa_{2} &= \boldsymbol{d}^{\top}(\boldsymbol{D} \boldsymbol{v}+\boldsymbol{e}), &
\kappa_{3} &= \boldsymbol{v}^{\top} (\boldsymbol{D} \boldsymbol{v} + \boldsymbol{e})
\end{align}$$とすれば，下記の二次関数で表せる：
$$
g(\alpha) = \frac{\kappa_{1}}{2} \alpha^{2} + \kappa_{2} \alpha + \kappa_{3}
$$ここで，$\boldsymbol{D}$が正定値であれば任意の$\boldsymbol{d}\ne \boldsymbol{0}$に対して$\kappa_{1} > 0$であることから$g(\alpha)$が凸関数であることが保証され，その最適解は以下の式で表される：
$$
\alpha^{\ast} = \begin{cases}
0 &\text{if } g^{\prime}(\alpha=0)=\kappa_{2} > 0\\
1 &\text{if } g^{\prime}(\alpha=1)=\kappa_{1}+\kappa_{2}<0\\
-\kappa_{2}/\kappa_{1} &\text{otherwise}
\end{cases}$$

経路変数表示の問題$\text{[UE-path]}$についても，リンク交通量を
$$
\boldsymbol{v} = \boldsymbol{\Delta}^{\top} \boldsymbol{x}
$$で置き換えれば，全く同様のロジックが成立する．具体的には，経路変数表示の利用者均衡配分モデル$\text{[UE-path]}$の目的関数は
$$\begin{align}
f(\boldsymbol{x}) &= \frac{1}{2} \boldsymbol{x}^{\top}\Delta \boldsymbol{D} \boldsymbol{\Delta}^{\top} \boldsymbol{x} + \boldsymbol{x}^{\top}\boldsymbol{\Delta} \boldsymbol{e}\\
&=\frac{1}{2}\boldsymbol{x}^{\top}\boldsymbol{H} \boldsymbol{x} + \boldsymbol{x}^{\top} \boldsymbol{g}
\end{align}
$$と表される．ただし，$$\begin{align}
\boldsymbol{H} &= \boldsymbol{\Delta} \boldsymbol{D} \boldsymbol{\Delta}^{\top}, &
\boldsymbol{g} &= \boldsymbol{\Delta} \boldsymbol{e}
\end{align}$$である． これらをリンク変数表示の場合の$\boldsymbol{D}, \boldsymbol{e}$の代わりに用いれば，最適ステップサイズが解析的に求められる．具体的には，
暫定解$\boldsymbol{x}$に対する補助問題$\text{[Aux-UE-path]}$の解を$\boldsymbol{y}$，降下方向を$\boldsymbol{d}=\boldsymbol{y}-\boldsymbol{x}$とし，
$$\begin{align}
\kappa_{1} &= \boldsymbol{d}^{\top} \boldsymbol{H} \boldsymbol{d}, &
\kappa_{2} &= \boldsymbol{d}^{\top}(\boldsymbol{H} \boldsymbol{x}+\boldsymbol{g})
\end{align}$$とすれば，最適ステップサイズ$\alpha^{\ast}$は上述の式と同様に求められる．