Origin-Based Partial Linearization Method for the Stochastic User Equilibrium Traffic Assignment Problem
Publication: Journal of Transportation Engineering
Volume 136, Issue 1
Abstract
This paper proposes a modified origin-based partial linearization method for solving the logit-based stochastic user equilibrium traffic assignment problem formulated by a strictly convex minimization model in terms of origin-based link flows. As a feasible descent direction method, it first generates a feasible descent direction in terms of the origin-based link flows by Bell’s second logit-based stochastic network loading algorithm without path enumeration, and it proceeds to improve the descent direction according to the Fukushima’s strategy and the PARTAN technique which haven been successfully applied to accelerate convergence of the link-based Frank-Wolfe method for solving the deterministic user equilibrium traffic assignment problem. To tackle the numerical overflow or underflow issue of the exponential function calculation arising in the computerized logit-based stochastic network loading algorithms, this paper develops a scientific notation based engineering approach for large-scale problems. Two numerical examples are carried out to compare the proposed solution method with the conventional origin-based partial linearization method and the method of successive averages in computational time and accuracy of solution.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The writers thank Jianghang Chen and Zhiyuan Liu from Department of Civil Engineering, National University of Singapore for their assistance in conducting numerical experiments. This research was mainly supported by Ministry of Education, Singapore, through a research grant from National University of Singapore (Grant No. UNSPECIFIEDR-264-000-200-112).
References
Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. (1993). Network flows: Theory, algorithm and applications, Prentice-Hall, Upper Saddle River, N.J.
Akamatsu, T. (1996). “Cyclic flows, Markov process and stochastic traffic assignment.” Transp. Res., Part B: Methodol., 30(5), 369–386.
Akamatsu, T. (1997). “Decomposition of path choice entropy in general transport networks.” Transp. Sci., 31(4), 349–362.
Arezki, Y., and Van Vliet, D. (1990). “A full analytical implementation of the PARTAN/Frank-Wolfe algorithm for equilibrium assignment.” Transp. Sci., 24(1), 58–62.
Bar-Gera, H. (2002). “Origin-based algorithm for the traffic assignment problem.” Transp. Sci., 36(4), 398–417.
Bar-Gera, H., and Boyce, D. (2003). “Origin-based algorithms for combined travel forecasting models.” Transp. Res., Part B: Methodol., 37, 405–422.
Beckmann, M., McGuire, C. B., and Winsten, C. B. (1956). Studies in the economics of transportation, Yale University Press, New Haven, Conn.
Bell, M. G. H. (1995). “Alternatives to Dial’s logit assignment algorithm.” Transp. Res., 29(4), 287–295.
Bertsekas, D., Gafni, E., and Gallager, G. (1984). “Seconding derivative algorithms for minimum delay distributed routing in networks.” IEEE Trans. Commun., 32(8), 911–919.
Bertsekas, D. P., and Gafni, E. M. (1983). “Projected Newton methods and optimization of multicommodity flow.” IEEE Trans. Autom. Control, 28, 1090–1096.
Boyce, D., Ralevic-Dekic, B., and Bar-Gera, H. (2004). “Convergence of traffic assignments: How much is enough?” J. Transp. Eng., 130(1), 49–55.
Bruynooghe, M., Gibert, A., and Sakarovitch, M. (1969). “Une méthode d’affectation du traffic.” Proc., 4th Int. Symp. on the Theory of Road Traffic Flow, W. Leutzbach and P. Baron, eds., Univ. of Karlsruhe, Karlsruhe, Germany, 198–204.
Dafermos, S. C. (1968). “Traffic assignment and resource allocation for transportation network.” Ph.D. thesis, Johns Hopkins Univ., Baltimore, Md.
Daganzo, C. F. (1982). “Unconstrained extremal formulation of some transportation equilibrium problems.” Transp. Sci., 16(3), 332–360.
Damberg, O., Lundgren, J. L., and Patriksson, M. (1996). “An algorithm for the stochastic user equilibrium problem.” Transp. Res., Part B: Methodol., 30(2), 115–131.
Dial, R. B. (1971). “A probabilistic multipath traffic assignment algorithm which obviates path enumeration.” Transp. Res., 5(2), 83–111.
Dial, R. B. (2006). “A path-based user-equilibrium traffic assignment algorithm that obviates path storage and enumeration.” Transp. Res., Part B: Methodol., 40, 917–936.
Fisk, C. (1980). “Some developments in equilibrium traffic assignment.” Transp. Res., Part B: Methodol., 14(3), 243–255.
Florian, M. (1977). “An improved linear approximation algorithm for the network equilibrium (packet switching) problem.” Proc., 10th IEEE Conf. on Decision and Control, IEEE Control System Society, New Orleans, 812–818.
Florian, M., Guelat, J., and Spiess, H. (1987). “An efficient implementation of the ‘PARTAN’ variant of the linear approximation method for the network equilibrium problem.” Networks, 17(3), 319–339.
Florian, M., and Hearn, D. (1995). “Network equilibrium models and algorithms.” Network Routing, 8, 485–550.
Fukushima, M. (1984). “A modified Frank-Wolfe algorithm for solving the traffic assignment problem.” Transp. Res., Part B: Methodol., 18(2), 169–177.
Gibert, A. (1968). “A method for the traffic assignment problem.” Rep. No. LBS-TNT-95, Transportation Network Theory Unit, London Business School, London.
Jayakrishnan, R., Tsai, W. K., Prashker, J. N., and Rajadhyaksha, S. (1994). “A fast path-based algorithm for traffic assignment.” Transp. Res. Rec., 1443, 75–83.
Larsson, T., and Patriksson, M. (1992). “Simplicial decomposition with disaggregated representation for the traffic assignment problem.” Transp. Sci., 26, 4–17.
LeBlanc, L. J. (1973). “Mathematical programming algorithms for large scale network equilibrium and network design problem.” Ph.D. thesis, Northwestern Univ., Evanston, Ill.
LeBlanc, L. J., Helgason, R. V., and Boyce, D. E. (1985). “Improved efficiency of the Frank-Wolfe algorithm for convex network problems.” Transp. Sci., 19(4), 445–462.
LeBlanc, L. J., Morlok, E. K., and Pierskalla, W. P. (1975). “An efficient approach to solving the road network equilibrium traffic assignment problem.” Transp. Res., 9, 309–318.
Luenberger, D. G. (1973). Introduction to linear and nonlinear programming, Addison-Wesley, Reading, Mass.
Patriksson, M. (1994). The traffic assignment problem: Models and methods, VSP, Utrecht, The Netherlands.
Powell, W. B., and Sheffi, Y. (1982). “The convergence of equilibrium algorithm with predetermined step sizes.” Transp. Sci., 16(1), 45–55.
Sheffi, Y. (1985). Urban transportation networks: Equilibrium analysis with mathematical programming methods, Prentice-Hall, Englewood Cliffs, N.J.
Wolfe, P. (1970). Convergent theory in nonlinear programming: Integer and nonlinear programming, J. Abadies, ed., North-Holland, Amsterdam, 1–36.
Zangwill, W. I. (1969). Nonlinear programming: A unified approach, Prentice-Hall, Englewood Cliffs, N.J.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 136 • Issue 1 • January 2010
Pages: 52 - 60
Copyright
© 2010 ASCE.
History
Received: Apr 28, 2005
Accepted: Sep 1, 2009
Published online: Dec 15, 2009
Published in print: Jan 2010
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.