An ADMM-based splitting algorithm with multiplier sequential updates for solving traffic assignment

doi:10.1080/23249935.2025.2528952

2025-07-05

PRE

DOI：10.1080/23249935.2025.2528952

原文链接

原文求助

摘要

En 中文

Efficient algorithms for solving traffic assignment (TA) problems have garnered significant attention in transportation research. This study focuses on designing a splitting algorithm for the user equilibrium (UE)-TA problem by leveraging decomposition and parallelisation techniques. First, we employ the origin-based form of the UE-TA problem, which facilitates the decomposition of the original problem into independent block-based (also referred to as link-based) subproblems. This decomposition strategy enables the algorithm to handle large-scale scenarios with minimal storage requirements. Then, we propose an alternating direction method of multipliers-based algorithm that utilises parallel computing techniques to solve the UE-TA problem. The Lagrange multiplier update, which has lower computational costs compared to solving the block-based subproblem, is performed before solving each decomposed block-based subproblem, resulting in a sequential update scheme in each iteration. In addition, a relaxation factor is introduced in each Lagrange multiplier update step to improve numerical performance. Our update scheme follows a Gauss-Seidel structure for updating both Lagrange multipliers and block-based link flows. Moreover, parallel computing is applied separately to Lagrange multiplier updates and link-based subproblems. Within each block of decision variables, the separable link-based subproblems are solved simultaneously using the gradient projection method. Finally, we demonstrate the computational performance and potential of the proposed algorithm through numerical experiments conducted on four different traffic networks.

Keyword:

Traffic assignment

user equilibrium

alternating direction method of multipliers

sequential updates of the Lagrange multiplier

parallel computing mode