research-article

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

Authors:

Christian S. JensenAuthors Info & Claims

GIS '08: Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems

Article No.: 14, Pages 1 - 10

https://doi.org/10.1145/1463434.1463452

Published: 05 November 2008 Publication History

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]

P. Bakalov, E. Keogh, and V. Tsotras. TS2-tree---an efficient similarity based organization for trajectory data. Proc. of the Annual ACM International Symposium on Advances in Geographic Information Systems, pp. 1--4, 2007.

Digital Library

[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. Bollobas, G. Das, D. Gunopulos, and H. Mannila. Time-series similarity problems and well-separated geometric sets. In Proc. of the Annual Symposium on Computational Geometry, pp. 454--456, 1997.

Digital Library

[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]

L. Chen and R. Ng. On the marriage of Lp-norms and edit distance. In Proc. of the International Conference on Very Large Data Bases, pp. 792--803, 2004.

Digital Library

[6]

L. Chen, M. T. Özsu, and V. Oria. Robust and fast similarity search for moving object trajectories. In Proc. of the ACM SIGMOD International Conference on Management of Data, pp. 491--502, 2005.

Digital Library

[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]

R. Fagin, A. Lotem, and M. Naor. Optimal aggregation algorithms for middleware. Journal of Comp. and Syst. Sciences, 66(4): 614--656, 2003.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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]

N. Pelekis, I. Kopanakis, G. Marketos, I. Ntoutsi, G. Andrienko, and Y. Theodoridis. Similarity Search in Trajectory Databases. In Proc. of the International Symposium on Temporal Representation and Reasoning, pp. 129--140, 2007.

Digital Library

[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.

Digital Library

[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]

M. Vlachos, G. Kollios, and D. Gunopulos. Discovering similar multidimensional trajectories. In Proc. of the International Conference on Data Engineering, pp. 673--684, 2002.

Digital Library

Cited By

Feng XLin QJia NTian J(2024)The actual impact of ride-splitting: An empirical study based on large-scale GPS dataTransport Policy10.1016/j.tranpol.2023.12.008147(94-112)Online publication date: Mar-2024
https://doi.org/10.1016/j.tranpol.2023.12.008
Yang MWu TMao JZhu KZhou A(2024)Attention Mechanism Based Multi-task Learning Framework for Transportation Time PredictionAdvances in Knowledge Discovery and Data Mining10.1007/978-981-97-2262-4_30(376-388)Online publication date: 25-Apr-2024
https://doi.org/10.1007/978-981-97-2262-4_30
Wang HZhang ZFan ZChen JZhang LShibasaki RSong X(2023)Multi-Task Weakly Supervised Learning for Origin–Destination Travel Time EstimationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.323606035:11(11628-11641)Online publication date: 1-Nov-2023
https://doi.org/10.1109/TKDE.2023.3236060
Show More Cited By

Index Terms

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

Recommendations

Neural network based lane change trajectory prediction in autonomous vehicles
Transactions on computational science XIII

During a lane change, vehicle collision warning systems detect the likelihood of collision and time to collision to warn vehicles of an imminent collision. In autonomous systems, a vehicle utilizes data obtained by its own sensors to predict future ...
Personalized Travel Time Prediction Using a Small Number of Probe Vehicles
Special Issue on SIGSPATIAL 2017

Predicting the travel time of a path is an important task in route planning and navigation applications. As more GPS probe data has been collected to monitor urban traffic, GPS trajectories of the probe vehicles have been frequently used to predict path ...
Overtaking Feasibility Prediction for Mixed Connected and Connectionless Vehicles
Intelligent transportation systems (ITS) utilize advanced technologies to enhance traffic safety and efficiency, contributing significantly to modern transportation. The integration of Vehicle-to-Everything (V2X) further elevates road safety and fosters ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GIS '08: Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems

November 2008

559 pages

ISBN:9781605583235

DOI:10.1145/1463434

Program Chairs:
Walid G. Aref
Purdue University
,
Mohamed F. Mokbel
University of Minnesota
,
Markus Schneider
University of Florida

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

ESRI
Google Inc.
Oak Ridge National Laboratory
Microsoft: Microsoft
SIGSPATIAL: ACM Special Interest Group on Spatial Information

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

GIS '08

Sponsor:

Microsoft
SIGSPATIAL

GIS '08: 16th International Symposium on Advances in Geographic Information Systems

November 5 - 7, 2008

California, Irvine

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

49
Total Citations
View Citations
742
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)2

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Feng XLin QJia NTian J(2024)The actual impact of ride-splitting: An empirical study based on large-scale GPS dataTransport Policy10.1016/j.tranpol.2023.12.008147(94-112)Online publication date: Mar-2024
https://doi.org/10.1016/j.tranpol.2023.12.008
Yang MWu TMao JZhu KZhou A(2024)Attention Mechanism Based Multi-task Learning Framework for Transportation Time PredictionAdvances in Knowledge Discovery and Data Mining10.1007/978-981-97-2262-4_30(376-388)Online publication date: 25-Apr-2024
https://doi.org/10.1007/978-981-97-2262-4_30
Wang HZhang ZFan ZChen JZhang LShibasaki RSong X(2023)Multi-Task Weakly Supervised Learning for Origin–Destination Travel Time EstimationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.323606035:11(11628-11641)Online publication date: 1-Nov-2023
https://doi.org/10.1109/TKDE.2023.3236060
Putatunda SLaha A(2023)Travel Time Prediction in Real time for GPS Taxi Data Streams and its Applications to Travel SafetyHuman-Centric Intelligent Systems10.1007/s44230-023-00028-03:3(381-401)Online publication date: 11-Jun-2023
https://doi.org/10.1007/s44230-023-00028-0
Jensen C(2022)Digitalization in the Service of Society: The Case of Big Vehicle Trajectory DataProceedings of the 34th International Conference on Scientific and Statistical Database Management10.1145/3538712.3543822(1-1)Online publication date: 6-Jul-2022
https://dl.acm.org/doi/10.1145/3538712.3543822
Zhang ZWang HFan ZChen JSong XShibasaki R(2022)GOF-TTE: Generative Online Federated Learning Framework for Travel Time EstimationIEEE Internet of Things Journal10.1109/JIOT.2022.31908649:23(24107-24121)Online publication date: 1-Dec-2022
https://doi.org/10.1109/JIOT.2022.3190864
Zhang ZWang HFan ZChen JSong XShibasaki R(2022)Route to Time and Time to Route: Travel Time Estimation from Sparse TrajectoriesMachine Learning and Knowledge Discovery in Databases10.1007/978-3-031-26422-1_30(489-504)Online publication date: 19-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-26422-1_30
Gong ZDu BLiu ZZeng WPerez PWu K(2020)SD-seq2seq : A Deep Learning Model for Bus Bunching Prediction Based on Smart Card Data2020 29th International Conference on Computer Communications and Networks (ICCCN)10.1109/ICCCN49398.2020.9209686(1-9)Online publication date: Aug-2020
https://doi.org/10.1109/ICCCN49398.2020.9209686
Zeng QWang JHe K(2020)Improving Destination Prediction via Ensemble of Trajectory Movement Separation and Adaptive ClusteringIEEE Access10.1109/ACCESS.2020.29713888(28142-28154)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2971388
Liu WHu ESu BWang J(2020)Using machine learning techniques for DSP software performance prediction at source code levelConnection Science10.1080/09540091.2020.176254233:1(26-41)Online publication date: 25-May-2020
https://doi.org/10.1080/09540091.2020.1762542
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents