Primal–Dual Heuristic for Path Flow Estimation in Medium to Large Networks
Abstract
The path flow estimator, an origin–destination demand estimation algorithm that relies on the computation of path flows, can be slow when applied to medium to large networks. A primal–dual heuristic that can significantly improve the computational efficiency of the algorithm when it is applied to large networks is developed. Numerical examples are provided to show the performance improvement of this primal–dual heuristic over the original path flow estimator algorithm.
Get full access to this article
View all access and purchase options for this article.
References
1. Bell M. G. H., and Iida Y. Transportation Network Analysis. John Wiley and Sons, Hoboken, N.J., 1997.
2. Cascetta E. Transportation Systems Engineering: Theory and Methods. Springer, Berlin, 2001.
3. Ortuzar J., and Willumsen L. G. Modelling Transport. John Wiley and Sons, Hoboken, N.J., 1994.
4. Willumsen L. Simplified Transport Models Based on Traffic Counts. Transportation, Vol. 10, No. 3, 1981, pp. 257–278.
5. Van Zuylen H. J., and Willumsen L. G. The Most Likely Trip Matrix Estimated from Traffic Counts. Transportation Research Part B: Methodological, Vol. 14, No. 3, 1980, pp. 281–293.
6. Cascetta E. Estimation of Trip Matrices from Traffic Counts and Survey Data: A Generalized Least Squares Estimator. Transportation Research Part B: Methodological, Vol. 18, No. 4, 1984, pp. 289–299.
7. Bell M. G. H. The Estimation of Origin-Destination Matrices by Constrained Generalised Least Squares. Transportation Research Part B: Methodological, Vol. 25, No. 1, 1991, pp. 13–22.
8. Bell M. G. H. The Estimation of an Origin-Destination Matrix from Traffic Counts. Transportation Science, Vol. 17, No. 2, 1983, pp. 198–217.
9. McNeil S., and Hendrickson C. A Regression Formulation of the Matrix Estimation Problem. Transportation Science, Vol. 19, No. 3, 1985, pp. 278–292.
10. Lo H., Zhang N., and Lam W. Estimation of an Origin-Destination Matrix with Random Link Choice Proportions: A Statistical Approach. Transportation Research Part B: Methodological, Vol. 30, No. 4, 1996, pp. 309–324.
11. Nguyen S. Estimating Origin Destination Matrices from Observed Flows. Elsevier Science Publishers BV, Amsterdam, Netherlands, 1984.
12. Nguyen S. Estimating an O-D Matrix from Network Data: A Network Equilibrium Approach. Technical Report 60. University of Montreal, Canada, 1977.
13. Turnquist M., and Gur Y. Estimation of Trip Tables from Observed Link Volumes. In Transportation Research Record 730, TRB, National Research Council, Washington, D.C., 1979, pp. 1–6.
14. LeBlanc L. J., and Farhangian K. Selection of a Trip Table Which Reproduces Observed Link Flows. Transportation Research Part B: Methodological, Vol. 16, No. 2, 1982, pp. 83–88.
15. Sheffi Y. Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice Hall, Inc., Englewood Cliffs, N.J., 1985.
16. Yang H., Sasaki T., Iida Y., and Asakura Y. Estimation of Origin-Destination Matrices from Link Traffic Counts on Congested Networks. Transportation Research Part B: Methodological, Vol. 26, No. 6, 1992, pp. 417–434.
17. Yang H. Heuristic Algorithms for the Bilevel Origin-Destination Matrix Estimation Problem. Transportation Research Part B: Methodological, Vol. 29, No. 4, 1995, pp. 231–242.
18. Spiess H. A Maximum Likelihood Model for Estimating Origin-Destination Matrices. Transportation Research Part B: Methodological, Vol. 21, No. 5, 1987, pp. 395–412.
19. Maher M. Inferences on Trip Matrices from Observations on Link Volumes: A Bayesian Statistical Approach. Transportation Research Part B: Methodological, Vol. 17, No. 6, 1983, pp. 435–447.
20. Fisk C., and Boyce D. A Note on Trip Matrix Estimation from Link Traffic Count Data. Transportation Research Part B: Methodological, Vol. 17, No. 3, 1983, pp. 245–250.
21. Fisk C. On Combining Maximum Entropy Trip Matrix Estimation with User Optimal Assignment. Transportation Research Part B: Methodological, Vol. 22, No. 1, 1988, pp. 69–73.
22. Maher M. J., Zhang X., and Vliet D. V. A Bilevel Programming Approach for Trip Matrix Estimation and Traffic Control Problems with Stochastic User Equilibrium Link Flows. Transportation Research Part B: Methodological, Vol. 35, No. 1, 2001, pp. 23–40.
23. Sherali H. D., Sivanandan R., and Hobeika A. G. A Linear Programming Approach for Synthesizing Origin-Destination Trip Tables from Link Traffic Volumes. Transportation Research Part B: Methodological, Vol. 28, No. 3, 1994, pp. 213–233.
24. Nie Y., and Lee D.-H. Uncoupled Method for Equilibrium-Based Linear Path Flow Estimator for Origin-Destination Trip Matrices. In Transportation Research Record: Journal of the Transportation Research Board, No. 1783, Transportation Research Board of the National Academies, Washington, D.C., 2002, pp. 72–79.
25. Nie Y., Zhang H., and Recker W. Inferring Origin-Destination Trip Matrices with a Decoupled GLS Path Flow Estimator. Transportation Research Part B: Methodological, Vol. 39, No. 6, 2005, pp. 497–518.
26. Bell M. G. H., Shield C. M., Busch F., and Kruse G. A Stochastic User Equilibrium Path Flow Estimator. Transportation Research Part C: Emerging Technologies, Vol. 5, No. 3-4, 1997, pp. 197–210.
27. Chootinan P., Chen A., and Recker W. W. Improved Path Flow Estimator for Origin-Destination Trip Tables. In Transportation Research Record: Journal of the Transportation Research Board, No. 1923, Transportation Research Board of the National Academies, Washington, D.C., 2005, pp. 9–17.
28. Chen A., Ryu S., and Chootinan P. L∞-Norm Path Flow Estimator for Handling Traffic Count Inconsistencies: Formulation and Solution Algorithm. Journal of Transportation Engineering, ASCE, Vol. 136, No. 6, 2010, pp. 565–575.
29. Lam W., and Lo H. Accuracy of O-D Estimates from Traffic Counts. Traffic Engineering & Control, Vol. 31, No. 6, 1990, pp. 358–367.
Cite article
Cite article
Cite article
OR
Download to reference manager
If you have citation software installed, you can download article citation data to the citation manager of your choice
Information, rights and permissions
Information
Published In
Article first published online: January 1, 2013
Issue published: January 2013
Authors
Metrics and citations
Metrics
Journals metrics
This article was published in Transportation Research Record: Journal of the Transportation Research Board.
VIEW ALL JOURNAL METRICSArticle usage*
Total views and downloads: 15
*Article usage tracking started in December 2016
Altmetric
See the impact this article is making through the number of times it’s been read, and the Altmetric Score.
Learn more about the Altmetric Scores
Articles citing this one
Receive email alerts when this article is cited
Web of Science: 0
Crossref: 6
- Semi-dynamic Markovian path flow estimator considering the inconsisten...
- A Demand Estimator Based on a Nested Logit Model
- Path Flow and Trip Matrix Estimation Using Link Flow Density
- Path Flow Estimator in an Entropy Model Using a Nonlinear L-Shaped Alg...
- A Bi-Level Model to Estimate the US Air Travel Demand
- Heuristics to Improve Efficiency of Solution Algorithm of Path Flow Es...
Figures and tables
Figures & Media
Tables
View Options
Get access
Access options
If you have access to journal content via a personal subscription, university, library, employer or society, select from the options below:
loading institutional access options
Alternatively, view purchase options below:
Purchase 24 hour online access to view and download content.
Access journal content via a DeepDyve subscription or find out more about this option.
