基于拓撲改變的地鐵網絡承載能力優化方法

孫 磊 李 榮 陳孝國

(1.浙江建設職業技術學院經濟管理系,311231，杭州; 2.浙江商業職業技術學院財金學院，310053，杭州；3.黑龍江科技大學理學院,150022,哈爾濱∥第一作者，講師)

?

基于拓撲改變的地鐵網絡承載能力優化方法

孫 磊1李 榮2陳孝國3

(1.浙江建設職業技術學院經濟管理系,311231，杭州; 2.浙江商業職業技術學院財金學院，310053，杭州；3.黑龍江科技大學理學院,150022,哈爾濱∥第一作者，講師)

基于復雜網絡理論,提出一種利用拓撲結構改變策略來提高地鐵網絡承載能力的方法。首先，確定地鐵網絡的最大介數站點;其次，使得通過該站點的某條地鐵線路在該站點越站運行;最后，以北京地鐵網絡進行仿真試驗。結果表明:該策略下北京地鐵網絡最大介數站點的介數值大幅下降,各站點的介數分布得到優化。該方法有效提高了地鐵網絡的承載能力,但由于負荷的重新配置,有些地鐵線路會出現客流量激增現象,需提早做好應對措施。

地鐵網絡; 承載能力; 拓撲結構改變策略

First-author′s address Department of Economic Management, Zhejiang College of Construction Technology, 311231,Hangzhou,China

復雜網絡是研究復雜系統拓撲結構和行為的關鍵因素。小世界網絡模型[1]與無標度網絡模型[2-3]的提出在全球范圍內引發了復雜網絡研究的浪潮。起初的研究主要集中在網絡的拓撲結構上,隨著研究的深入,人們開始關注網絡上的動力學過程,輸運模型(Traffic Routing Model)[4-5]的研究受到極大的關注。以往關于輸運模型的研究,主要針對網絡承載能力(即單位時間內網絡所能承受的最大進入負荷數,超過這一值,網絡就會出現擁堵狀態)。并提出許多提高承載能力的方法。

關于網絡承載能力的決定因素研究，文獻[4]提出了承載能力的推導公式：

(1)

式中：

D——該網絡的平均最短路徑；

Lmax——最大介數節點的編號；

Rc——網絡的相變臨界負荷個數；

BLmax——最大介數節點的介數值；

CLmax——最大介數節點的處理能力；

Bj——節點j的介數。

式(1)表明，在各節點處理能力(即節點能允許同時通過的最大負荷數)C相同的前提下,Rc受最大介數節點的制約,與最大介數節點的介數值成反比。因此，在其他條件不變的前提下,降低最大介數節點的介數值,可有效提高網絡的承載能力。這也是本文研究的出發點。

提高網絡承載能力的方法主要包括負荷行走路徑改變策略和拓撲結構改變策略兩種。實質就是通過策略實施,使得部分負荷運動繞過網絡最大介數節點,從而有效降低最大介數節點的介數值,進而提高網絡的承載能力。文獻[6-7]提出通過改變負荷的行走策略從而有效提高網絡的承載能力。文獻[8]證明均勻網絡由于缺少高介數節點而表現出更大的網絡承載能力。文獻[9]指出點或邊的移除能夠減輕甚至緩和網絡上由于過載造成的故障。文獻[10]提出了拓撲結構改變策略,通過增加或減少一些邊來改變網絡結構,從而提高網絡的承載能力；指出增加點或邊的成本較大,最簡單且成本最低的策略就是刪除點或邊，并提出HDF(High-Degree-First)策略。首先根據km×kn的乘積排序,其中km、kn是邊的兩端節點的度；然后根據排序，從大到小依次關閉對應的邊。因為HUB節點(網絡中連接數非常大的節點)非常重要,且承載非常多的負荷,km×kn越大則對應的邊越容易擁堵。所以,移除它會導致負荷的重新分流,進而增強網絡的處理和運輸能力。結果顯示,根據km×kn來關閉某些邊可以顯著提高網絡的承載能力。文獻[11]提出HBF(High-Between-First)策略,其將HDF策略稍加改變,采用介數來代替度。仿真結果顯示,HBF策略的效果好于HDF策略。文獻[12]提出VNDR(Variance-of-Neighbor-Degree-Reduction)策略,該策略不僅考慮到HUB節點的重要性,還通過降低某些節點的鄰居節點之間的度差異性來平衡這些節點到鄰居節點的負荷數量。仿真結果表明，該策略的效果要好于HBF策略,但復雜程度較高。

近年來利用復雜網絡理論進行交通網絡的研究越來越受到關注。文獻[13]運用復雜網絡理論對上海軌道交通近期(2012年)規劃網絡拓撲結構進行了分析。文獻[14]設計了軌道交通運營網絡的連通可靠性仿真分析的新算法,并應用到上海軌道交通遭受攻擊后的連通性分析上。在交通網絡中通過網絡拓撲結構改變策略來提升交通能力的研究也被經常報道。在高速公路網絡中,為了緩解高峰期交通壓力,往往關閉一些道路,而要實現道路的關閉,交管部門只需要關閉這些道路的入口。隨著社會的快速發展,交通網絡的規模越來越大,這帶給交通管理部門新的挑戰。考慮到增加點和邊所帶來的成本,交通管理部門在交通規劃時必須小心謹慎,因為不正當的加入點和邊,不但不能緩解交通反而會惡化交通。例如，2003年12月29日,連接上海交通大學徐匯校區和閔行校區的滬閔高架路正式開通,很多原來走不同道路的司機在當天早上都選擇滬閔高架,致使車輛過多造成嚴重擁堵。

地鐵網絡不同于一般的交通網絡。在一般的交通網絡中關閉某一條邊,不影響交通網絡的正常運行。地鐵列車只能在規定的線路上運行,不能關閉地鐵線路中的某段線路,否則該線路無法正常運行。基于此,本文提出一種適合地鐵網絡的拓撲結構優化策略,通過降低最大介數節點的介數值,從而有效提高地鐵網絡的承載能力。同時還關注到不同策略實施對地鐵網絡造成的后續影響。

1 基礎知識

1.1 輸運模型

為了模擬現實網絡,引入輸運模型。考慮到網絡的拓撲結構及網絡上的負荷運動,做以下假設:

首先,每時每刻進入網絡的負荷數為R,這些負荷的起點和終點隨機在網絡上產生,負荷按照最短路徑行進(當起點和終點之間存在多條最短路徑時,隨機選取一條);每時每刻也有負荷到達目的地,而在下一時刻從網絡中消失。

其次,網絡中每個節點都有一定的負荷處理能力C,本文實證分析中設地鐵網絡各站點C=10。當通過某節點的負荷超過其處理能力時,會產生局部擁堵,導致網絡上的負荷集聚，進而增大負荷到達目的地的難度。

第三,在網絡中每個負荷都有它的目的地,即使在出現擁堵的情況下,也不會改變自己的行進路線,只會延長通過擁堵節點的等待時間。此外，負荷通過節點時按照到達該節點的時間順序“先進先出”。

1.2 節點介數的定義

在使用最短路徑路由算法的網絡中,節點介數指標刻畫負荷經過給定節點的可能性。節點介數值大,節點在網絡中就居于核心地位。具體定義如下:

(2)

式中：

ghk——節點h和節點k之間的最短路徑數；

ghk(j)——節點h和節點k之間經過j的最短路徑數；

(N-1)(N-2)/2——最大可能的點介數。

2 地鐵網絡拓撲結構優化策略

考慮到地鐵網絡的實際情況,做以下幾點假設:① 人是理性的,人在既定的條件下,在起點和目的地之間總會選擇最短路徑策略;② 對于地鐵網絡,線路是固定的,若起點和目的地不在同一條線路上,負荷需要通過換乘站點換乘才能到達目的地,為方便研究,換乘成本忽略不計。以北京地鐵網絡西直門站點為例介紹拓撲結構優化策略(以下簡為“TC策略”)的實現過程。西直門站點處于2號線和4號線的交匯處,兩種TC策略如下:

(1) TC 1策略：2號線在西直門站越站運行。對應到地鐵網絡拓撲結構上,42站點(西直門站)、41站點(積水潭站)和43站點(車公莊站)的邊刪除,直接在41站(積水潭站)和43站(車公莊站)之間連邊,如圖1所示。

圖1 2號線在42站點越站運行前后的拓撲結構

(2) TC 2策略：4號線在西直門站點越站運行。對應到地鐵網絡拓撲結構上,42站點(西直門站)、136站點(新街口站)和137站點(動物園站)的邊刪除,直接在136站點(新街口站)和137站點(動物園站)之間連邊,如圖2所示。

圖2 4號線在42站點越站運行前后的拓撲結構

3 試驗數據對比

3.1 2004—2013年北京地鐵網絡的發展變化

從客運量來看,2004年北京地鐵年客運量達到6.066 8億人次,創歷史新高,比2003年增長28.57%;2013年北京地鐵年客運量達32.09億人次,比2012年增長28.7%,比2004年增長4.29倍。從運營線路長度來看,2004年底北京地鐵的運營線路為4條,長度為114 km;2013年底,北京地鐵共有17條運營線路,長度達465 km。2013年底北京地鐵運營線路如圖3所示。表1為北京地鐵拓撲結構網絡中介數排名前10位的站點，其中的數據通過MATLAB軟件和PAJEK軟件[15]計算所得。

圖3 2013年北京地鐵運行網絡圖

3.2 基于HBF策略的北京地鐵網絡各站點介數變化情況

從表1可以看出,42(西直門站)和43(車公莊站)站點的介數值排名居前兩位。刪除這兩個站點之間的邊,觀察刪除后地鐵網絡各站點介數的變化情況。考慮到HBF策略不適用于地鐵網絡,這里只進行方法上的對比。具體數據如表2所示。

表2顯示:HBF策略下，地鐵網絡的最大介數節點仍是42(西直門站)站點,其介數值從0.266 9下降到0.235 9,降幅達12%。網絡承載能力有所提升,從最初的35上升到40。而43(車公莊站)站點的介數值從0.211 5下降到0.078 4,降幅高達63%。

表1 介數值排名前10位的站點

表2 HBF策略下介數值排名前10位的站點

3.3 基于TC策略的北京地鐵網絡各站點介數變化情況

3.3.1 TC策略下介數值排名前10位的站點

基于上述兩種TC策略的地鐵網絡各站點介數變化情況如表3和表4所示。

表3 TC 1策略下介數值排名前10位的站點

表4 TC 2策略下介數值排名前10位的站點

由表3可以看出,TC 1策略實施后，可以將網絡的最大介數節點的介數值從42站點(西直門站)的0.266 9降為26站點(軍事博物館站)的0.209 5,降幅達22%。網絡承載能力從最初的35大幅上升到45。而42站點(西直門站)的介數值大幅下降到0.124 8,降幅達53%。

由表4可以看出,TC 2策略實施后，網絡的最大介數節點的介數值從42站點(西直門站)的0.266 9小幅上升為43站點(車公莊站)的0.271 8。網絡承載能力從最初的35小幅下降到34。而42站點(西直門站)的介數值下降到0.240 6,降幅為10%。

3.3.2 TC策略下介數值增幅排名前5位的站點

TC策略下地鐵網絡各站點介數值增幅排名前5位的站點如表5和表6所示。

表5 TC 1策略下介數值增幅前5位的站點

表6 TC 2策略下介數值增幅前5位的站點

從表5中可以看出,TC 1策略實施后，136(新街口站)和135(平安里站)站點的介數值大幅增加,尤其是136(新街口站)站點,介數值從0.019 0大幅上升到0.085 8。

從表6中可以看出,TC 2策略實施后，43(車公莊站)和202(車公莊西站)站點的介數值大幅增加,均超過0.05。

4 結語

以往的研究表明,網絡的承載能力受最大介數節點的制約,降低網絡最大介數節點的介數值，等價于提高網絡的承載能力。基于此,考慮到地鐵網絡的實際特點,本文提出TC策略來有效降低地鐵網絡站點的最大介數值,達到提高網絡承載能力的目的，并以北京地鐵網絡為底層拓撲結構,實證分析各種拓撲結構改變策略的具體做法,以及對網絡各站點介數的影響。結果顯示:

(1) TC策略對改善北京地鐵網絡的承載能力效果顯著。不同的拓撲結構改變策略對網絡承載能力的影響大不一樣。TC 1策略的效果最顯著,其將地鐵網絡最大介數節點的介數值從0.266 9降為0.209 5,下降幅度高達22%,從而有效提高網絡的承載能力,而42(西直門站)站點的最大介數節點地位由26(軍事博物館站)站點取代;TC 2策略實施后，網絡的最大介數節點的介數值從42站點(西直門站)的0.266 9小幅上升為43站點(車公莊站)的0.2718,網絡的承載能力反而小幅下降;HBF策略下，地鐵網絡的最大介數節點仍是42(西直門站)站點,介數值從0.266 9下降到0.235 9,下降幅度為12%,網絡的承載能力有所提升。

(2) TC策略實施對地鐵網絡的后續影響不容忽視。改變網絡拓撲結構,使得負荷繞開HUB節點,負荷分配更加均勻,從而有效提高網絡承載能力。不同的策略實施后,會導致不同的負荷分配,例如，TC 1策略實施后，136(新街口站)和135(平安里站)站點的介數值大幅增加,由于這兩個站點均在4號線上,預示著2號線在42(西直門站)站點越站運行后,會有更多的客流選擇4號線;TC 2策略實施后，43(車公莊站)和202(車公莊西站)站點的介數值大幅增加,預示著4號線在42(西直門站)站點越站運行后,會有更多的客流選擇6號線。

[1] WATTS D J,STROGATZ S H.Collective dynamics of small world networks[J].Nature,1998,393:440.

[3] ALBERT R,BARABSI A L.Statistical mechanics of complex networks[J].Rev of Modern Phys,2002,74:47.

[4] ZHAO L,LAI Y C,PARK K,et al.Onset of traffic congestion in complex networks[J].Physical Review E,2005,71(2):026125.

[6] WANG W X,WANG B H,YIN C Y,et al.Traffic dynamics based on local routing protocol on a scale-free network[J].Physical Review E,2006,73(2):026111.

[7] WANG W X,YIN C Y,YAN G,et al.Integrating local static and dynamic information for routing traffic[J].Physical Review E,2006,74(1):016101.

[8] GUIMERA R,ARENAS A,DAZ-GUILERA A,et al.Dynamical properties of model communication networks[J].Physical Review E,2002,66(2):026704.

[9] MOTTER A E.Cascade control and defense in complex networks[J].Physical Review Letters,2004,93(9):098701.

[10] LIU Z,HU M B,JIANG R,et al.Method to enhance traffic capacity for scale-free networks[J].Physical Review E,2007,76(3):037101.

[11] ZHANG G Q,WANG D,LI G J.Enhancing the transmission efficiency by edge deletion in scale-free networks[J].Physical Review E,2007,76(1):017101.

[12] HUANG W,CHOW T W S.An efficient strategy for enhancing traffic capacity by removing links in scale-free networks[J].Journal of Statistical Mechanics:Theory and Experiment,2010,2010(1):P01016.

[13] 王燚,楊超.上海市軌道交通網絡的復雜網絡特性研究[J].城市軌道交通研究,2009(2):33.

[14] 丁小兵.復雜網絡理論及其在上海城市軌道交通網絡可靠性分析評價中的應用[J].城市軌道交通研究,2012(11):50.

[15] De NOOY W,MRVAR A,BATAGELJ V.Exploratory social network analysis with Pajek[M].Cambridge：Cambridge University Press,2011.

Subway Network Capacity Improvement Based on Topology Change

SUN Lei, LI Rong, CHEN Xiaoguo

Based on complex network theory, an approach to improve the capacity of subway network by usingthe strategy of topological structure change is proposed. Firstly, the site with the largest betweenness is determined; secondly, a subway line passing through this site is arranged to overtake the station; and finally, Beijing subway network is taken for simulation. Results show that the largest betweenness value of Beijing subway network is reduced dramatically under this strategy, and the betweenness distribution of all the sites is optimized. This method can improve the capacity of Beijing subway network, but due to the re-assignment of transport loads, surges in passenger traffic on some lines will certain happen, so necessary measures should be taken as early as possible.

subway network; network capacity; strategy of topological structure change

U292.5∶U231

10.16037/j.1007-869x.2016.04.001

2014-04-30)