劉 巍,曾慶山
(鄭州大學(xué) 電氣工程學(xué)院,河南 鄭州450001)
Braess悖論是城市交通中一個(gè)看似矛盾的現(xiàn)象,其理論基礎(chǔ)是博弈論中的納什均衡[1],即每個(gè)人的策略都是對(duì)其他參與人策略的最優(yōu)反應(yīng)。在交通網(wǎng)絡(luò)中,由于每個(gè)人都不考慮自己的選擇對(duì)其他出行者的影響,使得即使增加道路,交通延滯也不會(huì)減少,反而增加了出行者的出行時(shí)間。若增加道路后,城市交通系統(tǒng)總阻抗沒(méi)有降低,則新增道路無(wú)意義。因此,在城市道路建設(shè)中應(yīng)盡量避免Braess悖論現(xiàn)象的發(fā)生。
目前對(duì)于城市交通中的Braess悖論現(xiàn)象的研究大多局限于簡(jiǎn)單的交通網(wǎng)絡(luò)模型[2-7],而在復(fù)雜城市交通網(wǎng)絡(luò)中,存在大量路段、交叉路口以及居民起訖點(diǎn) (origin destination,O-D),不同起訖點(diǎn)間的居民有大量可選出行路徑,且居民的出行行為互相影響。路段流量、阻抗隨著居民出行行為的改變而變化,任一路段阻抗或起訖點(diǎn)間居民出行行為的改變均會(huì)對(duì)整個(gè)網(wǎng)絡(luò)造成影響。本文根據(jù)城市交通網(wǎng)絡(luò)的特點(diǎn),應(yīng)用復(fù)雜網(wǎng)絡(luò)理論建立雙層城市交通網(wǎng)絡(luò),并依據(jù)Braess悖論現(xiàn)象的成因?qū)Τ鞘薪煌ňW(wǎng)絡(luò)進(jìn)行交通配流,同時(shí)分析路段實(shí)際通行能力、居民起訖點(diǎn)及新增道路對(duì)城市交通網(wǎng)絡(luò)的影響,確定出造成Braess悖論現(xiàn)象的路段,給出改善城市交通的方案。
本文基于復(fù)雜網(wǎng)絡(luò)理論利用MATLAB建立一雙層城市交通網(wǎng)絡(luò)模型,下層網(wǎng)絡(luò)為n×n網(wǎng)格的城市道路網(wǎng)絡(luò),上層為居民出行網(wǎng)絡(luò)。
考慮到城市道路網(wǎng)絡(luò)具有無(wú)標(biāo)度性和流量集中性[8,9],且居民往往集中在公園、商城、火車(chē)站等地,故居民出行網(wǎng)絡(luò)采用無(wú)標(biāo)度網(wǎng)絡(luò)。
雙層城市交通網(wǎng)絡(luò)模型如圖1所示。
圖1 雙層城市交通網(wǎng)絡(luò)模型
虛線為城市道路網(wǎng)絡(luò),其為一5×5的網(wǎng)格,虛線為路段,兩虛線交叉處為交叉路口。該網(wǎng)絡(luò)具有25個(gè)交叉路口及40條道路。本文用G{J,L}表示城市道路網(wǎng)絡(luò),其中J為交叉口集合,L為路段集合。
雙劃線為居民出行網(wǎng)絡(luò),其為一含10個(gè)節(jié)點(diǎn)、15條邊的無(wú)標(biāo)度網(wǎng)絡(luò)。每個(gè)節(jié)點(diǎn)的度至少為1,即至少有一個(gè)邊經(jīng)過(guò)該點(diǎn),設(shè)定居民只能沿網(wǎng)格出行。為方便計(jì)算,居民出行點(diǎn)及目的地均設(shè)定在交叉路口處。用H{B,E}表示居民出行網(wǎng)絡(luò),其中B為O-D對(duì)端點(diǎn)的集合,E為任意O-D對(duì)間邊的集合。為方便觀察,設(shè)定在所研究時(shí)間段內(nèi)所有O-D對(duì)間的流量均為1。
交通阻抗是指交通網(wǎng)絡(luò)上路段或路徑之間的運(yùn)行距離、時(shí)間、費(fèi)用、舒適度,或這些因素的綜合[10]。不同交通網(wǎng)絡(luò)的阻抗隨關(guān)注度不同而有所側(cè)重。
交通阻抗包括路段阻抗和節(jié)點(diǎn)阻抗兩部分。
用路段走行時(shí)間表示路段阻抗,采用美國(guó)公路局開(kāi)發(fā)的BPR函數(shù),其形式為
式中:tij(0)——路段 (i,j)上的車(chē)輛平均自由走行時(shí)間,即路段上流量為零時(shí)車(chē)輛自由形式所需的時(shí)間;eij——路段 (i,j)的實(shí)際通行能力,即單位時(shí)間內(nèi)可通過(guò)的最大車(chē)輛數(shù);α、β為模型參數(shù),一般的:α=0.15、β=4;Qij為路段 (i,j)上的車(chē)流量。
節(jié)點(diǎn)阻抗為車(chē)輛在交叉路口花費(fèi)的時(shí)間。城市交通網(wǎng)絡(luò)中,由于交叉口多種多樣,導(dǎo)致了其計(jì)算方法各異。
為方便計(jì)算,設(shè)定各個(gè)交叉路口的阻抗均相等,并將其阻抗計(jì)入到與之相連的路段上。
O-D對(duì)間的路徑阻抗即為連接O-D對(duì)的最短路徑上的所有路段阻抗與節(jié)點(diǎn)阻抗之和。其可用圖論中的經(jīng)典算法Dijkstra算法求得。
在傳統(tǒng)Dijkstra算法中,每次更新已識(shí)別點(diǎn)集都需要計(jì)算所有未識(shí)別點(diǎn)與起始點(diǎn)間的距離,隨著城市道路網(wǎng)絡(luò)網(wǎng)格數(shù)的增加,網(wǎng)絡(luò)節(jié)點(diǎn)大幅增加,采用傳統(tǒng)Dijkstra算法的運(yùn)行時(shí)間也會(huì)大幅增加。考慮到城市交通網(wǎng)絡(luò)中,絕大多數(shù)已識(shí)別點(diǎn)最多與3個(gè)未識(shí)別點(diǎn)直接相連,在路段阻抗差距不大時(shí),搜索范圍將在以起始點(diǎn)為中心的網(wǎng)格上逐步向外擴(kuò)散,本文在原始Dijkstra算法的基礎(chǔ)上新建一鄰點(diǎn)表,該表中包含所有與已識(shí)別點(diǎn)直接相連的未識(shí)別點(diǎn)。新算法步驟如下:
(1)設(shè)初始節(jié)點(diǎn)為s,終止節(jié)點(diǎn)為m,J為網(wǎng)絡(luò)所有節(jié)點(diǎn)的集合,P為網(wǎng)絡(luò)已識(shí)別點(diǎn)的集合,U為網(wǎng)絡(luò)中與任意已識(shí)別點(diǎn)直接相連的點(diǎn)的集合。對(duì)任意節(jié)點(diǎn)v∈J-P,D(v)為節(jié)點(diǎn)v到節(jié)點(diǎn)s的路徑阻抗。
初始化:P= {s},U= {s1,s2…sn},s1,s2…sn為與節(jié)點(diǎn)s直接相連的點(diǎn)
從集合U中尋找一節(jié)點(diǎn)w,其D(w)為最小,將節(jié)點(diǎn)w加入到集合P中,從集合U中刪除節(jié)點(diǎn)w,并將w的所有不在集合U、P中的鄰點(diǎn)加入到集合U中。D(w)計(jì)算規(guī)則如下
(3)判斷節(jié)點(diǎn)m是否在集合P中,若在,結(jié)束運(yùn)算,若不在,重復(fù)步驟 (2)。
表1為計(jì)算相同兩點(diǎn)間阻抗時(shí),不同算法的運(yùn)行時(shí)間,可以看出,針對(duì)城市交通網(wǎng)絡(luò),改進(jìn)Dijkstra算法運(yùn)行速度有了明顯提高。
表1 兩種算法的運(yùn)算速度/s
交通網(wǎng)絡(luò)的總阻抗為網(wǎng)絡(luò)上的總行駛時(shí)間,可用下式計(jì)算
式中:TSC——網(wǎng)絡(luò)總阻抗;Qij——路段 (i,j)上的流量;tij——路段 (i,j)上的阻抗函數(shù)。
網(wǎng)絡(luò)總阻抗是判斷交通網(wǎng)絡(luò)是否出現(xiàn)Braess悖論現(xiàn)象的重要指標(biāo)。
交通分配是指將交通需求按一定的擇路原則分配到交通網(wǎng)絡(luò)上,主要有兩種分配模型[11]:用戶(hù)平衡配流模型(UE配流模型)和系統(tǒng)最優(yōu)配流模型 (SO配流模型)。
用戶(hù)平衡配流模型中,每個(gè)人都力圖使自己的出行時(shí)間最小,系統(tǒng)最優(yōu)配流模型則力圖使系統(tǒng)總出行時(shí)間最小。
因Braess悖論實(shí)質(zhì)就是UE分配下的各個(gè)出行者間的不合作性,即每個(gè)人都力圖使自己的出行時(shí)間最短,而不考慮自己的選擇對(duì)他人的影響,故本文采用UE配流模型。
Wardrop平衡配流原則描述如下:在起止點(diǎn)間所有可供選擇的路線中,使用者所利用的各條路線上的出行費(fèi)用全都相等,而且不大于未利用路線上的出行費(fèi)用。
1956年Beckmann等學(xué)者提出了滿足Wardrop準(zhǔn)則的數(shù)學(xué)規(guī)劃模型,該模型如下
式中:tij——路段 (i,j)上的費(fèi)用;qij——路段 (i,j)上的流量;frsk——O-D對(duì)r-s之間路徑k 上的流量;xrs——所研究時(shí)間段O-D對(duì)r-s之間的交通需求量;為若路段 (i,j)在O-D對(duì)r-s之間的路徑k上,其值為1,否則為0。
基于上述數(shù)學(xué)規(guī)劃模型采用Frank-Wolfe方法利用MATLAB對(duì)雙層城市網(wǎng)絡(luò)進(jìn)行用戶(hù)平衡配流[12],步驟如下:
(1)初始化,q0ij令路段流量q0ij=0,采用BPR函數(shù)計(jì)算路段阻抗t0ij=tij(q0ij),用 “全有全無(wú)”法將所有O-D對(duì)間的流量一次性加載到城市道路上,得到新的道路流量q1 ij,令迭代次數(shù)n=1;
(2)更新路段阻抗,令tn ij=tij(qn ij),對(duì)城市道路重新進(jìn)行一次 “全有全無(wú)”交通流分配,得到一組附加流量pn ij;
(3)解方程
求得迭代步長(zhǎng)αn,確定新的迭代點(diǎn)
(4)若滿足
ε>0為誤差限值,則qn+1 ij為平衡解,計(jì)算結(jié)束;否則,令n=n+1,返回步驟 (2)。
本文對(duì)圖1所示雙層城市交通網(wǎng)絡(luò)進(jìn)行用戶(hù)平衡配流。
為方便觀察,對(duì)所有路段 (i,j),令tij(0)=1,eij=5,對(duì)所有O-D對(duì)r-s,令xrs=1。
進(jìn)行用戶(hù)平衡配流后的城市交通網(wǎng)絡(luò)如圖2所示。實(shí)線為道路流量網(wǎng)絡(luò),其中路段流量越大,線條越粗。系統(tǒng)總阻抗為40.2619。
圖2 進(jìn)行用戶(hù)均衡配流后的城市交通網(wǎng)絡(luò)
本文采用G1(J1,L1)表示道路流量網(wǎng)絡(luò),道路流量網(wǎng)絡(luò)為城市道路網(wǎng)絡(luò)中刪除流量為0的路段及節(jié)點(diǎn)后的網(wǎng)絡(luò)。
通過(guò)查詢(xún)城市道路網(wǎng)絡(luò)中是否存在無(wú)意義的道路來(lái)判斷城市交通網(wǎng)絡(luò)中是否存在Braess悖論現(xiàn)象。
在對(duì)原始城市交通網(wǎng)絡(luò)進(jìn)行用戶(hù)平衡配流后,依次查詢(xún)流量大于0的路段對(duì)城市交通的影響,若刪除該道路后,系統(tǒng)總阻抗并未增大,則該道路無(wú)意義。
在圖2所示流量道路網(wǎng)絡(luò)中,刪除任一道路,系統(tǒng)總阻抗均會(huì)增加,即該城市交通網(wǎng)絡(luò)并不存在Braess悖論現(xiàn)象。
分別討論改變路段實(shí)際通行能力、新增居民起訖點(diǎn)或新增路段的情況下的Braess悖論現(xiàn)象。
在城市交通網(wǎng)絡(luò)中,經(jīng)常需要通過(guò)拓寬城市道路以改善交通狀況,本文研究城市交通網(wǎng)絡(luò)中路段實(shí)際通行能力發(fā)生改變時(shí)的Braess悖論現(xiàn)象。
對(duì)所有流量大于0的路段 (i,j),依次令其道路通行能力eij=10,即增強(qiáng)路段的通行能力。對(duì)圖1所示城市交通網(wǎng)絡(luò)重新進(jìn)行用戶(hù)平衡配流,計(jì)算系統(tǒng)總阻抗。
通過(guò)計(jì)算發(fā)現(xiàn),存在5個(gè)方案,使得增強(qiáng)某路段通行能力后,系統(tǒng)總阻抗并未增加,其中,當(dāng)增強(qiáng)點(diǎn) (2,1)與 (2,2)間的路段通行能力時(shí),系統(tǒng)總阻抗最高,為40.2768。
令點(diǎn) (2,1)與 (2,2)間的路段通行能力e在區(qū)間[1,20]內(nèi)變化,通過(guò)進(jìn)一步的計(jì)算發(fā)現(xiàn),當(dāng)1≤e≤5或e≥6時(shí),系統(tǒng)總阻抗隨著e的增大而降低。其中當(dāng)e=6時(shí),系統(tǒng)總阻抗為40.2789;當(dāng)e=12時(shí),系統(tǒng)總阻抗降到40.2592,小于原系統(tǒng)阻抗40.2619,而后隨著e的增大系統(tǒng)總阻抗基本保持不變。
由上述結(jié)果可以看出,在城市交通網(wǎng)絡(luò)中,增強(qiáng)路段通行能力未必能夠有效的緩解交通壓力,有時(shí)甚至?xí)龃笙到y(tǒng)總阻抗。在城市交通網(wǎng)絡(luò)中,選擇合適而非更大的路段通行能力能夠更有效的改善城市交通。
公園、居民區(qū)、醫(yī)院、學(xué)校的建立會(huì)導(dǎo)致新的居民起訖點(diǎn)的出現(xiàn),產(chǎn)生新的O-D對(duì),使得城市交通網(wǎng)絡(luò)發(fā)生改變。
在圖1所示雙層城市交通網(wǎng)絡(luò)上,新增一居民出行點(diǎn)(2,2),并將該點(diǎn)以0.33的概率與其它居民出行點(diǎn)相連,生成一含11個(gè)節(jié)點(diǎn),19條邊的新的居民出行網(wǎng)絡(luò)。
新的城市交通網(wǎng)絡(luò)如圖3所示,圖中虛線為城市道路網(wǎng)絡(luò)、實(shí)線為道路流量網(wǎng)絡(luò)、雙劃線為居民出行網(wǎng)絡(luò)。系統(tǒng)總阻抗為49.6153。
圖3 增加居民出行點(diǎn)后的城市交通網(wǎng)絡(luò)
將圖3與圖2對(duì)比,可以看出,新增居民出行點(diǎn) (2,2)后,在用戶(hù)平衡配流下,節(jié)點(diǎn) (1,3)、(2,3)間的路段反而不再被使用。這是由于新的居民出行點(diǎn)的出現(xiàn)使得部分路段的阻抗增大,進(jìn)而使部分O-D對(duì)之間的最短路徑阻抗增大,該O-D對(duì)上的出行者將不再沿該路徑出行,使得該路徑上的路段流量受到影響,便出現(xiàn)了上述新的居民出行點(diǎn)的出現(xiàn)反而導(dǎo)致了原始路段不再被使用的現(xiàn)象。
若刪除G1中的任意路段 (i,j)后,居民可沿城市道路網(wǎng)絡(luò)G中的除 (i,j)外的路段出行,則無(wú)意義的路段數(shù)為6,即存在6個(gè)方案,使得刪除城市交通網(wǎng)絡(luò)中某一路段后,系統(tǒng)總阻抗并未增加。其中當(dāng)刪除點(diǎn) (3,4)與(3,5)間的路段時(shí),系統(tǒng)總阻抗最低,為49.5145,同時(shí)刪除該路段后,部分流量將重新分配到節(jié)點(diǎn) (1,3)、(2,3)間的路段上。
若刪除G1中的任意路段 (i,j)后,居民僅能沿G1中剩余路段出行,則無(wú)意義的路段數(shù)為6。其中當(dāng)刪除點(diǎn)(3,3)與 (4,3)間 的 路 段 時(shí),系統(tǒng) 總 阻 抗 最 低,為49.5313。
通過(guò)上述計(jì)算可知,新的居民出行點(diǎn)的出現(xiàn)可能會(huì)導(dǎo)致原本被使用的路段不再被使用,同時(shí)亦可能會(huì)引起B(yǎng)raess悖論現(xiàn)象的出現(xiàn)。
對(duì)某一存在Braess悖論現(xiàn)象的城市交通網(wǎng)絡(luò),相比于僅刪除某個(gè)無(wú)意義的路段,在刪除某個(gè)路段的同時(shí)合理增加部分原本看似無(wú)用的路段,可更加有效的降低系統(tǒng)總阻抗。
為緩解交通壓力,提高車(chē)速和通行能力,城市交通中往往會(huì)建立一些高架橋。
在點(diǎn) (1,1)、(5,5)間建立一高架橋,構(gòu)建圖4所示城市交通網(wǎng)絡(luò)。該網(wǎng)絡(luò)中tij(0)=1,eij=5。
圖4 建立高架橋后的城市道路網(wǎng)絡(luò)
進(jìn)行用戶(hù)均衡配流后的道路流量網(wǎng)絡(luò)如圖,系統(tǒng)總阻抗為37.1696,小于原城市交通網(wǎng)絡(luò)的系統(tǒng)總阻抗40.2619,系統(tǒng)性能有了較大提高。
由圖4可以看出,該高架橋的建立導(dǎo)致了節(jié)點(diǎn) (1,3)、(2,3)間的路段不再被使用,這是因?yàn)樾碌穆范蔚某霈F(xiàn)使得部分O-D對(duì)間的居民沿新的最短路徑出行,進(jìn)而對(duì)其它O-D對(duì)間的居民出行路線產(chǎn)生影響,最終導(dǎo)致流量重新分配,使得任意O-D對(duì)間的最短路徑都不再包括該路段。
通過(guò)計(jì)算發(fā)現(xiàn),當(dāng)刪除點(diǎn) (3,4)與 (3,5)間的路段后,用戶(hù)平衡配流下的出行者將沿G1中剩余路段出行,系統(tǒng)總阻抗會(huì)降低,其值為37.1670。
通過(guò)建立高架橋,雖大幅降低了系統(tǒng)總阻抗,卻也同時(shí)產(chǎn)生了Braess悖論現(xiàn)象,使得原來(lái)有意義的路段變得無(wú)意義,通過(guò)刪除該路段可使系統(tǒng)總阻抗得到進(jìn)一步降低。即建立新路段后合理刪除部分原路段可使系統(tǒng)性能得到進(jìn)一步的提高。
針對(duì)復(fù)雜城市交通網(wǎng)絡(luò)中存在大量的路段及O-D對(duì),使得通過(guò)傳統(tǒng)方法研究復(fù)雜城市交通網(wǎng)絡(luò)中的Braess悖論現(xiàn)象變得困難的情況,本文采用復(fù)雜網(wǎng)絡(luò)理論,依據(jù)城市網(wǎng)絡(luò)具有的無(wú)標(biāo)度性和流量集中性,構(gòu)建了一雙層城市交通網(wǎng)絡(luò),其中上層為無(wú)標(biāo)度居民出行網(wǎng)絡(luò),下層為城市道路網(wǎng)絡(luò)??紤]到Braess悖論現(xiàn)象的實(shí)質(zhì)便是博弈論中的納什均衡,對(duì)城市交通網(wǎng)絡(luò)進(jìn)行用戶(hù)平衡配流。在此基礎(chǔ)上,研究復(fù)雜城市交通網(wǎng)絡(luò)中的Braess悖論現(xiàn)象。
研究結(jié)果表明,在復(fù)雜城市交通網(wǎng)絡(luò)中,相比于單純的提高路段實(shí)際通行能力,選擇合適的路段通行能力能更加有效的緩解交通壓力。而改變居民起訖點(diǎn)及新增道路時(shí),均可能造成Braess悖論現(xiàn)象的出現(xiàn)或消失。相比于僅通過(guò)拆除無(wú)意義道路或新建道路來(lái)改善城市交通,同時(shí)將兩種方法配合使用,能取得更好的效果。本文在確定造成Braess悖論現(xiàn)象的路段同時(shí),給出了改善網(wǎng)絡(luò)狀況的方案。本文采用方法及所得結(jié)果可為城市交通規(guī)劃提供決策依據(jù),具有一定的理論意義和實(shí)用價(jià)值。
[1]Macko M,Larson K,Steskal L’.Braess’s paradox for flows over time [J].Theory of Computing Systems,2013;53 (1):86-106.
[2]Pala M,Baltazar S,Huant S,et al.Transport inefficiency in branched-out mesoscopic networks:An analog of the Braess paradox[J].Physical Review Letters,2012,108 (7):076802.
[3]ZHAO Chunxue,F(xiàn)U Baibai,WANG Tianming.Braess’paradox phenomenon of congested traffic networks [J].Journal of Transportation Systems Engineering and Information Technology,2012,12 (4):155-160 (in Chinese). [趙春雪,傅白白,王天明.擁擠交通網(wǎng)絡(luò)的Braess’s悖論現(xiàn)象 [J].交通運(yùn)輸系統(tǒng)工程與信息,2012,12 (4):155-160.]
[4]Park K.Detecting Braess paradox based on stable dynamics in general congested transportation networks [J].Networks &Spatial Economics,2011,11 (2):207-232.
[5]Lin Weihua,Hong K Lo.Investigating Braess’paradox with time-dependent queues [J].Transportation Science,2009,43(1):117-126.
[6]Rapoport A,Kugler T,Dugar S,et al.Choice of routes in congested traffic networks:Experimental tests of the Braess paradox [J].Games & Economic Behavior,2009,65 (2):538-571.
[7]Askoura Y,Lebacque J,Haj-Salem H.Optimal sub-networks in traffic assignment problem and the Braess paradox [J].Computers & Industrial Engineering,2011,61 (2):382-390.
[8]WU Jianjun.Studies on the complexity of topology structure in the urban traffic network [D].Beijing:Beijing Jiaotong University,2008(in Chinese).[吳建軍.城市交通網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)復(fù)雜性研究 [D].北京:北京交通大學(xué),2008.]
[9]Jiang B.A topological pattern of urban street networks:Universality and peculiarity [J].Physica A,2007,384 (2):647-655.
[10]ZHAO Yue.Study on the congestion characteristics and control methods on complex traffic network [D].Chengdu:Southwest Jiaotong University,2009 (in Chinese). [趙月.復(fù)雜交通網(wǎng)絡(luò)擁堵特性及控制方法研究 [D].成都:西南交通大學(xué),2009.]
[11]WU Jianjun,GAO Ziyou,SUN Huijun,et al.The complex of urban transport system [M].Beijing:Science Press,2011:36-40 (in Chinese).[吳建軍,高自友,孫會(huì)君,等.城市交通系統(tǒng)復(fù)雜性 [M].北京:科學(xué)出版社,2011:36-40.]
[12]ZHANG Hui.The analysis of the traffic flow distribution and failure of correlated traffic complex networks [D].Beijing:Beijing Jiaotong University,2012 (in Chinese).[張輝.具有相關(guān)性的復(fù)雜交通網(wǎng)絡(luò)流量分布及失效特性分析 [D].北京:北京交通大學(xué),2012.]