IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v545y2020ics0378437119320941.html
   My bibliography  Save this article

Markov Chains based route travel time estimation considering link spatio-temporal correlation

Author

Listed:
  • Tang, Jinjun
  • Hu, Jin
  • Hao, Wei
  • Chen, Xinqiang
  • Qi, Yong

Abstract

Travel time is a critical measure for road network traffic conditions, and travel time estimation provides available information for travellers and traffic management. This paper proposes an improved method based on Markov Chains to estimate route travel time by considering spatio-temporal correlation from related links. The method mainly contains three parts. Firstly, in the light of traffic flow data collected from microwave detectors, Gaussian mixture model (GMM) is applied to cluster travel time data under two consecutive links, and thus capture the underlying traffic states. The transition probability matrix is constructed to estimate variations of traffic states over time. Then, link travel time distributions can be estimated from historical observations. Accordingly, we can estimate route travel time distribution by aggregating weighted link travel time distribution based on convolution theory. Finally, a case study including three experiments are used to test the accuracy of travel time estimation, we also compare the estimation performance of proposed model with several traditional methods, and the results indicate that the proposed model is effective and superior to traditional modes based on two indicators: Kullback–Leibler (KL) divergence and Mean Absolute Error (MAE).

Suggested Citation

  • Tang, Jinjun & Hu, Jin & Hao, Wei & Chen, Xinqiang & Qi, Yong, 2020. "Markov Chains based route travel time estimation considering link spatio-temporal correlation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 545(C).
    • Handle: RePEc:eee:phsmap:v:545:y:2020:i:c:s0378437119320941
    DOI: 10.1016/j.physa.2019.123759
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437119320941
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000
    File URL: https://libkey.io/10.1016/j.physa.2019.123759?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Yeon, Jiyoun & Elefteriadou, Lily & Lawphongpanich, Siriphong, 2008. "Travel time estimation on a freeway using Discrete Time Markov Chains," Transportation Research Part B: Methodological, Elsevier, vol. 42(4), pages 325-338, May.
    2. Tang, Jinjun & Yang, Yifan & Qi, Yong, 2018. "A hybrid algorithm for Urban transit schedule optimization," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 512(C), pages 745-755.
    3. Ramezani, Mohsen & Geroliminis, Nikolas, 2012. "On the estimation of arterial route travel time distribution with Markov chains," Transportation Research Part B: Methodological, Elsevier, vol. 46(10), pages 1576-1590.
    4. Tang, Jinjun & Liang, Jian & Zhang, Shen & Huang, Helai & Liu, Fang, 2018. "Inferring driving trajectories based on probabilistic model from large scale taxi GPS data," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 506(C), pages 566-577.
    5. Xin Ye & Ke Wang & Yajie Zou & Dominique Lord, 2018. "A semi-nonparametric Poisson regression model for analyzing motor vehicle crash data," PLOS ONE, Public Library of Science, vol. 13(5), pages 1-17, May.
    6. Tang, Jinjun & Chen, Xinqiang & Hu, Zheng & Zong, Fang & Han, Chunyang & Li, Leixiao, 2019. "Traffic flow prediction based on combination of support vector machine and data denoising schemes," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 534(C).
    7. Zhang, Shen & Liu, Xin & Tang, Jinjun & Cheng, Shaowu & Qi, Yong & Wang, Yinhai, 2018. "Spatio-temporal modeling of destination choice behavior through the Bayesian hierarchical approach," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 512(C), pages 537-551.
    8. Ruone Zhang & Xin Ye & Ke Wang & Dongjin Li & Jiayu Zhu, 2019. "Development of Commute Mode Choice Model by Integrating Actively and Passively Collected Travel Data," Sustainability, MDPI, vol. 11(10), pages 1-15, May.
    9. Zong, Fang & Tian, Yongda & He, Yanan & Tang, Jinjun & Lv, Jianyu, 2019. "Trip destination prediction based on multi-day GPS data," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 515(C), pages 258-269.
    10. Changxi Ma & Ruichun He & Wei Zhang, 2018. "Path optimization of taxi carpooling," PLOS ONE, Public Library of Science, vol. 13(8), pages 1-15, August.
    11. David A. Hensher, 2001. "Measurement of the Valuation of Travel Time Savings," Journal of Transport Economics and Policy, University of Bath, vol. 35(1), pages 71-98, January.
    12. Van Arem, Bart & Van Der Vlist, Martie J. M. & Muste, M. (Rik) & Smulders, Stef A., 1997. "Travel time estimation in the GERDIEN project," International Journal of Forecasting, Elsevier, vol. 13(1), pages 73-85, March.
    13. Yan, Ying & Zhang, Shen & Tang, Jinjun & Wang, Xiaofei, 2017. "Understanding characteristics in multivariate traffic flow time series from complex network structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 477(C), pages 149-160.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Yong Wang & Jingxin Zhou & Yaoyao Sun & Xiuwen Wang & Jiayi Zhe & Haizhong Wang, 2022. "Electric Vehicle Charging Station Location-Routing Problem with Time Windows and Resource Sharing," Sustainability, MDPI, vol. 14(18), pages 1-31, September.
    2. Chen, Xinqiang & Chen, Huixing & Yang, Yongsheng & Wu, Huafeng & Zhang, Wenhui & Zhao, Jiansen & Xiong, Yong, 2021. "Traffic flow prediction by an ensemble framework with data denoising and deep learning model," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 565(C).
    3. Gao, Yuhong & Qu, Zhaowei & Song, Xianmin & Yun, Zhenyu & Xia, Yingji, 2021. "A novel relationship model between signal timing, queue length and travel speed," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 583(C).
    4. Zhang, Kunpeng & Feng, Xiaoliang & Jia, Ning & Zhao, Liang & He, Zhengbing, 2022. "TSR-GAN: Generative Adversarial Networks for Traffic State Reconstruction with Time Space Diagrams," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 591(C).
    5. A, Sheeba Angel & R, Jayaparvathy, 2024. "Modeling of emergency evacuation in high rise buildings considering congestion at stairs based on Markov chains," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 633(C).
    6. Xie, Minghui & Zhang, Xinying & Wu, Zhouhao & Wei, Sen & Gao, Yanan & Wang, Yuanqing, 2023. "A shared parking optimization framework based on dynamic resource allocation and path planning," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 616(C).
    7. Yang, Qiaoli & Shi, Zhongke, 2021. "The queue dynamics of protected/permissive left turns at pre-timed signalized intersections," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 562(C).
    8. Shao, Feng & Shao, Hu & Wang, Dongle & Lam, William H.K. & Cao, Shuhan, 2023. "A generative model for vehicular travel time distribution prediction considering spatial and temporal correlations," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 621(C).
    9. Shao, Feng & Shao, Hu & Wang, Dongle & Lam, William H.K., 2024. "A multi-task spatio-temporal generative adversarial network for prediction of travel time reliability in peak hour periods," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 638(C).
    10. Büchel, Beda & Corman, Francesco, 2022. "Modeling conditional dependencies for bus travel time estimation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 592(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Du, Zhouyang & Tang, Jinjun & Qi, Yong & Wang, Yiwei & Han, Chunyang & Yang, Yifan, 2020. "Identifying critical nodes in metro network considering topological potential: A case study in Shenzhen city—China," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 539(C).
    2. Zong, Fang & Yu, Ping & Tang, Jinjun & Sun, Xiao, 2019. "Understanding parking decisions with structural equation modeling," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 523(C), pages 408-417.
    3. Junjie Fu & Xinqiang Chen & Shubo Wu & Chaojian Shi & Huafeng Wu & Jiansen Zhao & Pengwen Xiong, 2020. "Mining ship deficiency correlations from historical port state control (PSC) inspection data," PLOS ONE, Public Library of Science, vol. 15(2), pages 1-19, February.
    4. Tang, Jinjun & Chen, Xinqiang & Hu, Zheng & Zong, Fang & Han, Chunyang & Li, Leixiao, 2019. "Traffic flow prediction based on combination of support vector machine and data denoising schemes," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 534(C).
    5. Xin Guan & Xin Ye & Cheng Shi & Yajie Zou, 2019. "A Multivariate Modeling Analysis of Commuters’ Non-Work Activity Allocations in Xiaoshan District of Hangzhou, China," Sustainability, MDPI, vol. 11(20), pages 1-19, October.
    6. Zhang, Shen & Liu, Xin & Tang, Jinjun & Cheng, Shaowu & Qi, Yong & Wang, Yinhai, 2018. "Spatio-temporal modeling of destination choice behavior through the Bayesian hierarchical approach," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 512(C), pages 537-551.
    7. Tang, Jinjun & Bi, Wei & Liu, Fang & Zhang, Wenhui, 2021. "Exploring urban travel patterns using density-based clustering with multi-attributes from large-scaled vehicle trajectories," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 561(C).
    8. Yan, Ying & Zhang, Ying & Yang, Xiangli & Hu, Jin & Tang, Jinjun & Guo, Zhongyin, 2020. "Crash prediction based on random effect negative binomial model considering data heterogeneity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 547(C).
    9. Büchel, Beda & Corman, Francesco, 2022. "Modeling conditional dependencies for bus travel time estimation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 592(C).
    10. Helai Huang & Jialing Wu & Fang Liu & Yiwei Wang, 2020. "Measuring Accessibility Based on Improved Impedance and Attractive Functions Using Taxi Trajectory Data," Sustainability, MDPI, vol. 13(1), pages 1-23, December.
    11. Qian Duan & Xin Ye & Jian Li & Ke Wang, 2020. "Empirical Modeling Analysis of Potential Commute Demand for Carsharing in Shanghai, China," Sustainability, MDPI, vol. 12(2), pages 1-18, January.
    12. Chen Xu & Decun Dong & Dongxiu Ou & Changxi Ma, 2019. "Time-of-Day Control Double-Order Optimization of Traffic Safety and Data-Driven Intersections," IJERPH, MDPI, vol. 16(5), pages 1-18, March.
    13. Gao, Yuhong & Qu, Zhaowei & Song, Xianmin & Yun, Zhenyu & Xia, Yingji, 2021. "A novel relationship model between signal timing, queue length and travel speed," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 583(C).
    14. Jinjun Tang & Fan Gao & Fang Liu & Wenhui Zhang & Yong Qi, 2019. "Understanding Spatio-Temporal Characteristics of Urban Travel Demand Based on the Combination of GWR and GLM," Sustainability, MDPI, vol. 11(19), pages 1-19, October.
    15. Wang, Chao & Ma, Changxi & Xu, Xuecai(Daniel), 2020. "Multi-objective optimization of real-time customized bus routes based on two-stage method," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 537(C).
    16. Changxi Ma & Dong Yang & Jibiao Zhou & Zhongxiang Feng & Quan Yuan, 2019. "Risk Riding Behaviors of Urban E-Bikes: A Literature Review," IJERPH, MDPI, vol. 16(13), pages 1-18, June.
    17. Guo, Yajuan & Yang, Licai & Hao, Shenxue & Gao, Jun, 2019. "Dynamic identification of urban traffic congestion warning communities in heterogeneous networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 522(C), pages 98-111.
    18. Tang, Jinjun & Yang, Yifan & Qi, Yong, 2018. "A hybrid algorithm for Urban transit schedule optimization," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 512(C), pages 745-755.
    19. A, Sheeba Angel & R, Jayaparvathy, 2024. "Modeling of emergency evacuation in high rise buildings considering congestion at stairs based on Markov chains," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 633(C).
    20. Xu, Ting & Jiang, Ruisen & Wen, Changlei & Liu, Meijun & Zhou, Jiehan, 2019. "A hybrid model for lane change prediction with V2X-based driver assistance," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 534(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:phsmap:v:545:y:2020:i:c:s0378437119320941. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.