地理信息系統(tǒng)中多起點(diǎn)和多終點(diǎn)路徑規(guī)劃的實(shí)現(xiàn)方法

趙曉君

（上海安吉星信息服務(wù)有限公司，上海 201206）

0 引言

網(wǎng)絡(luò)汽車導(dǎo)航系統(tǒng)中經(jīng)常遇見(jiàn)的問(wèn)題有車輛在A點(diǎn)位置請(qǐng)求導(dǎo)航服務(wù)，通過(guò)后臺(tái)路徑規(guī)劃系統(tǒng)并按照用戶的具體要求，完成路徑計(jì)算并下發(fā)到車機(jī)端時(shí)，車輛往往已經(jīng)駛離了A點(diǎn)，如果路徑規(guī)劃系統(tǒng)只設(shè)計(jì)了支持單點(diǎn)對(duì)單點(diǎn)的規(guī)劃，那么用戶就會(huì)不停地聽(tīng)到偏離航線的提示，而且車機(jī)端會(huì)不斷向后臺(tái)系統(tǒng)發(fā)送航線計(jì)算的請(qǐng)求；以此類推，對(duì)于終點(diǎn)信息而言，當(dāng)后臺(tái)客服人員幫助用戶搜索興趣點(diǎn)信息時(shí)，就會(huì)出現(xiàn)名稱和類別完全相同的信息，唯一的差別是位置不同，只有把這些信息投射到地圖上時(shí)，軟件使用人才能知曉。如果客服人員把錯(cuò)誤的興趣點(diǎn)發(fā)送給車機(jī)端，就會(huì)導(dǎo)致駕駛員繞路幾公里甚至十幾公里。本研究設(shè)計(jì)實(shí)現(xiàn)了基于多起點(diǎn)和多終點(diǎn)的路徑計(jì)算，應(yīng)用于當(dāng)前的車載導(dǎo)航服務(wù)中，能提升用戶的出行體驗(yàn)。

1 系統(tǒng)設(shè)計(jì)來(lái)源

隨著汽車保有量的持續(xù)增長(zhǎng)及移動(dòng)互聯(lián)網(wǎng)技術(shù)與車載信息的深入融合，車輛聯(lián)網(wǎng)已成為車載互聯(lián)中的一項(xiàng)標(biāo)準(zhǔn)服務(wù)，而聯(lián)網(wǎng)后的汽車提供的在線車載導(dǎo)航服務(wù)已成為車聯(lián)網(wǎng)服務(wù)的必備產(chǎn)品內(nèi)容[1]。網(wǎng)聯(lián)汽車導(dǎo)航在導(dǎo)航時(shí)經(jīng)常遇到以下問(wèn)題：當(dāng)導(dǎo)航系統(tǒng)規(guī)劃路線下發(fā)時(shí)，車輛已行駛到另一個(gè)地點(diǎn)，這是因?yàn)榫W(wǎng)絡(luò)數(shù)據(jù)傳輸需幾秒甚至十幾十秒[2]，在這段時(shí)間用戶不會(huì)獲得任何導(dǎo)航信息提示，當(dāng)車載導(dǎo)航端完成導(dǎo)航路線接收后，車輛的位置可能已經(jīng)不在規(guī)劃的路線上，從而導(dǎo)致需重新計(jì)算航線，并且每一次重新計(jì)算的航線也都需再次傳輸，不僅耗時(shí)、耗流量，而且會(huì)增加車載路線解析程序的計(jì)算負(fù)擔(dān)。針對(duì)網(wǎng)絡(luò)車載導(dǎo)航起點(diǎn)，在選擇導(dǎo)航目的地時(shí)，對(duì)于明確的地名也會(huì)存在多個(gè)相似的目的地[3]信息。例如，搜索“A服務(wù)區(qū)”或“B服務(wù)區(qū)停車場(chǎng)”，常發(fā)現(xiàn)有2個(gè)同樣名稱和屬性的興趣點(diǎn)，分別位于同一條公路的兩邊，車輛與同名的2個(gè)興趣點(diǎn)直線距離都很近，當(dāng)使用不同的興趣點(diǎn)作為目的地計(jì)算路徑時(shí)，規(guī)劃的路程會(huì)大相徑庭。假設(shè)以車輛行駛方向的“A服務(wù)區(qū)”為目的地，計(jì)算的航線路程結(jié)果只有數(shù)百米，而以與車輛行駛反向的“A服務(wù)區(qū)”為目的地，則需繞行幾公里甚至十幾公里。本研究提供的多起點(diǎn)和多終點(diǎn)導(dǎo)航路徑的方法，可以啟動(dòng)多起點(diǎn)路徑規(guī)劃的算法，避免起點(diǎn)反復(fù)變化的多次計(jì)算，還能預(yù)判并剔除相似的目的地航線后，再將正確的路線下發(fā)車機(jī)端導(dǎo)航接收系統(tǒng)。

2 系統(tǒng)設(shè)計(jì)思想（Design Idea）

本研究要解決的技術(shù)問(wèn)題如下：①提供導(dǎo)航系統(tǒng)多起點(diǎn)航線計(jì)算以降低重算概率，提高導(dǎo)航效率；②解決選擇了易混淆的目的地而導(dǎo)致的繞路問(wèn)題[4]。

如圖1所示，所述導(dǎo)航系統(tǒng)多起點(diǎn)航線計(jì)算以降低重算概率的方法，包括如下步驟：①服務(wù)器在接收到車輛發(fā)送的航線計(jì)算請(qǐng)求后，先確定車輛的位置、速度、方向及車輛前進(jìn)方向上是否有岔路口，然后將各岔路口各線路作為起點(diǎn)計(jì)算航線，將計(jì)算好的1種或多種航線起始部分下發(fā)到車輛導(dǎo)航裝置；②車輛接收到（航線起始部分）后，將當(dāng)前車輛的位置與之相匹配，如果不存在匹配航線則重新發(fā)送航線計(jì)算請(qǐng)求（轉(zhuǎn)步驟①），如果存在某條最佳匹配航線，則向服務(wù)器索取該航線的后續(xù)部分（服務(wù)器為云計(jì)算服務(wù)器）。

圖1 業(yè)務(wù)流程

步驟①中，服務(wù)器一次計(jì)算多條航線，將所有計(jì)算好的航線存儲(chǔ)在服務(wù)器中，并一次全部發(fā)給車輛導(dǎo)航裝置。

針對(duì)選擇了名稱相同的目的地而導(dǎo)致的繞路問(wèn)題，為避免繞路，提升導(dǎo)航服務(wù)效率并節(jié)約燃油和時(shí)間，進(jìn)行如下步驟：①移動(dòng)終端選擇一個(gè)興趣點(diǎn)作為目的地發(fā)送路徑導(dǎo)航請(qǐng)求到服務(wù)器，服務(wù)器接收到路徑導(dǎo)航請(qǐng)求后，以目的地為終點(diǎn)計(jì)算第一導(dǎo)航路徑；②服務(wù)器接著在所述目的地周圍的預(yù)定范圍（預(yù)定范圍為200～800 m）內(nèi)搜索同名或同類型的興趣點(diǎn)；③如果存在同名或同類型的興趣點(diǎn)，則所述服務(wù)器將搜索到的所有興趣點(diǎn)均作為終點(diǎn)繼續(xù)進(jìn)行航線計(jì)算，得出多條起點(diǎn)相同、終點(diǎn)相似的第二導(dǎo)航路徑；④服務(wù)器將多條第二導(dǎo)航路徑與第一導(dǎo)航路徑分別進(jìn)行比較，如果存在預(yù)估距離（導(dǎo)航路徑的減少量超過(guò)500 m的第二導(dǎo)航路徑）或預(yù)估時(shí)間相比第一導(dǎo)航路徑的減少量達(dá)到預(yù)定閥值（預(yù)估時(shí)間節(jié)省10%以上）的第二導(dǎo)航路徑，則同時(shí)下發(fā)該第二導(dǎo)航路徑和第一導(dǎo)航路徑供移動(dòng)終端選擇。

本研究提供的多終點(diǎn)路徑導(dǎo)航方法，通過(guò)在用戶選擇的目的地周圍的一定范圍內(nèi)搜索同名或同類型的興趣點(diǎn)，并將這些興趣點(diǎn)作為終點(diǎn)進(jìn)行航線計(jì)算，再對(duì)這些計(jì)算好的航線進(jìn)行對(duì)比后選出最優(yōu)的航線供用戶選擇，從而避免了用戶因目的地選擇不當(dāng)造成的繞路及時(shí)間上的浪費(fèi)，并且提高了導(dǎo)航效率。

3 系統(tǒng)實(shí)現(xiàn)

3.1 多起點(diǎn)路徑規(guī)劃的系統(tǒng)具體實(shí)現(xiàn)方法

結(jié)合系統(tǒng)狀態(tài)圖（如圖2所示）多起點(diǎn)路徑規(guī)劃的系統(tǒng)具體實(shí)現(xiàn)方法描述如下。

圖2 系統(tǒng)狀態(tài)圖

（1）服務(wù)器在接收到車輛發(fā)送的航線計(jì)算請(qǐng)求后（車輛通過(guò)GPS模塊、陀螺儀和車輪速度脈沖模塊，綜合得到部分參數(shù)，例如車輛的位置、速度、方向，目的地信息作為另一部分參數(shù)，然后通過(guò)2G/3G無(wú)線數(shù)據(jù)鏈路例如CDMA，向服務(wù)器發(fā)送航線計(jì)算請(qǐng)求），服務(wù)器從請(qǐng)求參數(shù)中，獲取車輛的位置、速度v、方向，然后根據(jù)位置和方向，配合服務(wù)器端存儲(chǔ)的全國(guó)地圖矢量數(shù)據(jù)，計(jì)算出車輛距離前方路口的距離d。

（2）如果d/v＞10（平均下發(fā)一條航線的時(shí)間在10 s以內(nèi)），則說(shuō)明在到達(dá)路口之前，預(yù)計(jì)至少還有10 s的時(shí)間，這樣就能在到達(dá)路口前將航線下發(fā)完畢，降低了重算的概率（重算是因車輛開(kāi)到了非航線的道路上引起的），此時(shí)不需要啟用多起點(diǎn)算法，而是直接以當(dāng)前車輛位置為起點(diǎn)，參數(shù)中的目的地為終點(diǎn)，計(jì)算航線并下發(fā)（通過(guò)同樣的2G/3G的無(wú)線數(shù)據(jù)鏈路下發(fā)，下同）到車輛的導(dǎo)航裝置。如果d/v≤10，則說(shuō)明到路口預(yù)計(jì)不到10 s，有可能在航線下發(fā)完畢后，車輛已越過(guò)路口，車輛不再位于航線上，則有必要繼續(xù)下一步操作。

（3）從矢量地圖中取得前方路口的綜合信息（包括該路口接下來(lái)通向的各條道路），并以該路口各個(gè)出發(fā)的路線為起點(diǎn)，參數(shù)中的目的地為終點(diǎn)，計(jì)算各個(gè)航線。將計(jì)算好的各個(gè)航線存儲(chǔ)在服務(wù)器的高速緩存中，以備在短時(shí)間內(nèi)使用。

（4）將各條航線的起始部分（5 km）下發(fā)到車輛導(dǎo)航裝置。

（5）車輛的導(dǎo)航裝置接收到下發(fā)的各條航線的起始部分后（此時(shí)可能已經(jīng)是10 s后，車輛已經(jīng)越過(guò)路口，也許在航線上，也許不在航線上），將車輛的當(dāng)前位置與多條航線的起始部分分別進(jìn)行匹配，試圖發(fā)現(xiàn)車輛在航線上的位置。如果沒(méi)有一條能匹配上，則說(shuō)明車輛已經(jīng)到達(dá)未預(yù)料的位置（這一般是通信不暢導(dǎo)致的下發(fā)過(guò)分延遲），此時(shí)就需要重新開(kāi)始計(jì)算，轉(zhuǎn)步驟（1）；否則（有至少一條航線能匹配上車輛）將繼續(xù)執(zhí)行下一步操作。

（6）車輛的導(dǎo)航裝置，對(duì)多條航線的匹配結(jié)果進(jìn)行優(yōu)選，評(píng)選標(biāo)準(zhǔn)是車輛所在的點(diǎn)距離航線的最短距離，選出其中匹配度最高的那條（即上述最短距離最短的航線），作為選定的航線，并剔除其他航線的初始部分。向服務(wù)器發(fā)出請(qǐng)求，索取選定航線的后續(xù)部分。服務(wù)器接收到該請(qǐng)求后，下發(fā)選定航線的后續(xù)部分，并刪除高速緩存中其他未被選定的航線。至此，路徑計(jì)算服務(wù)完成。

3.2 多終點(diǎn)路徑規(guī)劃的系統(tǒng)具體實(shí)現(xiàn)方法

本研究所描述的同名或同類型的興趣點(diǎn)為服務(wù)區(qū)、加油站、收費(fèi)口或停車場(chǎng)（如圖3所示），當(dāng)執(zhí)行搜索時(shí)，會(huì)得到完全相同的結(jié)果。

圖3 數(shù)字化后的興趣點(diǎn)例圖

服務(wù)區(qū)和收費(fèi)站都被數(shù)字化成一對(duì)同名的興趣點(diǎn)，分別位于高速公路的兩邊，以它們?yōu)槟康牡赜?jì)算航線時(shí)，常常因?yàn)檎`選對(duì)面的目的地而導(dǎo)致服務(wù)車輛繞路很遠(yuǎn)[5]。雖然高速兩邊的兩個(gè)服務(wù)區(qū)或收費(fèi)站的直線距離只有幾米或幾十米，但是從一個(gè)地點(diǎn)行駛到另一個(gè)地點(diǎn)，往往需要幾公里或幾十公里。本研究提供了一種導(dǎo)航系統(tǒng)多終點(diǎn)航線計(jì)算以避免類似繞路情況發(fā)生的技術(shù)解決方案，具體包括如下步驟。

（1）用戶通過(guò)移動(dòng)終端搜索并選擇一個(gè)興趣點(diǎn)作為目的地并發(fā)送到后臺(tái)服務(wù)器請(qǐng)求路徑規(guī)劃和導(dǎo)航服務(wù)，航線計(jì)算服務(wù)器接收到該路徑規(guī)劃請(qǐng)求后，以目的地為終點(diǎn)計(jì)算第一導(dǎo)航路徑[6]，并暫存等待后續(xù)導(dǎo)航路徑下發(fā)的指令。

（2）該服務(wù)器接著在所述目的地周圍的預(yù)定范圍內(nèi)搜索同名或同類型的興趣點(diǎn)；所述目的地周圍的預(yù)定范圍可由移動(dòng)終端在線設(shè)置后上傳給服務(wù)器，預(yù)定范圍一般設(shè)置為200～800 m，優(yōu)選為500 m；為了便于用戶靈活設(shè)置，所述目的地周圍的預(yù)定范圍參數(shù)可包含在路徑導(dǎo)航請(qǐng)求中，如果預(yù)定范圍值設(shè)置為0，則服務(wù)器不進(jìn)行同名或同類型的興趣點(diǎn)搜索，直接下發(fā)第一導(dǎo)航路徑給移動(dòng)終端。

（3）如果存在同名或同類型的興趣點(diǎn)，則服務(wù)器將搜索到的所有興趣點(diǎn)均作為終點(diǎn)進(jìn)行航線計(jì)算，得出多條起點(diǎn)相同，終點(diǎn)相類似的第二導(dǎo)航路徑，并暫存等待后續(xù)導(dǎo)航路徑下發(fā)的指令。

（4）服務(wù)器將多條第二導(dǎo)航路徑與第一導(dǎo)航路徑分別進(jìn)行比較，如果明顯存在更優(yōu)的第二導(dǎo)航路徑，比如存在預(yù)估距離或預(yù)估時(shí)間相比第一導(dǎo)航路徑的減少量達(dá)到預(yù)定閥值的第二導(dǎo)航路徑，則同時(shí)下發(fā)該第二導(dǎo)航路徑和第一導(dǎo)航路徑供移動(dòng)終端選擇（所述預(yù)估距離或預(yù)估時(shí)間減少量需要達(dá)到的預(yù)定閥值由移動(dòng)終端在線設(shè)置后上傳給服務(wù)器）。

服務(wù)器上可以預(yù)設(shè)默認(rèn)的預(yù)估距離或預(yù)估時(shí)間減少量需要達(dá)到預(yù)定閥值，比如如果存在預(yù)估距離較第一導(dǎo)航路徑的減少量超過(guò)500 m的第二導(dǎo)航路徑，則同時(shí)下發(fā)該第二導(dǎo)航路徑供移動(dòng)終端選擇；或者如果存在預(yù)估時(shí)間較第一導(dǎo)航路徑節(jié)省10%以上的第二導(dǎo)航路徑，則同時(shí)下發(fā)該第二導(dǎo)航路徑供移動(dòng)終端選擇。為了便于用戶選擇確認(rèn)，移動(dòng)終端最好顯示第一導(dǎo)航路徑與第二導(dǎo)航路徑差別并通過(guò)語(yǔ)音或界面彈出窗口提醒用戶：“您有可能選錯(cuò)了目的地，旁邊還有一個(gè)更好的選擇”，并顯示出兩條線路的具體差別。最后由用戶選擇接受最優(yōu)航線還是堅(jiān)持原航線，能有效避免因目的地選擇不當(dāng)造成的燃油和時(shí)間浪費(fèi)。

3.3 多終點(diǎn)路徑規(guī)劃的實(shí)施細(xì)節(jié)

圖5中，箭頭位置為車輛位置，曲線1為原來(lái)的第一導(dǎo)航路徑，曲線2為本選擇的最優(yōu)的一條第二導(dǎo)航路徑。

圖4 多終點(diǎn)路徑示意圖

圖5 多終點(diǎn)路徑導(dǎo)航第一導(dǎo)航路徑和第二導(dǎo)航路徑對(duì)比示意圖

用戶通過(guò)導(dǎo)航裝置搜索到一個(gè)興趣點(diǎn)，例如“A服務(wù)區(qū)”作為目的地，進(jìn)行航線計(jì)算時(shí)，導(dǎo)航系統(tǒng)會(huì)在后臺(tái)，在目的地周圍事先設(shè)定好的范圍內(nèi)（如500m）搜索同名或同類型的興趣點(diǎn)。如果沒(méi)有發(fā)現(xiàn)同名同類型的，則不做任何提醒，直接計(jì)算航線（起點(diǎn)是車輛的位置，或者是用戶選擇的特定位置，下同），本次導(dǎo)航結(jié)束。若查詢到同名同型的目的地，則判定為用戶的選擇存在錯(cuò)誤的可能，繼續(xù)后續(xù)的處理。系統(tǒng)將所有同名同型的目的地（也包括當(dāng)前用戶選中的），全部作為終點(diǎn)，起點(diǎn)不變，分別計(jì)算路線，并選出最優(yōu)航線（以預(yù)估行駛時(shí)間最少為判斷標(biāo)準(zhǔn)）。當(dāng)最優(yōu)航線比原航線不夠優(yōu)越時(shí)（比如時(shí)間節(jié)?。?0%），堅(jiān)持原航線（這樣處理的目的是避免非必要干擾用戶），本次導(dǎo)航結(jié)束。當(dāng)最優(yōu)航線比原航線優(yōu)越很多，比如時(shí)間節(jié)省≥10%，則繼續(xù)后續(xù)的處理。此時(shí)，直接通過(guò)語(yǔ)音或可視化界面彈出窗提示用戶，您可能選擇了錯(cuò)誤的目的地，并告知用戶具體差別。最后由用戶選擇接受最優(yōu)航線還是堅(jiān)持原航線。

4 結(jié)論

本研究提供了一種降低導(dǎo)航路徑規(guī)劃重復(fù)計(jì)算概率的方法，在可能引起重算的位置，系統(tǒng)獲取前方多個(gè)岔路，作為多個(gè)起點(diǎn)；把同名或同類型的興趣點(diǎn)全部作為終點(diǎn)進(jìn)行航線計(jì)算，利用服務(wù)器端強(qiáng)大的計(jì)算處理能力同時(shí)計(jì)算多個(gè)航線，并下發(fā)這些航線的起始和終點(diǎn)部分，然后挑選最匹配的一個(gè)，下發(fā)航線的剩余部分，避免了在網(wǎng)絡(luò)導(dǎo)航環(huán)境下，每次計(jì)算都要重新傳輸后再執(zhí)行計(jì)算，經(jīng)過(guò)這樣處理后不僅提高了導(dǎo)航效率，而且為用戶的出行節(jié)省了時(shí)間。