基于GIS的路徑規劃算法研究與實現

孫蘭會 成鋒 陸愈實

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

關鍵詞： 路徑規劃； GIS； 有利度； 重復度

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

0 引 言

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

1 K優路徑規劃算法及其擴展

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

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

1.1 KPLR算法

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

（1） int k=0（用整數[k]記錄已經得到的路徑數目）；int c=0（用整數[c]記錄在當前[θ]值下算法已循環的次數）；path_result=[?。]

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

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

（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）<[θ，]則當前路徑滿足重復度要求，path_result=path_result∪{path_current}，同時[k=k+1，]轉步驟（2）；若Repetition（path_current，path_result）為假，無操作，直接轉步驟（2）。

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

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

1.2 擴展的多點規劃KPLR算法

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

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

用ViaNode表示必經點序列，ForbiddenNode表示禁止點集合，DangerousArea表示危險區域集合，[vi∈]ForbiddenNode表示點[vi]為禁止點，[vi]∈DangerousArea表示點[vi]在危險區域中。使用 Edge（[vi]）表示以點[vi]為某一端點的所有邊的集合。使用 ForbiddenEdge表示某一禁止點或位于危險區域中的點[vi]為某一端點的所有邊的集合。其他符號同上文描述。帶必經點、禁止點和危險區域的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（用整數[k]記錄已經得到的路徑數目）； int c=0（用整數[c]記錄在當前[θ]值下算法已循環的次數）； path_result=?。

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

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

（6） 對每兩個相鄰必經點[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）<[θ，]則當前路徑滿足重復度要求，path_result= path_result+path_current，同時[k=k+1，]轉步驟（4）；若Repetition（path_current，path_result）為假，無操作，直接轉步驟（4）。

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

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

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

2 野外區域路徑規劃

2.1 問題概述

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

2.2 多路徑野外規劃

在對野外區域進行網格化處理后，便可采取相應的KSP算法對多路徑的野外區域規劃問題進行求解。在選用相應的算法時，結合野外區域的特點，要重點考慮網格的密度和路徑的重復程度。

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

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

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

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

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

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

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

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

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

（1） int k=0（用整數[k]記錄已經得到的路徑數目）；int c=0（用整數c記錄在當前[θ]值下算法已循環的次數）；path_result=?。

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

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

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

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

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

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

3 實現設計及分析

基于GIS系統，以Microsoft VC++ 6.0為軟件開發平臺，實現了基于某地域道路信息網及野外區域的多條差異路徑選取功能。

3.1 KPLR對比實驗

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

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

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

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

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

3.2 WKPLR對比實驗

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

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

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

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

4 結 論

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

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

參考文獻

[1] 牛振東，師雪霖，葉成林.數字圖書館支撐技術領域標準規范的現狀和發展[J].我國數字圖書館標準規范建設，2003（7）：11?12.

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

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

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

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

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

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

[8] 賈應煒.云計算環境下的GIS軟件工程設計分析[J].現代電子技術，2015，38（17）：133?134.