一種基于GPS軌跡的路線規(guī)劃方法

姜波

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

關(guān)鍵詞：汽車導(dǎo)航；GPS軌跡；路線規(guī)劃；路線切入

技術(shù)領(lǐng)域

本文涉及導(dǎo)航技術(shù)領(lǐng)域，更為具體地，涉及一種利用軌跡點(diǎn)進(jìn)行導(dǎo)航路線規(guī)劃的方法。

背景技術(shù)

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

在電子地圖數(shù)據(jù)中，存儲(chǔ)著包含道路數(shù)據(jù)在內(nèi)的豐富的地圖信息。Link 是能夠和實(shí)際的道路相對應(yīng)的、電子地圖當(dāng)中的道路數(shù)據(jù)的基本構(gòu)成元素。Link中包括了道路編號、名稱、寬度、方向、交通規(guī)則等道路信息。

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

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

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

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

比上述方法更進(jìn)一步地，在現(xiàn)有的導(dǎo)航設(shè)備中，通常采用以下兩種方式來利用旅途軌跡記錄。

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

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

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

解決方案

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

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

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

本方案提供了一種利用路線軌跡點(diǎn)信息來進(jìn)行路線規(guī)劃的方法，包括：

1. 獲取路線軌跡點(diǎn)信息，所述路線軌跡點(diǎn)信息包括一系列軌跡點(diǎn)的坐標(biāo)；

2. 在電子地圖上按照所述一系列軌跡點(diǎn)的坐標(biāo)形成與該一系列軌跡點(diǎn)對應(yīng)的正向鏈路或反向鏈路；

3. 根據(jù)當(dāng)前位置和所述正向鏈路或所述反向鏈路確定從所述當(dāng)前位置切入所述正向鏈路或所述反向鏈路的最佳切入點(diǎn)；

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

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

6. 獲得從所述當(dāng)前位置到每一個(gè)所述備選切入點(diǎn)之間的路線，計(jì)算所述路線的權(quán)值，并將所述權(quán)值最小的路線所對應(yīng)的備選切入點(diǎn)作為所述正向鏈路或所述反向鏈路的最佳切入點(diǎn)，以及將所述權(quán)值最小的路線作為所述正向鏈路或所述反向鏈路的最佳切入路線。

具體實(shí)施方法

圖4示出了利用路線軌跡點(diǎn)信息進(jìn)行路線規(guī)劃的方法的流程圖。

如圖4所示，在步驟S410中，通過導(dǎo)航裝置獲取路線軌跡點(diǎn)信息，所述路線軌跡點(diǎn)信息包括一系列軌跡點(diǎn)的坐標(biāo)。所述路線軌跡點(diǎn)信息可以預(yù)先存儲(chǔ)在導(dǎo)航裝置中，也可以從網(wǎng)絡(luò)下載。

然后，在步驟S420中，在電子地圖上，按照所述一系列軌跡點(diǎn)的坐標(biāo)，形成與該一系列軌跡點(diǎn)對應(yīng)的正向鏈路或反向鏈路。關(guān)于正向鏈路的形成過程，參照圖5。

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

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

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

在形成正向鏈路或反向鏈路后，根據(jù)用戶的當(dāng)前位置和所述正向鏈路或反向鏈路，確定從當(dāng)前位置切入所述正向鏈路或所述反向鏈路的最佳切入點(diǎn)以及所述正向鏈路或所述反向鏈路的最佳切入路線。

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

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

例如，圖9所示，如果在預(yù)定范圍L0內(nèi)沒有找到N個(gè)以上的備選切入點(diǎn)，則需要將預(yù)定范圍擴(kuò)大到L0 + L 、L0 + 2L 等。然后，在擴(kuò)大后的查找范圍內(nèi)，查找備選切入點(diǎn)，直到找到N個(gè)以上的備選切入點(diǎn)為止。

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

在找出備選切入點(diǎn)后，在步驟S440，利用導(dǎo)航裝置獲得從所述當(dāng)前位置到每一個(gè)所述備選切入點(diǎn)之間的引導(dǎo)路線，計(jì)算所述路線的權(quán)值，并將權(quán)值最小的路線所對應(yīng)的備選切入點(diǎn)作為所述正向鏈路或反向鏈路的最佳切入點(diǎn)，以及將該權(quán)值最小的路線作為所述正向鏈路或反向鏈路的最佳切入路線。

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

實(shí)施效果

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

參考文獻(xiàn)

[1] 專利名稱：一種導(dǎo)航軌跡的記錄方法、裝置、設(shè)備以及導(dǎo)航方法；專利權(quán)人：凱立德欣技術(shù)(深圳)有限公司，專利申請?zhí)枺篊N200610157916.3

[2] 專利名稱：路書制作方法和裝置、路書制作與共享系統(tǒng)；專利權(quán)人：北京靈圖軟件技術(shù)有限公司；專利申請?zhí)朇N200910236038.8

[3] 孫棣華 張星霞 張志良，地圖匹配技術(shù)及其在智能交通系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用 2005.20