[發明專利]一種基于馬爾科夫鏈的路徑行程時間確定方法及系統

有效

• 申請號: 202010012917.9
• 申請日: 2020-01-07
• 公開（公告）號: CN111209966B
• 公開（公告）日: 2023-09-26
• 發明（設計）人: 唐進君;胡瑾;劉芳
• 申請（專利權）人: 中南大學
• 主分類號: G06F18/20
• 分類號: G06F18/20;G06F18/2321;G08G1/01;G06N7/01
• 代理公司: 北京方圓嘉禾知識產權代理有限公司 11385
• 代理人: 馮靜

1.一種基于馬爾科夫鏈的路徑行程時間確定方法，其特征在于，所述方法包括：

確定各路段對應的行程時間；

以兩個相鄰路段的行程時間為一組，構成多個二維數組；

基于混合高斯模型對所有二維數組進行聚類，獲得路徑交通狀態；

基于馬爾科夫理論確定各種路徑交通狀態下的路徑狀態概率；

基于卷積理論確定各種路徑交通狀態下的路徑行程時間分布；

根據各種路徑交通狀態下的路徑狀態概率和路徑行程時間分布確定總路徑行程時間；

所述基于混合高斯模型對所有二維數組進行聚類，獲得路徑交通狀態，具體包括：

確定初始的聚類數，通過EM最大期望算法獲取混合高斯模型的相關參數，所述相關參數包括各分項混合高斯模型的均值與方差；在混合高斯模型中，每一個高斯模型代表一類路徑交通狀態；每一個高斯模型的均值與方差代表的是一類路徑交通狀態中行程時間的概率分布特征；

增加聚類數或路徑交通狀態數，重復確定初始的聚類數的步驟，根據聚類結果計算采用不同聚類數或路徑交通狀態數的誤差項平方和SSE；

SSE值的計算公式如下：

其中，K是聚類數，c_k是第k類的聚類中心，x是屬于類別k的相鄰路段行程時間組成的二維數組；

選擇最小SSE值對應的聚類數作為所述路徑交通狀態；

所述基于馬爾科夫理論確定各種路徑交通狀態下的路徑狀態概率，具體包括：

將兩相鄰路段聚類得到的路徑交通狀態按時間順序排列，等量分成初始狀態數據集和轉移狀態數據集；

根據所述初始狀態數據集和所述轉移狀態數據集構建馬爾可夫模型，獲得馬爾可夫鏈；

確定各所述馬爾可夫鏈的狀態轉移概率；具體公式為：

其中，為第n-1條馬爾可夫鏈從初始狀態數據轉移到初始狀態數據的狀態轉移概率，X^n-1(t)為時段t內第n-1條馬爾可夫鏈的狀態變量，為時段t內第n-1條馬爾可夫鏈的初始狀態數據，X^n-1(t+1)為時段t+1內第n-1條馬爾可夫鏈的狀態變量，為時段t+1內第n-1條馬爾可夫鏈的初始狀態數據，K_n-1為第n-1條馬爾可夫鏈劃分的交通狀態數；

確定兩條馬爾可夫鏈之間的連接概率；具體公式為：

其中，Xⁿ(t)為時段t內第n條馬爾可夫鏈的狀態變量，為時段t內第n條馬爾可夫鏈的初始狀態數據，Xⁿ⁺¹(t)為時段t內第n+1條馬爾可夫鏈的狀態變量，為時段t內第n+1條馬爾可夫鏈的初始狀態數據，為統計第n條馬爾可夫鏈初始狀態數據為且第n+1條馬爾可夫鏈初始狀態數據為的數量，K_n為第n條馬爾可夫鏈的狀態總數，1≤n≤N-1,N為馬爾可夫鏈的總數；

根據所述狀態轉移概率和所述連接概率確定各種路徑交通狀態下的路徑狀態概率；具體公式為：

其中，RP_q為第q種路徑交通狀態下的路徑狀態概率，1≤q≤Q,Q為路徑交通狀態的總數，為第n-1條馬爾可夫鏈的初始狀態數據的概率，為第n-1條馬爾可夫鏈從初始狀態數據轉移到初始狀態數據的狀態轉移概率，表示第n-2條馬爾可夫鏈與第n-1條馬爾可夫鏈之間的連接概率；

所述基于卷積理論確定各種路徑交通狀態下的路徑行程時間分布，具體包括：

確定各路段對應的路段行程時間分布；具體公式為：

其中，TTD_n-1為時段t內初始狀態數據為且時段t+1內初始狀態數據為條件下的第n-1個路段的行程時間數據所組成的行程時間分布；

基于卷積理論，根據各路段對應的路段行程時間分布確定各種路徑交通狀態下的路徑行程時間分布；具體公式為：

RTTD_q＝TTD₁*TTD₂*…*TTD_n；

其中，RTTD_q為第q種路徑交通狀態下的路徑行程時間分布，TTD_n為第n個路段對應的路段行程時間分布，*為卷積公式；

所述根據各種路徑交通狀態下的路徑狀態概率和路徑行程時間分布確定總路徑行程時間，具體公式為：

其中，RTTD為總路徑行程時間，RTTD_q為第q種路徑交通狀態下的路徑行程時間分布，RP_q為第q種路徑交通狀態下的路徑狀態概率，Q為路徑交通狀態的總種數。

2.一種基于馬爾科夫鏈的路徑行程時間確定系統，其特征在于，所述系統包括：

行程時間確定模塊，用于確定各路段對應的行程時間；

二維數組確定模塊，用于以兩個相鄰路段的行程時間為一組，構成多個二維數組；

路徑交通狀態確定模塊，用于基于混合高斯模型對所有二維數組進行聚類，獲得路徑交通狀態；

路徑狀態概率確定模塊，用于基于馬爾科夫理論確定各種路徑交通狀態下的路徑狀態概率；

路徑行程時間分布確定模塊，用于基于卷積理論確定各種路徑交通狀態下的路徑行程時間分布；

總路徑行程時間確定模塊，用于根據各種路徑交通狀態下的路徑狀態概率和路徑行程時間分布確定總路徑行程時間；

所述基于混合高斯模型對所有二維數組進行聚類，獲得路徑交通狀態，具體包括：

確定初始的聚類數，通過EM最大期望算法獲取混合高斯模型的相關參數，所述相關參數包括各分項混合高斯模型的均值與方差；在混合高斯模型中，每一個高斯模型代表一類路徑交通狀態；每一個高斯模型的均值與方差代表的是一類路徑交通狀態中行程時間的概率分布特征；

增加聚類數或路徑交通狀態數，重復確定初始的聚類數的步驟，根據聚類結果計算采用不同聚類數或路徑交通狀態數的誤差項平方和SSE；

SSE值的計算公式如下：

其中，K是聚類數，c_k是第k類的聚類中心，x是屬于類別k的相鄰路段行程時間組成的二維數組；

選擇最小SSE值對應的聚類數作為所述路徑交通狀態；

所述路徑狀態概率確定模塊，具體包括：

數據集確定單元，用于將兩相鄰路段聚類得到的路徑交通狀態按時間順序排列，等量分成初始狀態數據集和轉移狀態數據集；

馬爾可夫鏈確定單元，用于根據所述初始狀態數據集和所述轉移狀態數據集構建馬爾可夫模型，獲得馬爾可夫鏈；

狀態轉移概率確定單元，用于確定各所述馬爾可夫鏈的狀態轉移概率；具體公式為：

其中，為第n-1條馬爾可夫鏈從初始狀態數據轉移到初始狀態數據的狀態轉移概率，X^n-1(t)為時段t內第n-1條馬爾可夫鏈的狀態變量，為時段t內第n-1條馬爾可夫鏈的初始狀態數據，X^n-1(t+1)為時段t+1內第n-1條馬爾可夫鏈的狀態變量，為時段t+1內第n-1條馬爾可夫鏈的初始狀態數據，K_n-1為第n-1條馬爾可夫鏈劃分的交通狀態數；

連接概率確定單元，用于確定兩條馬爾可夫鏈之間的連接概率；具體公式為：

其中，Xⁿ(t)為時段t內第n條馬爾可夫鏈的狀態變量，為時段t內第n條馬爾可夫鏈的初始狀態數據，Xⁿ⁺¹(t)為時段t內第n+1條馬爾可夫鏈的狀態變量，為時段t內第n+1條馬爾可夫鏈的初始狀態數據，為統計第n條馬爾可夫鏈初始狀態數據為且第n+1條馬爾可夫鏈初始狀態數據為的數量，K_n為第n條馬爾可夫鏈的狀態總數，1≤n≤N-1,N為馬爾可夫鏈的總數；

路徑狀態概率確定單元，用于根據所述狀態轉移概率和所述連接概率確定各種路徑交通狀態下的路徑狀態概率；具體公式為：

其中，RP_q為第q種路徑交通狀態下的路徑狀態概率，1≤q≤Q,Q為路徑交通狀態的總數，為第n-1條馬爾可夫鏈的初始狀態數據的概率，為第n-1條馬爾可夫鏈從初始狀態數據轉移到初始狀態數據的狀態轉移概率，表示第n-2條馬爾可夫鏈與第n-1條馬爾可夫鏈之間的連接概率；

所述路徑行程時間分布確定模塊，具體包括：

路段行程時間分布確定單元，用于確定各路段對應的路段行程時間分布；具體公式為：

其中，TTD_n-1為時段t內初始狀態數據為且時段t+1內初始狀態數據為條件下的第n-1個路段的行程時間數據所組成的行程時間分布；

路徑行程時間分布確定單元，用于基于卷積理論，根據各路段對應的路段行程時間分布確定各種路徑交通狀態下的路徑行程時間分布；具體公式為：

RTTD_q＝TTD₁*TTD₂*…*TTD_n；

其中，RTTD_q為第q種路徑交通狀態下的路徑行程時間分布，TTD_n為第n個路段對應的路段行程時間分布，*為卷積公式；

所述根據各種路徑交通狀態下的路徑狀態概率和路徑行程時間分布確定總路徑行程時間，具體公式為：

其中，RTTD為總路徑行程時間，RTTD_q為第q種路徑交通狀態下的路徑行程時間分布，RP_q為第q種路徑交通狀態下的路徑狀態概率，Q為路徑交通狀態的總種數。