[發明專利]路徑規劃方法和裝置

有效

• 申請號: 201610131648.1
• 申請日: 2016-03-08
• 公開（公告）號: CN107167152B
• 公開（公告）日: 2019-12-03
• 發明（設計）人: 郭建山
• 申請（專利權）人: 高德信息技術有限公司
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 11690 北京領科知識產權代理事務所(特殊普通合伙)
• 代理人: 張丹<國際申請>=<國際公布>=<進入國

本發明提供了一種路徑規劃方法和裝置，其中的方法主要包括：獲取起點和終點；從所述起點和終點分別進行最短路徑計算，并在最短路徑計算過程中，執行以下獲取步驟：當判斷從起點進行最短路徑計算得到的第一最短路徑中的路段一與從終點進行最短路徑計算得到的第二最短路徑中的路段二具有相同道路標識時，從道路數據庫中獲取連通所述路段一和路段二的中間路段，并將該中間路段連接為中間路徑，其中所述中間路段的道路標識與所述路段一和路段二的道路標識相同；根據所述第一最短路徑、中間路徑和第二最短路徑，生成從所述起點到所述終點的路徑。本發明提供的技術方案能夠在較大程度上減小最短路徑的計算量，有效提高了路徑規劃效率。

技術領域

本發明涉及電子地圖技術，尤其涉及一種路徑規劃方法及路徑規劃裝置。

背景技術

在電子地圖技術中，經常會存在規劃起點和終點之間的路徑的需求。

目前，使用較為廣泛的一種路徑規劃方法的實現原理為：從起點和終點同時向外進行擴展計算，當基于起點計算出的最短路徑和基于終點計算出的最短路徑中包含有道路屬性完全相同的同一路段時，不再執行最短路徑的計算操作，合并基于起點計算出的最短路徑和基于終點計算出的最短路徑即可確定出起點和終點之間的路徑。

發明人在實現本發明過程中發現，在路網數據采集過程中，一條實際道路往往會由于紅綠燈、收費站、交叉路口、車道數量以及出入口等多種因素而被劃分為具有不同道路屬性的多個路段，如北京的二環路會由于車道數量以及出入口等多種因素而被劃分為數十條甚至上百個路段；由于現有的確定起點和終點之間的路徑過程是在基于起點計算出的最短路徑和基于終點計算出的最短路徑都包含具有完全相同道路屬性的同一路段時，才會停止最短路徑的計算過程，因此，現有的路徑規劃方法的計算量必然會包括：對尋找到的最短路徑所包含的各路段的計算量以及對尋找到的路徑所包含的各路段的周圍路段的計算量。雖然路徑規劃的算法在被不斷的優化，但是，現有的路徑規劃的實現原理導致其路徑規劃的計算量仍然較大，路徑規劃的效率有待于進一步提高。

發明內容

本發明的目的是提供一種路徑規劃方法和裝置。

根據本發明的一個方面，提供一種路徑規劃方法，其中，該方法主要包括以下步驟：獲取起點和終點；從所述起點和所述終點分別進行最短路徑計算，并在最短路徑計算過程中，執行以下獲取步驟：當判斷從起點進行最短路徑計算得到的第一最短路徑中的路段一與從終點進行最短路徑計算得到的第二最短路徑中的路段二具有相同道路標識時，從道路數據庫中獲取連通所述路段一和路段二的中間路段，并將該中間路段連接為中間路徑，其中所述中間路段的道路標識與所述路段一和路段二的道路標識相同；根據所述第一最短路徑、中間路徑和第二最短路徑，生成從所述起點到所述終點的路徑。

根據本發明的另一個方面，還提供一種路徑規劃裝置，其中，該裝置包括：獲取模塊，用于獲取起點和終點；計算模塊，用于從所述起點和終點分別進行最短路徑計算，并在最短路徑計算過程中，執行以下獲取步驟：當判斷從起點進行最短路徑計算得到的第一最短路徑中的路段一與從終點進行最短路徑計算得到的第二最短路徑中的路段二具有相同道路標識時，從道路數據庫中獲取連通所述路段一和路段二的中間路段，并將該中間路段連接為中間路徑，其中所述中間路段的道路標識與所述路段一和路段二的道路標識相同；路徑生成模塊，用于根據所述第一最短路徑、中間路徑以及第二最短路徑，生成從所述起點到所述終點的路徑。