A linear framework for dynamic user equilibrium traffic assignment in a single origin-destination capacitated network

Nam H. Hoang, Hai L. Vu, Manoj Panda, Hong K. Lo

Research output: Contribution to journalArticleResearchpeer-review

Abstract

The dynamic traffic assignment (DTA) problem has been studied intensively in the literature. However, there is no existing linear framework to solve the user equilibrium (UE) DTA problem. In this paper, we develop a novel linear programming framework to solve the UE-DTA problem in a dynamic capacity network that exploits the linkage between the UE and system optimal (SO) solutions underpinned by a first-in-first-out (FIFO) principle. This important property enables us to develop an incremental loading method to obtain the UE solutions efficiently by solving a sequence of linear programs. The proposed solution methodology possesses several nice properties such as a predictable number of iterations before reaching the UE solution, and a linear system of equations to be solved in each of the iterations.In contrast to the related iterative methods, such as Frank-Wolfe algorithm, successive average (MSA) or projection and their extensions where the purpose of iteration is to seek the solution convergence, whereas ours is to solve a linear problem over multiple iterations but only for a single unit of demand in each iteration. Furthermore, we provide a theoretical proof that in the limit, the SO objective can be used to obtain the UE solution as the system time step goes to zero given the satisfaction of the FIFO constraint. We show via numerical examples the significant improvements in the obtained UE solutions both in terms of accuracy and computational complexity.

Original languageEnglish
Pages (from-to)329-352
Number of pages24
JournalTransportation Research Part B: Methodological
Volume126
DOIs
Publication statusPublished - Aug 2019

Keywords

  • First-In-First-Out (FIFO)
  • Incremental solution method (ISM)
  • Linear programming (LP)
  • System optimal (SO)
  • User equilibrium (UE)

Cite this

@article{0c585c8da0f44afe8d1d888f58b85af3,
title = "A linear framework for dynamic user equilibrium traffic assignment in a single origin-destination capacitated network",
abstract = "The dynamic traffic assignment (DTA) problem has been studied intensively in the literature. However, there is no existing linear framework to solve the user equilibrium (UE) DTA problem. In this paper, we develop a novel linear programming framework to solve the UE-DTA problem in a dynamic capacity network that exploits the linkage between the UE and system optimal (SO) solutions underpinned by a first-in-first-out (FIFO) principle. This important property enables us to develop an incremental loading method to obtain the UE solutions efficiently by solving a sequence of linear programs. The proposed solution methodology possesses several nice properties such as a predictable number of iterations before reaching the UE solution, and a linear system of equations to be solved in each of the iterations.In contrast to the related iterative methods, such as Frank-Wolfe algorithm, successive average (MSA) or projection and their extensions where the purpose of iteration is to seek the solution convergence, whereas ours is to solve a linear problem over multiple iterations but only for a single unit of demand in each iteration. Furthermore, we provide a theoretical proof that in the limit, the SO objective can be used to obtain the UE solution as the system time step goes to zero given the satisfaction of the FIFO constraint. We show via numerical examples the significant improvements in the obtained UE solutions both in terms of accuracy and computational complexity.",
keywords = "First-In-First-Out (FIFO), Incremental solution method (ISM), Linear programming (LP), System optimal (SO), User equilibrium (UE)",
author = "Hoang, {Nam H.} and Vu, {Hai L.} and Manoj Panda and Lo, {Hong K.}",
year = "2019",
month = "8",
doi = "10.1016/j.trb.2017.11.013",
language = "English",
volume = "126",
pages = "329--352",
journal = "Transportation Research, Series B: Methodological",
issn = "0191-2615",
publisher = "Elsevier",

}

A linear framework for dynamic user equilibrium traffic assignment in a single origin-destination capacitated network. / Hoang, Nam H.; Vu, Hai L.; Panda, Manoj; Lo, Hong K.

In: Transportation Research Part B: Methodological, Vol. 126, 08.2019, p. 329-352.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - A linear framework for dynamic user equilibrium traffic assignment in a single origin-destination capacitated network

AU - Hoang, Nam H.

AU - Vu, Hai L.

AU - Panda, Manoj

AU - Lo, Hong K.

PY - 2019/8

Y1 - 2019/8

N2 - The dynamic traffic assignment (DTA) problem has been studied intensively in the literature. However, there is no existing linear framework to solve the user equilibrium (UE) DTA problem. In this paper, we develop a novel linear programming framework to solve the UE-DTA problem in a dynamic capacity network that exploits the linkage between the UE and system optimal (SO) solutions underpinned by a first-in-first-out (FIFO) principle. This important property enables us to develop an incremental loading method to obtain the UE solutions efficiently by solving a sequence of linear programs. The proposed solution methodology possesses several nice properties such as a predictable number of iterations before reaching the UE solution, and a linear system of equations to be solved in each of the iterations.In contrast to the related iterative methods, such as Frank-Wolfe algorithm, successive average (MSA) or projection and their extensions where the purpose of iteration is to seek the solution convergence, whereas ours is to solve a linear problem over multiple iterations but only for a single unit of demand in each iteration. Furthermore, we provide a theoretical proof that in the limit, the SO objective can be used to obtain the UE solution as the system time step goes to zero given the satisfaction of the FIFO constraint. We show via numerical examples the significant improvements in the obtained UE solutions both in terms of accuracy and computational complexity.

AB - The dynamic traffic assignment (DTA) problem has been studied intensively in the literature. However, there is no existing linear framework to solve the user equilibrium (UE) DTA problem. In this paper, we develop a novel linear programming framework to solve the UE-DTA problem in a dynamic capacity network that exploits the linkage between the UE and system optimal (SO) solutions underpinned by a first-in-first-out (FIFO) principle. This important property enables us to develop an incremental loading method to obtain the UE solutions efficiently by solving a sequence of linear programs. The proposed solution methodology possesses several nice properties such as a predictable number of iterations before reaching the UE solution, and a linear system of equations to be solved in each of the iterations.In contrast to the related iterative methods, such as Frank-Wolfe algorithm, successive average (MSA) or projection and their extensions where the purpose of iteration is to seek the solution convergence, whereas ours is to solve a linear problem over multiple iterations but only for a single unit of demand in each iteration. Furthermore, we provide a theoretical proof that in the limit, the SO objective can be used to obtain the UE solution as the system time step goes to zero given the satisfaction of the FIFO constraint. We show via numerical examples the significant improvements in the obtained UE solutions both in terms of accuracy and computational complexity.

KW - First-In-First-Out (FIFO)

KW - Incremental solution method (ISM)

KW - Linear programming (LP)

KW - System optimal (SO)

KW - User equilibrium (UE)

UR - http://www.scopus.com/inward/record.url?scp=85037656410&partnerID=8YFLogxK

U2 - 10.1016/j.trb.2017.11.013

DO - 10.1016/j.trb.2017.11.013

M3 - Article

VL - 126

SP - 329

EP - 352

JO - Transportation Research, Series B: Methodological

JF - Transportation Research, Series B: Methodological

SN - 0191-2615

ER -