Research On Road Matching Algorithm Of Taxi OD Time Series Trajectory Based On Hidden Markov Model

The GPS trajectory data of the taxi can be used for urban vehicle OD(OriginalDestination)path planning,road traffic and road condition assessment.Although its trajectory can reflect the shape of the road to a certain extent,the GPS data has latitude and longitude offset and data sampling Factors such as low accuracy are not completely equivalent to the urban road alignment,and it is often necessary to match it with the road.The usual matching method is to judge the affiliated road based on the closest vertical distance between the GPS track point and the adjacent road.This method not only causes low efficiency due to the high redundancy of the track point,but also easily generates matching errors for some track points that deviate greatly,so the new The matching algorithm is proposed to solve these problems.The research work first constructs a digital road network based on Xi'an Open Street Map road feature points,then extracts the OD time series trajectory set from the taxi GPS track points according to the getting on and off status,and finally processes each segment of the OD time series trajectory as follows:(1)Propose improved Douglas-Peucker(DP)trajectory compression algorithm.The algorithm automatically determines the threshold according to the compression ratio to remove the redundant points that do not reflect the shape change characteristics of the trajectory points in the OD time series trajectory.The algorithm is actually a pre-processing for the OD time series trajectory before road matching.(2)Propose a road matching algorithm based on hidden Markov model.The algorithm comprehensively considers the spatio-temporal characteristics of OD time series trajectory points,combines the road matching results of adjacent trajectory points from a global perspective,and uses the Viterbi algorithm to find the connected roads matched between the ODs with the smallest total cost,and converts the OD time series trajectory set into an OD path set,Solve the problem of matching error due to large deviation when matching only isolated GPS track points.The research of the subject removes the redundant points in the OD timing trajectory through the DP algorithm,and improves the accuracy of trajectory point matching through theroad matching algorithm based on the hidden Markov model.The point is anti-interference.The research results have application value for the analysis of urban taxi GPS data mining.