TY - JOUR
T1 - A novel parallel computing framework for traffic assignment problem
T2 - Integrating alternating direction method of multipliers with Jacobi over relaxation method
AU - Liu, Zhiyuan
AU - Dong, Yu
AU - Zhang, Honggang
AU - Zheng, Nan
AU - Huang, Kai
N1 - Publisher Copyright:
© 2024 Elsevier Ltd
PY - 2024/9
Y1 - 2024/9
N2 - Traffic assignment plays a crucial role in transport system analysis, and the user equilibrium model is a very essential tool. It is however highly challenging to efficiently solve the user equilibrium model, especially for large-scale networks. Taking the deterministic user equilibrium (DUE) model as a representative, this paper aims to harness parallel computing to tackle its high computing burden. A novel parallel computing framework is proposed, drawing from the frontier alternating direction method of multipliers (ADMM) method. This algorithmic framework takes a good balance between the convergence rate and the additional communication costs. Specifically, the paper incorporates insights from the Jacobi over-relaxation (JOR) iteration method into the framework of the ADMM method, improving the convergence rate by utilizing more information during the iteration process while striving to reduce the side effects it brings, thereby developing a novel parallel computing framework, named ADMM-JOR. Subsequently, convergence of the proposed algorithm is rigorously proven under an analytic framework of contractive-type methods. Furthermore, we develop an adaptive strategy for adjusting the relaxation factor in ADMM-JOR, guided by the principle of objective function value decline, which aims to further improve the convergence performance of ADMM-JOR, with minimal additional computational cost in a fully parallel setting. Numerical experiments indicate that the proposed ADMM-JOR significantly reduces computation time while retaining the excellent parallel performance of the original ADMM method and significantly improving its convergence rate.
AB - Traffic assignment plays a crucial role in transport system analysis, and the user equilibrium model is a very essential tool. It is however highly challenging to efficiently solve the user equilibrium model, especially for large-scale networks. Taking the deterministic user equilibrium (DUE) model as a representative, this paper aims to harness parallel computing to tackle its high computing burden. A novel parallel computing framework is proposed, drawing from the frontier alternating direction method of multipliers (ADMM) method. This algorithmic framework takes a good balance between the convergence rate and the additional communication costs. Specifically, the paper incorporates insights from the Jacobi over-relaxation (JOR) iteration method into the framework of the ADMM method, improving the convergence rate by utilizing more information during the iteration process while striving to reduce the side effects it brings, thereby developing a novel parallel computing framework, named ADMM-JOR. Subsequently, convergence of the proposed algorithm is rigorously proven under an analytic framework of contractive-type methods. Furthermore, we develop an adaptive strategy for adjusting the relaxation factor in ADMM-JOR, guided by the principle of objective function value decline, which aims to further improve the convergence performance of ADMM-JOR, with minimal additional computational cost in a fully parallel setting. Numerical experiments indicate that the proposed ADMM-JOR significantly reduces computation time while retaining the excellent parallel performance of the original ADMM method and significantly improving its convergence rate.
KW - Alternating direction method of multipliers
KW - Deterministic user equilibrium
KW - Jacobi over relaxation iteration method
KW - Parallel computing
KW - Traffic assignment
UR - http://www.scopus.com/inward/record.url?scp=85199777790&partnerID=8YFLogxK
U2 - 10.1016/j.tre.2024.103687
DO - 10.1016/j.tre.2024.103687
M3 - Article
AN - SCOPUS:85199777790
SN - 1366-5545
VL - 189
JO - Transportation Research Part E: Logistics and Transportation Review
JF - Transportation Research Part E: Logistics and Transportation Review
M1 - 103687
ER -