基于改進(jìn)K次短路徑算法的有效路徑搜索算法及實(shí)現(xiàn)

鄭貴省,王　元，王　鵬，李月明，車亞輝

(1.軍事交通學(xué)院 基礎(chǔ)部，天津300161； 2.軍事交通學(xué)院 研究生管理大隊(duì)，天津300161)

?

基于改進(jìn)K次短路徑算法的有效路徑搜索算法及實(shí)現(xiàn)

鄭貴省1,王元2，王鵬2，李月明2，車亞輝2

(1.軍事交通學(xué)院 基礎(chǔ)部，天津300161； 2.軍事交通學(xué)院 研究生管理大隊(duì)，天津300161)

為提高有效路徑搜索效率，結(jié)合ArcGIS具有的路徑分析功能，以K次短路徑算法為基礎(chǔ)，依據(jù)重疊懲罰算法的原理，提出基于改進(jìn)K次短路徑算法的有效路徑搜索算法。以ArcGIS為平臺(tái)，給出了算法的實(shí)現(xiàn)方法。經(jīng)過對實(shí)際路網(wǎng)的可視化測試，驗(yàn)證了改進(jìn)算法具有較高的運(yùn)行效率，為有效路徑相關(guān)理論在ArcGIS平臺(tái)的應(yīng)用提供了一種技術(shù)手段和方法。

有效路徑；K次短路徑算法；GIS

路網(wǎng)中有效路徑的計(jì)算方法是交通規(guī)劃中交通流分配的關(guān)鍵技術(shù)。現(xiàn)有的有效路徑計(jì)算方法很多，主要有啟發(fā)式的定向搜索算法[1]、分層定向搜索算法[2]、基于層次空間推理的搜索算法[3]，以及文獻(xiàn)[4-5]提出的K次短路徑算法、遍歷算法等。雖然相關(guān)理論研究很多，但對算法效率和實(shí)現(xiàn)方面的研究較少。

地理信息系統(tǒng)(geographic information system，GIS)集數(shù)據(jù)管理、可視化和空間分析于一體，在諸多領(lǐng)域(尤其是交通領(lǐng)域)得到了廣泛應(yīng)用。路網(wǎng)具有很強(qiáng)的地理分布特性，基于GIS技術(shù)的優(yōu)勢，實(shí)現(xiàn)大規(guī)模實(shí)際路網(wǎng)中有效路徑的快速搜索，是有效路徑理論得以實(shí)際應(yīng)用的必然趨勢。現(xiàn)有GIS平臺(tái)中的空間網(wǎng)絡(luò)分析功能不斷強(qiáng)化，已經(jīng)可以實(shí)現(xiàn)實(shí)際路網(wǎng)中的最近設(shè)施點(diǎn)分析、服務(wù)區(qū)分析、選址等問題，如何結(jié)合其強(qiáng)大的空間分析功能和數(shù)據(jù)處理能力來實(shí)現(xiàn)其有效路徑的搜索功能，將是需要研究的問題。

1　有效路徑的定義

有效路徑的定義方法很多，比較有代表性的有區(qū)間阻抗下的有效路徑[6]、基于影響度的有效路徑[7]和根據(jù)路徑選擇的因素提出的改進(jìn)Dail有效路徑[8]。常用的有效路徑[9]定義方法如下：

若OD對(r,s)之間的路徑k為有效路徑，則需滿足：

(1)k為簡單無環(huán)路徑；

Hrs與實(shí)際路網(wǎng)情況和交通需求量有關(guān)，要進(jìn)行深入分析才能確定。有關(guān)學(xué)者根據(jù)實(shí)際交通流數(shù)據(jù)對不同地區(qū)內(nèi)有效路徑的伸展系數(shù)進(jìn)行了研究。文獻(xiàn)[10]根據(jù)實(shí)際調(diào)查數(shù)據(jù)確定山東省高速公路網(wǎng)的伸展系數(shù)為0.3。現(xiàn)有研究也表明，路徑選擇行為會(huì)受到行駛距離的影響，因此有效路徑伸展系數(shù)并非單一的絕對值。文獻(xiàn)[11]考慮行駛里程的影響，采用“絕對差”與“相對差”結(jié)合的方式來確定河南省高速公路有效路徑阻抗(行駛里程)的取值范圍(見表1)，其中L為最短路徑里程。本文的有效路徑取值范圍也根據(jù)表1確定。

表1　有效路徑的劃分標(biāo)準(zhǔn)

2　基于改進(jìn)K次短路徑的有效路徑搜索算法

針對現(xiàn)有的有效路徑搜索算法，結(jié)合GIS具有的路徑分析功能，從可實(shí)現(xiàn)的角度出發(fā)，主要考慮K次短路徑算法來實(shí)現(xiàn)有效路徑的搜索。K次短路徑算法是按最短路、次短路、再下一條次短路的順序產(chǎn)生K條路徑集合的算法，具體算法有很多，它可以識(shí)別所有的有效路徑。但是，K次短路徑算法的時(shí)間復(fù)雜度很高。現(xiàn)有研究表明，與最短路徑行駛時(shí)間差在20%的路徑有幾千條，會(huì)導(dǎo)致算法的執(zhí)行時(shí)間過長。此外，識(shí)別出的有效路徑之間相似程度很高，對實(shí)際情況而言也沒有必要。因此，需要對K次短路徑算法進(jìn)一步改進(jìn)。

重疊懲罰算法是一種用于計(jì)算合理多路徑的算法，其基本原理是在每一次循環(huán)中，通過重疊懲罰函數(shù)來改變已經(jīng)辨識(shí)出的路徑中的路段阻抗，再采用最短路徑算法來計(jì)算下一條有效路徑。重疊懲罰算法原理簡單，得到的路徑差異較大，一般僅用來給出幾條合理路徑作參考。可以考慮結(jié)合重疊懲罰算法的原理來改進(jìn)K次短路徑算法，從而建立新的有效路徑搜索算法。基本思想是在保證搜索效果的前提下，在K次短路徑的循環(huán)中，按照重疊懲罰算法的基本原理來改變當(dāng)前路徑中的路段權(quán)重，從而達(dá)到降低計(jì)算出的有效路徑之間的相似程度、提高搜索效率的目的。

定義原始法表示的實(shí)際路網(wǎng)為G=(V,E,W)；n為節(jié)點(diǎn)個(gè)數(shù)，n=|V|；m為邊個(gè)數(shù)，m=|E|。其中：V={v1,v2,…，vn}為節(jié)點(diǎn)集；vs為起點(diǎn)；vt為終點(diǎn)；E為邊集；W={wij|(vi,vj)∈E}為邊的權(quán)集，在此表示各路段的里程。所有有效路徑可表示為{P|L(p)≤L′，p∈R}，R為從vs到vt的所有路徑，L(p)為路徑p的行駛里程。

2.1基于K次短路徑算法的有效路徑搜索算法

K次短路徑(K shortest paths，KSP)問題，本文具體為限定無環(huán)問題，通過有效路徑的條件依次篩選出所有的有效路徑，即可得到有效路徑集。現(xiàn)有的K次最短路徑算法主要有基于Dijkstra算法而產(chǎn)生的改進(jìn)算法和基于Yen算法的改進(jìn)算法[12]。在實(shí)際應(yīng)用中，最廣泛研究和采用的算法為Yen算法及其各種改進(jìn)算法。Yen算法又稱為偏離路徑算法，是由Yen于1971年提出，其基本思想是從最短路徑開始，循環(huán)利用當(dāng)前求得最短路徑來產(chǎn)生下一條次短路徑，相關(guān)的改進(jìn)算法主要改進(jìn)了偏離路徑的計(jì)算和獲取，有MPS算法、DFS算法等。文獻(xiàn)[13]對以上幾種算法的效率進(jìn)行了實(shí)驗(yàn)比較，發(fā)現(xiàn)MPS算法和DFS算法具有較高的時(shí)間效率，DFS算法雖然與MPS算法相比具有更高存儲(chǔ)效率，但在應(yīng)用中需提前知道K值，不滿足應(yīng)用條件。MPS算法和Yen算法的區(qū)別在于MPS算法采用偏離邊的縮小長度來替代候選路徑的長度。雖然MPS算法具有一定的時(shí)間優(yōu)勢，但GIS已提供最短路徑的分析功能，且可以直接獲得路徑長度，因此，在GIS平臺(tái)上，采用Yen算法來實(shí)現(xiàn)K次短路經(jīng)算法更為方便。基于Yen算法的有效路徑搜索算法的步驟如下。

(1)基于最短路徑算法——Dijkstra算法，得到第一條最短路徑p1，放入數(shù)組A中，并根據(jù)第一條最短路徑的行程里程L(p1)，確定有效路徑里程最大值為L′。

(2)根據(jù)p1生成p2的候選路徑集Q(初始為空)，其計(jì)算過程為

(a)從G中刪除一條邊(vi,vj)∈p1;

(b)計(jì)算從vi到vt的最短路徑為r，且r不通過p1從vi到vt之間的任何節(jié)點(diǎn)，由p1上從vs到vi的路徑和r組成一條候選路徑p，將路徑p加入數(shù)組Q中，節(jié)點(diǎn)vi為p的偏離節(jié)點(diǎn)dev(p)；

(c)恢復(fù)邊(vi,vj)，返回(a)，刪除p1中的另一條邊，直到計(jì)算完p1中所有的邊。

(3)令i=2。

(4)令Q中最短的路徑為pi，如果L(pi)>L′，則算法結(jié)束，A即為有效路徑的集合；否則，從Q中移除pi，放入A中，并按照生成候選路徑的方法由pi產(chǎn)生新的候選路徑集放入Q中。在生成候選路徑集的過程中，除了依次刪除pi上的邊之外，還要?jiǎng)h除之前的pj(j

(5)i=i+1，返回(4)。

2.2基于改進(jìn)K次短路徑算法的有效路徑搜索算法

主要通過改進(jìn)Yen算法中的(2)和(4)來建立新的有效路徑搜索算法，改進(jìn)后的算法步驟如下。

(1)基于最短路徑算法——Dijkstra算法，得到第一條最短路徑p1，放入數(shù)組A中，并根據(jù)第一條最短路徑的行程里程L(p1)，確定有效路徑里程最大值為L′。

(a)從G中刪除一條邊(vi,vj)∈p1；

(b)計(jì)算從vi到vt的最短路徑為r，且r不通過p1上從vs到vi之間的任何節(jié)點(diǎn)，由p1上從vs到vi的路徑和r組成一條候選路徑p，將路徑p加入數(shù)組Q中，節(jié)點(diǎn)vi為p的偏離節(jié)點(diǎn)dev(p)；

(c)恢復(fù)邊(vi,vj)，返回(a)，刪除p1中的另一條邊，直到計(jì)算完p1中所有的邊。

(3)令i=2。

(5)i=i+1，返回(4)。

算法的流程如圖1所示。

圖1　算法流程

3　算法的實(shí)現(xiàn)及實(shí)例測試

如圖2所示為某地區(qū)的密度較大的公路網(wǎng)局部，包含366條邊和236個(gè)節(jié)點(diǎn)，假設(shè)路網(wǎng)中有兩個(gè)節(jié)點(diǎn)為交通流的起訖點(diǎn)(圖中標(biāo)志出的兩個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)1為起點(diǎn)，節(jié)點(diǎn)2為終點(diǎn))，分別采用以上兩種搜索算法，通過Python語言編程來搜索有效路徑，搜索結(jié)果在GIS平臺(tái)上可視化表示。由于K次短路徑算法的時(shí)間復(fù)雜度過高，為測試比較兩種算法的效率，假設(shè)有效路徑里程的取值范圍為(L，1.1L)，其中，L為起訖點(diǎn)之間的最短路徑里程。

圖2　測試路網(wǎng)(局部)

以ArcGIS10.2軟件中的ArcMap10.2為GIS平臺(tái)，采用ArcGIS的腳本語言Python作為編程語言，程序編寫平臺(tái)為PythonWin。ArcGIS專門為Python提供了站點(diǎn)包Arcpy，可與ArcGIS中的地理數(shù)據(jù)庫進(jìn)行直接交互，也可直接調(diào)用ArcGIS中已有的各種分析功能。同時(shí)， Python的復(fù)雜網(wǎng)絡(luò)分析庫networkx也提供了很多網(wǎng)絡(luò)分析方面的算法庫。

3.1基于K次短路徑算法的測試結(jié)果

采用K次短路徑算法來搜索有效路徑，結(jié)果如圖3所示。程序執(zhí)行時(shí)間為7 842.30 s，搜索出的有效路徑共10 654條。

圖3　基于K次短路徑搜索算法的有效路徑搜索結(jié)果

3.2基于改進(jìn)K次短路徑算法的測試結(jié)果

算法中首先要確定懲罰系數(shù)α的取值，其取值范圍一般為(0，1)之間。α取值過大會(huì)導(dǎo)致遺漏的有效路徑過多，搜索結(jié)果不合理；α取值過小，則導(dǎo)致路徑相似程度過高，程序執(zhí)行時(shí)間過長。需要通過一定的實(shí)驗(yàn)來確定α的合理取值。

從出行的習(xí)慣上看，當(dāng)人們沿路線前進(jìn)時(shí)，總是希望能比當(dāng)前位置更加接近出行的目的地，所以，終點(diǎn)比起點(diǎn)更靠近出行終點(diǎn)的路段一般屬于有效路徑。基于此，從搜索結(jié)果看，α的合理取值一般能達(dá)到保留所有終點(diǎn)比起點(diǎn)更靠近出行終點(diǎn)的路段即可。分別取α為(0.20，0.15，0.10，0.05，0.01)，經(jīng)過實(shí)驗(yàn)測試，相關(guān)測試數(shù)據(jù)見表2，有效路徑搜索結(jié)果可視化表示如圖4—8所示。

表2　不同α取值下算法的測試數(shù)據(jù)

圖4　α=0.20的搜索結(jié)果

圖5　α=0.15的搜索結(jié)果

由以上測試結(jié)果可知，基于改進(jìn)K次短路徑算法的有效路徑搜索算法，在效率上具有明顯優(yōu)勢，且可排除由K次短路徑算法產(chǎn)生的許多不必要路徑。對比圖4—8可知，α取值分別為0.05和0.01時(shí)，基本滿足包括所有終點(diǎn)比起點(diǎn)更靠近出行終點(diǎn)的路段的要求。同時(shí)，對比α取0.05和0.01時(shí)的測試數(shù)據(jù)，初步確定在實(shí)際路網(wǎng)中α取值為0.05時(shí)，產(chǎn)生的有效路徑數(shù)目合理且程序運(yùn)行效率較高。

圖6　α=0.10的搜索結(jié)果

圖7　α=0.05的搜索結(jié)果

圖8　α=0.01的搜索結(jié)果

4　結(jié)　語

以K次短路徑算法為基礎(chǔ)，結(jié)合GIS所具有的路徑分析功能，提出在GIS環(huán)境下可實(shí)現(xiàn)的有效路徑搜索算法——基于改進(jìn)K次短路徑算法的有效路徑搜索算法。以ArcGIS軟件為GIS平臺(tái)，Python為腳本語言，以實(shí)際路網(wǎng)為對象，對所提出的算法進(jìn)行了實(shí)驗(yàn)，并初步確定了實(shí)際路網(wǎng)中懲罰系數(shù)的合理取值。實(shí)驗(yàn)結(jié)果證明，基于改進(jìn)K次短路徑算法的有效路徑搜索算法，大大提高了有效路徑的搜索效率。同時(shí)，算法在ArcGIS平臺(tái)上的實(shí)現(xiàn)方法，能為有效路徑相關(guān)理論在ArcGIS中的應(yīng)用提供一定的技術(shù)手段和方法。

[1]何勝學(xué),范炳全.隨機(jī)交通分配中有效路徑的搜索算法[J].交通與計(jì)算機(jī),2005,23(5):38-41.

[2]何勝學(xué),范炳全.基于有效路徑的交通流博弈分配算法[J].交通運(yùn)輸系統(tǒng)工程與信息,2007,7(1):115-119.

[3]何勝學(xué),范炳全.基于定向?qū)哟慰臻g推理的有效路徑搜索算法[J].交通運(yùn)輸系統(tǒng)工程與信息,2006,6(2):66-71.

[4]楊群,關(guān)偉,張國伍.基于合理多路徑的路徑選擇方法的研究[J].管理工程學(xué)報(bào),2002(4):42-45.

[5]賴樹坤,姚憲輝,彭愚.交通網(wǎng)絡(luò)中有效路徑確定方法的探討[J].交通標(biāo)準(zhǔn)化,2008(1):137-138.

[6]周和平,王芳,成軍.區(qū)間阻抗下的多路徑交通分配[J].長沙理工大學(xué)學(xué)報(bào),2014,11(3):1-5.

[7]楊信豐,劉蘭芬,李引珍,等.基于影響度的有效路徑集合的確定[J].交通運(yùn)輸系統(tǒng)工程與信息,2011,11(6):104-110.

[8]秦鳴,姜培.基于有效路徑的多路徑交通流分配[J].交通標(biāo)準(zhǔn)化,2010(4):30-32.

[9]李志純,黃海軍.隨機(jī)交通分配中有效路徑的確定方法[J].交通運(yùn)輸系統(tǒng)工程與信息,2003,3(1):28-32.

[10]張建勇,李成江,黃汝存.聯(lián)網(wǎng)高速公路有效路徑伸展系數(shù)[J].公路交通科技,2008,25(1):116-119.

[11]張洋,彭利人，呂培建.合理多路徑的確定方法與劃分標(biāo)準(zhǔn)[J].中國交通信息產(chǎn)業(yè),2007(5):48-52.

[12]白軼多,胡鵬,夏蘭芳.關(guān)于K次最短路徑問題的分析與求解[J].武漢大學(xué)學(xué)報(bào),2009,34(4)：492-494.

[13]GANG Feng. Improving space efficiency with path length prediction for finding K shortest simple path[J]. IEEE Transaction on Computers, 2014:2459-2472.

(編輯：張峰)

Algorithm of Efficient Path Searching and Its Implementation by Improving K Shortest Path Algorithm

ZHENG Guixing1, WANG Yuan2, WANG Peng2，LI Yueming2, CHE Yahui2

(1. General Course Department, Military Transportation University, Tianjin 300161, China; 2. Postgarduate Training Brigade, Military Transportation University, Tianjin 300161, China)

Aimed to obtain the most efficient paths within the shortest time, by employing the analytic founction of ArcGIS and the algorithm of overlapping penalty, this paper improves K shortest path algorithm and comes up with an efficient path searching algorithm which is implemented on ArcGIS platform and proved in road network visual tests to be effective and applicable.

effective path; K shortest path algorithm; GIS

2015- 08-31；

2015-10-26.

鄭貴省(1975—)，男，博士，副教授，碩士研究生導(dǎo)師.

10.16807/j.cnki.12-1372/e.2016.04.020

U491.1

A

1674-2192(2016)04- 0080- 05