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

趙曉君

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

0 引言

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

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

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

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

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

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

圖1 業(yè)務流程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖4 多終點路徑示意圖

圖5 多終點路徑導航第一導航路徑和第二導航路徑對比示意圖

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

4 結論

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