×

zbMATH — the first resource for mathematics

Improving truncated Newton method for the logit-based stochastic user equilibrium problem. (English) Zbl 1435.90045
Summary: This study proposes an improved truncated Newton (ITN) method for the logit-based stochastic user equilibrium problem. The ITN method incorporates a preprocessing procedure to the traditional truncated Newton method so that a good initial point is generated, on the basis of which a useful principle is developed for the choice of the basic variables. We discuss the rationale of both improvements from a theoretical point of view and demonstrate that they can enhance the computational efficiency in the early and late iteration stages, respectively, when solving the logit-based stochastic user equilibrium problem. The ITN method is compared with other related methods in the literature. Numerical results show that the ITN method performs favorably over these methods.

MSC:
90B20 Traffic problems in operations research
90C15 Stochastic programming
90C53 Methods of quasi-Newton type
Software:
tn
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Wardrop, J. G., Some theoretical aspects of road traffic research, Proceedings, Institute of Civil Engineers, Part II, 1, 325-378 (1952)
[2] Daganzo, C. F.; Sheffi, Y., On stochastic models of traffic assignment, Transportation Science, 11, 3, 253-274 (1977)
[3] Fisk, C., Some developments in equilibrium traffic assignment, Transportation Research Part B: Methodological, 14, 3, 243-255 (1980)
[4] Sheffi, Y.; Powell, W. B., An algorithm for the equilibrium assignment problem with random link times, Networks, 12, 2, 191-207 (1982) · Zbl 0485.90082
[5] Liu, Z.; Wang, S.; Zhou, B.; Cheng, Q., Robust optimization of distance-based tolls in a network considering stochastic day to day dynamics, Transportation Research Part C: Emerging Technologies, 79, 58-72 (2017)
[6] Sun, C.; Cheng, L.; Zhu, S.; Han, F.; Chu, Z., Multi-criteria user equilibrium model considering travel time, travel time reliability and distance, Transportation Research Part D: Transport and Environment, 66, 3-12 (2019)
[7] Wang, C.; Xu, C.; Xia, J.; Qian, Z., Modeling faults among e-bike-related fatal crashes in China, Traffic Injury Prevention, 18, 2, 175-181 (2017)
[8] Du, M.; Cheng, L., Better understanding the characteristics and influential factors of different travel patterns in free-floating bike sharing: evidence from Nanjing, China, Sustainability, 10, 4, 1244 (2018)
[9] Dial, R. B., A probabilistic multipath traffic assignment algorithm which obviates path enumeration, Transportation Research, 5, 2, 83-111 (1971)
[10] Maher, M., Algorithms for logit-based stochastic user equilibrium assignment, Transportation Research Part B: Methodological, 32, 8, 539-549 (1998)
[11] Bell, M. G. H., Alternatives to Dial’s logit assignment algorithm, Transportation Research Part B: Methodological, 29, 4, 287-295 (1995)
[12] Akamatsu, T., Cyclic flows, Markov process and stochastic traffic assignment, Transportation Research Part B: Methodological, 30, 5, 369-386 (1996)
[13] Damberg, O.; Lundgren, J. T.; Patriksson, M., An algorithm for the stochastic user equilibrium problem, Transportation Research Part B: Methodological, 30, 2, 115-131 (1996)
[14] Larsson, T.; Patriksson, M., Simplicial decomposition with disaggregated representation for the traffic assignment problem, Transportation Science, 26, 1, 4-17 (1992) · Zbl 0764.90033
[15] Bekhor, S.; Toledo, T., Investigating path-based solution algorithms to the stochastic user equilibrium problem, Transportation Research Part B: Methodological, 39, 3, 279-295 (2005)
[16] Zhou, B.; Bliemer, M. C.; Li, X.; Huang, D., A modified truncated Newton algorithm for the logit-based stochastic user equilibrium problem, Applied Mathematical Modelling, 39, 18, 5415-5435 (2015) · Zbl 1443.90089
[17] Patriksson, M., Partial linearization methods in nonlinear programming, Journal of Optimization Theory and Applications, 78, 2, 227-246 (1993) · Zbl 0796.90058
[18] Nocedal, J.; Wright, S. J., Numerical Optimization (2006), New York, NY, USA: Springer, New York, NY, USA · Zbl 1104.65059
[19] Dembo, R. S.; Steihaug, T., Truncated-newtono algorithms for large-scale unconstrained optimization, Mathematical Programming, 26, 2, 190-212 (1983) · Zbl 0523.90078
[20] Nash, S. G., Preconditioning of truncated-Newton methods, SIAM Journal on Scientific and Statistical Computation, 6, 3, 599-616 (1985) · Zbl 0592.65038
[21] Bar-Gera, H., Transportation network test problems, http://www.bgu.ac.il/∼bargera/tntp/
[22] Azevedo, J. A.; Santos Costa, M. E. O.; Silvestre Madera, J. J. E. R.; Vieira Martins, E. Q., An algorithm for the ranking of shortest paths, European Journal of Operational Research, 69, 1, 97-106 (1993) · Zbl 0782.90091
[23] De la Barra, T.; Perez, B.; Anez, J., Multidimensional path search and assignment, Proceedings of the 21st PTRC Summer Annual Meeting
[24] Zhou, Z.; Chen, A.; Bekhor, S., C-logit stochastic user equilibrium model: formulations and solution algorithm, Transportmetrica, 8, 1, 17-41 (2012)
[25] Evans, S. P., Derivation and analysis of some models for combining trip distribution and assignment, Transportation Research, 10, 1, 37-57 (1976)
[26] Vovsha, P.; Bekhor, S., Link-nested logit model of route choice: overcoming the route overlapping problem, Transportation Research Record, 1645, 1, 133-142 (1998)
[27] McFadden, D.; Karlquist, A., Modelling the choice of residential location, Spatial Interaction Theory and Residential Location, 75-96 (1978), Amsterdam, Netherlands: North-Holland, Amsterdam, Netherlands
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.