淺談交通網路分析中的隨機用戶均衡模型（一）：從經典的用戶均衡與系統最優說起

02-07

城市交通的出行者是交通網路分析的對象，在數據資源日益豐富的背景下，如何更好地理解人類出行活動（human mobility）面臨著挑戰，同時，在不同的道路、交通、控制和環境條件下，簡單地將交通現象進行回歸分析或是採用經驗公式來逼近現實並不能很好地從本質上理解交通，唯有從成因出發，探尋因果關係才能使得交通模型具有物理意義和可解釋性。故此，理解基本且經典的交通模型有利於我們更好地利用交通數據來挖掘城市出行的潛在規律。

在經典的交通模型中，一般從路段、路徑和OD（Origin-Destination，起點-終點）三個層面進行交通網路分析，相應地，交通網路分析過程也就伴隨著路段流量、路徑流量和OD流量的估計問題，最初的做法是假設每個出行者在相應出行的OD對間能夠找到出行時間最短的路徑，即構成了用戶均衡（user equilibrium, 簡稱UE）。但在現實生活中，每個出行者無法準確知道路網的實時交通狀況，並且精準地感知實際的行駛時間，這種情況下，出行者就存在一種感知時間（perceived time）和實際時間（actual time）之間的偏差，利用這種偏差的統計學假設，相應地就有了隨機用戶均衡（stochastic user equilibrium, 簡稱SUE）。

對隨機用戶均衡有一定了解的讀者可能都有過這樣一種體驗，即在閱讀與隨機用戶均衡相關的文獻或著作時，可能會被一連串抽象的公式和符號弄得暈頭轉向，那麼如何避免在閱讀過程中出現類似的情況呢？為了提高可讀性，這裡對符號進行了簡單的歸納，即經常會出現在上下標裡面的符號依次是 $r$ （OD對起點）， $s$ （OD對終點）， $k$ （路徑編號）和 $a$ （路段編號），相應地，也有 $q$ （OD流量）， $f$ （路徑流量）， $x$ （路段流量）和 $t$ （路段行駛時間）。

1 用戶均衡模型

在這裡，為什麼要先介紹用戶均衡呢？

前面說了隨機用戶均衡是建立在出行者感知到的行駛時間存在一定偏差的基礎上，那麼當這種偏差等於0時，則每個出行者在相應出行的OD對間能夠找到實際時間最短的路徑，這也就說明了用戶均衡實際上是隨機用戶均衡的一個特例。下面來具體介紹一下用戶均衡模型。

對於出行者選擇行駛時間最短的路徑這一行為，我們可以抽象地將其表達為求解個人出行成本最小化問題，給定一個交通網路 $A$ ，將路段 $ain A$ 在路段流量為 $x_a$ 下的行駛時間記為 $t_aleft( x _a ight)$ 來表示成本（cost）， $t_aleft( x _a ight)$ 也被稱為路阻函數（link performance function），隨著流量的增加，行程時間也會相應地增加，主觀上，這種出行成本-流量的關係是符合實際的交通規律。

用戶均衡模型的目標函數是每一條路段路阻函數積分的累加，可以寫成如下形式：

$min Z =sum_{ain A}{int_{0}^{x_a} t_aleft( w ight)dw }$

然而，比較遺憾的是，這個目標函數並沒有一個直觀的經濟學或行為學解釋，只能將其看成一個嚴格的數學表達式以用來解決均衡問題。

值得一提的是，在交通中，路阻函數要體現出交通擁堵規律，通常要求其要具備非線性，並嚴格地隨著流量遞增等性質（nonlinear, positive, and strictly increasing with flow）。最為經典的路阻函數表達式是標準的BPR（Bureau of Public Road，美國聯邦公路局）模型，即

$t_aleft( x_a ight) =t_{a}^{f} left[ 1+0.15left( frac{x_a}{C_a} ight)^4 ight]$

其中， $t_{a}^{f}$ 表示路段 $a$ 在自由流狀態（交通量極小，車輛可以「自由」行駛的狀態）下的行駛時間， $C_a$ 是指路段 $a$ 的通行能力。另外，BPR模型裡面的0.15和4是可以變化，當然，也可以定義其他形式的路阻函數。

接下來，考慮到路段流量、路徑流量和OD流量存在一定的轉換關係，因此，可以從三者轉換關係出發來分析用戶均衡模型的約束條件。

首先，路徑和OD之間存在流量的恆等約束，即在一個OD對上，所有路徑的流量之和應等於OD流量，用 $q^{rs}$ 表示OD對 $left( r,s ight)$ 的流量，若將OD對 $left( r,s ight)$ 上第 $k$ 條路徑的流量記為 $f_{k}^{rs}$ ，則

$q^{rs}=sum_{l}{f_{l}^{rs} } ,forall r,s$

其中，公式中出現的 $l$ 是路徑流累加的下標，為了避免混淆，下面在關於路徑流累加的求和公式中都用 $l$ 來代替 $k$ 。

其次，路段和路徑之間存在流量的恆等約束，即在一個路段上，對於所有通過該路段的路徑，其流量之和等於該路段的流量，但是在這裡需要先引入一個0-1變數來表達路段-路徑的關聯關係，用 $delta _{ak}^{rs} =1$ 表示OD對 $left( r,s ight)$ 上的第 $k$ 條路徑經過路段 $a$ ，若 $delta _{ak}^{rs} =0$ ，則第 $k$ 條路徑不經過路段 $a$ ，這樣，路段-路徑恆等約束可以寫成：

$x_a=sum_{rs}{sum_{l}{f_{l}^{rs} delta _{al}^{rs} } }, a in A$

最後是路段流量和路徑流量的非負約束，即

$x_{a} geq 0,a in A$

$f_{k}^{rs} geq 0, forall r,s,k$

用戶均衡模型也可以用來描述出行者在路徑選擇上的「自私」行為，即每個出行者都希望自己能夠走最快的路。說到這裡，接下來就不得不介紹一下與用戶均衡模型同樣經典的系統最優（system optimal, 簡稱SO）模型。

2 系統最優模型

2016年3月，麻省理工學院的馬爾塔·岡薩雷斯（Marta C. González）等在著名期刊《自然-通訊》上發表了一篇題為《Understanding congested travel in urban areas》的論文，文中介紹了一個有趣的組合模型恰好便於此處同時理解用戶均衡模型和系統最優模型。

如果將路段的行駛時間視為成本（cost），即 $c_{a}left( x_{a} ight) =t_{a}left( x_{a} ight)$ ，則一條路段所承擔的流量 $x_{a}$ 發生變化時對該路段上所有車輛總的行駛時間 $x_{a}t_{a} left ( x_{a} ight)$ 的影響可理解為一種邊際成本（marginal cost，經濟學概念），即 $c_{a}left( x_{a} ight) =frac{dleft[ x_{a}t_{a} left ( x_{a} ight) ight] }{dx_{a} }$ 。將成本和邊際成本賦予權重 $lambdain left[ 0,1 ight]$ ，則

$c_{a}^{lambda}left( x_{a} ight) =left( 1-lambda ight) t_{a}left( x_{a} ight) +lambda frac{dleft[ x_{a}t_{a} left ( x_{a} ight) ight] }{dx_{a} }$

將 $c_{a}^{lambda}left( x_{a} ight)$ 替換用戶均衡模型的目標函數中的 $t_{a}left( x_{a} ight)$ ，則目標函數 $Z$ 為

$Z =sum_{ain A}{int_{0}^{x_a} c_{a}^{lambda}left( w ight) dw }$

$=sum_{ain A}{int_{0}^{x_a} left{ left( 1-lambda ight)t_{a} left( w ight) +lambda frac{dleft[ x_{a}t_{a} left ( w ight) ight] }{dw } ight} dw }$

$=left( 1-lambda ight)sum_{ain A}{int_{0}^{x_a} t_{a}left( w ight) dw } +lambdasum_{ain A}x_{a} t_{a}left( x_{a} ight)$

在該目標函數中， $lambda=0$ 對應著用戶均衡模型，而 $lambda=1$ 時的目標函數 $Z=sum_{ain A}x_{a} t_{a}left( x_{a} ight)$ 表示網路上所有車輛總的行駛時間，對這個目標函數做優化恰好就得到了我們想要的系統最優模型。另外，系統最優模型的約束條件與用戶均衡模型完全相同。這樣，系統最優模型的完整表達式可以寫成：

$min Z=sum_{ain A}x_{a} t_{a}left( x_{a} ight)$

s.t. $q^{rs}=sum_{l}{f_{l}^{rs} } ,forall r,s$

$x_a=sum_{rs}{sum_{l}{f_{l}^{rs} delta _{al}^{rs} } }, a in A$

$x_{a} geq 0,a in A$

$f_{k}^{rs} geq 0, forall r,s,k$

綜上所述，用戶均衡是個體出行者追求自身利益最大化所導致的平衡狀態，而系統最優是通過犧牲某些個體出行者的利益從而達到系統效率最佳的平衡狀態，模型框架的簡圖見圖1。通過調整權重 $lambda$ 可以巧妙地分析兩種平衡狀態，當 $lambda=1$ 時的系統最優也可以用來評估城市交通網路對車輛的承載能力。

圖1 用戶均衡與系統最優兩大模型的框架簡圖

3 一個簡單路網的流量分配實例

為了更容易地理解用戶均衡與系統最優，這裡用《understanding congested travel in urban areas》（鏈接：Understanding congested travel in urban areas）一文中所給出的例子（如圖2所示，由5條路段、3條路徑、1個OD對構成的交通網路）來做流量分配（註：以下僅採用用戶均衡模型），不過在原文的公式(4)中有一處編輯錯誤，公式(4)中的目標函數應該更正為 $min sum_{ein E}{int_{0}^{x_e} c_{e}^{lambda}left( w ight) dw }$ 。

圖2 示例的交通網路

已知條件：在圖2所示的小路網上，有100輛車從A地出發駛往D地，每條路段上的標籤表示與流量相關的行駛時間（即路阻函數，此處不是BPR模型）。

分析過程：

第一步：確定各條路段的行駛時間為 $t_{AB}left( x_{AB} ight) =1+frac{x_{AB}}{100}$ ， $t_{AC}left( x_{AC} ight) =2$ ， $t_{BC}left( x_{BC} ight) =0.25$ ， $t_{BD}left( x_{BD} ight) =2$ ， $t_{CD}left( x_{CD} ight)=1+frac{x_{CD}}{100}$ 。

第二步：確定目標函數為

$Z=left( x_{AB}+frac{1}{200}x_{AB}^{2} ight) +2x_{AC}+frac{1}{4} x_{BC}+2x_{BD}+left( x_{CD}+frac{1}{200} x_{CD}^2 ight)$

第三步：確定約束條件為

$f_{ABD}^{AD}+f_{ACD}^{AD}+f_{ABCD}^{AD}=q^{AD}=100$

$x_{AB}=f_{ABD}^{AD}+f_{ABCD}^{AD}$

$x_{AC}=f_{ACD}^{AD}$

$x_{BC}=f_{ABCD}^{AD}$

$x_{BD}=f_{ABD}^{AD}$

$x_{CD}=f_{ACD}^{AD}+f_{ABCD}^{AD}$

$x_{AB},x_{AC},x_{BC},x_{BD},x_{CD}geq 0$

$f_{ABD}^{AD},f_{ACD}^{AD},f_{ABCD}^{AD}geq 0$

第四步：求解該凸規劃模型（本例模型可用序列二次規劃求解），OD流量分配到各條路徑的結果是

$f_{ABD}^{AD}=f_{ACD}^{AD}=25$ ， $f_{ABCD}^{AD}=50$

與原文所給例證結果是一致的。

4 回顧：用戶均衡與系統最優的提出

上面介紹了用戶均衡與系統最優兩大模型，而這兩大模型的出現正是源於現實的可觀察性和理論的可研究性，接下來我們來簡單地看看這兩大模型的發展過程。

1952年，Wardrop提出了兩種網路流量分配原則，即用戶均衡（假設條件：All travellers are minimizing their own travel cost）和系統最優（假設條件：The travellers choose their routes so as to minimize the total travel time in the transportation system），儘管用戶均衡原理是由經濟學家Knight最早提出來的（也有說法認為可能是Knight首先使用均衡一詞來解釋交通模式），但運籌與交通領域一般將Wardrop的兩種網路流量分配原則作為交通理論研究的一個重要里程碑。

實際上，Wardrop提出的用戶均衡和系統最優與上面給出來的數學表達式略有不同，現在看到的用戶均衡模型和系統最優模型是由Beckmann等在1956出版的著作《Studies in the Economics of Transportation》給出的，通過使用非線性優化理論，他們將兩大原則寫成了現在我們所看到的形式，即帶有線性約束的凸規劃模型。

5 推薦閱讀

本文主要參考了城市交通網路分析的兩部經典著作，第一部是Yosef Sheffi（現名：Yossi Sheffi）於1985年出版的著作《Urban transportation networks: equilibrium analysis with mathematical programming methods》（鏈接：Urban Transportation Networks:），第二部是Michael Patriksson於1994年出版的著作《The traffic assignment problem: models and methods》。

備註：全文僅僅是讀書筆記，如有不當之處，敬請指正。