城市交通網絡中社會成本的優化上界

毛太田，黃 格，李 勇,2

(1. 湘潭大學 公共管理學院，湖南 湘潭 411105；2. 長沙學院 工商管理系，湖南 長沙 410022)

?

城市交通網絡中社會成本的優化上界

毛太田1，黃 格1，李 勇1,2

(1. 湘潭大學 公共管理學院，湖南 湘潭 411105；2. 長沙學院 工商管理系，湖南 長沙 410022)

在固定需求的交通網絡中，均衡狀態下的網絡流量可能不是社會最優的，為了進一步明確用戶均衡與系統最優之間的關系，通過引入一個與均衡流量社會成本相關的量值，得到城市交通網絡社會成本優化上界的計算公式。結果表明：均衡交通網絡流量模式的社會成本最高為社會最優流量模式的兩倍，也就是說通過有效的控制策略最多可以節約網絡社會成本的一半。

交通工程；城市交通網絡；博弈；流量均衡；社會最優

20世紀80年代以來，我國城市普遍進入了快速發展期。在城市化與機動化的快速推進期，伴隨著車輛飽有量的不斷增加，交通問題逐漸成為眾多城市尤其是大城市的“心腹之患”，交通擁塞等城市病日益嚴重，成為城市可持續發展的重要瓶頸之一。很多學者從交通經濟學[1]、社會學[2]、建筑學[3]等不同的角度對交通擁塞問題進行了分析。從復雜網絡的角度來看，在給定的交通網絡中，網絡的結構和網絡節點的容量是相對固定的，可變化的值為網絡的交通流量，決定交通流量最重要的因素是出行者的數量與分布[4]，當一個交通網絡系統正常運行的時候，根據初行者的需求形成一個網絡流量模式，若每個出行者都擁有理性決策行為，那么網絡流量將出現一種均衡，這種均衡是基于出行者個人行為做出的最優選擇，往往這種均衡并不是系統的最優成本值[5]。筆者將運用網絡博弈論模型來分析網絡流量均衡與網絡社會成本最優值之間的關系，為城市解決交通擁堵提供可借鑒和參考的依據。

1 交通網絡流量的博弈論模型描述

在實際的交通網絡中，有向圖是一種常用的描述方式，圖1為一個典型的交通網絡。其中邊表示道路，節點表示路口。

圖1 一個典型的交通網絡Fig.1 A typical traffic network

1.1 均衡狀態流量模式

利用博弈論的思想來構建網絡流量模型：假設每個司機都要從v1開到vn，每一輛車都有多種可行的路線。這個過程相當于一場博弈，參與者是司機，每個參與者可能的策略是由v1到vn的可能路線，每個參與者得到的回報就是司機行程時間的負數。很容易發現，在這個流量博弈中，一般是沒有占優策略的[6]。每條路線都可能是參與者的最佳選擇，前提是其他參與者選擇另一條路線。

博弈論中的最佳應對即參與人的最佳選擇，而最佳應對過程就是參與人不斷動態調整其選擇策略以求能實現最佳應對的過程，交通流量網絡中參與者的最佳應對過程就是司機為了減少行駛時間而不斷動態調整路線以求能最佳應對當前的情況的過程[7]。定義一個流量模式為每個司機所作出的路線選擇，如果每個司機都對現狀作出了最佳選擇，這個過程終止，就形成了一種均衡狀態的網絡流量模式。

1.2 社會最優流量模式

現實情況下，交通網絡的社會成本不僅包括所有司機的行駛時間，還包括汽油的成本、車輛和路面的損耗等。而在交通擁塞，尤其是上下班高峰期時，相對于其他因素，行駛時間是影響司機選擇的主要因素，加快疏通網絡，縮短擁堵時間是降低整個交通網絡社會成本的關鍵。基于Roughgarden和Tardos等人的研究工作，所有司機的行駛時間和整個網絡的社會成本之間呈正比例線性關系。因此，為方便模型描述，定義一個流量模式的社會成本(Social Cost，以SC表示)是所有司機使用該流量模式產生的行程時間的和xTe(x)[8]，如果該流量模式實現了最小社會成本，就稱該模式為社會最優流量模式。

2 交通網絡社會成本的優化上界

均衡狀態下的網絡流量可能不是社會最優的，需要定量地比較均衡狀態下的流量與最理想的流量。相對而言，社會最優流量模式下的社會成本比較容易描述，即總行程時間xTe(x)，均衡狀態下的社會成本則不能簡單通過當前流量模式產生的社會成本來描述，因為一些最佳應對更新可以使社會成本變低(如出行者離開擁擠的道路更換到一條相對空閑的路段)，但另一些更新也可以使成本變高(如布雷斯悖論情況[9])，這就導致流量模式中的社會成本隨著最佳應對過程的進展而在上升或下降之間浮動，并且它與向均衡狀態發展的過程的之間的關系不明顯。因此，為了跟蹤最佳應對過程，引入潛能(Potential Energy，以PE表示)的概念[10]，假設某一邊e上有x量車在行駛，那么這條邊的潛能為：

PE(e)=Te(1)+Te(2)+…+Te(x)

(1)

一條邊的潛能并不是所有車輛穿過此邊的總行駛時間，而是一種累積的量值。定義一種流量模式的潛能為基于當前在其中行駛的車輛數，所有邊的潛能總和。

跟蹤潛能的變化很簡單，因為流量模式的變化過程也就是一個司機放棄當前的路線，更換到一條新路線的過程[11]。如果把這個過程分成兩步：首先，司機放棄當前路線，暫時離開該系統；然后司機回到系統中選擇一條新的路線，通過觀察這個轉換過程就可以知道潛能的變化。

具體地，有x個司機的邊e的潛能是：

PE(e)=Te(1)+Te(2)+…+Te(x-1)+Te(x)

(2)

當一個司機離開時，部分潛能被釋放，潛能變化為：

PE′(e)=Te(1)+Te(2)+…+Te(x-1)

(3)

因此，邊e的潛能變化為Te(x)，即司機在該邊上的行駛時間。綜合該司機在所有邊上的行駛時間，可以看到一個司機放棄當前路線所釋放的潛能恰巧是該司機當前的行駛時間。同樣，當一個司機選擇一條新的路線，所加入的每一邊e的潛能從PE(e)增加到：

PE″(e)=Te(1)+Te(2)+…+Te(x+1)

(4)

當一個司機改變路線，潛能的凈變化是該司機新的行駛時間減去原來的行駛時間。但是在最佳應對過程中，只有當司機的行駛時間會減少的情況下，他才會改變路線。所以每一次最佳應對更新都產生一個負值的潛能變化。因此，系統中的潛能隨著最佳應對過程的進行而減少，最終停止，形成一個均衡狀態的流量模式。

2.1 一條邊上潛能與行駛時間的關系

基于前面的論述，當一條邊上有x輛車行駛時，潛能為：

PE(e)=Te(1)+Te(2)+…+Te(x)

(5)

另外，x輛車中每輛車的行駛時間為Te(x)，則每條邊上所有車輛的總行駛時間(以T(e)表示)為：

(6)

由于潛能和總行駛時間都是x項，但行駛時間中的每一項至少應該和潛能中的每一項一樣大。因此：

PE(e)≤T(e)

(7)

圖2展示了當Te是一個線性函數時，潛能和總行駛時間之間的對比關系：總行駛時間為水平線以下的陰影部分的面積，Y值為Te(x)，而潛能則是高度分別為Te(1)，Te(2)，…，Te(x)，寬度為一個標準單位的所有長方形的面積。

圖2 潛能和總行駛時間關系的幾何圖示Fig.2 Geometric illustration of relationship between potential energy and total traveling time

圖2供了一個幾何圖示，由于Te(x)=αex+βe(αe,βe≥0)，可以得到：

(8)

以潛能和總行駛時間的形式來表述，得到：

(9)

2.2 均衡狀態行駛時間與社會最優行駛時間關系

當所有司機都遵循社會最優流量模式A時，所有邊的總潛能為PE(A)，該流量模式中的社會成本記為SC(A)，也就是所有司機行駛時間的總和∑T(e)。

根據前面的論述，潛能隨著最佳應對過程而減少，因此，均衡狀態流量模式的總潛能：

PE(A′)≤PE(A)

(10)

其次，根據潛能和社會成本之間的數量關系：

SC(A′)≤2PE(A′)

(11)

并且，PE(A)≤SC(A)

(12)

因此：

(13)

這就證明了最佳應對過程中潛能逐步減少，這種減少致使社會成本的增加限定在兩倍之內。因此，交通網絡社會成本的優化上界是社會最優流量模式社會成本的兩倍。

3 案例分析

建立一個交通運輸網絡如圖3。圖3中，邊表示道路，節點表示路口，每個司機都要從V1開到V4[7]。假設V1-V3和V2-V4邊并不受交通狀況影響，無論有多少輛車行駛都需要4個單位的時間穿越。相比之下，V1-V2和V3-V4邊受擁堵的影響較大，其行駛時間Te(x)=αex+βe，是為了使模型更簡單化，設置該兩條路線的行駛時間為x，V2-V3的行駛時間為0，盡管由此產生的效果有別于實際情況(但影響應該很小)。

圖3 案例網絡Fig.3 Network of the case

假設有4個司機，每個司機的起節點為V1，訖節點為V4，圖4展示了基于圖3兩種不同的流量模式。第一個流量模式如圖4(a)，該模式達到了最小社會成本，即每個司機需要8個單位時間到達目的地，因此社會成本為SC(A)=4×(2+4)=24，是社會最優流量模式。第二個流量模式圖4(b)是唯一的納什均衡，它的社會成本較高，SC(A′)=4×(4+4)=32。

圖4 兩種網絡流量模式Fig.4 Network traffic of two different modes

根據前面的假設，建立博弈矩陣如表1，通過3×3表格的行代表一部分出行者3種路線選擇，V1-V2-V4，V1-V3-V4以及V1-V2-V3-V4，也同樣通過3×3表格的列代表另外一部分出行者的3種路線選擇，出行者的回報是所消耗的行駛時間的負值。

表1 該流量模式中出行者之間的博弈

由該博弈矩陣發現，其中并沒有占優策略，V1-V2-V3-V4是該博弈中唯一的納什均衡，選擇這條路線是每個司機最佳應對。利用潛能跟蹤從圖4(a)模式轉變到圖4(b)模式的最佳應對過程，由PE(e)=Te(1)+Te(2)+…+Te(x)計算得出了網絡從社會最優向均衡交通進展時的潛能變化，圖5展示了最佳應多過程經歷的5個流量模式，并列出了每條邊的潛能。

圖5 最佳應對過程的追蹤Fig.5 Track of best-response dynamics progress

圖5中，(a)流量模式社會成本最小，是社會最優流量模式，其社會成本SC(a)=24，潛能PE(a)=22，從(b)開始，每一步變更一個司機的路線到V1-V2-V3-V4；(b)模式的社會成本SC(b)=25，潛能PE(b)=21；(c)模式的社會成本SC(c)=28，潛能PE(c)=21；(d)模式的社會成本SC(d)=29，潛能PE(d)=20；(e)模式的潛能最小，是均衡狀態流量模式，其社會成本SC(e)=32，潛能PE(e)=20。

容易發現，盡管在5個流量模式中社會成本在增加(從24增加到32)，潛能卻在不斷減少(從22到20)。圖6進一步細分了司機更換路線的過程，分為兩個步驟：第一步，司機放棄當前路線，暫時離開系統，表現為從圖6(a)向圖6(b)轉變，放棄之前的路線釋放了2+4=6個單位的潛能；第二步，司機重新回到系統選擇一條新路線，也就是圖6(b)向圖6(c)的變化，司機選擇之字形路線后，只有2+0+3=5個潛能回到系統中，因此潛能減少了1個單位。

圖6 潛能的釋放與增加Fig.6 Release and increase of potential energy

當一個司機為了其他路線而放棄當前路線時，潛能的改變就是司機行駛時間的改善。因此，系統增加的潛能等同于該司機當前的行駛時間。

再分析一條邊的潛能與行駛時間的關系。因為該模型中只有V1-V2和V3-V4邊受擁堵的影響，其行駛時間Te(x)=αex+βe=x，所以以V1-V2邊為例。該邊的潛能為：

PE(e)=1+2=3

(14)

行駛時間為：

T(e)=2×2=4

(15)

因此：

(16)

一個流量模式中的社會成本就是所有司機行駛時間的總和，因此，均衡狀態下的社會成本和社會最優流量模式下的社會成本之間的關系也就是總潛能和總行駛時間的關系。在本案例中表現為圖4(a)社會最優流量模式和圖4(b)均衡狀態中總行駛時間和總潛能的對比。以SC(a)表示(a)流量模式下的社會成本，以PE(a)表示(a)流量模式下的潛能，根據式17易算得：

(17)

以SC(b)表示(b)流量模式下的社會成本，以PE(b)表示(b)流量模式下的潛能，由于潛能隨著如圖6所示的最佳應對過程逐步減少，(a)流量模式的總潛能PE(a)=22，(b)模式的總潛能PE(b)=20，因此：

PE(b)

(18)

其次，(b)模式的社會成本SC(b)=32，潛能PE(b)=20，得：SC(b)<2PE(b)=40

(19)

將這些不等式聯系起來，得到：

(20)

最佳應對過程中潛能逐步減少，這種減少致使社會成本的增加限定在兩倍之內。

4 結 語

筆者運用博弈論的方法對交通網絡中出行者的行為和網絡流量進行分析，通過計算發現均衡交通網絡流量模式的社會成本最高為社會最優流量模式的兩倍，該值為交通網絡社會成本的可優化上界，也就是說通過有效的控制策略最多可以節約網絡社會成本的一半。

[1] 韓小亮,鄧祖新.城市交通擁堵的經濟學分析——基于計算經濟學的模擬檢驗[J].財經研究,2006,32(5):19-31. Han Xiaoliang,Deng Zuxin.The economic analysis of traffic congestions——an agent-based computational economics approach[J].Journal of Finance and Economics,2006,32(5):19-31.

[2] 王煜.交通擁堵現象背后的社會問題[J].城市問題,2004(2):76-78. Wang Yu.Social problems behind the traffic jam phenomenon[J].Urban Problems,2004(2):76-78.

[3] 李迅,張國華,黃坤鵬.中國城市交通發展的綠色之路[J].城市規劃學刊,2008(6):51-56. Li Xun,Zhang Guohua,Huang Kunpeng,The green way to the development of Chinese urban transportation[J].Urban Planning Forum,2008(6):51-56.

[4] Roughgarden T,Tardos é.How bad is selfish routing? [J].Journal of the ACM,2002,49(2):236-259.

[5] Anshelevich E,Dasgupta A,Kleinberg J,et al.The price of stability for network design with fair cost allocation[J].SIAM Journal on Computing,2008,38(4):1602-1623.

[6] Easley D,Kleinberg J.Networks,Crowds and Markets[M].Cambridge:Cambridge University Press,2010:229-230.

[7] 余孝軍.一類混合路由博弈的調和率研究[J].應用數學和力學,2013,34(4):420-426. Yu Xiaojun.On coordination ratio of a mixed routing game[J].Applied Mathematics and Mechanics,2013,34(4):420-426.

[8] Roughgarden T.Selfish Routing and the Price of Anarchy[M].MIT press,2005:16-17.

[9] Braess D.Uber ein Paradoxon aus der Verkehrsplanung[J].Unternehmensforschung,1968,12(1):258-268.

[10] Monderer D,Shapley L S.Potential games[J].Games and economic behavior,1996,14(1):124-143.

[11] 徐寅峰,余海燕,蘇兵,等.基于時間和路徑偏好的交通流分配模型與誘導策略[J].系統工程理論與實踐,2012,32(10):2306-2314. Xu Yinfeng,Yu Haiyan,Su Bing,et al.Traffic flow distribution models based on time and path preference and inducement strategy[J].Systems Engineering Theory & Practice,2012,32(10):2306-2314.

Upper Bound of Social Cost Optimization in Urban Traffic Networks

Mao Taitian1, Huang Ge1, Li Yong1,2

(1. School of Public Management, Xiangtan University, Xiangtan 411105, Hunan, China; 2. Department of Business Management, Changsha University, Changsha 410022, Hunan, China)

Existing research shows that network traffic at equilibrium may not be socially optimal in traffic networks with fixed demands. In order to further clarify the relationship between user equilibrium and system optimum flow patterns, new formula for computing the upper bound of social cost optimization in urban traffic networks was derived through introducing an alternate quantity associated with the user social cost of equilibrium flow pattern. The results show that the social cost of the equilibrium is twice the cost of the social optimum at most; hence the social cost of the network can be halved through an effective control strategy at most.

traffic engineering; urban traffic networks; game; traffic at equilibrium; social optimum

10.3969/j.issn.1674-0696.2015.02.26

2014-04-10；

2014-06-29

國家自然科學基金項目(71101013)；湖南省教育廳優秀青年項目(11B013)

毛太田(1971—)，男，湖南永州人，副教授，博士，主要從事信息資源管理方面的研究。E-mail: maotaitian@xtu.edu.cn。

U491

A

1674-0696(2015)02-124-04