TraPlan: An Effective Three-in-One Trajectory-Prediction Model in Transportation Networks

• Published in: IEEE transactions on intelligent transportation systems 2015-06, Vol.16 (3), p.1188-1198
• Main Authors: Shaojie Qiao, Nan Han, Zhu, William, Gutierrez, Louis Alberto
• Format: Article
• Language: English
• Subjects: Data mining; Index; Indexes; Maintenance engineering; moving objects; region of interests; Roads; Trajectory; trajectory prediction (TP); transportation networks; Vectors
• ISSN: 1524-9050; 1558-0016
• DOI: 10.1109/TITS.2014.2353302

The existing approaches for trajectory prediction (TP) are primarily concerned with discovering frequent trajectory patterns (FTPs) from historical movement data. Moreover, most of these approaches work by using a linear TP model to depict the positions of objects, which does not lend itself to the complexities of most real-world applications. In this research, we propose a three-in-one TP model in road-constrained transportation networks called TraPlan. TraPlan contains three essential techniques: 1) constrained network R-tree (CNR-tree), which is a two-tiered dynamic index structure of moving objects based on transportation networks; 2) a region-of-interest (RoI) discovery algorithm is employed to partition a large number of trajectory points into distinct clusters; and 3) a FTP-tree-based TP approach, called FTP-mining, is proposed to discover FTPs to infer future locations of objects moving within RoIs. In order to evaluate the results of the proposed CNR-tree index structure, we conducted experiments on synthetically generated data sets taken from real-world transportation networks. The results show that the CNR-tree can reduce the time cost of index maintenance by an average gap of about 40% when compared with the traditional NDTR-tree, as well as reduce the time cost of trajectory queries. Moreover, compared with fixed network R-Tree (FNR-trees), the accuracy of range queries has shown an on average improvement of about 32%. Furthermore, the experimental results show that the TraPlan demonstrates accurate and efficient prediction of possible motion curves of objects in distinct trajectory data sets by over 80% on average. Finally, we evaluate these results and the performance of the TraPlan model in regard to TP by comparing it with other TP algorithms.