Learning to Estimate the Travel Time

ABSTRACT

Vehicle travel time estimation or estimated time of arrival (ETA) is one of the most important location-based services (LBS). It is becoming increasingly important and has been widely used as a basic service in navigation systems and intelligent transportation systems. This paper presents a novel machine learning solution to predict the vehicle travel time based on floating-car data. First, we formulate ETA as a pure spatial-temporal regression problem based on a large set of effective features. Second, we adapt different existing machine learning models to solve the regression problem. Furthermore, we propose a Wide-Deep-Recurrent (WDR) learning model to accurately predict the travel time along a given route at a given departure time. We then jointly train wide linear models, deep neural networks and recurrent neural networks together to take full advantages of all three models. We evaluate our solution offline with millions of historical vehicle travel data. We also deploy the proposed solution on Didi Chuxing's platform, which services billions of ETA requests and benefits millions of customers per day. Our extensive evaluations show that our proposed deep learning algorithm significantly outperforms the state-of-the-art learning algorithms, as well as the solutions provided by leading industry LBS providers.

References

1. Pouria Amirian, Anahid Basiri, and Jeremy Morley. 2016. Predictive analytics for enhancing travel time estimation in navigation apps of Apple, Google, and Microsoft. In Proceedings of the 9th ACM SIGSPATIAL International Workshop on Computational Transportation Science.
2. Mohammad Asghari, Tobias Emrich, Ugur Demiryurek, and Cyrus Shahabi. 2015. Probabilistic Estimation of Link Travel Times in Dynamic Road Networks. In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems.
3. Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015. Neural machine translation by jointly learning to align and translate. In International Conference on Learning Representation (ICLR '15).
4. Tianqi Chen and Carlos Guestrin. 2016. XGBoost: A Scalable Tree Boosting System. In Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '16).
5. Heng-Tze Cheng, Levent Koc, et al. 2016. Wide &Deep Learning for Recommender Systems. In Proceedings of the 1st Workshop on Deep Learning for Recommender Systems (DLRS '16).
6. Yanjie Duan, Yisheng Lv, and Fei-Yue Wang. 2016. Travel time prediction with LSTM neural network. In IEEE 19th International Conference on Intelligent Transportation Systems (ITSC '16).
7. John Duchi, Elad Hazan, and Yoram Singer. 2011. Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. Journal of Machine Learning Research 12 (jul 2011), 2121--2159.
8. C. de Fabritiis, R. Ragona, and G. Valenti. 2008. Traffic Estimation And Prediction Based On Real Time Floating Car Data. In 2008 11th International IEEE Conference on Intelligent Transportation Systems.
9. Jerome H Friedman. 2001. Greedy function approximation: a gradient boosting machine. Annals of statistics (2001), 1189--1232.
10. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation 9, 8 (1997), 1735--1780.
11. Erik Jenelius and Haris N Koutsopoulos. 2013. Travel time estimation for urban road networks using low frequency probe vehicle data. Transportation Research Part B: Methodological 53 (2013), 64--81.
12. Diederik Kingma and Jimmy Ba. 2015. Adam: A Method for Stochastic Optimization. In International Conference on Learning Representations (ICLR '15).
13. M. Kormáksson, L. Barbosa, M. R. Vieira, and B. Zadrozny. 2014. Bus Travel Time Predictions Using Additive Models. In IEEE International Conference on Data Mining (ICDM '14).
14. Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. 2012. Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems (NIPS '12).
15. Wang-Chien Lee, Weiping Si, Ling-Jyh Chen, and Meng Chang Chen. 2012. HTTP: A New Framework for Bus Travel Time Prediction Based on Historical Trajectories. In Proceedings of the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.
16. H. B. Mcmahan. 2016. Follow-the-Regularized-Leader and Mirror Descent: Equivalence Theorems and L1 Regularization. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics (AISTATS '11).
17. Steffen Rendle. 2010. Factorization machines. In IEEE 10th International Conference on Data Mining (ICDM '10). IEEE, 995--1000.
18. Raffi Sevlian and Ram Rajagopal. 2010. Travel Time Estimation Using Floating Car Data. arXiv preprint arXiv:1012.4249 (2010).
19. Hongjian Wang, Yu-Hsuan Kuo, Daniel Kifer, and Zhenhui Li. 2016. A simple baseline for travel time estimation using large-scale trip data. In Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.
20. Yilun Wang, Yu Zheng, and Yexiang Xue. 2014. Travel Time Estimation of a Path Using Sparse Trajectories. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '14).
21. Jiancheng Weng, Chang Wang, Hainan Huang, Yueyue Wang, and Ledian Zhang. 2016. Real-time bus travel speed estimation model based on bus GPS data. Advances in Mechanical Engineering 8, 11 (2016), 1687814016678162.
22. Chun-Hsin Wu, Jan-Ming Ho, and D. T. Lee. 2004. Travel-time prediction with support vector regression. IEEE Transactions on Intelligent Transportation Systems 5, 4 (Dec 2004), 276--281.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Natural language processing

  • Machine learning

    • Cross-validation

    • Learning paradigms

      • Supervised learning

        • Supervised learning by regression

    • Learning settings

      • Batch learning

    • Machine learning approaches

      • Classification and regression trees

      • Neural networks

  • Parallel computing methodologies

    • Parallel programming languages

• General and reference

  • Document types

    • General conference proceedings

• Information systems

  • Information systems applications

    • Data mining

    • Spatial-temporal systems

      • Geographic information systems

      • Global positioning systems

      • Location based services

• Mathematics of computing

  • Probability and statistics

    • Probabilistic inference problems

      • Maximum likelihood estimation

    • Statistical paradigms

      • Time series analysis