Abstract
In this paper we propose a new iterative method for solving the asymmetric traffic equilibrium problem when formulated as a variational inequality whose variables are the path flows. The path formulation leads to a decomposable structure of the constraints set and allows us to obtain highly accurate solutions. The proposed method is a column generation scheme based on a variant of the Khobotov’s extragradient method for solving variational inequalities. Computational experiments have been carried out on several networks of a medium-large scale. The results obtained are promising and show the applicability of the method for solving large-scale equilibrium problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bar-Gera. H.: Transportation network test problems. http://www.bgu.ac.il/∼bargera/tntp/.
Beckmann M.J., McGuire C.B., Winsten C.B. (1956) Studies in the economics of transportation. Yale University Press, New Haven
Bertsekas D.P., Gafni E.M. (1982) Projection methods for variational inequalities with application to the traffic assignment problem. Math. Program. Study 17, 139–159
Chen A., Lee D.-H., Jayakrishnan R. (2002) Computational study of state-of-the-art path-based traffic assignment algorithms. Math. Comput. Simul. 59, 509–518
Chen A., Lee D.-H., Nie Y. (2003) A conjugate gradient projection algorithm for the traffic assignment problem. Math. Comput. Model. 37, 863–878
Dafermos S. (1980) Traffic equilibrium and variational inequalities. Transp. Sci. 14, 42–54
Dafermos S., Sparrow F. (1969) The traffic assignment problem for a general network. J. Res. Natl. Bur. Stand. 73B, 91–118
Dijkstra E.W. (1959) A note on two problems in connexion with graphs. Numer. Math. 1, 269–271
Bernstein D., Gabriel S.A. (1997) The traffic equilibrium problem with nonadditive path costs. Transp. Sci. 31, 337–348
Kanninen B.J. (1996) Intelligent transportation systems: an economic and environmental policy assessment. Transp. Res. 30A: 1–10
Khobotov E.N. (1987) Modification of the extra-gradient method for solving variational inequalities and certain optimization problems. USSR Comput. Math. Math. Phys. 27, 120–127
Larsson T., Lundgren J.T., Rydergren C., Patriksson M. Most likely traffic equilibrium route flows analysis and computation. In: Equilibrium Problems: Nonsmooth Optimization and Variational Inequality Methods, pp. 129–159, vol 58. Nonconvex Optim. Appl., Kluwer, Dordrecht (2001)
Leventhal T., Nemhauser G., Trotter L. (1973) A column generation algorithm for optimal traffic assignment. Transp. Sci. 7, 168–172
Marcotte P. (1991) Application of Khobotov’s algorithm to variational inequalities and network equilibrium problems. INFOR 29, 258–270
Michelot C. (1986) A finite algorithm for finding the projection of a point onto the canonical simplex of \(\mathbb{R}^{n}\). J. Optim. Theory Appl. 50, 195–200
Nagurney A. (1993) Network Economics: a Variational Inequality Approach. Kluwer, Dordrecht
Nagurney A. (1984) Comparative tests of multimodal traffic equilibrium methods. Transp. Res. 18B: 469–485
Nagurney A., Zhang D. (1997) Projected dynamical systems in the formulation, stability analysis, and computation of fixed-demand traffic network equilibria. Transp. Sci. 31, 147–158
Nagurney A., Zhang D. (1996) Projected dynamical systems and variational inequalities with applications. Kluwer, Boston
Nguyen S., Dupuis C. (1984) An efficient method for computing traffic equilibria in networks with asymmetric transportation costs. Transp. Sci. 18, 185–202
Passacantando M. Transportation network test problems. http://www2.ing.unipi.it/∼d9762/
Patriksson M. (2004) Algorithms for computing traffic equilibria. Netw. Spat. Econ. 4, 23–38
Smith M.J. (1979) The existence, uniqueness and stability of traffic equilibria. Transp. Res. 13B: 295–304
Solodov M.V., Svaiter B.F. (1999) A new projection method for variational inequality problems. SIAM J. Control Optim. 37, 765–776
Wardrop J.G. (1952) Some theoretical aspects of road traffic research. Proc. Inst. Civil Eng. 1, 325–378
Author information
Authors and Affiliations
Corresponding author
Additional information
This work has been supported by the National Research Program FIRB/RBNE01WBBBB on Large Scale Nonlinear Optimization.
Rights and permissions
About this article
Cite this article
Panicucci, B., Pappalardo, M. & Passacantando, M. A path-based double projection method for solving the asymmetric traffic network equilibrium problem. Optimization Letters 1, 171–185 (2007). https://doi.org/10.1007/s11590-006-0002-9
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-006-0002-9