Heuristics to Improve Efficiency of Solution Algorithm of Path Flow Estimator
Abstract
The path flow estimator (PFE) proposed by Bell and Shield in 1997 is an important demand estimator in ground transportation. The PFE is formulated as a nonlinear optimization model and solved by the iterative balancing solution algorithm given by Bell in 1995. This paper presents several theoretical results about the solution algorithm. In particular, the solution algorithm is shown to maximize the dual problem of the PFE sequentially along the directions defined by unit vectors. A closed-form relationship was identified between the increase in the objective of the dual problem and the optimal step length along each direction. In addition, three heuristics were developed to improve the computational efficiency of the solution algorithm. The first heuristic reduced the computational effects that could not yield significant increases to the objective value of the dual. The second reduced the probability of yielding marginal increases to the objective value of the dual. The third sped up convergence by partially avoiding zigzagging (i.e., approaching the optimal solution in small steps along perpendicular directions). The heuristics could be applied simultaneously with each other or with the methods developed to determine better initial values. The three heuristics were applied to a large-sized network, and the computational results were generally consistent with the theoretical results.
Get full access to this article
View all access and purchase options for this article.
References
Maher M. J. 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.
Bell M. G. H. The Estimation of an Origin-Destination Matrix from Traf-fic Counts. Transportation Science, Vol. 17, No. 2, 1983, pp. 198–217.
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.
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–5, 1984, pp. 289–299.
McNeil S., and Hendrickson C. A Regression Formulation of the Matrix Estimation Problem. Transportation Science, Vol. 19, No. 3, 1985, pp. 278–292.
Spiess H. A Maximum Likelihood Model for Estimating Origin-Destination Matrices. Transportation Research Part B: Methodological, Vol. 21, No. 5, 1987, pp. 395–412.
Barbour R., and Fricker J. D. Estimating an Origin-Destination Table Using a Method Based on Shortest Augmenting Paths. Transportation Research Part B: Methodological, Vol. 28, No. 2, 1994, pp. 77–89.
Bierlaire M., and Toint P. L. Meuse: An Origin-Destination Matrix Estimator that Exploits Structure. Transportation Research Part B: Methodological, Vol. 29, No. 1, 1995, pp. 47–60.
Lo H. P., Zhang N., and Lam W. H. K. 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.
Nguyen S. Estimating an OD Matrix from Network Data: A Network Equilibrium Approach. Publication 87. Centre de Recherche sur les Transports, University of Montreal, Quebec, Canada, 1977.
Jörnsten K. O., and Nguyen S. On the Estimation of a Trip Matrix from Network Data, Vol 1. Linköping Institute of Technology, Linköping, Sweden, 1979.
Gur Y. J., Turnquist M., Schneider M., Leblanc L., and Kurth D. Estimation of an Origin–Destination Trip Table Based on Observed Link Volumes and Turning Movements, Vo l 1. RD-80/034. FHWA, U.S. Department of Transportation, 1980.
Spiess H. A Gradient Approach for the O-D Matrix Adjustment Problem. Centre de Recherche sur les Transports, University of Montreal, Quebec, Canada, 1990.
Yang H., Meng Q., and Bell M. G. H. Simultaneous Estimation of the Origin-Destination Matrices and Travel-Cost Coefficient for Congested Networks in a Stochastic User Equilibrium. Transportation Science, Vol. 35, No. 2, 2001, pp. 107–123.
Doblas J., and Benitez F. G. An Approach to Estimating and Updating Origin–Destination Matrices Based upon Traffic Counts Preserving the Prior Structure of a Survey Matrix. Transportation Research Part B: Methodological, Vol. 39, No. 7, 2005, pp. 565–591.
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.
Florian M., and Chen Y. A Successive Linear Approximation Method for the O–D Matrix Adjustment Problem. Centre de Recherche sur les Transports, University of Montreal, Quebec, Canada, 1992.
Florian M., and Yang C. A Coordinate Descent Method for the Bi-Level O-D Matrix Adjustment Problem. International Transactions in Operational Research, Vol. 2, No. 2, 1995, pp. 165–179.
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.
Maher M. J., Zhang X., and Vliet D. V. A Bi-Level 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.
Codina E., and Barceló J. Adjustment of O–D Trip Matrices from Observed Volumes: An Algorithmic Approach Based on Conjugate Directions. European Journal of Operational Research, Vol. 155, No. 3, 2004, pp. 535–557.
Lundgren J. T., and Peterson A. A Heuristic for the Bilevel Origin–Destination-Matrix Estimation Problem. Transportation Research Part B: Methodological, Vol. 42, No. 4, 2008, pp. 339–354.
Fisk C. S. On Combining Maximum Entropy Trip Matrix Estimation with User Optimal Assignment. Transportation Research Part B: Methodological, Vol. 22, No. 1, 1988, pp. 69–73.
Shihsien L., and Fricker J. D. Estimation of a Trip Table and the Θ Parameter in a Stochastic Network. Transportation Research Part A: Policy and Practice, Vol. 30, No. 4, 1996, pp. 287–305.
Flötteröd G., Bierlaire M., and Nagel K. Bayesian Demand Calibration for Dynamic Traffic Simulations. Transportation Science, Vol. 45, No. 4, 2011, pp. 541–561.
Li T. A Bi-Level Model to Estimate the US Air Travel Demand. Asia-Pacific Journal of Operational Research, Vol. 32, No. 2, 2015, pp. 1–34.
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.
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.
Nie Y., Zhang H. M., and Recker W. 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.
Bell M. G. H., and Shield C. M. A Log-Linear Model for Path Flow Estimation. Proc., International Conference on Applications of Advanced Technologies in Transportation Engineering, Capri, Italy, 1996, ASCE, Reston, Va., pp. 695–699.
Bell M. G. H., and Shield C. M. A Stochastic User Equilibrium Path Flow Estimator. Transportation Research Part C: Emerging Technologies, Vol. 5, No. 34, 1997, pp. 197–210.
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.
Chen A., Chootinan P., and Recker W. Examining the Quality of Synthetic Origin–Destination Trip Table Estimated by Path Flow Estimator. Journal of Transportation Engineering, Vol. 131, No. 7, 2005, pp. 506–513.
Chen A., Chootinan P., and Recker W. Norm Approximation Method for Handling Traffic Count Inconsistencies in Path Flow Estimator. Transportation Research Part B: Methodological, Vol. 43, No. 8–9, 2009, pp. 852–872.
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, Vol. 136, No. 6, 2010, pp. 565–575.
Chootinan P., and Chen A. Confidence Interval Estimation for Path Flow Estimator. Transportation Research Part B: Methodological, Vol. 45, No. 10, 2011, pp. 1680–1698.
Lam W. H. K., and Xu G. A Traffic Flow Simulator for Network Reliability Assessment. Journal of Advanced Transportation, Vol. 33, No. 2, 1999, pp. 159–182.
Lee M., Chen A., Chootinan P., Laabs W., and Recker W. Modeling Network Traffic for Planning Applications in a Small Community. Journal of Urban Planning and Development, Vol. 132, No. 3, 2006, pp. 156–159.
Chen A., Chootinan P., Ryu S., Lee M., and Recker W. An Intersection Turning Movement Estimation Procedure Based on Path Flow Estimator. Journal of Advanced Transportation, Vol. 46, No. 2, 2012, pp. 161–176.
Jansuwan S., Chen A., and Ryu S. Alternative Planning Tool for Small Metropolitan Planning Organization in Utah. In Transportation Research Record: Journal of the Transportation Research Board, No. 2307, Transportation Research Board of the National Academies, Washington, D.C., 2012, pp. 68–79.
Li T., Baik H., and Trani A. A. A Method to Estimate the Historical US Air Travel Demand. Journal of Advanced Transportation, Vol. 47, No. 3, 2013, pp. 249–265.
Bell M. G. H. Stochastic User Equilibrium Assignment in Networks with Queues. Transportation Research Part B: Methodological, Vol. 29, No. 2, 1995, pp. 125–137.
Tang S., and Zhang H. M. Primal-Dual Heuristic for Path Flow Estimation in Medium to Large Networks. In Transportation Research Record: Journal of the Transportation Research Board, No. 2333, Transportation Research Board of the National Academies, Washington, D.C., 2013, pp. 91–99.
Bazaraa M. S., Sherali H. D., and Shetty C. M. Nonlinear Programming: Theory and Algorithms. Wiley-Interscience, Hoboken, N.J., 2006.
Transportation Network Test Problems. http://www.bgu.ac.il/∼bargera/tntp. Accessed Nov. 15, 2014.
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, 2015
Issue published: January 2015
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: 16
*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: 2
- Estimating the geographic distribution of originating air travel deman...
- A Demand Estimator Based on a Nested Logit Model
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.
