[發明專利]一種高斯過程路網下的最短路徑規劃方法

有效

• 申請號: 201911049289.5
• 申請日: 2019-10-31
• 公開（公告）號: CN110617834B
• 公開（公告）日: 2021-02-26
• 發明（設計）人: 郭宏亮;侯雪潔
• 申請（專利權）人: 電子科技大學
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 成都正華專利代理事務所(普通合伙) 51229
• 代理人: 陳選中

本發明公開了一種高斯過程路網下的最短路徑規劃方法，通過獲取與當前點相連的每條路徑的最短路徑的期望?方差或期望?標準差，獲取當前點與終點之間的最短的路徑，然后行進至下一個點，將下一個點作為當前點，重復若干次以上步驟，直至當前點為終點。本發明在簡單和復雜的交通網絡環境下都能夠快速選擇最短的路徑，同時通過不斷更新當前點，并重復判斷當前點與終點之間的最短路徑，實現了實時更新最短路徑。

技術領域

本發明屬于地圖中最短路徑規劃領域，具體涉及一種高斯過程路網下的最短路徑規劃方法。

背景技術

最短路徑算法是指找到一條連接起點與終點最短行使時間、距離或費用的路徑。在交通運輸領域，最短路徑算法在諸如車輛出行、交通分配和網絡設計等問題上有著廣泛的應用。在一定程度上，最短路徑問題是最基本的組成部分，為許多復雜而先進的交通研究奠定了基礎。最短路徑規劃問題分為標準最短路徑問題、隨機最短路徑問題和穩定最短路徑問題，前兩者應用廣泛，但均沒有考慮到行駛時間的變化性和風險問題。

發明內容

針對現有技術中的上述不足，本發明提供的一種高斯過程路網下的最短路徑規劃方法解決了最短路徑規劃時未考慮行駛時間變化的問題。

為了達到上述發明目的，本發明采用的技術方案為：一種高斯過程路網下的最短路徑規劃方法，包括以下步驟：

S1、采集地圖A，分別設置起點r、終點s、計算系數和計數器k＝0，從起點r至終點s行進，并將起點r作為當前點r_k；

S2、獲取與當前點r_k連接的n條路徑，設定地圖A中所有路徑的期望與方差為(μ,Σ)；

S3、根據起點r、終點s、計算系數、期望μ和方差Σ，模擬n條路徑的行駛時間，分別更新n種情況最短路徑的期望-方差或期望-標準差；

S4、重復m次步驟S3，選擇期望-方差平均值或期望-標準差平均值最小的最短路徑，行進至下一個點j_k；

S5、獲取當前實際行進時間t_k，更新路徑的期望μ和方差Σ，令當前點r_k為j_k點，同時令計數器k的計數值加一；

S6、判斷當前點r_k是否為終點s，若是則結束路徑規劃，否則返回步驟S3。

進一步地，所述步驟S2中所有路徑的期望μ服從高斯分布，所述高斯分布為：

所述期望μ為：

所述方差Σ為：

其中，X、X₁和X₂均表示路徑行駛時間的隨機分布，Σ₁₁、Σ₁₂、Σ₁₃和Σ₁₄均表示方差矩陣，μ₁和μ₂均表示期望矩陣。

進一步地，所述步驟S3包括以下分步驟：

S3.1、根據期望μ和方差Σ，隨機得到與當前點r_k連接的每條路徑的行進時間樣本值c；

S3.2、根據行進時間樣本值c，模擬在n條路徑上按相同速度行進時間c后到達的點o_n；

S3.3、分別令模擬期望μ_k＝μ和模擬方差Σ_k＝Σ，并根據行進時間樣本值c，更新模擬期望μ_k和模擬方差Σ_k；