Research On Road Topology Construction And Path Selection Method Based On GPS Trajectory

As car ownership of citizens grows fast in our country currently, the speed of road construction in urban is not satisfactory, coupled with irrational allocation of traffic resources, traffic jam and accidents happened frequently, caused a serious waste of resources and environmental pollution. Intelligent Transportation Systems, as a new transport system, can make allocating resources more reasonably, improve the traffic capacity and road conditions. Electronic map is the basic element of intelligent transportation systems, its functions include network display, real-time navigation, route recommendation, etc. As networks become more and more complicated nowadays, electronic map greatly facilitate people’s traveling because of its advantages of rich information and easily interacted. But, traditional methods of making an electronic map cost too much, which lead map data updating slowly, while networks usually changed frequently. Therefore, the study of how to upda te the map data in time and efficiently to provide the latest navigation and road recommendation information to users has a strong practical significance and broad application prospects.GPS data contains trajectories information of moving objects, the res ults by analyzing these data can provide auxiliary information for road network updating, this can reduce the cost of making an electronic map. On the other hand, as the devices with location capabilities more and more cheaper and rapid spread of smart pho nes, people can collect GPS data easily. In this case, spatio-temporal data mining technology based on GPS trajectories becomes a research hotspot.Taxis, as a type of commercial vehicle, have the advantages of long running time, wide range of tracks, large cardinal and low-cost of data collection, makes it very suitable for updating road networks. Our work in this paper includes three aspects with the taxi trajectories data provided by Microsoft Research Asia:(1) Preprocessing data to ensure data accuracy, then using a clustering algorithm to extract the Beijing main road network. The result by comparing with Google Map shows the extracted road network is correct.(2) Proposed a method to construct road network topologies based on taxis GPS trajectories. Road network topologies are the premise of navigation and path recommendation. In order to get the latest road network and connection relationships between each road, by using the road network extracted in step(1), with the characteristic of road points, we find out these intersections successfully, eventually we construct the road network topologies. The result by comparing with Google Map and Beijing shp map shows the extracted road intersections are correct.(3) Proposed a path selection method based on a quad-heap priority queue. According to the extracted road network and its topologies, combined with historical data, we implement the function of shortest and optimal path selection using Dij kstra algorithm based on a quad-heap priority queue.