An enhanced parallel block coordinate descent algorithm with shared memory for solving large-scale user equilibrium problems

Traffic assignment plays a critical role in urban planning by optimizing transportation efficiency and enhancing overall urban mobility. In large-scale transportation networks, traditional sequential algorithms often exhibit limited computational performance when solving traffic assignment problems (TAPs), which has led to growing interest in parallel algorithms. However, most existing studies primarily focus on the theoretical performance of parallel algorithms, without sufficient attention to their practical applicability. This paper restructures the parallel block coordinate descent (PBCD) algorithm using OpenMP in a shared-memory environment to assess its real-world performance. To address data race issues inherent in parallel computing, a thread-based private data structure is custom-designed. Furthermore, numerical experiments reveal that the convergence behavior of the algorithm becomes unstable as it approaches high-precision solutions, exhibiting significant oscillations. To alleviate this issue, we propose a dynamic block reduction (DBR) strategy that adaptively adjusts the number of OD pairs within each block throughout the iterative process. Two parameter selection methods for DBR are investigated: a fixed-parameter scheme and a self-adaptive scheme based on the Armijo rule. Numerical experiments demonstrate that the OpenMP-based DBR-PBCD algorithm significantly enhances convergence efficiency compared to existing algorithms, particularly for large-scale TAP instances in urban transportation networks.