×

A self-adaptive projection and contraction algorithm for the traffic assignment problem with path-specific costs. (English) Zbl 1077.90516

Summary: This paper considers solving a special case of the nonadditive traffic equilibrium problem presented by S. A. Gabriel and D. Bernstein [Transp. Sci. 31, No. 4, 337–348 (1997; Zbl 0920.90058)] in which the cost incurred on each path is made up of the sum of the arc travel times plus a path-specific cost for traveling on that path. A self-adaptive projection and contraction method is suggested to solve the path-specific cost traffic equilibrium problem, which is formulated as a nonlinear complementarity problem (NCP). The computational effort required per iteration is very modest. It consists of only two function evaluations and a simple projection on the nonnegative orthant. A self-adaptive technique is embedded in the projection and contraction method to find suitable scaling factor without the need to do a line search. The method is simple and has the ability to handle a general monotone mapping \(F\). Numerical results are provided to demonstrate the features of the projection and contraction method.

MSC:

90B20 Traffic problems in operations research
90C35 Programming involving graphs or networks

Citations:

Zbl 0920.90058
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aashtiani, H., 1979. The multi-modal traffic assignment problem. Ph.D. Thesis, Operations Research Center, MIT, Cambridge, MA; Aashtiani, H., 1979. The multi-modal traffic assignment problem. Ph.D. Thesis, Operations Research Center, MIT, Cambridge, MA
[2] Bazaraa, M.; Sherali, H.; Shetty, C., Nonlinear Programming: Theory and Algorithms (1993), Wiley: Wiley New York · Zbl 0774.90075
[3] Bernstein, D., Gabriel, G., 1997. Solving the nonadditive traffic equilibrium problem. In: Pardalos, P., Hearn, D., Hager, W. (Eds.), Proceedings of the Network Optimization Conference. Springer, New York, pp. 72-102; Bernstein, D., Gabriel, G., 1997. Solving the nonadditive traffic equilibrium problem. In: Pardalos, P., Hearn, D., Hager, W. (Eds.), Proceedings of the Network Optimization Conference. Springer, New York, pp. 72-102 · Zbl 0878.90030
[4] Cascetta, E., Russo, F., Vitetta, A., 1997. Stochastic user equilibrium assignment with explicit path enumeration: Comparison of models and algorithms. In: Proceedings of the International Federation of Automatic Control: Transportation Systems. Chania, Greece, pp. 1078-1084; Cascetta, E., Russo, F., Vitetta, A., 1997. Stochastic user equilibrium assignment with explicit path enumeration: Comparison of models and algorithms. In: Proceedings of the International Federation of Automatic Control: Transportation Systems. Chania, Greece, pp. 1078-1084
[5] Chen, A., Lee, D.-H., 1999. Path-based algorithms for large scale traffic equilibrium problem: A comparison between DSD and GP. Paper presented at the 79th Annual Meeting of Transportation Research Board; Chen, A., Lee, D.-H., 1999. Path-based algorithms for large scale traffic equilibrium problem: A comparison between DSD and GP. Paper presented at the 79th Annual Meeting of Transportation Research Board
[6] Eaves, B. C., On the basic theorem of complementarity, Mathematical Programming, 1, 68-85 (1971) · Zbl 0227.90044
[7] Fischer, A., A special Newton-type optimization method, Optimization, 24, 269-284 (1992) · Zbl 0814.65063
[8] Gabriel, S.; Bernstein, D., The traffic equilibrium problem with nonadditive path costs, Transportation Science, 31, 4, 337-348 (1997) · Zbl 0920.90058
[9] Gabriel, S.; Bernstein, D., Nonadditive shortest paths: subprobelms in multi-agent competitive network model, Computational and Mathematical Organization Theory, 6, 1, 29-45 (2000)
[10] He, B. S., A projection and contraction method for a class of linear complementarity problems and its application in convex quadratic programming, Applied Mathematics and Optimization, 25, 247-262 (1992) · Zbl 0767.90086
[11] He, B. S., On a class of iterative projection and contraction methods for linear programming, Journal of Optimization Theory and Applications, 78, 247-266 (1993) · Zbl 0792.90042
[12] He, B. S., A new method for a class of linear variational inequalities, Mathematical Programming, 66, 137-144 (1994) · Zbl 0813.49009
[13] He, B. S., Solving a class of linear projection equations, Numerische Mathematik, 68, 71-80 (1994) · Zbl 0822.65040
[14] He, B. S., A modified projection and contraction method for a class of linear complementarity problems, Journal of Computational Mathematics, 14, 1, 54-63 (1996) · Zbl 0854.65047
[15] He, B. S., A class of projection and contraction methods for monotone variational inequalities, Applied Mathematics and Optimization, 35, 69-76 (1997) · Zbl 0865.90119
[16] Korpelevich, G. M., The extra gradient method for finding saddle points and other problems, Matekon, 12, 35-49 (1977)
[17] Lo, H.K., 1997. A path-based traffic assignment formulation. Paper presented at the 76th Annual Meeting of Transportation Research Board; Lo, H.K., 1997. A path-based traffic assignment formulation. Paper presented at the 76th Annual Meeting of Transportation Research Board
[18] Lo, H. K.; Chen, A., Traffic equilibrium problem with route-specific costs: Formulation and algorithms, Transportation Research B, 34, 493-513 (1999)
[19] Lo, H. K., A dynamic traffic assignment formulation that encapsulates the cell transmission model, (Cedar, A., Transportation and Traffic Theory (1999), Elsevier: Elsevier Amsterdam), 327-350
[20] Luenberger, D. G., Introduction to Linear and Nonlinear Programming (1973), Addison-Wisley: Addison-Wisley Reading, MA · Zbl 0241.90052
[21] Nagurney, A., Network Economics, A Variational Inequality Approach (1993), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, Boston, London · Zbl 0873.90015
[22] Nagurney, A.; Zhang, D., Projected Dynamical Systems and Variational Inequality with Applications (1996), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, Boston, MA
[23] Nguyen, S.; Dupuis, D., An efficient method for computing traffic equilibria in networks with asymmetric transportation costs, Transportation Science, 18, 185-202 (1984)
[24] Scott, K., Bernstein, D., 1997. Solving a best path when the value of the time function is nonlinear. Paper presented at the 79th Annual Meeting of Transportation Research Board; Scott, K., Bernstein, D., 1997. Solving a best path when the value of the time function is nonlinear. Paper presented at the 79th Annual Meeting of Transportation Research Board
[25] Sheffi, Y., Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods (1985), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[26] Solodov, M. V.; Tseng, P., Modified projection-type methods for monotone variational inequalities, SIAM Journal of Control and Optimization, 34, 1814-1830 (1996) · Zbl 0866.49018
[27] Sun, D. F., A class of iterative methods for solving nonlinear projection equations, Journal of Optimization Theory and Applications, 91, 123-140 (1996) · Zbl 0871.90091
[28] Sun, D. F., A projection and contraction method for the nonlinear complementarity problem and its extensions, Mathematica Numerica Sinica, 16, 183-194 (1994) · Zbl 0900.65188
[29] Wardrop, J.G., 1952. Some theoretical aspects of road traffic research. In: Proceedings of the Institute of Civil Engineers, Part II, 1, pp. 325-378; Wardrop, J.G., 1952. Some theoretical aspects of road traffic research. In: Proceedings of the Institute of Civil Engineers, Part II, 1, pp. 325-378
[30] Wong, S. C.; Yang, C.; Lo, H. K., A path-based traffic assignment algorithm using the TRANSYT traffic model, Transportation Research B, 35, 2, 163-181 (2001)
[31] Yang, H., He, B.S., 1998. Neural network based dynamic method for solving general network equilibrium problems. Working Paper, Hong Kong University of Science and Technology; Yang, H., He, B.S., 1998. Neural network based dynamic method for solving general network equilibrium problems. Working Paper, Hong Kong University of Science and Technology
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.