基于POI分布的多導航任務路徑規劃算法研究

劉 銳，李 翔，黎 達

（1.鄭州測繪學院，河南 鄭州 450052）

基于POI分布的多導航任務路徑規劃算法研究

劉 銳1，李 翔1，黎 達1

（1.鄭州測繪學院，河南 鄭州 450052）

隨著導航系統在各領域的廣泛應用，用戶對導航系統的要求呈現出專業化、需求多樣化等特點，進而對導航服務相關理論提出了新的要求。因此，如何在現有導航服務模式的基礎上，結合導航用戶需求特點設計出更加科學合理的導航服務方案具有重要的研究意義與實際價值。研究首先針對導航需求建立了包括城市出行、遠距離自駕游、物流運輸、軍事作戰等一系列導航任務的多導航任務模型，探討了不同導航任務下路徑規劃的特點。然后基于現有POI分類分級體系量化了地圖POI分布對導航路徑規劃的影響，并在A*算法的基礎上設計了考慮POI分布的路徑規劃算法，提高了規劃路徑的科學性與適用性。

路徑規劃算法；多導航任務；A*算法；POI分布

導航路徑規劃是導航系統和導航信息服務的重要組成部分，其應用涉及從日常生活出行到交通物流以及軍事作戰的各個方面，如日常生活中基于GPS的城市道路規劃、遠距離自駕游路線規劃，交通行業中的物流運輸、人員運輸，軍事領域中無人機自主導航、單兵作戰導航等。導航路徑規劃的本質是在所有可行通道中搜尋出滿足導航用戶需求且總代價最小的連通方案，使用戶能以最合理的方式到達目的地。目前常用的路徑規劃算法有A*算法、Dijkstra算法、Floyd算法、神經網絡算法等[1]，不同的規劃算法適用于解決不同種類的路徑規劃問題。總體而言，所有算法都是在技術層面上，簡單地從最短、最快、最簡單等角度出發，對從A點到B點的可行性進行了探究，并沒有充分考慮導航用戶更深層次的專業需求。即使通過不同路徑規劃算法提供給用戶多條路徑進行選擇，由于導航電子地圖載負量限制，用戶也無法在充分考慮沿途地理要素的前提下科學選擇符合自己要求的路徑。因而對于建立面向多用戶多任務及多導航載體的綜合導航系統，還需要思考如何量化表達地理環境要素對導航路徑的影響，使導航路徑規劃服務朝專業化、智能化的方向發展。

1 多導航任務下路徑規劃與POI的關聯關系

1.1 多導航任務下路徑規劃特點

由于導航載體、導航人員、導航距離以及運送物質類型等因素的不同，不同導航任務下用戶對導航路徑的要求也不盡一致，主要體現在對導航路徑本身屬性以及對導航路徑周圍地理要素分布要求兩個方面。以長途物流運輸為例，司機更傾向于關注沿途對大型車輛的道路限制（如速度、載重、運送物資類型等）以及餐飲食宿、汽車服務點、收費站等地物分布。因此在進行路徑規劃時必須將一些道路屬性以及相關POI的分布情況考慮到路徑規劃算法當中。而在城市出行中，用戶可能更傾向于選擇紅綠燈少、交通更通暢或者沿途具有更多商業設施的道路作為最優路徑。總體而言，多導航任務下路徑規劃模型可表示如圖1。

圖1 多導航任務路徑規劃模型

1.2 多導航任務與POI的關聯關系研究

1.2.1 POI分類分級模型的建立

為了在導航電子地圖中根據不同使用需求進行POI要素的控制與表達。先要對比較有代表性的POI要素進行分類，分類代碼體系的編制應遵循普遍性、一致性、拓展性、延伸性、公共性5個原則[2]，從大類開始逐一細化。對于一般網絡電子地圖而言，可將POI分為包括自然地理、人文地理、黨政機構、教育培訓、醫療衛生、餐飲、文化休閑、住宿、宗教設施、購物、金融機構、汽車服務、日常服務、傳媒與通信、應急、企事業單位、軍事設施、其他要素18個大類。在導航電子地圖當中，POI可進一步簡化為自然地理、人文地理、醫療衛生、餐飲、文化休閑、住宿、購物、金融機構、汽車服務、日常服務、應急、軍事設施與目標12個大類。

并根據大類的特點繼續向下細分。如表1所示。

1.2.2 考慮POI需求的導航任務模型建立

研究導航用戶對導航系統的需求首先需要對導航任務進行分類，采用問卷調查與任務分析的方式對每一大類的導航任務特點進行研究。目前主要研究的導航任務類型包括城市出行、遠距離自駕游、物流運輸以及軍事作戰4大類，并選取了包括對POI的需求程度a、規避程度b、空間分布c 3類評價因子建立導航任務與12個POI大類之間的關聯關系，如表2所示。

表1 導航電子地圖POI分類表

表2 導航任務與POI關系表

通過對導航任務的特點進行分析，結合導航目的、導航距離、出行方式3類因素對各個導航任務下用戶需求的綜合影響的問卷調查結果加權計算出最終的用戶需求度權值和顯示等級。城市出行導航任務下各類POI要素的需求度權重值和顯示等級表如表3所示。

表3 城市出行導航任務下POI重要性等級表

2 多導航任務下基于POI分布的導航路徑規劃算法研究

2.1A*路徑規劃算法與考慮POI分布的路徑評價

2.1.1 A*路徑規劃算法

A*算法是一種建立在Dijkstra算法和BFS算法基礎上的啟發型搜索算法[3]。算法的關鍵是建立啟發函數f (x)=g (x)+h (x)來衡量可行路徑的優劣性并進行篩選，函數中g (x)表示從起點到當前節點所花費的代價值，h (x)表示從當前節點到終點預計花費的代價值，一般可以使用當前節點到終點距離d以及起點到當前節點線段與當前節點到終點線段之間的夾角a來描述代價值，其他變量還有時間、高程等[4]。若令f (x)中所有 h(x)=0，即只考慮從起點到當前節點路徑所花費的代價值，則A*算法等價于Dijkstra算法[5]。不同于Dijkstra算法，A*算法并不是一種最優路徑算法，因而可以搜索出多條符合要求的路徑供導航用戶進行評價與選擇[6-7]。

2.1.2 考慮POI分布的路徑評價

要找出最符合用戶需求的路徑首先需要基于A*算法計算出多條備選路徑，然后對計算出的多條備選路徑進行基于POI分布的整體代價值評價。主要是基于POI與導航路徑之間的距離、POI整體分布與導航路徑之間的關系、導航任務對不同POI的需求度3類指標對路徑優劣性進行衡量。考慮POI分布的最優路徑規劃算法基本流程如圖2所示。

圖2 考慮POI分布的路徑規劃流程圖

2.2 多導航任務下基于POI分布的路徑規劃模型建立

基于多任務導航的多任務下POI分布需要首先對POI性質進行描述與分類，初步可將導航電子地圖中所有POI分為必經點、禁止點、推送點、規避點以及無影響點5大類。其中，必經點是導航過程當中用戶必須經過的地理要素點，如軍事活動中重要必經目標點，物流運輸沿途取貨點或配送點等；禁止點針對導航過程中禁止經過的地理要素點，如軍事活動中的敵方火力點，對于某些特殊車輛采取的限制性道路設施；推送點主要是某些情況下導航用戶對導航路徑沿線的某些類別地理要素有強烈需求對應的POI，如長途運輸沿途的加油站、長途自駕游沿途服務區，或是城市觀光出行中的大型商區、銀行、景區等；規避點針對導航過程中導航用戶希望盡量避免通過的地理要素點，如城市出行中盡量避免的紅綠燈路口或擁堵區、危險品運輸過程中的大型居民區、長途車輛司機所關心的收費站等。無影響點是與導航任務無關或者關系微弱的地理要素點。其次需要確定所研究POI的范圍，綜合考慮算法的效率與實用性可將參與計算的POI地理范圍限定在備選路徑兩側半徑為1 km的緩沖區內。

評價上述范圍內的5類POI分布對備選路徑影響程度可從POI與路徑之間的距離、用戶對POI需求程度、POI規避系數、POI整體空間分布情況4個方面入手，建立POI對導航路徑進行評價的函數G(x)，且G(x)滿足：

式中，α表示POI需求度權值；β表示路徑總長度權值；γ表示POI整體空間分布權值；Dis(pi)表示任何一類POI中第i個POI點相對于導航路徑 的近似距離；Need(POIj)表示特定導航任務下用戶對第j類POI的需求度，根據特定導航任務種類下不同POI設定不同需求值，必經點需求度設為正向無窮大，禁止點需求度設為負向無窮大，推送點和規避點需求程度根據實際情況設定；同時總路徑長度SumDis(X)可表示為：

Distri(X)是衡量某一規劃路徑下POI空間分布對導航任務影響程度的變量。總體而言，影響程度與空間中POI分布的種類以及分布坐標有關。因此在計算Distri(X)之前需要通過聚類算法對導航空間中POI分布的種類與位置進行聚類分析，本文采取基于路徑的K-means聚類算法對相關POI點集進行聚類處理，具體步驟如下：

1）根據路徑總長度隨機均勻選取路徑上K個坐標點作為聚類初始質心，標記為μj；

2）計算一個POI大類中所有POI坐標點與K個聚類初始質心之間的距離，將每一個參與計算的POI點xi歸為與之距離最近的質心類Cj：

3）按照公式（4）重新計算每一質心類中POI點集的新質心點：

式中，εi表示對于某一類POI中單個POI的等級系數或重要系數，在沒有對POI分級進行研究的前提下可令所有εi=l，Projection函數用于計算某一空間坐標點在相應路徑上的投影點；

4）迭代第一到第三步直至新的質心點與原質心點相等或距離小于指定閾值，即當質心重合系數V滿足：

輸出該類POI空間分布聚類結果；

5）依照第一到第四步對導航電子地圖中與導航任務相關的所有POI大類地物進行空間聚類，輸出最終結果。

總體而言，最優路徑必須是在總長度、總POI需求度以及POI空間分布三方面綜合最優。

2.3 導航路徑規劃實驗

實驗基于VC平臺并采用鄭州地區導航電子地圖作為實驗基礎數據，全過程在Intel i3+2 GB內存的PC機環境下運行。 實驗對基于A*算法的路徑評價算法所篩選出的城市出行導航任務下的最佳路徑進行了著重顯示。并記錄了路徑選擇所用時間，為以后算法時間上進一步優化積累數據。最后結合表3中計算出的城市出行模式下用戶POI需求度權值表通過模擬用戶導航任務的方法對所篩選出的路徑進行可用性評價。實驗結果表明，通過考慮POI分布的路徑規劃算法規劃出的路徑能充分體現導航用戶對于導航路徑沿途POI的需求。圖3為考慮POI分布的導航路徑規劃實驗效果。

圖3 考慮POI分布的導航路徑規劃實驗

4 結 語

本文基于A*算法和導航電子地圖POI分布對多導航任務下的導航路徑規劃問題進行了研究。通過對導航電子地圖POI分類建模以及特定導航任務下導航需求的分析，建立了導航任務與導航電子地圖POI之間的關聯關系表。然后結合該關系表設計了針對多條備選路徑的評價體系與算法，在A*算法篩選出的多條導航路徑之中選擇最優路徑作為最終的規劃路徑。最后在基于Android的導航實驗平臺上實現了算法。實驗證明，新算法中規劃出的路徑能更加充分地體現用戶對導航路徑性質上的需求，從而更好地為用戶提供導航路徑規劃服務。但是，目前對導航路徑周圍POI分布情況的評價僅僅局限于文中所歸納的12個POI大類，且沒有考慮POI要素的等級。要建立功能更完善的導航系統并提供更專業化、智能化的導航路徑規劃服務[8]，還需要進一步研究導航任務對詳細POI類別的需求情況。

[1] 史輝,曹聞,朱述龍． A*算法的改進及其在路徑規劃中的應用[J]．測繪與空間地理信息, 2009, 32(6)：208-211

[2] 張玲． POI的分類標準研究[J]．測繪通報,2012 (10)： 82-84

[3] 張東,錢德沛,劉愛龍．車輛導航中基于約束條件的地圖引擎和路徑規劃[J]．計算機工程,2007, 33(1) ：236-238

[4] 楊正磊,宋建社,吳永定．多約束條件下戰場導航路徑規劃問題研究[J]．系統仿真學報,2011, 23(6) ：1 288-1 291

[5] 趙明元,周軍．基于A*算法的四維實時航跡規劃算法[J]．火力與指揮控制, 2008, 33(8)： 98-101

[6] 王殿君． 基于改進A*算法的室內移動機器人路徑規劃[J]．清華大學學報（自然科學版）, 2012, 52(8)：1 085-1 089

[7] 周成平,陳前洋．基于稀疏A*算法的三維航跡并行規劃算法[J]．華中科技大學學報（自然科學版）, 2005, 33(5)： 42-45

[8] 董勇,靳穎．中國導航電子地圖產業的發展[J]．中國航天, 2009 (12)： 10-12

[9] 蔡永香,劉挺．基于LBS 的貨運信息服務系統的設計與實現[J]．地理空間信息, 2015,13(2)： 78-80

P208

B文章編號：1672-4623（2017）06-0018-04

10.3969/j.issn.1672-4623.2017.06.005

劉銳，碩士研究生，主要研究方向為導航定位算法、嵌入式導航系統開發。

2016-01-21。

項目來源：國家自然科學基金資助項目（41271450）。