Dynamic Network Contraflow Evacuation Planning Problem

Abstract

Evacuation planning problem gives effcient way-out on existing road network that attempts to shift evacuees from risk zone to safer in minimum time with minimum casualty during disasters. Its domain based on network ow problems has been ourished with models and solutions with various network attributes. A common feature on almost all of these models is that the ow function obeys conservation constraints at each intermediate vertex. In particular, maximum dynamic ow (MDF) problem, earliest arrival ow (EAF) problem and quickest ow (QF) problem have great applicability in evacuation planning problems. Contra ow approach recon gures the network identifying ideal direction and reallocating available capacity for each arc to improve ow egress time and/or improve the number of

ow units from source to sink. This thesis sketches a brief survey of models and results on contra ow evacuation planning problems. Continuous time model for maximum dynamic contra ow (MDCF) problem is studied with its e cient solution. Thesis also extends contra ow model for multi-network. Network modi cation strategy is applied to give polynomial time algorithms to solve the problems; namely, MDCF problem and earliest arrival contra ow (EACF) problem based on extended model with discrete as well as continuous time setting. The former problems are considered in general networks whereas the latter problems in two terminal series parallel (TTSP) networks. Arc reversibility is allowed only once at time zero in each of the cases. Evacuation models with intermediate temporary shelters could be extra bene t while implementing them. This thesis formulates, as another contribution, ow model for network with capacitated vertices of given priority order in which ow conservation may be violated. This violation makes possible for ow units to be held at intermediate vertices which turns out to be applicable in modeling an evacuation planning problem with intermediate holding of evacuees at temporary shelters despite sending them into the sink. Based on this model, maximum ow problem is considered and proposed a polynomial solution for static case and pseudo-polynomial solution for dynamic case. Also, polynomial solutions for MDF problem and QF problem modeled on uniform path length (UPL) network and for EAF problem modeled on UPL-TTSP network are proposed. As the nal contribution, contra ow approach is linked to evacuation problems with capacitated prioritized vertices. Keywords: Network ow models, Contra ow, Capacitated vertices, Evacuation planning problem, Disaster management.