A parallel computing framework for solving user equilibrium problem on computer clusters

Xinyuan Chen, Zhiyuan Liu, Inhi Kim

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Traffic assignment is a fundamental tool to evaluate and analyse the travel behaviour of network users in the transportation network. Although many extensions have been developed, the principle of user equilibrium (UE) is still the cornerstone for solving traffic equilibrium problems. Applications of UE in large-scale transportation networks have been largely limited due to the overwhelming computation burden. Therefore, with the recent advances in parallel computing, this paper proposes an efficient parallel-computing framework based on Map-Reduce to solve the UE problem. This Map-Reduce model provides a concise abstraction, Map and Reduce, for separable computational tasks. We incorporate this parallel programming model into the Frank–Wolfe algorithm and gradient projection algorithm to achieve efficient in-memory computations on large clusters in a fault-tolerant manner. The proposed parallel-computing algorithms are applied to large-scale transportation networks to examine its computation efficiency. This acceleration approach is found to significantly reduce the execution time.

Original languageEnglish
Pages (from-to)550-573
Number of pages24
JournalTransportmetrica A: Transport Science
Volume16
Issue number3
DOIs
Publication statusPublished - 2020

Keywords

  • Map-Reduce
  • Parallel computing
  • shortest path
  • Spark
  • user equilibrium

Cite this