Efficient negative cycle-canceling algorithm for finding the optimal traffic routing for network evacuation with nonuniform threats

Nassir, Neema, Zheng, Hong and Hickman, Mark (2014) Efficient negative cycle-canceling algorithm for finding the optimal traffic routing for network evacuation with nonuniform threats. Transportation Research Record, 2459 81-90. doi:10.3141/2459-10

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
UQ353698_OA.pdf Full text (open access) application/pdf 1.61MB 0

Author Nassir, Neema
Zheng, Hong
Hickman, Mark
Title Efficient negative cycle-canceling algorithm for finding the optimal traffic routing for network evacuation with nonuniform threats
Journal name Transportation Research Record   Check publisher's open access policy
ISSN 0361-1981
2169-4052
ISBN 9780309295512
Publication date 2014
Year available 2014
Sub-type Article (original research)
DOI 10.3141/2459-10
Open Access Status File (Publisher version)
Volume 2459
Start page 81
End page 90
Total pages 10
Place of publication Washington, DC, United States
Publisher U.S. National Research Council, Transportation Research Board
Collection year 2015
Language eng
Abstract A new network flow solution method is designed to determine optimal traffic routing efficiently for the evacuation of networks with several threat zones and with nonuniform threat levels across zones. The objective is to minimize total exposure (as duration and severity) to the threat for all evacuees during the evacuation. The problem is formulated as a minimum cost dynamic flow problem coupled with traffic dynamic constraints. The traffic flow dynamic constraints are enforced by the well-known point queue and spatial queue models in a time-expanded network presentation. The key to the efficiency of the proposed method is that, for any feasible solution, the algorithm can find and can cancel multiple negative cycles (including the cycle with the largest negative cost) with a single shortest path calculation made possible by applying a proposed transformation to the original problem. A cost transformation function and a multisource shortest path algorithm are proposed to facilitate the efficient detection and cancelation of negative cycles. Zone by zone, negative cycles are canceled at the border links of the zones. The solution method is proved to be optimal. The algorithm is implemented, tested, and verified to be optimal for a midsized example problem.
Keyword Time-varying flows
Congested networks
Optimization model
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: School of Civil Engineering Publications
Official 2015 Collection
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 1 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 1 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Thu, 12 Mar 2015, 11:54:17 EST by Mark Hickman on behalf of School of Civil Engineering