An alternating direction method of multipliers for solving user equilibrium problem

Zhiyuan Liu, Xinyuan Chen, Jintao Hu, Shuaian Wang, Kai Zhang, Honggang Zhang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

11 Citations (Scopus)

Abstract

This paper introduces a new parallel computing algorithm to address the user equilibrium (UE) problem. Searching for efficient solution algorithms for UE has been a recurring study subject in transportation research and has attracted much attention in past decades. Existing solution algorithms can be classified into three categories: link-based, path-based, and origin-based. This paper introduces an alternating direction method of multipliers (ADMM) algorithm that is different from these categories. Based on the origin-based formulation of UE problem, an equivalent problem is proposed which eliminates the flow conservation conditions through the augmented Lagrangian function. In order to make use of the ADMM, the network links should be grouped into different blocks, where the links in the same block are disconnected. This link grouping problem falls into the category of edge-coloring problem in graph theory, and it follows the Vizing theorem. A novel approach is developed for the link grouping problem. For links in the same block, we have a separable subproblem, which is solved in parallel by the gradient projection algorithm. Numerical experiments are conducted to validate the proposed algorithm, which shows its computation efficiency.

Original languageEnglish
Pages (from-to)1072-1084
Number of pages13
JournalEuropean Journal of Operational Research
Volume310
Issue number3
DOIs
Publication statusPublished - 1 Nov 2023

Keywords

  • Alternating direction method of multipliers
  • Edge-coloring problem
  • Parallel computing
  • Traffic assignment
  • User equilibrium

ASJC Scopus subject areas

  • General Computer Science
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint

Dive into the research topics of 'An alternating direction method of multipliers for solving user equilibrium problem'. Together they form a unique fingerprint.

Cite this