基于復(fù)雜網(wǎng)絡(luò)的Braess悖論現(xiàn)象

劉 巍，曾慶山

（鄭州大學(xué) 電氣工程學(xué)院，河南 鄭州450001）

0 引 言

Braess悖論是城市交通中一個看似矛盾的現(xiàn)象，其理論基礎(chǔ)是博弈論中的納什均衡［1］，即每個人的策略都是對其他參與人策略的最優(yōu)反應(yīng)。在交通網(wǎng)絡(luò)中，由于每個人都不考慮自己的選擇對其他出行者的影響，使得即使增加道路，交通延滯也不會減少，反而增加了出行者的出行時間。若增加道路后，城市交通系統(tǒng)總阻抗沒有降低，則新增道路無意義。因此，在城市道路建設(shè)中應(yīng)盡量避免Braess悖論現(xiàn)象的發(fā)生。

目前對于城市交通中的Braess悖論現(xiàn)象的研究大多局限于簡單的交通網(wǎng)絡(luò)模型［2－7］，而在復(fù)雜城市交通網(wǎng)絡(luò)中，存在大量路段、交叉路口以及居民起訖點 （origin destination，O－D），不同起訖點間的居民有大量可選出行路徑，且居民的出行行為互相影響。路段流量、阻抗隨著居民出行行為的改變而變化，任一路段阻抗或起訖點間居民出行行為的改變均會對整個網(wǎng)絡(luò)造成影響。本文根據(jù)城市交通網(wǎng)絡(luò)的特點，應(yīng)用復(fù)雜網(wǎng)絡(luò)理論建立雙層城市交通網(wǎng)絡(luò)，并依據(jù)Braess悖論現(xiàn)象的成因?qū)Τ鞘薪煌ňW(wǎng)絡(luò)進(jìn)行交通配流，同時分析路段實際通行能力、居民起訖點及新增道路對城市交通網(wǎng)絡(luò)的影響，確定出造成Braess悖論現(xiàn)象的路段，給出改善城市交通的方案。

1 城市交通網(wǎng)絡(luò)模型

本文基于復(fù)雜網(wǎng)絡(luò)理論利用MATLAB建立一雙層城市交通網(wǎng)絡(luò)模型，下層網(wǎng)絡(luò)為n×n網(wǎng)格的城市道路網(wǎng)絡(luò)，上層為居民出行網(wǎng)絡(luò)。

考慮到城市道路網(wǎng)絡(luò)具有無標(biāo)度性和流量集中性［8，9］，且居民往往集中在公園、商城、火車站等地，故居民出行網(wǎng)絡(luò)采用無標(biāo)度網(wǎng)絡(luò)。

雙層城市交通網(wǎng)絡(luò)模型如圖1所示。

圖1 雙層城市交通網(wǎng)絡(luò)模型

虛線為城市道路網(wǎng)絡(luò)，其為一5×5的網(wǎng)格，虛線為路段，兩虛線交叉處為交叉路口。該網(wǎng)絡(luò)具有25個交叉路口及40條道路。本文用G｛J，L｝表示城市道路網(wǎng)絡(luò)，其中J為交叉口集合，L為路段集合。

雙劃線為居民出行網(wǎng)絡(luò)，其為一含10個節(jié)點、15條邊的無標(biāo)度網(wǎng)絡(luò)。每個節(jié)點的度至少為1，即至少有一個邊經(jīng)過該點，設(shè)定居民只能沿網(wǎng)格出行。為方便計算，居民出行點及目的地均設(shè)定在交叉路口處。用H｛B，E｝表示居民出行網(wǎng)絡(luò)，其中B為O－D對端點的集合，E為任意O－D對間邊的集合。為方便觀察，設(shè)定在所研究時間段內(nèi)所有O－D對間的流量均為1。

2 交通阻抗

交通阻抗是指交通網(wǎng)絡(luò)上路段或路徑之間的運行距離、時間、費用、舒適度，或這些因素的綜合［10］。不同交通網(wǎng)絡(luò)的阻抗隨關(guān)注度不同而有所側(cè)重。

交通阻抗包括路段阻抗和節(jié)點阻抗兩部分。

2.1 路段阻抗

用路段走行時間表示路段阻抗，采用美國公路局開發(fā)的BPR函數(shù)，其形式為

式中：tij（0）——路段 （i，j）上的車輛平均自由走行時間，即路段上流量為零時車輛自由形式所需的時間；eij——路段 （i，j）的實際通行能力，即單位時間內(nèi)可通過的最大車輛數(shù)；α、β為模型參數(shù)，一般的：α＝0.15、β＝4；Qij為路段 （i，j）上的車流量。

2.2 節(jié)點阻抗

節(jié)點阻抗為車輛在交叉路口花費的時間。城市交通網(wǎng)絡(luò)中，由于交叉口多種多樣，導(dǎo)致了其計算方法各異。

為方便計算，設(shè)定各個交叉路口的阻抗均相等，并將其阻抗計入到與之相連的路段上。

2.3 路徑阻抗

O－D對間的路徑阻抗即為連接O－D對的最短路徑上的所有路段阻抗與節(jié)點阻抗之和。其可用圖論中的經(jīng)典算法Dijkstra算法求得。

在傳統(tǒng)Dijkstra算法中，每次更新已識別點集都需要計算所有未識別點與起始點間的距離，隨著城市道路網(wǎng)絡(luò)網(wǎng)格數(shù)的增加，網(wǎng)絡(luò)節(jié)點大幅增加，采用傳統(tǒng)Dijkstra算法的運行時間也會大幅增加?？紤]到城市交通網(wǎng)絡(luò)中，絕大多數(shù)已識別點最多與3個未識別點直接相連，在路段阻抗差距不大時，搜索范圍將在以起始點為中心的網(wǎng)格上逐步向外擴(kuò)散，本文在原始Dijkstra算法的基礎(chǔ)上新建一鄰點表，該表中包含所有與已識別點直接相連的未識別點。新算法步驟如下：

（1）設(shè)初始節(jié)點為s，終止節(jié)點為m，J為網(wǎng)絡(luò)所有節(jié)點的集合，P為網(wǎng)絡(luò)已識別點的集合，U為網(wǎng)絡(luò)中與任意已識別點直接相連的點的集合。對任意節(jié)點v∈J－P，D（v）為節(jié)點v到節(jié)點s的路徑阻抗。

初始化：P＝ ｛s｝，U＝ ｛s1，s2…sn｝，s1，s2…sn為與節(jié)點s直接相連的點

從集合U中尋找一節(jié)點w，其D（w）為最小，將節(jié)點w加入到集合P中，從集合U中刪除節(jié)點w，并將w的所有不在集合U、P中的鄰點加入到集合U中。D（w）計算規(guī)則如下

（3）判斷節(jié)點m是否在集合P中，若在，結(jié)束運算，若不在，重復(fù)步驟 （2）。

表1為計算相同兩點間阻抗時，不同算法的運行時間，可以看出，針對城市交通網(wǎng)絡(luò)，改進(jìn)Dijkstra算法運行速度有了明顯提高。

表1 兩種算法的運算速度／s

2.4 網(wǎng)絡(luò)總阻抗

交通網(wǎng)絡(luò)的總阻抗為網(wǎng)絡(luò)上的總行駛時間，可用下式計算

式中：TSC——網(wǎng)絡(luò)總阻抗；Qij——路段 （i，j）上的流量；tij——路段 （i，j）上的阻抗函數(shù)。

網(wǎng)絡(luò)總阻抗是判斷交通網(wǎng)絡(luò)是否出現(xiàn)Braess悖論現(xiàn)象的重要指標(biāo)。

3 復(fù)雜交通網(wǎng)絡(luò)上用戶平衡配流

交通分配是指將交通需求按一定的擇路原則分配到交通網(wǎng)絡(luò)上，主要有兩種分配模型［11］：用戶平衡配流模型（UE配流模型）和系統(tǒng)最優(yōu)配流模型 （SO配流模型）。

用戶平衡配流模型中，每個人都力圖使自己的出行時間最小，系統(tǒng)最優(yōu)配流模型則力圖使系統(tǒng)總出行時間最小。

因Braess悖論實質(zhì)就是UE分配下的各個出行者間的不合作性，即每個人都力圖使自己的出行時間最短，而不考慮自己的選擇對他人的影響，故本文采用UE配流模型。

Wardrop平衡配流原則描述如下：在起止點間所有可供選擇的路線中，使用者所利用的各條路線上的出行費用全都相等，而且不大于未利用路線上的出行費用。

1956年Beckmann等學(xué)者提出了滿足Wardrop準(zhǔn)則的數(shù)學(xué)規(guī)劃模型，該模型如下

式中：tij——路段 （i，j）上的費用；qij——路段 （i，j）上的流量；frsk——O－D對r－s之間路徑k 上的流量；xrs——所研究時間段O－D對r－s之間的交通需求量；為若路段 （i，j）在O－D對r－s之間的路徑k上，其值為1，否則為0。

基于上述數(shù)學(xué)規(guī)劃模型采用Frank－Wolfe方法利用MATLAB對雙層城市網(wǎng)絡(luò)進(jìn)行用戶平衡配流［12］，步驟如下：

（1）初始化，q0ij令路段流量q0ij＝0，采用BPR函數(shù)計算路段阻抗t0ij＝tij（q0ij），用 “全有全無”法將所有O－D對間的流量一次性加載到城市道路上，得到新的道路流量q1 ij，令迭代次數(shù)n＝1；

（2）更新路段阻抗，令tn ij＝tij（qn ij），對城市道路重新進(jìn)行一次 “全有全無”交通流分配，得到一組附加流量pn ij；

（3）解方程

求得迭代步長αn，確定新的迭代點

（4）若滿足

ε＞0為誤差限值，則qn＋1 ij為平衡解，計算結(jié)束；否則，令n＝n＋1，返回步驟 （2）。

本文對圖1所示雙層城市交通網(wǎng)絡(luò)進(jìn)行用戶平衡配流。

為方便觀察，對所有路段 （i，j），令tij（0）＝1，eij＝5，對所有O－D對r－s，令xrs＝1。

進(jìn)行用戶平衡配流后的城市交通網(wǎng)絡(luò)如圖2所示。實線為道路流量網(wǎng)絡(luò)，其中路段流量越大，線條越粗。系統(tǒng)總阻抗為40.2619。

圖2 進(jìn)行用戶均衡配流后的城市交通網(wǎng)絡(luò)

本文采用G1（J1，L1）表示道路流量網(wǎng)絡(luò)，道路流量網(wǎng)絡(luò)為城市道路網(wǎng)絡(luò)中刪除流量為0的路段及節(jié)點后的網(wǎng)絡(luò)。

4 復(fù)雜交通網(wǎng)絡(luò)上的Braess悖論現(xiàn)象

通過查詢城市道路網(wǎng)絡(luò)中是否存在無意義的道路來判斷城市交通網(wǎng)絡(luò)中是否存在Braess悖論現(xiàn)象。

在對原始城市交通網(wǎng)絡(luò)進(jìn)行用戶平衡配流后，依次查詢流量大于0的路段對城市交通的影響，若刪除該道路后，系統(tǒng)總阻抗并未增大，則該道路無意義。

在圖2所示流量道路網(wǎng)絡(luò)中，刪除任一道路，系統(tǒng)總阻抗均會增加，即該城市交通網(wǎng)絡(luò)并不存在Braess悖論現(xiàn)象。

分別討論改變路段實際通行能力、新增居民起訖點或新增路段的情況下的Braess悖論現(xiàn)象。

4.1 改變路段實際通行能力

在城市交通網(wǎng)絡(luò)中，經(jīng)常需要通過拓寬城市道路以改善交通狀況，本文研究城市交通網(wǎng)絡(luò)中路段實際通行能力發(fā)生改變時的Braess悖論現(xiàn)象。

對所有流量大于0的路段 （i，j），依次令其道路通行能力eij＝10，即增強(qiáng)路段的通行能力。對圖1所示城市交通網(wǎng)絡(luò)重新進(jìn)行用戶平衡配流，計算系統(tǒng)總阻抗。

通過計算發(fā)現(xiàn)，存在5個方案，使得增強(qiáng)某路段通行能力后，系統(tǒng)總阻抗并未增加，其中，當(dāng)增強(qiáng)點 （2，1）與 （2，2）間的路段通行能力時，系統(tǒng)總阻抗最高，為40.2768。

令點 （2，1）與 （2，2）間的路段通行能力e在區(qū)間［1，20］內(nèi)變化，通過進(jìn)一步的計算發(fā)現(xiàn)，當(dāng)1≤e≤5或e≥6時，系統(tǒng)總阻抗隨著e的增大而降低。其中當(dāng)e＝6時，系統(tǒng)總阻抗為40.2789；當(dāng)e＝12時，系統(tǒng)總阻抗降到40.2592，小于原系統(tǒng)阻抗40.2619，而后隨著e的增大系統(tǒng)總阻抗基本保持不變。

由上述結(jié)果可以看出，在城市交通網(wǎng)絡(luò)中，增強(qiáng)路段通行能力未必能夠有效的緩解交通壓力，有時甚至?xí)龃笙到y(tǒng)總阻抗。在城市交通網(wǎng)絡(luò)中，選擇合適而非更大的路段通行能力能夠更有效的改善城市交通。

4.2 新增居民起訖點

公園、居民區(qū)、醫(yī)院、學(xué)校的建立會導(dǎo)致新的居民起訖點的出現(xiàn)，產(chǎn)生新的O－D對，使得城市交通網(wǎng)絡(luò)發(fā)生改變。

在圖1所示雙層城市交通網(wǎng)絡(luò)上，新增一居民出行點（2，2），并將該點以0.33的概率與其它居民出行點相連，生成一含11個節(jié)點，19條邊的新的居民出行網(wǎng)絡(luò)。

新的城市交通網(wǎng)絡(luò)如圖3所示，圖中虛線為城市道路網(wǎng)絡(luò)、實線為道路流量網(wǎng)絡(luò)、雙劃線為居民出行網(wǎng)絡(luò)。系統(tǒng)總阻抗為49.6153。

圖3 增加居民出行點后的城市交通網(wǎng)絡(luò)

將圖3與圖2對比，可以看出，新增居民出行點 （2，2）后，在用戶平衡配流下，節(jié)點 （1，3）、（2，3）間的路段反而不再被使用。這是由于新的居民出行點的出現(xiàn)使得部分路段的阻抗增大，進(jìn)而使部分O－D對之間的最短路徑阻抗增大，該O－D對上的出行者將不再沿該路徑出行，使得該路徑上的路段流量受到影響，便出現(xiàn)了上述新的居民出行點的出現(xiàn)反而導(dǎo)致了原始路段不再被使用的現(xiàn)象。

若刪除G1中的任意路段 （i，j）后，居民可沿城市道路網(wǎng)絡(luò)G中的除 （i，j）外的路段出行，則無意義的路段數(shù)為6，即存在6個方案，使得刪除城市交通網(wǎng)絡(luò)中某一路段后，系統(tǒng)總阻抗并未增加。其中當(dāng)刪除點 （3，4）與（3，5）間的路段時，系統(tǒng)總阻抗最低，為49.5145，同時刪除該路段后，部分流量將重新分配到節(jié)點 （1，3）、（2，3）間的路段上。

若刪除G1中的任意路段 （i，j）后，居民僅能沿G1中剩余路段出行，則無意義的路段數(shù)為6。其中當(dāng)刪除點（3，3）與 （4，3）間 的 路 段 時，系統(tǒng) 總 阻 抗 最 低，為49.5313。

通過上述計算可知，新的居民出行點的出現(xiàn)可能會導(dǎo)致原本被使用的路段不再被使用，同時亦可能會引起B(yǎng)raess悖論現(xiàn)象的出現(xiàn)。

對某一存在Braess悖論現(xiàn)象的城市交通網(wǎng)絡(luò)，相比于僅刪除某個無意義的路段，在刪除某個路段的同時合理增加部分原本看似無用的路段，可更加有效的降低系統(tǒng)總阻抗。

4.3 新增路段

為緩解交通壓力，提高車速和通行能力，城市交通中往往會建立一些高架橋。

在點 （1，1）、（5，5）間建立一高架橋，構(gòu)建圖4所示城市交通網(wǎng)絡(luò)。該網(wǎng)絡(luò)中tij（0）＝1，eij＝5。

圖4 建立高架橋后的城市道路網(wǎng)絡(luò)

進(jìn)行用戶均衡配流后的道路流量網(wǎng)絡(luò)如圖，系統(tǒng)總阻抗為37.1696，小于原城市交通網(wǎng)絡(luò)的系統(tǒng)總阻抗40.2619，系統(tǒng)性能有了較大提高。

由圖4可以看出，該高架橋的建立導(dǎo)致了節(jié)點 （1，3）、（2，3）間的路段不再被使用，這是因為新的路段的出現(xiàn)使得部分O－D對間的居民沿新的最短路徑出行，進(jìn)而對其它O－D對間的居民出行路線產(chǎn)生影響，最終導(dǎo)致流量重新分配，使得任意O－D對間的最短路徑都不再包括該路段。

通過計算發(fā)現(xiàn)，當(dāng)刪除點 （3，4）與 （3，5）間的路段后，用戶平衡配流下的出行者將沿G1中剩余路段出行，系統(tǒng)總阻抗會降低，其值為37.1670。

通過建立高架橋，雖大幅降低了系統(tǒng)總阻抗，卻也同時產(chǎn)生了Braess悖論現(xiàn)象，使得原來有意義的路段變得無意義，通過刪除該路段可使系統(tǒng)總阻抗得到進(jìn)一步降低。即建立新路段后合理刪除部分原路段可使系統(tǒng)性能得到進(jìn)一步的提高。

5 結(jié)束語

針對復(fù)雜城市交通網(wǎng)絡(luò)中存在大量的路段及O－D對，使得通過傳統(tǒng)方法研究復(fù)雜城市交通網(wǎng)絡(luò)中的Braess悖論現(xiàn)象變得困難的情況，本文采用復(fù)雜網(wǎng)絡(luò)理論，依據(jù)城市網(wǎng)絡(luò)具有的無標(biāo)度性和流量集中性，構(gòu)建了一雙層城市交通網(wǎng)絡(luò)，其中上層為無標(biāo)度居民出行網(wǎng)絡(luò)，下層為城市道路網(wǎng)絡(luò)?？紤]到Braess悖論現(xiàn)象的實質(zhì)便是博弈論中的納什均衡，對城市交通網(wǎng)絡(luò)進(jìn)行用戶平衡配流。在此基礎(chǔ)上，研究復(fù)雜城市交通網(wǎng)絡(luò)中的Braess悖論現(xiàn)象。

研究結(jié)果表明，在復(fù)雜城市交通網(wǎng)絡(luò)中，相比于單純的提高路段實際通行能力，選擇合適的路段通行能力能更加有效的緩解交通壓力。而改變居民起訖點及新增道路時，均可能造成Braess悖論現(xiàn)象的出現(xiàn)或消失。相比于僅通過拆除無意義道路或新建道路來改善城市交通，同時將兩種方法配合使用，能取得更好的效果。本文在確定造成Braess悖論現(xiàn)象的路段同時，給出了改善網(wǎng)絡(luò)狀況的方案。本文采用方法及所得結(jié)果可為城市交通規(guī)劃提供決策依據(jù)，具有一定的理論意義和實用價值。

［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］.交通運輸系統(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）.［吳建軍，高自友，孫會君，等.城市交通系統(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.］