A novel parallel computing framework for traffic assignment problem: Integrating alternating direction method of multipliers with Jacobi over relaxation method
提出一种融合交替方向乘子法和雅可比超松弛法的并行计算框架ADMM-JOR，用于高效求解大规模交通网络中的用户均衡模型，显著减少计算时间并提升收敛速度。
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.