城市交通網(wǎng)絡(luò)中社會(huì)成本的優(yōu)化上界

毛太田，黃 格，李 勇,2

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

?

城市交通網(wǎng)絡(luò)中社會(huì)成本的優(yōu)化上界

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

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

在固定需求的交通網(wǎng)絡(luò)中，均衡狀態(tài)下的網(wǎng)絡(luò)流量可能不是社會(huì)最優(yōu)的，為了進(jìn)一步明確用戶(hù)均衡與系統(tǒng)最優(yōu)之間的關(guān)系，通過(guò)引入一個(gè)與均衡流量社會(huì)成本相關(guān)的量值，得到城市交通網(wǎng)絡(luò)社會(huì)成本優(yōu)化上界的計(jì)算公式。結(jié)果表明：均衡交通網(wǎng)絡(luò)流量模式的社會(huì)成本最高為社會(huì)最優(yōu)流量模式的兩倍，也就是說(shuō)通過(guò)有效的控制策略最多可以節(jié)約網(wǎng)絡(luò)社會(huì)成本的一半。

交通工程；城市交通網(wǎng)絡(luò)；博弈；流量均衡；社會(huì)最優(yōu)

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

1 交通網(wǎng)絡(luò)流量的博弈論模型描述

在實(shí)際的交通網(wǎng)絡(luò)中，有向圖是一種常用的描述方式，圖1為一個(gè)典型的交通網(wǎng)絡(luò)。其中邊表示道路，節(jié)點(diǎn)表示路口。

圖1 一個(gè)典型的交通網(wǎng)絡(luò)Fig.1 A typical traffic network

1.1 均衡狀態(tài)流量模式

利用博弈論的思想來(lái)構(gòu)建網(wǎng)絡(luò)流量模型：假設(shè)每個(gè)司機(jī)都要從v1開(kāi)到vn，每一輛車(chē)都有多種可行的路線(xiàn)。這個(gè)過(guò)程相當(dāng)于一場(chǎng)博弈，參與者是司機(jī)，每個(gè)參與者可能的策略是由v1到vn的可能路線(xiàn)，每個(gè)參與者得到的回報(bào)就是司機(jī)行程時(shí)間的負(fù)數(shù)。很容易發(fā)現(xiàn)，在這個(gè)流量博弈中，一般是沒(méi)有占優(yōu)策略的[6]。每條路線(xiàn)都可能是參與者的最佳選擇，前提是其他參與者選擇另一條路線(xiàn)。

博弈論中的最佳應(yīng)對(duì)即參與人的最佳選擇，而最佳應(yīng)對(duì)過(guò)程就是參與人不斷動(dòng)態(tài)調(diào)整其選擇策略以求能實(shí)現(xiàn)最佳應(yīng)對(duì)的過(guò)程，交通流量網(wǎng)絡(luò)中參與者的最佳應(yīng)對(duì)過(guò)程就是司機(jī)為了減少行駛時(shí)間而不斷動(dòng)態(tài)調(diào)整路線(xiàn)以求能最佳應(yīng)對(duì)當(dāng)前的情況的過(guò)程[7]。定義一個(gè)流量模式為每個(gè)司機(jī)所作出的路線(xiàn)選擇，如果每個(gè)司機(jī)都對(duì)現(xiàn)狀作出了最佳選擇，這個(gè)過(guò)程終止，就形成了一種均衡狀態(tài)的網(wǎng)絡(luò)流量模式。

1.2 社會(huì)最優(yōu)流量模式

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

2 交通網(wǎng)絡(luò)社會(huì)成本的優(yōu)化上界

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

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

(1)

一條邊的潛能并不是所有車(chē)輛穿過(guò)此邊的總行駛時(shí)間，而是一種累積的量值。定義一種流量模式的潛能為基于當(dāng)前在其中行駛的車(chē)輛數(shù)，所有邊的潛能總和。

跟蹤潛能的變化很簡(jiǎn)單，因?yàn)榱髁磕Ｊ降淖兓^(guò)程也就是一個(gè)司機(jī)放棄當(dāng)前的路線(xiàn)，更換到一條新路線(xiàn)的過(guò)程[11]。如果把這個(gè)過(guò)程分成兩步：首先，司機(jī)放棄當(dāng)前路線(xiàn)，暫時(shí)離開(kāi)該系統(tǒng)；然后司機(jī)回到系統(tǒng)中選擇一條新的路線(xiàn)，通過(guò)觀察這個(gè)轉(zhuǎn)換過(guò)程就可以知道潛能的變化。

具體地，有x個(gè)司機(jī)的邊e的潛能是：

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

(2)

當(dāng)一個(gè)司機(jī)離開(kāi)時(shí)，部分潛能被釋放，潛能變化為：

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

(3)

因此，邊e的潛能變化為T(mén)e(x)，即司機(jī)在該邊上的行駛時(shí)間。綜合該司機(jī)在所有邊上的行駛時(shí)間，可以看到一個(gè)司機(jī)放棄當(dāng)前路線(xiàn)所釋放的潛能恰巧是該司機(jī)當(dāng)前的行駛時(shí)間。同樣，當(dāng)一個(gè)司機(jī)選擇一條新的路線(xiàn)，所加入的每一邊e的潛能從PE(e)增加到：

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

(4)

當(dāng)一個(gè)司機(jī)改變路線(xiàn)，潛能的凈變化是該司機(jī)新的行駛時(shí)間減去原來(lái)的行駛時(shí)間。但是在最佳應(yīng)對(duì)過(guò)程中，只有當(dāng)司機(jī)的行駛時(shí)間會(huì)減少的情況下，他才會(huì)改變路線(xiàn)。所以每一次最佳應(yīng)對(duì)更新都產(chǎn)生一個(gè)負(fù)值的潛能變化。因此，系統(tǒng)中的潛能隨著最佳應(yīng)對(duì)過(guò)程的進(jìn)行而減少，最終停止，形成一個(gè)均衡狀態(tài)的流量模式。

2.1 一條邊上潛能與行駛時(shí)間的關(guān)系

基于前面的論述，當(dāng)一條邊上有x輛車(chē)行駛時(shí)，潛能為：

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

(5)

另外，x輛車(chē)中每輛車(chē)的行駛時(shí)間為T(mén)e(x)，則每條邊上所有車(chē)輛的總行駛時(shí)間(以T(e)表示)為：

(6)

由于潛能和總行駛時(shí)間都是x項(xiàng)，但行駛時(shí)間中的每一項(xiàng)至少應(yīng)該和潛能中的每一項(xiàng)一樣大。因此：

PE(e)≤T(e)

(7)

圖2展示了當(dāng)Te是一個(gè)線(xiàn)性函數(shù)時(shí)，潛能和總行駛時(shí)間之間的對(duì)比關(guān)系：總行駛時(shí)間為水平線(xiàn)以下的陰影部分的面積，Y值為T(mén)e(x)，而潛能則是高度分別為T(mén)e(1)，Te(2)，…，Te(x)，寬度為一個(gè)標(biāo)準(zhǔn)單位的所有長(zhǎng)方形的面積。

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

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

(8)

以潛能和總行駛時(shí)間的形式來(lái)表述，得到：

(9)

2.2 均衡狀態(tài)行駛時(shí)間與社會(huì)最優(yōu)行駛時(shí)間關(guān)系

當(dāng)所有司機(jī)都遵循社會(huì)最優(yōu)流量模式A時(shí)，所有邊的總潛能為PE(A)，該流量模式中的社會(huì)成本記為SC(A)，也就是所有司機(jī)行駛時(shí)間的總和∑T(e)。

根據(jù)前面的論述，潛能隨著最佳應(yīng)對(duì)過(guò)程而減少，因此，均衡狀態(tài)流量模式的總潛能：

PE(A′)≤PE(A)

(10)

其次，根據(jù)潛能和社會(huì)成本之間的數(shù)量關(guān)系：

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

(11)

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

(12)

因此：

(13)

這就證明了最佳應(yīng)對(duì)過(guò)程中潛能逐步減少，這種減少致使社會(huì)成本的增加限定在兩倍之內(nèi)。因此，交通網(wǎng)絡(luò)社會(huì)成本的優(yōu)化上界是社會(huì)最優(yōu)流量模式社會(huì)成本的兩倍。

3 案例分析

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

圖3 案例網(wǎng)絡(luò)Fig.3 Network of the case

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

圖4 兩種網(wǎng)絡(luò)流量模式Fig.4 Network traffic of two different modes

根據(jù)前面的假設(shè)，建立博弈矩陣如表1，通過(guò)3×3表格的行代表一部分出行者3種路線(xiàn)選擇，V1-V2-V4，V1-V3-V4以及V1-V2-V3-V4，也同樣通過(guò)3×3表格的列代表另外一部分出行者的3種路線(xiàn)選擇，出行者的回報(bào)是所消耗的行駛時(shí)間的負(fù)值。

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

由該博弈矩陣發(fā)現(xiàn)，其中并沒(méi)有占優(yōu)策略，V1-V2-V3-V4是該博弈中唯一的納什均衡，選擇這條路線(xiàn)是每個(gè)司機(jī)最佳應(yīng)對(duì)。利用潛能跟蹤從圖4(a)模式轉(zhuǎn)變到圖4(b)模式的最佳應(yīng)對(duì)過(guò)程，由PE(e)=Te(1)+Te(2)+…+Te(x)計(jì)算得出了網(wǎng)絡(luò)從社會(huì)最優(yōu)向均衡交通進(jìn)展時(shí)的潛能變化，圖5展示了最佳應(yīng)多過(guò)程經(jīng)歷的5個(gè)流量模式，并列出了每條邊的潛能。

圖5 最佳應(yīng)對(duì)過(guò)程的追蹤Fig.5 Track of best-response dynamics progress

圖5中，(a)流量模式社會(huì)成本最小，是社會(huì)最優(yōu)流量模式，其社會(huì)成本SC(a)=24，潛能PE(a)=22，從(b)開(kāi)始，每一步變更一個(gè)司機(jī)的路線(xiàn)到V1-V2-V3-V4；(b)模式的社會(huì)成本SC(b)=25，潛能PE(b)=21；(c)模式的社會(huì)成本SC(c)=28，潛能PE(c)=21；(d)模式的社會(huì)成本SC(d)=29，潛能PE(d)=20；(e)模式的潛能最小，是均衡狀態(tài)流量模式，其社會(huì)成本SC(e)=32，潛能PE(e)=20。

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

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

當(dāng)一個(gè)司機(jī)為了其他路線(xiàn)而放棄當(dāng)前路線(xiàn)時(shí)，潛能的改變就是司機(jī)行駛時(shí)間的改善。因此，系統(tǒng)增加的潛能等同于該司機(jī)當(dāng)前的行駛時(shí)間。

再分析一條邊的潛能與行駛時(shí)間的關(guān)系。因?yàn)樵撃Ｐ椭兄挥蠽1-V2和V3-V4邊受擁堵的影響，其行駛時(shí)間Te(x)=αex+βe=x，所以以V1-V2邊為例。該邊的潛能為：

PE(e)=1+2=3

(14)

行駛時(shí)間為：

T(e)=2×2=4

(15)

因此：

(16)

一個(gè)流量模式中的社會(huì)成本就是所有司機(jī)行駛時(shí)間的總和，因此，均衡狀態(tài)下的社會(huì)成本和社會(huì)最優(yōu)流量模式下的社會(huì)成本之間的關(guān)系也就是總潛能和總行駛時(shí)間的關(guān)系。在本案例中表現(xiàn)為圖4(a)社會(huì)最優(yōu)流量模式和圖4(b)均衡狀態(tài)中總行駛時(shí)間和總潛能的對(duì)比。以SC(a)表示(a)流量模式下的社會(huì)成本，以PE(a)表示(a)流量模式下的潛能，根據(jù)式17易算得：

(17)

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

PE(b)

(18)

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

(19)

將這些不等式聯(lián)系起來(lái)，得到：

(20)

最佳應(yīng)對(duì)過(guò)程中潛能逐步減少，這種減少致使社會(huì)成本的增加限定在兩倍之內(nèi)。

4 結(jié) 語(yǔ)

筆者運(yùn)用博弈論的方法對(duì)交通網(wǎng)絡(luò)中出行者的行為和網(wǎng)絡(luò)流量進(jìn)行分析，通過(guò)計(jì)算發(fā)現(xiàn)均衡交通網(wǎng)絡(luò)流量模式的社會(huì)成本最高為社會(huì)最優(yōu)流量模式的兩倍，該值為交通網(wǎng)絡(luò)社會(huì)成本的可優(yōu)化上界，也就是說(shuō)通過(guò)有效的控制策略最多可以節(jié)約網(wǎng)絡(luò)社會(huì)成本的一半。

[1] 韓小亮,鄧祖新.城市交通擁堵的經(jīng)濟(jì)學(xué)分析——基于計(jì)算經(jīng)濟(jì)學(xué)的模擬檢驗(yàn)[J].財(cái)經(jīng)研究,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] 王煜.交通擁堵現(xiàn)象背后的社會(huì)問(wèn)題[J].城市問(wèn)題,2004(2):76-78. Wang Yu.Social problems behind the traffic jam phenomenon[J].Urban Problems,2004(2):76-78.

[3] 李迅,張國(guó)華,黃坤鵬.中國(guó)城市交通發(fā)展的綠色之路[J].城市規(guī)劃學(xué)刊,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] 余孝軍.一類(lèi)混合路由博弈的調(diào)和率研究[J].應(yīng)用數(shù)學(xué)和力學(xué),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] 徐寅峰,余海燕,蘇兵,等.基于時(shí)間和路徑偏好的交通流分配模型與誘導(dǎo)策略[J].系統(tǒng)工程理論與實(shí)踐,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

國(guó)家自然科學(xué)基金項(xiàng)目(71101013)；湖南省教育廳優(yōu)秀青年項(xiàng)目(11B013)

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

U491

A

1674-0696(2015)02-124-04