路徑規劃方法和系統的製作方法

2023-06-15 01:29:56

專利名稱：路徑規劃方法和系統的製作方法
技術領域：
本發明涉及交通領域，具體而言，涉及一種路徑規劃方法和系統。
背景技術：
在道路網絡(簡稱路網)日益發達的今天，用戶的出行已經不再容易。路徑規劃是幫助駕單車輛駛員在旅行前規划行駛路線的過程。它要解決的主要問 題是在給定的道路網中尋找從出發點到目的地之間的最優路徑。現有技術提供了一種基於鄰接矩陣的Dijkstra方法，用以解決上述路徑規劃中 的具有最小代價的最短路徑問題。在實現本發明過程中，發明人發現現有技術中採用鄰接矩陣的Dijkstra方法來 存儲交通網絡拓撲數據，雖然可以在0(1)時間內完成(i ；j)是否是一條網絡邊的查詢，但 對最短路徑規劃最關鍵的關聯結點的查詢，其複雜度均為0(n)，導致查詢的複雜度較高。

發明內容
本發明旨在提供一種路徑規劃方法和系統，能夠解決現有技術中採用鄰接矩陣的 Dijkstra方法來存儲交通網絡拓撲數據，雖然可以在0(1)時間內完成(i ； j)是否是一條 網絡邊的查詢，但對最短路徑規劃最關鍵的關聯結點的查詢，其複雜度均為0(n)，導致查詢 的複雜度較高的問題。在本發明的實施例中，提供了一種路徑規劃方法，包括以下步驟將道路映射成交通網絡拓撲圖中的結點，將道路的端點映射成交通網絡拓撲圖中 的弧段；從原結點和目標結點雙向搜索得到多個當前結點；依次計算多個當前結點到原結點和目標結點的代價，得到從原結點到目標結點的 代價最小的當前結點；根據代價最小的當前結點和原結點以及目標結點，得到從原結點到目標結點的路 線方案。優選地，在上述路徑規劃方法中，從原結點和目標結點雙向搜索得到多個當前結 點具體包括將在前向搜索和後向搜索中均搜索到的結點作為當前結點。優選地，在上述路徑規劃方法中，代價為費用代價或距離代價或時間代價。優選地，在上述路徑規劃方法中，依次計算多個當前結點到原結點和目標結點的 費用代價，得到從原結點到目標結點的費用代價最小的當前結點具體包括計算從原結點到當前結點的費用g(n)，g(n) = g (n-1) +D (η) X R (η) +T (η)，其中，g(n-l)為到達道路結點n-1所經過的弧段的實際費用值，D(η)為從道路結 點n-1到達結點η的導航路徑的長度，R(n)為從道路結點n_l到達結點η的路徑的屬性取
4值因子，R(n) = 360/m_rtCost[layerType][distType][methodType][roadClass]其中，360 為經驗值，layerType、distType、methodType 和 roadClass 分別是結 點η的道路層類型、道路長度類型、駕乘選項和道路功能等級屬性，T(η)為從上一道路 結點η-1進入結點η時經過的導航路徑的轉向耗費，T(n) = m_turnCost[methodType] [turnDirection]，其中methodType和turnDirection分別是結點η的駕乘選項和道路轉 向屬性；計算從結點η到目標結點的費用h' (η)h' (η) = μ X0(n) XR' (η)，其中，μ為耗費係數，其取值與原結點到目標結點的歐氏距離的平方相關; 0(η)為結點η到目標結點的歐氏距離；R' (η)為道路結點η的後續費用估算的比例因 子:R' (η) = 360/m_toCost[layerType] [distType] [methodType]，其中 360 是經驗值， layerType,distType,methodType分別是從道路結點n_l到達結點η的導航路徑的道路層 類型、道路長度類型和駕乘選項屬性，計算原結點到目標結點的總費用f(n) = g(n)+h' (η)；將根據多個當前結點計算得到的多個總費用進行比較，得到路徑總費用最小的當 前結點。優選地，在上述路徑規劃方法中，當原結點到目標結點的歐氏距離的平方小於 3000時，μ取值為0. 2。在本發明的實施例中，還提供了一種路徑規劃系統，包括用戶終端，用於接受用戶對出發地點和目標地點的輸入；中間層模塊，用於實時裝載導航數據；計算模塊，用於根據出發地點和目標地點以及導航數據，雙向搜索計算得出從出 發地點到目標地點代價最小的路線方案。在上述實施例中，通過採用雙向搜索，即不僅進行從起始結點到目標結點的前向 搜索，而且進行從目標結點到起始結點的後向搜索，提高了對當前結點的搜索效率，降低了 路徑規劃中搜索的複雜度，克服了現有技術中採用鄰接矩陣的Di jkstra方法來存儲交通 網絡拓撲數據，雖然可以在0(1)時間內完成(i ；j)是否是一條網絡邊的查詢，但對最短路 徑規劃最關鍵的關聯結點的查詢，其複雜度均為0(n)，導致查詢的複雜度較高的問題。


此處所說明的附圖用來提供對本發明的進一步理解，構成本申請的一部分，本發 明的示意性實施例及其說明用於解釋本發明，並不構成對本發明的不當限定。在附圖中圖1示出了根據本發明一個實施例的路徑規劃方法流程圖；圖2示出了根據本發明一個實施例的路徑規劃系統模塊圖；圖3示出了根據本發明一個實施例的在線導航服務平臺運行過程示意圖；圖4示出了根據本發明一個實施例的複合結點示意圖；圖5示出了根據本發明一個實施例的二次網格示意5
圖6示出了根據本發明一個實施例的路徑連接示意圖；圖7示出了根據本發明一個實施例的ID號跨越網格示意圖；圖8示出了根據本發明一個實施例的複合路口子結點示意圖；圖9示出了根據本發明一個實施例的結點形態示意圖。
具體實施例方式下面將參考附圖並結合實施例，來詳細說明本發明。圖1示出了根據本發明一個實施例的路徑規劃方法流程圖，包括以下步驟S102，將道路映射成交通網絡拓撲圖中的結點，將道路的端點映射成交通網絡拓 撲圖中的弧段；S104，從原結點和目標結點雙向搜索得到多個當前結點；S106，依次計算多個當前結點到原結點和目標結點的代價，得到從原結點到目標 結點的代價最小的當前結點；S108，根據代價最小的當前結點和原結點以及目標結點，得到從原結點到目標結 點的路線方案。在本實施例中，通過採用雙向搜索，即不僅進行從起始結點到目標結點的前向搜 索，而且進行從目標結點到起始結點的後向搜索，提高了對當前結點的搜索效率，降低了路 徑規劃中搜索的複雜度，克服了現有技術中採用鄰接矩陣的Di jkstra方法來存儲交通網 絡拓撲數據，雖然可以在0(1)時間內完成(i ；j)是否是一條網絡邊的查詢，但對最短路徑 規劃最關鍵的關聯結點的查詢，其複雜度均為0(n)，導致查詢的複雜度較高的問題。同時，通過將道路映射成交通網絡拓撲圖中的結點，將道路的端點映射成交通網 絡拓撲圖中的弧段，在保證邏輯正確性的情況下極大的簡化了距離因子值的計算，生成的 最佳路徑結果集直接就是可操作的導航弧段序列，而不是現有方法中生成的結點序列，因 此無須再次由結點序列進行遍歷和比對製作導航弧段序列，提高了路徑規劃的效率。在本實施例中，對導航路網進行矩形分幅，矩形分幅指按矩形地理網格範圍(兩 條經線和兩條緯線圍成的區域)為單位組織一幅地圖的數據集。空間尺度為城市圖(製圖 比例尺1 5000)時，有兩種分幅規格，一個是一次網格的尺寸，一個是二次網格的尺寸，一 次網格的大小是經差1° X緯差40』，二次網格則是在一次網格的基礎上，再劃分為八行八 列，共64個二次網格，每個二次網格的大小是經差7. 5』 X緯差5』(相當於國家1 2.5 萬基礎地形圖的分幅規格)。優選地，在上述路徑規劃方法中，從原結點和目標結點雙向搜索得到多個當前結 點具體包括將在前向搜索和後向搜索中均搜索到的結點作為當前結點。對於前向後向搜索切換標準，可以只保持一次前向後向搜索的交替操作。搜索停 止的條件，我們作如下限制搜索到這樣一個結點iNodemin，它在前向後向搜索過程中均被標為scanned結 點；gl iNodemin+g2iNodemin確實是最小的，其中gl iNodemin表示從原結點到iNodemin 的最小費用，g2iNodemin表示從目標結點到iNodemin的最小費用。如果只滿足第一個條件就停止搜索，找到的最優路徑不一定是最優的。只有加上第二個條件，才能確保找到最優的路徑，但付出的代價是要多搜索幾十個結點。使用雙向搜索，能有效地減少在搜索的過程中生成的開表和閉表的大小，降低在 兩表中的搜索用時，且配合估價費用函數的引入，可以更快地完成路徑規劃的搜索。優選地，在上述路徑規劃方法中，代價為費用代價或距離代價或時間代價。優選地，在上述路徑規劃方法中，依次計算多個當前結點到原結點和目標結點的 費用代價，得到從原結點到目標結點的費用代價最小的當前結點具體包括計算從原結點到當前結點的費用g(n)，
g(n) = g (n-1) +D (η) X R (η) +T (η)，其中，g(n-l)為到達道路結點n-1所經過的弧段的實際費用值，D (η)為從道路結 點n-1到達結點η的路徑的長度，R(n)為從道路結點n_l到達結點η的導航路線的屬性取 值因子；R(n) = 360/m_rtCost[layerType][distType][methodType][roadClass]其中，360 為經驗值，layerType、distType、methodType 和 roadClass 分別是結 點η的道路層類型、道路長度類型、駕乘選項和道路功能等級屬性，T(η)為從上一道路 結點n-1進入結點η時經過的導航路徑的轉向耗費，T(n) = m_turnCost[methodType] [turnDirection]，其中methodType和turnDirection分別是從道路結點n_l到達結點η 的導航路線的駕乘選項和道路轉向屬性；計算從結點η到目標結點的費用h' (η)h' (η) = μ X0(n) XR' (η)，其中，μ為耗費係數，其取值與原結點到目標結點的歐氏距離的平方相關；0(η) 為結點η到目標結點的歐氏距離；R' (η)為道路結點η 的後續費用估算的比例因子 R 『 (n) = 360/m_toCost [layerType] [distType] [methodType],其中 360 是經驗值， layerType,distType,methodType分別是從道路結點n_l到達結點η的導航路線的道路層 類型、道路長度類型和駕乘選項屬性，計算原結點到目標結點的總費用f (n) = g (η) +h 『 (η)；將根據多個當前結點計算得到的多個總費用進行比較，得到總費用最小的當前結
點ο圖2示出了根據本發明一個實施例的路徑規劃系統模塊圖，包括用戶終端10，用於接受用戶對出發地點和目標地點的輸入；中間層模塊20，用於預先裝載導航數據；計算模塊30，用於根據出發地點和目標地點以及導航數據，雙向搜索計算得出從 出發地點到目標地點代價最小的路線方案。在上述實施例中，通過採用雙向搜索，即不僅進行從起始結點到目標結點的前向 搜索，而且進行從目標結點到起始結點的後向搜索，提高了對當前結點的搜索效率，降低了 路徑規劃中搜索的複雜度，克服了現有技術中採用鄰接矩陣的Di jkstra方法來存儲交通 網絡拓撲數據，雖然可以在0(1)時間內完成(i ；j)是否是一條網絡邊的查詢，但對最短路 徑規劃最關鍵的關聯結點的查詢，其複雜度均為0(n)，導致查詢的複雜度較高的問題。為了可以在任何平臺上通過http輕鬆訪問導航服務，在本實施例中選擇在Windows 2003上搭建一個Web服務。Web服務是利用SOAP (簡單對象訪問協議，Simple Object Access Protocol)在HTTP上直行遠程調用的一種新方法。用戶可以在網上，通過 導航伺服器提供的web服務通訊來取得導航方案。圖3示出了根據本發明一個實施例的在線導航服務平臺運行過程，其過程如下導航服務啟動首先要做的是裝載導航數據；當數據裝載完成後，服務將開始等待 接入請求；用戶通過網站上的自駕導航頁面，選定需進行路徑規劃的起始點和目的點，並向 Web伺服器發送查詢請求；Web伺服器接收到用戶的請求，取得起始點和目的點的經緯度坐 標，並生成一個Web服務實例來與導航伺服器進行通訊，向其傳入相應的參數，發起路徑規 劃請求；導航伺服器接收到請求，調用導航路徑規划算法，生成相應的規劃方案，並將方案 的關鍵數據返回給Web伺服器；Web伺服器接收到導航服務的返回，取得其處理狀態，若規 劃成功，則經過頁面處理，以方便用戶理解的方式返回給用戶；否則，提示規劃出錯信息。在本發明的實施例中，導航數據是這樣生成的矩形分幅指按矩形地理網格範圍(兩條經線和兩條緯線圍成的區域)為單位組織 一幅地圖的數據集。空間尺度為城市圖(製圖比例尺1 5000)時，有兩種分幅規格，一個 是一次網格的尺寸，一個是二次網格的尺寸，一次網格的大小是經差1° X緯差40』，二次 網格則是在一次網格的基礎上，再劃分為八行八列，共64個二次網格，每個二次網格的大 小是經差7. 5』 X緯差5』(相當於國家1 2. 5萬基礎地形圖的分幅規格)。我們所使用 的導航路網數據，都是根據這種矩形分幅來進行網格劃分的。導航道路路網線是導航地圖的核心部分，詳細描述了道路行車路線和路口交叉點 的連通關係，是導航路徑規劃的依據，通常簡稱為導航線，等價於⑶F (Geographical Data File)標準中的Roads andFerries專題的Road Element線狀要素，在這裡，我們稱一條導 航線為一條link。導航道路路網組成行車的道路網絡，因此跨水域的由渡口連接的輪渡線 (水道線)也包含在內。其主要數據結構如表1所示表 1
8
權利要求
一種路徑規劃方法，其特徵在於，包括以下步驟將道路映射成交通網絡拓撲圖中的結點，將所述道路的端點映射成所述交通網絡拓撲圖中的弧段；從原結點和目標結點雙向搜索得到多個當前結點；依次計算多個所述當前結點到所述原結點和所述目標結點的代價，得到從所述原結點到所述目標結點的代價最小的所述當前結點；根據所述代價最小的所述當前結點和所述原結點以及所述目標結點，得到從所述原結點到所述目標結點的路線方案。
2.根據權利要求1所述的路徑規劃方法，其特徵在於，從原結點和目標結點雙向搜索 得到多個當前結點具體包括將在前向搜索和後向搜索中均搜索到的結點作為當前結點。
3.根據權利要求1所述的路徑規劃方法，其特徵在於，所述代價為費用代價或距離代 價或時間代價。
4.根據權利要求3所述的路徑規劃方法，其特徵在於，依次計算多個所述當前結點到 所述原結點和所述目標結點的費用代價，得到從所述原結點到所述目標結點的費用代價最 小的所述當前結點具體包括計算從所述原結點到所述當前結點的費用g(n)， g(n) = g(n-l)+D(n) XR(η)+T(η),其中，g(n-l)為到達道路結點η-1所經過的弧段的實際費用值，D (η)為從道路結點η_1 到達結點η的路徑的長度，R(n)為從道路結點η-1到達結點η的路徑的屬性取值因子，R(n) =360/m_rtCost[layerType][distType][methodType][roadClass]其中，360 為經驗值，layerType、distType、methodType 和 roadClass 分別是所述結 點η的道路層類型、道路長度類型、駕乘選項和道路功能等級屬性，T(η)為從上一道路結 點η-1進入所述結點η時經過的導航路徑的轉向耗費，T(n) = m_turnCost [methodType] [turnDirection]，其中methodType和turnDirection分別是所述結點η的駕乘選項和道 路轉向屬性；計算從所述結點η到所述目標結點的費用h' (η) h' (η) = μ XO(η) XR' (η)，其中，μ為耗費係數，其取值與所述原結點到所述目標結點的歐氏距離的平方相關; 0(η)為所述結點η到所述目標結點的歐氏距離；R' (η)為所述道路結點η的後續費用估算 的比例因子:R' (η) = 360/m_toCost [layerType] [distType] [methodType]，其中 360 是 經驗值，layerType、distType、methodType分別是從道路結點n_l到達所述結點η的導航 路線的道路層類型、道路長度類型和駕乘選項屬性， 計算所述原結點到所述目標結點的總費用 f' (n) = g(n)+h' (η)；將根據多個所述當前結點計算得到的多個所述總費用進行比較，得到所述總費用最小 的所述當前結點。
5.一種路徑規劃系統，其特徵在於，包括用戶終端，用於接受用戶對出發地點和目標地點的輸入；中間層模塊，用於預先裝載導航數據；計算模塊，用於根據所述出發地點和所述目標地點以及所述導航數據，雙向搜索計算 得出從所述出發地點到所述目標地點代價最小的路線方案。
全文摘要
本發明提供了一種路徑規劃方法和系統，其中，方法包括以下步驟將道路映射成交通網絡拓撲圖中的結點，將道路的端點映射成交通網絡拓撲圖中的弧段；從原結點和目標結點雙向搜索得到多個當前結點；依次計算多個當前結點到原結點和目標結點的代價，得到從原結點到目標結點的代價最小的當前結點；根據代價最小的當前結點和原結點以及目標結點，得到從原結點到目標結點的路線方案。本發明克服了現有技術中採用鄰接矩陣的Dijkstra方法來存儲交通網絡拓撲數據，雖然可以在O(1)時間內完成(i；j)是否是一條網絡邊的查詢，但對最短路徑規劃最關鍵的關聯結點的查詢，其複雜度均為O(n)，導致查詢的複雜度較高的問題。
文檔編號G01C21/34GK101944095SQ20091015893
公開日2011年1月12日 申請日期2009年7月8日 優先權日2009年7月8日
發明者柳宗偉 申請人:廣東融訊信息科技有限公司