Real Time Map Matching Algorithm of Floating Car In Support of Spatial Grid Index

Aiming at the demand on fast and real time map matching for massive floating car,this paper proposed a local map matching algorithm which combined online map matching with offline calculation.The Offline calculation firstly build two levels of grids for vector road network,and then combined similarity could be pre-calculated offline which takes both the distance from center of each cell to every candidate matching road segment or node and traffic direction of every candidate matching road segment into account.According to the value of the difference between the maximal combined similarity and the second largest combined similarity,the related road segment or road node whose combined similarity clearly dominated could be stored in advance as attribute value of the cell in second level grid.When online map matching is implemented for every real time GPS point,the cell in the second level of grid where the GPS point fall within could be firstly instantly got,and then measure of path accessibility from previous GPS point to current GPS point could be quickly determined by means of two-way forward and backward method,and then final matching result of real time GPS point that is the attribute value stored in advance could be instantly obtained according to the value of path accessibility.Experiments on massive floating car in Shenzhen city show that the matching speed of this method is twice as fast as the matching speed of local map matching method,and it only occupied about 8 M storage space on storing two level of grids and its attribute values which could be read into memory once,and it took about 32 hours to finish offline calculation for the whole Shenzhen road network,however,once offline calculation is finished,it was able to provide a long history service to online map match.