Road congestion discovery method based on higher-order Markov model

Abstract

The invention discloses a road congestion discovery method based on a higher-order Markov model. The method includes two steps: probability transfer matrix calculation and congestion state prediction;during probability transfer matrix calculation, obtaining appropriate road section state classification by employing affinity propagation clustering, and then calculating a transfer probability matrix of the road section state in different time intervals; and during congestion state prediction, predicting the congestion state with the combination of the transfer probability matrix according to the state of road section at which a moving object is located and adjacent road sections. According to the method, the transfer probability matrix is calculated through the affinity propagation clustering algorithm in advance and then stored in a database, when a model is required for prediction, the probability matrix is directly read from the database, the transfer probability matrix is calculatedin advance and stored, the matrix can be directly inquired during prediction, the speed of real-time prediction is greatly increased, and the classification accuracy can be improved by employing affinity propagation clustering so that the correctness of the probability transfer matrix is improved.

Description

technical field [0001] The invention relates to the field of information technology, in particular to a method for discovering road congestion based on a high-order Markov model on an urban road network. Background technique [0002] With the continuous development of urban road network data collection technology, the real-time and accuracy of data are continuously improved, which poses a new challenge to how to make full use of the historical data of moving objects to predict the travel time of vehicles on the road network. Public transport vehicles, taxis, and other vehicles in digital cities are equipped with GPS and vehicle navigation equipment, which can connect vehicle location information collected at different times to form a complete trajectory time series, and then mine its dynamic motion patterns. For mobile The purpose of mining the trajectory information of the object is to remind drivers in accident-prone areas in time, predict road congestion, provide better r...

AI Technical Summary

Problems solved by technology

[0005] Purpose of the invention: In order to overcome the problem of low accuracy and real-time performance of road network congestion prediction in the prior art, provide a road congestion discovery method based on a high-order Markov model on an urban road network. This method is based on a hybrid The Markov model prediction algorithm separates the model prediction from the transition matrix prediction, calculates the transition probability matrix in advance through the nearest neighbor propagation clustering algorithm, and then stores it in the database. When the model prediction is needed, the probability matrix is ​​directly read from the database , the transition probability matrix is ​​pre-calculated and stored, and it can be directly queried when predicting, which greatly improves the speed of real-time prediction. The use of neighbor propagation clustering can improve the classification accuracy, thereby improving the correctness of the probability transition matrix

Images