一種基于GPS軌跡的路線規劃方法

姜波

摘要：本發明提供了一種利用路線軌跡點信息來進行路線規劃的方法，包括：獲取包括一系列軌跡點的坐標的路線軌跡點信息；在電子地圖上按照該一系列軌跡點的坐標形成與該一系列軌跡點對應的正向鏈路或反向鏈路；在以當前位置為中心的預定范圍內，找到正向鏈路或反向鏈路與電子地圖中路網的交叉點，作為正向鏈路或反向鏈路的備選切入點，其中備選切入點的數日大于預定值；獲得從當前位置到每一個備選切入點的路線，計算所述路線的權值，并將權值最小的路線所對應的備選切入點作為最佳切入點，并將權值最小的路線作為最佳切入路線，將最佳切入路線與從最佳切入點到正向鏈路或所述反向鏈路的終點的正向鏈路或反向鏈路連接，形成正向或反向規劃路線。

關鍵詞：汽車導航；GPS軌跡；路線規劃；路線切入

技術領域

本文涉及導航技術領域，更為具體地，涉及一種利用軌跡點進行導航路線規劃的方法。

背景技術

隨著公共交通設施的不斷發展，駕駛者越來越需要導航設備來進行路線導航。通常情況下，導航設備都能夠記錄當前位置的GPS信息，其中包括當前位置的經緯度信息。例如，每隔一段時間或者距離，提取GPS信息當中的當前位置的經緯度信息并記錄下來，這種記錄點通常稱為軌跡點。一系列軌跡點的經緯度信息稱為路線軌跡。用戶可以利用導航設備把軌跡保存在軌跡文件中，用戶還可以記錄旅途感受等文字信息或在旅途中拍攝的照片、視頻、音頻等信息，然后通過工具，把這些信息（統稱為POI信息）附加到軌跡點上，形成包含軌跡信息、多媒體信息的旅途軌跡記錄。

在電子地圖數據中，存儲著包含道路數據在內的豐富的地圖信息。Link 是能夠和實際的道路相對應的、電子地圖當中的道路數據的基本構成元素。Link中包括了道路編號、名稱、寬度、方向、交通規則等道路信息。

把旅途軌跡記錄和電子地圖同時顯示，可以直觀地看出旅途上都經過了哪些地方。

用戶可以從網絡上下載這種旅途軌跡記錄，從而可以根據所下載的旅途軌跡記錄當中的軌跡點信息，從自己的當前位置開始，“重新走過”一段路途，游覽前人推薦的地點，曾經住宿的賓館，曾經吃過的飯店等，由此實現省心、省力又能得到比較好的服務和享受的目的。

目前，多數導航設備能夠顯示旅途軌跡記錄，用戶在駕車的時候可以一邊看旅途軌跡記錄，一邊對照自己的位置，判斷自己走到哪里。

圖1示出了在電子地圖上顯示的旅途軌跡記錄的一個示例。

比上述方法更進一步地，在現有的導航設備中，通常采用以下兩種方式來利用旅途軌跡記錄。

第一種方式是用戶進行手動操作，將旅途上的一些重要地點設定為一系列目的地，然后利用導航裝置規劃出一條經過這些目的地的經路，如圖2所示。然而，通常情況下，利用導航裝置規劃出來的經路與所下載的旅途軌跡記錄的軌跡所示的經路并不相同，從而導致用戶不能充分地利用所下載的旅途軌跡記錄中所記錄的信息。

第二種方式是通過導航裝置自動尋找軌跡上距離當前位置最近的點作為切入點，提示用戶切入點的位置，讓用戶決定利用旅途軌跡記錄當中軌跡的哪一段（是“切入點到旅途軌跡起點”，還是“切入點到旅途軌跡終點”) ，如圖3所示。

在確定出利用哪一段后，在導航裝置上顯示這段旅途軌跡記錄上的軌跡和信息，但是不能進行路線規劃，或者如第一種方式類似，將該段旅途軌跡記錄上的所有POI作為有序目的地，利用導航裝置進行路線規劃。在這種情況下，同樣存在利用導航裝置規劃出來的經路與所下載的旅途軌跡記錄的軌跡所示的經路并不相同，從而導致用戶不能充分地利用所下載的旅途軌跡記錄中所記錄的信息的問題。此外，用戶當前位置和切入點之間簡單連線可能不和實際道路對應。

解決方案

鑒于上述問題，本文提供了一種新的用于路線規劃的方法及裝置，其利用路線軌跡點信息和導航裝置中存儲的電子地圖，形成正向鏈路或反向鏈路，根據用戶的當前位置以及所述正向鏈路或反向鏈路，確定從當前位置切入所述正向鏈路或反向鏈路的最佳切入點以及所述正向鏈路或反向鏈路的最佳切入路線，將所述正向鏈路或反向鏈路的最佳切入路線與所述正向鏈路或反向鏈路的最佳切入點到所述正向鏈路或反向鏈路的終點的正向鏈路或反向鏈路連接，形成利用路線軌跡點信息的正向規劃路線或反向規劃路線。流程如圖4所示。

按照這種方式，可以使得用戶能夠以合適地方式，最大限度地利用旅途軌跡記錄當中的路線軌跡點信息，從用戶的當前位置開始，重新走過一段路程，從而最真實地再現旅途軌跡記錄所描述的路線。

這里要說明的是，旅途軌跡記錄當中的路線軌跡是有方向的，正向軌跡路線（也稱為正向鏈路）指的是與所述的旅途軌跡記錄當中的路線軌跡匹配并且方向一致的軌跡路線，而反向軌跡路線（也稱為反向鏈路）指的是與所述的旅途軌跡記錄當中的路線軌跡匹配并且方向相反的軌跡路線。

本方案提供了一種利用路線軌跡點信息來進行路線規劃的方法，包括：

1. 獲取路線軌跡點信息，所述路線軌跡點信息包括一系列軌跡點的坐標；

2. 在電子地圖上按照所述一系列軌跡點的坐標形成與該一系列軌跡點對應的正向鏈路或反向鏈路；

3. 根據當前位置和所述正向鏈路或所述反向鏈路確定從所述當前位置切入所述正向鏈路或所述反向鏈路的最佳切入點；

4. 將所述正向鏈路或所述反向鏈路的最佳切入路線與所述正向鏈路或所述反向鏈路的最佳切入點到所述正向鏈路或所述反響鏈路的終點的正向鏈路或反響鏈路連接，形成利用路線軌跡點信息的正向規劃路線或反向規劃路線；

5. 其中所述確定最佳切入點以及最佳切入路線的步驟還包括：在以當前位置為中心的預定范圍內，找到所述正向鏈路或所述反向鏈路與電子地圖中路網的交叉點，作為所述正向鏈路或所述反向鏈路的備選切入點，其中所述備選切入點的數目大于預定值；

6. 獲得從所述當前位置到每一個所述備選切入點之間的路線，計算所述路線的權值，并將所述權值最小的路線所對應的備選切入點作為所述正向鏈路或所述反向鏈路的最佳切入點，以及將所述權值最小的路線作為所述正向鏈路或所述反向鏈路的最佳切入路線。

具體實施方法

圖4示出了利用路線軌跡點信息進行路線規劃的方法的流程圖。

如圖4所示，在步驟S410中，通過導航裝置獲取路線軌跡點信息，所述路線軌跡點信息包括一系列軌跡點的坐標。所述路線軌跡點信息可以預先存儲在導航裝置中，也可以從網絡下載。

然后，在步驟S420中，在電子地圖上，按照所述一系列軌跡點的坐標，形成與該一系列軌跡點對應的正向鏈路或反向鏈路。關于正向鏈路的形成過程，參照圖5。

反向鏈路的形成過程，參照圖6。

在形成反向鏈路的過程中，如果軌跡匹配的路線是單行線，需要尋找“替代路線”，在近距離下有多段單行線的時候，合并處理：

如圖7所示①、②之間是單行線，③、④之間也是單行線，因為②、③之間的距離很短（例如<3km）,所以把兩部分合并處理，計算一條回避④到①之間的道路的路線，用這條路線替代原來的路線。

在形成正向鏈路或反向鏈路后，根據用戶的當前位置和所述正向鏈路或反向鏈路，確定從當前位置切入所述正向鏈路或所述反向鏈路的最佳切入點以及所述正向鏈路或所述反向鏈路的最佳切入路線。

換言之，如圖4所示，在形成正向鏈路或反向鏈路后，流程進行到步驟S430。在步驟S430，在以用戶的當前位置為中心的預定范圍內，找到所述正向鏈路或反向鏈路與電子地圖中路網的交叉點，作為所述正向鏈路或反向鏈路的備選切入點，其中所述備選切入點的數目要大于預定值。例如，在以當前位置為中心的預定范圍L（例如，以當前位置為中心的3km）內，找出所選擇出的軌跡路線與實際路網之間的交叉點，作為備選切入點，如圖8所示。

其中L是可變的距離參數。所述預定范圍L可以是以當前位置為中心的同心圓或同心矩形。通常，要求備選切入點的數目人于或等于N,其中N可以是任何整數值，例如5。當備選切入點的數目小于N時，可以擴大預定查找范圍L來重新進行查找，直到所找出的備選切入點的數目大于或等于N為止。

例如，圖9所示，如果在預定范圍L0內沒有找到N個以上的備選切入點，則需要將預定范圍擴大到L0 + L 、L0 + 2L 等。然后，在擴大后的查找范圍內，查找備選切入點，直到找到N個以上的備選切入點為止。

這里要說明的是，如果整條軌跡路線都在查找范圍內，所找到的備選切入點的數日仍然小于N，則停止查找，并將所找到的交叉點作為備選切入點。然后，流程進行到步驟S440。

在找出備選切入點后，在步驟S440，利用導航裝置獲得從所述當前位置到每一個所述備選切入點之間的引導路線，計算所述路線的權值，并將權值最小的路線所對應的備選切入點作為所述正向鏈路或反向鏈路的最佳切入點，以及將該權值最小的路線作為所述正向鏈路或反向鏈路的最佳切入路線。

在確定出最佳切入點以及最佳切入路線后，流程進行到步驟S450。在步驟S450中，將所述正向鏈路或反向鏈路的最佳切入路線與所述正向鏈路或反向鏈路的最佳切入點到所述正向鏈路或反向鏈路的終點的正向鏈路或反向鏈路連接，形成利用路線軌跡點信息的正向規劃路線或反向規劃路線。

實施效果

通過以上結合附圖對實施方法的詳細描述，不難看出：利用路線軌跡點信息和導航裝置中存儲的電子地圖，形成正向鏈路或反向鏈路，根據用戶的當前位置以及所述正向鏈路或反向鏈路，確定從當前位置切入所述正向鏈路或反向鏈路的最佳切入點以及所述正向鏈路或反向鏈路的最佳切入路線，將所述正向鏈路或反向鏈路的最佳切入路線與所述正向鏈路或反向鏈路的最佳切入點到所述正向鏈路或反向鏈路的終點的正向鏈路或反向鏈路連接，形成利用路線軌跡點信息的正向規劃路線或反向規劃路線。按照這種方式，可以使得用戶能夠以合適地方式，最大限度地利用旅途軌跡記錄當中的路線軌跡點信息，從用戶的當前位置開始，重新走過一段路程，從而最真實地再現旅途軌跡記錄所描述的路線。

參考文獻

[1] 專利名稱：一種導航軌跡的記錄方法、裝置、設備以及導航方法；專利權人：凱立德欣技術(深圳)有限公司，專利申請號：CN200610157916.3

[2] 專利名稱：路書制作方法和裝置、路書制作與共享系統；專利權人：北京靈圖軟件技術有限公司；專利申請號CN200910236038.8

[3] 孫棣華 張星霞 張志良，地圖匹配技術及其在智能交通系統中的應用[J].計算機工程與應用 2005.20