孫蘭會 成鋒 陸愈實

摘 要： 路徑規(guī)劃問題是地理信息系統(tǒng)（GIS）研究領(lǐng)域中的關(guān)鍵內(nèi)容之一，最短路徑的尋找更是熱點問題。在數(shù)據(jù)量較大時，傳統(tǒng)前K條最短路徑算法效率較低，且不能解決某些實際需求下規(guī)劃K條差異較大的路徑問題。在Dijkstra算法的基礎(chǔ)上，引入有利度與重復(fù)度的概念，通過對路徑結(jié)果重復(fù)度的檢測以及由有利度的改變所引起的圖的變化，循環(huán)尋找當(dāng)前圖中的最短路徑，從而實現(xiàn)了多條差異路徑的規(guī)劃。在上述算法的基礎(chǔ)上，對野外區(qū)域中帶狀區(qū)域的有利度及重復(fù)度進行控制，解決了傳統(tǒng)前K條最短路徑算法難以滿足野外區(qū)域多條差異路徑規(guī)劃的問題。

關(guān)鍵詞： 路徑規(guī)劃； GIS； 有利度； 重復(fù)度

中圖分類號： TN911?34； TM417 文獻標(biāo)識碼： A 文章編號： 1004?373X（2016）05?0101?04

0 引 言

KSP問題是一個非常復(fù)雜的問題，而且根據(jù)不同的應(yīng)用場景以及具體需求要采用完全不同的算法來解決[1]。目前雖然存在多種KSP算法，但沒有一種算法能夠普遍適用于常規(guī)多條路徑規(guī)劃的問題，而且每種KSP算法都傾向于問題的某些方面對問題進行解決[2]。

1 K優(yōu)路徑規(guī)劃算法及其擴展

KSP問題是一個非常復(fù)雜的問題，根據(jù)不同的應(yīng)用場景以及具體的需求，KSP問題需要相應(yīng)的解決辦法?，F(xiàn)有的各種算法并不能很好地解決本文所面對的在大規(guī)模數(shù)據(jù)下尋找多條滿足一定差異性路徑的問題。因此，提出了大規(guī)模數(shù)據(jù)下滿足重復(fù)度要求的K優(yōu)路徑規(guī)劃算法（KPLR）[3]。

KPLR算法可有效解決在大規(guī)模數(shù)據(jù)下多條差異路徑規(guī)劃的問題。KPLR算法引入了有利度的概念，它是一種簡單的啟發(fā)信息，是圖中每條邊的附加屬性，促使算法在每次循環(huán)中搜索有別于上次結(jié)果的其他路徑[4]。同時，KPLR算法引入了重復(fù)度的概念，它的使用保證了結(jié)果集的質(zhì)量。由于使用的啟發(fā)信息較為簡單，算法得到的路徑結(jié)果犧牲了一定的精度，但大大提高了效率?？紤]到在大規(guī)模數(shù)據(jù)下進行路徑規(guī)劃的需求以及用戶注重路徑之間差異的特點，這樣的做法是較為合理的。由于需要解決的是實際中的問題，因此暫不考慮負邊值所帶來的問題[5]。

1.1 KPLR算法

使用path_current表示當(dāng)前分析路徑，path_current_vertex表示其頂點序列；path_current_edge表示其邊序列；path_result表示已經(jīng)得到的可用路徑結(jié)果集合；函數(shù)Repetition（path_current，path_result）計算當(dāng)前路徑與路徑結(jié)果集合中每條路徑的重復(fù)度是否滿足重復(fù)度限制系數(shù)[θ；][Kth]表示需要找到的路徑數(shù)量；Count表示在給定某[θ]值時算法可以進行的循環(huán)次數(shù)上限；[Δθ]表示當(dāng)需要放寬重復(fù)度限制時的遞增步長。KPLR算法如下：

（1） int k=0（用整數(shù)[k]記錄已經(jīng)得到的路徑數(shù)目）；int c=0（用整數(shù)[c]記錄在當(dāng)前[θ]值下算法已循環(huán)的次數(shù)）；path_result=[?。]

（2） 若[k>Kth]或者[θ≥1，]算法退出，否則轉(zhuǎn)步驟（3）。

（3） 若[c>Count，]置[c=0；]對所有[ei∈E，]重置[ei.u=]1；同時[θ=θ+Δθ，]即放寬重復(fù)度的限制。

（4） path_current=Dijkstra（G，s，e）；c=c+1。

（5） 按順序遍歷path_current_edge中所有的邊[ei，]降低其有利度，使[ei.u=ei.uα。]

（6） 若Repetition（path_current，path_result）為真，即對任意path∈path_result，Repetition（path，path_current）<[θ，]則當(dāng)前路徑滿足重復(fù)度要求，path_result=path_result∪{path_current}，同時[k=k+1，]轉(zhuǎn)步驟（2）；若Repetition（path_current，path_result）為假，無操作，直接轉(zhuǎn)步驟（2）。

在步驟（5）中，對當(dāng)前路徑path_current中所有邊降低其有利度，這樣就改變了當(dāng)前圖[G，]并降低了path_current在下次循環(huán)中的有利度，促使Dijkstra在新圖[G]中尋找有別于它的最短路徑。

在具體的實現(xiàn)過程中，可以通過有利度懲罰因子[α]以及重復(fù)度限制系數(shù)[θ]對算法進行一定的控制。

1.2 擴展的多點規(guī)劃KPLR算法

在實際應(yīng)用場景中的路徑規(guī)劃往往不僅限于兩點之間，經(jīng)常會有在多點之間規(guī)劃路線的需求，而上述KPLR算法無法滿足這種需求，因此需要將其擴展，以便滿足這種需求[6]。

擴展的KPLR算法（EKPLR）可用于進行多點之間的K優(yōu)路徑規(guī)劃。在實際應(yīng)用中的多點規(guī)劃除起始點和終止點外，還有必經(jīng)點、禁止點以及危險區(qū)域等[7]。

用ViaNode表示必經(jīng)點序列，F(xiàn)orbiddenNode表示禁止點集合，DangerousArea表示危險區(qū)域集合，[vi∈]ForbiddenNode表示點[vi]為禁止點，[vi]∈DangerousArea表示點[vi]在危險區(qū)域中。使用 Edge（[vi]）表示以點[vi]為某一端點的所有邊的集合。使用 ForbiddenEdge表示某一禁止點或位于危險區(qū)域中的點[vi]為某一端點的所有邊的集合。其他符號同上文描述。帶必經(jīng)點、禁止點和危險區(qū)域的KPLR算法如下：

（1） 對任意[vi∈V，]若[vi∈]ForbiddenNode或[vi∈]DangerousArea，則對所有[ei∈]Edge（[vi]），做[ei.u=1∞，]使其任意小，同時將[ei]加入ForbiddenEdge。

（2） 將起點[s]加入ViaNode開頭，終點[e]加入ViaNode末尾。

（3） int k=0（用整數(shù)[k]記錄已經(jīng)得到的路徑數(shù)目）； int c=0（用整數(shù)[c]記錄在當(dāng)前[θ]值下算法已循環(huán)的次數(shù)）； path_result=?。

（4） 若[k>Kth]或者θ≥1，算法退出，否則轉(zhuǎn)步驟（5）。

（5） 若[c>Count，]置[c=0；]對所有[ei∈E]且[ei∈]ForbiddenEdge，重置 [ei.u=1；]同時[θ=θ+Δθ，]即放寬重復(fù)度的限制。

（6） 對每兩個相鄰必經(jīng)點[vi]和[vi+1，]其中[i=0，]1，…，|ViaNode|-2， pathi=Dijkstra（G，vi，vi+1）。

（7） path_current=[pathi；]c=c+1。

（8） 按順序遍歷path_current_edge中所有的邊[ei，]降低其有利度，使[ei.u=ei.uα。]

（9） 若Repetition（path_current，path_result）為真，即對任意path∈path_result，Repetition（path，path_current）<[θ，]則當(dāng)前路徑滿足重復(fù)度要求，path_result= path_result+path_current，同時[k=k+1，]轉(zhuǎn)步驟（4）；若Repetition（path_current，path_result）為假，無操作，直接轉(zhuǎn)步驟（4）。

在步驟（1）中，首先對禁止點和危險區(qū)域進行處理，對所有禁止點以及在危險區(qū)域中的點，將其所屬的所有邊的有利度降低為任意小，從而其權(quán)值為任意大，也即標(biāo)記為該邊不可行。

在步驟（2）中，將起點和終點作為必經(jīng)點加入ViaNode可以簡化程序代碼，同時仍保持程序的正確性。

在步驟（6）中，首先求出每兩個相鄰必經(jīng)點之間的最短路徑段，然后在步驟（7）中將這些路徑段依次連接，從而得到最終的當(dāng)前路徑path_current。

2 野外區(qū)域路徑規(guī)劃

2.1 問題概述

野外區(qū)域是指沒有路網(wǎng)覆蓋的區(qū)域，由于野外區(qū)域并沒有路網(wǎng)覆蓋，而常規(guī)的路徑規(guī)劃算法是在從路網(wǎng)抽象而成的圖中利用點和線的關(guān)系進行搜索的，因此常規(guī)算法無法直接應(yīng)用于野外區(qū)域的路徑規(guī)劃，在野外區(qū)域中進行路徑規(guī)劃之前，需要根據(jù)所采用的算法對野外區(qū)域進行一定的預(yù)處理[8]。

2.2 多路徑野外規(guī)劃

在對野外區(qū)域進行網(wǎng)格化處理后，便可采取相應(yīng)的KSP算法對多路徑的野外區(qū)域規(guī)劃問題進行求解。在選用相應(yīng)的算法時，結(jié)合野外區(qū)域的特點，要重點考慮網(wǎng)格的密度和路徑的重復(fù)程度。

提出的KPLR算法較適用于求解該問題，但需要結(jié)合野外區(qū)域的上述幾個特點對KPLR算法進行如下改進：

（1） 在算法的每次循環(huán)后，不僅僅是對本次循環(huán)所得臨時路徑進行有利度的衰減，而是將衰減范圍擴展到包括圖中所有以臨時路徑中的節(jié)點為某一端點的所有邊。

（2） 在計算路徑之間的重復(fù)程度時，也將被對比的路徑擴展為包括其上各節(jié)點的所有相鄰8個節(jié)點，即將重復(fù)度的計算改為如下公式：

設(shè)path1和path2為兩條野外路徑，設(shè)Vertex（path1）為path1中所有節(jié)點與其中每個節(jié)點的所有8個相鄰節(jié)點組成的集合，則path2相對于path1的路徑重復(fù)度為path2與集合Vertex（path1）中相同節(jié)點的數(shù)目占path2中所有邊數(shù)的比重，記為YeWaiRepetition（path1，path2）：

YewaiRepetition（pathi，pathj）=|SameVertex（Vertex（pathi），pathj）[||pathj|]

其中|pathj|表示路徑pathj中節(jié)點的數(shù)目；集合SameEdge（Vertex（pathi），pathj）={[ei|ei]∈Vertex（pathi）∧[ei∈]pathj}，|SameEdge（Vertex（pathi），pathj）|表示該集合中元素的個數(shù)。

采用上述兩種改進是為盡可能防止算法所得各結(jié)果路徑出現(xiàn)如圖1所示的情況，即各路徑雖不相同，但其均通過相同的一片區(qū)域，并無實際意義。

將結(jié)合野外區(qū)域的特點進行上述改進后的KPLR算法稱作WKPLR算法。因此，野外區(qū)域中的多路徑規(guī)劃問題的解決步驟大體如下：首先，根據(jù)選擇的所有必經(jīng)點（包含起始點和終止點）劃定一個矩形框，將該矩形框作為搜索范圍；其次，將該矩形框按步長或按數(shù)量劃分為網(wǎng)格，并將該劃分好的網(wǎng)格拓撲為一張圖；最后，在該圖中應(yīng)用WKPLR算法進行路徑規(guī)劃。

野外區(qū)域規(guī)劃WKPLR算法在對野外區(qū)域進行上述預(yù)處理之后，就可以應(yīng)用WKPLR算法在處理得到的圖中進行路徑規(guī)劃。使用path_current表示當(dāng)前分析路徑，path_current_vertex表示其頂點序列；path_current_edge表示其邊序列；path_result表示已經(jīng)得到的可用路徑結(jié)果集合；函數(shù)YewaiRepetition（path_current，path_result）計算當(dāng)前路徑與路徑結(jié)果集合中每條路徑的重復(fù)度是否滿足重復(fù)度限制系數(shù)[θ； Kth]表示需要找到的路徑數(shù)量；Count表示在給定某[θ]值時算法可以進行的循環(huán)次數(shù)上限；[Δθ]表示當(dāng)需要放寬重復(fù)度限制時的遞增步長。野外區(qū)域WKPLR算法如下：

（1） int k=0（用整數(shù)[k]記錄已經(jīng)得到的路徑數(shù)目）；int c=0（用整數(shù)c記錄在當(dāng)前[θ]值下算法已循環(huán)的次數(shù)）；path_result=?。

（2） 若[k>Kth]或者θ≥1，算法退出，否則轉(zhuǎn)步驟（3）。

（3） 若c>Count，置c=0；對所有ei∈E，重置[ei.u=1；]同時θ=θ+Δθ，即放寬重復(fù)度的限制。

（4） path_current=Dijkstra（G，s，e）；[c=c+1。]

（5） 按順序遍歷path_current_edge中所有的節(jié)點[vi，]降低以[vi]為某一端點的所有邊[eii]的有利度，即做[eii.u=][eii.uα。]

（6） 若YewaiRepetition（path_current，path_result）為真，即對任意path∈path_result，YewaiRepetition（path，path_current）<θ，則當(dāng)前路徑滿足重復(fù)度要求，path_result=path_result∪{path_current}，同時[k=k+1，]轉(zhuǎn)步驟（2）；若YewaiRepetition（Path_current，path_result）為假，無操作，直接轉(zhuǎn)步驟（2）。

上述WKPLR算法與KPLR算法基本相同，區(qū)別在于降低有利度的邊的范圍有所擴展，以及計算重復(fù)度時有所改變。

3 實現(xiàn)設(shè)計及分析

基于GIS系統(tǒng)，以Microsoft VC++ 6.0為軟件開發(fā)平臺，實現(xiàn)了基于某地域道路信息網(wǎng)及野外區(qū)域的多條差異路徑選取功能。

3.1 KPLR對比實驗

將該算法與候選消除邊算法（下稱對比算法）進行對比實驗，其為各前K條最短路徑算法中最精確的算法。對比算法所得數(shù)據(jù)作為參考來說明本文算法在上述特定需求下的有效性。其中，以前5條路徑為例，且本文算法各系數(shù)設(shè)置為：[θ=0.5，][Δθ=0.1，][α=1.1。]

采用1[∶]50 000比例尺地圖，選取的起訖點直線距離約為200 km，采用Dijkstra算法找到的最短路徑長度均為229.70 km。經(jīng)過對地圖數(shù)據(jù)處理后得到的圖包含201 070條邊，145 029個節(jié)點。圖2為本文算法得到的5條差異路徑，圖3為對比算法得到的前5條最短路徑。表1為兩種算法得到的路徑之間的重復(fù)度系數(shù)。表2為兩種算法得到的路徑長度信息（單位：km）以及算法運行時間（單位：ms）。

實驗中數(shù)據(jù)量大幅增加，由103級增長為105級。此時，本文算法所得路徑之間重復(fù)度最大值為0.286，小于重復(fù)度初始閾值0.5，對比算法重復(fù)度均在0.97以上。運行時間方面，本文算法約為13 s，考慮到數(shù)據(jù)量之大，在實際應(yīng)用中，這是較為合理的時間；對比算法耗時約為85 min，僅作參考。

在路徑長度方面，兩種算法得到的路徑1長度相同，本文算法得到的剩余4條路徑長度值也較為合理，其中路徑5與對比算法差值最大為13.43 km，占總長度比重不到10%。

本次實驗較好地體現(xiàn)了在大量數(shù)據(jù)下本文算法的有效性。在運行時間上，本文算法有著絕對的優(yōu)勢，同時13 s的運行時間在實際應(yīng)用中也是較合理的時間。在大幅度提升效率的同時，本文算法并未損失太多精度，同時考慮到對差異度的要求本身就是對一部分精度的放棄，因此本文算法較好地滿足了大量數(shù)據(jù)、一定重復(fù)度要求以及合理的運行時間的綜合需求。

3.2 WKPLR對比實驗

下面進行野外區(qū)域中多條差異路徑規(guī)劃的對比實驗，對比算法為針對野外區(qū)域進行改進的WKPLR算法與雙向搜索算法。實驗以前3條路徑為例，且WKPLR算法各系數(shù)設(shè)置為：[θ=0.5，][Δθ=0.1，][α=1.1。]

采用1[∶]250 000比例尺地圖，選取的起訖點直線距離約為13 km。由于起訖點距離長度較為合適，因此實現(xiàn)中網(wǎng)格劃分采用按步長的方式，以保證路徑結(jié)果的精確程度。在具體實現(xiàn)中，步長設(shè)置為200 m。圖4為WKPLR算法所得的3條差異路徑，圖5為對比算法所得的3條差異路徑。表3為兩種算法得到的路徑之間重復(fù)度系數(shù)。

由圖4，圖5可以看到WKPLR算法和對比算法在野外區(qū)域中規(guī)劃所得路徑的直觀效果。對比算法所得3條路徑全部通過同一條帶狀區(qū)域，且3條路線交織在一起，這樣的3條路線在實際應(yīng)用中其實可看做是同一條路線，并無太多實際應(yīng)用價值。而針對野外區(qū)域改進后的WKPLR算法所得3條路徑能夠找到規(guī)劃區(qū)域中的3個差別較大的帶狀區(qū)域，從直觀效果來看，3條路線之間的差異度較大，效果也較好。

表3的數(shù)據(jù)也證實了這種差異性。由于在計算野外區(qū)域中路線的重復(fù)度時采用了改進的帶狀區(qū)域重復(fù)度計算方式，不僅計算路線上的點，而且包括這些點的所有相鄰節(jié)點，也即被對比的點集合為路線所經(jīng)過的一條帶狀區(qū)域，因此對比算法的3條路徑之間差異度均在0.98以上，雖然它們經(jīng)過的點有一定的區(qū)別，但這些點均在同一帶狀區(qū)域中。而改進的KPLR算法所得重復(fù)度均在0.5以下。因此，實驗數(shù)據(jù)也進一步證實了WKPLR算法在野外區(qū)域中進行多條差異路徑規(guī)劃的有效性。

4 結(jié) 論

KSP問題是路徑規(guī)劃領(lǐng)域中的重點問題之一，也是近些年研究的熱點問題。KSP應(yīng)用場景非常廣泛，它是GIS中的重點研究內(nèi)容，同時也應(yīng)用到路由選擇、圖像分割以及語音識別等領(lǐng)域。KSP問題是一個非常復(fù)雜的問題，針對不同的應(yīng)用場景及需求往往需要不同的解決辦法。

本文從實際應(yīng)用的角度，結(jié)合大規(guī)模數(shù)據(jù)以及路徑差異度的需求提出了KPLR算法及其野外區(qū)域版本W(wǎng)KPLR，其中KPLR算法是解決大規(guī)模數(shù)據(jù)下進行多條差異路徑規(guī)劃問題的有效算法，同時，WKPLR算法結(jié)合野外區(qū)域的特點對KPLR算法進行改進，可有效解決野外區(qū)域中的多條差異路徑規(guī)劃問題，具有實際的應(yīng)用價值。

參考文獻

[1] 牛振東，師雪霖，葉成林.數(shù)字圖書館支撐技術(shù)領(lǐng)域標(biāo)準規(guī)范的現(xiàn)狀和發(fā)展[J].我國數(shù)字圖書館標(biāo)準規(guī)范建設(shè)，2003（7）：11?12.

[2] 蔡俊，李欽富，王金泉.一種Dijkstra優(yōu)化算法的研究與實現(xiàn)[J].信息技術(shù)，2011，35（4）：104?107.

[3] 王開義，趙春江，胥桂仙，等.GIS領(lǐng)域最短路徑搜索問題的一種高效實現(xiàn)[J].中國圖象圖形學(xué)報，2003，8（8）：951?956.

[4] 高松，陸峰.K則最短路徑算法效率與精度評估[J].中國圖象圖形學(xué)報，2009，14（8）：1677?1683.

[5] 柴登峰，張登榮.前N條最短路徑問題的算法及應(yīng)用[J].浙江大學(xué)學(xué)報，2002，36（5）：531?534.

[6] 袁紅濤，朱美正.K優(yōu)路徑的一種求解算法與實現(xiàn)[J].計算機工程與應(yīng)用，2004，40（6）：51?53.

[7] 馬炫，劉慶.求解K條最短路徑問題的混合蛙跳算法[J].信息與控制，2011，40（5）：614?618.

[8] 賈應(yīng)煒.云計算環(huán)境下的GIS軟件工程設(shè)計分析[J].現(xiàn)代電子技術(shù)，2015，38（17）：133?134.