[發明專利]一種啟發式搜索的高速路網約束尋路算法

有效

• 申請號: 201811415513.3
• 申請日: 2018-11-26
• 公開（公告）號: CN109540165B
• 公開（公告）日: 2022-07-01
• 發明（設計）人: 王剛;李劍;梅樂翔;劉旭;高薪;張鵬;李婧芳;劉晶;宋杰;王夢佳;賀文濤;趙晴
• 申請（專利權）人: 交通運輸部路網監測與應急處置中心
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 北京萬象新悅知識產權代理有限公司 11360
• 代理人: 黃鳳茹

本發明公布了一種基于啟發式搜索的高速路網約束尋路算法，以指定路網、指定路網中的道路起點、道路終點和駛經的收費路段集合為輸入數據，通過啟發式搜索，生成連接道路起點與道路終點之間的多條路徑，并從多條路徑中選擇一條與輸入的收費路段重合度最高的路徑，作為輸出路徑。采用本發明技術方案，通過可復用的路網結構與記錄的起點、終點和收費路段集合來進行路徑解析，能夠節省大量路徑儲存空間；可以得到該行駛記錄中用戶的行駛路徑是從起點到終點的第幾短路，也可以得到該路徑在集合中覆蓋到了幾個有效收費路段；且算法速度快，效率高，具有比較好的可調節性。

技術領域

本發明屬于智能交通技術領域，涉及路網尋路方法，尤其涉及一種啟發式的高速路網約束尋路算法，實現在給定路徑提示的約束下在高速路網上的兩點間的尋路。

背景技術

高速出行已經是我國的骨干交通方式之一，高速路網的運行狀況將與民生直接相關。為了使其長久平穩地運行，車輛在路網上的行駛信息需要被記錄在數據庫中。但每日路網上行駛的車次數目巨大，車輛的行駛路徑也很多變。將每條行駛路徑直接記錄在數據庫中是不現實的，它所需的存儲代價過大；另一方面，直接保存行駛路徑也要求車輛在經過交匯口時能被準確追蹤，這也是不現實的。

在一種對高速路網的建模方式中，結點通常指代收費站、交叉口等實體，而原子路段則是連接這些實體之間的基本單元。路網上的收費站可以被劃分成多個不相交的集合以便管理，并且每個集合都有一個唯一編號。類似的，路網上的每個結點和原子路段也都有一個唯一編號。在數據庫中記錄車輛駛過的不同收費站集合的編號來間接保存行駛路徑，是一種對原始的行駛路徑的壓縮。這種方式雖然會使行駛路徑有一定的精確性損失，但其在存儲和管理上帶來的好處是巨大的。不過，在后續利用以這種方式存儲的行駛記錄時，必須先從記錄中的各個收費站集合解析出車輛的行駛路徑，才能進行下一步的統計研究。

車輛行駛在原子路段上，因此上述以收費站集合為單元的表示方式與這個情景并不直接相容。以每個收費站為起點，以遇到其他收費站為截止條件，使用搜索算法對路網上的原子路段染色，可以取得一個收費站控制的原子路段集合。將一個收費站集合中所有收費站控制的原子路段集合取并集，可以實現從收費站集合到原子路段集合的轉換。因此在這里引入“收費路段”的概念，它與“收費站集合”一一對應，收費路段包含的原子路段列表，就是對應的收費站集合通過上述方式求得的原子路段集合。

現有技術中，一種用于從收費路段的集合解析出行駛路徑的算法需要對路網進行預處理，算法先枚舉路網上所有不同收費站的二元組，然后對每個二元組計算得到連接它們的最短的N條路徑，最后將這些路徑保存在某張表中該二元組對應的表項內。該算法解析路徑時，首先依據記錄中的起點和終點，在上述表中找到保存的N條路徑的表項，再遍歷這些路徑，以確定與記錄中收費路段的集合最為匹配的一條。

但是，上述方法存在很大的局限性。首先，當路網規模固定時，路徑解析的準確性將與預處理環節中保存的路徑數量N有關。N從小到大時，準確性增加的速度將會放緩，而保存的路徑總數也會增大，運行時處理每一條記錄需要比對的路徑數量也會隨之增大。其次，由于保存的路徑總數量與路網中收費站數量的平方呈正比關系，當路網規模增大、收費站數量增加時，存儲這些預處理路徑的代價將迅速增大。因此，這種解析路徑算法的局限性比較大。

啟發式搜索是一種利用提示條件來尋找目標最優解(或較優解)的有效算法。這種方法的應用范圍很大，算法使用的啟發函數可以任意配置，在使用上非常靈活。另外，啟發函數可以使算法在效率和精確性之間取得平衡，而在處理海量的高速公路行駛記錄時，效率和精確性都是重要的因素。啟發式搜索是一種重要的尋路算法，但目前在解析路徑的過程中還沒有使用啟發式搜索的高速路網約束尋路算法。

發明內容

為了克服上述現有技術的不足，本發明提供一種基于啟發式搜索的高速路網約束尋路算法，在真實路網的大小規模下可以高效地解析行駛路徑，能夠滿足實際應用需求。