Mining K primary corridors from vehicle GPS trajectories on a road network based on traffic flow

摘要

Given a set of GPS trajectories on a road network and a specified number of k, the K-Primary-Corridors(KPC) problem aims to find k trajectories as primary corridors so that the overall distance from all trajectories to their closest primary corridors is minimized. It is important for the applications such as optimization of transportation network, greener travel and disaster rescue. However, many of the existing algorithms of primary corridors are based on geometric space, and the value of practical application is low. Although some are based on network space, they randomly select k primary corridors or ideally set the weights of each side of the road network to 1 before computing. This not only reduces the accuracy of the results, but may also increase the computational complexity. This paper proposes the k-primary-corridors algorithm based on traffic flow on a road network. Firstly, the algorithm initializes the k primary corridors based on the traffic flow and the distance between the trajectories. Secondly, according to the actual traffic conditions, each side of the road network is given a reasonable weight. Finally, we use adjacency list to store the structure of road network graph and the lower bound filtering algorithm and the Dijkstra algorithm based on priority queue are used to reduce the time and space complexity of the algorithm. Some experiments are performed on the data set of Chengdu taxi GPS trajectories and the results shows that the algorithm is reasonable and effective.