趙曉君

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

0 引言

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

1 系統(tǒng)設(shè)計來源

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 多終點路徑規(guī)劃的實施細節(jié)

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

圖4 多終點路徑示意圖

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

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

4 結(jié)論

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