Published
2020-11-12
Issue
Section
Special Issue: Innovations for Transport Planning in China
License
Copyright (c) 2020 Heqing Tan, Muqing Du, Chun-bin Yu
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Authors who publish with JTLU agree to the following terms: 1) Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under Creative Commons Attribution-Noncommercial License 4.0 that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal. 2) Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal. 3) Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
How to Cite
A multiple-path gradient projection method for solving the logit-based stochastic user equilibrium model
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
DOI: https://doi.org/10.5198/jtlu.2020.1600
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.
