[非線形計画問題トップに戻る](https://hackmd.io/@nagae/NLP)

# 利用者均衡配分モデル
## まずはシンプルなモデルから
図に示すような，1対の起点($O$)と終点($D$)のペアを2本のリンク$a, b$が結ぶネットワークを考えよう：

<div style="text-align:center; padding=20pt">

</div>

この道路ネットワークの利用者の総数($O$から$D$への交通需要)が定数$Q=10$で与えられるとする．各リンクの利用者数(リンク交通量)を$x_{a}, x_{b}$で表し，$\boldsymbol{x} = (x_{a}, x_{b})$とする．交通量の許容領域は，
$$\left\{\boldsymbol{x}
\left| x_{a} +x_{b} = Q,
\quad x_{a}, x_{b} \geq 0\right.
\right\}$$
で表される．

各リンクの所要時間は，当該リンク交通量の関数$$\begin{align}
t_{a}(x_{a}) &= x_{a} + 10\\
t_{b}(x_{b}) &= 3 x_{b} + 4
\end{align}$$で表されるとする．

各利用者について，以下を仮定する（**完全合理性**)：
1. **全ての経路**の所要時間を**正確に把握**している
2. **所要時間が最小となる経路**を選択する

> なお，ここで示しているネットワークでは **経路** と **リンク** は同じ意味を持つ．後述するように，通常のネットワークでは，1つの経路が複数のリンクで構成される．

この条件の下で，どのような交通状態が**安定的**に起こるだろうか，という問題を考えよう．

## Nash均衡，Wardrop交通配分原則と相補性条件としての表現
全ての利用者が完全合理的であるとき，少しでも空いている（所要時間の短い）経路があれば，利用者は**抜け目なく**その経路へと選択を変更するだろう．つまり，所要時間が短い経路が残っている状態では，利用者は自らの行動を変更する**インセンティブ**を持っており，**安定的**とはいえない．

「どの利用者も自分だけが行動を変更することでは所要時間を改善できない」という状態を **均衡状態**（あるいは提唱者の John Nash の名を関して**Nash 均衡状態**）と呼ぶ([Nash, 1952](https://www.pnas.org/doi/10.1073/pnas.36.1.48))).

この Nash 均衡と同等の概念を，Wardrop は **交通配分の第1原則** として発表している：
「利用されている経路の所要時間は全て等しく，それより所要時間の大きな経路は利用されない」([Wardrop, 1952](https://www.icevirtuallibrary.com/doi/epdf/10.1680/ipeds.1952.11259))．

この Nash均衡状態 / Wardrop 第1原則は，以下の**相補性条件**として表現できる：
$$\begin{cases}
x_{i}^{\ast} > 0 & \rightarrow t_{i}(\boldsymbol{x}^{\ast}) = \rho^{\ast}\\
x_{i}^{\ast} = 0 & \leftarrow t_{i}(\boldsymbol{x}^{\ast}) > \rho^{\ast}
\end{cases}\qquad i = a, b$$
ここで，$\rho^{\ast}$は均衡状態において利用されている経路の所要時間であり，**均衡所要時間（均衡コスト）** と呼ばれる．

この相補性条件は，最初の式で「利用されている経路の所要時間は全て$\rho^{\ast}$等しい」ことを表しており，次の式で「$\rho^{\ast}$より所要時間の大きな経路は利用されない」ことを表している．

$\boldsymbol{x}^{\ast}$が均衡交通配分となるためには，この相補性条件に加えて，もちろん，交通量保存則：
$$
x_{a}^{\ast} + x_{b}^{\ast} = Q
$$も満足していなければならない．

$t_{a} = x_{a} + 10, t_{b} = 3x_{b} + 4$のケースでは，均衡交通量は$\boldsymbol{x}^{\ast} = (6, 4)$であり，均衡所要時間は$\rho^{\ast} = 16$となる．

## 相補性条件で繋がる最適化問題と均衡配分
**均衡交通配分** $(\boldsymbol{x}, \rho)$ が満たすべき条件（**均衡条件**）：
$$\begin{align}
&\begin{cases}
x_{i} > 0 & \rightarrow t_{i}(\boldsymbol{x}) = \rho\\
x_{i} = 0 & \leftarrow t_{i}(\boldsymbol{x}) > \rho
\end{cases}\qquad i = a, b
\\
& x_{a} + x_{b} = Q
\end{align}
$$は，実は，次の**非線形最適化問題の最適性条件**と等価である：
$$\begin{align}
\text{[UE-2link]}
\min_{\boldsymbol{x}} f(\boldsymbol{x}) &= \int_{0}^{x_{a}} t_{a}(\omega)\mathrm{d}{\omega} + \int_{0}^{x_{b}} t_{b}(\omega)\mathrm{d}{\omega} \\
\text{s.t.} \quad &
x_{a} + x_{b} = Q\\
&x_{a}, x_{b} \geq 0
\end{align}
$$これは，以下のようにして確認できる．

まず，等式制約（交通量保存則）$x_{a} + x_{b} = Q$は，全ての要素が1であるベクトル$\boldsymbol{1} = (1, 1)$を用いて
$$
g(\boldsymbol{x}) =
\boldsymbol{1}^{\top} \boldsymbol{x} - Q = 0
$$と書ける．この制約に対する Langrange 乗数を$\rho$とおき， Lagrangian を
$$
L(\boldsymbol{x}, \rho) = f(\boldsymbol{x}) - \rho g(\boldsymbol{x})
$$と定義する．このとき，最適性条件は[こちら](https://hackmd.io/@nagae/NLP-Ch02#%E7%B7%9A%E5%BD%A2%E7%AD%89%E5%BC%8F%E5%88%B6%E7%B4%84%E3%81%A8%E9%9D%9E%E8%B2%A0%E5%88%B6%E7%B4%84)より，
$$\begin{align}
&\begin{cases}
\boldsymbol{x}^{\top} \left\{
\nabla f(\boldsymbol{x}) - \rho\nabla g(\boldsymbol{x})
\right\} = 0\\
\boldsymbol{x} \geq \boldsymbol{0}, \quad \nabla f(\boldsymbol{x}) - \rho\nabla g(\boldsymbol{x}) \geq \boldsymbol{0}
\end{cases}\\
& g(\boldsymbol{x}) = 0
\end{align}
$$である．要素ごとに書き下せば，
$$\begin{align}
&\begin{cases}
x_{i} > 0 &\rightarrow \frac{\partial f}{\partial x_{i}}(\boldsymbol{x}) - \rho \frac{\partial g}{\partial x_{i}}(\boldsymbol{x}) = 0\\
x_{i} = 0 &\leftarrow \frac{\partial f}{\partial x_{i}}(\boldsymbol{x}) - \rho \frac{\partial g}{\partial x_{i}}(\boldsymbol{x}) > 0
\end{cases}, \quad i = a, b\\
& g(\boldsymbol{x}) = 0
\end{align}
$$となる．いま，
$$
\begin{align}
\frac{\partial f}{\partial x_{i}}(\boldsymbol{x}) &= t_{i}(\boldsymbol{x})\\
\frac{\partial g}{\partial x_{i}}(\boldsymbol{x}) &= 1
\end{align}
$$であることに注意すれば，最適性条件は
$$
\begin{align}
&\begin{cases}
x_{i} > 0 & \rightarrow t_{i}(\boldsymbol{x}) = \rho\\
x_{i} = 0 & \leftarrow t_{i}(\boldsymbol{x}) > \rho
\end{cases}\qquad i = a, b
\\
& x_{a} + x_{b} = Q
\end{align}
$$であり，均衡条件そのものである．

このことを図でも確認してみよう． $t_{a} = x_{a} + 10, t_{b} = 3x_{b} + 4$の場合，目的関数は
$$
f(\boldsymbol{x}) = \frac{1}{2} x_{a}^{2} + 10 x_{a} + \frac{3}{2}x_{b}^{2} + 4 x_{b}
$$であり，その等高線は下図で示される（左下ほど目的関数が小さい）．この図において橙の直線は$x_{a} + x_{b}= 10, x_{a}, x_{b}\geq 0$なる$\boldsymbol{x}$の許容領域を表している．この許容領域内で目的関数を最小とするのは$\boldsymbol{x}^{\ast} = (6, 4)$であり，図中の赤丸で表されている．黒い矢印はこの点における目的関数の降下方向$-\nabla f(\boldsymbol{x}) = (-16, -16)$を表しており，制約条件$x_{a} + x_{b}=10$の法線$-\nabla g(\boldsymbol{x}) = (-1, -1)$の定数倍となっている．

<div style="text-align:center; padding:20pt">

</div>

## 図で理解する均衡配分と最適化問題の等価性

均衡配分と等価な最適化問題の目的関数：
$$
f(\boldsymbol{x}) = \int_{0}^{x_{a}} t_{a}(\omega)\mathrm{d}{\omega} + \int_{0}^{x_{b}} t_{b}(\omega)\mathrm{d}{\omega}
$$は何を表しているのだろうか．図示して確認してみよう．

まず，$x_{b} = Q-x_{a}$であることから，交通量は$x_{a} \in [0, Q]$だけで完全に表せる．下の図は，横軸にリンク$a$の交通量$x_{a}$を取り，縦軸に各リンクの所要時間$t_{a}(x_{a})$および$t_{b}(Q-x_{a})$をプロットしたものである．リンク$b$の所要時間$t_{b}$が$x_{a}$について減少していることに注意されたい．

**均衡状態**は，この2本の直線の交点（i.e. 利用されている経路の所要時間が全て等しい状態）である．

<div style="text-align:center; padding:20pt">

</div>

:::warning
もちろん，$x_{a}=0$や$x_{a}=Q$が均衡状態となる場合もある．具体的には，
- $t_{a}(0) > t_{b}(Q)$ならば均衡状態は$\boldsymbol{x}^{\ast}=(0, Q)$
- $t_{a}(Q) < t_{b}(0)$ならば均衡状態は$\boldsymbol{x}^{\ast}=(Q, 0)$

である．
:::

この所要時間を積分したものが目的関数である．例えば，$(x_{a}, x_{b})=(5,5)$の場合，それぞれの目的関数を$[0, 5]$の範囲で積分したものは，下図の青い領域および橙の領域で表される．
<div style="text-align:center; padding:20pt">

</div>

$(x_{a}, x_{b})=(7,3)$の場合，目的関数は下図のように$t_{a}$を$x_{a} \in [0,7]$で積分した青い領域と$t_{b}$を$x_{b} \in [0,3]$で積分した橙の領域（$x_{a}$の積分範囲は$[10, 7]$）との和である．
<div style="text-align:center; padding:20pt">

</div>

2つのリンクの所要時間が等しくなる点$(x_{a}, x_{b}) = (6,4)$において，目的関数は下図の領域となり，上の2つのケース$x_{a}=5$, $x_{a}=7$よりも小さくなっていることが判る．
<div style="text-align:center; padding:20pt">

</div>

実際，この点は目的関数を最小化する点である．このことは，各リンクの所要時間のグラフと目的関数のグラフを縦方向に並べてみると一目瞭然である．
<div style="text-align:center; padding:20pt">

</div>

# 一般的なネットワークでの利用者均衡モデル
## 有向グラフとしてのネットワーク表現
交通均衡配分モデルを，より一般的なネットワークに拡張しよう．下図のように，一般的なネットワークは，交差点をノード，道路区間を有向リンクとした有向グラフで構成される．

<div style="text-align:center; padding:20pt">

</div>

この場合，1つの経路が複数のリンクで構成され得る．例えば，上図のネットワークでノード1を起点，ノード6を終点とした経路は，全部で8本存在する（括弧内は経路上のリンク）：
1. 1→2→3→4→5→6 ($a, c, e, g, i$)
2. 1→2→3→4→6 ($a, c, e, h$)
3. 1→2→3→5→6 ($a, c, f, i$)
4. 1→2→4→5→6 ($a, d, g, i$)
5. 1→2→4→6 ($a, d, h$)
6. 1→3→4→5→6 ($b, e, g, i$)
7. 1→3→4→6 ($b, e, h$)
8. 1→3→5→6 ($b, f, i$)

以下では，経路集合を$\mathcal{K}$，リンク集合を$\mathcal{L}$で表し，経路$k$とリンク$a$の関係を，以下の Kroneckerのデルタを用いて表現する：
$$
\delta_{k, a} =\begin{cases}
1 &\text{path $k$ includes link $a$}\\
0 &\text{otherwise}
\end{cases}
$$

この$\delta_{k, a}$を$k$行$a$列要素として持つ行列$\boldsymbol{\Delta}$を**経路-リンク接続行列 (path-link incident matrix)** と呼ぶ．上述の例での経路-リンク接続行列は以下で表される：
$$\boldsymbol{\Delta} = \begin{array}{c|ccccccccc}
&a&b&c&d&e&f&g&h&i\\\hline
1&1&0&1&0&1&0&1&0&1\\
2&1&0&1&0&1&0&0&1&0\\
3&1&0&1&0&0&1&0&0&1\\
4&1&0&0&1&0&0&1&0&1\\
5&1&0&0&1&0&0&0&1&0\\
6&0&1&0&0&1&0&1&0&1\\
7&0&1&0&0&1&0&0&1&0\\
8&0&1&0&0&0&1&0&0&1\\
\end{array}$$
:::danger
この行列は8行×9列であるが，一般的なネットワークでは，経路の本数（列数）がリンクの本数（行数）よりも**圧倒的に多い**ことに注意されたい．
:::

## 経路/リンク交通量とリンク/経路所要時間
経路交通量を$\boldsymbol{x} = (x_{k}: k \in K)$，リンク交通量を$\boldsymbol{v}= (v_{a}: a \in L)$で表そう．起点ノードから終点ノードへの交通需要が所与の定数$Q$で与えられるとき，全ての経路交通量の和はこれに等しくなければならない：
$$
\sum_{k \in K} x_{k} = Q
$$

あるリンク$a$の交通量は，そのリンクを通過する全ての経路の交通量の和に等しい：
$$
v_{a} = \sum_{k \in K} \delta_{k, a} x_{k}
$$
この関係式は，ベクトルと行列を用いて
$$
\boldsymbol{v} = \boldsymbol{\Delta}^{\top} \boldsymbol{x}
$$
と表すこともできる．

上述のネットワークでは，この関係式は以下のように表される：
$$
\boldsymbol{v} = \begin{bmatrix}
v_{a}\\v_{b}\\v_{c}\\v_{d}\\v_{e}\\v_{f}\\v_{g}\\v_{h}\\v_{i}
\end{bmatrix} = \boldsymbol{\Delta}^{\top} \boldsymbol{x} =
\begin{bmatrix}
1&1&1&1&1&0&0&0\\
0&0&0&0&0&1&1&1\\
1&1&1&0&0&0&0&0\\
0&0&0&1&1&0&0&0\\
1&1&0&0&0&1&1&0\\
0&0&1&0&0&0&0&1\\
1&0&0&1&0&1&0&0\\
0&1&0&0&1&0&1&0\\
1&0&1&1&0&1&0&1
\end{bmatrix}
\begin{bmatrix}
x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\\x_{6}\\x_{7}\\x_{8}
\end{bmatrix}=\begin{bmatrix}
x_{1}+x_{2}+x_{3}+x_{4}+x_{5}\\
x_{6}+x_{7}+x_{8}\\
x_{1}+x_{2}+x_{3}\\
x_{4}+x_{5}\\
x_{1}+x_{2}+x_{6}+x_{7}\\
x_{3}+x_{8}\\
x_{1}+x_{4}+x_{6}\\
x_{2}+x_{5}+x_{7}\\
x_{1}+x_{3}+x_{4}+x_{6}+x_{8}
\end{bmatrix}
$$

リンク$a \in L$の所要時間を$\boldsymbol{t}(\boldsymbol{v}) = (t_{a}: a \in L)$で表し，経路所要時間を$\boldsymbol{C} = (C_{k}: k \in K)$で表そう．ある経路$k$の所要時間は，その経路上のリンク所要時間の総和に等しい：
$$
C_{k} = \sum_{a \in L} \delta_{k, a} t_{a}
$$
この関係式は，ベクトルと行列を用いて
$$
\boldsymbol{C} = \boldsymbol{\Delta} \boldsymbol{t}
$$
と表せる．

各リンクの所要時間が当該リンク交通量の非減少関数:
$$
\boldsymbol{t}(\boldsymbol{v}) = (t_{a}(v_{a}): a \in L)
$$
で表されるとしよう．経路交通量$\boldsymbol{x}$に対するリンク交通量を$\boldsymbol{v}(\boldsymbol{x}) = \boldsymbol{\Delta}^{\top} \boldsymbol{x}$で表せば，経路所要時間は，以下の式で表される：
$$\begin{align}
\boldsymbol{C}(\boldsymbol{x}) &=
\boldsymbol{\Delta} \boldsymbol{t}(\boldsymbol{v}(\boldsymbol{x}))\\ & = \boldsymbol{\Delta} \boldsymbol{t}(\boldsymbol{\Delta}^{\top} \boldsymbol{x})
\end{align}$$

## 均衡条件と等価な最適化問題
上記の枠組の下で **Wardropの均衡配分原則** （利用されている経路の所要時間は全て等しく，それより所要時間の大きな経路は利用されない）は，以下のように記述される：
$$\begin{cases}
x_{k}^{\ast} > 0 & \rightarrow C_{k}(\boldsymbol{x}^{\ast}) = \rho^{\ast}\\
x_{k}^{\ast} = 0 & \leftarrow C_{k}(\boldsymbol{x}^{\ast}) > \rho^{\ast}
\end{cases}\qquad \forall k \in K
$$
ここで，$\rho^{\ast}$は均衡状態における起終点ペア$(1, 6)$間の所要時間（均衡所要時間）である．この**経路選択条件**に，以下の**交通量保存則**：
$$
\sum_{k \in K} x_{k}^{\ast} = Q
$$
を加えたものが **均衡条件** である．

一起点・一終点の一般ネットワークを対象とした上述の**均衡配分モデル**もまた，等価な最適化問題に帰着できる．具体的には，上述の均衡条件は，以下の最適化問題の最適性条件と等価である：
$$\begin{align}
\text{[UE]} \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}$$

この最適化問題は，目的関数の定義に経路交通量に対応したリンク交通量$\boldsymbol{v}(\boldsymbol{x})$を用いていることを除けば，2リンクのシンプルなネットワークのものと**本質的には全く同じものである**ことに注意されたい．具体的には，目的関数$f(\boldsymbol{x})$は各リンクの所要時間を0から当該リンクの交通量$v_{a}(\boldsymbol{x})$までの範囲で積分したものであり，制約条件は交通量保存則と交通量の非負制約のみである．

目的関数の勾配は，微分の連鎖則$$\begin{align}
\frac{\partial}{\partial x_{k}} &= \sum_{a \in L} \frac{\partial v_{a}}{\partial x_{k}} \frac{\partial}{\partial v_{a}}\\ &=
\sum_{a \in L} \delta_{k, a} \frac{\partial}{\partial v_{a}}
\end{align}$$
を用いれば以下のように求められる：
$$\begin{align}
\frac{\partial f}{\partial x_{k}} &=
\sum_{a \in L} \delta_{k, a} \frac{\partial f}{\partial v_{a}}(\boldsymbol{x})\\
&= \sum_{a \in L} \delta_{k, a} t_{a}(\boldsymbol{v}(\boldsymbol{x})) = C_{k}(\boldsymbol{x})
\end{align}$$

このことから，交通量保存則
$$
g(\boldsymbol{x}) = \sum_{k \in K} x_{k} - Q = 0
$$
に対する Lagrange 乗数を$\rho$とおけば，上述の最適化問題[UE]に対する**最適性条件**(KKT条件)は，
$$
\begin{align}
&\begin{cases}
x_{k} > 0 & \rightarrow C_{k}(\boldsymbol{x}) = \rho\\
x_{k} = 0 & \leftarrow C_{k}(\boldsymbol{x}) > \rho
\end{cases}\qquad \forall k \in K\\
&
\sum_{k \in K} x_{k} - Q = 0
\end{align}
$$
と求められる．これは，Wardropの均衡条件に他ならない．

## 多起点・多終点ネットワークの場合

ここまで例では起終点のペアが1つだけであるとしたが，実際の交通ネットワークは，複数の起終点ペアについて，それぞれ異なる交通需要が発生する（例えば，長町から仙台駅への利用者や泉中央から青葉山への利用者など）．上述の利用者均衡配分モデルと等価な最適化問題への帰着は，このような多起点・多終点ネットワークにも容易に拡張できる．

その具体的なロジックは以下の通りである：
1. 起終点ペアの集合を
$W = \left( (r_{1}, s_{1}), \cdots, (r_{\mathrm{W}}, s_{\mathrm{W}}) \right)$で表し，各起終点ペア$(r, s) \in W$についての交通需要を所与の定数$Q^{rs}$で表す．起終点$(r, s)$の経路交通量を$\boldsymbol{x}^{rs} = (x_{k}^{rs}: k \in K^{rs})$で表すとき，交通量保存則は
$$
\sum_{k \in K^{rs}} x_{k}^{rs} = Q^{rs}
$$
で表される．
2. 起終点ペア$(r, s)$間の経路集合を$K^{rs}$で表し，$(r, s)$間の経路$k$とリンク$a$の接続関係を以下の Kronecker デルタで表す：
$$
\delta_{k, a}^{rs} = \begin{cases}
1 & \text{if path $k$ of $(r, s)$ includes link $a$}\\
0 & \text{otherwise}
\end{cases}
$$
このとき，経路交通量$\boldsymbol{x} = (\boldsymbol{x}^{rs}: (r, s) \in W)$に対応するリンク$a$の交通量は
$$
v_{a} = \sum_{(r,s) \in W} \sum_{k \in K^{rs}} \delta_{k,a}^{rs} x_{k}^{rs}
$$
で表される．この式は，起終点別の経路-リンク接続行列$\boldsymbol{\Delta}^{rs} = [\delta_{k, a}^{rs}]$を用いれば
$$
\boldsymbol{v} = \sum_{(r, s) \in W} (\boldsymbol{\Delta}^{rs})^{\top} \boldsymbol{x}^{rs}
$$
と記述できるし，$\boldsymbol{\Delta}^{rs}$を縦に並べた全経路-リンク接続行列
$$\boldsymbol{\Delta} = \begin{bmatrix}\boldsymbol{\Delta}^{r_{1}s_{1}}\\\vdots\\\boldsymbol{\Delta}^{r_{\mathrm{W}}s_{\mathrm{W}}}\end{bmatrix}$$を用いて
$$
\boldsymbol{v} = \boldsymbol{\Delta}^{\top}\boldsymbol{x}
$$
と表すこともできる．
3. リンク所要時間がリンク交通量の関数
$$\boldsymbol{t}(\boldsymbol{v}) = (t_{a}(v_{a}) : a \in L)$$
で与えられるとき，起終点ペア$(r, s)$の経路所要時間は
$$
C_{k}^{rs} = \sum_{a \in L} \delta_{k, a}^{rs} t_{a}， \quad \forall k \in K^{rs}
$$
で表される．$\boldsymbol{C}^{rs} = (C_{k}^{rs} : k \in K^{rs})$とすれば，
この式は起終点別経路-リンク接続行列を用いて
$$
\boldsymbol{C}^{rs} = \boldsymbol{\Delta}^{rs} \boldsymbol{t}
$$
と表せる．同様に，全起終点ペアについての経路所要時間$\boldsymbol{C} = (\boldsymbol{C}^{rs} : (r, s) \in W)$ は，全起終点ペアの経路-リンク接続行列を用いて以下のように表せる：
$$
\boldsymbol{C} = \boldsymbol{\Delta} \boldsymbol{t}
$$
4. 複数の起終点ペアが存在する場合，それぞれの起終点ペアについて**Wardropの均衡配分原則**が成立する．すなわち，均衡条件は，起終点ペア$(r, s)$ごとに定義された均衡所要時間$\rho^{rs}$を用いて，
$$
\begin{align}
&\begin{cases}
x_{k}^{rs} > 0 & \rightarrow C_{k}^{rs}(\boldsymbol{x}) = \rho^{rs}\\
x_{k}^{rs} = 0 & \leftarrow C_{k}^{rs}(\boldsymbol{x}) > \rho^{rs}
\end{cases}\qquad \forall k \in K^{rs}, \forall (r, s) \in W\\
&
\sum_{k \in K^{rs}} x_{k}^{rs} - Q^{rs} = 0, \quad \forall (r, s) \in W
\end{align}
$$
と表される．この利用者均衡配分の等価最適化問題は，制約条件のみを多起点・多終点に書き換えた以下の問題として定式化される：
$$\begin{align}
\text{[UE-multi]} \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^{rs}} x_{k}^{rs} = Q^{rs}, \quad \forall (r, s) \in W\\
&x_{k}^{rs} \geq 0, \quad \forall k \in K^{rs}, \forall (r, s) \in W
\end{align}$$
この最適性条件が多起点・多終点均衡配分条件と等価であることは
$$
\frac{\partial f}{\partial x_{k}^{rs}} = \sum_{a \in L} \frac{\partial v_{a}}{\partial x_{k}^{rs}} \frac{\partial f}{\partial v_{a}} = \sum_{a \in L} \delta_{k}^{rs} t_{a} = C_{k}^{rs}, \quad \forall k \in K^{rs}, \forall (r,s) \in W
$$
となることより明らか．

# システム最適交通配分
利用者均衡配分モデルは「各利用者が自らにとって最適な経路を**利己的(selfish)に**選択する」ことを仮定している．このとき，リンク所要時間が交通量とともに増加する場合**ネットワーク全体の総走行時間**は**最小化されない**．換言すれば「**個々の利用者にとって最適**な交通パターン」は「**社会全体にとって最適**な交通パターン」ではない．

例えば，冒頭で用いた2リンク・ネットワークにおいて，ネットワーク全体の総走行時間は，
$$\begin{align}
T(\boldsymbol{x}) &= x_{a} t_{a}(x_{a}) + x_{b} t_{b}(x_{b})\\
&= x_{a}^{2} + 10 x_{a} + 3x_{b}^{2} + 4x_{b}
\end{align}$$
であり，$x_{a}+x_{b} = 10$を代入すれば
$$
T(x_{a}) = x_{a}^{2} + 10 x_{a} + 3(10-x_{a})^{2} + 4(10-x_{a})
$$
であるから，$\boldsymbol{x} > \boldsymbol{0}$を仮定した時の$x_{a}$についての最適性条件は
$$
T'(x_{a}) = 2x_{a} + 10 - 6(10-x_{a}) - 4 = 0
$$
となり，その解は$x_{a} = \frac{27}{4}$と求められる．
$(x_{a}, x_{b}) = (6.75, 3.25)$における各リンクの所要時間は，それぞれ，
$$\begin{align}
t_{a}(6.75) &= 16.75, &
t_{b}(3.25) &= 13.75
\end{align}$$
であるから，総走行時間は
$$
T(6.75, 3.25) = 6.75\times 16.75 + 3.25\times 13.75 = 157.75
$$
となり，均衡状態$(6,4)$における総走行時間
$$
T(6,4) = 10 \times 16 = 160
$$
よりも小さくなっている．以下では，ネットワーク全体の総走行時間を最小化する交通量を**システム最適(SO: system optimal)** (交通)配分 と呼び
$$
\boldsymbol{x}^{SO} = (x_{a}^{SO}, x_{b}^{SO}) = (6.75, 3.75)
$$
で表す．一方，**利用者均衡(UE: user equilibrium)** (交通)配分をシステム最適配分と明示的に区別する必要がある場合には
$$
\boldsymbol{x}^{UE} = (x_{a}^{UE}, x_{b}^{UE}) = (6, 4)
$$

### 一般的なシステム最適配分
一般的な（一起点・一終点）ネットワークを対象としたシステム最適配分モデルは，以下の非線形最適化問題として定式化できる：
$$\begin{align}
\text{[SO]} \quad
\min_{\boldsymbol{x}} T(\boldsymbol{x}) &= \sum_{a \in L} v_{a}(\boldsymbol{x}) t_{a}(\boldsymbol{v}(\boldsymbol{x})) \\
\text{s.t.} \quad &
\sum_{k \in K} x_{k} = Q\\
&x_{k} \geq 0, \quad \forall k \in K
\end{align}$$

目的関数の勾配が
$$
\frac{\partial T}{\partial x_{k}} = \sum_{a \in L} \frac{\partial v_{a}}{\partial x_{k}}\frac{\partial T}{\partial v_{a}}
= \sum_{a \in L} \delta_{k, a} \left\{t_{a}(v_{a}(\boldsymbol{x})) + v_{a}(\boldsymbol{x}) t_{a}^{\prime}(v_{a}(\boldsymbol{x}))\right\}
$$
であることにすれば，その最適性条件は，
$$
\begin{align}
&\begin{cases}
x_{k} > 0 & \rightarrow \hat{C}_{k}(\boldsymbol{x}) = \rho\\
x_{k} = 0 & \leftarrow \hat{C}_{k}(\boldsymbol{x}) > \rho
\end{cases}\qquad \forall k \in K\\
&
\sum_{k \in K} x_{k} - Q = 0
\end{align}
$$
で表される．ここで，
$$\begin{align}
\hat{C}_{k}(\boldsymbol{x}) &= \sum_{a \in L} \delta_{k, a} \hat{t}_{a}(\boldsymbol{v}(\boldsymbol{x}))\\
&=\sum_{a \in L} \delta_{k, a} \left\{t_{a}(v_{a}(\boldsymbol{x})) + v_{a}(\boldsymbol{x}) t_{a}^{\prime}(v_{a}(\boldsymbol{x}))\right\}\end{align}$$

### システム最適配分と利用者最適配分の違い
システム最適配分と利用者均衡配分の違いを深く理解するために，以下の関係に注目しよう：
$$
x_{a} t_{a}(x_{a}) = \int_{0}^{x_{a}} \left\{t_{a}(\omega) + \omega\ t_{a}^{\prime}(\omega)\right\}\mathrm{d} \omega, \quad \forall a \in L
$$
すなわち，あるリンク$a$の総走行時間$x_{a} t_{a}(x_{a})$は，$t_{a}(x_{a}) + x_{a} t_{a}^{\prime}(x_{a})$なる関数を$[0, x_{a}]$の範囲で積分したものに等しい．このことは，
$$
\frac{\mathrm{d}}{\mathrm{d} x_{a}} (x_{a} t_{a}(x_{a})) = (x_{a} t_{a}(x_{a}))^{\prime} = t_{a}(x_{a}) + x_{a} t_{a}^{\prime}(x_{a})
$$
からも明らかである．従って，下図のように，各リンクの総走行時間は
- 緑の四角で囲われた領域$x_{a}t_{a}(x_{a})$および赤の四角で囲われた領域$x_{b}t_{b}(x_{b})$
- $t_{a} + x_{a} t_{a}^{\prime}$ (青点線)および$t_{b} + x_{b} t_{b}^{\prime}$ (橙点線)をそれぞれ積分した領域

の**いずれとしても** 表せる．
<div style="text-align:center; padding:20pt">

</div>

そして，利用者均衡配分と等価な最適化問題の関係から明らかなように，総走行時間を最小化する交通量は（$\boldsymbol{x} > \boldsymbol{0}$ならば），下図のように，$t_{a}(x_{a}) + x_{a} t_{a}^{\prime}(x_{a})$(青点線)と$t_{b} + x_{b} t_{b}^{\prime}$ (橙点線)が交わる点である．
<div style="text-align:center; padding:20pt">

</div>

いま，一般的なネットワークにおける**利用者均衡問題**の目的関数：
$$
f(\boldsymbol{x}) = \sum_{a \in L}
\int_{0}^{v_{a}(\boldsymbol{x})} t_{a}(\omega) \mathrm{d} \omega
$$
と**システム最適配分**の目的関数
$$\begin{align}
T(\boldsymbol{x}) &= \sum_{a \in L} v_{a}(\boldsymbol{x}) t_{a}(\boldsymbol{v}(\boldsymbol{x}))\\
&=
\int_{0}^{v_{a}(\boldsymbol{x})}
\left\{t_{a}(\omega) + \omega t_{a}^{\prime}(\omega) \right\}\mathrm{d} \omega
\end{align}$$
を比較すると，前者は積分される関数が$t_{a}(v_{a})$であるのに対し，後者は
$$
\hat{t}_{a}(v_{a}) = t_{a}(v_{a}) + v_{a} t_{a}^{\prime}(v_{a})
$$
である点である．言い換えれば **システム最適配分**は，リンク所要時間関数を$\hat{t}_{a}$に置き換えた場合の**利用者均衡配分**に他ならない．つまり，もしリンク所要時間が$\hat{t}_{a}$に置き換えられたならば**個々の利用者の利己的な行動に任せておくことで，社会的に望ましい（システム最適配分）が実現する**のである．

では，利用者均衡配分とシステム最適配分との唯一の違いである
$$
\hat{t}_{a}(v_{a}) - t_{a}(v_{a}) = v_{a} t_{a}^{\prime}(v_{a})
$$
は，一体何を意味しているのだろうか？この式は次の2つの項：
- $v_{a}$: リンク$a$の利用者数
- $t_{a}^{\prime}(v_{a}) = \lim_{h\rightarrow 0}\frac{t_{a}(v_{a}+h)-t_{a}(v_{a})}{h}$: リンク$a$の交通量が$v_{a}$からほんの少し増えた時(i.e. 誰かが新しくリンク$a$に流入した時)の所要時間の増分

の積である．つまり，$v_{a}t_{a}^{\prime}(v_{a})$は「新しく誰かがリンク$a$に流入しようとした時に，他の$v_{a}$だけの利用者に(所要時間の増加として)かける**迷惑コスト**」と解釈できる．そして，$\hat{t}_{a}$は「**迷惑コスト込みを上乗せしたリンク所要時間**」と解釈でき，リンク所要時間を$\hat{t}_{a}$で置き換えた時の利用者均衡配分がシステム最適配分となるのは「**各利用者が他者への"迷惑コスト"を考慮した利他的な経路選択を行うならば，社会的に最適な状態が実現する**」ことを意味している．

このように「個人の利己的行動によって他者が迷惑を被る（混雑や環境汚染などの**外部不経済**が存在する）」ような状況において，「他者への迷惑料」を「各個人のコストに上乗せする」ことで社会的に望ましい状態が(自然に)実現するという考え方は，経済学の分野では，提案者であるイギリスの経済学者 [Pigou](https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%BC%E3%82%B5%E3%83%BC%E3%83%BB%E3%82%BB%E3%82%B7%E3%83%AB%E3%83%BB%E3%83%94%E3%82%B0%E3%83%BC) に因んで **ピグー税(Pigouvian tax)** と呼ばれている．

# 練習問題
図のような，4つのノードと5本のリンクからなるネットワークを考え，起終点ペアを$(1, 4)$とする．
<div style="text-align:center;padding:20pt">

</div>

このネットワークには下記の3本の経路が存在する：
1. 1→2→4 $(a, d)$
2. 1→2→3→4 $(a, c, e)$
3. 1→3→4 $(b, e)$

各リンクの所要時間は，それぞれ，以下の関数で表されるとする：
$$\begin{align}
t_{a}(v_{a}) &= 3 v_{a}, &
t_{b}(v_{b}) &= v_{b}+16, &
t_{c}(v_{c}) &= 2\\
t_{d}(v_{d}) &= v_{d}+16, &
t_{e}(v_{e}) &= 3 v_{3}
\end{align}
$$あるいは，以下の行列$\boldsymbol{D}$およびベクトル$\boldsymbol{e}$：
$$\begin{align}
\boldsymbol{D} &= \begin{bmatrix}
3 \\
& 1\\
& & 0\\
& & & 1\\
& & & & 3
\end{bmatrix},& \boldsymbol{e}&=\begin{bmatrix}0 \\ 16 \\ 2 \\\ 16 \\0
\end{bmatrix}
\end{align}
$$を用いて
$$\boldsymbol{t}(\boldsymbol{v}) = \boldsymbol{D} \boldsymbol{v} + \boldsymbol{e}
$$と書いてもよい．

このとき，以下の問いに応えよ：
1. 経路-リンク接続行列$\Delta \in \mathcal{R}^{3\times 5}$を求めよ
2. 経路交通量$\boldsymbol{x} = (x_{1}, x_{2}, x_{3})$に対する経路費用$\boldsymbol{C}(\boldsymbol{x}) = (C_{1}(\boldsymbol{x}), C_{2}(\boldsymbol{x}), C_{3}(\boldsymbol{x}))$を，
$$\begin{align}
\boldsymbol{C}(\boldsymbol{x}) &= \boldsymbol{H} \boldsymbol{x} + \boldsymbol{g}\\
&= \begin{bmatrix}
H_{11} & H_{12} & H_{13}\\
H_{21} & H_{22} & H_{23}\\
H_{31} & H_{32} & H_{33}
\end{bmatrix}
\begin{bmatrix}x_{1} \\ x_{2} \\ x_{3}
\end{bmatrix} +
\begin{bmatrix}g_{1} \\ g_{2} \\ g_{3}
\end{bmatrix}
\end{align}
$$の形で表せ．ここで，$\boldsymbol{H} \in \mathcal{R}^{3\times 3}$および$\boldsymbol{g} \in \mathcal{R}^{3\times 1}$は，いずれも，$\boldsymbol{D}, \boldsymbol{e}$および$\Delta$より求められる．
3. 起終点の交通需要を$Q=10$とする．利用者均衡問題と等価な最適化問題を導出せよ．
4. 上述の利用者均衡問題の最適性条件(ie. 利用者均衡条件)は
$$\begin{align}
&\begin{cases}
\boldsymbol{x}^{\top} \left\{\boldsymbol{C}(\boldsymbol{x}) - \rho \boldsymbol{1}\right\} = 0\\
\boldsymbol{x} \geq \boldsymbol{0}, \quad \boldsymbol{C}(\boldsymbol{x}) - \rho \boldsymbol{1} \geq \boldsymbol{0}
\end{cases}\\
&\boldsymbol{1}^{\top} \boldsymbol{x} = Q
\end{align}
$$と表せる．ただし，$\rho$は交通量保存則に対する Lagrange乗数（均衡交通費用）であり，$\boldsymbol{1}$は全ての要素が1の3次元列ベクトルである．

いま，均衡解が$\boldsymbol{x} > \boldsymbol{0}$であると仮定すると，この均衡条件は，以下の連立方程式：
$$\begin{align}
\boldsymbol{C}(\boldsymbol{x}) - \rho \boldsymbol{1} = 0\\
\boldsymbol{1}^{\top} \boldsymbol{x} - Q = 0
\end{align}
$$あるいは，$\boldsymbol{C}(\boldsymbol{x}) = \boldsymbol{H}\boldsymbol{x} + \boldsymbol{g}$より
$$\begin{bmatrix}
\boldsymbol{H} & -\boldsymbol{1} \\
\boldsymbol{1}^{\top} & 0
\end{bmatrix}\begin{bmatrix}\boldsymbol{x} \\ \rho
\end{bmatrix} + \begin{bmatrix}\boldsymbol{g}\\-Q\end{bmatrix} = \begin{bmatrix}\boldsymbol{0}\\0\end{bmatrix}
$$と書ける．この連立方程式を解いて均衡状態$(\boldsymbol{x}, \rho)$を求めよ．