AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Communications in Transportation Research Article
Article Link
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Research Article | Open Access

An ADMM-based parallel algorithm for solving traffic assignment problem with elastic demand

Kai Zhanga, Honggang Zhanga, Yu Donga, Yunchi Wua, Xinyuan Chena,b( )
Jiangsu Key Laboratory of Urban ITS, Jiangsu Province Collaborative Innovation Center of Modern Urban Traffic Technologies, School of Transportation, Southeast University, Nanjing, 211000, China
College of Civil Aviation, Nanjing University of Aeronautics and Astronautics, Nanjing, 210016, China
Show Author Information

Abstract

Efficiently solving the user equilibrium traffic assignment problem with elastic demand (UE-TAPED) for transportation networks is a critical problem for transportation studies. Most existing UE-TAPED algorithms are designed using a sequential computing scheme, which cannot take advantage of advanced parallel computing power. Therefore, this study focuses on model decomposition and parallelization, proposing an origin-based formulation for UE-TAPED and proving an equivalent reformulation of the original problem. Furthermore, the alternative direction method of multipliers (ADMM) is employed to decompose the original problem into independent link-based subproblems, which can solve large-scale problems with small storage space. In addition, to enhance the efficiency of our algorithm, the parallel computing technology with optimal parallel computing schedule is implemented to solve the link-based subproblems. Numerical experiments are performed to validate the computation efficiency of the proposed parallel algorithm.

Keywords

Parallel computingTraffic assignment problemElastic demandModel decompositionAlternative direction method of multipliers (ADMM)

References

 

Babonneau, F., Vial, J.P., 2008. An efficient method to compute traffic assignment problems with elastic demands. Transport. Sci. 42, 249–260.
Crossref Google Scholar
 

Bar-Gera, H., 2010. Traffic assignment by paired alternative segments. Transp. Res. Part B Methodol. 44, 1022–1046.
Crossref Google Scholar
 
Beckmann, M., McGuire, C.B., Winsten, C.B., 1956. Studies in the Economics of Transportation. Yale University Press.
 

Bertsekas, D., Gafni, E., Gallager, R., 1984. Second derivative algorithms for minimum delay distributed routing in networks. IEEE Trans. Commun. 32, 911–919.
Crossref Google Scholar
 

Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J., 2010. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3 (1), 1–122.
Crossref Google Scholar
 

Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J., 2011. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach. Learn. 3, 1–122.
Crossref Google Scholar
 
Boyd, S., Vandenberghe, L., 2004. Convex Optimization. Cambridge University Press, Cambridge, UK.
Crossref
 
Brooks, J., Hager, W., Zhu, J., 2015. A Decentralized Multi-Block ADMM for Demand-Side Primary Frequency Control Using Local Frequency Measurements. https://arxiv.org/abs/1509.08206.pdf.
 

Carey, M., 1985. The dual of the traffic assignment problem with elastic demands. Transp. Res. Part B Methodol. 19, 227–237.
Crossref Google Scholar
 
Chen, A., Jayakrishnan, R., 1998. A path-based gradient projection algorithm: effects of equilibration with a restricted path set under two flow update policies. In: 77th Annual Meeting of the Transportation Research Board, Washington, DC.
 

Cheng, Q., Lin, Y., Zhou, X., Liu, Z., 2023. Analytical formulation for explaining the variations in traffic states: a fundamental diagram modeling perspective with stochastic parameters. Eur. J. Oper. Res. 312, 182–197.
Crossref Google Scholar
 

Dafermos, S.C., Sparrow, F.T., 1969. Traffic assignment problem for a general network. J. Res. Natl. Bur Stand Sect. B Math. Sci. 73B, 91.
Crossref Google Scholar
 

Daganzo, C.F., Sheffi, Y., 1977. On stochastic models of traffic assignment. Transport. Sci. 11, 253–274.
Crossref Google Scholar
 

Douglas, J., Rachford, H.H., 1956. On the numerical solution of heat conduction problems in two and three space variables. Trans. Am. Math. Soc. 82, 421–439.
Crossref Google Scholar
 

Ezaki, T., Imura, N., Nishinari, K., 2022. Towards understanding network topology and robustness of logistics systems. Commun. Transp. Res. 2, 100064.
Crossref Google Scholar
 

Fan, Y., Ding, J., Liu, H., Wang, Y., Long, J., 2022. Large-scale multimodal transportation network models and algorithms-Part Ⅰ: the combined mode split and traffic assignment problem. Transport. Res. Part E Logist Transp Rev 164, 102832.
Crossref Google Scholar
 

Feijoo, B., Meyer, R.R., 1988. Piecewise-linear approximation methods for nonseparable convex optimization. Manag. Sci. 34, 411–419.
Crossref Google Scholar
 

Florian, M., Nguyen, S., 1974. A method for computing network equilibrium with elastic demands. Transport. Sci. 8, 321–332.
Crossref Google Scholar
 

Fukushima, M., 1984. On the dual approach to the traffic assignment problem. Transp. Res. Part B Methodol. 18, 235–245.
Crossref Google Scholar
 

Gabay, D., Mercier, B., 1976. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. Appl. 2, 17–40.
Crossref Google Scholar
 

Galligari, A., Sciandrone, M., 2019. A computational study of path-based methods for optimal traffic assignment with both inelastic and elastic demand. Comput. Oper. Res. 103, 158–166.
Crossref Google Scholar
 

Gartner, N.H., 1980. Optimal traffic assignment with elastic demands: a review part Ⅱ. algorithmic approaches. Transport. Sci. 14, 192–208.
Crossref Google Scholar
 
Goncalves, A., Liu, X., Banerjee, A., 2019. Two-block vs. Multi-block ADMM: an empirical evaluation of convergence. https://arxiv.org/abs/1907.04524.pdf.
 

Gu, Z., Najmi, A., Saberi, M., Liu, W., Rashidi, T.H., 2020. Macroscopic parking dynamics modeling and optimal real-time pricing considering cruising-for-parking. Transport. Res. C Emerg. Technol. 118, 102714.
Crossref Google Scholar
 

Han, D., Yuan, X., Zhang, W., 2014. An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing. Math. Comput. 83, 2263–2291.
Crossref Google Scholar
 

Han, K., Szeto, W.Y., Friesz, T.L., 2015. Formulation, existence, and computation of boundedly rational dynamic user equilibrium with fixed or endogenous user tolerance. Transp. Res. Part B Methodol. 79, 16–49.
Crossref Google Scholar
 

He, B., Tao, M., Yuan, X., 2012. Alternating direction method with Gaussian back substitution for separable convex programming. SIAM J. Optim. 22, 313–340.
Crossref Google Scholar
 
Hearn, D.W., Yildirim, M.B., 2002. A toll pricing framework for traffic assignment problems with elastic demand. In: Applied Optimization. Springer US, Boston, MA, pp. 135–145.
Crossref
 

Huang, D., Wang, Y., Jia, S., Liu, Z., Wang, S., 2023. A Lagrangian relaxation approach for the electric bus charging scheduling optimisation problem. Transportmetrica A: Transport Sci. 19, 2023690.
Crossref Google Scholar
 

Huo, J., Liu, Z., Chen, J., Cheng, Q., Meng, Q., 2023. Bayesian optimization for congestion pricing problems: a general framework and its instability. Transp. Res. Part B Methodol. 169, 1–28.
Crossref Google Scholar
 

Jafari, E., Pandey, V., Boyles, S.D., 2017. A decomposition approach to the static traffic assignment problem. Transp. Res. Part B Methodol. 105, 270–296.
Crossref Google Scholar
 

Javani, B., Babazadeh, A., 2017. Origin-destination-based truncated quadratic programming algorithm for traffic assignment problem. Transp Lett 9, 166–176.
Crossref Google Scholar
 

Jayakrishnan, R., Tsai, W.T., Prashker, J.N., Rajadhyaksha, S., 1994. A faster path-based algorithm for traffic assignment. Transport. Res. Rec. 191.
Google Scholar
 

Kitthamkesorn, S., Chen, A., Xu, X., 2015. Elastic demand with weibit stochastic user equilibrium flows and application in a motorised and non-motorised network. Transportmetrica A: Transport Sci. 11, 158–185.
Crossref Google Scholar
 

Larsson, T., Patriksson, M., 1992. Simplicial decomposition with disaggregated representation for the traffic assignment problem. Transport. Sci. 26, 4–17.
Crossref Google Scholar
 

LeBlanc, L.J., Farhangian, K., 1981. Efficient algorithms for solving elastic demand traffic assignment problems and mode split-assignment problems. Transport. Sci. 15, 306–317.
Crossref Google Scholar
 

LeBlanc, L.J., Morlok, E.K., Pierskalla, W.P., 1975. An efficient approach to solving the road network equilibrium traffic assignment problem. Transport. Res. 9, 309–318.
Crossref Google Scholar
 

Lin, B., Zhao, Y., Lin, R., Liu, C., 2022. Shipment path planning for rail networks considering elastic capacity. IEEE Intell. Transp. Syst. Mag. 14, 160–174.
Crossref Google Scholar
 

Liu, R., Gui, X., Chen, D., Ni, S., 2023c. Market competition oriented air-rail ticket fare optimization. Multimodal Transp. 2, 100053.
Crossref Google Scholar
 

Liu, Y., Wu, F., Liu, Z., Wang, K., Wang, F., Qu, X., 2023a. Can language models be used for real-world urban-delivery route optimization? Innovation. https://doi.org/10.1016/j.xinn.2023.100520.
Crossref Google Scholar
 

Liu, Z., Chen, X., Hu, J., Wang, S., Zhang, K., Zhang, H., 2023b. An alternating direction method of multipliers for solving user equilibrium problem. Eur. J. Oper. Res. 310, 1072–1084.
Crossref Google Scholar
 

Maher, M., 2001. Stochastic user equilibrium assignment with elastic demand. Traffic Eng. Control 42, 163–167.
Google Scholar
 

Meng, Q., Liu, Z., 2012. Mathematical models and computational algorithms for probit-based asymmetric stochastic user equilibrium problem with elastic demand. Transportmetrica 8, 261–290.
Crossref Google Scholar
 

Meng, Q., Liu, Z., Wang, S., 2014. Asymmetric stochastic user equilibrium problem with elastic demand and link capacity constraints. Transportmetrica A: Transport Sci. 10, 304–326.
Crossref Google Scholar
 

Mitradjieva, M., Lindberg, P.O., 2013. The stiff is moving—conjugate direction frank-wolfe methods with applications to traffic assignment. Transport. Sci. 47, 280–293.
Crossref Google Scholar
 

Nagurney, A., 1988. An equilibration scheme for the traffic assignment problem with elastic demands. Transp. Res. Part B Methodol. 22, 73–79.
Crossref Google Scholar
 

Nie, Y., 2010. A class of bush-based algorithms for the traffic assignment problem. Transp. Res. Part B Methodol. 44, 73–89.
Crossref Google Scholar
 
Pan, V.Y., Preparata, F.P., 1992. Supereffective slow-down of parallel computations. In: Proceedings of the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 402–409.
Crossref
 
Patriksson, M., 2015. The Traffic Assignment Problem: Models and Methods. Courier Dover Publications, Garden City, Kansas, USA.
 

Qin, X., Ke, J., Wang, X., Tang, Y., Yang, H., 2022. Demand management for smart transportation: a review. Multimodal Transp. 1, 100038.
Crossref Google Scholar
 

Ryu, S., Chen, A., Choi, K., 2014. A modified gradient projection algorithm for solving the elastic demand traffic assignment problem. Comput. Oper. Res. 47, 61–71.
Crossref Google Scholar
 

Ryu, S., Chen, A., Choi, K., 2017. Solving the combined modal split and traffic assignment problem with two types of transit impedance function. Eur. J. Oper. Res. 257, 870–880.
Crossref Google Scholar
 
Sheffi, Y., 1985. Urban Transportation Networks. Prentice-Hall, Englewood Cliffs, NJ.
 

Sheffi, Y., Powell, W., 1981. A comparison of stochastic and deterministic traffic assignment over congested networks. Transp. Res. Part B Methodol. 15, 53–64.
Crossref Google Scholar
 

Simon Zhou, X., Cheng, Q., Wu, X., Li, P., Belezamo, B., Lu, J., et al., 2022. A meso-to-macro cross-resolution performance approach for connecting polynomial arrival queue model to volume-delay function with inflow demand-to-capacity ratio. Multimodal Transp. 1, 100017.
Crossref Google Scholar
 

Siri, E., Siri, S., Sacone, S., 2022. A topology-based bounded rationality day-to-day traffic assignment model. Commun. Transp. Res. 2, 100076.
Crossref Google Scholar
 

Song, M., Lu, B., Cheng, L., Sun, C., 2022. Lagrangian relaxation-based decomposition approaches for the capacitated arc routing problem in the state-space-time network. Transp Lett 1–16.
Crossref Google Scholar
 

Tao, M., Yuan, X., 2011. Recovering low-rank and sparse components of matrices from incomplete and noisy observations. SIAM J. Optim. 21, 57–81.
Crossref Google Scholar
 

Vizing, V.G., 1965. The chromatic class of a multigraph. Cybernetics 1, 32–41.
Crossref Google Scholar
 

Wang, A., Tang, Y., Mohmand, Y.T., Xu, P., 2022. Modifying link capacity to avoid Braess Paradox considering elastic demand. Phys. Stat. Mech. Appl. 605, 127951.
Crossref Google Scholar
 

Wang, D., Liao, F., 2023. Formulation and solution for calibrating boundedly rational activity-travel assignment: an exploratory study. Commun. Transp. Res. 3, 100092.
Crossref Google Scholar
 

Wang, D., Liao, F., Gao, Z., Rasouli, S., Huang, H.J., 2020. Tolerance-based column generation for boundedly rational dynamic activity-travel assignment in large-scale networks. Transport. Res. Part E Logist Transp Rev 141, 102034.
Crossref Google Scholar
 

Wang, S., Chen, X., Qu, X., 2021. Model on empirically calibrating stochastic traffic flow fundamental diagram. Commun. Transp. Res. 1, 100015.
Crossref Google Scholar
 

Wardrop, J.G., 1952. Road paper. some theoretical aspects of road traffic research. Proc. Inst. Civ. Eng. 1, 325–362.
Crossref Google Scholar
 

Wu, Z.X., Lam, W.H.K., 2003. Network equilibrium for congested multi-mode networks with elastic demand. J. Adv. Transport. 37, 295–318.
Crossref Google Scholar
 

Xie, C., Wan, Y., Xu, M., Chen, X., Waller, T., 2023. On the primal and dual formulations of traffic assignment problems with perception stochasticity and demand elasticity. Transp Lett 15, 537–552.
Crossref Google Scholar
 

Xing, J., Wu, W., Cheng, Q., Liu, R., 2022. Traffic state estimation of urban road networks by multi-source data fusion: review and new insights. Phys. Stat. Mech. Appl. 595, 127079.
Crossref Google Scholar
 

Xu, Q., Li, K., Wang, J., Yuan, Q., Yang, Y., Chu, W., 2022. The status, challenges, and trends: an interpretation of technology roadmap of intelligent and connected vehicles in China (2020). J. Intell. Connect Veh. 5, 1–7.
Crossref Google Scholar
 

Xu, X., Chen, A., 2013. C-logit stochastic user equilibrium model with elastic demand. Transport. Plann. Technol. 36, 463–478.
Crossref Google Scholar
 

Zhang, K., Zhang, H., Cheng, Q., Chen, X., Wang, Z., Liu, Z., 2023. A customized two-stage parallel computing algorithm for solving the combined modal split and traffic assignment problem. Comput. Oper. Res. 154, 106193.
Crossref Google Scholar
 

Zhang, R., Kwok, J., 2014. Asynchronous distributed ADMM for consensus optimization. PMLR 1701–1709.
Google Scholar
 

Zhang, Y., Li, L., Zhang, W., Cheng, Q., 2022. GATC and DeepCut: deep spatiotemporal feature extraction and clustering for large-scale transportation network partition. Phys. Stat. Mech. Appl. 606, 128110.
Crossref Google Scholar
Communications in Transportation Research
Volume 3,
December 2023
Article number: 100108
DOI: 10.1016/j.commtr.2023.100108
Cite this article:
Zhang K, Zhang H, Dong Y, et al. An ADMM-based parallel algorithm for solving traffic assignment problem with elastic demand. Communications in Transportation Research, 2023, 3: 100108. https://doi.org/10.1016/j.commtr.2023.100108

338

Views

2

Crossref

2

Web of Science

2

Scopus

Altmetrics
Received: 03 August 2023
Revised: 17 September 2023
Accepted: 06 October 2023
Published: 27 November 2023
© 2023 The Authors.

This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).
Return