基于POI分布的多導(dǎo)航任務(wù)路徑規(guī)劃算法研究

劉 銳，李 翔，黎 達

（1.鄭州測繪學(xué)院，河南 鄭州 450052）

基于POI分布的多導(dǎo)航任務(wù)路徑規(guī)劃算法研究

劉 銳1，李 翔1，黎 達1

（1.鄭州測繪學(xué)院，河南 鄭州 450052）

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

路徑規(guī)劃算法；多導(dǎo)航任務(wù)；A*算法；POI分布

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

1 多導(dǎo)航任務(wù)下路徑規(guī)劃與POI的關(guān)聯(lián)關(guān)系

1.1 多導(dǎo)航任務(wù)下路徑規(guī)劃特點

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

圖1 多導(dǎo)航任務(wù)路徑規(guī)劃模型

1.2 多導(dǎo)航任務(wù)與POI的關(guān)聯(lián)關(guān)系研究

1.2.1 POI分類分級模型的建立

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

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

1.2.2 考慮POI需求的導(dǎo)航任務(wù)模型建立

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

表1 導(dǎo)航電子地圖POI分類表

表2 導(dǎo)航任務(wù)與POI關(guān)系表

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

表3 城市出行導(dǎo)航任務(wù)下POI重要性等級表

2 多導(dǎo)航任務(wù)下基于POI分布的導(dǎo)航路徑規(guī)劃算法研究

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

2.1.1 A*路徑規(guī)劃算法

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

2.1.2 考慮POI分布的路徑評價

要找出最符合用戶需求的路徑首先需要基于A*算法計算出多條備選路徑，然后對計算出的多條備選路徑進行基于POI分布的整體代價值評價。主要是基于POI與導(dǎo)航路徑之間的距離、POI整體分布與導(dǎo)航路徑之間的關(guān)系、導(dǎo)航任務(wù)對不同POI的需求度3類指標對路徑優(yōu)劣性進行衡量?？紤]POI分布的最優(yōu)路徑規(guī)劃算法基本流程如圖2所示。

圖2 考慮POI分布的路徑規(guī)劃流程圖

2.2 多導(dǎo)航任務(wù)下基于POI分布的路徑規(guī)劃模型建立

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

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

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

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

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

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

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

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

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

輸出該類POI空間分布聚類結(jié)果；

5）依照第一到第四步對導(dǎo)航電子地圖中與導(dǎo)航任務(wù)相關(guān)的所有POI大類地物進行空間聚類，輸出最終結(jié)果。

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

2.3 導(dǎo)航路徑規(guī)劃實驗

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

圖3 考慮POI分布的導(dǎo)航路徑規(guī)劃實驗

4 結(jié) 語

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

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

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

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

[4] 楊正磊,宋建社,吳永定．多約束條件下戰(zhàn)場導(dǎo)航路徑規(guī)劃問題研究[J]．系統(tǒng)仿真學(xué)報,2011, 23(6) ：1 288-1 291

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

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

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

[8] 董勇,靳穎．中國導(dǎo)航電子地圖產(chǎn)業(yè)的發(fā)展[J]．中國航天, 2009 (12)： 10-12

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

P208

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

10.3969/j.issn.1672-4623.2017.06.005

劉銳，碩士研究生，主要研究方向為導(dǎo)航定位算法、嵌入式導(dǎo)航系統(tǒng)開發(fā)。

2016-01-21。

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