Optimization Of Public Transport Network Driven By Large Scale Trajectory Data

Ubiquitous positioning devices generate massive amounts of trajectory data.The analysis and application of large-scale trajectory data has become an important issue in the field of trajectory data.Trajectory clustering can not only help understand urban traffic flow,congestion and road network load,but also serve as an important basis for traffic planning and management.However,the analysis performance of large-scale trajectory data in various scenarios is still a huge challenge.Rapid large-scale trajectory clustering can identify hot spots for passengers to travel in a short time,providing a basis for data-driven bus network optimization.This paper conducts in-depth research on large-scale trajectory clustering and bus network optimization.The main work is as follows:(1)In the trajectory preprocessing stage,the original trajectory data is mapped to the road network structure,and the continuous co-occurrence probability of the edges of the road network in the trajectory is analyzed,and a distance measurement method based on the road network structure LORE(the Longest Overlapped Repeating Edges)is proposed.LORE can return similar values only using sequential cross traversal,and its worst-case time complexity is O(m+n).Compared with the mainstream distance measurement method,it greatly reduces the time of distance calculation.Finally,the comparative experiments show that the LORE distance metric can effectively improve the efficiency of large-scale trajectory clustering.(2)In the trajectory clustering stage,a fast large-scale trajectory clustering algorithm KMTC(K-Mediod-based Trajectory Clustering)and a centroid path refine algorithm CPRP(Centroid Path Refine based on Pivot-table)are proposed,which can effectively deal with large-scale trajectories data,optimizing the performance of trajectory clustering.The KMTC algorithm improves the k-medoids algorithm according to the characteristics of the trajectory data.By applying the triangle inequality and the boundary pruning strategy in the process of trajectory assignment and centroid path refinement,the clustering effect and execution speed of the algorithm are improved.The CPRP algorithm first uses the pivot-table to bind similar trajectories into a group to reduce the number of allocations in the trajectory allocation stage;then establishes an inverted index for each side of the road network to further reduce the cost of distance calculation;finally uses the graph traversal algorithm to avoid trajectory data duplication Access to get the centroid path.Experiments results show that the combination of KMTC and CPRP can further improve the trajectory clustering effect and algorithm performance,which is an order of magnitude faster than the traditional trajectory clustering method in terms of time.(3)A public transportation route planning solution RDDC(Route Design based on Demand and Connectivity)is proposed,which covers the hot spots of commuting demand and ensures the connectivity of the bus network.By extending the KMTC algorithm and combining network connectivity factors,a heuristic method ERD(Extension based Route Design)is designed to realize RDDC.The Lanczos method is used to estimate the natural connectivity of the bus network with bounded errors,avoiding the calculation expansion caused by matrix operations,and accelerating the convergence of the algorithm.Based on the boundary idea,the IUB(Incremental Update on Bound)algorithm is proposed,which uses the boundary increment to expand the selection edge with a greedy strategy,and reduces repeated matrix calculations in the iterative process.The method proposed in this paper is verified experimentally on two real data sets.The results show that the method proposed in this paper is effective and feasible,and for the optimization scheme that only depends on commuting needs,the shortest commuting distance is reduced by 20-30%.