A multiple-path gradient projection method for solving the logit-based stochastic user equilibrium model

Authors

• Heqing Tan College of Civil and Transportation Engineering, Hohai University
• Muqing Du College of Civil and Transportation Engineering, Hohai University
• Chun-bin Yu College of Civil and Transportation Engineering, Hohai University

Keywords:

Transportation Planning, Traffic assignment, Stochastic User Equilibrium, Gradient Projection Method, Multiple Paths

Abstract

This paper proposes a path-based algorithm for solving the well-known logit-based stochastic user equilibrium (SUE) problem in transportation planning and management. Based on the gradient projection (GP) method, the new algorithm incorporates a novel multiple-path gradient approach to generate the descent direction in consideration of many paths existing in every single origin-destination (O-D) pair. To apply the path-based algorithm, the SUE problem is reformulated as a variational inequality (VI), and a working path set is predetermined. The numerical experiments are conducted on the Winnipeg network where a large number of paths are provided. The results show the multiple-path gradient projection algorithm outperforms the original GP method. Three different step size strategies, including the fixed step size, self-regulated averaging and self-adaptive Armijo’s strategies, are involved to draw a more general conclusion. Also, the effects of the path number on computational performance are analyzed. The multiple-path gradient projection (MGP) method converges much faster than the GP method when the path set size gets large.

References

Armijo, L. (1966). Minimization of functions having Lipschitz continuous first partial derivatives. Pacific Journal of Mathematics, 16(1), 1–3.

Blum, J. (1954). Multidimensional stochastic approximation methods. Annals of Mathematical Statistics, 4, 737–744.

Bar-Gera, H., & Boyce, D. (2006). Solving a non-convex combined travel forecasting model by the method of successive averages with constant step sizes. Transportation Research Part B, 40(5), 351–367.

Bertsekas, D. P. (1976). On the Goldstein-Levitin-Polyak Gradient Projection method. IEEE Transactions on Automatic Control, 21(2), 174–184.

Ben-Akiva, M., & Bierlaire, M. (2003). Handbook of transportation science. Boston: Springer.

Bekhor, S., & Toledo, T. (2005). Investigating path-based solution algorithms to the stochastic user equilibrium problem. Transportation Research Part B, 39, 279–295.

Bekhor, S., Toledo, T., & Prashker J. N. (2008). Effects of choice set size and route choice models on path-based traffic assignment. Transportmetrica, 4, 117–133.

Bekhor, S., Toledo, T., & Reznikova, L. (2009). A path-based algorithm for the cross-nested logit stochastic user equilibrium traffic assignment. Computer-Aided Civil and Infrastructure Engineering, 24(1), 15–25.

Boyce, D., O’Neill, C. R., & Scherr, W. (2008). Solving the sequential travel forecasting procedure with feedback. Transportation Research Record, 2077(1), 129–135.

Chen, A., Lee, D. H., & Jayakrishnan, R. (2002). Computational study of state-of-the-art path-based traffic assignment algorithms. Mathematics and Computers in Simulation, 59(6), 509–518.

Chen, A., Pravinvongvuth, S., Xu, X., Ryu, S., & Chootinan, P. (2012) Examining the scaling effect and overlapping problem in logit-based stochastic user equilibrium model. Transportation Research Part A, 46, 1343–1358.

Chen, A., Ryu, S., Xu, X., & Choi, K. (2014). Computation and application of the paired combinatorial logit stochastic user equilibrium problem. Computers & Operations Research, 43, 68–77.

Chen, A., Xu, X., Ryu, S., & Zhou, Z. (2013). A self-adaptive Armijo step size strategy with application to traffic assignment models and algorithms. Transportmetrica, 9(8), 695–712.

Chen, A., Zhou, Z., & Xu, X. (2012). A self-adaptive gradient projection algorithm for the nonadditive traffic equilibrium problem. Computer & Operation Research, 39(2), 127–138.

Chen, M., & Alfa, A. (1991). Algorithms for solving Fisk’s stochastic traffic assignment model. Transportation Research Part B, 25(6), 405–412.

Dial, R. (1971). A probabilistic multipath traffic assignment model which obviates path enumeration. Transportation Research, 5(2), 83–111.

Daganzo, C. F., & Sheffi, Y. (1977). On stochastic models of traffic assignment. Transportation Science, 11, 351–372.

Damberg, O., Lundgren, J., & Patriksson, M. (1995). An algorithm for the stochastic user equilibrium problem. Transportation Research Part B, 30, 115–131.

Fisk, C. (1980). Some developments in equilibrium traffic assignment. Transportation Research 14B, 243–255.

Gibb, J. (2016). Solving travel demand model equilibrium with Barzilai-Browein step sizes. Paper presented at 95th Annual Meeting of the Transportation Research Board, Washington, DC.

Jayakrishnan, R., Tsai, W. K., & Prashker J. N. (1994). A faster path-based algorithm for traffic assignment. Transportation Research Record, 1554, 75–83.

Kitthamkesorn, S., & Chen, A. (2013). A path-size Weibit stochastic user equilibrium model. Transportation Research Part B, 57, 378–397.

Kitthamkesorn, S., & Chen, A. (2014). Unconstrained weibit stochastic user equilibrium model with extensions. Transportation Research Part B, 59, 1–21.

Kitthamkesorn, S., Chen, A., & Xu, X. (2015). Elastic demand with weibit stochastic user equilibrium flows and application in a motorized and non-motorized network. Transportmetrica A: Transport Science, 11(2), 158–185.

Liu, H., He, X., & He, B. (2009). Method of successive weighted averages and self-regulated averaging schemes for solving stochastic user equilibrium problem. Networks and Spatial Economics, 9, 485–503.

Maher, M. (1998). Algorithm for logit-based stochastic user equilibrium assignment. Transportation Research Part B, 32(8), 539–549.

Nagurney, A., & Zhang, D. (1996). Projected dynamical systems and variational inequalities with applications. Boston: Kluwer.

Perederieieva, O., Ehrgott, M., Raith, A., & Wang, J. Y. T. (2015). A framework for and empirical study of algorithms for traffic assignment. Computers and Operations Research, 54, 90–107.

Polyak, B. (1990). New method of stochastic approximation type. Automation and Remote Control, 51(7), 937–946.

Prashker, J. N., & Bekhor, S. (1998). Investigation of stochastic network loading procedures. Transportation Research Board, 1645, 94–102.

Rosen, J. (1960). The gradient projection method for nonlinear programming. Part I. Linear Constraints. Journal of the Society for Industrial and Applied Mathematics, 8(1), 181–217.

Ryu, S., Chen, A., & Choi, K. (2014). A modified gradient projection algorithm for solving the elastic demand traffic assignment problem. Computers and Operations Research, 47, 61–71.

Ryu, S., Chen A., & Choi K. (2017). Solving the combined modal split and traffic assignment problem with two types of transit impedance function. European Journal of Operational Research, 257, 870–880.

Sheffi, Y. (1985). Urban transportation networks: Equilibrium analysis with mathematical programming methods. Upper Saddle River, NJ: Prentice-Hall.

Xu, X., & Chen, A. (2013). C-logit stochastic user equilibrium problem with elastic demand. Transportation Planning and Technology, 36(5), 463–478.

Xu, X., Chen, A., Zhou, Z., & Bekhor, S. (2012). Path-based algorithms to solve C-logit stochastic user equilibrium assignment problem. Transportation Research Record, 2279, 21–30.

Zhou, Z., Chen, A., & Bekhor, S. (2012). C-logit stochastic user equilibrium model: Formulations and solution algorithm. Transportmetrica, 8(1), 17–41.

2020-11-12

How to Cite

Tan, H., Du, M., & Yu, C.- bin. (2020). A multiple-path gradient projection method for solving the logit-based stochastic user equilibrium model. Journal of Transport and Land Use, 13(1), 539-558. https://doi.org/10.5198/jtlu.2020.1600

Section

Special Issue: Innovations for Transport Planning in China