面向城市交通網(wǎng)絡(luò)的K最短路徑集合算法

段宗濤，WANG Wei-xing，康 軍，李 瑩，鄭西彬，程 豪，劉 研

（1、長安大學(xué)信息工程學(xué)院，西安710064；2、陜西省道路交通智能檢測與裝備工程技術(shù)研究中心，西安710064；3、Royal Institute of Technology,Stockholm,Sweden）

面向城市交通網(wǎng)絡(luò)的K最短路徑集合算法

段宗濤*1,2，WANG Wei-xing3，康 軍1,2，李 瑩1，鄭西彬1，程 豪1，劉 研1

（1、長安大學(xué)信息工程學(xué)院，西安710064；2、陜西省道路交通智能檢測與裝備工程技術(shù)研究中心，西安710064；3、Royal Institute of Technology,Stockholm,Sweden）

在城市交通網(wǎng)絡(luò)中，為了優(yōu)化交通流，需要搜索到符合出行需求K最短路徑，并將OD（Origin-Destination）交通流合理分配到這些路徑上.本文主要對搜索符合出行需求的K最短路徑搜索算法進(jìn)行了研究，解決了已有算法僅能搜索出單條滿足最短及K最短條件路徑的問題.根據(jù)Wardrop第二原則及路段阻抗函數(shù)理論，分析了路徑集合搜索方法對優(yōu)化城市交通流的必要性，并定義了城市交通網(wǎng)絡(luò)中K最短路徑集合的概念及選擇條件，提出了一種面向城市交通網(wǎng)絡(luò)的具有多項式時間復(fù)雜度的K最短路徑集合搜索算法.仿真結(jié)果表明，本文所提算法可以搜索出滿足出行需求的所有K最短路徑集合，在該路徑集合上進(jìn)行交通流分配的效果明顯優(yōu)于傳統(tǒng)方法.

城市交通；路徑搜索算法；K最短路徑集合；城市路網(wǎng)；交通流優(yōu)化

1 引 言

最短路徑問題是圖論中的重要問題，在智能交通、物聯(lián)網(wǎng)、機(jī)器人等領(lǐng)域均有著廣泛的應(yīng)用.最短路徑問題主要包括狹義最短路徑問題和廣義最短路徑問題.狹義最短路徑問題是對于確定節(jié)點(diǎn)對，在目標(biāo)網(wǎng)絡(luò)中搜索出一條代價最小的路徑.常用算法包括Dijkstra算法、Floyd算法、Auction算法和A*算法，目前此類問題依然吸引著很多研究者的關(guān)注，如Zhang[1]提出了一種基于Amoeba算法的最短路徑算法用于通信網(wǎng)絡(luò)優(yōu)化，Li[2]提出了基于中國象棋規(guī)則的最短路徑搜索算法.廣義最短路徑問題即K最短路徑搜索問題旨在尋找確定節(jié)點(diǎn)對間的多個備選的優(yōu)化路徑，形成最短路徑組，以最大程度滿足用戶對不同出行路徑選擇的需求.K最短路徑問題是狹義最短路徑問題的推廣，具有重要的研究意義和廣闊的應(yīng)用前景[3].針對K最短路徑問題的解決方法通常包括兩類：一類是一般K最短路徑算法，如Azevedo[4]提出的Deletion算法和Martins[5]提出的MS算法等；另一類是限定無環(huán)的K最短路徑算法，其中主要包括兩類算法：一類是偏離路徑算法，如Yen[6]提出的Yen算法和Martins[7]提出的MTS算法；另一類是改進(jìn)的Dijkstra算法，如MAO[8]基于Dijkstra算法與MPS算法提出了一種改進(jìn)的K最短路徑搜索算法，并應(yīng)用于通信網(wǎng)絡(luò)中搜索K最大可靠路徑、K最大容量路徑和K最大期望容量路徑；WANG[9]在Dijkstra算法的基礎(chǔ)上提出了一種限定搜索范圍的K最短路徑算法，有效解決了電力網(wǎng)絡(luò)中輸電斷面的搜索問題.

在城市交通網(wǎng)絡(luò)中常常包含多條K最短路徑，根據(jù)Wardrop第二原則[10]，將給定OD對的交通流分配在多條K最短路徑上，更有利于優(yōu)化城市交通流分配，這就要求能夠高效地搜索到給定OD對之間的所有K最短路徑.因此，本文提出了一種面向城市交通網(wǎng)絡(luò)的K最短路徑集合搜索算法.分析了路徑集合搜索方法對于城市交通流優(yōu)化分配問題的必要性；定義了城市交通網(wǎng)絡(luò)中K最短路徑集合的選擇條件；設(shè)計并實(shí)現(xiàn)了一種面向城市交通網(wǎng)絡(luò)的K最短路徑集合搜索算法，并分析了該算法的時間復(fù)雜度.最后，通過仿真實(shí)例驗證了算法的有效性.

2 問題描述

城市交通網(wǎng)絡(luò)流理論中的Wardrop第二原則認(rèn)為所有出行者都遵循“網(wǎng)絡(luò)總旅行時間最小化”的目標(biāo)來選擇路徑，滿足Wardrop第二原則的交通網(wǎng)絡(luò)流狀態(tài)稱為系統(tǒng)最優(yōu)狀態(tài)（System Optimal，SO），在SO狀態(tài)下，交通網(wǎng)絡(luò)資源得到最佳利用，交通網(wǎng)絡(luò)效益得到最大限度發(fā)揮.Wardrop第二原則定義的交通網(wǎng)絡(luò)總代價函數(shù)z(x)如式(1)所示，即z(x)越小系統(tǒng)越優(yōu).

式中 xi為所選用路徑中路段i的路段流量；ti(xi)為路段i的路段旅行時間函數(shù)，即路段阻抗函數(shù)，該函數(shù)滿足擁擠效應(yīng)即是關(guān)于xi的嚴(yán)格增函數(shù).目前廣泛采用美國聯(lián)邦公路局提出的BPR函數(shù)作為的路段阻抗函數(shù)[11]，如式(2)所示.

式中 C為路段設(shè)計通行能力，在后續(xù)分析中假設(shè)參數(shù)C為常量；α，β為待標(biāo)定參數(shù)，美國聯(lián)邦公路局標(biāo)定α=0.15、β=4.顯然式(2)是嚴(yán)格增函數(shù).t0為路段自由流出行時間，可表示為

式中 Li為路段長度；V為路段限行最高速度，在后續(xù)分析中假設(shè)參數(shù)V為常量.

定義函數(shù) f(xi)如下式：

則 f(xi)為xi的嚴(yán)格增函數(shù)，由式(2)至式(4)可得

假設(shè)某個OD對上需要分配的交通流量為X，同時該OD對之間存在n條最短路徑 p1,...,pn和m條K級最短路徑,...,.設(shè)K級最短路徑的選擇標(biāo)準(zhǔn)是該OD對之間的總長度是最短路徑總長度d倍的所有路徑.

在不考慮其它OD對交通流量影響的情況下，如果僅搜索到1條最短路徑 p1，則 p1包含路段承載的交通流量均為X，由式(1)和式(5)，可得此時交通網(wǎng)絡(luò)總代價z1(x)可表示為

如果能夠搜索到所有的n條最短路徑和m條K級最短路徑，使交通流量X由路徑 p1,...,pn和,...均勻承載，則由式(1)和式(4)，可得此時交通網(wǎng)絡(luò)總代價z2(x)可表示為

綜上所述，當(dāng)對給定OD對進(jìn)行交通流分配時，若能把該OD對之間存在的所有K最短路徑全部搜索出來，并將交通流均勻分配在上述路徑上，則會有效降低交通網(wǎng)絡(luò)總代價，提高交通網(wǎng)絡(luò)資源利用率和交通網(wǎng)絡(luò)效益.因此，為了優(yōu)化交通流分配，客觀要求能夠搜索到給定OD對之間的所有K最短路徑.上述分析說明，本文提出的面向城市交通網(wǎng)絡(luò)的K最短路徑集合搜索算法對于交通規(guī)劃領(lǐng)域具有一定的研究價值和現(xiàn)實(shí)意義.

3 算法描述

3.1 城市交通網(wǎng)絡(luò)G(N,E)的表示方式及存儲結(jié)構(gòu)

城市交通網(wǎng)絡(luò)G(N,E)的拓?fù)浣Y(jié)構(gòu)采用|N|×|N|階加權(quán)鄰接矩陣M表示，其矩陣元素定義如式(9)所示：

在算法執(zhí)行前，需要將矩陣M加載到內(nèi)存中，矩陣M的存儲結(jié)構(gòu)采用鄰接表的方式表示，如圖1所示.其中鄰接表頂點(diǎn)結(jié)構(gòu)包括兩個域，即頂點(diǎn)域用于存放頂點(diǎn)ni的信息，指針域用于指向ni的鄰接表的頭指針；鄰接表表節(jié)點(diǎn)結(jié)構(gòu)包括三個域，即鄰接點(diǎn)域用于存放與頂點(diǎn)ni相鄰接的頂點(diǎn)nj的序號j，邊長域用于存放邊(ni,nj)的長度，鏈域用于將鄰接表的所有表結(jié)點(diǎn)鏈在一起.

圖1 G(N,E)的存儲結(jié)構(gòu)Fig.1 The storage structure of G(N,E)

3.2 面向城市交通網(wǎng)絡(luò)的限定無環(huán)的K最短路徑集合搜索算法

下面為了詳細(xì)描述算法內(nèi)容，首先給出K最短路徑集合的選擇標(biāo)準(zhǔn).根據(jù)城市道路交通運(yùn)行評價指標(biāo)體系[12]，可將城市路網(wǎng)中源節(jié)點(diǎn)O到目標(biāo)節(jié)點(diǎn)D的K最短路徑集合劃分為4個等級，設(shè)該OD對之間的最短路徑總長度為L，則0級最短路徑集合為OD對之間總長度等于L的所有路徑；1級最短路徑集合為OD對之間總長度在(L,1.2L]范圍內(nèi)的所有路徑；2級最短路徑集合為OD對之間總長度在(1.2L,1.5L]范圍內(nèi)的所有路徑；3級最短路徑集合為OD對之間總長度在(1.5L,1.8L]范圍內(nèi)的所有路徑；4級最短路徑集合OD對之間總長度在(1.8L,2.1L]范圍內(nèi)的OD對之間所有路徑.

（1）算法.

對于交通網(wǎng)絡(luò)G(N,E)，對應(yīng)的加權(quán)鄰接矩陣為M，已知需要搜索源節(jié)點(diǎn)O到目標(biāo)節(jié)點(diǎn)D之間的K最短路徑集合，則算法執(zhí)行流程如圖2所示.

在算法中需要找到的路徑信息，其輸出格式為集合標(biāo)號+{路徑所包含節(jié)點(diǎn)序列}，集合標(biāo)號格式設(shè)定為OD:K:Length，其中，OD表示源目節(jié)點(diǎn)編號，Length表示當(dāng)前路徑長度，K代表路徑類型，從最短路徑到4級最短路徑，K分別取值0,1,2,3,4.

（2）算法時間復(fù)雜度分析.

由于算法中分別執(zhí)行了1次Dijkstra算法和1次深度優(yōu)先遍歷算法，Dijkstra算法的時間復(fù)雜度為O(n2)，深度優(yōu)先遍歷算法的時間復(fù)雜度為O(n+ e)，因此算法的時間復(fù)雜度為O(n2+n+e).

圖2 算法流程圖Fig.2 The Algorithm flow chart

4 仿真實(shí)例

仿真硬件環(huán)境為主頻2.83GHZ、4核CPU，4G內(nèi)存，500G硬盤.以西安雁塔區(qū)路網(wǎng)為例，路網(wǎng)G (70,94)共包括70個節(jié)點(diǎn)，94條邊.G(70,94)的網(wǎng)絡(luò)拓?fù)淙鐖D3所示.路網(wǎng)中各個路段的長度如表1所示,其中路段長度以km為單位.仿真實(shí)例中源節(jié)點(diǎn)為1，目標(biāo)節(jié)點(diǎn)為50，需要搜索節(jié)點(diǎn)1到節(jié)點(diǎn)50之間的最短路徑集合和各級最短路徑集合.

算法的搜索計算結(jié)果如表2所示.在OD對（1,50）之間搜索到1條最短路徑，45條1級最短路徑，1 432條2級最短路徑，8 878條3級最短路徑，30 558條4級最短路徑，算法執(zhí)行總耗時2.882 s.其中，搜索到的45條1級最短路徑長度如圖4所示，平均長度15.15 km，最大長度15.7 km，最小長度13.6 km.

圖3 仿真實(shí)例中的路網(wǎng)拓?fù)鋱DFig.3 Topology of traffic network in simulation examples

表1 仿真路網(wǎng)中的路段長度Table1 The length of sections in simulation examples

2 仿真結(jié)果Table2 Results of simulation

圖4 1級最短路徑長度Fig.4 Length of the 1st shortest path

假設(shè)OD對（1,50）之間需要分配的交通流為110 veh/h，路段設(shè)計通行能力C為100 veh/h，路段限行最高速度V為70 km/h.如果上述交通流量被分配在1條最短路徑上，則在不考慮其他交通流量影響的條件下，由式(6)可得交通網(wǎng)絡(luò)總代價Z1為26.99；如果將上述交通流量均勻分配到1條0級最短路徑和45條1級最短路徑上，其中最短路徑長度為13.1 km，45條1級最短路徑長度如圖4所示，在不考慮其他交通流量影響的條件下，由式(8)可得交通網(wǎng)絡(luò)總代價Z2為23.74，顯然Z2

（3）本文所提算法仍然存在一些不足：算法的時間復(fù)雜度為O(n2+n+e)，在對大規(guī)模路網(wǎng)進(jìn)行搜索時算法執(zhí)行時間仍至少達(dá)到秒級，無法為具有強(qiáng)實(shí)時性交通應(yīng)用提供支持；實(shí)際應(yīng)用中，關(guān)于具體需要搜索到第幾級最短路徑的問題，目前還沒有一般性結(jié)論.

（4）下一步研究工作中，需要重點(diǎn)解決以下幾個問題：設(shè)計和實(shí)現(xiàn)K最短路徑并行搜索算法，進(jìn)一步提高算法的實(shí)時性；收集并整理實(shí)際城市交通流數(shù)據(jù)，通過大數(shù)據(jù)分析技術(shù)，結(jié)合具體城市交通應(yīng)用，對需要搜索到第幾級最短路徑的問題展開研究.

5 研究結(jié)論

（1）基于Wardrop第二原則中的交通網(wǎng)絡(luò)代價函數(shù)，討論了搜索所有K最短路徑對于優(yōu)化交通流分配的現(xiàn)實(shí)意義.

（2）結(jié)合《城市道路交通運(yùn)行評價指標(biāo)體系》，提出了城市路網(wǎng)中各級最短路徑的選擇標(biāo)準(zhǔn).實(shí)現(xiàn)了一種面向城市路網(wǎng)的K最短路徑算法.該算法在滿足多項式時間復(fù)雜度的條件下，可以有效搜索出滿足各級最短條件的所有路徑集合.最后，以西安市雁塔區(qū)路網(wǎng)為例進(jìn)行了仿真測試，測試結(jié)果驗證了所提算法的有效性.

[1]Zhang Xiaoge,Cui Chuan,Dong Ping,et al.Solving allpairs shortest path problem based on amoeba algorithm [J].ICIC Express Letters,2013,7(8):2455-2460.

[2]Li Bi-Yi,Chen Chun-Hua,Su Kuo-Lan,et al.Develop?ment of the searching algorithm based Chinese chess game[J].ICIC Express Letters,2012,6(5):245-253.

[3]徐濤,丁曉璐,李建伏.K最短路徑算法綜述[J].計算機(jī)工程與設(shè)計,2013,34(11):3900-3907.[XU T,DING X L,LI J F.Review on K shortest paths algorithms[J].Com?puter Engineering and Design,2013,34(11):3900-3907.] [4]J A Azevedo,J J E R S Madeira,E Q V.Martins，et al. A shortest paths ranking algorithm[C]//Proceedings of the Annual Conference AIRO'90,Models and Methods for Decision Support,Operational Research Society of It?aly,1990:1001-1011.

[5]E Q V Martins,J L E Santos.A new shortest paths rank?ing algorithm[J].Investigacao Operacional,2000,20(1): 47-62.

[6]J Y Yen.Finding the K shortest loopless paths in a net?work[J].Management Science,1971,17:712-716.

[7]E Q V Martins,Marta M B Pascoal.A new implementa?tion of Yen’s ranking loopless paths algorithm[J].Quar?terly Journal of the Belgian,French and Italian Opera?tions Research Societies,2003,1(2):121-133.

[8]毛少武,張煥國,黃崇超,等.改進(jìn)的K最短路徑算法在通信網(wǎng)絡(luò)中的應(yīng)用[J].武漢大學(xué)學(xué)報(理學(xué)版),2013,59 (6):534-538.[MAO S W,ZHANG H G,HUANG C C,et. al.A new fault-tolerance mechanism in communica?tions based on K shortest path algorithm[J].Journal of Wuhan University(Natural Science Edition),2013,59 (6):534-538.]

[9]王增平,李剛,任建文.基于前K最短路徑的輸電斷面搜索新算法[J].電工技術(shù)學(xué)報,,2012,27(4):193-201. [Wang Z P,LI G,REN J W.A new search algorithm for transmission section based on K shortest paths[J].Trans?actions of China Electrotechnical Society,2012,27(4): 193-201.]

[10]程琳.城市交通網(wǎng)絡(luò)流理論[M].南京：東南大學(xué)出版社，2010.[CHENG L.Urban transportation network flow theory[M].Nanjing：Southeast University Press,2010.]

[11]劉寧,趙勝川,何南.基于BPR函數(shù)的路阻函數(shù)研究[J].武漢理工大學(xué)學(xué)報(交通科學(xué)與工程版),2013,37 (3):545-548.[LIU N,ZHAO S C,HE N.Further study of Impedance Function Based on BPR Function[J].Jour?nal of Wuhan University of Technology(Transportation Science&Engineering),2013,37(3):545-548.]

[12]DB11/T 785-2011.城市道路交通運(yùn)行評價指標(biāo)體系[S].北京市地方標(biāo)準(zhǔn),中國,2011.[DB11/T 785-2011. Urban road traffic performance index[S].Bei Jing Munic?ipal Local Standard,China,2011.]

A K-th Shortest Path Set Algorithm for Urban Traffic Network

DUAN Zong-tao1,2，WANG Wei-xing3，KANG Jun1，LI Ying1，ZHENG Xi-bin1，CHENG Hao1，LIU Yan1
(1.School of Information Engineering,Chang’an University,Xi’an 710064,Shaanxi,China;2.Shaanxi Road and Traffic Detection Engineering and Technical Research Center,Xi’an 710064,Shaanxi,China;3.Royal Institute of Technology, Stockholm,Sweden)

urban traffic;path searching algorithm;K-th shortest path set;urban traffic network;traffic flow Optimization

1009-6744（2014）03-0194-07

U495

A

2014-01-21

2014-03-08錄用日期：2014-03-12

國家自然科學(xué)基金（51278058，61303041）；中央高校科研資金項目（2013G2241020，2013G1241119）；交通運(yùn)輸部應(yīng)用基礎(chǔ)研究項目（2014319812150）；陜西省科技攻關(guān)項目（2014K05-28）.

段宗濤（1977－），男，陜西鳳翔人，副教授，工學(xué)博士.*通訊作者：ztduan@chd.edu.cn

Absttract:In urban traffic network，it is important to optimize traffic flow of the K-th shortest path that meets the travel demand and then allocate the OD traffic flow onto the paths.This paper investigates the algorithm of searching K-th shortest path that meets the travel demand.The method overcomes the weakness of the traditional algorithm that can only get single K-th shortest path.According to the second principle of Wardrop and the road impedance function theory,the paper analyzes the necessity of the path set searching method for optimizing traffic flow,and proposes the definition and criterions of the K-th shortest path set in urban traffic network.Then,it presents an algorithm with the polynomial time complexity for searching K-th shortest path set in urban traffic network.The simulation results show that all of the K-th shortest path which meet the travel demand can be obtained effectively,and the feasibility of traffic allocation on above path set is proved with comparison of traditional algorithms.