Chinese Journal of Computers   Full Text
Title	A Heuristic Path-Estimating Algorithm by Using Vector-Based Recognition
Authors	LU Wei-Feng WU Dong-Dong ZHU Tong-Yu
Address	(State Key Laboratory of Software Development Environment, Beihang University, Beijing 100083)
Year	2009
Issue	No.7(1443—1450)
Abstract &   Background	Abstract Floating Car Data (FCD) is an important material for a broad range of application such as traffic management and control, traffic conditions computation and so on. However, in the original data exists error, and the data must be handled by path-estimating and be related to the road. The traditional path-estimating algorithms mainly use two methods: the incremental method and the global method. Both of them have advantages and disadvantages of themselves: while the global map-matching algorithm produces better matching results, the incremental algorithm produces results of lower quality faster. All things considering the two traditional algorithms, this paper proposes a heuristic path-estimating algorithm by using vector-based recognition. Firstly, the algorithm uses the heuristic search method, and it makes use of geometric operation to form the restriction, and make the comparison between the vector formed with the vehicular GPS points and the special road network model to search and select the vehicular possible traveling routes. Secondly, it globally compares all the vehicular possible traveling routes, and then chooses the optimal one. The result of testing demonstrates the efficiency of the algorithm both at accuracy and computational speed when handling the large-scale data of GPS tracking data even under the complex road network conditions. Keywords path-estimating; Floating Car Data(FCD); GPS; heuristic search Background How to acquire real-time and dynamic transportation information is becoming prevailing research focus in the community of Intelligent Transport Systems (ITS) nowadays. This information can be applied in the transportation area like vehicle navigation, traffic control and so on. Floating car data(FCD) refers to assess the overall traffic conditions. Using technologies like orientation, wireless communication and information processing to achieve the collection and disposal of the raw data like instantaneous speed, position and travel time of the floating cars. A pre-processing step that matches FCD to the road network is needed. This technique is commonly referred to as path-estimating. Large-scale, real-time and discrete distribution is the main characteristics of FCD, and the core processing algorithms must provide good performance of high efficiency and accuracy in order to meet the needs of real traffic information system. The traditional path-estimating algorithm adopts two mechanisms: incremental and global. The incremental method is simple and fast, while the accuracy of the results is poor; the global method is complicated and the accuracy of the result is pretty good, while the processing speed is slow. For this reason, the paper studies and designs a heuristic route-estimating algorithm by using vector-based recognition. The proposed algorithm is efficient both at accuracy and computational speed when handling the large-scale data of GPS tracking data even under the complex road network conditions. This subject belongs to the Next Generation Internet Demonstrated Project—“Beijing Internet ITS Demonstration and Application Project” and the National High-Tech Research and Development Plan of China “The research to key technologies of high-quality dynamic traffic information services for vehicles’ navigation”. With the result of the projects, it provides real-time picture of traffic conditions of the whole road network of Beijing through handling large volume of GPS data recorded by 13000 taxis. The results of this paper provide the core computations which make the “raw” FCD to be related which the city road.