Integrating alternating direction method of multipliers and bush for solving the traffic assignment problem

Zhiyuan Liu, Honggang Zhang, Kai Zhang and Zihan Zhou

Transportation Research Part E: Logistics and Transportation Review, 2023, vol. 177, issue C

Abstract: This paper introduces two novel parallel algorithmic frameworks to address the user equilibrium traffic assignment problem (UE-TAP). Most of the existing solution algorithms for the UE-TAP are executed in a sequential manner. This study endeavors to explore parallel computing methods based on model decomposition. Considering that the TAPs can be decomposed based on their origins, thus, following the spirit of the alternating direction method of multipliers (ADMM), a new parallel algorithm B-ADMM is proposed, which integrates the concept of the bush. Subsequently, the convergence of the proposed algorithm is rigorously proven. To enhance the algorithmic parallelism while maintaining the convergence efficiency of the B-ADMM algorithm, this paper further employs the parallel block coordinate descent (PBCD) method to improve the B-ADMM algorithm. We develop a bi-level parallel algorithm PBCD-ADMM, in which the independent origins/bushes are separated into several blocks, and the origin/bush-based restricted subproblems in each block can be solved in parallel. Furthermore, for the given bush belonging to a block, the bush links can also be grouped into several sub-blocks based on the original link-blocking scheme. Thus, these link-based subproblems in each sub-block can also be solved in parallel. A numerical experiment is conducted to validate the proposed algorithms, which indicates that the two new parallel algorithms perform better in terms of convergence speed compared with the original ADMM algorithm.

Keywords: User equilibrium; Alternating direction methods of multipliers; Bush; Parallel computing; Parallel block coordinate descent method (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S1366554523002211
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transe:v:177:y:2023:i:c:s1366554523002211

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

DOI: 10.1016/j.tre.2023.103233

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().