楊國菁，吳建軍

(北京交通大學軌道交通控制與安全國家重點實驗室，北京 100044)

具有圈性結構的城市交通網絡承載能力分析

楊國菁，吳建軍

(北京交通大學軌道交通控制與安全國家重點實驗室，北京 100044)

建立了圈性網絡的演化機理，研究了相同路網規(guī)模下具有不同圈性網絡拓撲結構的交通承載能力，發(fā)現(xiàn)在流量不斷加載并最終達到飽和狀態(tài)的過程中，當圈性較小或者較大時，網絡流量都比較容易達到飽和狀態(tài)。相反，當圈性在0.54附近時，網絡則更不容易達到擁堵狀態(tài)。

城市交通；承載力；網絡結構；圈性

0 引言

隨著城市化進程的加速，目前城市特別是大城市的交通承載能力已經逼近甚至超過了當前的極限,從而導致城市交通問題愈演愈烈。但是，城市的發(fā)展不可能突破土地資源的限制，交通的發(fā)展也不可能嚴重超過系統(tǒng)的承載能力。各城市積極地通過各種方式來緩解交通問題并盡可能提高城市的交通承載能力。研究具有怎樣的拓撲結構才可以使承載的交通流量達到最大不僅是合理規(guī)劃城市道路網絡，緩解城市交通擁堵的關鍵，也是研究城市交通網絡演化的基礎。

隨著人們對承載力概念認識的不斷加深，國內外學者從不同角度對城市交通承載力的大小進行了估算。從優(yōu)化角度看，F(xiàn)ord 和 Fulkerson[1]應用圖論中最大流最小割集定理的方法建立了路網容量模型。Asakura[2]第一個針對平衡網絡交通容量問題提出求解平衡網絡交通容量問題的雙層規(guī)劃模型和相應的啟發(fā)式算法。Yang等[3]在總結先前研究成果的基礎上提出城市交通承載力問題是一個系統(tǒng)問題，并改進了求解城市交通承載力的雙層規(guī)劃模型。在此基礎上，侯德勛[4]建立了評價交通承載力大小的體系，提出了求解城市交通設施承載力的多目標雙層規(guī)劃模型并用遺傳算法求解。詹歆曄等[5]基于“機動車在駛量”構建了由路網資源、燃油供給和大氣環(huán)境3個模塊組成的交通承載力宏觀定量模型。李榮等[6]在分析交通承載力的關鍵影響因素的基礎上，建立交通承載力定量計算模型，通過關鍵因素的時間序列分析對交通承載力進行預測。Li等[7]從宏觀層面重新定義了城市交通承載力，結合高峰小時交通量和擁堵指數(shù)給出了交通承載力的計算方法?；诙嘁蛩胤治龇ㄑ芯苛擞绊懕本┦薪煌ǔ休d力的關鍵因素，應用因子分析和非線性回歸方法得到城市交通承載力與這些影響因素之間的內在關系。王乾等[8]從系統(tǒng)工程角度通過對交通環(huán)境承載力、環(huán)境容量進行研究，提出了基于灰色模型的交通承載力確定方法并進行了應用。隨著網絡復雜性研究的興起，許多學者開始嘗試研究道路網絡結構與交通承載力之間的關系。吳建軍[9]結合用戶均衡配流與復雜網絡理論，研究了網絡拓撲結構對交通堵塞的影響以及網絡拓撲與交通承載流量之間的關系，并進一步討論了最優(yōu)的交通網絡拓撲。賈順平等[10]研究了居民出行特性與路網承載力下的城市交通狀態(tài)。許明濤[11]建立了在容量限制的情況下城市道路和交通的互演化模型。Zhao等[12]提出了一種考慮道路投資及其路段能力的城市道路交通網絡演化模型。龍雪琴等[13]通過簡化公路網系統(tǒng)，建立了公路網結構自組織演化框架，對演化過程進行了仿真研究。

綜上可知，對于城市交通承載力的概念和定量計算已有較成熟的研究，但是以往的研究是基于城市可以不斷擴張的模式，還缺乏對給定路網規(guī)模的條件下如何優(yōu)化交通網絡結構的研究。一般情況下，由于城市交通網絡結構具有小世界特性，因此可以用圈性和樹性來度量。圈性代表了路網成環(huán)成網的程度，即網絡連通性的大小，圈性越大連通性越好。而樹性則表示路網呈現(xiàn)樹狀結構的程度。樹性大的網絡，網絡結構相對簡單，道路的建設成本相對較少。圈性和樹性是一對相對的概念，圈性越大的網絡其樹性越小，反之亦然。隨著城市規(guī)模的不斷擴張，城市道路長度也在不斷增加，城市道路網卻顯得越來越擁堵，如何在有限的資源約束下，更加合理地規(guī)劃城市的道路網絡，找出道路長度一定情況下，承載力最大時網絡的圈性大小顯得尤為重要。在保證網絡連通的前提下，通過對節(jié)點數(shù)相同的全連通網絡隨機刪除網絡中的邊，最終得到邊數(shù)相同，圈性不同的連通網絡。從而建立具有不同圈性特性的路網結構演化模型，并對得到的網絡進行UE平衡配流，研究了不同網絡上的流量分布特性，通過對不同網絡結構不斷加載相同單位流量，探討了網絡結構與城市交通承載力之間的相關關系。研究發(fā)現(xiàn)，在逐步向網絡加載流量的過程中，圈性較大的網絡和圈性較小的網絡均比較快達到擁堵狀態(tài)，而圈性在0.5左右時，網絡的承載能力反而更大。由此可知，網絡的承載力隨著圈性的逐漸增大呈現(xiàn)出先增大后減小的趨勢。從而找到承載力最大的網絡結構，通過研究路網演化過程中交通承載力的變化，探討了城市交通承載力與路網結構之間的協(xié)同演化關系，揭示了隨著路網結構的變化，承載力的變化規(guī)律。為合理規(guī)劃道路結構，緩解交通擁堵提供一定的依據(jù)。

1 網絡產生機制

1.1 交通道路網絡結構特征參量

為了研究道路網絡成環(huán)成網的特性對網絡承載流量的影響，引入Haggett等[14]在1969年提出的圈和樹的概念。即對于一個連通的網絡來說，如果從網絡上某一點出發(fā)經過若干條邊(大于等于3)之后還能回到起點，則稱經過的這些邊圍成了一個圈，稱在圈上的邊為圈邊。如果一條邊只在一個圈上則認為這條邊屬于一個環(huán)，如果一條邊屬于多個圈就表明這條邊在網上，如果一個邊不在任何圈上則認為這條邊在樹上，稱這條邊為樹邊。用圈性(φcircuit)表示城市道路網絡成環(huán)成網的程度，樹性(φtree)表示城市道路網絡成樹狀程度。不考慮每條邊的長短差異和每條道路的等級差異，給出路網圈性及樹性的計算公式

(1)

φcircuit=1-φtree

(2)

其中，m為網絡中屬于樹的邊的個數(shù)，n為網絡中邊的個數(shù)。

本文通過鄰接矩陣表示兩個點之間是否有邊相連，相連的為1，不相連的為0，因為道路網絡為無向圖，所以鄰接矩陣為主對角元素為0的對稱矩陣A。則網絡中邊的個數(shù)m為網絡中所有非零元素和的一半。假設lij為網絡中i點到j點的一條邊(即Aij=1)，若去掉該邊之后網絡不連通了，則說明該條邊為樹邊，否則為圈邊。

1.2 圈性網絡產生機制

節(jié)點為q的全連通的網絡通過逐漸刪除網絡中的邊，得到給定邊數(shù)為N，不同圈性的網絡結構的生成過程為：

步驟1：生成一個全連通網絡(即生成一個對角線元素為0其他元素均為1的鄰接矩陣A)；

步驟2：隨機刪除一條邊(即在鄰接矩陣中隨機找到一個非零元素Aij，令Aij=0,Aji=0)判斷刪除邊后網絡連通性，若不連通則將刪除的邊恢復(即令Aij=1,Aji=1)重復執(zhí)行步驟2。若網絡連通，則執(zhí)行步驟3；

步驟3：計算網絡的圈性φ0，判斷是否滿足φ0>φn(φn為終止條件)，若不滿足，則將刪除的邊恢復(Aij=1,Aij=1)。計算網絡中剩余邊的個數(shù)；

步驟4：重復步驟2，計算網絡的圈性，判斷是否滿足φk>φn，若不滿足，則將刪除的邊恢復(Aij=1,Aji=1)；

步驟5：重復步驟2，3，4。當剩余的邊數(shù)n=N時停止循環(huán)。得到需要的網絡;

步驟6：為了便于比較不同φn值對城市交通網絡承載力的影響，對于給定的不同φn值，重復以上步驟2至5，便可以得到滿足給定圈性值的網絡。

2 流量加載

2.1 用戶平衡配流

1952年，Wardrop[15]提出平衡配流原則：在起訖點之間所有可供選擇的路徑中，所有被使用者利用的各條路徑上的出行費用全都相等，而且不大于未被利用路徑上的出行費用。又可稱為用戶平衡配流(User Equilibrium，簡稱UE)。滿足這一原則的交通狀態(tài)被定義為Wardrop平衡狀態(tài)，Beckmann采用以下數(shù)學形式描述Wardrop平衡狀態(tài)：

(3)

通常情況下，UE平衡配流問題被認為是一個凸規(guī)劃問題，1956年Beckmann等[16]提出了一種滿足Wardrop原則的數(shù)學規(guī)劃模型:

(4)

(5)

(6)

(7)

(8)

其中，xa為路段a上的交通量，ta為路段a上流量為xa時的阻抗，I為產生交通量的起始節(jié)點的集合，J為交通量的終訖節(jié)點的集合，i為一個起始節(jié)點，?i∈I,j為一個終訖節(jié)點，?j∈J，qij為O-D對i-j的交通需求量。

該模型中的目標函數(shù)是所有路段阻抗函數(shù)積分的和，方程(5)代表路徑流量與O-D流量之間的守恒關系，方程(6)保證了所有路徑的流量都是非負的，方程(7)是路段流量與路徑流量之間的關聯(lián)關系，有：

(9)

需要注意的是，該用戶均衡配流模型必須滿足以下兩個假設：1)路段的阻抗僅僅是該路段流量的函數(shù)，與其他路段上的流量沒有聯(lián)系；2)假設路段阻抗是流量的嚴格增函數(shù)。用數(shù)學形式表示為

(10)

隨機給定各個路段的零流阻抗t0，任意兩點之間的O-D交通量都是相同的，即O-D需求矩陣是對角線為0其余元素均為1的對稱矩陣。按照用戶均衡理論對演化得到的網絡分別進行流量加載，則流量為xa時路段的阻抗函數(shù)按照美國公路局提供的(U.S.BureauofPublicRoads—BPR)公式計算。

(11)

其中，xa為路段a上的交通量，ua為路段a的最大承載流量，ta為路段a上流量為xa時的阻抗，α，β為固定參數(shù)，模型中取α為0.15，β為4。

2.2 算法

對于該模型的求解一般用Frank-Wolfe方法，該算法是Frank和Wolfe[17]于1956年求解線性約束問題時提出的，通常簡稱F-W算法。算法的基本思想是，在每次迭代中，將目標函數(shù)線性化，通過解線性規(guī)劃來求得下降可行方向，進而沿此方向在可行域內作一維搜索以得到新的迭代點。

迭代次數(shù)為n時，目標函數(shù)值Z(x)下降的搜索方向應由求解下面的線性規(guī)劃問題得到：

minZn(y)=

(12)

(13)

(14)

(15)

(16)

該模型實際上是在各路段阻抗固定為ta的條件下使網絡總阻抗最小的經典運輸問題。F-W算法的具體求解過程可參見參考文獻[18]。

2.3 擁堵度

對于既有的路段，如果路段上的流量超過了其最大的承載流量則認為該路段處于擁堵狀態(tài)。在本模型中，假設一共有N條路段，給定路段a(a∈N)最大承載流量為ua，零流阻抗為t0。假設通過用戶平衡配流最終達到平衡狀態(tài)的過程中，每一步迭代，所有O-D對之間均產生一個單位的交通流量。因此可以確定平衡狀態(tài)下每條路段上的交通流量。如果某條路段上的交通流量超過其最大承載流量，則說明該路段屬于擁堵路段，且記擁堵路段數(shù)目T加1。計算公式為

(17)

觀察不同拓撲結構網絡的擁堵路段的變化情況，進而分析出不同網絡結構中最優(yōu)的拓撲結構。道路交通狀態(tài)用道路交通擁堵程度表示，即實際發(fā)生的交通擁堵路段與城市道路總路段的比值．按照計算公式(18)：

(18)

其中，e為網絡的擁堵程度，T為網絡中擁堵路段的個數(shù)，L為網絡中總的路段的個數(shù)。

3 算例分析

3.1 網絡的生成及流量分配

以節(jié)點數(shù)為50的網絡為例，在節(jié)點全連通的情況下，按照前面分析的方法，得到邊數(shù)為56，圈性為0.33,0.43,0.54,0.66,0.75,0.86,0.96的網絡的鄰接矩陣，在考慮網絡拓撲特性的基礎上研究分析了不同圈性情況下，對網絡中的道路隨機分配道路的容量，按照UE平衡原理，對不同網絡逐次加載相同流量。分析不同圈性情況下，網絡承載流量變化情況。計算隨著不斷給網絡加載流量，不同網絡結構下路段擁堵情況的變化，最終找出相同流量下，網絡的擁堵度最小時網絡的圈性大小，即得到比較適合的圈性大小的網絡結構。

3.2 結果分析

分別對不同圈性的網絡進行流量加載250步，可以得到不同圈性的網絡承載相同流量的擁堵程度變化如圖1所示。從圖1中可以看出隨著流量的增加，即在網絡的交通流從自由流向擁堵流演化的過程中，擁堵路段的增加量是逐漸減少的。

分別取流量加載次數(shù)初始階段(如圖2a)和流量趨于飽和階段(如圖2b)的網絡擁堵狀況進行分析。從圖2a和圖2b對比可以看出，不同網絡之間的擁堵度差異隨著流量的加載有不斷擴大的趨勢。這就說明在交通流量較小的情況下網絡的圈性大小對交通擁堵程度的影響并不明顯，但是隨著網絡中交通量的大幅增加，網絡拓撲結構的影響也逐漸明顯。從圖2b中可以明顯看出圈性為0.54的網絡在同等迭代次數(shù)條件下?lián)矶鲁潭仁亲钌俚?，而圈性?.33和0.96的網絡擁堵程度是較高的。也就是說在城市道路自由演化的過程中圈性為0.54左右的道路網絡在相同條件下能承載更多的流量，更能適應由于城市的不斷發(fā)展而不斷增加的交通流量的需求，相同情況下，該網絡結構的交通壓力更小。

圖1 不同圈性網絡擁堵度隨流量增加的變化

圖2 不同圈性網絡的擁堵情況

分別對迭代100步，150步，200步和250步的不同圈性下的擁堵程度做進一步分析，如圖3所示。從圖3可以看出，隨著迭代次數(shù)的增加,不同圈性網絡在承載相同流量情況下的擁堵路段的增加量的變化逐漸趨于平和，這與隨著迭代次數(shù)的增加，流量逐漸趨于飽和是有關系的。說明不同圈性情況下隨著迭代次數(shù)的不斷增加，網絡最終的演化方向都是趨于全部擁堵。從圖3中可以清楚地看出在迭代次數(shù)相同的情況下，隨著圈性的不斷增大，網絡擁堵情況的變化趨勢是先減少后增大的。也就是說，圈性為0.5左右的時候是擁堵情況較小的網絡結構。

以北京地鐵網絡為例，將各個地鐵站看成一個節(jié)點，兩個站點之間的線路看成一條無向的邊，換乘站不同線路近似看成相交于同一個點，不考慮換乘站的換乘距離和換乘時間，則可以把地鐵網絡看成一個無向圖。按照前面所說的理論，統(tǒng)計出地鐵網絡中屬于環(huán)上的邊有156條，屬于邊上的邊有105條，按照前面所給公式可以計算出北京地鐵的圈性為0.597 7，與結果分析中一致，是承載力較大的網絡結構。

圖3 相同迭代次數(shù)不同圈性的擁堵情況

4 總結與展望

近些年復雜網絡的快速發(fā)展為緩解交通擁堵問題提供了一個全新的思路，它從拓撲結構上說明了什么樣的網絡拓撲結構是有利于城市交通的發(fā)展的。隨著計算機技術的不斷發(fā)展和復雜網絡的深入研究，通過對網絡的模擬仿真即可分析得到網絡的拓撲特性，為解決交通擁堵問題提供新的途徑。本文主要結合了網絡拓撲結構和UE均衡配流，運用計算機模擬，研究了不同圈性網絡條件下路網的承載能力變化，而造成城市交通擁堵的因素有很多，除了經濟的發(fā)展與交通基礎設施建設的不協(xié)調、城市交通管理混亂，既有交通缺乏整合之外，最重要的是車輛增加過快和路網結構不合理。單純依靠修建一條道路來緩解交通擁擠問題不僅需要投入大量的資本，還有可能產生更大的擁堵出現(xiàn)Braess詭異現(xiàn)象，使得交通擁堵問題更加嚴峻。因此，尋找最大承載力的路網拓撲結構有著非常重要的現(xiàn)實意義。尤其是對新城區(qū)的建設，不僅可以使得新城區(qū)快速發(fā)展又可以避免其日后陷入擁堵的狀況，還能減少開支，避免資源的浪費。

本文僅是從網絡的樹性和圈性這一方面來分析了拓撲結構對網絡承載力的影響，對于理解網絡的拓撲結構和弄清網絡的性能有很大幫助。今后將環(huán)型、放射型、網狀、蜂窩狀等網絡拓撲結構與復雜網絡中的規(guī)則網絡、隨機網絡、小世界網絡、無標度網絡相結合進行定量研究，探索出承載力最大的網絡拓撲結構。

[1]Ford L R Jr, Fulkerson D R. Solving the transportation problem [J].Management Science.1956， (10): 24-32.

[2]Asakura Y. Maximum capacity of road network constrained by user equilibrium conditions [C]//The Proceeding of 24th Annual Conference of the UTSG，Newcastle，1992:4.

[3]Yang H, Bell G H，Meng Q. Modeling the capacity and level of service of urban transportation network[J]. Transportation Research Part B,2000,34(4):255-275.

[4]侯德勛． 城市交通承載力研究[D].上海: 同濟大學, 2008． Hou De Xun. The study of traffic carrying capacity[D]. Shanghai： Tongji University, 2008.

[5]詹歆曄，郁亞娟，郭懷成，等.特大城市交通承載力定量模型的建立與應用[J].環(huán)境科學學報，2008，28(9)：1923-1931 Zhan Xinye, Yu Yajuan, Guo Huaicheng, et al. Modeling and application of metropolitan transportation support capacity[J].Acta Scientiae Circumstantiae, 2008,28(9): 1923-1931.

[6]李榮，吳建軍.北京市交通承載力預測研究[J].山東科學，2013,26(2):98-111. Li Rong, Wu Jianjun.Prediction of Beijing traffic carrying capacity[J]. Shandong Science.2013.26(2):98-111.

[7]Li Tongfei, Wu Jianjun. Carrying capacity of urban traffic network: modeling and empirical analysis[C] //2013 International Conference on Industrial Engineering and Management Science. Shanghai:DEStech，2013, 566-572.

[8]王乾，雷黎．基于灰色預測模型的交通環(huán)境承載力研究[J].科學之友,2008,7(20) :70-72． Wang Qian, Lei Li. Study on traffic capacity based on grey forecasting model [J].Friend of Science Amateurs,2008,7(20):70-72.

[9]吳建軍.城市交通網絡拓撲結構復雜性研究[D].北京：北京交通大學，2008. Wu Jianjun. The study of Urban traffic network topology complexity[D]. Beijing： Beijing Jiaotong University, 2008.

[10]賈順平，彭宏勤，劉爽． 基于居民出行特性與路網承載力的城市交通狀態(tài)研究[J]． 交通運輸系統(tǒng)工程與信息，2011,11(5) : 81-85． Jia Shunping, Peng Hongqin, Liu Shuang. Urban traffic state estimation considering resident travel characteristics and road network capacity[J].Journal of Transportation Systems Engineering and Information Technology, 2011,11(5):81-85.

[11]許明濤，吳建軍． 基于容量限制的道路與城市交通的互演化研究[J].山東科學，2012， 25( 4) :58-63． Xu Mingtao, Wu Jianjun. Research on limited capacity based co-evolution of road surface and urban traffic[J]. Shandong Science, 2012,25(4):58-63．

[12]Zhao F X, Sun H J, Wu J J, et al. Urban road network evolution to maximize the capacity[J]. Procedia-Social and Behavioral Sciences, 2014, 138: 251-258.

[13]龍雪琴, 王建軍, 關宏志. 基于建設成本約束的公路網結構演化研究[J]. 交通運輸系統(tǒng)工程與信息, 2014, 14(4): 23-29. Long Xueqin, Wang Jianjun, Guan Hongzhi. Self-organization of roads network structure based on restraint of construct cost[J]. Journal of Transportation Systems Engineering and Information Technology,2014, 14(4): 23-29.

[14]Haggett P, Chorley R J. Network Analysis in Geography[M]. London: Edward Arnold, 1969.

[15]Wardrop J G. Some theoretical aspects of road traffic research[C]//ICE Proceedings Engineering Divisions. London:Thomas Telford, 1952, 1(3): 325-378.

[16]Beckmann M J, McGuire C B, Winsten C B. Studies in the economics of transportation[M]. New Haven:Yale University Press, 1956.

[17]Frank M, Wolfe P. An algorithm for quadratic programming[J].Naval Research Logistics Quarterly,1956,3:95-110.

[18]黃海軍. 城市交通網絡平衡分析: 理論與實踐[M]. 北京:人民交通出版社, 1994.

(責任編輯 耿金花)

Carrying Capacity Analysis of the Urban Traffic Network Under Different Circuitness

YANG Guojing,WU Jianjun

(State Key Laboratory of Rail Traffic Control and Safety, Beijing Jiaotong University, Beijing 100044,China)

In this paper, we establish the evolution mechanism of the circuitness of the urban traffic network, and obtain the different topologies of networks. Then, we study the traffic carrying capacity under different network topology structure. As a result, with the increasing network traffic flow, it is much easier to be saturated for the smaller and larger cirucitness. On the contrary, the network has the largest carrying capacity when the circuitness is about 0.54.

urban traffic; network carrying capacity; network structure; circuitness

1672-3813(2015)04-0036-07;

10.13306/j.1672-3813.2015.04.005

2014-08-01 ；

2014-11-06

國家自然科學基金(71271024)；教育部新世紀優(yōu)秀人才支持計劃(NCET-12-0764)

楊國菁(1989-)，女，河南新鄉(xiāng)人，碩士研究生，主要研究方向為交通運輸系統(tǒng)分析與集成。

U491.1

A