Faster Frank-Wolfe Traffic Assignment with New Flow Update Scheme
Publication: Journal of Transportation Engineering
Volume 128, Issue 1
Abstract
The most widely used algorithm for solving traffic assignment problems is the Frank-Wolfe (FW) algorithm. Its popularity is attributed to its modest memory requirements and simplicity. However, it is also known that FW converges very slowly. This paper describes a method to accelerate the performance of the FW algorithm. It utilizes path information to speed the convergence of the algorithm by updating the flow pattern one origin-destination (OD) at a time. The results indicate that a FW implementation with an OD-based flow update takes less iteration to reach convergence but requires more computational times per iteration. This computational burden is due to the fact that the flow update of each OD pair requires a separate line search, which demands a significant amount of computational times, making it only competitive to the standard FW algorithm in some extreme cases. However, since the OD-based Frank-Wolfe algorithm takes fewer iterations to reach convergence, it requires much less computer storage and thus, is a better alternative to the standard FW if path-flow solutions are to be derived from a link-flow based FW algorithm.
Get full access to this article
View all available purchase options and get full access to this article.
References
Arezki, Y., and Van Vliet, D.(1985). “The use of quantal loading in equilibrium traffic assignment.” Transp. Res., 19B, 521–525.
Arezki, Y., and Van Vliet, D.(1990). “A full analytical implementation of the PARTAN/Frank-Wolfe Algorithm for equilibrium assignment.” Transp. Sci., 24, 58–62.
Bar-Gera, H., and Boyce, D. E. (2000). “Origin Based Network Assignment.” Advances in Transportation Network Modelling, M. Patriksson, ed., Kluwer Academic, Boston, in press.
Bertsekas, D. P., and Gafni, E. M.(1983). “Projected Newton methods and optimization of multicommodity flows.” IEEE Trans. Autom. Control, 28(1), 1090–1096.
Chen, A., and Jayakrishnan, R. (1996). “Path and link flow based assignment algorithms: Finding and storing path-flow solutions and computational performance.” ITS Working Paper, Univ. of California, Irvine, Calif.
Chen, A., and Jayakrishnan, R. (1998). “A path-based gradient projection algorithm: Effects of equilibration with a restricted path set under two flow update policies.” Transportation Research Board, Washington, D.C.
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, 319–339.
Fukushima, M.(1984). “A modified Frank-Wolfe Algorithm for solving the traffic assignment problem.” Transp. Res., 18B, 169–177.
Hearn, D. W., Lawphongpanich, S., and Ventura, J. A.(1985). “Finiteness in restricted simplicial decomposition.” Operations Research Letters, 4(3), 125–130.
Holloway, C. A.(1974). “An extension of the Frank-Wolfe method of feasible directions.” Math. Program., 6, 14–27.
Larsson, T., and Patriksson, M.(1992). “Simplicial decomposition with disaggregate representation for the traffic assignment problem.” Transp. Sci., 26, 4–17.
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, 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.
Leonard, D. R., Gower, P., and Taylor, N. B. (1989). CONTRAM 5, “Structure of the model.” TRRL Rep. RR 178, Dept. of Transport, Transport and Road Research Laboratory, Crowthorne.
Nguyen, S. (1976). “A unified approach to equilibrium methods for traffic assignment.” Traffic equilibrium methods, M. A. Florian, ed., Vol. 118: Lecture notes in economics and mathematical systems, Springer-Verlag, 148–182.
Patriksson, M. (1994). The traffic assignment problem: Models and methods, VSP, Utrecht, The Netherlands.
Sheffi, Y. (1985). Urban traffic networks: Equilibrium analysis with mathematical programming methods, Prentice-Hall, Englewood Cliffs, N.J.
Weintraub, A., Ortiz, C., and Gonzalez, J.(1985). “Accelerating convergence of the Frank-Wolfe algorithm.” Transp. Res., 19B, 113–122.
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 128 • Issue 1 • January 2002
Pages: 31 - 39
Copyright
Copyright © 2002 American Society of Civil Engineers.
History
Received: Apr 4, 2000
Accepted: Jul 17, 2000
Published online: Jan 1, 2002
Published in print: Jan 2002
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.