Efficient Algorithms for the Cell Based Single Destination System Optimal Dynamic Traffic Assignment Problem

Persistent Link:
http://hdl.handle.net/10150/195304
Title:
Efficient Algorithms for the Cell Based Single Destination System Optimal Dynamic Traffic Assignment Problem
Author:
Zheng, Hong
Issue Date:
2009
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
The cell transmission model (CTM) based single destination system optimal dynamic traffic assignment (SD-SO-DTA) model has been widely applied to situations such as mass evacuations on a transportation network. Although formulated as a linear programming (LP) model, embedded multi-period cell network representation yields an extremely large model for real-size networks. As a result, most of these models are not solvable using existing LP solvers. Solutions obtained by LP also involve holding vehicles at certain locations, violating CTM flow dynamics. This doctoral research is aimed at developing innovative algorithms that overcome both computational efficiency and solution realism issues. We first prove that the LP formulation of the SD-SO-DTA problem is equivalent to the earliest arrival flow (EAF), and then develop efficient algorithms to solve EAF. Two variants of the algorithm are developed under different model assumptions and network operating conditions. For the case of time-varying network parameters, we develop a network flow algorithm on a time-expanded network. The main challenge in this approach is to address the issue of having backward wave speed lower than forward wave speed. This situation leads to non-typical constraints involving coefficients with value of less than 1. In this dissertation we develop a new network algorithm to solve this problem in optimal, even with coefficients of value less than 1. Additionally, the developed approach solves for optimal flows that exhibit non-vehicle-holding properties, which is a major breakthrough compared to all existing solution techniques for SD-SODTA. For the case of time-invariant network parameters, we reduce the SD-SO-DTA to a standard EAF problem on a dynamic network, which is constructed on the original roadway network without dividing it into cells. We prove that the EAF under free flow status is one of the optimal solutions of SD-SO-DTA, if cell properties follow a trapezoidal/triangular fundamental diagram. We use chain flows obtained on a static network to induce dynamic flows, an approach applicable to large-scale networks. Another contribution of this research is to provide a simple and practical algorithm solving the EAF with multiple sources, which has been an active research area for many years. Most existing studies involve submodular function optimization as subroutines, and thus are not practical for real-life implementation. This study’s contribution in this regard is the development of a practical algorithm that avoids submodular function optimization. The main body of the given method is comprised of |S⁺| iterations of earliest arrival s - t flow computations, where |S⁺| is the number of sources. Numerical results show that our multi-source EAF algorithm solves the SD-SO-DTA problem with time-invariant parameters to optimum.
Type:
text; Electronic Dissertation
Keywords:
cell transmission model; dynamic network flow; dynamic traffic assignment; earliest arrival flow; network flow; scaled flow
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Civil Engineering; Graduate College
Degree Grantor:
University of Arizona
Advisor:
Chiu, Yi-Chang
Committee Chair:
Chiu, Yi-Chang

Full metadata record

DC FieldValue Language
dc.language.isoENen_US
dc.titleEfficient Algorithms for the Cell Based Single Destination System Optimal Dynamic Traffic Assignment Problemen_US
dc.creatorZheng, Hongen_US
dc.contributor.authorZheng, Hongen_US
dc.date.issued2009en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractThe cell transmission model (CTM) based single destination system optimal dynamic traffic assignment (SD-SO-DTA) model has been widely applied to situations such as mass evacuations on a transportation network. Although formulated as a linear programming (LP) model, embedded multi-period cell network representation yields an extremely large model for real-size networks. As a result, most of these models are not solvable using existing LP solvers. Solutions obtained by LP also involve holding vehicles at certain locations, violating CTM flow dynamics. This doctoral research is aimed at developing innovative algorithms that overcome both computational efficiency and solution realism issues. We first prove that the LP formulation of the SD-SO-DTA problem is equivalent to the earliest arrival flow (EAF), and then develop efficient algorithms to solve EAF. Two variants of the algorithm are developed under different model assumptions and network operating conditions. For the case of time-varying network parameters, we develop a network flow algorithm on a time-expanded network. The main challenge in this approach is to address the issue of having backward wave speed lower than forward wave speed. This situation leads to non-typical constraints involving coefficients with value of less than 1. In this dissertation we develop a new network algorithm to solve this problem in optimal, even with coefficients of value less than 1. Additionally, the developed approach solves for optimal flows that exhibit non-vehicle-holding properties, which is a major breakthrough compared to all existing solution techniques for SD-SODTA. For the case of time-invariant network parameters, we reduce the SD-SO-DTA to a standard EAF problem on a dynamic network, which is constructed on the original roadway network without dividing it into cells. We prove that the EAF under free flow status is one of the optimal solutions of SD-SO-DTA, if cell properties follow a trapezoidal/triangular fundamental diagram. We use chain flows obtained on a static network to induce dynamic flows, an approach applicable to large-scale networks. Another contribution of this research is to provide a simple and practical algorithm solving the EAF with multiple sources, which has been an active research area for many years. Most existing studies involve submodular function optimization as subroutines, and thus are not practical for real-life implementation. This study’s contribution in this regard is the development of a practical algorithm that avoids submodular function optimization. The main body of the given method is comprised of |S⁺| iterations of earliest arrival s - t flow computations, where |S⁺| is the number of sources. Numerical results show that our multi-source EAF algorithm solves the SD-SO-DTA problem with time-invariant parameters to optimum.en_US
dc.typetexten_US
dc.typeElectronic Dissertationen_US
dc.subjectcell transmission modelen_US
dc.subjectdynamic network flowen_US
dc.subjectdynamic traffic assignmenten_US
dc.subjectearliest arrival flowen_US
dc.subjectnetwork flowen_US
dc.subjectscaled flowen_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineCivil Engineeringen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorChiu, Yi-Changen_US
dc.contributor.chairChiu, Yi-Changen_US
dc.contributor.committeememberMirchandani, Pitu B.en_US
dc.contributor.committeememberHickman, Marken_US
dc.contributor.committeememberLin, Wei-Huaen_US
dc.identifier.proquest10573en_US
dc.identifier.oclc659752316en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.