[發明專利]一種基于元路徑擁塞模式挖掘的移動對象行駛時間預測方法及裝置

有效

• 申請號: 201910110832.1
• 申請日: 2019-02-12
• 公開（公告）號: CN109712402B
• 公開（公告）日: 2021-11-12
• 發明（設計）人: 韓京宇;王寧
• 申請（專利權）人: 南京郵電大學
• 主分類號: G08G1/01
• 分類號: G08G1/01;G06K9/62
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 王恒靜

1.一種基于元路徑擁塞模式挖掘的移動對象行駛時間預測方法，其特征在于，包括以下步驟：

(1)采集固定時間間隔的多個GPS數據作為訓練樣本，并將所述GPS數據通過地圖匹配算法匹配到路網上，得到與GPS數據對應的路徑軌跡；

(2)將匹配后的路徑軌跡分割成元路徑存儲到路徑字典中，挖掘每條元路徑各個時間的擁塞狀態，并根據不同元路徑間的關聯性，提取擁塞特征向量，其中，元路徑為所述路網上任意相鄰路口間的路徑，路徑字典為元路徑的集合；

所述步驟(2)具體包括：

步驟(21)、從歷史數據中提取各條元路徑的經過時間d(r)，并計算其累積分布函數，歷史數據是移動對象的歷史GPS軌跡，即移動對象在以前經過元路徑并將歷史GPS數據上傳；

根據累積分布函數計算元路徑上的擁塞狀態為[0,1]間的均勻分布，由此可以比較不同元路徑和不同行駛時間下的擁塞程度；

步驟(22)、元路徑r的鄰域集合NB(r)＝{o₁,…,o_s}，表示與元路徑r鄰接的s條元路徑，其中包含元路徑r，計算其動態擁塞狀態，將整個時間范圍離散成固定的時間間隔f_i，計算在各個時間間隔內，元路徑上觀測到的經過時間有些時間間隔f_i包含多個觀測值，用觀測值的期望表示，并計算擁塞狀態

步驟(23)、給定元路徑r和鄰域{o₁,…,o_s}，定義時間間隔f_i的特征向量M(r)_i，M(r)_i為在時間間隔f_i包含NB(r)的擁塞狀態的S維向量，即：

將計算的所有M(r)_i疊加到特征矩陣M(r)中；

設N為特征矩陣中是特征向量的數量，即離散的時間間隔的總量，矩陣M(r)表示NB(r)的動態擁塞狀態，有如下結構：

(3)將提取的擁塞特征向量加入特征矩陣中，并采用K-Means聚類算法填補所述特征矩陣中的空缺值，得到預測模型；

步驟(3)中，采用K-Means聚類算法填補所述特征矩陣中的空缺值，還包括采用時間相似性約束優化初始聚類結果，包括將相鄰固定時間間隔之間的相似性以及基于城市交通流量的周期相似性作為時間相似性約束；步驟(3)具體包括：

步驟(31)、將M(r)的行聚類為k個組，計算k個聚類中心c₁,…,c_k，然后找到距離M(r)中的行最近的聚類中心，使用聚類中心來初始化M(r)中的缺失值，采用K-Means方法找出最優的k值；

步驟(32)、通過在擁塞特征中引入時間關系來優化初始聚類結果；給定特征矩陣M(r)，關聯矩陣W表示M(r)中兩個時間間隔的時間相似性約束，矩陣中的每一項為下文中求得的w_i,j，找出k個聚類中心，減少與實際觀測值的差距，同時確定M(r)中的行與k個聚類中心中的軟分配；

步驟(33)、將相鄰固定時間間隔之間的相似性設為第一種類型的時間相似性約束，即在連續的時間間隔內，元路徑交通狀況不能從完全暢通狀態轉換到完全擁塞狀態，因此在第i個時間間隔和第j個時間間隔之間定義指數衰減函數：

t_i和t_j為時間間隔f_i和f_j的開始時間；

步驟(34)、第二種類型的時間相似性約束是基于城市交通流量的周期相似性，不考慮其是否處在工作日或周末，定義第i個時間間隔f_i和第j個時間間隔f_j內到達高峰段的用時之間的權重：

其中，h_i為時間間隔f_i內到達高峰段的用時；

步驟(35)、邊權重w_i,j由C_SOD和C_sm的線性組合計算得出：

w_i,j＝θC_sm(i,j)+(1-θ)C_SOD(i,j)，θ為系數；

步驟(36)、Q為N×k階聚類分配矩陣，Q的每行q_i是一個二元向量，如果時間間隔f_i被分配給聚類j，則q_i(j)＝1，否則為0，k個聚類中心為k×s階矩陣C的行向量，使用上述結果初始化Q和C，然后不斷迭代，通過達到下列最小化問題找出最優值：

其中，L為拉普拉斯矩陣，L＝D-W，常系數γ控制聚簇過程中時間一致性問題的權重，上式使用交替方向優化方法來求解；

(4)輸入需要預測行駛時間的路徑軌跡，實現行駛時間的預測。