Skip to main content
SpringerLink
Log in

Origin-Destination Demand Reconstruction Using Observed Travel Time under Congested Network

  • Published:
Networks and Spatial Economics Aims and scope Submit manuscript

Abstract

Two bi-level models to reconstruct origin-destination (O-D) demand under congested network are explored in terms of the observed link and route travel times, where one model inputs the known trajectories of observed route travel times and the other model uses both known and unknown trajectories of observed route travel times. The proposed models leverage both the link and route traffic information to determine the network O-D demand that minimizes the distances between the observed and estimated traffic information (O-D, link and route travel times) in the upper-level, and optimize the stochastic user equilibrium (SUE) in the lower-level. Meanwhile, the observed information of travel time can capture the relationships between traffic flow and travel cost/time in congested network. The K-means (hard assignment) and Gaussian mixture model (GMM, soft assignment) clustering methods are presented to identify the trajectories of observed route travel times. An iterative solution algorithm is proposed to solve the built O-D reconstruction models, where the method of gradient descent, the method of successive average and Expectation-Maximization (EM) algorithm are used to solve the upper-level model, lower level model, and GMM, respectively. Results from numerical experiments demonstrate the superiority of the travel time based model over the traditional flow based method in congested traffic network, and also suggest that using both the route and link information outperforms only using link information in the reconstruction of O-D demand.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11

Similar content being viewed by others

References

  • Abdelghany K, Hassan A, Alnawaiseh A, Hashemi H (2015) Flow-based and density-based time-dependent demand estimation for congested urban transportation networks. Transp Res Rec 2498:27–36

    Google Scholar 

  • Antoniou C, Ben-Akiva M, Koutsopoulos HN (2006) Dynamic traffic demand prediction using conventional and emerging data sources. IEE proceedings-intelligent transport systems. IET Digital Library 153(1):97–104

    Google Scholar 

  • Ashok K, Ben-Akiva ME (2000) Alternative approaches for real-time estimation and prediction of time-dependent origin-destination flows. Transp Sci 34(1):21–36

    Google Scholar 

  • Barceló J, Montero L, Marqués L, Carmona C (2010) Travel time forecasting and dynamic origin-destination estimation for freeways based on bluetooth traffic monitoring. Transp Res Rec 2175:19–27

    Google Scholar 

  • Bell MGH (1983) The estimation of an origin-destination matrix from traffic counts. Transp Sci 17(2):198–217

    Google Scholar 

  • Bierlaire M, Crittin F (2004) An efficient algorithm for real-time estimation and prediction of dynamic OD tables. Oper Res 52(1):116–127

    Google Scholar 

  • Cao P, Miwa T, Yamamoto T, Morikawa T (2013) Bilevel generalized least squares estimation of dynamic origin-destination matrix for urban network with probe vehicle data. Transp Res Rec 2333:66–73

    Google Scholar 

  • Cascetta E, Inaudi D, Marquis G (1993) Dynamic estimators of origin-destination matrices using traffic counts. Transp Sci 27(4):363–373

    Google Scholar 

  • Castillo E, Conejo AJ, Menéndez JM, Jimenez P (2008) The observability problem in traffic network models. Comput-Aided Civ Inf 23(3):208–222

    Google Scholar 

  • Castillo E, Grande Z, Calviño A, Szeto WY, Lo HK (2015) A state-of-the-art review of the sensor location, flow observability, estimation, and prediction problems in traffic networks J Sensors

    Google Scholar 

  • Chiou YC, Lan LW, Tseng CM, Fan CC (2012) Optimal locations of license plate recognition to enhance the origin-destination matrix estimation. Asian Transport Studies 2(1):80–92

    Google Scholar 

  • de Grange L, González F, Bekhor S (2017) Path flow and trip matrix estimation using link flow density. Netw Spat Econ 17(1):173–195

    Google Scholar 

  • Dempster AP, Laird NM, Rubin DB (1977) Maximum likelihood from incomplete data via the EM algorithm. J R Stat Soc B:1–38

  • Djukic T, Barceló J, Bullejos M, Montero L, Cipriani E, van Lint H (2015) Advanced traffic data for dynamic OD demand estimation: the state of the art and benchmark study. In 94th Transportation Research Board of the National Academies, Washington, D.C.

  • Frederix R, Viti F, Tampère CMJ (2013) Dynamic origin-destination estimation in congested networks: theoretical findings and implications in practice. Transportmetrica A 9(6):494–513

    Google Scholar 

  • Ge Q, Fukuda D (2016) Updating origin-destination matrices with aggregated data of GPS traces. Transport Res C Emer 69:291–312

    Google Scholar 

  • Hazelton ML (2001) Inference for origin-destination matrices: estimation, prediction and reconstruction. Transp Res B Methodol 35(7):667–676

    Google Scholar 

  • C, Hendrickson, S, McNeil (1984) Matrix entry estimation errors. Proceedings of the 9th international symposium on transportation and traffic theory. Delft University the Netherlands 413-430

  • Hu SR, Peeta S, Liou HT (2016) Integrated determination of network origin-destination trip matrix and heterogeneous sensor selection and location strategy. IEEE Trans Intell Transp Syst 17(1):195–205

    Google Scholar 

  • Hu X, Chiu YC, Villalobos JA, Nava E (2017) A sequential decomposition framework and method for calibrating dynamic origin-destination demand in a congested network. IEEE Trans Intell Transp Syst 18(10):2790–2797

    Google Scholar 

  • Iqbal MS, Choudhury CF, Wang P, González MC (2014) Development of origin-destination matrices using mobile phone call data. Transport Res C Emer 40:63–74

    Google Scholar 

  • Kerner BS (2009) Introduction to modern traffic flow theory and control: the long road to three-phase traffic theory Springer Science & Business Media

    Google Scholar 

  • Leblanc LJ (1973) Mathematical programming algorithms for large-scale network equilibrium and network design problems. PhD Thesis, Northwestern University

    Google Scholar 

  • Lu CC, Zhou X, Zhang K (2013) Dynamic origin-destination demand flow estimation under congested traffic conditions. Transport Res C Emer 34:16–37

    Google Scholar 

  • Maher MJ (1983) Inferences on trip matrices from observations on link volumes: a Bayesian statistical approach. Transp Res B Methodol 17(6):435–447

    Google Scholar 

  • Ma W, Qian ZS (2018a) Estimating multi-year 24/7 origin-destination demand using high-granular multi-source traffic data. Transport Res C Emer 96:96–121

    Google Scholar 

  • Ma W, Qian ZS (2018b) Statistical inference of probabilistic origin-destination demand using day-to-day traffic data. Transport Res C Emer 88:227–256

    Google Scholar 

  • Nguyen S, Dupuis C (1984) An efficient method for computing traffic equilibria in networks with asymmetric transportation costs. Transp Sci 18(2):185–202

    Google Scholar 

  • Parry K, Hazelton ML (2012) Estimation of origin-destination matrices from link counts and sporadic routing data. Transp Res B Methodol 46(1):175–188

    Google Scholar 

  • Shao H, Lam WHK, Sumalee A, Chen A, Hazelton ML (2014) Estimation of mean and covariance of peak hour origin-destination demands from day-to-day traffic counts. Transp Res B Methodol 68:52–75

    Google Scholar 

  • Shao H, Lam WHK, Sumalee A, Hazelton ML (2015) Estimation of mean and covariance of stochastic multi-class OD demands from classified traffic counts. Transp Res Pro 7:192–211

    Google Scholar 

  • Sheffi Y (1982) Powell W B. an algorithm for the equilibrium assignment problem with random link times. Networks 12(2):191–207

    Google Scholar 

  • Shenoy GV (2007) Linear programming: methods and applications New Age International

    Google Scholar 

  • Sun C, Chang Y, Shi Y, Cheng L, Ma J, (2019a) Subnetwork origin-destination matrix estimation under travel demand constraints. Netw Spat Econ 19(4):1123–1142

  • Sun C, Cheng L, Zhu S, Han F, Chu Z, (2019b) Multi-criteria user equilibrium model considering travel time, travel time reliability and distance. Transp Res D: Transp Environ 66:3–12

  • Toole JL, Colak S, Sturt B, Alexander LP, Evsukoff A, González MC (2015) The path most traveled: travel demand estimation using big data resources. Transport Res C Emer 58:162–177

    Google Scholar 

  • Xie C, Duthie J (2015) An excess-demand dynamic traffic assignment approach for inferring origin-destination trip matrices. Netw Spat Econ 15(4):947–979

    Google Scholar 

  • Yang H, Rakha H (2017) A novel approach for estimation of dynamic from static origin-destination matrices. Transp Lett:1–10

  • Yang Y, Fan Y (2015) Data dependent input control for origin-destination demand estimation using observability analysis. Transp Res B Methodol 78:385–403

    Google Scholar 

  • Yang Y, Fan Y, Royset JO (2019) Estimating probability distributions of travel demand on a congested network. Transp Res B Methodol 122:265–286

    Google Scholar 

  • Yang Y, Fan Y, Wets RJB (2018) Stochastic travel demand estimation: improving network identifiability using multi-day observation sets. Transp Res B Methodol 107:192–211

    Google Scholar 

  • Yin K, Wang W, Wang XB, Adams TM (2015) Link travel time inference using entry/exit information of trips on a network. Transp Res B Methodol 80:303–321

    Google Scholar 

  • Ying L, Zhu J, Huiyan W, Zhenyu L (2016) A novel method for estimation of dynamic OD flow. Procedia engineering 137:94–102

    Google Scholar 

  • Zhang H, Nie Y, Qian Z (2008) Estimating time-dependent freeway origin-destination demands with different data coverage: sensitivity analysis. Transp Res Rec 2047:91–99

    Google Scholar 

  • Zhou X, Mahmassani HS (2006) Dynamic origin-destination demand estimation using automatic vehicle identification data. IEEE Trans Intell Transp Syst 7(1):105–114

    Google Scholar 

  • Zhou X, Mahmassani HS (2007) A structural state space model for real-time traffic origin-destination demand estimation and prediction in a day-to-day learning framework. Transp Res B Methodol 41(8):823–840

    Google Scholar 

  • Zhou X, Qin X, Mahmassani H (2003) Dynamic origin-destination demand estimation with multiday link traffic counts for planning applications. Transp Res Rec 1831:30–38

    Google Scholar 

Download references

Acknowledgements

The authors are grateful to the anonymous referees for their constructive comments and suggestions to improve the quality and clarity of the paper. This research is supported by the National Natural Science Foundation of China (No. 71801115), the National Key Research and Development Program of China (No. 2018YFB1600503), the Natural Science Foundation of Jiangsu Province (No. BK20190845), and the Transportation Technology and Achievement Transformation Project of Jiangsu Province (No. JSZC-G2018-176).

Author information

Authors and Affiliations

  1. School of Automotive and Traffic Engineering, Jiangsu University, No. 301, Xuefu Road, Zhenjiang, 212013, China

    Chao Sun & Yulin Chang

  2. School of Transportation, Southeast University, No. 2, Si Pai Lou, Nanjing, 210096, China

    Xin Luan & Qiang Tu

  3. School of Automobile and Traffic engineering, Nanjing Forestry University, Road, Chaoyang, 210037, China

    Wenyun Tang

Authors
  1. Chao Sun
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yulin Chang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xin Luan
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Qiang Tu
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Wenyun Tang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Chao Sun.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sun, C., Chang, Y., Luan, X. et al. Origin-Destination Demand Reconstruction Using Observed Travel Time under Congested Network. Netw Spat Econ 20, 733–755 (2020). https://doi.org/10.1007/s11067-020-09496-4

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11067-020-09496-4

Keywords

Search

Navigation