地理信息系統中多起點和多終點路徑規劃的實現方法

趙曉君

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

0 引言

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

1 系統設計來源

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

2 系統設計思想（Design Idea）

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

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

圖1 業務流程

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

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

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

3 系統實現

3.1 多起點路徑規劃的系統具體實現方法

結合系統狀態圖（如圖2所示）多起點路徑規劃的系統具體實現方法描述如下。

圖2 系統狀態圖

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

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

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

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

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

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

3.2 多終點路徑規劃的系統具體實現方法

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

圖3 數字化后的興趣點例圖

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

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

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

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

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

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

3.3 多終點路徑規劃的實施細節

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

圖4 多終點路徑示意圖

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

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

4 結論

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