Efficient contraflow algorithms for quickest evacuation planning

The optimization models and algorithms with their implementations on flow over time problems have been an emerging field of research because of largely increasing human-created and natural disasters worldwide. For an optimal use of transportation network to shift affected people and normalize the di...

Full description

Saved in:
Bibliographic Details
Published in:Science China. Mathematics 2018-11, Vol.61 (11), p.2079-2100
Main Authors: Pyakurel, Urmila, Nath, Hari Nandan, Dhamala, Tanka Nath
Format: Article
Language:English
Subjects:
Algorithms
Applications of Mathematics
Computing time
Evacuation
Evacuations & rescues
Mathematics
Mathematics and Statistics
Natural disasters
Operations research
Reconfiguration
Transportation planning
Travel time
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The optimization models and algorithms with their implementations on flow over time problems have been an emerging field of research because of largely increasing human-created and natural disasters worldwide. For an optimal use of transportation network to shift affected people and normalize the disastrous situation as quickly and Efficiently as possible, contraflow configuration is one of the highly applicable operations research (OR) models. It increases the outbound road capacities by reversing the direction of arcs towards the safe destinations that not only minimize the congestion and increase the flow but also decrease the evacuation time significantly. In this paper, we sketch the state of quickest flow solutions and solve the quickest contraflow problem with constant transit times on arcs proving that the problem can be solved in strongly polynomial time O ( nm 2 (log n ) 2 ), where n and m are number of nodes and number of arcs, respectively in the network. This contraflow solution has the same computational time bound as that of the best min-cost flow solution. Moreover, we also introduce the contraflow approach with load dependent transit times on arcs and present an Efficient algorithm to solve the quickest contraflow problem approximately. Supporting the claim, our computational experiments on Kathmandu road network and on randomly generated instances perform very well matching the theoretical results. For sufficiently large number of evacuees, about double flow can be shifted with the same evacuation time and about half time is sufficient to push the given flow value with contraflow reconfiguration.
ISSN:1674-7283
1869-1862
DOI:10.1007/s11425-017-9264-3