[發明專利]一種考慮路段相關性的時變隨機網絡動態路徑搜索方法

有效

• 申請號: 201710573641.X
• 申請日: 2017-07-14
• 公開（公告）號: CN107145991B
• 公開（公告）日: 2020-06-19
• 發明（設計）人: 陳鵬;童睿;王云鵬;魯光泉;鹿應榮
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/12
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種考慮路段相關性的時變隨機網絡動態路徑搜索方法，包括以下幾個步驟：

步驟一、采集路網狀態信息，并基于預處理后的數據，建立動態行程時間數據庫；

步驟二、出行者設定本次出行的始發地、目的地和行程時間可靠度；

步驟三、設置遺傳算法參數，并基于所產生的初始路徑集及構建的適應度函數計算候選路徑適應度；

其中，每一條候選路徑的適應度，將根據如下方法確定：計算該路段序列中每個路段行程時間平均值之和m，以及路段序列協方差矩陣各元素之和v；將m和v經過轉換后，得到高精度近似該路徑行程時間的對數正態分布的均值參數μ和方差參數δ，即得到該對數正態分布的累積分布曲線；再根據出行者設定的行程時間可靠度，求得該對數正態分布中該行程時間可靠度所對應的行程時間，該行程時間即是該候選路徑的適應度；

假設某條候選路徑包含n個路段，由這n個路段的行程時間數據計算得到的協方差矩陣如下所示：

其中，

Cov(i,j)：表示路段i和路段j行程時間的協方差；

σ_i：表示路段i行程時間的標準差；

ρ_i,j：表示路段i和路段j行程時間的相關系數；

該路段序列中每個路段行程時間平均值之和m由公式(2)計算：

TT_i：表示路段i的平均行程時間

該路段序列協方差矩陣各元素之和v由公式(3)計算：

高精度近似該路徑行程時間的對數正態分布的均值參數μ和方差參數δ分別由公式(4)、公式(5)計算：

步驟四、基于遺傳算法迭代搜索最優路徑，車輛按照迭代后所得到的當前最優路徑行駛；

步驟五、通過判斷車輛狀態及路網狀態，實現最優路徑的實時更新，以確保車輛持續在最優路徑內行駛，直至目的地。

2.根據權利要求1所述的一種考慮路段相關性的時變隨機網絡動態路徑搜索方法，所述的步驟一中，動態行程時間數據庫包含如下信息：時間、各路段編號、各路段的行程時間平均值、各路段的行程時間方差。

3.根據權利要求1所述的一種考慮路段相關性的時變隨機網絡動態路徑搜索方法，所述的步驟二中，行程時間可靠度如下定義：行程時間可靠度α是指出行者在當前位置能夠準時到達目的地的概率，范圍為0到1之間。

4.根據權利要求1所述的一種考慮路段相關性的時變隨機網絡動態路徑搜索方法，所述的步驟三中，遺傳算法的參數需要根據實際問題的不同來調整，比如在動態路徑搜索中，若當前節點距離目的地較近，可以設置較小的初始路徑集規模和最大迭代次數，否則設置較大的初始路徑集規模和最大迭代次數。

5.根據權利要求1所述的一種考慮路段相關性的時變隨機網絡動態路徑搜索方法，所述的步驟三中，初始路徑集需要在滿足無環路的前提下，盡量增大路徑集的多樣性，保證動態路徑搜索具有較快的收斂速度和較好的搜索結果。

6.根據權利要求1所述的一種考慮路段相關性的時變隨機網絡動態路徑搜索方法，所述的步驟五中，將在車輛即將到達當前路段終點時開始判斷是否重新搜索動態最優路線，確保車輛在到達當前路段終點前就已經規劃好下一步的路線，又不會因過早重新規劃路線而違背最新路網信息。