Validation of an agent-based building evacuation model with a school drill

An effective evacuation of buildings is critical to minimize casualties due to natural or anthropogenic hazards. Building evacuation models help in preparing for future events and shed light on possible shortcomings of current evacuation designs. However, such models are seldom compared or validated with real evacuations, which is a critical step in assessing their predictive capacities. This research focuses on the evacuation of a K-12 (kindergarten to 12th grade) school located within the tsunami inundation zone of Iquique, Chile. An agent-based evacuation model was developed to simulate the evacuation of approximately 1500 children and staff from the school during a global evacuation drill carried out for the entire city. The model simulates the motions of heterogeneous human agents, and the simulations were validated using video analysis of the real event. Resulting error estimations between predicted versus measured flow rates and evacuation times are 13.5% and 5.9%, respectively. The good agreement between the simulated and measured values can be attributed to the known distribution of students and staff at the start of the drill, and their known exposure to emergency preparedness protocols. However, the results presented herein show that this mathematical evacuation model can be used for logistical changes in the emergency planning.     

Risk-based spatial zone determination problem for stage-based evacuation operations

This study seeks to determine risk-based evacuation subzones for stage-based evacuation operations in a region threatened/affected by a disaster so that information-based evacuation strategies can be implemented in real-time for the subzone currently with highest evacuation risk to achieve some system-level performance objectives. Labeled the evacuation risk zone (ERZ), this subzone encompasses the spatial locations containing the population with highest evacuation risk which is a measure based on whether the population at a location can be safely evacuated before the disaster impacts it. The ERZ for a stage is calculated based on the evolving disaster characteristics, traffic demand pattern, and network supply conditions over the region in real-time subject to the resource limitations (personnel, equipment, etc.) of the disaster response operators related to implementing the evacuation strategies. Thereby, the estimated time-dependent lead time to disaster impact at a location and the estimated time-dependent clearance time based on evolving traffic conditions are used to compute evacuation risk. This time-unit measure of evacuation risk enables the ERZ concept to be seamlessly applied to different types of disasters, providing a generalized framework for mass evacuation operations in relation to disaster characteristics. Numerical experiments conducted to analyze the performance of the ERZ-based paradigm highlight its benefits in terms of better adapting to the dynamics of disaster impact and ensuring a certain level of operational performance effectiveness benchmarked against the idealized system optimal traffic pattern for the evacuation operation, while efficiently utilizing available disaster response resources.     

A threshold model of social contagion process for evacuation decision making

Individual evacuation decisions are often characterized by the influence of one’s social network. In this paper a threshold model of social contagion, originally proposed in the network science literature, is presented to characterize this social influence in the evacuation decision making process. Initiated by a single agent, the condition of a cascade when a portion of the population decides to evacuate has been derived from the model. Simulation models are also developed to investigate the effects of community mixing patterns and the initial seed on cascade propagation and the effect of previous time-steps considered by the agents and the strength of ties on average cascade size. Insights related to social influence include the significant role of mixing patterns among communities in the network and the role of the initial seed on cascade propagation. Specifically, faster propagation of warning is observed in community networks with greater inter-community connections.     

A three-stage evacuation decision-making and behavior model for the onset of an attack

Pedestrian behavior models have successfully reproduced human movement in many situations. However, few studies focus on modeling human behavior in the context of terrorist attacks. Terrorist attacks commonly occur in crowded public areas and result in a large number of casualties. This paper proposes a three-stage model to reproduce a series of complex behaviors and decision-making processes at the onset of an attack, when pedestrians generally do not have clear targets and have to deal with fuzzy information from the attack. The first stage of the model builds a Bayesian belief network to represent the pedestrians’ initial judgment of the threat and their evacuation decisions. The second stage focuses on pedestrians’ global assessment of the situation through an analogy with diffusion processes. The third stage uses a cost function to reproduce the trade-offs of distance, safety, and emotional impact when considering a path to take. The model is validated using a video from the November 2015 Paris attack. The behavioral characteristics and trajectories of three pedestrians extracted from the video are reproduced by the simulation results based on the model. The research can be used to set rules when performing risk analysis and strategic defensive resource allocation of terrorist attacks using agent-based simulation methods.     

A mathematical programming technique for matching time-stamped records in logistics and transportation systems

Time-stamped data for transportation and logistics are essential for estimating times on transportation legs and times between successive stages in logistic processes. Often these data are subject to recording errors and omissions. Matches must then be inferred from the time stamps alone because identifying keys are unavailable, suppressed to preserve confidentiality, or ambiguous because of missing observations. We present an integer programming (IP) model developed for matching successive events in such situations and illustrate its application in three problem settings involving (a) airline operations at an airport, (b) taxi service between an airport and a train station, and (c) taxi services from an airport. With data from the third setting (where a matching key was available), we illustrate the robustness of estimates for median and mean times between events under different random rates for “failure to record”, different screening criteria for outliers, and different target times used in the IP objective. The IP model proves to be a tractable and informative tool for data matching and data cleaning, with a wide range of potential applications.     

A bikeway network design model for urban areas

This work develops a bikeway network design model for cycling in urban areas. The objectives of the proposed model are to minimize cyclist risk, maximize cyclist comfort, maximize service coverage for residents, and minimize the impact of the bikeway on existing traffic. The proposed model considers the following constraints: bikeway type, monetary budgets, path continuities, and value ranges of decision variables. Grey numbers are employed to deal with parameter uncertainties, and the proposed model is developed as a multi-objective grey 0–1 programming problem. A case study of the Xinyi District, Taipei City, is conducted. The grey one-stage algorithm is applied to solve this problem. In total, six non-dominated alternatives are generated for the case study. In comparing model alternatives with the existing network, this work confirms that the existing biking network prioritizes cyclist comfort. Scenario analyses indicate that maintaining the lower bound of the length percentage of wooded areas at 20–40 % generates better performance than that of the other scenarios, while decreasing the number of traffic accidents only decreases cyclist risk and does not alter the other objectives. The proposed model is the first network design model for bikeways in literature and will assist bikeway planners in developing alternatives for further evaluation and in developing detailed designs efficiently and systematically.     

Compromising system and user interests in shelter location and evacuation planning

Traffic management during an evacuation and the decision of where to locate the shelters are of critical importance to the performance of an evacuation plan. From the evacuation management authority’s point of view, the desirable goal is to minimize the total evacuation time by computing a system optimum (SO). However, evacuees may not be willing to take long routes enforced on them by a SO solution; but they may consent to taking routes with lengths not longer than the shortest path to the nearest shelter site by more than a tolerable factor. We develop a model that optimally locates shelters and assigns evacuees to the nearest shelter sites by assigning them to shortest paths, shortest and nearest with a given degree of tolerance, so that the total evacuation time is minimized. As the travel time on a road segment is often modeled as a nonlinear function of the flow on the segment, the resulting model is a nonlinear mixed integer programming model. We develop a solution method that can handle practical size problems using second order cone programming techniques. Using our model, we investigate the importance of the number and locations of shelter sites and the trade-off between efficiency and fairness.     

Location planning for transit-based evacuation under the risk of service disruptions

The effectiveness of transit-based emergency evacuation highly depends on the location of pick-up facilities, resource allocation, and management. These facilities themselves are often subject to service disruptions during or after the emergency. This paper proposes a reliable emergency facility location model that determines both pre-emergency facility location planning and the evacuation operations afterwards, while facilities are subject to the risk of disruptions. We analyze how evacuation resource availability leverages individual evacuees’ response to service disruptions, and show how equilibrium of the evacuee arrival process could be reached at a functioning pick-up facility. Based on this equilibrium, an optimal resource allocation strategy is found to balance the tradeoff between the evacuees’ risks and the evacuation agency’s operation costs. This leads to the development of a compact polynomial-size linear integer programming formulation that minimizes the total expected system cost from both pre-emergency planning (e.g., facility set-up) and the evacuation operations (e.g., fleet management, transportation, and exposure to hazardous surroundings) across an exponential number of possible disruption scenarios. We also show how the model can be flexibly used to plan not only pre-disaster evacuation but also post-disaster rescue actions. Numerical experiments and an empirical case study for three coastal cities in the State of Mississippi (Biloxi, Gulfport, and D’lberville) are conducted to study the performance of the proposed models and to draw managerial insights.     

Leveraging social networks for efficient hurricane evacuation

One of the important factors affecting evacuation performance is the departure time choices made by evacuees. Simultaneous departures of evacuees can lead to overloading of road networks causing congestion. We are especially interested in cases when evacuees subject to little or no risk of exposure evacuate along with evacuees subject to higher risk of threat (also known as shadow evacuation). One of the reasons for correlated evacuee departures is higher perceived risk of threat spread through social contacts. In this work, we study an evacuation scenario consisting of a high risk region and a surrounding low risk area. We propose a probabilistic evacuee departure time model incorporating both evacuee individual characteristics and the underlying evacuee social network. We find that the performance of an evacuation process can be improved by forcing a small subset of evacuees (inhibitors) in the low risk area to delay their departure. The performance of an evacuation is measured by both average travel time of the population and total evacuation time of the high risk evacuees. We derive closed form expressions for average travel time for ER random network. A detailed experimental analysis of various inhibitor selection strategies and their effectiveness on different social network topologies and risk distribution is performed. Results indicate that significant improvement in evacuation performance can be achieved in scenarios where evacuee social networks have short average path lengths and topologically influential evacuees do not belong to the high risk regions. Additionally, communities with stronger ties improve evacuation performance.     

A heuristic model of bounded route choice in urban areas

There is substantial evidence to indicate that route choice in urban areas is complex cognitive process, conducted under uncertainty and formed on partial perspectives. Yet, conventional route choice models continue make simplistic assumptions around the nature of human cognitive ability, memory and preference. In this paper, a novel framework for route choice in urban areas is introduced, aiming to more accurately reflect the uncertain, bounded nature of route choice decision making. Two main advances are introduced. The first involves the definition of a hierarchical model of space representing the relationship between urban features and human cognition, combining findings from both the extensive previous literature on spatial cognition and a large route choice dataset. The second advance involves the development of heuristic rules for route choice decisions, building upon the hierarchical model of urban space. The heuristics describe the process by which quick, ‘good enough’ decisions are made when individuals are faced with uncertainty. This element of the model is once more constructed and parameterised according to findings from prior research and the trends identified within a large routing dataset. The paper outlines the implementation of the framework within a real-world context, validating the results against observed behaviours. Conclusions are offered as to the extension and improvement of this approach, outlining its potential as an alternative to other route choice modelling frameworks.     

Behavior-consistent information-based network traffic control for evacuation operations

The evacuation operations problem aims to avoid or mitigate the potential loss of life in a region threatened or affected by a disaster. It is shaped to a large extent by the evolution of evacuation traffic resulting from the demand–supply interactions of the associated transportation network. Information-based control is a strategic tool for evacuation traffic operations as it can enable greater access to the affected population and more effective response. However, comparatively few studies have focused on the implementation of information-based control in evacuation operations. This study develops a control module for evacuation operations centered on addressing the demand–supply interactions by using behavior-consistent information strategies. These strategies incorporate the likely responses of evacuees to the information provided in the determination of route guidance information. The control module works as an iterative computational process involving an evacuee route choice model and a control model of information strategies to determine the route guidance information to direct evacuation traffic so as to approach a desired network traffic flow pattern. The problem is formulated as a fuzzy logic based optimization framework to explicitly incorporate practical concerns related to information dissemination characteristics and social equity in evacuation operations. Numerical experiments highlight the importance of accounting for the demand–supply interactions, as the use of behavior-consistent information strategies can lead evacuee route choices to approach the operator-desired proportions corresponding to the desired traffic pattern. The results also indicate that while a behavior-consistent information strategy can be effective, gaps with the desired route proportions can exist due to the discrete nature of the linguistic messages and the real-world difficulty in accurately modeling evacuees’ actual route choice behavior.     

Order-first split-second methods for vehicle routing problems: A review

Cluster-first route-second methods like the sweep heuristic (Gillett and Miller, 1974) are well known in vehicle routing. They determine clusters of customers compatible with vehicle capacity and solve a traveling salesman problem for each cluster. The opposite approach, called route-first cluster-second, builds a giant tour covering all customers and splits it into feasible trips. Cited as a curiosity for a long time but lacking numerical evaluation, this technique has nevertheless led to successful metaheuristics for various vehicle routing problems in the last decade. As many implementations consider an ordering of customers instead of building a giant tour, we propose in this paper the more general name of ordering-first split-second methods. This article shows how this approach can be declined for different vehicle routing problems and reviews the associated literature, with more than 70 references.     

Model and a solution algorithm for the dynamic resource allocation problem for large-scale transportation network evacuation

Allocating movable resources dynamically enables evacuation management agencies to improve evacuation system performance in both the spatial and temporal dimensions. This study proposes a mixed integer linear program (MILP) model to address the dynamic resource allocation problem for transportation evacuation planning on large-scale networks. The proposed model is built on the earliest arrival flow formulation that significantly reduces problem size. A set of binary variables, specifically, the beginning and the ending time of resource allocation at a location, enable a strong formulation with tight constraints. A solution algorithm is developed to solve for an optimal solution on large-scale network applications by adopting Benders decomposition. In this algorithm, the MILP model is decomposed into two sub-problems. The first sub-problem, called the restricted master problem, identifies a feasible dynamic resource allocation plan. The second sub-problem, called the auxiliary problem, models dynamic traffic assignment in the evacuation network given a resource allocation plan. A numerical study is performed on the Dallas–Fort Worth network. The results show that the Benders decomposition algorithm can solve an optimal solution efficiently on a large-scale network.     

Estimating road network accessibility during a hurricane evacuation: A case study of hurricane Irma in Florida

Understanding the spatio-temporal road network accessibility during a hurricane evacuation—the level of ease of residents in an area in reaching evacuation destination sites through the road network—is a critical component of emergency management. While many studies have attempted to measure road accessibility (either in the scope of evacuation or beyond), few have considered both dynamic evacuation demand and characteristics of a hurricane. This study proposes a methodological framework to achieve this goal. In an interval of every six hours, the method first estimates the evacuation demand in terms of number of vehicles per household in each county subdivision (sub-county) by considering the hurricane’s wind radius and track. The closest facility analysis is then employed to model evacuees’ route choices towards the predefined evacuation destinations. The potential crowdedness index (PCI), a metric capturing the level of crowdedness of each road segment, is then computed by coupling the estimated evacuation demand and route choices. Finally, the road accessibility of each sub-county is measured by calculating the reciprocal of the sum of PCI values of corresponding roads connecting evacuees from the sub-county to the designated destinations. The method is applied to the entire state of Florida during Hurricane Irma in September 2017. Results show that I-75 and I-95 northbound have a high level of congestion, and sub-counties along the northbound I-95 suffer from the worst road accessibility. In addition, this research performs a sensitivity analysis for examining the impacts of different choices of behavioral response curves on accessibility results.     

A network flow model for lane-based evacuation routing

Most traffic delays in regional evacuations occur at intersections. Lane-based routing is one strategy for reducing these delays. This paper presents a network flow model for identifying optimal lane-based evacuation routing plans in a complex road network. The model is an integer extension of the minimum-cost flow problem. It can be used to generate routing plans that trade total vehicle travel-distance against merging, while preventing traffic crossing-conflicts at intersections. A mixed-integer programming solver is used to derive optimal routing plans for a sample network. Manual capacity analysis and microscopic traffic simulation are used to compare the relative efficiency of the plans. An application is presented for Salt Lake City, Utah.     

A new shared vehicle system for urban areas

The paper concerns the conceptual design of a transport system for pedestrian areas. The proposed transport system is based on a fleet of eco-sustainable Personal Intelligent City Accessible Vehicles (PICAVs). The vehicles are shared through the day by different users and the following specific services will be provided: instant access, open ended reservation and one way trips. Referring to the proposed transport system, a new methodology to optimise the fleet dimension and its distribution among the stations is proposed in this paper. The problem faced is an optimisation problem where the cost function to be minimised takes into account both the transport system cost and the user costs that depend on the waiting times. A random search algorithm has been adopted. Given a fleet dimension and its distribution among the stations, the waiting times of the users are assessed by a microscopic simulation. The simulation model tracks the second-by-second activity of each PICAV user, as well as the second-by-second activity of each vehicle. The overall methodology has been implemented in an object-oriented simulator. The proposed transport system has been planned and simulated for the historical city centre of Genoa, Italy.     

Mapping evacuation risk on transportation networks using a spatial optimization model

The focus of this paper is on the development of a methodology to identify network and demographic characteristics on real transportation networks which may lead to significant problems in evacuation during some extreme event, like a wildfire or hazardous material spill. We present an optimization model, called the critical cluster model, that can be used to identify small areas or neighborhoods which have high ratios of population to exit capacity. Although this model in its simplest form is a nonlinear, constrained optimization problem, a special integer-linear programming equivalent can be formulated. Special contiguity constraints are needed to keep identified clusters spatially connected. We present details on how this model can be solved optimally as well as discuss computational experience for several example transportation networks. We describe how this model can be integrated within a GIS system to produce maps of evacuation risk or vulnerability. This model is now being utilized in several research projects, in Europe and the US.     

A model of an urban transportation system formulated as a multiobjective mathematical programming problem under uncertainty

An urban transportation system formulated in terms of a multiobjective mixed integer linear fractional programming (MOMILFP) problem under uncertainty is considered. The system is based on two means of public transportation i.e., trams and buses. One takes into account the factors of both passengers' and operator's concern, whose objectives are, generally, in conflict. The real uncertainty and imprecision of data is modeled by L-R type fuzzy numbers. To solve the fuzzy MOMILFP problem an interactive method is utilized. As an illustration of that approach an application to Poznan's urban transportation system is presented.