Evolutionary optimisation of network flow plans for emergency movement in the built environment

Abstract

Planning for emergency evacuation, and, more generally, for emergency movement involving both evacuation (egress) of occupants and ingress of first responders, presents important and challenging problems. A number of the current issues that arise during emergency incidents are due to the uncertainty and transiency of environmental conditions. In general, movement plans are formulated at building design-time, and those involved, such as building occupants and emergency responders, are left to adapt routing plans to actual events as they unfold. In the context of next-generation emergency response systems, it has been proposed to dynamically plan and route individuals during an emergency event, replanning to take account of changes in the environment. In this work, an emergency movement problem, the Maximal Safest Escape (MSE) problem, is formulated in terms that model the uncertain and transient environmental conditions as a flow problem in time-dependent networks with time-varying and stochastic edge travel-times and capacities (STV Networks). The objective of the MSE problem is to find flow patterns with the a priori maximal probability of successfully conveying all supply from the source to the sink in some given STV Network. The MSE and its deterministic counterpart are proved to be NP-hard. Furthermore, due to inherent complexity in evaluating the exact quality of candidate solutions, a simulation approximation method is presented based on well-known Monte-Carlo sampling methods. Given the complexity of the problem, and using the approximation method for evaluating solutions, it is proposed to tackle the MSE problem using a metaheuristic approach based on an existing framework that integrates Evolutionary Algorithms (EA) with a state-of-the-art statistical ranking and selection method, the Optimal Computing Budget Allocation (OCBA). Several improvements are proposed for the framework to reduce the computational demand of the ranking method. Empirically, the approach is compared with a simple fitness averaging approach and conditions under which the integrated framework is more efficient are investigated. The performance of the EA is compared against upper and lower bounds on optimal solutions. An upper bound is established through the “wait-and-see” bound, and a lower bound by a naıve random search algorithm (RSA). An experimental design is presented that allows for a fair comparison between the EA and the RSA. While there is no guarantee that the EA will find optimal solutions, this work demonstrates that the EA can still find useful solutions; useful solutions are those that are at least better than some baseline, here the lower bound, in terms of solution quality and computational effort. Experimentally, it is demonstrated that the EA performs significantly better than the baseline. Also, the EA finds solutions relatively close to the upper bound; however, it is difficult to establish how optimistic the upper bounds. The main approach is also compared against an existing approach developed for solving a related problem wrapped in a heuristic procedure in order to apply the approach to the MSE. Empirical results show that the heuristic approach requires significantly less computation time, but finds solutions of significantly lower quality. Overall, this work introduces and empirically verifies the efficacy of a metaheuristic based on a framework integrating EAs with a state-of-the-art statistical ranking and selection technique, the OCBA, for a novel flow problem in STV Networks. It is suggested that the lessons learned during the course of this work, along with the specific techniques developed, may be relevant for addressing other flow problems of similar complexity.