Similarity-based prediction of travel times for vehicles traveling on known routes

ABSTRACT

The use of centralized, real-time position tracking is proliferating in the areas of logistics and public transportation. Real-time positions can be used to provide up-to-date information to a variety of users, and they can also be accumulated for uses in subsequent data analyses. In particular, historical data in combination with real-time data may be used to predict the future travel times of vehicles more accurately, thus improving the experience of the users who rely on such information. We propose a Nearest-Neighbor Trajectory (NNT) technique that identifies the historical trajectory that is the most similar to the current, partial trajectory of a vehicle. The historical trajectory is then used for predicting the future movement of the vehicle. The paper's specific contributions are two-fold. First, we define distance measures and a notion of nearest neighbor that are specific to trajectories of vehicles that travel along known routes. In empirical studies with real data from buses, we evaluate how well the proposed distance functions are capable of predicting future vehicle movements. Second, we propose a main-memory index structure that enables incremental similarity search and that is capable of supporting varying-length nearest neighbor queries.

REFERENCES

• 1: Petko Bakalov , Eamonn Keogh , Vassilis J. Tsotras, TS2-tree - an efficient similarity based organization for trajectory data, Proceedings of the 15th annual ACM international symposium on Advances in geographic information systems, November 07-09, 2007, Seattle, Washington [doi>10.1145/1341012.1341082]
• 2: Y. Bin, Y. Zhongzhen, and Y. Baozhen. Bus arrival time prediction using support vector machines. Journal of Int. Transp. Systems: Technology, Planning, and Operations, 10(4): 151--158, 2006.
• 3: Béla Bollobás , Gautam Das , Dimitrios Gunopulos , Heikki Mannila, Time-series similarity problems and well-separated geometric sets, Proceedings of the thirteenth annual symposium on Computational geometry, p.454-456, June 04-06, 1997, Nice, France [doi>10.1145/262839.263080]
• 4: F. Cathey and D. Dailey. A prescription for transit arrival/departure prediction using automatic vehicle location data. Transp. Res. Part C, 11(3--4): 241--264, 2003.
• 5: Lei Chen , Raymond Ng, On the marriage of Lp-norms and edit distance, Proceedings of the Thirtieth international conference on Very large data bases, p.792-803, August 31-September 03, 2004, Toronto, Canada
• 6: Lei Chen , M. Tamer Özsu , Vincent Oria, Robust and fast similarity search for moving object trajectories, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066213]
• 7: S. I.-J. Chien, Y. Ding, and C. Wei. Dynamic bus arrival time prediction with artificial neural networks. Trans. Engrg., 128: 429--438, 2002.
• 8: E.-H. Chung and A. Shalaby. Expected time of arrival model for school bus transit using real-time global positioning system-based automatic vehicle location data. Journal of Int. Transp. Systems, 11: 157--167, 2007.
• 9: D. Dailey, S. Maclean, F. Cathey, and Z. Wall. Transit vehicle arrival prediction: An algorithm and a large scale implementation. Transp. Res. Rec., Transportation Network Modeling, pp. 46--51, 2001.
• 10: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Journal of Computer and System Sciences, v.66 n.4, p.614-656, 1 June 2003 [doi>10.1016/S0022-0000(03)00026-6]
• 11: J. R. Hee and L. R. Rilett. Bus arrival time prediction using artificial neural network model. In Proc. of the International IEEE Conference on Int. Transp. Systems, pp. 988--993, 2004.
• 12: J. Hwang, H. Kang, and K. Li. Spatio-temporal similarity analysis between trajectories on road networks. In Proc. of the International Workshop on Conceptual Modeling for Geographic Information Systems, pp. 280--289, 2005.
• 13: J. Hwang, H. Kang, and K. Li. Searching for similar trajectories on road networks using spatio-temporal similarity. In Proc. of the East-European Conference on Advances in Databases and Information Systems, pp. 282--295, 2006.
• 14: R. H. Jeong. The Prediction of Bus Arrival Time Using Automatic Vehicle Location Systems Data. Doctoral dissertation, Texas A&M University, 2004.
• 15: R. Kalaputapu and M. J. Demetsky. Modeling schedule deviations of buses using automatic vehicle location data and artificial neural networks. Transp. Res. Rec., 1497: 44--52, 1995.
• 16: M. G. Kendall. Rank Correlation Methods. Charles Griffin & Co. Ltd., 166 p, 1962.
• 17: W.-H. Lin and J. Zeng. An experimental study on real time bus arrival time prediction with GPS data. Journal of Transportation Research Board, pages 101--109, 1999.
• 18: T. Park, S. Lee, and Y.-J. Moon. Real time estimation of bus arrival time under mobile environment. In Proc. of International Conference on Computational Science and its Applications, pp. 1088--1096, 2004.
• 19: Nikos Pelekis , Ioannis Kopanakis , Gerasimos Marketos , Irene Ntoutsi , Gennady Andrienko , Yannis Theodoridis, Similarity Search in Trajectory Databases, Proceedings of the 14th International Symposium on Temporal Representation and Reasoning, p.129-140, June 28-30, 2007 [doi>10.1109/TIME.2007.59]
• 20: B. Predic, D. Stojanovic, S. Djordjevic-Kajan, A. Milosavljevic, and D. Rancic. Prediction of bus motion and continuous query processing for traveler information services. In Proc of the East European Conference on Advances in Databases and Information Systems, pp. 234--249, 2007.
• 21: H. Sakoe and S. Chiba. Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans. Acoustics, Speech and Signal Processing, 26(1):43--49, 1978.
• 22: A. Shalaby and A. Farhan. Prediction model of bus arrival and departure times using AVL and APC data. Journal of Pub. Transp., 7: 41--61, 2004.
• 23: D. Tiesyte and C. S. Jensen. Recovery of vehicle trajectories from tracking data for analysis purposes. In Proc. of the European Congress and Exhibition on Intelligent Transport Systems and Services, pp. 1--12, 2007.
• 24: Michail Vlachos , Dimitrios Gunopoulos , George Kollios, Discovering Similar Multidimensional Trajectories, Proceedings of the 18th International Conference on Data Engineering, p.673, February 26-March 01, 2002

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Similarity measures

General Terms:
Algorithms, Experimentation, Performance