基于K-最短路徑的交通網(wǎng)絡(luò)傳輸性能分析

，，

(1.浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023；2.浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州 310023)

隨著互聯(lián)網(wǎng)[1]、手機(jī)移動(dòng)網(wǎng)絡(luò)[2-4]以及公共交通[5-6]等現(xiàn)代設(shè)施的出現(xiàn)和改善，有效的信息傳輸和交互顯得越發(fā)的重要[7-8].在這樣日新月異的環(huán)境下，如何有效地提高系統(tǒng)的傳輸效果是人們不斷追求的目標(biāo)，而交通網(wǎng)絡(luò)作為與人們關(guān)系最為緊密的網(wǎng)絡(luò)系統(tǒng)之一，一直是我們關(guān)注和研究的焦點(diǎn).現(xiàn)階段大部分改善交通網(wǎng)傳輸效果的手段都著眼于控制客流(單雙號(hào)限行、單行道設(shè)置等具體手段)或者調(diào)整道路網(wǎng)結(jié)構(gòu)，它們作為改變傳輸結(jié)果的兩項(xiàng)基本手段，能協(xié)調(diào)網(wǎng)絡(luò)流量分布、提高網(wǎng)絡(luò)傳輸效率[9-11]，但同時(shí)它們也存在著不足之處：道路網(wǎng)結(jié)構(gòu)的改變所需成本太大、時(shí)間太長；大部分通過限制出行手段進(jìn)行的客流控制只能處于輔助地位，改善效果甚微.如果能找到除改變結(jié)構(gòu)和控制客流之外的有效提高交通網(wǎng)傳輸效果的方法，不僅能增加管理道路網(wǎng)的有效手段，同時(shí)也能為網(wǎng)絡(luò)優(yōu)化及其他網(wǎng)絡(luò)問題的研究提供思路.現(xiàn)階段對(duì)于交通網(wǎng)傳輸?shù)难芯糠绞酱蠖嘀谧疃搪窂缴蟍12-13]，但實(shí)際生活中以最短路徑作為傳輸方式卻很少，原因是當(dāng)距離較遠(yuǎn)時(shí)，擁堵及其他各種不利因素就會(huì)變得非常嚴(yán)重[14-15]，導(dǎo)致實(shí)際中人們無法保持最短路徑(不僅僅是路徑長度最短，在這里可以將其視為出行成本最小)的傳輸方式.

為了解決道路擁堵、提高交通流量分布的協(xié)調(diào)性及節(jié)點(diǎn)利用率，研究了更好反應(yīng)現(xiàn)實(shí)生活中人們出行的K-最短路徑的路由方式[16].具體步驟是利用模擬的隨概率變化的交通流需求，研究DTN網(wǎng)絡(luò)(用于模擬實(shí)際道路交通網(wǎng)絡(luò))中的交通流特性.在該網(wǎng)絡(luò)上使用K-最短路徑的路由算法，發(fā)現(xiàn)隨著K值增大，網(wǎng)絡(luò)的平均路徑長度隨之增大、描述交通流分布非均勻性的基尼系數(shù)減小，隨后定義一個(gè)綜合考慮基尼系數(shù)和平均路徑長度的優(yōu)化指標(biāo)，通過優(yōu)化指標(biāo)驗(yàn)證該路由方式的有效性.

1 擁堵問題的提出

1.1 交通流分布

交通流分布的是否合理將影響道路網(wǎng)運(yùn)行的良好與否，具體表現(xiàn)在如下兩方面：首先流量分布是否合理對(duì)擁堵的發(fā)生至關(guān)重要，每條交通路線上都存在交通流容量上限值，當(dāng)路線上分配的交通流大于其上限值時(shí)，就會(huì)發(fā)生擁堵；其次流量分布是否合理也影響網(wǎng)絡(luò)中節(jié)點(diǎn)利用率的高低，如果道路網(wǎng)上部分路線交通流量巨大，剩余路線交通流量稀少，那么就會(huì)出現(xiàn)網(wǎng)絡(luò)中部分節(jié)點(diǎn)的利用率偏低甚至發(fā)生“閑置”現(xiàn)象.由此可見合理分配交通流，使其不過于集中，就可以解決交通擁堵問題和部分節(jié)點(diǎn)和路線的利用率偏低的問題.

交通流的集中由兩方面的原因：首先是道路網(wǎng)中節(jié)點(diǎn)和路線設(shè)置的不合理，使人流聚集地的交通流容量值較低，例如城市工作地點(diǎn)相對(duì)集中，但較低的容量卻使無法在短時(shí)間內(nèi)分散這些人流從而形成的早晚高峰.其次是擇路方式的不合理，當(dāng)有多條路線可選的情況下，人們大多采取最短路徑的方式進(jìn)行擇路，相對(duì)于整個(gè)交通網(wǎng)絡(luò)來講，這種擇路方式容易集中交通流.通過改變路由從而減緩交通流聚集的方式，減小節(jié)點(diǎn)流量的“貧富差距”.

1.2 網(wǎng)絡(luò)建模

使用DTN網(wǎng)作為仿真網(wǎng)絡(luò)模擬實(shí)際道路網(wǎng)，選擇DTN網(wǎng)中的節(jié)點(diǎn)作為OD(Origin-destination)交通量的起點(diǎn)和終點(diǎn)，從而形成隨OD變化的仿真交通網(wǎng)絡(luò).上述的OD交通量是指起終點(diǎn)間的交通出行量.它能明確指定節(jié)點(diǎn)之間的流量、決定路線分配，對(duì)于網(wǎng)絡(luò)中交通流分布有很大的影響.

為了簡便采用以單中心的OD對(duì)作為切入點(diǎn).開始時(shí)所有OD對(duì)都以最中心的節(jié)點(diǎn)為終點(diǎn)，剩余其他節(jié)點(diǎn)都作為起點(diǎn)指向中心節(jié)點(diǎn)，然后引入概率P用以改變OD對(duì)(OD對(duì)改變的方式是起點(diǎn)不變，終點(diǎn)以概率P在除起點(diǎn)以外剩余的全部節(jié)點(diǎn)中進(jìn)行重新選擇).由此產(chǎn)生可以動(dòng)態(tài)變化的交通網(wǎng)絡(luò)模型.圖1，2顯示了研究使用網(wǎng)絡(luò)與網(wǎng)絡(luò)OD交通量的一個(gè)范例.

如圖1所示為15個(gè)節(jié)點(diǎn)連接產(chǎn)生的DTN網(wǎng)，以此模擬道路網(wǎng)，其中節(jié)點(diǎn)代表城市交通中的路口，連邊代表道路.

圖1 狄洛尼三角網(wǎng)

圖2 OD矩陣中OD對(duì)由箭頭表示圖

如圖2所示為由交通流需求OD組成的OD網(wǎng)絡(luò)，其中紅色節(jié)點(diǎn)代表中道路網(wǎng)中的路口，連邊代表出行的OD對(duì)，箭頭指示方向.

2 擁堵問題的解決方案——K-最短路徑算法

2.1 基尼系數(shù)及平均路徑長度

基尼系數(shù)是意大利經(jīng)濟(jì)學(xué)家基尼為定量測定收入分配的差異程度于1922年提出的概念，取值范圍在0～1之間.其中基尼系數(shù)越接近于0就表明收入分配越是趨向于平均，反之，表示貧富差距越大.利用基尼系數(shù)來描述交通流在網(wǎng)絡(luò)結(jié)構(gòu)中分布的差異，能有效的計(jì)量交通流的集中程度，為交通網(wǎng)傳輸?shù)慕Y(jié)果提供有效指標(biāo).

當(dāng)全網(wǎng)絡(luò)的交通流都集中在網(wǎng)絡(luò)的一條連邊上，則G的值為1；當(dāng)全部的流量均勻的分布在網(wǎng)絡(luò)的每一條連邊上，則G的值為0，故G定義[17]為

(1)

介數(shù)指網(wǎng)絡(luò)中所有根據(jù)OD對(duì)的路徑中經(jīng)過該邊路徑的數(shù)目占全部路徑總數(shù)的比例，具體定義為

(2)

平均路徑長度L指根據(jù)OD對(duì)和K-最短路徑的路由方式的路程總長度相對(duì)于整個(gè)網(wǎng)絡(luò)全部節(jié)點(diǎn)的路程長度，具體定義分別為

(3)

(4)

其中：k為路徑數(shù)目；lij為i到j(luò)的路徑長度；N為網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)；lijm為加權(quán)因子，代表i到j(luò)的第m條路徑長度.

2.2 K-最短路徑

根據(jù)傳輸網(wǎng)絡(luò)的需求，由起點(diǎn)到終點(diǎn)的路徑一般選擇“最短路徑”即成本最小的路徑.得到最短路徑，在此基礎(chǔ)上得到比最短路徑長的K-1條路徑[18]，它們之間的關(guān)系是L2

K-最短路徑得出的基本思路是通過Dijstra算法[19]找出網(wǎng)絡(luò)的最短路徑，然后根據(jù)比這條路徑長的路徑所經(jīng)過的節(jié)點(diǎn)一定有部分節(jié)點(diǎn)是在這條路徑上的思路找尋下一條路徑，逐步將K條路徑全部找出.接著通過得到的K條路徑，以1.2節(jié)假定的OD對(duì)模擬城市交通出行，通過網(wǎng)絡(luò)的平均路徑長度與交通流基尼系數(shù)研究網(wǎng)絡(luò)的交通流特性.

2.3 優(yōu)化函數(shù)

K-最短路徑的路由方式使交通流分布范圍擴(kuò)大，不會(huì)過度集中，但隨之而來的是網(wǎng)絡(luò)平均路徑長度的增長，但K-最短路徑的路由方式只擴(kuò)大流量分布范圍，并不考慮路程長短與否.為使兩者在合理范圍內(nèi)達(dá)到平衡，必須給出優(yōu)化函數(shù)均衡基尼系數(shù)G和平均路徑長度L.

G和L都會(huì)由于路徑數(shù)量K的變化而變化，但它們卻呈負(fù)相關(guān)的變化趨勢：G隨著K的增長而逐漸降低，L卻隨著K的升高而逐漸變大.考慮到這種呈相反趨勢的變化，將優(yōu)化函數(shù)設(shè)為F=G+tL(G和L在計(jì)算之前需要進(jìn)行歸一化處理)，t為基尼系數(shù)與平均路徑長度之間的權(quán)重(可以理解為平均路徑長度和基尼系數(shù)之間重要性的程度)，t可以根據(jù)具體的實(shí)際情況進(jìn)行調(diào)節(jié).

3 仿真分析

仿真選用的網(wǎng)絡(luò)為100個(gè)隨機(jī)生成的節(jié)點(diǎn)組成的DTN作為道路網(wǎng)絡(luò).仿真的步驟如下：

首先，將OD對(duì)數(shù)目定為99對(duì)，初始對(duì)于所有的OD對(duì)，將最靠近中心的節(jié)點(diǎn)作為終點(diǎn)，其他節(jié)點(diǎn)作為每個(gè)OD對(duì)的起點(diǎn).按照概率P，對(duì)所有的OD對(duì)的終點(diǎn)進(jìn)行重選，即對(duì)任意一個(gè)OD對(duì)，其終點(diǎn)有概率P變?yōu)榫W(wǎng)絡(luò)中的非中心節(jié)點(diǎn).當(dāng)概率P越大，終點(diǎn)選擇的隨機(jī)性越大，而保持起點(diǎn)不變.

然后，遍歷不同的概率P與不同的K-最短路徑的K值，得到隨P與K變化的基尼系數(shù)和平均路徑長度的變化圖.仿真結(jié)果如圖3-5所示.

圖3，4是網(wǎng)絡(luò)進(jìn)行50次迭代后達(dá)到穩(wěn)定狀態(tài)時(shí)基尼系數(shù)及平均路徑長度的變化圖，其中圓形、方形、菱形、五角星、星形、向右三角形及上三角形(○,□,◇,☆,*,?,△)分別表示1—7條路徑時(shí)的基尼系數(shù)和平均路徑長度.

圖3 目的地隨機(jī)化下的基尼系數(shù)變化圖

圖4 目的地隨機(jī)化下的平均路徑長度變化圖

在圖3中隨著概率P的逐漸增大(OD對(duì)的分布趨向均勻分布)基尼系數(shù)逐漸降低的同時(shí)，基尼系數(shù)也隨著路徑數(shù)量的逐漸增加而逐漸降低.圖4中隨著概率P的逐漸增大(OD對(duì)的分布趨向均勻分布)，平均路徑長度逐漸變大的同時(shí)，平均路徑長度也隨著路徑數(shù)量的逐漸增加而逐漸增大.因?yàn)椴捎肒-最短路徑路由算法以后，流量遍布的范圍擴(kuò)大，節(jié)點(diǎn)間流量的“貧富差距”降低，使得交通變得均勻化，另一方面流量遍布的范圍擴(kuò)大之后，經(jīng)過的節(jié)點(diǎn)數(shù)量增加，平均路徑長度隨之變大.

考慮到基尼系數(shù)與平均路徑長度變化趨勢的矛盾，定義優(yōu)化指標(biāo)F=G+tL，其中t作為調(diào)節(jié)基尼系數(shù)和平均路徑長度權(quán)重的因子，將t設(shè)定為0.5，即優(yōu)化函數(shù)為F=G+0.5L.

如圖5所示，隨著概率P的增加，優(yōu)化函數(shù)值逐漸降低，即在該函數(shù)下，交通流需求逐漸均勻化，網(wǎng)絡(luò)的運(yùn)行效果漸漸變高；同時(shí)在路徑數(shù)目K=4時(shí)，優(yōu)化函數(shù)值達(dá)到最低，即K=4時(shí)網(wǎng)絡(luò)的運(yùn)行效果最好.由此得出結(jié)論：在道路網(wǎng)結(jié)構(gòu)固定及交通流需求基本穩(wěn)定的情況下，通過調(diào)節(jié)K-最短路徑路由的K值使網(wǎng)絡(luò)的交通流特性得到優(yōu)化，達(dá)到最佳效果.

圖5 不同路徑數(shù)目下的優(yōu)化指標(biāo)變化圖

4 結(jié)束語

通過仿真實(shí)驗(yàn)，提出的K-最短路徑的路由方式，在提高交通道路網(wǎng)的利用率、優(yōu)化交通流分配、減少道路擁堵方面有一定促進(jìn)作用，能為交通建設(shè)和管理工作提供一些思路和借鑒.雖然如此，也存在著一些不足，仿真中假定時(shí)間無限，參數(shù)來自日常經(jīng)驗(yàn)及其他實(shí)驗(yàn)的數(shù)據(jù)，無法準(zhǔn)確得出該路由方式對(duì)利用率的提高程度.進(jìn)一步的研究將引入時(shí)間及道路網(wǎng)擁堵的情況，得到更加貼合實(shí)際交通的結(jié)果.

參考文獻(xiàn)：

[1] BRADDE S, CACCIOLI F, DALL’ASTA L, et al. Critical fluctuations in spatial complex networks[J]． Physical Review Letters,2010，104:218701.

[2] 王波,王萬良,楊旭華．WS與NW兩種小世界網(wǎng)絡(luò)模型的建模及仿真研究[J]．浙江工業(yè)大學(xué)學(xué)報(bào),2009,37(2):179-189．

[3] 張美玉,簡琤峰,侯向輝．Dijkstra算法在多約束農(nóng)產(chǎn)品配送最優(yōu)路徑中的研究應(yīng)用[J]．浙江工業(yè)大學(xué)學(xué)報(bào),2012,40(3):321-330．

[4] RADICCHI F, RAMASCO J J, FORTUNATO S． Information filtering in complex weighted networks[J]． Physical Review E,2011，83：046101.

[5] MIRITELLO G, MORO E, LARA R． Dynamical strength of social ties in information spreading[J]． Physical Review E,2011,83:045102．

[6] WEST J, MACE M． Browsing as the killer app: explaining the rapid success of Apple’s iPhone[J]． Telecommunications Policy,2010,34:270-286．

[7] 蔡春梅．復(fù)雜網(wǎng)絡(luò)與城市交通網(wǎng)絡(luò)復(fù)雜性研究[J]．軟件導(dǎo)刊,2013,12(4):14-15．

[8] 顧前,楊旭華,王萬良,等．基于復(fù)雜網(wǎng)絡(luò)的城市公共交通網(wǎng)絡(luò)研究[J]．計(jì)算機(jī)工程,2008,34(20):266-269．

[9] MOKDAD B, AMMAR A, NORMANDIN M, et al． A fully deterministic micro-macro simulation of complex flows involving reversible network fluid models[J]． Mathematics and computers in simulation,2010, 80:1936-1961．

[10] NICOLAIDES C, CUETO-FELGUEROSO L, JUANES R． Anomalous physical transport in complex networks[J]． Physical Review E,2010,82:055101．

[11] CUQUET M, CALSAMIGLIA J． Limited-path-length entanglement percolation in quantum complex networks[J]． Physical Review A,2011,83:032319．

[12] 陳曉瞇,孟志青,徐杰．基于混合禁忌搜索算法的動(dòng)態(tài)車輛路徑研究[J]．浙江工業(yè)大學(xué)學(xué)報(bào),2009,37(5):580-581．

[13] ZHENG Jian-feng, GAO Zi-you, ZHAO Xiao-mei, et al． Self-organized diffusion of congestion in complex networks[J]．Physica A-Statistical Mechanics and Its Application,2010,389:342-348．

[14] 李樹彬,吳建軍,高自友,等．基于復(fù)雜網(wǎng)絡(luò)的交通擁堵與傳播動(dòng)力學(xué)分析[J]．物理學(xué)報(bào),2011,60(5):146-154．

[15] FREDERICKSON G N． An optimal algorithm for selection in a min-heap[J]． Information and Computation,1993,104:197-214.

[16] GOLDBERG A V． Scaling algorithms for the shortest paths problem[J]． Siam Journal on Computing,1995,24:494-504.

[17] MORRIS R G, BARTHELEMY M． Transport on coupled spatial networks[J]． Physical Review Letters,2012,109:128703.

[18] RUPPERT E． Finding the k shortest paths in parallel[J]． Algorithmica,2000,28:242-254．

[19] 樂陽,龔健雅．Dijkstra最短路徑算法的一種高效率實(shí)現(xiàn)[J]．武漢測繪科技大學(xué)學(xué)報(bào),1999,24(3):209-212.