孫黎，凌溪蔓，譚倩，王璞

(中南大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長(zhǎng)沙 410000)

?

城市大規(guī)模交通網(wǎng)絡(luò)低效路段組合定位及分析

孫黎，凌溪蔓，譚倩，王璞

(中南大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長(zhǎng)沙 410000)

基于布雷斯悖論現(xiàn)象，根據(jù)城市交通網(wǎng)絡(luò)中路段或路段組合對(duì)路網(wǎng)通行效率的影響，可將其劃分為低效的或必要的,合理關(guān)閉路網(wǎng)中的低效路段及路段組合將減少所有出行者的出行時(shí)間成本，必要路段及路段組合的關(guān)閉將增加出行者額外的出行延誤。采用改進(jìn)的自適應(yīng)遺傳算法以有效地定位大規(guī)模真實(shí)交通網(wǎng)絡(luò)中的低效路段組合，結(jié)合美國(guó)舊金山市大規(guī)模實(shí)際交通網(wǎng)絡(luò)地理信息系統(tǒng)(GIS)數(shù)據(jù)以及該區(qū)居民通勤出行數(shù)據(jù)進(jìn)行實(shí)證分析。研究結(jié)果證實(shí)低效路段和必要路段的組合可能是低效的。分析表明，低效路段組合的低效程度|ΔTS|隨著所含路段數(shù)量增加呈現(xiàn)先增后減的變化趨勢(shì)，含路段數(shù)相對(duì)少的低效路段組合對(duì)路網(wǎng)效率產(chǎn)生更大的影響也更普遍。

城市交通效率；布雷斯悖論；大規(guī)模交通網(wǎng)絡(luò)；自適應(yīng)遺傳算法

1968年，德國(guó)數(shù)學(xué)家Braess提出交通網(wǎng)絡(luò)中的布雷斯悖論現(xiàn)象[1]，即在拓?fù)浣Y(jié)構(gòu)確定的網(wǎng)絡(luò)中，當(dāng)網(wǎng)絡(luò)中的流量分配達(dá)到均衡時(shí)，增加一條連邊，改變?cè)摼W(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，非但不會(huì)減少出行者的出行成本，反而增加該網(wǎng)絡(luò)中所有用戶的出行成本。該現(xiàn)象為治理城市交通擁擠提供了新的思路。2008年，Youn[2]認(rèn)為由于出行者總是期望個(gè)人出行費(fèi)用最低，使得系統(tǒng)需要額外損失將近30%的出行成本。1984年，Dafermos等[3]現(xiàn)了道路交通網(wǎng)絡(luò)中路段阻抗隨著路網(wǎng)中交通需求改變和路段數(shù)量增加而變化的規(guī)律。在此基礎(chǔ)上，Pas等[4]的研究發(fā)現(xiàn)路網(wǎng)中的布雷斯悖論現(xiàn)象與路阻函數(shù)參數(shù)取值和交通需求量有關(guān)，并提出悖論現(xiàn)象只會(huì)在特定的交通需求總量下發(fā)生。Hagstrom等[5]分析了布雷斯悖論現(xiàn)象在簡(jiǎn)單網(wǎng)絡(luò)中的發(fā)生機(jī)制。直到2010年，Nagurney[6]用數(shù)學(xué)推導(dǎo)證實(shí)在非常大的交通需求下，布雷斯悖論現(xiàn)象隨即消失，并以“群體智慧”解釋了這一現(xiàn)象。Roughgarden[7]的研究表明大規(guī)模復(fù)雜交通網(wǎng)絡(luò)中基于布雷斯悖論研究網(wǎng)絡(luò)結(jié)構(gòu)最優(yōu)化是一類(lèi)NP難問(wèn)題，實(shí)際上隨著網(wǎng)絡(luò)規(guī)模的增大，尋求該問(wèn)題的最優(yōu)解越難實(shí)現(xiàn)。由于大規(guī)模實(shí)際數(shù)據(jù)難以獲取，布雷斯悖論的相關(guān)研究大多以理論模型為基礎(chǔ)，關(guān)于真實(shí)數(shù)據(jù)的仿真分析相對(duì)有限。2014年，Bagloee等[8]利用加拿大溫尼伯的路網(wǎng)數(shù)據(jù)提出了一個(gè)利用啟發(fā)式算法搜索路網(wǎng)低效路段的計(jì)算模型。Sun等[9]研究了大規(guī)模實(shí)際道路交通網(wǎng)絡(luò)低效路段及其屬性特征，提出路網(wǎng)中低效路段的數(shù)量和分布與交通流的不均勻分布密切相關(guān)。本文作者提出改進(jìn)的低效路段組合啟發(fā)式定位算法，并對(duì)低效路段組合屬性進(jìn)行了深入分析。

1　問(wèn)題描述

根據(jù)布雷斯悖論現(xiàn)象的描述，悖論現(xiàn)象的產(chǎn)生是由于網(wǎng)絡(luò)中的納什均衡往往偏離帕累托最優(yōu)[10]，即個(gè)體所追求的效益最大化并非系統(tǒng)最優(yōu)，新增道路看似能為出行者提供便利，卻適得其反。1990年，紐約市決定臨時(shí)關(guān)閉該市最繁忙路段之一的第42號(hào)大街一天，結(jié)果該市的車(chē)輛通行反而比平時(shí)更為順暢。一項(xiàng)調(diào)查表明，波士頓的6條公路，曼哈頓的12條公路以及倫敦中部的7條公路如果關(guān)閉，或可減少車(chē)輛的平均出行時(shí)間[11]。由此可見(jiàn)，在特定的交通流下，既有的城市道路交通網(wǎng)絡(luò)總是存在一些低效路段，關(guān)閉這些路段反而能提高整個(gè)網(wǎng)絡(luò)的通行效率，減少每個(gè)出行者的出行時(shí)間。

2　定位低效路段及其組合的算法

2.1用戶均衡算法

出行者在路網(wǎng)中總是基于個(gè)人出行成本最優(yōu)選擇出行路徑，此時(shí)網(wǎng)絡(luò)中所有出行達(dá)到納什均衡[12-13]。假設(shè)所有出行者對(duì)路網(wǎng)都非常熟悉，并選擇從起點(diǎn)到終點(diǎn)之間出行時(shí)間最小的徑路，只有當(dāng)不存在出行者能單方面改變其徑路來(lái)降低其行駛時(shí)間，出行分布即達(dá)到均衡狀態(tài)。為計(jì)算均衡狀態(tài)下各個(gè)路段上的車(chē)流量fi以及各路段的行駛時(shí)間ti(fi)，這里采用用戶均衡的Beckmann模型進(jìn)行求解[14]，即出行分布達(dá)到均衡時(shí)滿足：

(1)

ti由BPR方程求解得出：

(2)

表1　各等級(jí)路段PKFAC以及α的取值表[19]

2.2低效路段組合定位算法

近年來(lái)，啟發(fā)式算法被廣泛應(yīng)用到路徑優(yōu)化[20]，資源調(diào)配[ 21]等組合優(yōu)化問(wèn)題中。本文采用改進(jìn)的自適應(yīng)遺傳算法定位大規(guī)模真實(shí)道路交通網(wǎng)絡(luò)中的低效路段組合。首先，需要計(jì)算初始網(wǎng)絡(luò)G0中各路段屬性，具體步驟為：

步驟1:初始化,將既有路網(wǎng)定義為初始狀態(tài)G0，求解在滿足用戶均衡的條件下G0中所有出行的出行總時(shí)間T，i=1，開(kāi)始迭代；

步驟2:計(jì)算路段ei是否為關(guān)鍵路段，如果是，i=i+1繼續(xù)步驟2，否則轉(zhuǎn)入步驟3；

步驟3:在初始狀態(tài)中關(guān)閉路段ei，得到新路網(wǎng)Gi，求解在滿足用戶均衡狀態(tài)下所有出行在路網(wǎng)Gi的出行總時(shí)間Ti，并計(jì)算ΔTi。若ΔTi<0，則ei為低效路段，否則，ei為必要路段。

步驟4:迭代終止條件：如果滿足i=n則停止迭代；否則i=i+1返回步驟2。

通過(guò)以上步驟，可以將G0中的路段劃分為關(guān)鍵路段集合Ec，必要路段集合En，以及低效路段集合Ei。以必要路段和低效路段集合組成路段集Et，各路段按ΔTi從小到大排序，并對(duì)路段重新編號(hào)，編號(hào)從1到m，其中m表示Et中的路段總數(shù)。Ec中各路段的編號(hào)從m+1到n。

其中計(jì)算網(wǎng)絡(luò)中路段ei是否為關(guān)鍵路段的具體方法為：

1)在路網(wǎng)G0中去除路段ei，并利用Dijkstra算法計(jì)算所有出行的起點(diǎn)和終點(diǎn)之間的最短路徑。

2)如果出行中存在至少一對(duì)起終點(diǎn)之間的最短路徑長(zhǎng)度為無(wú)窮大，則表明路段ei為關(guān)鍵路段。否則路段ei為非關(guān)鍵路段。

(3)

算法的具體步驟：

步驟1：計(jì)算初始解

從G0的低效路段集合Ei中隨機(jī)選擇Q個(gè)低效路段構(gòu)成的初始解集P(0)。其中，每個(gè)個(gè)體sq只有一個(gè)路段處于關(guān)閉狀態(tài)(且均為低效路段)。t=1，i=1開(kāi)始迭代。

步驟2：選擇操作

步驟3：交叉操作

對(duì)步驟2選擇的兩個(gè)父代個(gè)體，按照式(4)中的pc進(jìn)行交叉操作，生成兩個(gè)新個(gè)體；

(4)

式中：pc1=0.9，F(xiàn)max為父代種群中的最大適應(yīng)度值；Fave為父代種群的平均適應(yīng)度值；F*為進(jìn)行交叉的兩個(gè)父代個(gè)體中較大的適應(yīng)度值；pc2表示父代種群中具有最大適應(yīng)度值的個(gè)體的交叉概率。

步驟4：變異操作

對(duì)步驟3生成的兩個(gè)新個(gè)體，依據(jù)變異概率pm進(jìn)行變異操作，得到第t代解集P(t)的兩個(gè)解st(i)和st(i+1)。

步驟5：收斂性判斷

如果i+1=Q且t

3　舊金山市道路網(wǎng)絡(luò)實(shí)證分析

3.1舊金山市道路網(wǎng)絡(luò)基本信息

圖1　舊金山市地理網(wǎng)絡(luò)和出行數(shù)據(jù)Fig.1 Transport network and traffic in San Francisco

3.2舊金山市道路網(wǎng)絡(luò)的低效路段

根據(jù)3.1中用戶均衡算法將4.1中舊金山市早高峰小時(shí)通勤出行分布到路網(wǎng)G0，得到各路段的車(chē)流量fi如圖2所示。

圖2　舊金山市早高峰小時(shí)通勤出行流量分布圖Fig.2 Traffic flow distribution of San Francisco during the morning peak

采用3.2中計(jì)算路網(wǎng)各路段屬性的步驟，得出舊金山市城市道路交通網(wǎng)絡(luò)G0各屬性路段如表2所示。

表2　G0和G109各屬性路段對(duì)比

3.3舊金山市道路網(wǎng)絡(luò)的低效路段組合

圖3　不同路段數(shù)的低效路段組合的|ΔTS|ave以及|ΔTS|max變化曲線Fig.3 Number of roads in inefficient road cluster versus |ΔTS|ave and |ΔTS|max

同時(shí)，滿意解集對(duì)應(yīng)的路段組合所含路段數(shù)的概率密度分布(圖4)顯示路段組合中Nroads≤20的占比達(dá)到75.86%，而Nroads≥40的占比僅為0.3%。整個(gè)滿意解集對(duì)應(yīng)的路段組合中Nroads的概率密度呈現(xiàn)高斯分布，擬合函數(shù)滿足P(Nroads)=0.068×e-((Nroads-14.23)/9.14)2，其中(R2=0.95)。進(jìn)一步說(shuō)明，Nroads相對(duì)較小的路段組合在交通網(wǎng)絡(luò)中更為普遍，在提高網(wǎng)絡(luò)運(yùn)行效率方面的作用也更大。

圖4　Nroads 的概率密度圖Fig.4 Probability density of Nroads

4　結(jié)論

1)本文實(shí)例結(jié)果證明，實(shí)際道路交通網(wǎng)絡(luò)中的一些必要路段和低效路段的組合可能是低效的，低效路段組合的低效程度隨著組合中路段數(shù)的增加呈現(xiàn)出先增后減的變化趨勢(shì)。

2)低效路段尤其是低效路段組合的研究，對(duì)優(yōu)化交通網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，提高交通網(wǎng)絡(luò)資源利用率，緩解城市擁擠等具有重要應(yīng)用價(jià)值。同時(shí)本研究的相關(guān)結(jié)論可進(jìn)一步推廣到具有類(lèi)似拓?fù)浣Y(jié)構(gòu)特性的復(fù)雜網(wǎng)絡(luò)系統(tǒng)。

3)需要指出的是：雖然自適應(yīng)遺傳算法能較快的搜索大量的可行解，但鑒于問(wèn)題解的規(guī)模較大，難以快速定位到最優(yōu)解，算法的收斂相對(duì)較慢。

[1]BraessVD. übereinParadoxonausderVerkehrsplanung[J].Unternehmensforschung, 1968, 12 (1): 258-268.

[2]YounH,GastnerMT,JcongH.Priceofanarchyintransportationnetworks:efficiencyandoptimalitycontrol[J].PhysicalReviewLetters, 2008, 101(12): 128701-128704.

[3]DafermosS,NagurneyA.Onsometrafficequilibriumtheoryparadoxes[J].TransportationResearchPartB:Methodological, 1984, 18(2): 101-110.

[4]PASEI,PRINCIPIOSL.Braess'paradox:Somenewinsights[J].TransportationResearch, 1997, 31 (3-31): 265-276.

[5]HagstromJN,AbramsRA.CharacterizingBraess'sparadoxfortrafficnetworks[C]//ProceedingsoftheIEEEConferenceonIntelligentTransportationSystems, 2001: 837-842.

[6]NagurneyA.ThenegationoftheBraessparadoxasdemandincreases:Thewisdomofcrowdsintransportationnetworks[J].EPL, 2010, 91(4): 48002-48006.

[7]RoughgardenT.OntheseverityofBraess’sParadox:Designingnetworksforselfishusersishard[J].JournalofComputerandSystemSciences, 2006, 72 (5): 922-953.

[8]BagloeeSA,CederA,TavanaM,etal.Aheuristicmethodologytotacklethebraessparadoxdetectingproblemtailoredforrealroadnetworks[J].TransportmetricaA:TransportScience, 2014, 10 (5): 437-456.

[9]SUNLi,LIULike,XUZhongzhi,etal.Locatinginefficientlinksinalarge-scaletransportnetwork[J].PhysicaA:StatisticalMechanicsanditsApplications, 2015(419): 537-545.

[10]WilliamES,RapoportA,DarrylAS.Batchqueueswithchoiceofarrivals:Equilibriumanalysisandexperimentalstudy[J].GamesandEconomicBehavior, 2007, 59 (2): 345-363.

[11] 張薇薇. 少即是多, 從布雷斯悖論引出的話題 [J]. 世界科學(xué), 2014(6): 53-55.

ZHANGWeiwei.Lessismore,topicslearnfromBraessparadox[J].WorldScientific, 2014(6): 53-55.

[12]KubeS,SeltenR,ChmuraT,etal.Commutersroutechoicebehavior[J].GamesandEconomicBehavior, 2007, 58 (2): 394-406.

[13]RoughgardenT.Selfishroutingandthepriceofanarchy[M].Cambridge:MITPress, 2005.

[14]BeckmannMJ,MeguireCR,WinstenCB.Studiesintheeconomicsoftransportation[M].NewHaven:YaleUniversityPress, 1956.

[15]FrankM,WolfeP.Analgorithmforquadraticprogramming[J].NavalResearchLogisticsQuarterly, 1956, 3 (1-2): 95-110.

[16] 張歡, 盧毅, 朱東鐵. 基于用戶均衡分析的公路超限車(chē)輛補(bǔ)償費(fèi)率優(yōu)化模型 [J]. 鐵道科學(xué)與工程學(xué)報(bào), 2012, 9 (6): 84-89.

ZHANGHuan,LUYi,ZHUDongtie.Optimizationmodelonhighwayreimbursementrateofoversizevehicleswithuserequilibriumanalysis[J].JournalofRailwayScienceandEngineering, 2012, 9 (6): 84-89.

[17] 史峰, 王英姿, 徐光明, 等. 考慮支路路段雙向車(chē)流相互影響的單向交通組織優(yōu)化 [J]. 鐵道科學(xué)與工程學(xué)報(bào), 2012, 9(2): 66-71.

SHIFeng,WANGYingzi,XUGuangming,etal.Optimizationapproachforone-waytrafficorganizationwithbidirectionalflow’seffectoflocalroad[J].JournalofRailwayScienceandEngineering, 2012, 9(2): 66-71.

[18] 周和平, 胡列格, 晏克非. 基于模糊路段流量的OD反推的不確定規(guī)劃模型與算法研究[J]. 鐵道科學(xué)與工程學(xué)報(bào), 2005, 43(1):68-74.

ZHOUHeping,HULieke,YANGKefei.Uncertainprogrammingmodelandalgorithmforestimatingorigin-destinationmatricesbasedonfuzzylinkflow[J].JournalofRailwayScienceandEngineering, 2005, 43 (1): 68-74.

[19]WilliamAM,NancyAM.Travelestimationtechniquesforurbanplanning(NCHRPReport365) [M].Wasington,DC:NationalAcademyPress, 1998.

[20] 胡列格, 夏云, 王佳, 等. 城市公共自行車(chē)高峰期需求不均衡的調(diào)度優(yōu)化研究 [J]. 鐵道科學(xué)與工程學(xué)報(bào), 2015, 12(2): 441-448.

HULiege,XIAYun,WANGJia,etal.Schedulingoptimizationresearchondemandimbalanceofurbanpublicbicyclesduringpeakperiod. [J].JournalofRailwayScienceandEngineering, 2015, 12(2): 441-448.

[21] 童曉進(jìn), 符卓, 劉勇, 等. 連續(xù)消耗應(yīng)急物資調(diào)運(yùn)問(wèn)題研究 [J]. 鐵道科學(xué)與工程學(xué)報(bào), 2013, 10 (5): 78-82.

TONGXiaojin,FUZhuo,LIUYong,etal.Studyofemergencymaterialdispatchofthecontinuousconsumption[J].JournalofRailwayScienceandEngineering, 2013, 10 (5): 78-82.

[22]Navteqoffciolwelsike[DB/OL].http://www.navteq.com/, 2016.7.4.

[23]UScensusbareat[DB/OL].http://www.census.gov/geo/www/tiger/tgrshp2010/tgrshp20 10.html, 2016.7.4.

Locating and researching of inefficient road clusters in a large-scale transportation network

SUN Li, LING Ximan, TAN Qian, WANG Pu

(SchoolofTrafficandTransportationEngineering,CentralSouthUniversity,Changsha410000,China)

Inthispaper,roadandclusterofroadsintransportationnetworkwereclassifiedasinefficientornecessaryaccordingtotheireffectontheefficiencyoftheroadnetwork,basedonBraess'sparadox.Reasonableclosureofinefficientlinkscanreducetravelcostsconsiderably,whilethefailureofnecessarylinkswouldresultinextratraveldelays.Wemodifiedtheadaptivegeneticalgorithmtopinpointinefficientroadclustersinareallarge-scaletrafficnetwork.Actualtransportationnetworkdatafromgeographicalinformationsystems(GIS)anddailycommutingorigindestinationmatrixintheSanFranciscowereused.Ourempiricalresultsshowthatinefficientroadclustersincludenotonlyinefficientroadbutalsonecessaryroad.Meanwhile,thedegreeofinefficiency|ΔTS|increasesfirstandthendecreasesasthenumberofroadsintheroadclustersincrease.Inefficientroadclusterscontainlessroadwithlarge|ΔTS|,whichismuchmorecommonaswell.

efficiencyofurbantraffic;Braess’sparadox;largescaletransportationnetwork;adaptivegeneticalgorithm

2015-11-15

中央高?；究蒲袠I(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金資助項(xiàng)目(2015zzts207)

王璞(1983-)，男，河北石家莊人，教授，博士，從事交通運(yùn)輸規(guī)劃與管理、統(tǒng)計(jì)物理學(xué)、復(fù)雜網(wǎng)絡(luò)和數(shù)據(jù)挖掘方面的研究；E-mail:wangpu@csu.edu.cn

U491.1+3

A

1672-7029(2016)07-1414-06