劉 銳，李 翔，黎 達(dá)

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

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

劉 銳1，李 翔1，黎 達(dá)1

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

隨著導(dǎo)航系統(tǒng)在各領(lǐng)域的廣泛應(yīng)用，用戶對導(dǎo)航系統(tǒng)的要求呈現(xiàn)出專業(yè)化、需求多樣化等特點(diǎn)，進(jìn)而對導(dǎo)航服務(wù)相關(guān)理論提出了新的要求。因此，如何在現(xiàn)有導(dǎo)航服務(wù)模式的基礎(chǔ)上，結(jié)合導(dǎo)航用戶需求特點(diǎn)設(shè)計出更加科學(xué)合理的導(dǎo)航服務(wù)方案具有重要的研究意義與實(shí)際價值。研究首先針對導(dǎo)航需求建立了包括城市出行、遠(yuǎn)距離自駕游、物流運(yùn)輸、軍事作戰(zhàn)等一系列導(dǎo)航任務(wù)的多導(dǎo)航任務(wù)模型，探討了不同導(dǎo)航任務(wù)下路徑規(guī)劃的特點(diǎn)。然后基于現(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ī)劃、遠(yuǎn)距離自駕游路線規(guī)劃，交通行業(yè)中的物流運(yùn)輸、人員運(yùn)輸，軍事領(lǐng)域中無人機(jī)自主導(dǎo)航、單兵作戰(zhàn)導(dǎo)航等。導(dǎo)航路徑規(guī)劃的本質(zhì)是在所有可行通道中搜尋出滿足導(dǎo)航用戶需求且總代價最小的連通方案，使用戶能以最合理的方式到達(dá)目的地。目前常用的路徑規(guī)劃算法有A*算法、Dijkstra算法、Floyd算法、神經(jīng)網(wǎng)絡(luò)算法等[1]，不同的規(guī)劃算法適用于解決不同種類的路徑規(guī)劃問題?？傮w而言，所有算法都是在技術(shù)層面上，簡單地從最短、最快、最簡單等角度出發(fā)，對從A點(diǎn)到B點(diǎn)的可行性進(jìn)行了探究，并沒有充分考慮導(dǎo)航用戶更深層次的專業(yè)需求。即使通過不同路徑規(guī)劃算法提供給用戶多條路徑進(jìn)行選擇，由于導(dǎo)航電子地圖載負(fù)量限制，用戶也無法在充分考慮沿途地理要素的前提下科學(xué)選擇符合自己要求的路徑。因而對于建立面向多用戶多任務(wù)及多導(dǎo)航載體的綜合導(dǎo)航系統(tǒng)，還需要思考如何量化表達(dá)地理環(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ī)劃特點(diǎn)

由于導(dǎo)航載體、導(dǎo)航人員、導(dǎo)航距離以及運(yùn)送物質(zhì)類型等因素的不同，不同導(dǎo)航任務(wù)下用戶對導(dǎo)航路徑的要求也不盡一致，主要體現(xiàn)在對導(dǎo)航路徑本身屬性以及對導(dǎo)航路徑周圍地理要素分布要求兩個方面。以長途物流運(yùn)輸為例，司機(jī)更傾向于關(guān)注沿途對大型車輛的道路限制（如速度、載重、運(yùn)送物資類型等）以及餐飲食宿、汽車服務(wù)點(diǎn)、收費(fèi)站等地物分布。因此在進(jìn)行路徑規(guī)劃時必須將一些道路屬性以及相關(guān)POI的分布情況考慮到路徑規(guī)劃算法當(dāng)中。而在城市出行中，用戶可能更傾向于選擇紅綠燈少、交通更通暢或者沿途具有更多商業(yè)設(shè)施的道路作為最優(yōu)路徑。總體而言，多導(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ù)不同使用需求進(jìn)行POI要素的控制與表達(dá)。先要對比較有代表性的POI要素進(jìn)行分類，分類代碼體系的編制應(yīng)遵循普遍性、一致性、拓展性、延伸性、公共性5個原則[2]，從大類開始逐一細(xì)化。對于一般網(wǎng)絡(luò)電子地圖而言，可將POI分為包括自然地理、人文地理、黨政機(jī)構(gòu)、教育培訓(xùn)、醫(yī)療衛(wèi)生、餐飲、文化休閑、住宿、宗教設(shè)施、購物、金融機(jī)構(gòu)、汽車服務(wù)、日常服務(wù)、傳媒與通信、應(yīng)急、企事業(yè)單位、軍事設(shè)施、其他要素18個大類。在導(dǎo)航電子地圖當(dāng)中，POI可進(jìn)一步簡化為自然地理、人文地理、醫(yī)療衛(wèi)生、餐飲、文化休閑、住宿、購物、金融機(jī)構(gòu)、汽車服務(wù)、日常服務(wù)、應(yīng)急、軍事設(shè)施與目標(biāo)12個大類。

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

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

研究導(dǎo)航用戶對導(dǎo)航系統(tǒng)的需求首先需要對導(dǎo)航任務(wù)進(jìn)行分類，采用問卷調(diào)查與任務(wù)分析的方式對每一大類的導(dǎo)航任務(wù)特點(diǎn)進(jìn)行研究。目前主要研究的導(dǎo)航任務(wù)類型包括城市出行、遠(yuǎn)距離自駕游、物流運(yùn)輸以及軍事作戰(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ù)的特點(diǎn)進(jìn)行分析，結(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)劣性并進(jìn)行篩選，函數(shù)中g(shù) (x)表示從起點(diǎn)到當(dāng)前節(jié)點(diǎn)所花費(fèi)的代價值，h (x)表示從當(dāng)前節(jié)點(diǎn)到終點(diǎn)預(yù)計花費(fèi)的代價值，一般可以使用當(dāng)前節(jié)點(diǎn)到終點(diǎn)距離d以及起點(diǎn)到當(dāng)前節(jié)點(diǎn)線段與當(dāng)前節(jié)點(diǎn)到終點(diǎn)線段之間的夾角a來描述代價值，其他變量還有時間、高程等[4]。若令f (x)中所有 h(x)=0，即只考慮從起點(diǎn)到當(dāng)前節(jié)點(diǎn)路徑所花費(fèi)的代價值，則A*算法等價于Dijkstra算法[5]。不同于Dijkstra算法，A*算法并不是一種最優(yōu)路徑算法，因而可以搜索出多條符合要求的路徑供導(dǎo)航用戶進(jìn)行評價與選擇[6-7]。

2.1.2 考慮POI分布的路徑評價

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 導(dǎo)航路徑規(guī)劃實(shí)驗(yàn)

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

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

4 結(jié) 語

本文基于A*算法和導(dǎo)航電子地圖POI分布對多導(dǎo)航任務(wù)下的導(dǎo)航路徑規(guī)劃問題進(jìn)行了研究。通過對導(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)航實(shí)驗(yàn)平臺上實(shí)現(xiàn)了算法。實(shí)驗(yà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]，還需要進(jìn)一步研究導(dǎo)航任務(wù)對詳細(xì)POI類別的需求情況。

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

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

[3] 張東,錢德沛,劉愛龍．車輛導(dǎo)航中基于約束條件的地圖引擎和路徑規(guī)劃[J]．計算機(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*算法的四維實(shí)時航跡規(guī)劃算法[J]．火力與指揮控制, 2008, 33(8)： 98-101

[6] 王殿君． 基于改進(jìn)A*算法的室內(nèi)移動機(jī)器人路徑規(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 的貨運(yùn)信息服務(wù)系統(tǒng)的設(shè)計與實(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

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

2016-01-21。

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