Research On Key Issues Of Road Network Through Large-Scale Trajectory Data Mining

Urban road network is an open and highly complex system. Understanding the working status of road network, and grasping the network dynamics is essential to improve the efficiency of the entire transportation system. For a long time physical models, such as partial differential equation, have employed to descript the underlying logic of road network, and microscopic simulation methods have been used to reveal its dynamical mechanism, and many achievements have been made in such research field. With the rapid development of sensing and computing technology, a wide variety of big data can be easily collected. Especially the trajectory data, which grow out of a large number of " Mobile Sensors of Cities"—taxis moving on the roads, contains a wealth of the road network dynamics, and provides us with an unprecedented opportunity to analyze, evaluate and understand the behaviors and status of the road network, but big challenges are also posed to the existing data analysis techniques and methods.Focusing on the technologies of trajectory data mining, this dissertation solves several important problems in analysis and evaluation of road network, such as map matching of the uncertain trajectories, discovery of key nodes in road network, anomalies detection and measurement of road network reliability. Our proposed methods have great value in terms of optimal controlling traffic flow; improving the transportation plan and emergency management of the road network. In brief, these results provide important reference for the road network running smoothly. Specifically, the main contributions and innovations of this dissertation are reflected as follows.(1) In terms of the trajectory preprocessing techniques, an offline map matching algorithm for uncertain trajectory is proposed. This algorithm is based on conditional random field model, which fully support the overlapping, non-independent features. By taking advantage of this, the spatial-temporal features representing the context of adjacent sampling points are introduced, which greatly improve the resolving power of features. The driver route preference is also used to bolster the temporal-spatial context when a low GPS sampling rate impairs the resolving power of temporal-spatial context in CRF, allowing the map matching accuracy of uncertain GPS trajectories to get improved significantly. The experimental results show that our proposed algorithm is more accurate than existing methods, especially in the case of a low-sampling-rate.(2) In order to identify key nodes in the road network accurately, an innovative tripartite graph is proposed to model the dynamic travel network, which contains traffic volume, travel demand, route strategy, driver experience and topology of road network. Such information is extracted from trajectories and electronic map. From these, two data-driven algorithms of key-node identification are presented:1) traffic and OD entropy-based algorithm; 2) eigenvector calculation-based algorithm. The first algorithm can make a trade-off between the traffic volume and centrality, while the last algorithm performs a procedure of score propagation on our tripartite graph, and reflects the mutual reinforcement relationship among OD pairs, paths and intersections. Apart from traffic volume and centrality, other factors are combined in the process of calculation, e.g. the intersections passed by the irreplaceable or long-distance paths may be important. In addition, the high-load OD pairs and popular paths can be got in the result of the last algorithm. Experimental results on synthetic and real data validate the efficiency and effectiveness of both of proposed methods.(3) The existing anomaly detection methods cannot detect various types of the spatial-temporal network anomaly, and they are not effective in a complex environment such as road network. To address this problem, this dissertation proposes an anomaly detection method based on sliding window tensor decomposition, in which traffic information is extracted from large-scale trajectories, and represented by a third-order tensor. Through tensor decomposition technology, the main traffic variation under interactions among multiple modes is obtained. This method has the following three characteristics:1) a sliding window tensor and a fast SVD method (IFAST) is combined. The advantage of this is that only updated part of the tensor is calculated during each iterative step, therefore the algorithm cost is so low that it is suitable for the applications with real-time requirements; 2) through cooperation and integration of interactions among spatial, temporal and historical modes, not only can this method detect various types of anomalies, but it can improve the effectiveness of any type of anomaly detection; 3) this method can detect network-wide anomalies. In addition, this dissertation also proposes a method to infer associated OD pairs according to OD traffic and anomaly scarcity, which help to further analysis the causes of anomalies.(4) This dissertation proposes a cloud model-based regional connectivity estimation method, in which the velocity and distance measurements between any two regions are extracted from trajectories and urban electronic map first, and then they are normalized and projected onto a two-dimensional coordinate system. The connectivity between two regions is represented by the size of corresponding rectangle. Considering the uncertainty of trajectories, the region connectivity is modeled using cloud model. For grade division of connectivity, a method integrating golden section into cloud model is presented.