ABSTRACT Title of dissertation: DEVELOPMENT OF A MIXED-FLOW OPTIMIZATION SYSTEM FOR EMERGENCY EVACUATION IN URBAN NETWORKS Xin Zhang, Doctor of Philosophy, 2012 Dissertation directed by: Professor Gang-len Chang Department of Civil & Environmental Engineering In most metropolitan areas, an emergency evacuation may demand a potentially large number of evacuees to use transit systems or to walk over some distance to access their passenger cars. In the process of approaching designated pick-up points for evacuation, the massive number of pedestrians often incurs tremendous burden to vehicles in the roadway network. Hence, one critical issue in a multi-modal evacuation planning is the effective coordination of the vehicle and pedestrian flows by considering their complex interactions. The purpose of this research is to develop an integrated system that is capable of generating the optimal evacuation plan and reflecting the real-world network traffic conditions caused by the conflicts of these two types of flows. The first part of this research is an integer programming model designed to optimize the control plans for massive mixed pedestrian-vehicle flows within the evacuation zone. The proposed model, integrating the pedestrian and vehicle networks, can effectively account for their potential conflicts during the evacuation. The model can generate the optimal routing strategies to guide evacuees moving toward either their pick-up locations or parking areas and can also produce a responsive plan to accommodate the massive pedestrian movements. The second part of this research is a mixed-flow simulation tool that can capture the conflicts between pedestrians, between vehicles, and between pedestrians and vehicles in an evacuation network. The core logic of this simulation model is the Mixed-Cellular Automata (MCA) concept, which, with some embedded components, offers a realistic mechanism to reflect the competing and conflicting interactions between vehicle and pedestrian flows. This study is expected to yield the following contributions ? Design of an effective framework for planning a multi-modal evacuation within metropolitan areas; ? Development of an integrated mixed-flow optimization model that can overcome various modeling and computing difficulties in capturing the mixed-flow dynamics in urban network evacuation; ? Construction and calibration of a new mixed-flow simulation model, based on the Cellular Automaton concept, to reflect various conflicting patterns between vehicle and pedestrian flows in an evacuation network. DEVELOPMENT OF A MIXED-FLOW OPTIMIZATION SYSTEM FOR EMERGENCY EVACUATION IN URBAN NETWORKS By Xin Zhang Dissertation submitted to the Faculty of the Graduate School of the University of Maryland, College Park, in partial fulfillment of the requirements for the degree of Doctor of Philosophy 2012 Advisory Committee Members: Professor Gang-len Chang, Chair/Advisor Professor Martin Dresner Professor Ali Haghani Associate Professor David Lovell Assistant Professor Lei Zhang ? Copyright by Xin Zhang 2012 ii Acknowledgements I would like to express my gratitude to my advisor, Dr. Gang-len Chang, for his continuous support and advice throughout my study at the University of Maryland. Those long and thoughtful discussions with him about diverse research topics are helpful. He will continue to be a source of motivation and encouragement in my future career. I am very grateful to Dr. Martin Dresner, Dr. Ali Haghani, Dr. David Lovell, and Dr. Lei Zhang for their encouragement and participation in my dissertation committee. With their constructive comments and recommendations, I am able to move in the direction of perfecting my existing research. I have also learned a lot from their helpful advice and generosity in sharing their knowledge. My sincere gratitude is also extended to Dr. Paul Schonfeld and Dr. Cinzia Cirillo, for their service on the committee of my Ph.D. qualifying examination. Their persistence, skill, and integrity with which they approach their research, coupled with their devotion to education, have touched my heart and inspired me. I would also like to acknowledge my colleagues in the Traffic Safety and Operational Lab, Mark Franz, Gregory Kramida, Hyeonmi Kim, Shanjiang Zhu, Sung Park, Xianfeng Yang, Carl Lu Yang, and Woon Kim. The discussions with them on research, study, sports and activities are insightful and memorable. Finally, deep thanks to my beloved parents who have selflessly supported me for so many years. Without their unconditional love and persistent support, I wouldn?t have fulfilled my dream to finish my Ph.D. degree. iii Table of Contents LIST OF FIGURES ........................................................................................................... vi LIST OF TABLES ........................................................................................................... viii Chapter 1: Introduction ....................................................................................................... 1 1.1. Research motivation ....................................................................................... 1 1.2. Research objective and scope of work ........................................................... 3 1.3. Dissertation organization................................................................................ 5 Chapter 2: Literature Review .............................................................................................. 8 2.1. Evacuation literatures by the disaster nature .................................................. 8 2.1.1. Nuclear and chemical accidents .............................................................. 9 2.1.2. Natural Disasters ................................................................................... 12 2.1.3. Terrorist Attacks ................................................................................... 15 2.2. Vehicle optimization modeling for evacuation ............................................ 17 2.2.1. Stage evacuation ................................................................................... 18 2.2.2. Route choice.......................................................................................... 19 2.3. Pedestrian optimization modeling for evacuation ........................................ 22 2.4. Vehicle simulation models for evacuation ................................................... 24 2.5. Pedestrian simulation modeling for evacuation ........................................... 26 2.5.1. Lattice Gas / Cellular automaton simulation models for evacuation .... 27 2.5.2. Social force model for evacuation ........................................................ 28 2.5.3. Agent-based simulation models for evacuation .................................... 28 2.5.4. Simulation tools for building evacuation .............................................. 30 2.6. Mixed vehicle-pedestrian flow modeling ..................................................... 31 2.7. Review Findings ........................................................................................... 32 Chapter 3: Overview of the Framework for a Mixed-flow Evacuation System ............... 34 3.1. Two-stage evacuation process ...................................................................... 34 3.2. Critical issues in a mixed-flow evacuation .................................................. 37 3.3. Framework of the multi-modal evacuation system ...................................... 40 Chapter 4: Mixed-Flow Optimization Model ................................................................... 45 4.1. Mixed Flow Network Representation .......................................................... 46 iv 4.1.1. Components of the mixed network ....................................................... 46 4.1.2. Representation of the vehicle network .................................................. 47 4.1.3. Representation of the pedestrian network ............................................. 47 4.1.4. Representation of the connections ........................................................ 48 4.1.5. Representation of the signal controllers ................................................ 49 4.2. Network-wide mixed-flow and signal control optimization formulations ... 50 4.2.1. Constraints for vehicle flows in the vehicle network ............................ 53 4.2.2. Constraints for pedestrian flows ........................................................... 53 4.2.3. Constraints for connection links ........................................................... 54 4.2.4. Constraints for dynamic signal controllers ........................................... 54 4.2.5. Constraints for pre-timed signal controllers ......................................... 56 4.2.6. System optimal objective function........................................................ 58 4.3. Solution algorithm ........................................................................................ 61 4.3.1. Bender?s partitioning algorithm ............................................................ 62 4.3.2. A modified algorithm ............................................................................ 70 4.3.3. Reformulation of the relaxed sub-problem ........................................... 72 4.4. Numerical example ...................................................................................... 75 4.4.1. Evacuation scenario .............................................................................. 75 4.4.2. Optimized results .................................................................................. 80 4.4.3. Model Comparison................................................................................ 85 4.4.4. Algorithm performance ......................................................................... 88 4.5. Summary ...................................................................................................... 93 Chapter 5: Mixed Flow Simulation Model ....................................................................... 94 5.1. Vehicle simulation with the Cellular Automaton concept ........................... 95 5.2. Mixed-flow Cellular Automaton (MCA) framework................................... 96 5.3. Neighborhood Definition ............................................................................. 98 5.4. Floor Fields ................................................................................................ 102 5.4.1. Floor field for distance ........................................................................ 102 5.4.2. Floor field for direction ....................................................................... 104 5.4.3. Floor field for signal ........................................................................... 105 v 5.4.4. Selection of target cells ....................................................................... 106 5.5. Modeling the responses during conflict movements .................................. 108 5.6. Comparison with existing simulation programs......................................... 113 5.7. Comparison without considering pedestrians ............................................ 118 5.8. Calibration and Validation ......................................................................... 121 5.8.1. Data collection .................................................................................... 122 5.8.2. Key parameters for calibration ............................................................ 125 5.8.3. Selection of key parameters with sensitivity analysis......................... 126 5.8.4. Calibration algorithm .......................................................................... 129 5.8.5. Model calibration and validation with real-world data ....................... 135 5.9. Summary .................................................................................................... 140 Chapter 6: Conclusions and Recommendations ............................................................. 143 6.1. Research Summary ..................................................................................... 143 6.2. Potential Future Research........................................................................... 147 Reference: ....................................................................................................................... 149 vi LIST OF FIGURES Figure 1-1 A graphic illustration of Hamburg street@MD295 near the M&T stadium 2 Figure 2-1 Disasters in timeline that required major evacuation .................................. 9 Figure 2-2 Evacuation Models in Timeline ................................................................ 17 Figure 3-1 The mixed-flow evacuation procedure ...................................................... 35 Figure 3-2 The two-stage evacuation process ............................................................. 36 Figure 3-3 The framework of the multimode evacuation system ............................... 44 Figure 4-1 A graphic illustration of the vehicle network ............................................ 47 Figure 4-2 A graphic illustration of the pedestrian network ....................................... 48 Figure 4-3 A graphic illustration of the connection between the two networks ......... 49 Figure 4-4 Ring-and-barrier diagram for a typical four-leg intersection .................... 49 Figure 4-5 Ring-and-barrier diagram with an additional exclusive right turn phase .. 50 Figure 4-6 The mixed-flow network and the expanded network ................................ 59 Figure 4-7 An example of the unrealistic flow ........................................................... 61 Figure 4-8 The Bender?s Decomposition algorithm ................................................... 70 Figure 4-9 The revised Bender?s Decomposition algorithm ....................................... 72 Figure 4-10 A graphic illustration of connectors and hold-over arcs ......................... 73 Figure 4-11 Layout of the M&T stadium in Baltimore city ....................................... 75 Figure 4-12 Representation of the pedestrian network ............................................... 76 Figure 4-13 Representation of the vehicle network .................................................... 78 Figure 4-14 The signal phase plan for Russell St@MD295 ....................................... 79 Figure 4-15 Optimized Moving Directions for Pedestrians ........................................ 80 Figure 4-16 Throughput comparisons between the dynamic and pre-timed controller ..................................................................................................................................... 84 Figure 4-17 Pedestrian flow distribution in the network ............................................ 84 Figure 4-18 Vehicle flow distribution in the network ................................................ 85 Figure 4-19 Conventional signal phase for Intersection 1 .......................................... 86 Figure 4-20 Comparisons between utilization ratios of two particular conflict movements .................................................................................................................. 87 Figure 4-21 Convergence comparisons between the two algorithms ......................... 90 Figure 5-1 Cell lattice representation of an example intersection .............................. 97 Figure 5-2 Neighborhood cells for different maximum velocities ............................. 99 Figure 5-3 Example of diagonal moves .................................................................... 102 Figure 5-4 Distance floor field of an example intersection ...................................... 103 vii Figure 5-5 Examples of direction floor fields ........................................................... 105 Figure 5-6 Examples of signal floor fields for vehicle and pedestrian network ....... 105 Figure 5-7 An example of decision making for the next movement ........................ 108 Figure 5-8 Types of conflicts at an intersection........................................................ 109 Figure 5-9 An example to illustrate the cost factor ................................................... 111 Figure 5-10 Examples of potential conflicts ............................................................. 113 Figure 5-11 layout of the intersection ....................................................................... 114 Figure 5-12 Signal timing plan for the intersection .................................................. 116 Figure 5-13 The road network between the gate and Stamp Union ......................... 119 Figure 5-14 The distribution of different driver behaviors ....................................... 119 Figure 5-15 Overall calibration and validation procedure ........................................ 122 Figure 5-16 The layout of the data collection site .................................................... 123 Figure 5-17 The signal plan for the intersection ....................................................... 123 Figure 5-18 The free-moving speed distributions .................................................... 124 Figure 5-19 The cumulative counts for pedestrian and vehicle movements ........... 124 Figure 5-20 The delay distributions for pedestrian and vehicle movements ............ 125 Figure 5-21 Delay plots for levels of signal floor field weight ................................. 128 Figure 5-22 The confidence intervals of the delays ................................................. 135 Figure 5-23 The convergence of the GA algorithm ................................................. 136 Figure 5-24 Delay confidence bands ....................................................................... 137 Figure 5-25 Re-calibrated delay confidence bands .................................................. 139 viii LIST OF TABLES Table 2-1 Route choice and departure scheduling models for evacuations ................ 22 Table 2-2 Characteristics of selected vehicle simulation tools for evacuation ........... 26 Table 2-3 Characteristics of selected pedestrian simulation tools for evacuation ...... 31 Table 4-1 Connection node information ..................................................................... 77 Table 4-2 Conflict flow movements at intersections .................................................. 78 Table 4-3 Movements for Signal Phases .................................................................... 79 Table 4-4 Minimum and maximum green for signal phases of intersection-1 ........... 81 Table 4-5 Optimized Cycles for Dynamic Signal Controller 1 .................................. 82 Table 4-6 Optimized Cycles for Pre-timed Signal Controller-1 ................................. 83 Table 4-7 Optimized cycles for conventional pre-timed signal controller-1 .............. 86 Table 4-8 Comparison between different objectives .................................................. 88 Table 4-9 Algorithm Performance Comparisons ........................................................ 89 Table 4-10 Computation comparisons of different optimality conditions .................. 92 Table 5-1 Demand settings ....................................................................................... 115 Table 5-2 Comparison between the delay (s) output for every scenario .................. 117 Table 5-3 Paired t-test results for every scenario ...................................................... 118 Table 5-4 The vehicle and pedestrian demand ......................................................... 120 Table 5-5 Measures of Effectiveness of the Two Simulations ................................. 121 Table 5-6 ANOVA test result on the individual tunable parameters ........................ 128 Table 5-7 The target, initial and calibrated parameter values ................................... 133 Table 5-8 The delay comparisons between the simulated and observed data .......... 134 Table 5-9 The calibrated parameter values ............................................................... 137 Table 5-10 Comparisons between the simulation result and the validation data ...... 139 1 Chapter 1: Introduction 1.1. Research motivation Mitigating traffic congestion during emergency evacuation has evolved as a major task for traffic management authorities over the past decades. In congested metropolitan areas, commuters are likely to depend either on mass transit or on other modes for their daily commutes. Thus, during an emergency evacuation, evacuees often need to move over some distance to their designated locations, and the massive number of pedestrians may consequently incur a tremendous burden on vehicles in the roadway network. For example, after a football game in the M&T football stadium in the Baltimore downtown area (see Figure 1-1), a massive number of people will have to cross the streets to get to their parking lots or transit stops. Conflicts between pedestrian and vehicle flows may inevitably take place in the roadway network. To minimize such potential conflicts, one first needs to identify possible paths between each pedestrian or vehicle O-D (Origin-Destination) pair, and then to provide the guidance for them to distribute among all paths. Since there is a large number of pedestrians to be evacuated during any emergency event, the conflicts between these two types of flows need to be properly coordinated, by either manually directing the evacuation traffic at intersections or by setting effective signal control strategies. 2 Figure 1-0-1 A graphic illustration of Hamburg street@MD295 near the M&T stadium Conceivably, preventing the formation of bottlenecks due to conflicts between vehicle and pedestrian flows is one of the most critical issues in minimizing the evacuation clearance time. Effective control measures can help to improve the evacuation efficiency and reduce the clearance time. To plan for emergency evacuation, responsible agencies often need to make the following decisions: (1) choosing the possible shelters and safe destinations; (2) coordinating and guiding evacuees from each evacuation zone to their assigned locations; and (3) optimizing the signal timings and controls at major intersections and ramps. Any model or tool designed to assist responsible agencies in making such decisions should be capable of projecting the traffic conditions under various evacuation scenarios and then 3 providing the best route guidance and the responsive control strategy to maximize the evacuation efficiency. To offer these required functions, a candidate model or tool needs to explicitly consider the complex interactions between vehicles and pedestrians and realistically capture the responses as well as the conflicts of these flows during their evacuation process. Despite the increasing number of studies on either vehicle or pedestrian evacuation, the complex issues associated with urban evacuation, such as the conflicts between vehicle and pedestrian flows, have not been adequately addressed. Hence, development of an integrated system to provide all essential information for planning and management of urban evacuation remains an imperative task. The proposed system for such needs includes an operational model to coordinate both the pedestrian and vehicle flows and a simulation model to replicate and evaluate the mixed-flow evolution during the evacuation process. 1.2. Research objective and scope of work The primary objective of this study is to develop an integrated operating system that can effectively assist responsible agencies in planning and real-time management of any emergency evacuation. The proposed system offers the following functions to contend with congestion during the evacuation process: ? Guiding evacuees in scheduling their departure times and selecting the designated paths; ? Optimizing the assignment of safe destinations for evacuees and directing individual vehicles from their parking areas; 4 ? Providing signal plans to accommodate the massive crossing evacuees and to coordinate the conflicts between the vehicle and pedestrian flows at intersections; and ? Simulating the interactions of pedestrian and vehicle flows in an emergency evacuation environment and evaluating the effectiveness of any candidate evacuation strategy. To achieve the above objective and to produce an effective system with all essential functions, this research comprises the following principal tasks: Task 1: Literature review. An in-depth investigation of all traffic studies for evacuation and the related modeling techniques, including optimization algorithms and simulation models for both the vehicle and pedestrian flows; Task 2: Development of an effective system structure for the mixed-flow evacuation. The focus was to highlight the critical roles of all principal system components and their interrelationships as well as key functions; Task 3: Formulations of the integrated optimization model. This task was to formulate the mathematic equations for the dynamic mixed traffic flow and signal timings where intersections can be either under a pre-timed or a time-dependent signal control; Task 4: Design of an efficient solution algorithm for the mixed-flow optimization model. The core of this task was to develop an efficient algorithm to efficiently solve the proposed formulations for mixed-flow evacuation in urban networks; 5 Task 5: Development of a mixed-flow simulation model. This task developed a tool that was capable of capturing the complex interactions between evacuees and vehicles in the evacuation process as well as reflecting their way-finding and conflict avoidance behaviors; Task 6: Calibrations and validations of the proposed simulation model. Videos from congested mixed-flow intersections were recorded and processed in this task to ensure that the developed mixed-flow simulation model can offer the desirable level of fidelity to the actual traffic conditions. 1.3. Dissertation organization The entire dissertation is divided into seven chapters. The next chapter reviews the existing literature related to either the vehicle flow optimization or the pedestrian behavior responses during emergency evacuation. Classified by incident nature, Section 2.1 first presents those studies associated with nuclear and chemical emergencies, natural disasters, and terrorist attacks. Section 2.2 summarizes the related literature in the stage evacuation of vehicle flows and the route choice prediction. Section 2.3 reports the pedestrian evacuation modeling efforts, focusing mostly on in-building evacuation process. Sections 2.4 and 2.5 evaluate various modeling efforts on simulations of vehicle and pedestrian flows during evacuation. Section 2.6 briefly describes the limited existing modeling efforts on mixed pedestrian-vehicle flows. Chapter 3 presents the overall system structure for emergency evacuation in urban networks. Section 3.1 explains the concept of the two-stage evacuation, where its first 6 stage is to evacuate evacuees and/or vehicles within the impact zone and the second stage is to direct all vehicles to specified destinations. Section 3.2 identifies critical associated issues from a traffic manager?s perspective, including departure scheduling, path selections, signal control settings, and transit dispatches. Sec 3.3 illustrates the framework of a mixed-flow optimization system, highlighting the main functions and the modeling challenges of the two principal models: the mixed-flow optimization and the mixed-flow simulation models. Chapter 4 describes the core logic of the mixed-flow optimization module, focusing on the formulations of an integrated mixed-flow network model and the phase design for signal control. In section 4.1, the mixed-flow network is represented with the vehicle network, the pedestrian network, and the connectors between them. The special signal phase is designed to accommodate the massive number of crossing pedestrians at intersections. Section 4.2 details an integer-linear optimization model that is proposed to produce the routing strategies for vehicle and pedestrian flows as well as signal timings within the evacuation zone. Section 4.3 proposes a revised algorithm to solve the formulation based on Bender?s Decomposition. Section 4.4 presents an illustrative case with the proposed model to show the applicability of the formulations and the efficiency of the solution algorithm. Section 4.5 summarizes the key concepts of the proposed mixed-flow optimization model. Chapter 5 discusses the key logic used to develop the mixed-flow simulation model, based on the Mixed-Cellular Automaton (MCA) concept that consists of two overlapped layers of rectangular grids for vehicles and pedestrians, respectively. Section 5.1 introduces the core concept, grounded on the Cellular Automaton (CA) 7 model, for vehicle flow simulation. Section 5.2 details the mixed-flow CA framework, including the cell representation and the simulation evolution process. Section 5.3 defines the neighborhood structure for the cells, taking the diagonal movements into consideration. Section 5.4 highlights the floor field concepts, designed to reflect those factors influencing the way-finding behavior. Section 5.5 models the conflict avoidance during individual movements, focusing on the use of competition factors to represent the behavior discrepancies among evacuees. Section 5.6 compares the developed vehicle simulation model with the existing traffic simulation software. Section 5.7 evaluates the results generated with and without considering the impact of pedestrians on the vehicle flows. Section 5.8 discusses the calibration and validation procedure of the proposed mixed-flow simulation model. Section 5.9 summarizes all key components in the proposed mixed-flow simulation model. Chapter 6 summarizes the research findings and the potential future research directions. 8 Chapter 2: Literature Review This chapter presents the literature review of various models and methodologies associated with emergency evacuation. To facilitate the presentation, all related evacuation studies are divided into the following categories based on the incident nature: nuclear and chemical incidents, natural disasters and terrorist attacks. 2.1. Evacuation literature by the disaster nature Depending on the nature of the disaster and the evacuation process, one can classify most evacuation studies into three categories: nuclear and chemical accidents, hurricane and other environmental disasters, and terrorist attacks. The major events of these disasters over the past decades are shown in Figure 2-1. The font size is used to reflect the severity of each incident. 9 1980 1990 2000 2010 1980 1990 2000 2010 1980 1990 2000 2010 Nuclear and Chemical Hurricanes Terrorist Attacks Three Mile Island Nuclear Incident (1979) SL-1 Nuclear Accident (1961) Greifswald Nuclear Accident in Germany (1975) Czech Nuclear Incident (1977) Nuclear Accident in Alabama (1984) Nuclear Accident in Alabama (1985) Chernobyl Nuclear Incident (1986) Nuclear Accident in Pennsylvania (1987) Nuclear Accident in Maryland (1989) Nuclear Accident in Florida (1996) Tokaimura Nuclear Incident in Japan (1997) Nuclear Accident in Ohio (2002) Mihama Accident in Japan (2004) Fukushima Nuclear Disaster (2011) Hurricane Hugo (1989) Hurricane Andrew (1992) Hurricane Opal (1995) Hurricane Mitch (1998) Hurricane Floyd (1999) Hurricane Fran (1996) Hurricane Keith (2000) Hurricane Isabel (2003) Hurricane Allison (2001) Hurricane Ivan (2004) Hurricane Katrina (2005) Hurricane Dean (2007) Hurricane Ike (2008) 911 terrorist attack (2001) Tokyo Subway System Attack (2005) IRA Attacks on London Undergrounds (1973-1992) Attacks on French Surface Transportation (1970-1995) Figure 2-0-1 Disasters in timeline that required major evacuation 2.1.1. Nuclear and chemical accidents In response to the Three-Mile Island nuclear incident, Urbanik (1980; 2000) first examined the methods for estimating evacuation times at nuclear power plants, sponsored by the U.S. Nuclear Regulatory Commission and the Federal Emergency 10 Management Agency. Urbanik?s research, along with the work by Federal Emergency Management Agency contractors, constitutes the basis for the NUREG-0654/FEMA- REP-1 (U.S. Nuclear Regulatory Commission 1980), which provides the guidelines for estimating the evacuation time. For the same purpose, some researchers developed NETVACI (Sheffi, 1982), a macro traffic simulation model used primarily to assess the evacuation time during a nuclear plant emergency. The resulting evacuation times of these studies are sensitive to the network topology, intersection design, and a wide array of evacuation management strategies. TEVAS (Han, 1990) is an adaptation of NETVACI for multimodal networks in Taiwan. EVAC PLAN PACK (PRC, 1982) is a probabilistic model, considering human behavior issues in estimating the loading and response rate of evacuees. CLEAR (Calculates Logical Evacuation And Response) is a microscopic simulation model developed by the U.S. Nuclear Regulatory Commission (Moeller, 1982). DYNEV (DYnamic Network EVacuation) by KLD Associates (1984) is a macroscopic simulation model for determining the impact of various traffic controls, network capacity, and evacuation demand during the evacuation period, which has been used to compute the evacuation travel times at nuclear power stations (FEMA, 1984). SNEM (Stern, 1989; Sinuany, 1993) is a micro-simulation model for radiological evacuation that incorporates behavioral aspects of the evacuees in the simulation process. 11 TEDSS (Transportation Evacuation Decision Support System, 1994) is a software package for the analysis, evaluation, and development of evacuation plans around nuclear power stations developed by Hobeika (1994). The simulation module of TEDSS is an event-type simulation designed to load evacuees onto the roadway network according to the best evacuation routes, based on the simulation model MASSVAC (Hobeika, 1985). RODOS (Ehrhardt, 1997; French, 1998) is a Real-time On-line DecisiOn Support system designed to provide off-site emergency management in the event of radiation incidents. The system can predict the radiological level over time and simulates countermeasures such as evacuation, sheltering, and food supply. The system is capable of evaluating and generating (Papamichail, 1999) feasible strategies, for use by the decision makers (Papamichail, 2000). Focusing on analyzing various operational issues, Dunning (2007) studied the transportation impacts caused by a train wreck and chlorine spill in Graniteville, South Carolina. He highlighted some key evacuation issues, such as how to determine the shelter locations, what routes would best protect people given different hazardous materials, and the role of transportation professionals in working with emergency responders. Paraskevi (2007) developed a model to generate evacuation plans, providing the temporal and spatial distribution of the evacuees around a major hazard facility. The proposed plans include critical actions, such as sheltering the population, evacuating the population from the exposure zone, and providing gas masks and medicines. 12 Aside from nuclear plants, Newsom (1992) addressed the evacuation issues near the chemical stockpile sites. Sorenson (1992) developed a systematic methodology that can be used to identify emergency planning zones for hazardous chemical stockpile facilities. 2.1.2. Natural Disasters The increased development in the coastal area, together with rising sea levels and climatic trends, has exposed more populations to hurricane threats. To address this issue, Pielke (1998) provided normalized data for the hurricanes plaguing the United States between 1925-1995, and reported the tremendous economic loss. Most early studies along this line tend to focus on hurricane evacuation plans (Urbanik, 1978; COE, 1979). For instance, the Federal Emergency Management Agency initiated the Hurricane Evacuation Studies (HES) to integrate various key tasks in evacuation planning and disaster preparedness. HES consist of critical analysis on the hazard level, population vulnerability, evacuee behavior, sheltering availability, and transportation capacity. The massive evacuation and resulting traffic problems during Hurricanes Andrew in 1992, Georges in 1998, and Floyd in 1999 raised widespread concerns in studying the evacuation-related issues in response to hurricane attacks. For example, Dow (2002) conducted a survey of coastal South Carolina residents, addressing the role of household decisions during the Floyd evacuation. Radwan (1985) developed a macroscopic simulation model based on NETSIM (FHWA, 1980) for coordinating the evacuation with rural highway networks under the threat of natural disasters. His model was tested, validated, and applied to a small rural town in Virginia. 13 MASSVAC is a macroscopic traffic simulator developed to model various disasters and was used for hurricane evacuation in Virginia Beach (Hobeika, 1985). HURREVAC (HURRicane EVACuation) was developed specifically to help Emergency Managers to track hurricanes and to assist responsible agencies in making evacuation decisions for their communities (COE, 1994). HURREVAC uses data from a variety of sources, including the National Hurricane Center, inundation estimates from the SLOSH model, and related information to commence evacuations. REMS (Regional Evacuation Modeling System) is a planning module for emergency hurricane evacuation developed by the University of Florida after Hurricane Andrew (Tufekci, 1995). The software comprises a simulation and several network optimization models for use to estimate the evacuation time and the traffic flow on a given transportation network. OREMS (Oak Ridge Evacuation Modeling System) was designed to model evacuations due to a variety of disasters (ORNL, 1995), which can estimate the clearance time and identify operational deficiencies. The research team of the ORNL (Oak Ridge National Laboratory) later developed a computer-based IMDAS (Incident Management Decision Aid System) that can be used to model hurricane evacuation activities in more timely and accurate manner (Franzese, 2001). The ETIS (Evacuation Traffic Information System) was developed in the aftermath of Hurricane Floyd, mainly for the southeastern United States, including Florida, Georgia, South Carolina, and North Carolina (PBS&J, 2000; Lewis, 2001). ETIS is web-based and operated within an environment of geographic information systems. Lindell (2002a; b) implemented EMBLEM (EMpirically Based Large Scale 14 ETE Method) to generate the hurricane ETEs (Evacuation Time Estimates) used by the state of Texas (Lindell, 2002a; b). The algorithm was later revised by Lindell (2008) and included in EMBLEM2. In view of the dynamic nature of emergency evacuation, Barrett (2000) proposed a dynamic traffic management framework for hurricane evacuation. Chiu (2008) applied DynusT to model the Hurricane Rita evacuation event, focusing on contra- flow strategies in selected corridors. Brown (2009) developed an evacuation planning model that uses dynamic network loading and mesoscopic simulation techniques to represent the traffic evolution during a hurricane evacuation in the Greater Houston, Texas area. To understand critical operational issues, Wolshon (2005a; b) and Urbina (2003) reviewed the policies and practices for hurricane evacuations with extensive surveys. Their studies showed the vital need for responsible agencies to have reliable and up- to-date information for timely dissemination. The Texas Transportation Institute researched the traffic response practices of various states along the coasts of the Gulf of Mexico and the Atlantic Ocean and recommended some traffic response plans for hurricane evacuation, including contra flows, scheduled operations, traffic signs, access control issues, time-of-day operations, and ITS implementations (Ballard, 2007). Compared with hurricane evacuation-related studies, very few reports are available in the literature on traffic evacuations due to other natural disasters, such as floods and earthquakes. In this regard, Boyce (2002) performed a traffic delay 15 analysis due to flooding by the Des Plaines River, using a static user equilibrium method. Ziliaskopoulos (2003; 2004) developed an FIM (Flood Impact Methodology) to compare the base and worst-case flood scenarios with respect to traffic conditions. Wakabayashi (1992) worked on network reliability that analyzed the traffic flow in the Loma Prieta earthquake in 1989. Werner (1997) modeled bridge damage, network traffic flows, and the costs associated with traffic delays due to seismic risks. Shinozuka (1998) further linked the analysis to traffic flows, transport costs, and regional production losses due to an earthquake. 2.1.3. Terrorist Attacks In response to the 9/11 terrorist attack, Pearce (2002) reported some efforts on collaboration of transportation operators with emergency managers regarding information sharing, strategic planning, and management of transportation systems during emergencies. To ensure timely communications among evacuees and all responsible agencies, Hamza-Lup (2007) developed a Smart Traffic Evacuation Management System (STEMS) that can dynamically generate evacuation plans during terrorist attacks, based on real-time traffic information. The system can also control signals to guide evacuation traffic to target directions. Camille (2003) reviewed historical terrorist attacks on transportation systems, including attacks on the London underground and commuter rail network from 1973 to 1998, on French surface transportation systems from 1970 to 1995, and on the Tokyo subway system in 1995. The author concluded that countermeasures must be addressed and adopted within financial constraints. Aaron (2006) revealed the vulnerability of America?s transit systems, focusing on post-9/11 security measures 16 adopted by the FTA, New York City Transit, WMATA (Washington Metropolitan Area Transit Authority), San Francisco?s BART (Bay Area Rapid Transit) and Oregon?s TriMet (Tri-County Metropolitan Transportation District). Noor (2007) used VISSIM, a traffic simulation program, to capture the impact of different emergency evacuation strategies on transit facilities such as a bus depot. Their scenarios include different mode choices, route choices, bus priorities, ITS technologies, and roadway closures. Figure 2-2 summarizes all related studies in each of these categories based on the development dates. 17 1980 1990 2000 2010 1980 1990 2000 2010 1980 1990 2000 2010 Nuclear and Chemical Hurricanes Terrorist Attacks NUREG-0654/FEMA-REP-1 (Urbanik ?80) NETVACI (Sheffi ?82) EVAC PLAN PAK (PRC ?82) DYNEV (KLD ?84) CLEAR (MOELLER ?82) TEVAS (Han ?90) SNEM (Stern ?90) TEDSS (Hobeika ?94) RODOS (Ehrhardt ?97) Dunning (?07), Paraskevi (?07) Papamichail (?99) Radwan (?85) MASSVAC (Hobeika ?85) Hurricane Data (Pielke ?98) EMBLEM (Lindell ?02) HURREVAC (COE ?94) REMS (Tufekci?95) OREMS (ORNL ?95) ETIS (PBS&J ?00) IMDAS (Franzese ?01) EMBLEM2 (Lindell ?08) Brown (?09) Wolshon (?05) Urbina (?03) Ballard (?07) Pearce (?00) STEMS (Hamza-Lup ?07) Camille (?03) Aaron (?06) Figure 2-0-2 Evacuation Models in Timeline 2.2. Vehicle optimization modeling for evacuation The optimization literature for emergency evacuation can be divided into the following categories, based on the focus of operations during the emergency event: 18 ? Demand modeling: to estimate the total evacuation demands and their departure times; ? Stage evacuation: to schedule the evacuation populations over a well-specified horizon to avoid excessive congestions on the roadway network; ? Route choice: to provide evacuees the suggested routes so that the traffic flow can evolve to the desired pattern during the evacuation process; ? Contra flow operation: to reverse the inbound lanes for outbound traffic so as to increase the roadway capacity; ? Transit operations: to provide transit vehicle or train services to rescue those evacuees within the impact zone; ? Relief operations: to transport relief supplies or personnel from different areas to target locations in the disaster area; In view of the focus of this dissertation, the remaining literature review will be centered on the subject of the stage evacuation and route choice. 2.2.1. Stage evacuation Under unexpected events such as terrorist attacks, nuclear or chemical leaks, all vehicles need to evacuate concurrently, which will certainly lead to congestion and excessively delays on the streets. However, under some predictable events, such as hurricanes, the evacuation can be operated more efficiently by spreading the evacuation demands over a well-specified time horizon. In this regard, Malone (2001) applied cellular automaton to evaluate staggering the evacuation for different coastal counties in Charleston S. C. and found that it can reduce the evacuation time, depending on the direction of a hurricane. Mitchell (2006) evaluated six different 19 departure shift strategies on a given network and demonstrated that they can improve the overall clearance time. Chen (2008) demonstrated the feasibility of using agent- based modeling techniques to compare the performance between the concurrent evacuation and staged evacuation strategies. The simulation results indicated that the staged evacuation strategy would work better in high-density areas that are susceptible to congestion. Sbyati (2006) proposed a system-optimal dynamic formulation to schedule evacuation trips between a selected set of origins and safety destinations. The method of successive average (MSA) was used to find the flow assignment, and a traffic simulator, DYNASMART-P, was employed to propagate vehicles and determine the state of the system. The results were then aggregated to produce a time-dependent staging policy for each selected origin zone for evacuation. Chien (2007) developed a model to illustrate how to determine the number of evacuation stages and which zones to be evacuated during each stage, considering critical factors such as total demand, evacuation route length, access flow rate and capacity. Liu (2006) proposed a cell-based network model to determine the optimal starting time and routes for evacuees in different zones. 2.2.2. Route choice Routing people to safety areas is the primary challenge in managing a regional evacuation. Hamacher (2001) gave an overview of the mathematical models for various evacuation related issues, focusing especially on variation of modeling dynamic network flows and route choices, e.g., maximum dynamic flows, earliest arrival flows, quickest paths and flows as well as continuous dynamic flows. Ziliaskopoulos (2000) pointed out that most analytical formulations cannot 20 adequately capture all constraints in existing street networks due to simplification, and thus become intractable for a realistic size of urban networks. Heuristic approaches, especially simulation-based, fail to guarantee optimality and convergence, and also lack insights into the nature of the problem. Thus, he proposed a simple linear formulation, based on the cell transmission model, for producing the system- optimal dynamic traffic assignment to a single destination. Cova (2003) presented a lane-based routing evacuation model in a complex roadway network, intending to eliminate conflicts and reduce traffic delays at intersections. Cova?s model was inspired by the extraordinarily efficient and rapid evacuation of Los Alamos, New Mexico, during the 2000 Cerro Grande Fire. He hypothesized that the efficiency of the Los Alamos evacuation plan stemmed from a lane-based routing approach that minimized traffic conflicts. Chiu (2008) found evacuees? route choice behaviors usually lead to selecting non- optimal routes, which may result in significant degradation of evacuation effectiveness. He proposed an FIR (Feedback Information Routing) strategy by regularly providing frequently updated route information, using existing intelligent transportation system infrastructures such as detectors, cameras, and surveillance systems. Robinson (2010) identified variables associated with the decision to alter routes by carrying out a pilot behavioral survey of potential hurricane evacuees. His study reached the conclusion that the decision on whether evacuees will take the detour instruction or not is predictable and somewhat controllable by transportation managers through the discerning use of ATIS (Advanced Traveler?s Information System). Yuan (2006) simultaneous optimized the destination and route choices by 21 solving a traffic assignment problem on a modified network structure. Afshar (2008) devised a heuristic optimization procedure to provide a system-optimal solution to the time-varying traffic assignment problem. The algorithm allows for the joint optimal choice of destinations, routes, and departure times. Stepanov (2009) formulated an integer programming for system optimal route assignment, using M/G/c/c state-dependent queueing models to cope with congestion and time delays. The formulations include multiple minimization objectives with respect to clearance time, total travelled distance, and blocking probabilities. Yao (2009) developed a robust linear programming model to account for demand uncertainty during evacuation in large-scale networks. Yazici (2010) proposed an analytical CTM-based system-optimal dynamic traffic assignment model with probabilistic demand and capacity constraints to optimize the dynamic routing strategies. His model can be used to calculate the change in clearance time, average travel time, and risk exposure measures by varying different reliability levels imposed on the probabilistic constraints. Ng (2010) also presented an evacuation route planning model that accounts for the demand and capacity uncertainties. His model plans for more evacuees and less road capacity to ensure a user-specified reliability level. Zheng (2010) discussed an optimal zone-based vehicle evacuation strategy based on an optimization-simulation approach. The optimal routing strategy is obtained by solving a universal quickest flow problem and evaluated with a mesoscopic simulation model-DynusT (Chiu, 2009). His study included the background traffic in simulation and provided a more realistic representation of the traffic conditions. 22 Table 2-1 summarizes key studies on the subject of optimizing the route and/or departure strategies during emergency evacuation. (Reviewer?s note: this is an excellent summary!) Table 2-1 Route choice and departure scheduling models for evacuations Author and Year Incident Type Optimization Type Simulation Fidelity Operations Other Notes Ziliaskopoulos (2000) General System optimal Meso (CTM) Route choice Malone (2001) Coastal Hazards Candidate comparison Micro (CA) Departure Scheduling Cova (2003) General Minimum cost flow Macro Route choice Lane-based routing Mitchell (2006) Short- notice Event Heuristic ranking Macro Departure scheduling Sbyati (2006) Terrorist Attack System optimal Meso (Dynasmart) Departure scheduling SO-DTA Liu (2006) General System optimal Meso (CTM) Departure scheduling & route choice Yuan (2006) General System optimal Macro Route choice Ant-colony algorithm Chien (2007) General Candidate comparison Macro Departure scheduling Afshar (2008) Coastal Hazards Heuristic Meso Departure scheduling & route choice Chen (2008) General Candidate comparison Micro (Paramics) Departure scheduling Chiu (2008) Short- notice event System optimal Meso (DynusT) Route choice Online feedback Stepanov (2009) General System optimal Macro (M/G/C/C) Route choice Stochastic multi- objective 2.3. Pedestrian optimization modeling for evacuation Most pedestrian evacuation studies dealt with emergencies within the building environments, e.g., apartments (Proulx, 1995), university buildings (Olsson, 2001; Fang, 2010), high-rise office buildings (Cakici, 2009; Galea, 2008), dance hall (Jiang, 23 2009), classrooms (Zhang, 2008), theatres (Weckman, 1999), stadiums (Fang, 2011), malls (Chow, 2007), retail stores (Cheng, 2009), metro-stations or subways (Zhong, 2008; Jiang, 2010; Tsukahara, 2011; Shi, 2010), railway stations (Chow, 2008), ships (Lee, 2003; 2004), and facilities with low visibilities caused by fires or smoke (Isobe, 2004; Jeon, 2011). Most modeling efforts in the literature on building environments focused on finding the best departure schedules and routing strategies within the buildings for evacuees and on simulating the floor or room conditions under various scenarios. The simulation models for pedestrian evacuation will be illustrated in a subsequent section. The review hereafter covers only the optimization models for pedestrian evacuation. Note that an early static trans-shipment network model of building 101 has been widely explored as a benchmark for assessing the applicability of network flow optimization models for building evacuation (Francis, 1979; 1981). Chalmet (1982) expanded it to a dynamic model using the procedure of Ford and Fulkerson (Ford, 1956) that simultaneously maximizes the total number of people evacuating the building for all the time periods and also minimizes the time duration for the last evacuee to exit the building. An application of EVACNET (Francis, 1984a; b; 1985; Kiosk, 1998) was designed later to generate the optimal evacuation plans and to estimate evacuation times for the in-building evacuees. Choi (1987; 1988) modeled the building evacuation by solving the minimal cost dynamic network flows with side constraints of variable arc capacities. He proposed the ?greedy? algorithms for some special networks, and developed the solution procedures that take advantage of the unique network structures. Hoppe (1995) 24 proposed polynomial time algorithms for the maximum dynamic flow and quickest flow problems with a fixed number of sources and sinks. Lu (2003; 2005) developed new heuristic approaches, named single-route and multiple-route approaches, to find a sub-optimal evacuation plan with reduced computation cost. However, the heuristics requires the capacity of a link to be constant and independent of the amount of traffic flow at the link. Pursals (2009) improved Francis? model (Francis 1979; 1981) by incorporating the evacuation routes and movement equations (Nelson, 1990). Fang (2011) proposed three hierarchical objectives in optimizing a stadium evacuation, namely, to minimize total evacuation time, total evacuation distance, and the cumulative congestion level. His algorithm adopted two critical strategies: the hierarchical heuristic searching strategy of an ant and the binary pheromone updating strategy. Lin (2008) dealt with a priority evacuation where occupants are classified into several groups with different escape priorities according to their vulnerability to hazards. He proposed a multi-stage time-varying quickest flow approach for networks of dynamic features. Cepolina (2009) considered the capacity drop phenomenon under oversaturated conditions and developed an optimization model to schedule the phased evacuation. A new movement model was embedded in his optimization algorithm to assess the network?s performance. 2.4. Vehicle simulation models for evacuation Most of the simulation tools developed for vehicle evacuations are introduced in Section 2.1, such as NETVAC, ETIS, DYNEV,etc. In addition, CEMPS (Configurable Emergency Management and Planning System) is a spatial decision 25 support system that uses a Geographical Information System (GIS) to link to a specially-designed discrete simulation model (Pidd 1996; De Silva 2000). Among all the simulation tools, DYNEV and ETIS employed static assignment while NETVAC, MASSVAC and OREMS employed dynamic assignment procedures. Cova (2002) applied an off-the-shelf microscopic traffic simulator, Paramics (Quadstone, 2002; Cameron and Duncan, 1996), to design and test evacuation plans for neighborhoods in fire-prone wild-lands. Balakrishna (2008s) presented a simulation-based framework for modeling transportation network performance under emergency conditions. The system, based on a DTA framework, is demonstrated by using the Boston, Massachusetts network. Both DYNASMART-X (Mahmassani, 1993) and DynaMIT (Ben-Akiva, 2003) have the potential to be used for real-time emergency response due to their dynamic network modeling capacities. Liu (2005) applied the cell transmission model as the traffic simulation mechanism for evacuation. MITSIMLab is a microscopic simulation model for evaluating emergency evacuation plans developed for the Los Alamos National Laboratory (LANL) (Jha 2004). The network area includes all technical sections within the LANL and the towns of White Rock and Los Alamos, New Mexico. MITSIMLab can model various traffic control operations and signal plans. Zou (2005) presented an emergency evacuation system for Ocean City during hurricanes using CORSIM. The proposed system can be integrated with sensors to provide real-time evaluation of different control strategies. Georgiadou (2007) proposed a stochastic model based on Markov processes for simulating the evacuation area around a hazardous facility, 26 where the transition from node to node is simulated as a random process. A Monte Carlo solution of the model can provide actual trajectories of evacuees. Table 2-2 lists the key features of some simulation tools that have been used for modeling evacuation traffic. Table 2-2 Characteristics of selected vehicle simulation tools for evacuation Simulation tool Simulation type Incident type Assignment type Author (year) NETVACI Macro Nuclear Dynamic Sheffi (?82) CLEAR Micro Nuclear Simple Moeller (?82) DYNEC Macro Nuclear Static KLD (?84) SNEM Micro Nuclear Simple Stern (?89) MASSVAC Macro Hurricane Dynamic Hobeika (?85) TEVAS Macro Nuclear Dynamic Han (?90) HURREVAC Macro Hurricane Dynamic COE (?94) OREMS Macro General Dynamic ORNL (?99) ETIS Macro Hurricane Static Lewis (?01) DYNASMART* Meso General Dynamic Mahmassani (?95) DYNAMIT* Meso General Dynamic Ben-Akiva (?03) 2.5. Pedestrian simulation modeling for evacuation Pedestrian flows are much more complicated than vehicle flows because there is no lane channelization to guide pedestrians. There is a variety of modeling methods in the literature, but the discrete method seems to offer the best promise for use in a computing environment. The core logic of the discrete models is to divide the space into grids and set up the rules to simulate the evolution of pedestrians. These kinds of models can be easily implemented into computers and thus are widely used to study the behaviors of the pedestrians. The LG (Lattice Gas) models and the CA (Cellular Automaton) models belong to this category, which have been reported in the evacuation literature. 27 2.5.1. Lattice Gas / Cellular automaton simulation models for evacuation The lattice gas model mimics each evacuee as a biased random walker and has been adopted by Helbing (2003) and Nagai (2004, 2006) in replicating the classroom evacuation experiments. Weng (2007) described a small-grid analysis of the lattice gas model that can reproduce some typical phenomena of evacuation, such as jam, block, and faster-is-slower. Yang (2005) modeled the kin behavior in occupant evacuation through a 2D-CA model that is capable of simulating the jam, incoherence, gathering, backtracking and waiting caused by sub-groups. Yuan (2007) proposed a CA model to simulate evacuation from a room or compartment with multiple exits. Human behaviors, including the unadventurous effect, group effect and inertia effect, are considered in the modeling process. Guo (2007) combined the lattice gas model and social gas model to simulate the pedestrian evacuation process in public buildings. His model imposes much less computational burden and gives more accurate evacuation time. Abdelghany (2010) presented a framework, adopting a micro- simulation assignment approach implemented in a CA platform. It captures different behavioral rules that govern the dynamics of an evacuee?s decision, including the exit gate choice, the paths to these gates, and the frequency of updating of the exit gate choice, and the tolerance for congestion. The framework was used to evaluate the evacuation performance of one floor of the Masa?s facility in Al-Haram Al-Sharif in Makkah, Saudi Arabia. Kirchner (2002) applied a bionics approach to describe the interaction between the pedestrians during evacuations using ideas from chemotaxis. His model introduced the concept of the static and dynamic floor field to enable pedestrians to 28 make decisions based on the local field values. The dynamic floor field is a virtual trace left by the pedestrians and has its own dynamics through diffusion and decay. Kirchner (2003) compared CA-based simulation results with the experiment in aircraft evacuation toward an egress. He introduced the concept of using a friction parameter to distinguish between competitive and cooperative movements. Varas (2007) simulated the evacuation process from a room with or without obstacles. A distance floor field is calculated for each cell so that at each time step, the pedestrians try to advance to the neighboring cell with the smallest floor field value. The model also introduced a panic variable to reflect the hesitation factor among pedestrians. 2.5.2. Social force model for evacuation Helbing (2000) was the first to create the social force model for simulating the escaping panicked pedestrian dynamics during evacuations. He assumed the existence of a mixture of socio-psychological and physical forces that will influence the behavior in a crowd. Such forces include interaction forces to keep a velocity- dependent distance from other pedestrians, body forces to counteract body compression, and the sliding friction force to impede relative tangential motion. Parisi (2005) studied the room evacuation using the social force model and simulated with various desired velocities with a fixed door width. 2.5.3. Agent-based simulation models for evacuation Agent-based simulation allows users to build an artificial environment where autonomous agents are able to make their own decisions and interact with each other. Pan (2007) presented a Multi-Agent Simulation System for Egress analysis (MASSEgress) to simulate human and social behaviors during an emergency 29 evacuation. In the MASSEgress framework, each human individual is modeled as an agent who interacts with a virtual environment and other agents according to some rules. Depending on the environment and the behavioral levels of individuals, the agent could interact and react in a collaborative or competitive manner. Shi (2009) proposed an agent-based simulation program for fire evacuation?AIEva, which integrates an evacuation simulation model and a fire simulation model. The integration of evacuation simulation and fire simulation is crucially important as the behavior responses reflect the impacts of both the environmental factors and human body conditions. The model has been tested in a gymnasium for the 2008 Beijng Olympic Games with a large span that covers an area of 33*33m and an overall height of 11m. Yang (2011) used an agent-based fire and human interaction model to simulate the fire emergency evacuation in an underground subway station. The social force model is adopted in modeling agents? movements. In his model, a full coupling between the fire conditions and the human behavior is allowed. The fire conditions can influence the evacuation conditions, and evacuees? responses can also influence the impact of fire. Augustinjn-Beckers (2010) applied an agent-based evacuation model to simulate evacuation behavior for a Chinese supermarket and an international university in The Netherlands. Data collected from questionnaires and videos were used to validate the simulation model. Sensitivity analyses were conducted to investigate the effect of different pre-evacuation behaviors and exit choice strategies. Fang (2011) considered various routing choice strategies and waiting time rules 30 during a stadium evacuation and applied an agent-based simulation to test his proposed strategies. 2.5.4. Simulation tools for building evacuation Some popular simulation tools that have been developed for building evacuations are BFIRES (Stahl, 1982), EVACSIM (Drager, 1992), CRISP (Phillips, 1994), EXODUS (Galea, 1994; Owen, 1996), SIMULEX (Thompson, 1995a; b), EXIT89 (Fahy, 1993), SGEM (Lo 2000a; b) and buildingEXODUS (Galea, 2004). A comprehensive review of these models is available in the work by Gwynne (1999) and Kuligowski (2005). In general, two categories of approaches are used by the simulation tools: the coarse network approach and the fine network approach. In the former approach, a space is modeled as several interconnected nodes and arcs, where nodes usually stand for a distinct space enclosed in the building, such as a room irrespective of the enclosure size, and arcs for the actual connections of the building spaces, such as hallways or corridors. This approach describes the flow and speeds of occupant groups instead of explicitly modeling each individual. Thus, it is efficient for both operations and computation. Simulation tools that fall into this category are EVACSIM, EXIT and CRISP. In the fine network approach, the floor spaces are usually divided and covered with tiles or nodes, whose sizes and shapes vary from model to model. This kind of model consumes more memory and computation power but can accurately represent 31 the real space layout and individual response at any time. Simulation tools such as EXODUS, buildingEXODUS, SIMULEX and SGEM belong to this category. Table 2-3 lists the characteristics of some pedestrian simulation tools reported in the literature for evacuation. Table 2-3 Characteristics of selected pedestrian simulation tools for evacuation Simulation tool Fidelity Network Behavior Author (year) BFIRES Micro Fine Rule, probabilistic Stahl (?82) EVACSIM Micro Fine Rule, probabilistic Drager (?92) SIMULEX Micro Coarse Implicit Thompson (?95) EXIT89 Micro Coarse Implicit Fahy (?93) SGEM Micro Fine No Lo (?00) buildingEXODUS Micro Fine Rule Galea (?04) CRISP Micro Fine Rule, probabilistic Phillips (?94) 2.6. Mixed vehicle-pedestrian flow modeling On the subject of modeling mixed pedestrian-vehicle flows over a congested network, only a limited number of studies have been reported in the literature. Helbing and Jiang (Helbing, 2005) proposed a macro model to investigate the oscillations and delays of pedestrian and vehicle flows. Jiang and Wu (Jiang, 2006a; b) explored a simple lattice gas model to study the vehicle and pedestrian flows in a narrow channel. Both models presume that the moving directions of both types of traffic flows are not subject to change. Ishaque and Noland (2007) studied the pedestrian traffic with VISSIM, where vehicle and pedestrian modes are operated independently and controlled by the traffic signals at the potential conflicting areas. This function has later been expanded in VISSIM to model the conflicts between 32 pedestrian and vehicle flows when any of them need to cross a street using the gap acceptance model (Boenisch and Kretz 2009). 2.7. Review Findings Based on the extensive review reported in this chapter, it is clear that: ? Most evacuation models for vehicle traffic are focused on the traffic conditions on the major freeways or arterials and most evacuation models for pedestrian traffic put their emphasis within the buildings. Little research has been focused on the local streets or major intersections in urban areas where the mixed flow dominates the traffic. ? Regarding the optimization of the evacuation plans for vehicles during the emergencies, much literature addressed the issues of scheduled evacuation, route choice or signal timing settings. However, few publications attempted to combine the three to account for their interrelated impact on the traffic conditions during evacuation. ? Existing control strategies on roadways mainly deal with coordinating the vehicle traffic without considering the numerous panic crossing pedestrians. For example, most signal optimization models explicitly consider the pedestrian phase timing. However, failure to give adequate control to the massive evacuees at major intersections will result a deteriorating traffic condition. ? No models have ever attempted to integrate the vehicles and the pedestrians in an integrated network to capture their interactions. In reality, the evacuees usually rush onto the street towards the locations of their vehicles and drive 33 out of the danger zone. In this sense, the pedestrian flows are converting to the vehicle flows, and they are in potential conflict with each other at critical intersections or roadway blocks. ? Although the simulation models for vehicles or pedestrians have been extensively studied in the past decades, the study on the mixed-flow simulation model is still at an early stage. How to model the way-finding and the conflict between the mixed-flows is the most critical issue. For example, in some simulation models for pedestrians, the ways for individuals to resolve a conflict are modeled as a result of the stochastic process. Human behaviors? impact on the consequence is not given adequate attention. ? Only a very small portion of the above models are calibrated and validated based on data from real-world scenarios because it is relatively hard to obtain detailed and exact data from the evacuation process. However, from a strict point of view, it is necessary to provide a standardized procedure for the model calibration and validation. To overcome the limitations of the above literature findings, the study will propose to build a mixed-flow evacuation system for urban areas under emergencies. The framework for the system will be presented in the next chapter, and the modeling details within the system modules will be illustrated in the following chapters. 34 Chapter 3: Overview of the Framework for a Mixed-flow Evacuation System This chapter introduces the proposed multi-modal evacuation system designed for the Baltimore metropolitan area. The proposed system structure is generic in nature, including all essential components and their interrelationships in activating emergency evacuations. The next section first illustrates a two-stage multi-modal evacuation control process, where the first stage occurs in the incident?s immediate impact area and the second stage guides evacuees to designated safe destinations. The mixed-flow model, a core of the evacuation system, is exclusively developed for the first-stage evacuation where the massive evacuee and vehicle interactions may cause serious chaos and congestion in the evacuation network. Section 3.2 discusses all critical issues associated with the development of each critical component and their complex interrelations. Section 3.3 presents all system components and critical modules, emphasizing those core models developed in this research. 3.1. Two-stage evacuation process When detecting an incident within a metropolitan area, the responsible agencies first need to identify the impacted zones and decide the proper time to activate the evacuation order. After activating the evacuation order, evacuees within the impact zones are expected to rush onto the street to their passenger cars or to designated locations where they will be rescued by public transit systems. As soon as the evacuees get access to their cars or are picked up by shuttles, their vehicles will enter the roadway network, creating mixed vehicle-pedestrian flows at critical intersections 35 within the impact zones. Some vehicles may choose the intermediate shelters as their destinations while the others may select the safety areas. Beyond the immediate impact boundaries, it is likely that the network will have mainly vehicle flows. Figure 3-1 illustrates the five steps during the emergency evacuation identified, along with the timeline. Note that those critical steps may be overlapped rather than sequential during the evacuation operation. For example, the impact areas may be expanded due to the evacuation progress, and the transit operations within the impact zone may be impeded by its congested traffic condition. Figure 3-1 The mixed-flow evacuation procedure The final safe destinations for all evacuees should be relatively far away from the impact zone to minimize the safety impact due to the incident. Note that the control boundaries for the evacuation are determined by the incident nature and the estimated evacuation population, which tend to divide the network into two parts. Critical points along the control boundaries are the main control locations for vehicles to exit the impact boundaries. Usually, these points are the major intersections on the arterial or ramps on the freeway. 36 Figure 3-2 illustrates the two-stage multi-modal evacuation process: mixed pedestrian-vehicle flow evacuation within the control boundaries and vehicle flow evacuation from the control boundaries to final destinations. Note that there are three different modes within the control boundaries: walking, passenger cars, and the public transportation systems. However, evacuees are not expected to walk beyond the control points. The primary tasks of the multimodal evacuation within the impact zone are to generate the optimal or near-optimal plans to guide pedestrian and vehicle flows, retime the signal phases to accommodate massive evacuees, and implement efficient response routes for transit systems. Beyond the multi-modal boundaries, the evacuation is mainly a single-mode operation. Note that the available transit systems may include the metro bus, light rail, and subways, and each needs a different control strategy for effective implementation. Figure 3-2 The two-stage evacuation process 37 3.2. Critical issues in a mixed-flow evacuation In order to identify all critical issues associated with a mixed-flow evacuation, this section uses a potential terrorist attack at the MT&T stadium in the Baltimore downtown area to facilitate the illustration. Around the stadium, there are more than a dozen of parking lots just for the football game, and a number of private or public parking structures. There are also several metro-bus stops and light-rail stations in the neighboring area. Prior to selecting the evacuation plan during an emergency, the responsible agencies should first obtain the following information in real time or in advance: ? The total population and their spatial distributions within the impact boundaries; ? The locations of the parking areas and the number of parked vehicles; ? The locations and capacities of the possible pick-up points for evacuees; ? The locations of the transit depots around the impact area; ? The availability of the buses and the trains during the evacuation period; ? The road and walking facility layout within and beyond the impact area; and ? The possible shelters and safety areas to accommodate evacuees. The above data will be used to define the incident scenario and to serve as the input for other computing modules. Based on these inputs, the decision makers need to establish proper controls within the impacted mixed-flow area and beyond the boundaries. Due to the complex conflicts between pedestrian and vehicle flows, this research focuses mainly on developing effective strategies to manage the massive 38 mixed flows in the immediate impact zone. To ensure the effectiveness and efficiency of the mixed-flow evacuation process, the following issues need to be considered: 1. How to coordinate the evacuees within the impact area with the best scheduled departure process. This step is to ensure that the evacuation process will not cause excessive congestion and bottlenecks within the evacuation zone, and each individual evacuee can be guided with the best schedule and route to the designated locations. 2. How to choose the best walking paths for the evacuees to reach their intended parking areas and pick-up locations. By suggesting the best paths and controlling the moving directions of evacuees on the walking facilities, the responsible agency can direct the pedestrian flows out of the streets as fast as possible, which can also reduce the impact of the pedestrian flows on the vehicle flows. 3. How to direct vehicles from the parking areas to the assigned safe destinations. This step is to ensure that all evacuation vehicles can efficiently pass through all intersections to the designated destinations to prevent blockages by both the massive vehicle and pedestrian flows. 4. How to design the phase plans that can accommodate the massive crossing evacuees at critical intersections. Although existing conventional signal controllers consider pedestrians in the design of the signal timings, most existing designs cannot accommodate a large number of panicked pedestrians. To prevent excessive blockage caused by massive numbers of evacuees, responsible agencies need to identify critical intersections and implement proper control strategies. 39 5. How to evaluate the effectiveness of different control plans. To ensure the effectiveness of a candidate evacuation plan, it is necessary to know the time- varying road conditions during the evacuation, including pedestrian distributions, potential bottlenecks, speed patterns, and travel time estimations. These estimated results can help decision makers to evaluate candidate control plans and quickly spot the locations more susceptible to congestion. 6. How to assess uncertainties in the evacuation process that may be caused by some evacuees who do not obey the rules or regulations by the responsible agencies. The decision makers should have some tools to estimate the evolution process if some evacuees or vehicles do not follow the guidance and incur severe conflicts or bottlenecks in the network within the impact zone. 7. How to dispatch available transit vehicles to rescue evacuees waiting at designated locations. Since transit agencies could play an important role in reducing the evacuation time and providing services to those without access to vehicles, it is essential to have an effective plan that can assign routes and time- tables for each bus or train in response to the time-varying number of evacuees at the pick-up locations. Note that the first four issues are to justify the need to have the best control plan that can coordinate the mixed-flow movements within the impact area. Such a plan should be generated from an optimization model that can capture the mixed-flow network characteristics, reflect the control objective as well as the flow and signal timing constraints, and generate the solutions with an effective algorithm. Both issues 5 and 6 belong to the descriptive category, targeting the need to have a tool that can 40 describe the real-world mixed-traffic conditions such as simulating evacuees? way- finding strategies, replicating individual movements and behaviors upon conflicts. Issue 7 is similar but more complex than the transit routing problem as it needs a real- time algorithm that can offer both vehicle routing and scheduling plans. This dissertation will focus only on the first two models, which are needed for evacuation within the immediate impact area. 3.3. Framework of the multi-modal evacuation system Figure 3-3 presents the structure of the entire multi-modal evacuation system, highlighting all essential components and the key role of those models to be developed in this research. A brief description of each component is given below. ? Input module: It allows users to characterize the incident scenarios as well as to set up various control parameters. ? Database module: It pre-stores relevant information, including the road networks, walking facilities, zone population information, parking areas, and transit stops. ? Mixed-flow optimization module: This module is designed to produce the best evacuation plan under the given scenario. The input for this module is the identified evacuation scenario, including the impact area, the total population with access to personal vehicle, the spatial distribution of parking lots, the potential locations for pick-up of transit users, the shelters or the safety areas, the mixed-flow network within the impact area, and the evacuation network beyond the control boundaries. The module will then generate the optimal plans for each group of evacuees, including the optimal 41 departure schedules, the routings for the passenger cars from the parking areas, and the signal plans to accommodate massive pedestrians and vehicles. ? Mixed-flow simulation module: To evaluate the proposed evacuation plan in the impact zone, this specially designed model for vehicle-pedestrian mixed flows is responsible for simulating the evolution of the network over the evacuation period, including the speed and density on each link, the required time for each mode to evacuate its share of evacuees, and the clearance time to vacate the entire evacuation zone. This simulation module can also be used to assess the impact of evacuees? compliance on the efficiency and the effectiveness of the entire operations. ? Transit dispatch module: Due to the inevitable need for using transit vehicles to evacuate massive number of evacuees, the proposed system should include a transit module to generate the routing plans and schedules for available buses or trains to pick up and drop off evacuees. The design of these plans needs to be based on the spatial distribution of available transit vehicles and the output from the mixed flow simulation module, including the number of arrivals to each pick-up location and the time-dependent network traffic conditions. ? Vehicle-flow routing module: This module functions to generate the optimal routing plans from the incident impact zone to the final safe locations for all evacuation vehicles. 42 ? Vehicle-flow simulation module: It is designed to evacuate the effectiveness of the strategies generated by the vehicle-flow routing module, mainly for the network between the impact zones and the final destinations. ? Output module: The purpose of this module is to manage and display the customized output from all above computing modules. Among all modules stated above, the mixed-flow optimization and mixed-flow simulation modules are the two most critical ones, and thus constitute the core of this dissertation. The mixed-flow optimization model is designed for guiding and controlling vehicle-pedestrian flows under emergency evacuation, and its development needs to overcome the following challenges: ? Need to have an integrated network that can concurrently represent the vehicle and the pedestrian networks and realistically capture the mixed-flow interactions; ? Need to design signal phasing and timing plans to accommodate massive pedestrian flows to prevent the formation of blockages at intersections. ? Need to maximize the total number of evacuees rather than vehicles arriving at the safe destinations over a given time window. The model should also be able to generate plans that give priority to the high-occupancy vehicles under this objective. The mixed-flow simulation model is a descriptive model for replicating the mixed- flow conditions under emergency evacuation. The development of such a model has to face the following modeling challenges: 43 ? Realistically represent the way-finding behavior of both the pedestrians and drivers; ? Model pedestrian and vehicle movements along any direction at the critical intersection areas; ? Incorporate individual behaviors in identifying and resolving the potential conflicts; and ? Provide flexibility in reflecting the impacts of individual compliance on the effectiveness of traffic enforcements or controls. A detailed discussion of the above modeling issues will be provided in the following chapters. 44 Figure 3-3 The framework of the multimode evacuation system 45 Chapter 4: Mixed-Flow Optimization Model This chapter presents the formulations for optimizing the mixed pedestrian- vehicle flows during emergency evacuation in urban networks and proposes a modified Bender?s decomposition algorithm to solve the formulation. The operational model for guiding and controlling vehicle-pedestrian flows should have the following key features: 1. Realistically represent the integrated network consisting of vehicle and pedestrian flows and capture their interactions; 2. Generate the signal phase plan that can fully account for both massive pedestrian and vehicle flows; and 3. Concurrently optimize the departure rates, routing strategies, and signal timings for both pedestrian and vehicle flows within the incident impact zones. An early study addressing the issue was done by Zhang and Chang (2010) with an extended cell transmission (CTM) concept. Their model concurrently optimizes traffic signal timings with optimally assigned mixed flows. However, the non-linear integer nature of the formulations renders the proposed model difficult to solve and to use in real-time operations. This chapter presents a new set of formulations grounded on Zhang and Chang?s work for the same research issues, which are to realistically capture the interactions between the mixed flows and available roadway capacities and also to circumvent the computing burdens for use in real-time evacuation operations. 46 This chapter is organized as follows: Section 4.1 presents the formulations of the mixed flow traffic network and its key components. Section 4.2 details an integer- linear optimization model that accounts for vehicle and pedestrian flows as well as their routing strategies and the signal timings within the evacuation zones. Section 4.3 illustrates the details of the proposed algorithm and its merits in solving the abovementioned inter-linear optimization formulation. Section 4.4 carries out a numerical experiment in applying the model to a hypothetical evacuation after football games in the Baltimore region. 4.1. Mixed Flow Network Representation 4.1.1. Components of the mixed network The proposed mixed-flow network consists of three main components: the vehicle network, the pedestrian network, and their connections. This study adopts the common unidirectional node-link concept for the vehicle network and uses the bi- direction link-node notion for the pedestrian network. However, to ensure safety and reduce conflicts, the proposed model enforces only one direction of pedestrian flow on each link. To reflect the interactions and conflicts between evacuees and vehicles, the proposed model generates the connection node and intersection nodes to capture such mixed-flow movements. The connection between the two networks is used to convert the pedestrian flows to the vehicle flows, usually taking place at the parking areas and pick-up locations (e.g., transit stop, metro stations). The conflicts between these vehicle and pedestrian flows usually occur at the intersections or crossing areas, where proper signal controls are needed to coordinate these two types of flows. 47 4.1.2. Representation of the vehicle network Consider a directed graph ( , )V V VG V E= , where {1,..., }v vV n= is the set of nodes, and {( , ) | , }v vE i j i j V= ? is the set of directed links. These nodes represent the intersections, and the links denote those one-way street segments between two intersections. Figure 4-1 (a) is an example of two neighboring intersections, and Figure 4-1 (b) shows the corresponding vehicle network. Figure 4-1 A graphic illustration of the vehicle network 4.1.3. Representation of the pedestrian network In general, all pedestrian movements during evacuation may take place in one of the following areas: inside-building area, sidewalks, and intersection crossings. Due to the need to guide and control pedestrian-vehicle flows, the study focuses on formulating the pedestrian flows along sidewalks and at intersection crossings that can be represented with nodes and links, respectively. Different from vehicle networks, the pedestrian network is bidirectional in nature as pedestrians can move toward either direction on each arc. Consider a graph ( , )p p pG V E= , where {1,..., }p pV n= is the set of nodes, and {( , ) | , }p pE i j i j V= ? is the set of undirected links. The links represent the sidewalks or the crosswalks, and the nodes represent the connections between the sidewalks and (b) (a) 48 the crosswalks. An illustrative example is given in Figure 4-2. The solid lines in Figure 5(b) represent the sidewalks, and the dashed lines represent the crosswalks. Figure 4-2 A graphic illustration of the pedestrian network 4.1.4. Representation of the connections During the evacuation process, evacuees are likely to run to the parking garage or bus stops where passenger cars or buses are loaded onto the vehicle network to the final safe destinations. The parking garages and bus stops function as the connections between the pedestrian and vehicle networks. Two parameters are associated with the connection: the carpooling rate and the access delay. The carpooling rate determines the ratio between the pedestrian inflows and the vehicle outflows from the connections, and the access delay represents the average time needed for evacuees to access their vehicles. To realistically capture interactions in the mixed flow movements, this study first defines two nodes for each connection site: one in the pedestrian network and the other in the vehicle network. Connection links are then created to connect the set of pedestrian nodes to vehicle nodes in order to transfer the pedestrian flows to vehicle flows. The traverse time in a connection link is equal to its (b) (a) 49 access delay. In Figure 4-3, the dotted line, connecting the empty and the solid circle, represents the connection link. (a) (b) Figure 4-3 A graphic illustration of the connection between the two networks 4.1.5. Representation of the signal controllers Note that conflicts may inevitably take place between vehicles, between pedestrians, or between vehicle and pedestrians during the evacuation process. In practice, one can use a traffic control device to enforce the sequence and duration for each right-of-way movement at an intersection. A typical ring-and-barrier diagram is selected to represent the phase sequence of a signal controller. Taking a typical four- leg intersection for example, the conventional NEMA signal phase sequence is depicted in Figure 4-4. 2?1? 5? 6? 3? 4? 7? 8? Figure 4-4 Ring-and-barrier diagram for a typical four-leg intersection 50 Note that under a typical signal design (i.e., phases 2, 4 6 and 8), the right-turn vehicles should always yield to the pedestrian traffic. However, during an evacuation all arterial links are likely to be saturated with mixed traffic flows, which may cause a blockage to the right-turn traffic. To address this critical issue, this study proposes to split each through-right-pedestrian phase into two phases, separating the right-turn from the pedestrian movement, as depicted in Figure 4-5. 5?1? 15? 17? 7? 9? 19? 21? 2? 3? 4? 13? 14? 16? 6? 8? 10? 11? 12? 18? 20? 22? 23? 24? Figure 4-5 Ring-and-barrier diagram with an additional exclusive right turn phase 4.2. Network-wide mixed-flow and signal control optimization formulations The decision variables for the mixed-flow network optimization include the dynamic flow distributions for both the vehicles and evacuees in the network, the connection of different movements at intersections, and the signal parameters such as cycle length and green splits. The notations for those decision variables are listed below: , , , = v i j k tf vehicle flow from link , )i j to , )j k at time t , , , = p i j k tf pedestrian flow from link , )i j to , )j k at time t , , , = v i j k tq vehicle flow available at node j on link , )i j to , )j k at time t , , , = p i j k tq pedestrian flow available at node j on link , )i j to , )j k at time t 51 ic = fixed cycle length for pre-timed signal controller at intersection i ,i jg = the fixed interval for the j-th phase at intersection i , ,i j ks = the start time of the k -th phase of the j -th cycle at intersection i , ,i j ke = the end time of the k -th phase of the j -th cycle at intersection i , , , 0, if vehicle movement from link (i,j) to (j,k) is red at time t = 1, if vehicle movement from link (i,j) to (j,k) is green at time t v i j k tb ??? , , 0, if pedestrian movement from node i to j is red at time t = 1, if pedestrian movement from node i to j is green at time t p i j tb ??? , 0, if pedestrians are banned to walk from pedestrian node i to j = 1, if pedestrians are allowed to walk from pedestrian node i to j p i jb ??? , , 0, if signal barrier j of signal at node i is inactive at time t = 1, if signal barrier j of signal at node i is active at time ti j tv ??? , , 0, if signal phase j of signal at node i is not active at time t = 1, if signal phase j of signal at node i is active at time ti j tw ??? i,j,k , , , i,j,k 0, if t is earlier than s = 1, if t is equal or later than si j k t u ??? i,j,k , , , i,j,k 0, if t is later than e = 1, if t is equal or earlier than ei j k t v ??? i,j,k i,j,k , , , i,j,k i,j,k 0, if t is not between s and e = 1, if t is between s and ei j k t w ??? Variables that are known to the users before executing the proposed model include the topology of the network, the capacity and the saturation flow of each link, the locations of the origins and destinations, and the parking lots and pick-up locations. The notations of those known variables are listed below: 52 T : The total time of interest ( ) :v i?? The set of vehicle nodes directed to a node i ( )v i+? : The set of vehicle nodes directed from a node i ( ) :p i?? The set of pedestrian nodes directed to a node i ( )p i+? : The set of pedestrian nodes directed from a node i , v i jS : The saturation flow rate of the vehicle link ( , )i j sV : The set of intersections with signal controllers cV : The set of connection nodes vE : The set of vehicle links in the vehicle network pE : The set of pedestrian links in the pedestrian network cE : The set of connection links vO : The set of origin nodes for vehicles pO : The set of origin nodes for pedestrians D: The set of destination nodes for vehicles im : The number of evacuees at the pedestrian origin node i i? : The carpooling rate for the connection node i p iU : The maximum pedestrian holding capacity of the connection node i iC : The set of phases of the signal plan at node i 53 ,i jC : The set of allowed movements in phase j of the signal plan at node i 4.2.1. Constraints for vehicle flows in the vehicle network , , , , , , 1 , , , , , , ( ) ( ) ( ) ( ) ij v v v v v v v v i j k t i j k t k i j t i j k t k j k j k i k j q q f f? + + ? + ? ? ?? ?? ?? ?? = + ?? ? ? ? , ( , ) vi j E? ? ?. (4-1) , , , , , ( )v v v i j k t i j t k j q S +?? ?? , ( , ) vi j E? ? ????????????????.. (4-2) , , , , , , , , , * v v v i j k t i j k t i j k tf S b? , ( , ) vi j E? ? , ( )vk j+?? ???????????. (4-3) , , , , , , v v i j k t i j k tf q? , ( , ) vi j E? ? , ( )vk j+?? ..?????????????.. (4-4) The vehicle flow constraints mainly reflect flow conservation and capacity restraints. Constraint (4-1) computes the available vehicle flow at a given time step for the outgoing links, based on the available vehicle flow, the inflow to the link and the outflow to the outgoing links at a previous time step. Constraint (4-2) sets the available vehicle flow to be less than the maximum link capacity. Constraint (4-3) limits the outgoing flow to be less than the saturation flow rate at a given time, based on the signal status of the corresponding movement. Constraint (4-4) is to ensure that the actual outgoing flow will not exceed the available flow at that time. 4.2.2. Constraints for pedestrian flows , , , , , , 1 , , , , , , ( ) ( ) ( ) ( ) ij p p p p v v v v i j k t i j k t k i j t i j k t k j k j k i k j q q f f? + + ? + ? ? ?? ?? ?? ?? = + ?? ? ? ? , ( , ) pi j E? ? .. (4-5) , , , , , , ( ) * p p p p i j k t i j t i j k j q S b +?? ?? , ( , ) pi j E? ? ?..????????????... (4-6) , , , , , , , ( ) * p p p p i j k t i j t i j t k j f S b +?? ?? , ( , ) pi j E? ? ?..????????????.. (4-7) , , , , , , , ( ) * p p p p i j k t i j t i j t k j f S b +?? ?? , ( , ) pi j E? ? ?????????????.. (4-8) 54 , , , , , , v v i j k t i j k tf q? , ( , ) pi j E? ? , ( )pk j+?? ????????????? (4-9) , , 1p pi j j ib b+ = , ( , ) pi j E? ? ??????????????????.. (4-10) , , , p p i j t i jb b? , ( , ) pi j E? ? ?.?????????????????? (4-11) The pedestrian flow constraints are similar to the vehicle flow constraints with some exceptions, where Constraints (4-7) and (4-8) set the upper bound of the total inflow and outflow of a pedestrian link as the link?s saturation flow rate. Constraint (4-10) enforces a unique direction flow for each pedestrian link. Constraint (4-11) guarantees that no pedestrian flow will exist in the prohibited direction. 4.2.3. Constraints for connection links Equation (4-12) is designed to reflect the process where evacuees move into vehicles and join the queue to the assigned safe destinations. The pedestrian flows are modeled to move for ? time steps on the connection links before they are converted to the vehicle flows. The vehicle flows will be converted from the pedestrian stream according to the car-pooling ratio? . In urban networks, each connection node at the end of a connection link could be a bus stop or a parking lot. For bus stops, a holding capacity constraint (4-13) is specified to prevent the waiting passengers from exceeding the limit. , , , 1 , , , 1 ( ) ( )v v p v i j k t i i j k t k j k j q q? + + ? ? ?? ?? =? ? ( , ) ci j E? ? ??????????? (4-12) , , , ( )v p p i j k t i k j q U +?? ?? , ( , ) ci j E? ? ????????????????.. (4-13) 4.2.4. Constraints for dynamic signal controllers 55 There are either pre-timed or dynamic signal controllers at most urban intersections. Dynamic signal controllers account for the dynamic nature of the traffic network and are able to extend the green time of each phase based on the real-time detected traffic information. Controllers with the embedded function are able to adjust the signal timings on the basis of actual flows under the maximum and minimum green time constraints. In pre-timed operations, the cycle length, phase sequence, and timing of each phase are constant. Although not as flexible as the dynamic controllers, pre-timed signals are still the most widely deployed control at most intersections due to concerns about the cost. Different from previous network-wide signal optimization formulations (e.g., Ziliaskopoulos 2000), the proposed model incorporates the safety concern of pedestrian movements into the signal phase sequence and explicitly considers the lost time for each phase to prevent frequent transitions or short phases. The constraints related to the dynamic traffic signal controllers are set as follows: , , 1i j t j v =? , si V? ? , ij C? ? ?????????????????.. (4-14) , , , ,i l t i j t l w v=? si V? ? , ij C? ? ?..???????????????. (4-15) , , , 1, 1 , 1, 0.9i j t i j t i j tw w w? ? ?? ? ? , si V? ? , ij C? ? , 1j > ??..?????... (4-16) max , 1 max , , , i jt G i j i j t w G? ? + + = ?? , si V? ? , ij C? ? ???.???????????. (4-17) min , min , , , , , , , 1*( ) i jt G i j i j i j t i j t t w G w w? ? + ? = ? ?? , si V? ? , ij C? ? ????????? (4-18) , , , , , = v k l m t i j tb w , si V? ? , ij C? ? , ,( , , ) i jk l m C? ? ??????????? (4-19) , , , , = p k l t i j tb w , si V? ? , ij C? ? , ,( , ) i jk l C? ? ???..????..????.. (4-20) 56 The binary variable , ,i j tv is defined to determine whether the signal is active for the j -th barrier of the intersection i at time t . For a typical 4-leg signal phase illustrated above, there are two barriers, as indicated in the ring-and-barrier diagram. If any signal phases at the first barrier for the east-west streets is green, then set ,1, 1i tv = , otherwise ,1, 0i tv = . A similar variable ,2 ,i tv is designed to determine whether any phases are green at the second barrier for the north-south street. Constraint (4-14) ensures that only one barrier is active at each time. Constraint (4-15) states that if a barrier is active at a particular time, there is one and only one green phase belonging to the barrier in each ring. For example, if the left barrier is active, then only one of the phases (1-6) in the upper ring and only one of the phases (13-18) in the lower ring will be in the green status. Constraint (4-16) guarantees that a yellow and all-red phase will follow immediately after each green phase. For example, phase 6 should be activated right after phase 5. Constraint (4-17) limits the phase green time to be under a specified maximum. Constraint (4-18) enforces a minimum green time for each phase. For these yellow and all red interval phases (2, 4, 6 ?), this study sets their minimum and maximum times at an identical predetermined value. Constraints (4-19) and (4-20) build the connections between the signals and the networks. 4.2.5. Constraints for pre-timed signal controllers The pre-timed signal control constraints share the same constraints (4-14) to (4- 16) and (4-19) to (4-20) as the dynamic control. However, additional constraints are needed to determine the cycle length, phase sequences, and phase green times. Hence, the proposed model employs three new indication variables , , ,i j k tu , , , ,i j k tv and , , ,i j k tw , 57 where , , ,i j k tw indicates whether the current time t is within phase k of the j -th cycle; , , ,i j k tu and , , ,i j k tv are used to determine , , ,i j k tw . All additional constraints for pre-timed controllers are listed below: , i i i j j C c g ? = ? , si V? ? ??..??????????????.???? (4-21) ,min ,maxi i iC c C? ? , si V? ? ????????????????.??. (4-22) , , , , ,i j i k j i k jg e s= ? , si V? ? , ij C? ? , k K? ? ?????????.??.. (4-23) , ,min , , ,maxi j i j i jG g G? ? , si V? ? , ij C? ? ????????????.?. (4-24) , , , , 1i j k i i j ks c s ++ = , si V? ? , ,j? , ik C? ? ?????????...??.?.. (4-25) , , , , 1i j k i i j ke c e ++ = , si V? ? , ,j? , ik C? ? ?????????..??.?... (4-26) , , 1 , , 1i j k i j ks e+ = + , si V? ? , ,j? , ik C? ? ??????????.?...?... (4-27) , , , , , , , , (1 )i j k t i j k i j k tMv t e M v? ? ? ? ? , si V? ? , ,j? , ik C? ? , t T? ? ?...?.. (4-28) , , , , , , , , (1 )i j k t i j k i j k tMu s t M u? ? ? ? ? , si V? ? , ,j? , ik C? ? , t T? ? ??.. (4-29) , , , , , , , , , 2 i j k t i j k t i j k tw v u? + , si V? ? , ,j? , ik C? ? , t T? ? ?????.?.? (4-30) , , , , , i i j t i j k t k C w w ? = ? si V? ? , ,j? t T? ? ????????????........ (4-31) The above constraints are specified to regulate the controllers such that the signal can operate on a fixed cycle with constant green phases and time-invariant offsets. Constraint (4-21) computes the cycle length by adding the phase interval times, and Constraint (4-22) imposes a minimum and maximum on the cycle length. Constraint (4-23) computes the phase duration by measuring the time difference between a phase starting and its ending times. Constraint (4-24) also imposes restrictions on the 58 minimum and maximum intervals. Constraints (4-25) and (4-26) ensure that the phase start times and end times for consecutive cycles are equal to the difference in cycle length. Constraint (4-27) regulates the phase sequence by setting the start time of the next phase immediately after the ending time of the previous phase. Constraints (4-28) and (4-29) shows how , , ,i j k tu and , , ,i j k tv are determined by evaluating whether the current time falls into the green duration of a particular phase. Constraints (4-30) and (4-31) are used to determine , , ,i j k tw based on the values of , , ,i j k tu and , , ,i j k tv . 4.2.6. System optimal objective function The common purposes for imposing traffic control and management on a congested network are to: (1) send most travelers to their intended destinations within a given time window; (2) reduce the total cost for all the travelers (e.g., travel-time cost); and (3) prevent any lane blockage or spillback. The objective function for this model is for the first purpose, which is to maximize the total system throughput during a time window. One can easily reformulate the objective function to fit the second and third purposes. Note that due to the presence of mixed flows, the formulation of the objective function is not a straight-forward task. This study proposes to expand the mixed-flow network and restructure as a new network for reformulation. The new formulation can give the identical optimal objective to the original formulation; however, it may also yield unrealistic optimal flows. Thus, one needs to restructure the network with a pseudo-network to ensure the existence of an optimal solution. After the connection nodes are grouped by their carpooling rates, one can duplicate a vehicle network for 59 each group and then add a directional link from the connection nodes in each group to the corresponding copied vehicle network. Figure 4-6 presents an illustrative example where the set of white, shaded, and black nodes represents pedestrian, connection, and vehicle nodes, respectively. The number on each link represents the roadway capacity. The first connection node has a carpooling rate of 50 (e.g., a bus stop), and the second has a carpooling rate of 2 (e.g., a passenger car parking lot). The new expanded network is shown in Figure 4-6 (b), which consists of two vehicle networks, as circled. The copy-1 network corresponds to the car-pooling rate of 50, so the capacities of these links in the newly created network are 49 times their original values. The original destination and the duplicated destinations are all connected to a super sink node with an infinite capacity. 1 50? = 2 2? = 2000 2500 1800 1500 500 500 500 1500 2000 2500 1800 1500 500 500 500 1500 7350024500 1500 1500 ? ? 500 500 ? 24500 24500 1 50? = 1 2? = (a) (b) Figure 4-6 The mixed-flow network and the expanded network The above expanded network can hold the flow conservation relation at all connection nodes. By doing so, one can generate a network with its link flows 60 representing the actual number of evacuees under different types of evacuation vehicles. Constraint (4-12) for connection links needs to be replaced with constraint (4-32) while keeping all the others unchanged. , , , 1 , , , 1 ( ) ( )v v p v i j k t i j k t k j k j q q + + ? ? ?? ?? =? ? ( , ) ci j E? ? ????????????? (4-32) By denoting n i as the corresponding node in the duplicated network n for node i in the original network, constraints (4-33) and (4-34) guarantee that the signal setting at the intersection of the extended vehicle network is identical to the original network. , , , , , ,n n n v v i j k t i j k tb b= , ( , ) , ( )v vi j E k j+? ? ? ?? , t T? ? , cVn C? ? ????.?. (4-33) , , , ,n n p p i j t i j tb b= , ( , ) pi j E? ? , t T? ? , cVn C? ? ???????????... (4-34) The objective function for this study is to maximize the total evacuee throughput to all pre-designated destination nodes within a given time window. The objective function can be expressed with Equation (4-35): , , 1, ( )v v v i j T j Di j q ? ? ??? ? ? ?????????????????..????. (4-35) Note that Figure 4-7 shows that the aforementioned formulations may generate unrealistic flows without proper constraints. For instance, there are two chains 1? and 2? with the flow values of 500 and 1000 in these two duplicated networks; however, no flow exists in the original network. To be consistent with the actual flow distribution, each path with flows in the i -th network should have a corresponding path in the original network with its flow rate equal to 1i? ? times of the original one. 61 The restructured flow distributions consistent with their original patterns are shown in Figure 4-7(b). Constraints (4-36) and (4-37) are proposed for such a need. , , , , , , 1( ) 1 n n n v v i j k t i j k t n n q q?= ?? , ( , ) , ( )v voi j E k j+? ? ? ?? , t T? ? , cV n C? ? ? (4-36) , , , , , , 1( ) 1 n n n v v i j k t i j k t n n f f?= ?? , ( , ) , ( )v voi j E k j+? ? ? ?? , t T? ? , cVn C? ? ? (4-37) Where: v oE is the link set in the original network; cVC is the set of connection node groups categorized by the car-pooling rate; n i is the node in the n th copied network corresponding to original node i 1 2 1980 500 1000 Copy 1 Copy 2 1 50? = 1 2? = 980 1000 1000 1000 2040 980 980 980 * 1 500? = 2 1000? = (a) (b) Figure 4-7 An example of the unrealistic flow 4.3. Solution algorithm The above formulation contains a set of integer variables representing the selection of pedestrian link directions and the signal indications and a set of continuous variables representing the flows and holdovers on each link. The number of variables is quite large even for medium-size networks. However, the presented 62 mixed-integer structure is rather suitable for mathematical decomposition such as with Bender?s decomposition (Benders 1962). 4.3.1. Bender?s partitioning algorithm The idea of the Bender?s Decomposition is to decompose the mixed-integer problem into two separate problems: one pure integer master problem with integer variables only and one linear sub-problem with linear variables only. The value of the 0-1 vector , , , , ,{ ,..., } v p i j k t i j tb b needs to be fixed to obtain the sub-problem. In the proposed formulation, the linear sub-problem (SP) is formulated below from (4-38) to (4-52), where , , p i j tb and , , ,vi j k tb are known variables. (SP)Maximize , , , ( ) ( ) v i j k T j D i j k j q ? +? ?? ?? ? ? ? ???????????.??? (4-38) Subject to: - , , , , , , 1 , , , , , , ( j) ( j) (i) ( j) 0 ij v v v v i j k t i j k t k i j t i j k t k k k k q q f f? + + + ? ? ?? ?? ?? ?? ? ? + =? ? ? ? , , ( , ) , [ , ]c v iji V i j E t T?? ? ? ? ? ? ????????????.??..... (4-39) - , , , , , , 1 , , , , , , ( j) ( j) (i) ( j) 0 ij p p p p i j k t i j k t k i j t i j k t k k k k q q f f? + + + ? ? ?? ?? ?? ?? ? ? + =? ? ? ? , , ( , ) , [ , ]c p ijj V i j E t T?? ? ? ? ? ? ????????????..??.... (4-40) - , , , , , , 1 , , , , , , ( j) ( j) (i) ( j) 0 ij v v p v i j k t i j k t k i j t i j k t k k k k q q f f? + + + ? ? ?? ?? ?? ?? ? ? + =? ? ? ? , , ( , ) , [ , ]c v iji V i j E t T?? ? ? ? ? ? ????????????...??.... (4-41) 63 , , , , ( j) v v i j k t i j k q S +?? ?? , ( , ) , [0, ]vi j E t T? ? ? ? ?..???????????. (4-42) , , , , , , ( j) * p p p i j k t i j i j t k q S b +?? ?? , ( , ) , [0, ]pi j E t T? ? ? ? ????.??????. (4-43) , , , , , , , , , * v v v i j k t i j k t i j k tf S b? , ( , ) , ( j), [0, ] vi j E k t T+? ? ? ?? ? ? ??????? (4-44) , , , , , , , (i) * p p p k i j t i j t i j t k f S b ??? ?? , ( , ) , [0, ]pi j E t T? ? ? ? ???.??????? (4-45) , , , , , , 0v vi j k t i j k tf q? ? , ( , ) , ( j), [0, ]vi j E k t T+? ? ? ?? ? ? ????????? (4-46) , , , , , , 0p pi j k t i j k tf q? ? , ( , ) , ( j), [0, ]pi j E k t T+? ? ? ?? ? ? ????????? (4-47) , , , , , , 1( ) 0 1 n n n v v i j k t i j k t n n q q?? =?? , ( , ) , ( )v voi j E k j+? ? ? ?? , t T? ? , cn V? ? ? (4-48) , , , , , , 1( ) 0 1 n n n v v i j k t i j k t n n f f?? =?? , ( , ) , ( )v voi j E k j+? ? ? ?? , t T? ? , cn V? ? ? (4-49) , , ,0 0 v i j kq = , ( , ) vi j E? ? ??.???????.?????????..?? (4-50) , , ,0 0 p i j kq = , pj O? ? ??.????????.???????.??..?? (4-51) , , ,0 p i j k jq m= , , ( , ) , ( , )p p pj O j k E i j E? ? ? ? ? ? ??.?????????. (4-52) In order to generate Bender?s cuts to the master problem, one also needs to obtain the dual solution of the sub-problem. By defining the dual variables , , v i j tu , , , p i j tu , , , c i j tu , , , v i j tv , , , p i j tv , , , , v i j k tw , , , p i j tw , , , , v i j k tpi , , , , p i j k tpi , (1) , , ,i j k t? , (2), , ,i j k t? , , ,vi j k? , , ,pi j k? , , ,ci j k? corresponding to the equations (4-39) to (4-52), one can formulate the dual of the sub-problem (DSP) below with equations (4-53) to (4-86): 64 (DSP) Minimize , , , , , , , , , , , , [0, ] [0, ]( , ) ( , ) ( ) , , , , , , , , , , , [0, ] [0, ]( , ) ( , ) , , ( ) ( ) V V P P v v v v v i j i j t i j k t i j k t i j k t t T t Ti j E i j E k j p p p p p p i j t i j i j t i j t i j t i j t t T t Ti j E i j E c j i j k i j k j S v b S w b S v b S w m ? + ? + ? ? ? ?? ? ? ? ? ?? ? ? ? ?? ? ? ? ?? ?? + + + + ? ? ? ? ? ? ? ? ? ? ? ????.?. (4-53) Subject to: (2) , , , , , , , , , , , , , 0 jk v v v v i j t j k t i j k t i j k t i j k tu u w? pi ?+? + + + ? , 0, ( , ) , ( ), [0, ]c v jki V i j E k j t T ?+? ? ? ? ? ?? ? ? ? ??????????.. (4-54) (2) , , , , , , , , , , , 0c v vi j t i j k t i j k t i j k tu w pi ?+ + + ? , 0, ( , ) , ( ), [0, ]c v jki V i j E k j t T ?+? ? ? ? ? ?? ? ? ? ??????????.. (4-55) (2) , , , , , , , , , , , , , 0 1jk i j k tv v v v i j t j k t i j k t i j k t l u u w? ? pi ?+? + + ? ?? , 0, , ( , ) , ( ), [0, ]c vl jkl i V i j E k j t T ?+? ? ? ? ? ? ? ?? ? ? ? ?????..??. (4-56) (2) , , , , , , , , , , , 0 1 i j k tc v v i j t i j k t i j k t l u w ? pi ?+ + ? ?? , 0, , ( , ) , ( ), [0, ]c vl jkl i V i j E k j t T ?+? ? ? ? ? ? ? ?? ? ? ? ?????..??. (4-57) (2) , , , , , , , , , , , 0v v vi j t i j k t i j k t i j k tu w pi ?+ + + ? , 0, ( , ) , ( ), [ 1, ]c v jki V i j E k j t T T?+? ? ? ? ? ?? ? ? ? + ???????. (4-58) 65 (2) , , , , , , , , , , , 0c v vi j t i j k t i j k t i j k tu w pi ?+ + + ? , 0, ( , ) , ( ), [ 1, ]c v jki V i j E k j t T T?+? ? ? ? ? ?? ? ? ? + ???????. (4-59) (2) , , , , , , , , , , , 0 1 i j k tv v v i j t i j k t i j k t l u w ? pi ?+ + ? ?? , 0, , ( , ) , ( ), [ 1, ]c vl jkl i V i j E k j t T T?+? ? ? ? ? ? ? ?? ? ? ? + ???..?... (4-60) (2) , , , , , , , , , , , 0 1 i j k tc v v i j t i j k t i j k t l u w ? pi ?+ + ? ?? , 0, , ( , ) , ( ), [ 1, ]c vl jkl i V i j E k j t T T?+? ? ? ? ? ? ? ?? ? ? ? + ???..?... (4-61) , , , , , , , , , 0 jk p p p i j t j k t j k t i j k tu u w? pi+? + + ? , , ( , ) , ( ), [0, ]c p jkj V i j E k j t T ?+? ? ? ? ? ?? ? ? ? ??????.???.. (4-62) , , , , , , , , , , , 0 jk jk p p c p i j t j k t j k t j k t i j k tu u u w? ? pi+ +? ? + + ? , , ( , ) , ( ), [0, ]c p jkj V i j E k j t T ?+? ? ? ? ? ?? ? ? ? ??????.???.. (4-63) (2) (2) (1) , , , , , , , , , 0j k t j k t i j t i j k tu w v pi+ ? + ? , ( , ) , ( ), [ 1, ]p jki j E k j t T T?+? ? ? ?? ? ? ? + ??????....? (4-64) (1) , ,0 , ,1 , ,0 , , ,0 , , ,0 , , 0 v v v v v i j i j i j i j k i j k i j ku u v pi ? ?? + ? + + ? , 0, ( , ) , ( )c vi V i j E k j+? ? ? ? ? ?? ???????????? (4-65) (1) , , , , 1 , , , , , , , , 0 v v v v i j t i j t i j t i j k t i j k tu u v pi ?+? + ? + ? , 0, ( , ) , ( ), [1, 1]c vi V i j E k j t T+? ? ? ? ? ?? ? ? ? ????????? (4-67) 66 (1) , ,0 , ,1 , ,0 , , ,0 , , ,0 , , 0 c c v v v i j i j i j i j k i j k i j ku u v pi ? ?? + ? + + ? , 0, ( , ) , ( )c vi V i j E k j+? ? ? ? ? ?? ?????????? (4-68) (1) , , , , 1 , , , , , , , , 0 c c v v i j t i j t i j t i j k t i j k tu u v pi ?+? + ? + ? , 0, ( , ) , ( ), [1, 1]c vi V i j E k j t T+? ? ? ? ? ?? ? ? ? ?????????? (4-69) (1) , , ,0 , ,0 , ,1 , ,0 , , ,0 , , 01 i j kv v v v v i j i j i j i j k i j k l u u v ? pi ??? + ? + + ?? , 0, , ( , ) , ( )c vll i V i j E k j+? ? ? ? ? ? ? ?? ????????. (4-70) (1) , , , , , , , 1 , , , , , 01 i j k tv v v v i j t i j t i j t i j k t l u u v ? pi ?+? + ? + ?? , 0, , ( , ) , ( ), [1, 1]c vll i V i j E k j t T+? ? ? ? ? ? ? ?? ? ? ? ???????. (4-71) (1) , , ,0 , ,0 , ,1 , ,0 , , ,0 , , 01 i j kc c v v v i j i j i j i j k i j k l u u v ? pi ??? + ? + + ?? , 0, , ( , ) , ( )c vll i V i j E k j+? ? ? ? ? ? ? ?? ????????????. (4-72) (1) , , , , , , , 1 , , , , , 01 i j k tc c v v i j t i j t i j t i j k t l u u v ? pi ?+? + ? + ?? , 0, , ( , ) , ( ), [1, 1]c vll i V i j E k j t T+? ? ? ? ? ? ? ?? ? ? ? ???????. (4-73) (1) , , , , , , , , , , 0v v vi j T i j T i j k T i j k Tu v pi ?+ ? + ? , 0, , ( , ) , ( )c vj D i V i j E k j+? ? ? ? ? ? ? ?? ?????.??????.. (4-74) (1) , , , , , , , , , , 0c v vi j T i j T i j k T i j k Tu v pi ?+ ? + ? , 0, , ( , ) , ( )c vj D i V i j E k j+? ? ? ? ? ? ? ?? ??????.?????.. (4-75) 67 (1) , , , , , , , , , , 0 1 i j k Tv v v i j T i j T i j k T l u v ? pi ?+ ? ? ?? , 0, , , ( , ) , ( )c vll j D i V i j E k j+? ? ? ? ? ? ? ? ? ?? ??????????. (4-76) (1) , , , , , , , , , , 0 1 i j k Tc v v i j T i j T i j k T l u v ? pi ?+ ? ? ?? , 0, , , ( , ) , ( )c vll j D i V i j E k j+? ? ? ? ? ? ? ? ? ?? ??????????. (4-77) (1) , , , , , , , , , , 1v v vi j T i j T i j k T i j k Tu v pi ?+ ? + ? , 0, , ( , ) , ( )c vj D i V i j E k j+? ? ? ? ? ? ? ?? ??????????.??.. (4-78) (1) , , , , , , , , , , 1c v vi j T i j T i j k T i j k Tu v pi ?+ ? + ? , 0, , ( , ) , ( )c vj D i V i j E k j+? ? ? ? ? ? ? ?? ??????????.??.. (4-79) (1) , , , , , , , , , , 1 1 i j k Tv v v i j T i j T i j k T l u v ? pi ?+ ? ? ?? , 0, , , ( , ) , ( )c vll j D i V i j E k j+? ? ? ? ? ? ? ? ? ?? ?????????.. (4-80) (1) , , , , , , , , , , 1 1 i j k Tc v v i j T i j T i j k T l u v ? pi ?+ ? ? ?? , 0, , , ( , ) , ( )c vll j D i V i j E k j+? ? ? ? ? ? ? ? ? ?? ?????????.. (4-81) , ,0 , ,1 , ,0 , , ,0 , , 0 p p p p c i j i j i j i j k i j ku u v pi ?? + ? + ? , , ( ), ( )pj O i j k j? +? ? ? ?? ? ?? ???????.???????... (4-82) , ,0 , ,1 , ,0 , , ,0 , , 0 p p p p p i j i j i j i j k i j ku u v pi ?? + ? + ? , , ( ), ( )pj O i j k j? +? ? ? ?? ? ?? ???????????..?.??... (4-83) 68 , , , , 1 , , , , , 0 p p p p i j t i j t i j t i j k tu u v pi+? + ? ? , ( , ) , ( ), [1, 1]pi j E k j t T+? ? ? ?? ? ? ? ??????????..??... (4-84) , , , , , , , 0p p pi j T i j T i j k Tu v pi+ ? ? , ( , ) , ( )pi j E k j+? ? ? ?? ???????.?.. (4-85) , , , , , , , , , , , , , , , , , 0, 0, 0, 0, 0, 0, 0v p c v p p vi j t i j t i j t i j k t i j t i j k t i j k tv v v w w pi pi? ? ? ? ? ? ? ???.. (4-86) The Bender?s master problem is obtained by adding Bender?s cuts based on the solution of the dual sub-problem. Constraint (4-88) is the optimality cut, ensuring that corresponding non-optimal solutions are excluded. Constraint (4-89) is the feasible cut to ensure that the resulting primal sub-problem is feasible. By introducing another slack variable Z, the problem P can be reformulated as an equivalent problem P below from (4-87) to (4-100). ( P ) Maximize Z ??????????????????????... (4-87) Subject to: , , , , , , , , , , , , [0, ] [0, ]( , ) ( , ) ( ) , , , , , , , , , , , [0, ] [0, ]( , ) ( , ) , , ( ( ) ( ) ( ) ( ) ( ) V V P P v v v v v i j i j t i j k t i j k t i j k t t T t Ti j E i j E k j p p p p p p i j t i j i j t i j t i j t i j t t T t Ti j E i j E c j i j k k j Z S v m b S w m b S v m b S w m m m? + + ? ? ? ?? ? ? ? ? ?? ? ? ? ?? ? ? ? ?? ? + + + + ? ? ? ? ? ? ? ? ? ( ) ) , 1, 2,3,.... i j m ??? =? ? ??(4-88) , , , , , , , , , , , , [0, ] [0, ]( , ) ( , ) ( ) , , , , , , , , , , , [0, ] [0, ]( , ) ( , ) , , ( ) ( ) ( ) ( ) ( ) ( ) V V P P v v v v v i j i j t i j k t i j k t i j k t t T t Ti j E i j E k j p p p p p p i j t i j i j t i j t i j t i j t t T t Ti j E i j E c j i j k k j S v n b S w n b S v n b S w n m n? + + ? ? ? ?? ? ? ? ? ?? ? ? ? ?? ? ? ? ?? + + + + ? ? ? ? ? ? ? ? ? ? ( ) 0, 1, 2,3,... i j n ??? ? =? ?? (4-89) 69 , , 1p pi j j ib b+ = , ( , ) pi j E? ? ???????????????.............. (4-90) , , , p p i j t i jb b? , ( , ) , [0, ]pi j E t T? ? ? ? ??????.?????.............. (4-91) , , 1i j t j v =? , si V? ? , ij C? ? ?????????????????.. (4-92) , , , ,i l t i j t l w v=? si V? ? , ij C? ? ?..???????????????. (4-93) , , , 1, 1 , 1, 0.9i j t i j t i j tw w w? ? ?? ? ? , si V? ? , ij C? ? , 1j > ??..?????... (4-94) max , 1 max , , , i jt G i j i j t w G? ? + + = ?? , si V? ? , ij C? ? ???.???????????. (4-95) min , min , , , , , , , 1*( ) i jt G i j i j i j t i j t t w G w w? ? + ? = ? ?? , si V? ? , ij C? ? ????????? (4-96) , , , , , = v k l m t i j tb w , si V? ? , ij C? ? , ,( , , ) i jk l m C? ? ??????????? (4-97) , , , , = p k l t i j tb w , si V? ? , ij C? ? , ,( , ) i jk l C? ? ???..????..????.. (4-98) , , , , , ,n n n v v i j k t i j k tb b= , ( , ) , ( )v vi j E k j+? ? ? ?? , t T? ? , cV n C? ? ?????. (4-99) , , , ,n n p p i j t i j tb b= , ( , ) pi j E? ? , t T? ? , cVn C? ? ???????????.. (4-100) The Bender?s Decomposition algorithm begins by solving the relaxed master problem and adding cuts iteratively to it until the convergence is obtained. Figure 4-8 shows the main steps of the Bender?s algorithm very briefly. 70 Figure 4-8 The Bender?s Decomposition algorithm This algorithm will always be terminated within a finite number of steps (Benders 1962). Some encouraging results in the literature (Etschmaier 1973, Florian 1972, Geoffrion 1974, and Muckstadt 1968) reported that Bender?s algorithm can solve the mixed-integer program in a relatively efficient manner. 4.3.2. A modified algorithm Under Bender?s algorithm, the number of constraints grows with the number of iterations and the integer master problem can be very costly in computation. The algorithm is of specific interest if some efficient algorithms can be adopted to solve the master problem or the dual sub-problem. Our modifications are based on the following two judgments: 71 ? Good constraints can also be generated without solving the pure integer problem at each iteration (McDaniel 1977). ? The dual sub-problem does not need to be solved to optimality if a sub- optimal objective function has been found that is less than uB (Hooker 2003). Thus, there are two approaches for developing an alternative algorithm: ? Relax the integrality of the master problem and solve it as a linear program for some number of iterations; or ? Relax the sub-problem and apply an efficient network algorithm to generate a feasible dual solution for some number of iterations. The main advantage of obtaining the cuts by relaxing the integer or sub-problem is that it takes less time to solve the relaxed problem at each iteration; however, the disadvantage of the approaches are that more iterations maybe needed for the algorithm to reach convergence since the cut generated at each iteration is not as tight as that of the non-relaxed approach. Thus, some heuristics need to be carefully designed to determine how many iterations are needed to solve the sub-problem as a relaxed network problem or the master problem as a linear problem. There are commonly two choices: (a) Continue until no further iterations are possible (in this case, no tighter cut can be derived by relaxing either the problems, (b) Solve them for a fixed number of iterations in the beginning. Our revised procedure combined the two choices and is given below: 72 Figure 4-9 The revised Bender?s Decomposition algorithm 4.3.3. Reformulation of the relaxed sub-problem The reason to relax the sub-problem is to apply more efficient algorithms to the formulation with network properties. In the relaxed sub-problem, the decision variables of turning and holdover flows can be converted to decision variables of link 73 flows by introducing connector and holdover arcs in the network, as depicted in Figure 4-10 (a) and 4-10 (b). (a) (b) Figure 4-10 A graphic illustration of connectors and hold-over arcs After the network conversion, the relaxed sub-problem (RSP) can be re- formulated in the new network, as shown with equations (4-89) to (4-82): (RSP) Maximize , ,i i T i D f ? ? ?????????????????..??. (4-79) Subject to: + , , , , { } (i) (i), 0 ji ij i j t j i t j i j t f f ? ?? ? ? ?? ?? ? ? =? ? , ', [0, ]i V t T? ? ? ? ???????? (4-80) , , , ,i j t i j tf S? , ( , ) , ( j), [0, ]vi j E k t T+? ? ? ?? ? ? ?????????..?. (4-81) + , , , , { } (i) (i), 0 ji ij i j t j i t j i j t f f ? ?? ? ? ?? ?? ? ? =? ? ???????????????..... (4-82) 74 where , ,i j tf : the flow of link ( , )i j at time t , ,i j tS : the flow upper-bound of link ( , )i j at time t The upper bounds for the vehicle connectors are determined by the saturation turning flow and the current signal indication; the flow upper bounds for the holdover arcs represents the link?s capacity in holding vehicles or pedestrians; and the flow upper bounds for the other pedestrian and vehicle links are equal to those in the mixed-flow network. To solve this relaxed sub-problem, this study adopts the generalized dynamic flow algorithm developed by Halpern (1979). It is an extension of the classic dynamic maximal problem where the link capacities are fixed and no holdovers at nodes are allowed (Ford, 1956). The algorithm requires no construction of the time-expanded network, which is usually inefficient because the resulting network may be extremely large, varying with the study time period and the discrete time interval. The main steps of the algorithm are stated below: Step-1: Data truncation: it performs only once at the beginning with the purpose to modify the available data to save memory space and computational effort in subsequent parts of the algorithm. Step-2: Breakthrough: it tries to find a path from the source to the destination along which to send an additional positive flow. Step-3: Backtracking: it lists and orders all vertices that enable the breakthrough path. 75 Step-4: Saturating: it determines the maximum additional amount of flow that may be delivered from the source to the destination. Step-5: Updating: it performs the necessary data modifications that reflect the changes in the flows and holdovers along the breakthrough path. 4.4. Numerical example This section presents an illustrative case during a hypothetical emergency evacuation at the M&T stadium in downtown Baltimore with the proposed model. 4.4.1. Evacuation scenario The scenario assumes that a total of 20,000 individuals need to leave the stadium after the football game. The available transportation modes include private cars, buses, and the light rail. The satellite image and the parking lot layout around the M&T stadium are depicted in Figure 4-11. Figure 4-11 Layout of the M&T stadium in Baltimore city The following information is assumed to be available to define the scenario for the model implementation: 76 ? Pedestrian network layout (See Figure 4-12) ? Locations of parking areas and pick-up points (See Figure 4-12) ? The information about connection points (See Table 4-1) ? Vehicle network layout (See Figure 4-13) ? Vehicle destinations (See Figure 4-13) ? The set of critical movements at critical intersections (See Table 2) The layout of the pedestrian network is shown in Figure 4-12. The source node 1000 represents the stadium; the sink nodes 101 to 105 are the parking lots; and the sink node 106 is the pick-up point for those without access to passenger cars. The solid arrow lines are sidewalks and the dashed arrow lines are crosswalks. Figure 4-12 Representation of the pedestrian network The pedestrian destination nodes are connected to the vehicle source nodes, which are also the connection nodes. The capacity of each connection node is estimated based on the parking or waiting spaces, and the average car access times 77 are based on the size of the parking lot. The carpooling rates are assumed to be 2 for the parking lots and 20 for the transit stops. Table 4-1 Connection node information Connection ID Connection Type Car Pooling Rate Car Access Time Estimated Capacity 101 Parking Lot 2.0 60s 4000 veh 102 Parking Lot 2.0 20s 1000 veh 103 Parking Lot 2.0 20s 2000 veh 104 Parking Lot 2.0 20s 500 veh 105 Parking Lot 2.0 60s 2500 veh 106 Transit Stop 20.0 20s 60 ped The layout of the vehicle network is presented in Figure 4-13. The arrows indicate the possible flow directions between nodes. The sink nodes 301, 302, 303, 304 and 305 can be viewed as destinations for vehicles to further access I83, US40, I395 South, MD295 South, and MD2, respectively. These solid lines represent the vehicle roads and the other lines represent the connectors or the turning movements. The dashed lines represent intersection links that are subjected to conflicts. 78 Figure 4-13 Representation of the vehicle network Table 4-2 lists the three intersections with major flow conflicts that require traffic signal controls. Table 4-2 Conflict flow movements at intersections Intersection ID Crosswalks Vehicle Upstream Link Vehicle Downstream Link 1 (10, 16) (50, 56) (56, 59) (55, 56) (56, 53) (9, 14) (56, 58) (56, 59) (14, 15) (57, 56) (56, 53) (56, 58) (56, 59) (58, 56) (56, 58) (15, 16) (56, 59) (56, 53) 2 (1, 2) (103, 50) (50, 56) (51, 50) (50, 56) 3 N/A (63, 62) (62, 301) 79 (62, 58) The first intersection (the crossing of Hamburg Street and Russell Street) is a critical intersection with the most potential conflicts. The ring and barrier diagram for the intersection is depicted in Figure 4-14 (only including possible turning movements for the stadium traffic): 2?1? 5? 6? 8? 10? 4?3? 11? 12?7? 9? Figure 4-14 The signal phase plan for Russell St@MD295 The allowed vehicle and pedestrian movements for each phase in the above signal plan are listed in Table 4-3: Table 4-3 Movements for Signal Phases Phase Vehicle Upstream Link Vehicle Downstream Link Crosswalk 1 (55, 56) (56, 53) N/A (57, 56) (56, 53) 3 (58, 56) (56, 53) (9, 14) 5 (55, 56) (56, 58) N/A (55, 56) (56, 59) 7 (57, 56) (56, 58) N/A (57, 56) (56, 59) 9 N/A N/A (14, 15) 80 (15, 16) 11 (50, 56) (56, 58) N/A 4.4.2. Optimized results The proposed control strategies for use with the optimization model include: (1) Pedestrian link directions; (2) Signal timings for each phase (dynamic control or pre-timed control); (3) Dynamic flows on each pedestrian walkway; (4) Dynamic flows on each vehicle roadway; (5) Pedestrian flow arrivals at the parking areas and transit stop; and (6) Vehicle and evacuee flow arrivals at the vehicle destinations The optimized moving direction for each pedestrian link is shown in Figure 4-15, where the generated results are very consistent with the experienced-based method. Figure 4-15 Optimized Moving Directions for Pedestrians 81 Two types of signal controllers are used for experiments with our model: dynamic controller and pre-timed controller. Table 4-4 lists the minimum and maximum green durations for each phase and the cycle length. Table 4-4 Minimum and maximum green for signal phases of intersection-1 Phase ID Minimum Green Maximum Green Minimum Cycle Maximum Cycle 1 10s 90s 15s 180s 2 4s 4s 3 10s 90s 4 4s 4s 5 5s 30s 6 4s 4s 7 5s 30s 8 4s 4s 9 5s 30s 10 4s 4s 11 10s 90s 12 4s 4s Table 4-5 lists the optimized signal timing plan for the dynamic controller of Signal-1. Since the timings are different from cycle to cycle, only the first and last 82 three cycles are shown in the table. It is noticeable that the green times for the pedestrian phase (phase 9) are relatively what? Missing word at the beginning period and then gradually reduced to a shorter interval. This is consistent with the reality that there are more crossing evacuees and fewer vehicles in the network at the beginning of the evacuation, thus requiring longer green times for the pedestrian phase so that more people can access their vehicles or get to the pick-up points. Table 4-5 Optimized Cycles for Dynamic Signal Controller 1 Cycle Phase 1 (s) Phase 3 (s) Phase 5 (s) Phase 7 (s) Phase 9 (s) Phase 11 (s) 1st 44 15 5 5 30 15 2nd 54 22 8 12 30 22 3rd 52 28 10 14 22 28 Bottom 3rd 64 90 20 25 5 90 Bottom 2rd 63 90 20 24 5 90 Bottom 1st 60 90 20 21 5 90 In comparison, the optimized signal timing plan for the pre-timed controller is listed in Table 4-6. 83 Table 4-6 Optimized Cycles for Pre-timed Signal Controller-1 Cycle Length (s) Phase Green Time (s) 139 1 68 2 4 3 56 4 4 5 20 6 4 7 24 8 4 9 16 10 4 11 56 12 4 By comparing the throughput curves under the dynamic control and the pre-timed control in Figure 4-16, one can see that the benefits of dynamic control are quite clear during the early stage of evacuation. This is likely because the timings allocated for the vehicle movements are wasted for the pre-timed controllers at the beginning. As time goes on, the relative benefits obtained by the dynamic control begin to decrease, mainly because the traffic conditions on the road are becoming congested. The adaptive control strategy has little benefit over a pre-timed strategy under over- saturated conditions. It can also be foreseen that the benefits of the dynamic control will rise again at the end of the evacuation when all the pedestrians have gained access to their vehicles. 84 Figure 4-16 Throughput comparisons between the dynamic and pre-timed controller Figure 4-17 (a) and (b) shows the optimized flow distribution aggregated over five minutes in the pedestrian network at the start of the evacuation and at the end of the first hour, respectively. It can be observed that more pedestrian flows are assigned to the network at the start than one hour later since there are relatively fewer vehicle flows in the beginning. Figure 4-17 (b) also shows the hourly pedestrian throughput for the destinations in the unit of the number of pedestrians. 1000 104 1 103 2 3 4 5 6 7 8 9 10 11 12 105 101106102 13 14 15 16 17 g28g21g19g19g83g83g75 g23g22g19g19g83g83g75 g21g21g19g19g83g83g75 g22g23g19g19g83g83g75 g28g21g19g19g83g83g75 g23g22g19g19g83g83g75 g21g24g19g19g83g83g75 g20g27g19g19g83g83g75 g20g27g19g19g83g83g75 g20g27g19g19g83g83g75 g20g27g19g19g83g83g75 g21g25g19g19 g83g83g75 g22g23g19g19 g83g83g75 g22g23g19g19g83g83g75 g21g21g19g19 g83g83g75 g20g21g19g19g83g83g75 g20g21g19g19g83g83g75 g21g25g19g19 g83g83g75 g20g27g19g19g83g83g75 g21g21g19g19 g83g83g75 1000 104 1 103 2 3 4 5 6 7 8 9 10 11 12 105 101106102 13 14 15 16 17 g22g19g19g19g83g83g75 g22g19g19g19 g83g83g75 g21g21g19g19g83g83g75 g20g21g19g19g83g83g75 g22g19g19g19g83g83g75 g20g26g19g19g83g83g75 g20g20g19g19 g83g83g75 g25g19g19g83g83g75 g25g19g19g83g83g75 g25g19g19g83g83g75 g25g19g19g83g83g75 g20g27g19g19 g83g83g75 g20g21g19g19 g83g83g75 g20g21g19g19g83g83g75 g27g19g19g83g83g75 g23g19g19g83g83g75 g23g19g19g83g83g75 g20g27g19g19g83g83g75 g28g27g19 g20g27g23g19 g21g23g26g19 g28g27g19 g21g21g19g19 g20g22g19g19 g21g21g19g19g83g83g75 g19g83g83g75 g19g83g83g75 g19g83g83g75 g19g83g83g75 g19g83g83g75 (a) (b) Figure 4-17 Pedestrian flow distribution in the network Figure 4-18 (a) and (b) shows the optimized flow distribution aggregated over five minutes in the vehicle network at the start of the evacuation and at the end of the 85 first hour, respectively. It can also be observed that fewer vehicle flows are assigned to the network at the start than one hour later since the evacuees need time to access their vehicles in the beginning. Figure 4-18 (b) also shows the hourly vehicle throughput for the destinations in the unit of the number of vehicles. (a) (b) Figure 4-18 Vehicle flow distribution in the network 4.4.3. Model Comparison In our proposed model, the three major modifications to the conventional methods are: ? Separating signal phases for crossing pedestrians and right turn vehicles. ? Considering the transition time between the phases. ? Formulating the objective as maximizing the evacuee throughput. To illustrate the importance of the first two model modifications, we have re- executed the model and generated the optimized signal timing plans with the typical signal phasing plan shown in Figure 4-19. Table 4-7 shows the results that the optimal evacuation model under the typical phasing plan will yield much shorter 86 signal timings that are mostly insufficient for the need of evacuation flows. Another notable property is that without considering the potential conflicts between the massive pedestrian crossings and the right-turn vehicles, any optimal evacuation model may substantially overestimate its efficiency and yield unreasonable flow patterns. Figure 4-20 depicts two ratios: the ratio between the turning volume from link (57, 56) to link (56, 59) and its saturation flow rate, and the ratio between the pedestrian volume on link (10, 16) and its saturation flow rate in each cycle. It is expected that the sum of these two ratios (i.e., volume to capacity ratios) should not exceed one since these two movements are in direct conflict and only one movement is allowed at a particular time interval. However, both ratios, without accounting for the pedestrian-vehicle conflicts, are close to one, which implies that these two flows coexist during most of the evacuation time except at the beginning stage, when no vehicles are loaded onto the network. This is obviously, unrealistic and evidences the need to address such conflicts. In brief, the formulations based on conventional phase plans tend to give unrealistic flow patterns, over-estimate the objective function, and generate short green durations. 1? 3? 2? 5?4? Figure 4-19 Conventional signal phase for Intersection 1 Table 4-7 Optimized cycles for conventional pre-timed signal controller-1 87 Cycle Length (s) Phase Green Time (s) 50 1 32 2 24 3 16 4 16 5 24 Figure 4-20 Comparisons between utilization ratios of two particular conflict movements Another important contribution of this model is to formulate the objective function as maximizing the evacuee throughput rather than the vehicle throughput to each destination by creating the expanded mixed-flow network. If the objective function is to maximize the total number of vehicles arriving at the safety nodes over a given time window, one needs not to expand the network. Table 4-8 compares the throughput results generated from the two objective functions. The percentage of buses is the proportion of buses in the total arriving vehicles to the destination nodes, and the percentage of evacuees in buses is the proportion of evacuee throughput rescued by buses. 88 Table 4-8 Comparison between different objectives Objective Function Evacuee Throughput Vehicle Throughput Percentage of buses Percentage of evacuees in buses 1 (Maximize Evacuees) 5234 persons 2077 vehicles 2.9% 23% 2 (Maximize Vehicles) 4868 persons 2389 vehicles 0.2% 2.0% From Table 4-8, we can draw the following conclusion: ? Targeting the evacuation on maximizing vehicles or evacuees can lead to totally different control strategies and outcomes. ? As reflected in the percentage of buses, the control plan with objective-1 can evacuate more evacuees and use more transit vehicles while the control plan with objective-2 will favor the use of more passenger cars. ? Under the first objective, the number of buses constitutes only a small percentage of the total evacuation flow (3%) but carries a substantial volume of evacuees (23%). 4.4.4. Algorithm performance To evaluate the operational efficiency, this study also conducted performance evaluation between the proposed algorithm and the Bender?s original algorithm. The MOSEK solver is called whenever the linear programming or integer programming problem needs to be solved during the iterations. The network algorithm, including the time-expanded network and generalized maximum flow algorithm, is 89 implemented with a code by C#. The performance comparison includes the following algorithms: 1) Bender?s original algorithm. 2) Modified algorithm relaxing master problem only. 3) Modified algorithm relaxing sub-problem only and employing time-expanded network algorithm. 4) Modified algorithm relaxing sub-problem and employing generalized maximum flow algorithm. 5) Modified algorithm relaxing both the master problem and the sub-problem while employing generalized maximum flow algorithm (proposed algorithm). Table 4-9 lists the computing timing and number of iterations required for the above algorithms on our illustrated evacuation scenario. For each algorithm, the number of iterations required was divided into two categories: solving a relaxed problem and a non-relaxed problem. All algorithms are tested on a laptop computer with a single core 1.86 GHz CPU and a 504 MB memory as the results are for comparison of their relative efficiency, not for the actual operational need. The above algorithms have also been tested on another desktop computer with the configuration of Dual Core 2.67 GHz CPU and 8 GB memory, and their running times can be cut in one third. Table 4-9 Algorithm Performance Comparisons Algorithm Time(h) Number of Iterations 90 Total Master Sub Relaxed Master Integer Master Relaxed Sub Linear Sub 1 72 56 16 0 821 0 821 2 54 41 13 724 289 0 1013 3 75 58 17 0 834 687 247 4 73 58 15 0 834 687 247 5 53 40 12 743 275 622 385 Figure 4-21 plots the convergence rate for the original Bender?s algorithm (algorithm-1) and our proposed algorithm (algorithm-5). The results are plotted once every 200 iterations. ? ?? ? +? UB lB Figure 4-21 Convergence comparisons between the two algorithms From Table 4-9 and Figure 4-21, we can reach the following conclusions: 91 1) Relaxing the master problem significantly improves the running time from 72 hours to 53 hours, although it requires more iterations to solve to its optimality, because the CPU saving for solving the linear program is significant, compared with solving the pure integer program. 2) Relaxing only the sub-problem does not improve the algorithm?s overall efficiency. The savings in solving the sub-problem cannot compensate for the additional computation costs incurred in solving the integer problems brought about by the generated loose cut. 3) There are some savings in applying the generalized maximum algorithm compared with the time-expanded network. This is consistent with Halpern?s claim that the generalized maximum algorithm is efficient as long as the network properties do not changed frequently. 4) By combining the two relaxations, our proposed algorithm clearly outperforms the original Bender?s decomposition procedure and the master relaxing algorithm. An alternative to the BD algorithm is to employ some branch-and-cut algorithms based on a similar concept to the relaxation step employed in the BD algorithm. The main idea of the branch-and-cut algorithms is to relax the integrality constraints and solve to linear optimality, find the violated constraints and add a cut to them to exclude the current solution. Table 4-10 provides the computation times required by the Bender?s original algorithm, our proposed algorithm, and the branch-and-cut algorithm. For the Bender?s algorithm, we also provide the computation time to solve 92 to different optimality conditions. The %x optimality conditions mean that the algorithm terminates when 1 %U L U B B x B ? ? ? Table 4-10 Computation comparisons of different optimality conditions Algorithm Optimality Condition Number of iterations/cuts CPU time (h) 1 To 100% optimality 821 72 To 90% optimality 548 40 5 To 100% optimality 1017 53 To 90% optimality 810 28 Branch and Cut To optimality >3000 >80 From Table 4-10, we can draw the following conclusion: 1) The Bender?s Decomposition algorithms perform much better than the branch-and-cut algorithm in this example of a medium- to large-scale network problem. 2) For both solving 100% and 90% to optimality, our proposed algorithm outperforms the conventional Bender?s decomposition algorithm in terms of the computation time although it requires more iteration in both cases. 3) For the algorithms based on Bender?s Decomposition, solving the problem to 90% optimality only took half of the computation effort required for solving to 100% optimality. Thus, users can adjust the optimality criterion flexibly based on their available time budget and solution requirement. 93 4.5. Summary This chapter has presented an enhanced model for integrating the optimization of the mixed-flow movements and the signal timings within the metropolitan area that considers the conflicts between congested vehicle and pedestrian flows. The proposed model employs the common node-link concept to represent the evacuee and vehicle networks and designs connectors to model turning movements at intersections. The connection node is defined to connect the flow conversion between pedestrian and vehicle flows. Based on the locations of pick-up points for evacuees using transit systems and parking garage distributions for these having access to vehicles, the proposed model is capable of producing a set of effective routing strategies to guide pedestrians and vehicles. The model also can concurrently provide an optimal signal timing design for both the dynamic control and pre-timed strategies. A set of constraints, representing signal control mechanisms, is employed in the model to capture the interactions among the mixed flows in the metropolitan area. The solution algorithm is a modification of the conventional Bender?s decomposition method. Its main idea is to generate cuts from solving relaxed decomposed problems that run much faster. Although it may need more iterations for the algorithm to converge compared with the conventional Bender?s decomposition method, overall computation time can still be saved. The numerical experiment assumed a hypothetical terrorist attack in the Baltimore downtown area. The result confirms the claimed contributions of our proposed model and the computation savings in applying the revised algorithm. 94 Chapter 5: Mixed Flow Simulation Model This chapter presents the simulation model developed to replicate the mixed pedestrian-vehicle flow environment. To model the mixed-flow dynamics and their complex interactions, the following critical issues need to be first addressed: 1) How to model the real-time way-finding strategies of pedestrians and drivers? This includes identification of an initial route from their origins to the destination, and possible later changes based on the perceived roadway conditions. 2) How to model pedestrian and vehicle movements along all possible directions? Note that pedestrians may make diagonal moves at an intersection or at any other locations, whereas vehicles are confined by the boundaries of travel lanes at roadway segments. 3) How to model the potential conflicts between vehicles and pedestrians? Some existing simulation models have addressed the vehicle-vehicle and pedestrian- pedestrian conflicts, but not the pedestrian-vehicle conflicts. 4) How to model the response of drivers or walking evacuees during conflict conditions as their decision behaviors are likely to correlate with the urgency of the evacuation state and their waiting times at the conflict locations To address the above critical issues in the model development, the chapter is organized as follows: Section 5.1 introduces the basic concept of the Cellular Automaton (CA) modeling for vehicle simulation. Section 5.2 details the extended mixed-flow CA modeling framework. Section 5.3 presents the methodology for defining the neighborhood cells-taking logic, including the concept for representing the maximum speed and diagonal movements. Section 5.4 illustrates the notion of the 95 floor field that can reflect an individual?s way-finding behavior. Section 5.5 proposes the conflict-solving procedure using the competition factor, constituted with the waiting time and yielding cost, to reflect the conflicts between vehicles and pedestrians. One can adjust the parameters embedded in a competition factor to represent different levels of aggressiveness among individual drivers or pedestrians. Section 5.6 details the calibration and validation procedure for applying the proposed mixed-flow simulation model to replicate the real-world scenario. 5.1. Vehicle simulation with the Cellular Automaton concept The Cellular Automaton (CA) model consists of a regular grid of cells, each having a set of cells called a neighborhood. The state of a cell can evolve over discrete time steps based on the preset rules and the state of its neighboring cell. Such rules can be applied iteratively for as many time steps as needed. Von Neumann was one of the pioneers to incorporate a cellular model into his ?universal constructor? in 1940, and the logic was published in 1966 (Von Neumann, 1966). Wolfram was the first to perform comprehensive studies of the cellular automata (Wolfram, 1983). Instead of grounding the simulation logic on a well-established traffic flow theory, some researchers have explored the Cellular Automata (CA) methodology to develop low-fidelity micro-simulation traffic models that update individual movements with a set of local rules over discretized time and space units. Due to their computing efficiency, such models are quite promising for large-scale networks (Schreckenberg et al., 2001) or online simulation (Wahle et al., 2001). 96 Nagel and Shreckenberg (1992) are two of the pioneers who attempted to apply Cellular Automata to study one-dimensional vehicle traffic dynamics. Their model (NaSch model) is defined with one-dimensional arrays of Lsites, and each site may either be occupied by one vehicle or be empty. For an initial configuration, every update of the simulation system consists of the following four consecutive steps, which are performed in parallel for all vehicles: 1) Acceleration: if the velocity v of a vehicle is lower than maxv and if the distance to the next car ahead is larger than 1v + , then the speed is advanced by one [ 1]v v? + ; 2) Deceleration: if a vehicle at site isees the next vehicle at site i j+ with j v? , it will reduce its speed to 1j ? [ 1]v j? ? ; 3) Randomization: with the probability of p , the velocity of each vehicle (if greater than zero) is decreased by one [ 1]v v? ? ; 4) Vehicle motion: each vehicle will be advanced v cells forward. The mixed-flow simulation presented hereafter is extended from the NaSch model, which covers multiple lanes and offers a more realistic representation of the roadway traffic by creating a set of 2-D cell networks and related movement rules. The same model framework has also been adopted to simulate the pedestrian movements and the complex mixed-flow interactions in the evacuation network. 5.2. Mixed-flow Cellular Automaton (MCA) framework The MCA model, grounded on the Cellular Automata logic, has the following key features: 97 ? The study area is divided into two overlapped layers of rectangular grids whose cell sizes are determined by the space that a vehicle and a pedestrian can occupy. Each cell can hold only one vehicle or pedestrian as depicted in Figure 5-1. ? The maximum speed of a pedestrian is one pedestrian cell per time step. ? The vehicle or pedestrian is supposed to move in a straight direction at each time step. ? Pedestrians are grouped by their origins and destinations. ? Random factors are used to reflect the behavioral discrepancies associated with either drivers or pedestrians under various traffic environments. Figure 5-1 Cell lattice representation of an example intersection The Mixed-Cellular Automata (MCA) model takes the following steps to simulate the evolution of the mixed vehicle-pedestrian flows: 1) Update each vehicle?s position at current interval t , based on the direction and speed in interval 1t ? . 2) Update each pedestrian?s position at current interval t, based on the speed in time interval 1t ? . 3) Determine each vehicle?s target position at the next step 1t + from the current (a) (b) (c) 98 interval t , based on the floor fields. 4) Check whether or not multiple vehicles share the same target position, and then solve the vehicle-to-vehicle conflict by adjusting their target cells. 5) Determine each pedestrian?s target position for the next step 1t + from the current interval t. 6) Check whether multiple pedestrians share the same target position, and then solve the conflict by adjusting their target cells. 7) Check whether both pedestrians and vehicles share the same target position, and then solve the conflict by adjusting the target cells. 8) Reposition each individual decision maker to its target cell and then return to step 1 for the next time step. 5.3. Neighborhood Definition The neighborhood is defined as the cells that an individual can reach within one time step. The time step is usually very short (e.g., 0.5 seconds). For convenience of illustration, pedestrians are assumed to move toward one of the eight possible directions at each time step: North, South, East, West, Northwest, Northeast, Southwest and Southeast. With such an assumption, Figure 5-2 shows the neighborhood defined in this study under different maximum velocities of one to three cells per time step. However, one can certainly adopt other types of neighborhoods for different applications (Kretz, 2007). 99 Figure 5-2 Neighborhood cells for different maximum velocities Note that the following two critical issues need to be tackled in defining the neighborhood: (1) The neighborhood defined for vehicles with their maximum velocity may yield a non-integer number of cell distance sizes, e.g., 2.5 cells per time step; (2) The neighborhood defined for the diagonal movement should reflect the fact that the diagonal length of a cell is longer than the distance of the vertical or horizontal movements. To address the first issue, one needs to round up the fractional speed to integer speed at each time interval and then adopt the corresponding neighborhood definition for that speed. The round-up is a stochastic process that gives two probabilities for the two possible round-up values. For example, assuming that a vehicle?s maximum speed is .a b cells per time step ( a is the integer part and b is the fraction part), the following two possible rounding-up values exist for this vehicle: a cells per time step and 1a + cells per time step. The probabilities can be computed as: 100 ( ) 1P v a b= = ? ??????????.???????????.. (5-1) and ( 1)P v a b= + = .?????????????????????.. (5-2) With respect to the second issue, most existing CA-based simulation models view the diagonal move in the same manner as the lateral or parallel movements (Yamamoto and Kokubo, 2007; Kretz, 2007). Such a simplification could yield unrealistic results when replicating the movement of massive pedestrian flows over a long walking distance. In reality, the distance of diagonal moves is longer than vertical or horizontal moves. For example, a vehicle in Figure 5-3 moves at a speed of four cells/time interval. It traverse four cells per unit time in the vertical direction, but only 4/1.5=2.66 cells per unit time in the diagonal direction since the distance of a diagonal movement is 1.5 times of each horizontal/vertical movement. Most CA models do not account for such a difference, and thus could move an individual at an unrealistic speed. To provide a realistic representation of such a diagonal move, this study proposes the following steps in the simulation: 1. First, move the target individual to the new position with the maximum moving velocity; 2. Then, keep the same position right on the grid by performing the following repositioning process: assuming that two candidate points shown in Figure 5-3 are selected, one can assign each with a probability for selection. The probability is determined by the distance between the current position and the target point. 101 In Figure 5-3, the maximum velocity of an individual is four cells per time step. Thus, if taking a diagonal move, he/she will be at point C, a position between cell A and cell B. However, in the CA model, the position of each individual should be exactly in a cell rather than somewhere between cells. By applying the above procedure, the probability of an individual falling on point A or point B can be calculated as: , ( ) ACi t AC BC dP x A d d = = + ???????????????????.. (5-3) and , ( ) BCi t AC BC dP x B d d = = + ???????????????????.. (5-4) where, , ( )i tP x K= is the probability that an individual falls on point K, and mnd is the distance from point m to point n . In either case, the maximum velocity of the next time interval can be calculated as: max max , , 1i t i t ACv v d?= + ?????????..????????????.. (5-5) and max max , , 1i t i t BCv v d?= ? ?????????..????????????.. (5-6) respectively, where max ,i tv is the maximum speed of individual iat time step t. 102 ,i tx Figure 5-3 Example of diagonal moves 5.4. Floor Fields The way-finding decision-making process for each individual at each time step depends on many factors. For example, evacuees tend to move towards their destinations in the same directions under the same traffic conditions. To reflect the impact of these factors on the simulation, the proposed simulation model adopts the distance, direction, and signal floor field concepts. 5.4.1. Floor field for distance To model the real-time way-finding behavior, one needs to update the perceived shortest path to the final destination at every simulation time step. This process often causes a great computing burden on the system. Rather than globally updating the paths, the study adopts the notion of a distance floor field (Burstedde et al., 2001) for a real-time decision, based on the local neighborhood information. The core logic is 103 to assign a value to every cell to represent the shortest path distance from that cell to the final destination. Cells with lower values indicate that they are closer to the destination and thus the floor fields in the neighborhood of an individual can help to decide where they should move. This study assigns a value of 1.5 (a close value to the exact distance of 2 units) rather than 1 for such a diagonal move. Figure 5-4 illustrates an example of the distance floor field, given the upper-right destination cell. Figure 5-4 Distance floor field of an example intersection 104 5.4.2. Floor field for direction Note that both pedestrians and vehicles under the identical environment are assumed to have the tendency of moving toward the same directions. Thus, aside from the distance, the preference to keep the same direction is another individual behavior included in the model. This study introduces the floor field template, based on the moving direction and the maximum speed at the previous time step. To limit the number of templates, the simulation process considers only eight moving directions. Figure 5-5 gives two examples of the floor field. The first is for the east moving pedestrian with the maximum speed of one cell per time step, and the second is for the same pedestrian without moving at the last time step. The template?s center indicates the individual?s current position and the other cells belong to his/her neighbors. For the east-moving pedestrian, he/she has the most tendency to keep moving east, and it is almost impossible to abruptly reverse his/her direction to move west. However, for the motionless pedestrian, the template exhibits no difference to move to any direction. (a) East moving individuals (b) Motionless individuals 105 Figure 5-5 Examples of direction floor fields 5.4.3. Floor field for signal Similar to the concept of static distance floor field that represents an individual?s preference over the distance, the signal floor field aims to reflect the signal controller?s effect on an individual?s movement. Such a floor field depends on the signal controller?s status at a given time step. Vehicles are expected to stop in those approaches with red indications, and the pedestrians are expected to be away from the restricted walking areas at a given time step. To reflect such restrictions, this study employs a sufficiently large number for the corresponding cells to prevent vehicles or individuals from entering these cells. Figure 5-6 Examples of signal floor fields for vehicle and pedestrian network Figure 5-6 gives an example of the dynamic signal floor field for the given time interval when the East-West vehicle and pedestrian flows are allowed to move and the South-North vehicle and pedestrian flows are prohibited. The black cells in the vehicle and pedestrian networks represent the cells with large floor fields. The white cells have the identical floor field of zeros. The sufficiently large floor field values in the black cells will stop flows from white cells to black cells, but will facilitate the flows from black cells to white cells. 106 5.4.4. Selection of target cells To model the probability of moving to a certain neighborhood cell or remaining at the same location, the study defines a utility function ,i jU for all possible movements from cell i to cell j . The utility function represents the gain made from the choice. Given the utility functions of all possible movements, one can express the probability of a particular movement from cell i to cell j as follows: , , , ( ) i j i k U i j U k i i eP e ? ?? ? = ? ??????????????????????.. (5-7) In Equation (5-7), ,i jP is the probability of an individual moving from cell i to cell j and ( )i? is the set of unoccupied neighborhood cells of the cell i . Equation (5-7) implies that an individual is more likely to take a movement of a higher utility. Grounded on the notion that an individual will select the target cell to move, based on the floor field values at each time interval, this study has further made the following assumptions: (1) Each individual has a larger probability to move to a cell closer to the destination. (2) Each individual has a larger probability to continue the movement in the same direction; and (3) Each individual will generally follow the traffic rules and the instructions of law-enforcement staff. 107 To link the utility function to the floor fields, one can interpret the gain as the reduced floor fields due to the movement. Thus, the utility function can be expressed with Equation (5-8): , , , , dist dir sig i j dist i j dir i j sig i jU w M w M w M= ? + ? + ? ??????????????. (5-8) where, ,i jU is the individual utility gain if moving from cell i to the cell j ; ,disti jM? is the decreased value in the distance floor field if moving from cell i to the cell j ; , dir i jM? is the decreased value in the direction floor field if moving from cell i to the cell j ; , sig i jM? is the decreased value in the direction floor field if moving from cell i to the cell j ; and distw , dirw , sigw are the parameters to reflect the weight of each floor field. For example, the bold number in each cell in Figure 5-7 is the weighted floor field value, and the number in brackets denotes the cell index. Consider an individual in cell (5) who is making a choice of movements out of 9 possible options, (i.e., moving to 8 directions or staying at the same location). By setting 1? = , one can use the above equation to compute the probability of moving towards to each of these 9 directions. The probabilities for moving to each of these nine movements are shown in the following set: (0.07,0.2,0.31,0.04,0.2,0.11,0.01,0.02,0.04) . 108 6 (1) 5 (2) 4.5 (3) 6.5 (4) 6 (5) 5.5 (6) 7.5 (7) 7 (8) 6.5 (9) Figure 5-7 An example of decision making for the next movement 5.5. Modeling the responses during conflict movements Figure 5-8 illustrates an intersection, which has 2 OD-pairs for vehicles and 2 OD-pairs for pedestrians. Assuming that the pedestrians stick to the rules that crossing can only occur at the intersection, Figure 5-8 depicts several possible vehicle paths for each OD-pair and the potential conflict locations. Note that during the evacuation process, there are three types of potential conflicts: between pedestrians and pedestrians, between vehicles and vehicles, and between pedestrians and vehicles. To model the possible responses during conflict movements, this study employs the following competition factor concept. 109 Figure 5-8 Types of conflicts at an intersection Competition factor Conflicts will always take place whenever there are more than one individual targeting the same cell. Since the outcome is that only one individual can finally occupy the cell, one can regard this as a process of competition for the target cell among candidate individuals. This study employs the competition factor attached to each competitor to approximate the likelihood for an individual to win the competition. In general, the more waiting time an individual has endured, the more aggressive he/she would be. When a vehicle-pedestrian conflict happens, the same mechanism is used. By denoting the competition factor, the current waiting time of individual i at time step t , and the yielding cost for individual i under the particular conflict scenario at time t, as ,i tK , ,i tW and ,i tC , one can model the competition factor as follows; , , , ( , )i t i i t i tK f W C= ????????????????????? (5-9) 110 While the exact functional is to be estimated from the field data, this study tentatively adopts a linear relationship as follows in this study: , ,0 , ,i t i i t i tK K W C? ?= + + ????????????..?????? (5-10) ,0iK can be interpreted as the initial aggressiveness of individual i ; ? is the patience factor; and ? is the cost factor. A larger ? implies a rapid increase in aggressiveness over time, and thus is less likely to yield to others. A larger ? implies a less likelihood of yielding to others, given the same perceived cost. Note that the yield costs indicate the additional effort needed to yield to others. For example, a vehicle traveling at 80 miles per hour demands much more effort than a vehicle traveling at 20 miles per hour to yield to a pedestrian. This study adopts the following simple cost function to represent such a behavioral pattern: , ,i t i tC v= ? ????????????????????? (5-11) where, ,i tv? is the speed deceleration needed for individual i to yield to others at time step t. Figure 5-9 depicts an example of the cost factor between a vehicle and a pedestrian. If the vehicle at the speed of three vehicle cells per time unit intends to yield to the pedestrian, it can only stay at the same position and thus the cost for it to yield is to decelerate at the rate of three vehicle cells at the time step. For the same reason, the additional cost for the pedestrian to yield to the vehicle is one pedestrian cell. 111 3vehC veh cells= ? 1pedC ped cells= ? Figure 5-9 An example to illustrate the cost factor In addition to defining the competition factor for each pedestrian and vehicle, this study also introduces another competition factor to model the hesitation behavior. This is because when conflict happens among several individuals competing for the same cell, no one will make a move. In that case, nobody wins the competition. The proposed mechanism for modeling such behavior is presented below. Pedestrian-Pedestrian conflict If multiple pedestrians are targeting the same cell, they will compete for the opportunity to move forward, based on their current competition factors. For example, in Figure 10, three pedestrians are competing for the same cell, and the probability that the i -th pedestrian will win is: , ', , ' p i t i p i t idle t i K P K K = +? ??????????????????? (5-12) where , p i tK represents the competition factor for pedestrian iat time t , and ,idle tK is the hesitation factor of these pedestrians. 112 Vehicle-Vehicle conflict Since the speed of a vehicle during one time interval exceeds one cell per time step, potential movements for all cells to the target position should be checked to see if any other vehicle can use one of these cells towards its target position. Once all potentially conflicting vehicles have been identified, one can adopt a similar approach as described previously to model the pedestrian-pedestrian conflict. For example, in Figure 10, three vehicles are in a potential conflict, and the probability of the i -th vehicle to win is , ', , ' v i t i v i t idle t i K P K K = +? ??????????????????? (5-13) where , v i tK represents the competition factor for vehicle i at time t , and ,idle tK represents the hesitation factor of these vehicles. Pedestrian-Vehicle conflict For each vehicle in the simulation process, one needs to check whether there is any conflict with pedestrians along its trajectory. Using the same notion for resolving the conflict, one can compute the probability of a vehicle moving along all pedestrian cells in its trajectory one at a time. For example, the vehicle?s trajectory in Figure 5-10 includes two vehicle cells in the bold borders. The first bold vehicle cell overlaps with four pedestrian cells, and two of these are also the target cells for two pedestrians, respectively. Thus, the vehicle is in conflict with two pedestrians. Similarly, the vehicle is also in conflict with another pedestrian in the second cell. In the proposed simulation procedure, the 113 vehicle has to compete with pedestrian cells one by one in sequence. In the example above, the vehicle will first compete with the two pedestrians in the first cell, and then go on to the second cell if it wins. For a given cell, its winning probability of moving forward, iP , can be calculated as: , , , , v i t i v p i t j t idle t j K P K K K = + +? ????????????????? (5-14) where , p i tK represents the competition factor for pedestrian iat time t, , v i tK represents the competition factor for vehicle iat time tand ,idle tK represents the hesitation factor. 1, p t? 2, p t? 3, p t? 1, v t? 3, v t? 2, v t? 1, p t? 2, p t? 3, p t? 1, v t? Figure 5-10 Examples of potential conflicts 5.6. Comparison with existing simulation programs Before the calibration and validation procedure, we first compare the vehicle simulation in our model with the commercial simulation software TRANSMODELER to show the fidelity of our model in simulating the vehicles. The intersection in Figure 5-11 is used for both models to show that our proposed model can replicate results close to those of TRANSMODELER for vehicle-only simulation. Note that since there are no potential conflicts under the signal controller, there is no need for the parameters used to resolve the conflicts. The way-finding parameters are 114 set to force vehicles to strictly follow the traffic lights and look for the closest path to their destination. Three levels of demands are listed in Table 5-1 and the signal timing plan in Figure 5-11 is used for both simulation models. 1 2 3 4 Figure 5-11 layout of the intersection 115 Table 5-1 Demand settings Light demand (vph) From/To 1 2 3 4 1 0 200 0 40 2 200 0 40 3 40 0 0 300 4 0 40 300 0 Medium demand (vph) From/To 1 2 3 4 1 0 800 0 100 2 800 0 100 3 100 0 0 1200 4 0 100 1200 0 Heavy demand (vph) From/To 1 2 3 4 1 0 1000 0 1500 2 1000 0 150 3 1500 0 0 1500 4 0 150 1500 0 116 Figure 5-12 Signal timing plan for the intersection Table 5-2 shows the simulation results for these two programs, including different movements and levels of demand.. A paired t-test is conducted to compare the delays generated from these two simulations programs under each scenario. The results of the t-tests in Table 5-3 reflect that there are no significant differences in time- dependent delays between these two models. This result shows that our proposed model can replicate the traffic condition with the same fidelity as the existing tool for vehicle simulation. 117 Table 5-2 Comparison between the delay (s) output for every scenario Low Demand EWT EWL NST NSL Time Trans Mix Trans Mix Trans Mix Trans Mix 5 31 28 24 32 23 25 67 61 10 30 31 34 41 29 26 64 61 15 23 27 69 53 24 23 47 58 20 32 30 48 44 26 24 46 54 25 33 28 38 40 25 26 67 60 30 28 29 17 28 28 27 53 57 35 30 33 35 30 22 25 72 66 40 29 34 42 34 29 28 23 48 45 29 26 38 32 27 29 47 49 50 23 25 54 45 28 24 27 31 55 23 26 45 42 23 24 33 39 60 19 24 61 54 28 26 36 35 Medium Demand EWT EWL NST NSL Time Trans Mix Trans Mix Trans Mix Trans Mix 5 31 34 65 74 33 32 59 65 10 31 30 57 68 32 31 79 73 15 28 35 31 41 33 30 99 86 20 30 36 60 50 32 32 50 67 25 33 27 49 48 32 33 49 54 30 31 40 78 69 33 34 88 80 35 43 32 117 85 32 31 79 70 40 32 40 49 58 31 35 73 79 45 29 38 83 86 33 29 41 51 50 45 42 98 91 33 28 61 58 55 28 30 55 72 31 34 53 57 60 33 33 49 62 31 35 59 55 High Demand EWT EWL NST NSL Time Trans Mix Trans Mix Trans Mix Trans Mix 5 33 44 53 67 38 49 127 83 10 77 69 151 134 90 63 314 203 15 88 74 83 126 141 101 428 386 20 108 126 205 164 182 152 649 534 25 221 214 305 236 212 246 798 705 30 282 275 362 309 249 228 813 897 35 366 323 448 387 292 344 961 1043 40 391 381 364 421 340 389 1010 1058 45 372 394 401 443 384 362 1182 1108 50 385 403 452 465 423 400 1337 1230 55 414 425 463 487 475 435 1473 1589 60 413 434 432 504 530 441 1626 1571 118 Table 5-3 Paired t-test results for every scenario Demand Movement p-value 95% threshold Significance Low Demand EWT 0.37 2.19 Not significant EWL 0.30 Not significant NST 0.52 Not significant NSL 0.26 Not significant Medium Demand EWT 0.32 Not significant EWL 0.79 Not significant NST 0.84 Not significant NSL 0.87 Not significant High Demand EWT 0.86 Not significant EWL 0.90 Not significant NST 0.32 Not significant NSL 0.31 Not significant 5.7. Comparison without considering pedestrians VISSIM can model pedestrian movements at walking areas, stairs and ramps, and it can also model the street-crossing behavior of pedestrians on the crosswalks in mid-block or at intersections. TRANSMODELER does not have a separate module for pedestrian simulation although it can define crosswalks and the crossing volumes to simulate the crossing pedestrians? impact on the vehicle flows. None of the above tools can simulate the pedestrian-vehicle interactions at the intersection area where both can move in arbitrary directions and be in conflict at any location. To illustrate the need to account for vehicle-pedestrian interaction in simulating a mixed-flow network, we apply our model to the road network between an example network from the entrance gate on US1 and the Stamp Union of the University of Maryland, College Park (See Figure 5-13). The vehicle and pedestrian demands are listed in Table 5-4, where the behavior of pedestrians and driver types is assumed to follow that in Figure 5-14. 119 Figure 5-13 The road network between the gate and Stamp Union Figure 5-14 The distribution of different driver behaviors 120 Table 5-4 The vehicle and pedestrian demand Origin Destination Demand Pedestrians PO1 PD1 200 ped/hour PD2 200 ped/hour PO2 PD1 200 ped/hour PD2 200 ped/hour PO3 PD1 200 ped/hour PD2 200 ped/hour PO4 PD1 200 ped/hour PD2 200 ped/hour Vehicles VO1 VD1 300 veh/hour VO2 VD1 300 veh/hour VO3 VD1 300 veh/hour The analysis results presented hereafter are based on the following two simulation experiments: (1) One hour simulation with our proposed mixed-flow model; and (2) One hour vehicle simulation using TRANSMODELER The average measures of effectiveness over ten replications with these two simulation methods are listed in Table 5-5. As expected, by considering all possible conflicts within a mixed-flow traffic system, both individuals and vehicles will experience much longer delays than those from simulation programs without adequately accounting for this vital issue. This overall system throughput under such a traffic system is likely to be overestimated with existing simulation models. 121 Table 5-5 Measures of Effectiveness of the Two Simulations Mixed-Flow Simulation Trans-modeler Pedestrians Vehicles Pedestrians Vehicles Total Throughput 927 421 0 852 Average Delay (s) 8.14 24.56 0 6.21 5.8. Calibration and Validation To ensure the effectiveness of the proposed model for simulating complex roadway traffic during evacuation, the remaining sections first demonstrate the model fidelity with field data and then illustrate the calibration procedure for a target application. Due to the lack of field traffic data collected from a real-world evacuation, we use the data collected from the videos for a congested mixed-flow intersection in China for calibration. The procedure used to calibrate the mixed-flow simulation consists of the following steps: simulation model set-up, field data collection, MOE (Measure of Effectiveness) identification, sensitivity analysis, and selection of parameters for calibration. Figure 5-15 shows the flowchart of the entire process. 122 Figure 5-15 Overall calibration and validation procedure 5.8.1. Data collection This study selects the test site at a congested mixed-flow intersection in China. The intersection is located at the crossing of the Jiang Nan West Road and the Jiang Nan Middle Avenue in Guangzhou city of the Guangdong province. A twenty-minute video is collected from 10:00 a.m. to 10:20 a.m., covering the vehicle and pedestrian movements at that intersection. The first fifteen minutes are used for calibration of the simulation parameters to minimize the differences in performance measures between the field data and simulation results. The remaining data of five minutes are reserved for testing whether the parameters estimated from the calibration process are sufficiently accurate to replicate the observed traffic conditions. 123 Figure 5-16 (a) shows the network layout of the intersection. Figures 5-16 (b) and 5-16 (c) show the CA networks for the pedestrians and vehicles, respectively. The following traffic condition and control information are extracted from the video: ? Pre-timed signal phasing and timing plan; ? Free-moving speeds for pedestrians; ? Free-flow speeds for vehicles; ? Time-dependent counts of different pedestrian movements; ? Time-dependent counts of different vehicle movements; ? Travel time for each pedestrian movement; and ? Travel time for each vehicle movement (a) (b) (c) Figure 5-16 The layout of the data collection site Figure 5-17 shows the signal phasing and timing plan for the field site that has an exclusive walking phase for pedestrian safety. Figure 5-17 The signal plan for the intersection 124 Figure 5-18 (a) and (b) show the distributions for the pedestrian and vehicle free- moving speeds, respectively. (a) Pedestrian (b) Vehicle Figure 5-18 The free-moving speed distributions Figure 5-19 (a) and (b) shows the cumulative counts of pedestrian and vehicle movements, respectively. Each curve represents a particular movement. For example, the ?ac? and ?12? represent the pedestrian movement from a to c and the vehicle movement from 1 to 2, respectively. (a) Pedestrian movements (b) Vehicle movements Figure 5-19 The cumulative counts for pedestrian and vehicle movements Figure 5-20 (a) and (b) shows the delay distributions for each pedestrian and vehicle movement, respectively. 125 (a) (b) Figure 5-20 The delay distributions for pedestrian and vehicle movements 5.8.2. Key parameters for calibration Due to the nature of the test site, the delays for each O-D pedestrian and each vehicle movement are used as the measures of effectiveness to evaluate the difference between the simulated and the observed results. The simulation will generate delay for each simulated individual for comparison with the field data. 0 10 20 30 40 50 60 Pe rc en ta ge (% ) Delay Time (s) ac ad ca cd da dc 0 5 10 15 20 25 30 0~10 10~20 20~30 30~40 40~50 50~60 60~70 Pe rc en ta ge (% ) Delay Times (s) 12 13 14 21 31 126 The input parameters for the mixed-flow simulation can be divided into two categories: uncontrollable parameters and tunable parameters. Uncontrollable input parameters include roadway geometry, intersection layout, traffic counts, signal timing plans and etc. Tunable input parameters, representing embedded individual behaviors in the proposed simulation model, include: ? Weight of the distance floor field for vehicles: veh distw ? Weight of the distance floor field for pedestrians: ped distw ? Weight of the direction floor field for vehicles: veh dirw ? Weight of the direction floor field for pedestrians: ped dirw ? Weight of the signal floor field for vehicles: veh sigw ? Weight of the signal floor field for pedestrians: ped sigw ? Initial aggressiveness for vehicles: vehk ? Initial aggressiveness for pedestrians: pedk ? Hesitation factor: hesk ? Patience factor for vehicles: veh? ? Patience factor for pedestrians: ped? ? Cost factor for vehicles: veh? ? Cost factor for pedestrians: ped? 5.8.3. Selection of key parameters with sensitivity analysis 127 The purpose of the task is to evaluate the sensitivity of simulation results with respect to each parameter, and thus identify the set of most critical parameters for necessary calibration. The analysis includes the following steps: (1) Define the target parameters and their values at different levels. In this study, we limit the abovementioned 12 parameters in the range between 0 and 1 with the levels of 0.01 for the lower, 0.50 for the middle and 0.99 for the upper level. (2) Pick a proper sampling method to generate sample sets for calibration. Since a full factorial design for all parameters needs to run as many as 123 531441= scenarios, the Latin Hypercube Sampling was employed to generate a total of 1000 scenarios. (3) Plot the scatter of the average delay by each simulation versus the variation of each parameter in the evaluation set. Figure 5-21 shows the impact of different signal floor values on the resulting delays generated from the simulation. (4) Perform a statistical test to identify the most sensitive parameters. Table 5-6 shows the ANOVA and F-test results, including the significance of each parameter and its allocations of variance. Notably, all the parameters in the set are significant in influencing the simulation?s results. However, some parameters accounts for more variance of the simulation output, e.g., the signal floor field weights, the distance floor field weights, and the hesitation factor. 128 Figure 5-21 Delay plots for levels of signal floor field weight Table 5-6 ANOVA test result on the individual tunable parameters Parameter F-level F-Level (0.95) Conclusion Allocation of Variance (%) veh distw 1485.93 19.5 Sensitive 7.31 ped distw 1665.21 Sensitive 8.20 veh dirw 836.36 Sensitive 4.12 ped dirw 648.53 Sensitive 3.21 veh sigw 2748.65 Sensitive 13.53 ped sigw 3422.58 Sensitive 16.86 vehk 1398.67 Sensitive 6.89 pedk 1749.32 Sensitive 8.62 hesk 1898.05 Sensitive 9.35 veh? 1319.86 Sensitive 6.51 129 ped? 1561.46 Sensitive 7.69 veh? 383.67 Sensitive 1.89 ped? 369.15 Sensitive 1.76 Unexplained 8.29 5.8.4. Calibration algorithm The calibration procedure aims to find the proper parameter values that allow the model to best replicate the field data. In that sense, the tunable parameters can be regarded as decision variables and the calibration is targeting to find a solution of a constrained minimization problem where the objective function shows the deviation of the simulated output from the observed measures of performance. This study adopts the root mean square percentage error (RMSPE), defined below, to represent the objective function: 2 2( ) ( ) obs sim obs sim p p v v obs obs p P v Vp v D p v D D D D TT D RMSPE N N ? ? ? ? + = + ? ? ??????? (5-15) Where; pN : the number of observed pedestrians vN : the number of observed vehicles obs pD : the observed delay time for pedestrian p obs vD : the observed delay time for vehicle v sim pD : the simulated delay time for pedestrian p 130 sim vD : the simulated delay time for vehicle v Besides the RMSPE, the Theil?s inequality coefficient (Pindyck and Rubinfeld, 1998) widely used in econometrics was also adopted to test the fitness of the simulation. The Theil?s inequality coefficient is in the following form: 2 1 2 2 1 1 1 ( ) 1 1( ) ( ) N s o i i i N N s o i i i i x x NU x x N N = = = ? = + ? ? ? ????????????? (5-16) 0U = indicates a perfect match and 1U = indicates the worst performance of the simulation model. The Theil coefficient also measures the RMSE in relative terms. The constraint of the optimization problem is the simulation function, which takes the parameters as inputs and generates the measures of performance as the outputs. It can be expressed as: ( , , , , , , , , , )sim veh ped veh ped veh ped veh ped veh pedp dist dist dir dir sig sigD F w w w w w w k k ? ?= ????? (5-17) 0 , , , , , , , , , 1veh ped veh ped veh ped veh ped veh peddist dist dir dir sig sigw w w w w w k k ? ?? ? ??????.. (5-18) As the simulation model is nonlinear and non-convex, there are three main difficulties in solving the optimization problem: ? There are potentially several optimal solutions; ? The quality of these local solutions varies substantially; and ? Existing optimization techniques can not guarantee finding the global optimal solution. 131 There is a large body of heuristic optimization techniques that can solve the above problem efficiently although none promises a global optimum. Genetic algorithm (GA) is one of those based on the mechanics of natural selection and evolution (Goldberg and Beckman, 1989). It has also been employed for calibration of simulation parameters with promising results (Park and Hongtu, 2005). Before directly calibrating parameters with field data, the laboratory test is an important step to justify the calibration procedures, such as the choice of the performance measure, the objective function, and the optimization algorithm. The laboratory procedures begin with setting a target parameter value and running multiple simulation runs. The simulation outputs are then collected and considered as real data coming from the virtual detectors. Parameters are then changed to random values and the calibration procedure is performed to test its ability to find the initial values set for these target parameters. The laboratory data have eliminated all uncertainties that may exist in the field data. Ciuffo et al. (2007) pointed out that the laboratory test is rather useful in focusing exclusively on the effect of the selected algorithm and parameters. In this study, the steps for carrying out the laboratory test are as follows: 1) Set the parameters in the simulation model with the initial values shown in Table 2 (can be any values within reasonable range); 2) Use the same demand pattern collected from the field (can use any other reasonable demand patterns) and run the simulation; 132 3) Compute the delay for each individual what? Missing word here and treat them as the virtual observed data; 4) Change the parameters to random initial values and perform the calibration based on the virtual observed data; 5) Compare the calibrated parameter values with the initial set; and 6) Compare the calibrated simulation results with the virtual observed data. Table 5-7 also shows the calibrated results from the laboratory test, including each parameter?s initial and final calibrated values. Table 5-18 shows the RMSE, RMSPE and Theil?s coefficient, based on the comparison between the simulated and the virtually collected delays for each pedestrian and vehicle movement. The RMSPEs and Theil?s coefficients for all movements are close to 0, indicating the effectiveness of the calibration. Aside from that, we have further computed the confidence interval band for the estimated delay by using Equation 5-19. Figures 5-22 (a)-(d) show the confidence bands for the delay associated with pedestrian movement ac, pedestrian movement ad, vehicle movement 12 and vehicle movement 13, respectively. Noticeably, all delays collected with simulation detectors lie within their confidence bands. / 2,2 2 Pr{ } 1 ( ) ( ) obs sim nobs sim obs sim D D t s s n n ? ? ? < > ? + ?????????????? (5-19) where 0.05? = 133 Table 5-7 The target, initial and calibrated parameter values Parameter Target value Initial value Calibrated value veh distw 0.20 0.32 0.28 ped distw 0.50 0.45 0.40 veh dirw (fix) 0.10 0.10 0.10 ped dirw (fix) 0.10 0.10 0.10 veh sigw 0.95 0.68 0.81 ped sigw 0.50 0.39 0.69 vehk (fix) 0.10 0.10 0.10 pedk 0.30 0.52 0.18 hesk 0.50 0.37 0.44 veh? 0.30 0.50 0.54 ped? 0.40 0.33 0.67 veh? 0.20 0.12 0.29 ped? (fix) 0.10 0.10 0.10 134 Table 5-8 The delay comparisons between the simulated and observed data From To RMSE RMSPE Theil?s Inequality Coefficient Pedestrians a c 3.19 0.048 0.021 a d 4.20 0.068 0.032 c a 4.17 0.063 0.024 c d 3.44 0.059 0.043 d a 3.63 0.038 0.019 d c 4.33 0.046 0.021 Vehicles 1 2 4.71 0.061 0.044 1 3 5.01 0.085 0.032 1 4 6.22 0.086 0.046 2 1 5.68 0.074 0.039 3 1 6.11 0.069 0.054 (a) Pedestrian movement ac (b) Pedestrian movement ad 135 (c) Vehicle movement 12 (d) Vehicle movement 13 Figure 5-22 The confidence intervals of the delays 5.8.5. Model calibration and validation with real-world data Based on the procedures developed for the laboratory test, we have further performed the simulation parameter calibration with the collected field data. Figure 5- 23 shows the convergence of the GA-based calibration results after 150 generations and a population size of 20. Other parameter settings for the GA algorithm include a crossover rate of 0.8 and a mutation rate of 0.05. The fitness values decrease as the number of generations increases, which indicates that the simulation results are closer to the field data. All simulation parameters under the proposed calibration procedures reach a steady state after the 60th generation. 136 Figure 5-23 The convergence of the GA algorithm Figure 5-24 (a)-(d) shows the confidence bands of delays for selected individual movements, indicating that field measured delays are beyond the boundaries of the confidence band. This figure reflects that our simulation results do not match with the observed field data. (a) Pedestrian movement ac (b) Pedestrian movement ad 137 (c) Vehicle movement 12 (d) Vehicle movement 13 Figure 5-24 Delay confidence bands To identify the cause of such inconsistencies, we have scrutinized the video and the calibration procedure again finding that the inconsistencies are due to the behavioral discrepancies in response to the traffic signal. The field data show that the pedestrian crowd can be divided in two approximately equal groups: one obeying and the other ignoring the signal?s instructions. Thus, it is necessary to estimate the signal floor field weights for each group rather than to view them as one population. Thus, we have replaced the signal floor field weight for pedestrians ped sigw with two weights, _ped obey sigw and _ped violate sigw , which indicate the weights for those who obey and those who violate the traffic rules, respectively. The final calibrated parameters are listed in Table 5-9: Table 5-9 The calibrated parameter values Parameter Calibrated Value veh distw 0.28 ped distw 0.30 138 veh dirw 0.10 ped dirw 0.10 veh sigw 0.93 _ped obey sigw 0.86 _ped violate sigw 0.07 vehk 0.10 pedk 0.21 hesk 0.04 veh? 0.01 ped? 0.02 veh? 0.05 ped? 0.10 Figure 5-25 (a)-(d) shows the results for individual pedestrian and vehicle movements from the re-calibrated simulation. The collected delays for each individual movement fall within its confidence boundaries, indicating a match between the calibrated and actual traffic conditions. 139 (a) Pedestrian movement ac (b) Pedestrian movement ad (c) Vehicle movement 12 (d) Vehicle movement 13 Figure 5-25 Re-calibrated delay confidence bands After the calibration step, the last phase of the application procedure is to test the model?s ability to reproduce a new set of field data. The simulation model with recalibrated parameters was applied to simulate the whole twenty minutes for the target intersection, and results obtained from the last five minutes were used for the model validation. Table 5-10 shows the comparison between the average of the simulation results and the validation data. The small values for both RMSPE and Theil?s inequality confirm the reliability of the calibrated parameters and also reflect that our proposed models with proper calibration procedures can realistically replicate the complex pedestrian-vehicle mixed-flows in either congested downtown intersections or in evacuation networks. Table 5-10 Comparisons between the simulation result and the validation data From To RMSE RMSPE Theil?s Inequality Coefficient Pedestrians a c 6.19 0.091 0.045 a d 8.20 0.114 0.063 140 c a 6.17 0.083 0.042 c d 8.44 0.095 0.048 d a 8.63 0.112 0.056 d c 7.33 0.079 0.037 Vehicles 1 2 4.71 0.061 0.048 1 3 5.01 0.085 0.044 1 4 6.22 0.086 0.049 2 1 5.68 0.074 0.052 3 1 6.11 0.069 0.033 5.9. Summary This section has first presented a mixed CA-based model to simulate the mixed vehicle-pedestrian traffic movements. The proposed model divides the space into discrete cells and develops a set of rules to represent the local and global interactions between individual vehicles and pedestrians. The floor field concept is applied to model an individual?s way-finding process toward his/her current target cell. The proposed method can dynamically update vehicle and pedestrian paths with the minimum computing load. The concept of a competition factor is put forward in this model to reflect various conflicts among pedestrians and vehicles during the evacuation process. A linear function of waiting time is used to model the aggressiveness of individuals in the driving or walking mode. Also, unlike most previous CA models, the proposed model has accounted for the potential diagonal movements by pedestrians in an evacuation network, more realistically reflecting 141 various movements of the mixed pedestrian-vehicle traffic flows. The paper then presented the procedures proposed to calibrate its underlying behavioral parameters for the simulation model to replicate a real world scenario. The individual delay is used as the measure of effectiveness to evaluate the discrepancy between the output produced by the simulation and the field data. The proposed calibration procedure is based on an optimization formulation with its objective of minimizing the deviation of the simulated output from the observed measures of performance using a GA- based solution algorithm. The proposed calibration procedure has been tested on a typical mixed-flow intersection at Guangzhou, China for the developed mixed pedestrian-vehicle simulation model. The sensitivity analysis with field data shows that all behavioral parameters embedded in the mixed flow simulation model are significant, and with different degrees of contribution to the output variance. The first calibration attempt on the collected data reveals the need to divide the pedestrians into two categories, reflecting two different behavioral patterns in response to signal instructions. The second calibration with two sets of parameters achieves a successful match between the field data and the simulated results, confirming the fidelity of the proposed mixed- flow simulation model for use at intersections with heavy pedestrian volume, such as in a downtown area during peak hours or during evacuation. Our future research will focus on integrating the proposed mixed-flow simulation model with a multi-modal evacuation system to evaluate the efficiency of any candidate emergency evacuation plan. Extensions of the mixed-flow simulation model to other modes such as transit vehicles and bikes may also be included. 142 143 Chapter 6: Conclusions and Recommendations 6.1. Research Summary This study presents a multi-modal system to assist the transportation management and operational authorities in making proper evacuation plans under an emergency. Based on the typical two-stage evacuation concept, the evacuation process is generally divided into two steps: multi-modal evacuation within the impact zone and single vehicle-flow evacuation beyond the control boundaries. The study focuses on the major mixed-flow issues at the first stage within the impact zone, intending to address the following two critical concerns: what control strategies are to be implemented and what would be the resulting traffic condition. Hence, the study comprises two core models: the mixed-flow optimization model and the mixed-flow simulation model. The former generates the optimal control strategies, including the optimal time-dependent flow distributions over the entire network and the recommended intersection timing control. The latter offers a tool to project the evolution of traffic conditions such as delays, travel times and speeds, and allows the user to identify the potential bottlenecks and evaluate the effectiveness of various candidate plans. Chapter 2 has provided a comprehensive review of the relevant studies on models and methodologies associated with emergency evacuation. The vast amount of evacuation studies is divided by categories of the disaster nature, optimization for vehicle flows, optimization for pedestrian flows, simulation for vehicle movements, and simulation for pedestrian movements. Not only has the review identified the lack of work on how to represent the interactions between the mixed pedestrian-vehicle 144 flows in the literature, but it has also discovered the deficiencies of existing operational models in coordinating the two types of flows. In response to the identified needs, Chapter 3 introduced the proposed multi- modal evacuation system designed for the Baltimore metropolitan area. The system is designed to provide responsible agencies with the best control plan and simulated road conditions under an evacuation. The system framework consists of eight essential modules among which the mixed-flow optimization and simulation modules are the two most critical ones and constitute the core of this study. The mathematical model used for the multi-modal optimization is detailed in Chapter 4. It began with constructing a mixed-flow network and designing a timing phase for mixed-flow intersections, which serve as the basis for capturing and coordinating the interactions between the two types of flows. Then, the objective and the constraints are formulated as an integer-linear programming problem. In order to improve the computing speed of the obvious NP-hard formulation, a revised Bender?s Decomposition algorithm is proposed thereafter by decomposing the formulation into two problems: a master problem and a sub-problem and solving the relaxed versions of the two problems iteratively until a satisfactory convergence is reached. An illustrative example has proved the model?s effectiveness in capturing the interactions of these two types of flows and preventing deficiencies if adopting the conventional methods. The experimental results also confirm that our revised algorithm outperforms the alternative algorithms with regard to the computational speed. 145 Chapter 5 has detailed the simulation model developed to replicate the real-world traffic conditions under the mixed pedestrian-vehicle flow environment. The proposed model is based on the notion of Cellular Automaton, which is widely used in complexity theories. The model first defines two layers of lattice for the pedestrians and vehicles and then adopts the floor field concept to reflect the influential factors in the way-finding behaviors, including distances, directions and signal indications. The conflicts between evacuees and vehicles are resolved with the notion of competition, and the probability of winning the competition is directly related to an individual?s aggressiveness and patience. The model has been compared with the existing simulation products to show its reliability in terms of producing a similar level of traffic conditions. The model has also been calibrated using a video captured from a typical mixed-flow intersection in Guangzhou, China. With an extensive calibration process, this study has showed that the proposed mixed-flow simulation model can realistically replicate field mixed-traffic conditions as long as its key parameters are properly calibrated. This study has led to the following conclusions: 1. The proposed mixed-flow models for optimization and simulation fill the research gap in the existing literature. The models addressed the important issues of coordinating the two heterogeneous traffic flows and simulating the complex interaction between them; 2. The two-stage evacuation process is rather suitable for the regional-wide evacuations at urban areas. By focusing on the impact areas closer to the 146 incident location rather than on the whole network, one can address the mixed-flow issues without sacrificing too much computation effort. 3. The proposed mixed-flow optimization model modeled the interactions between the pedestrian and vehicle flows by introducing the network connection components and expanding the signal phases. The network is expanded to formulate the objective of maximizing the total evacuee throughput. These model improvements are capable of reflecting the real traffic conditions and generating better control plans, as proved in the numerical example. 4. The revised Bender?s Decomposition algorithm can largely decrease the computational time compared with the conventional BD and other algorithms. In addition, it allows the user to balance the computation and the accuracy by setting the optimality condition. 5. The mixed-flow simulation model is capable of simulating the complex interactions between individual pedestrians and vehicles at the intersection areas. The model parameters can also reflect the individual?s real-way finding behaviors and their reactions facing potential conflicts. By comparing the proposed model with the existing simulation tools, our model can produce similar traffic conditions under different scenarios. The mixed-flow simulation result is also more realistic compared with the models without considering the pedestrian-vehicle interaction. 6. The calibration and validation experiment shows that the mixed-flow simulation model can be adapted to particular locations by fitting the 147 corresponding behavioral parameters. The calibration procedure can also help to identify the behavioral patterns at different field sites. The validation shows the simulation model can replicate the real-world mixed-flow traffic conditions collected in the field. 6.2. Potential Future Research Mixed-flow research has emerged as a critical issue in the traffic network community. Despite the progress made in this study, much remains to be done to address the complex, mixed-flow related issues in emergency evacuation. Some of the necessary extensions are listed below: 1. Real-time emergency operations: This study is for planning application for emergency evacuation. Although it is of vital importance to be well prepared for any potential emergencies, the incidents are always unpredictable and the evacuee behaviors do not always fit the controls under such scenarios. Thus, it is also critical to develop a model that is capable of adjusting the plans according to the feedback during the ongoing evacuation process, such as detector data from sensors and on-road camera videos. The model should be able to run in a real-time manner, which imposes a lot of restrictions on the computation efficiency issues. 2. Micro-level optimization: The optimization model in this study is on the macro-flow level. However, it may not be accurate since the pedestrian- vehicle conflict under the micro-level cannot be reflected. For example, it is not possible to model the diagonal crossing phenomenon in the link-node network. Thus, a potential working direction is to embed the existing mixed- 148 flow simulation model into the optimization process to reflect all micro-level behaviors. 3. Stochastic optimization: Despite the faster running speed compared to stochastic models, the deterministic model is sometimes criticized for its inflexibility to represent the uncertainties in the real-world, for example, the number and locations of the evacuees, the number of drivers and transit- dependent pedestrians, the road capacity, the intended destinations for evacuees, the travel time, the behavior of the evacuees and etc. Although the effectiveness of a stochastic model can?t be asserted, it is generally believed to be more flexible in capturing real-world uncertainties. 4. Parallel implementation of the simulation: The notion to divide the road and walking facilities into cells increases the network size and, in turn, reduces the computational speed. However, the local-rule structure based on the CA framework also allows the parallel processing to be efficient and possible. Previous studies on the parallel implementations of vehicle traffic simulations based on Cellular Automata (e.g., Dupuis and Chopar, 1998; Wahle, 2001) have obtained rather promising results in terms of the computation efficiency. With the recent hardware advancement, such as the increase in CPU cores and the emergence of GPU programming, the computational speed of the mixed-flow simulation model can be greatly improved if the simulation is carefully programmed to best use the multi- processing architecture. 149 References: Abdelghany A., Abdelghany K., Mahmassani H. and Alhalabi W., Modeling the Evacuation of Large-Scale Crowded Pedestrian Facilities, Transportation Research Record, No. 2198, pp. 152-160, 2010. Antonini G., Bierlaire M., Discrete Choice Models of Pedestrian Walking Behavior, Transportation Research Part B, Vol. 40, pp. 667-687, 2006. Aaron E., After September 11, 2011: How Transit Agencies Prepare for the Threat of Terrorism, Transportation Research Record, No. 1927, pp. 92-100, 2005. Afshar A. M and Haghani A, Heuristic Framework for Optimizing Hurricane Evacuation Operations, Transportation Research Record, No. 2089, pp. 9-17, 2008. Balakrishna R, Wen Y, Ben-Akiva M and Antoniou C, Simulation-Based Framework for Transportation Network Management in Emergencies, Transportation Research Record, No. 2041, pp. 80-88, 2008. Ballard A. J., Traffic Operations for Hurricane Evacuation, Transportation Research Record, No. 2035, pp. 195-204, 2007. Barrett B, Ran B and Pillai R, Developing a Dynamic Traffic Management Modeling Framework for Hurricane Evacuation, in Transportation Research Record, No. 1733, pp. 115-121, 2000. 150 Beckers E. W., Flacke J. and Retsios B., Investigating the Effect of Different Pre- evacuation Behavior and Exit Choice Strategies Using Agent-based Modeling, Procedia Engineering, Vol. 3, pp. 23-35, 2010. Benders J. F, Partitioning Procedures for Solving Mixed-variables Programming Problems, Numerische Mathematik, 4, pp. 238-252, 1962 Boenisch C., and Kretz T., Simulation of Pedestrians Crossing a Street. Transport, pp. 1-9, Retrieved from http://arxiv.org/abs/0911.2902, 2009. Boyce D. E. and Pandy B., Analysis of Traffic Delays - Des Plaines River Watershed Study from Flooding, Final Report, U.S. Army Corps of Engineers, Chicago District: Chicago, Illinois, 2002. Brown C., White W., Slyke C., and Benson J. D., Development of a Strategic Hurricane Evacuation?Dynamic Traffic Assignment, Model for the Houston, Texas, Region, Transportation Research Record: Journal of the Transportation Research Board, No. 2137, Transportation Research Board of the National Academies, Washington, D.C., pp. 46?53, 2009. Burstedde C., Klauck K., Schadschneider A., Zittartz J., Simulation of pedestrian dynamics using a 2-dimensional cellular automaton. Physica A, Vol. 295, pp. 507- 525, 2001. Cakici N. and Oven V. A., Modeling the Evacuation of a High-rise Office Building in Istanbul, Fire Safety Journal, Vol. 44, pp. 1-15, 2009. 151 Cameron G. and Duncan G., Paramics: Parallel Microscopic Simulation of Road Traffic, Journal of Supercomputing, Vol. 10, pp. 25-53, 1996. Camille N. Y., Antiterrorism Security and Surface Transportation Systems: Review of Case Studies and Current Tactics, Transportation Research Record, No. 1622, pp. 9-17, 2003. Cepolina E. M., Phased Evacuation: An Optimization Model Which Takes into Account the Capacity Drop Phenomenon in Pedestrian Flows, Fire Safety Journal, Vol. 44, pp. 532-544, 2009. Chalmet L. G. and Francis R. L., Network Models for Building Evacuation, Management Science, Volume 28, No 1, pp. 86-104, January 1982. Cheng X., Zhang H., Xie Q., Zhou Y., Zhang H. and Zhang C., Study of Announced Evacuation Drill from a Retail Store, Building and Environment, Vol. 44, pp. 864- 870, 2009. Chen X and Zhan F.B., Agent-based modeling and simulation of urban evacuation: relative effectiveness of simultaneous and staged evacuation strategies, Journal of the Operational Research Society, Vol. 59, pp. 25-33, 2008. Chien S. and Korikanthimath V., Analysis and Modeling of Simultaneous and Staged Emergency Evacuations, Journal of Transportation Engineering, Vol. 133, No. 3, pp. 190-197, March 2007 152 Chiu Y. C. and Mirchandani P. B., Online Behavior-Robust Feedback Information Routing Strategy for Mass Evacuation, IEEE Transactions on Intelligent Transportation Systems, Vol. 9, No. 2, pp. 264-274, June 2008. Chiu Y. C., Zheng H., Villalobos J. A., Peacock W. and Henk R., Evaluating Regional Contra-Flow and Phased Evacuation Strategies for Texas Using a Large- Scale Dynamic Traffic Simulation and Assignment Approach, Journal of Homeland Security and Emergency Management, Vol. 5, pp. 1-27, 2008. Chiu Y. C., Nava E., Zheng H. and Bustillos B., DynusT User?s Manual, 2009. Choi W., Network Flow Models of Building Evacuation Problems with Flow- Dependent Arc Capacities, Ph. D. Thesis, University of Florida, 1987. Choi W., Hamacher S., Tufekci S., Modeling of Building Evacuation Problems by Network Flows with Side Constraints, European Journal of Operational Research, Vol. 35, pp. 98-110, 1988. Chow W. K., Waiting Time for Evacuation in Crowded Areas, Building and Environment, Vol. 42, pp. 3757-3761, 2007. Chow W. K. and Ng C. M. Y., Waiting Time in Emergency Evacuation of Crowded Public Transport Terminals, Safety Science, Vol. 46, pp. 844-857, 2008. Ciuffo Biagio, Punzo Vincenzo and Torrieri Vincenzo, A Framework for the Calibration of Microscopic Traffic Flow Models, Presented at the 86th Transportation Research Board, 2007 153 Corps of Engineers (COE) and Southwest Florida Region Planning Council (SWFRPC), Lee County Florida Flood Emergency Evacuation Plan, Fla, 1979. Corps of Engineers (COE), A Hurricane Evacuation Computer Model for Southeast Louisiana, HURREVAC Version 6.0, Documentation and User?s Guide, Prepared for the Louisiana Department of Military Affairs Office of Emergency Preparedness, Baton Rouge, La, 1994. Cova T. J. and Johnson J. P., Microsimulation of Neighborhood Evacuations in the Urban Wildland Interface, Environment and Planning A, Vol. 34, pp. 2211-2229, 2002. Cova T. J and Johnson J. P, A Network Flow Model for Lane-based Evacuation Routing, Transportation Research Part A, Vol. 37, pp. 579-604, 2003. De Silva F. N. and Eglese R. W., Integrating Simulation Modeling and GIS: Spatial Decision Support Systems for Evacuation Planning, The Journal of the Operational Research Society, Vol. 51, No. 4, pp. 423-430, 2000. Dow K. and Cutter S. L., Emerging Hurricane Evacuation Issues: Hurricane Floyd and South Carolina, Natural Hazards Review, Vol. 3, No. 1, pp. 12-18, February 2002. Drager K.H., Lovas G.G. and Wiklund J., EVACSIM: a comprehensive evacuation simulation tool, in: Proceeding of the 1992 International Emergency Management and Engineering Conference, Florida, pp. 101-108, 1992. Dunning A. E. and Jennifer L. O., Train Wreck and Chlorine Spill in Graniteville, South Carolina, Transportation Research Record, No. 2009, pp. 130-135, 2007. 154 Dupuis A. and Chopard B., Parallel Simulation of Traffic in Geneva Using Cellular Automata, Scientific International Journal for Parallel and Distributed Computing, No. 1, Vol. 3, 1998 Ehrhardt J., Brown J., French S., RODOS: Decision-Making Suppport for Off-site Emergency Management after Nuclear Accidents, Kerntechnik, Vol. 62, pp. 122-128, 1997. Etschmaier M. M and Richardson R.J., Improving the Efficiency of Benders? Decomposition Algorithm for a Special Problem in Transportation, Technical Report No. 14, Department of Industrial Engineering, University of Pittsburg, May, 1973 Fang Z., Li Q. Q., Li Q. P., Han L. D. and Wang D., A Proposed Pedestrian Waiting- time Model for Improving Space-Time Use Efficiency in Stadium Evacuation Scenarios, Building and Environment, Vol. 46, pp. 1774-1784, 2011. Fang Z., Song W., Zhang J. and Wu H., Experiment and Modeling of Exit-Selecting Behaviors during a Building Evacuation, Physica A, Vol. 389, pp. 815-824, 2010. Fahy R. F., An Evacuation Model for High-rise Buildings, Proceedings of INTERFLAM - 6th International Fire Conference, London, pp. 519-528, 1993. FEMA, Application of the I-DYNEV System to Compute Estimates of Evacuation Travel Times at Nuclear Power Stations, Federal Emergency Management Agency Report 8, Washington D. C, 1984. Federal Highway Administration, NETSIM Implementation Package, FHWA-IP-80, January, 1980. 155 Florian M. Guerin G and Bushell G., The Engine Scheduling Problem in a Railway Network ? Part 1, Publication No. 89, Department of Information, University of Montreal, May, 1972 Ford L.R.; Fulkerson D.R., Maximal Flow through a Network, Canadian Journal of Mathematics, Vol. 8, pp.399-404, 1956. Francis R. L., A Simple Graphical Procedure to Estimate the Minimum Time to Evacuate a Building, Society of Fire Protection Engineers, Technology Report 1979-5, pp. 14, 1979. Francis R. L., A ?Uniformity Principle? for Evacuation Route Allocation, Journal of Research of National Bureau of Standards, Vol. 86, No. 5, pp. 509-513, September- October, 1981. Francis R. L., A Negative Exponential Solution to An Evacuation Problem, Research Report, No. 84-86, National Bureau of Standards, Center for Fire Research, October 1984a. Francis R. L. and Kisko T. M., Network Models for Building Evacuation: Development of Software System, Grant No. NB81NADA2057, 62p, 1984b. Francis R. L and Kisko T. M, EVACNET+: A Computer Program to Determine Optimal Building Evacuation Plans, Fire Safety, Vol. 9, pp. 211-220, 1985. Franzese O. and Han L., Traffic Modeling Framework for Hurricane Evacuation, Proceedings of 80th Annual Meeting, Transportation Research Board, Washington D. C, Paper No. 01-2591, 2001. 156 French S., Papamichail K. N., Ranyard D. C. and Smith J. Q., Design of a Decision Support System for Use in the Event of a Nuclear Emergency, in: F. Javier Giron, M. Lina Martinez (Eds.), Applied Decision Analysis, Kluwer Academic Publishers, Boston, pp. 2-18, 1998. Galea E. R. and Galparsoro J., EXODUS: An Evacuation Model for Mass Transport Vehicles, Fire Safety Journal, Vol. 22, pp. 41-66, 1994. Galea, E.R., Gwynne, S., Lawrenec, P.J., Filippidis, L., Blackshields, D., buildingEXODOUS V4.0 User Guide and Technical Manual, University of Greenwich, UK, 2004. Galea E. R., Sharp G., Lawrence P. J. and Holden R., Approximating the Evacuation of the World Trade Center North Tower Using Computer Simulation, Journal of Fire Protection Engineering, Vol. 18, pp. 85-115, 2008. Geoffrion A.M and Graves G.W., Multicommodity Distribution System Design by Benders? Decomposition, Management Science, Vol. 20, No. 5, pp. 822-844, January, 1974 Georgiadou P. S., Papazoglou I. A, Kiranoudis C. T and Markatos N. C, Modeling Emergency Evacuation for Major Hazard Industrial Sites, Reliability Engineering and System Safety, Vol. 92, pp. 1388-1402, 2007. Goldberg D. E. and Beckman R. J., Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Publising Co., Inc., Reading, Mass., 1989. 157 Guo R. Y. and Huang H. J., A Mobile Lattice Gas Model for Simulating Pedestrian Evacuation, Physica A, Vol. 387, pp. 580-586, 2008. Gwynne S., Galea E. R. and Owen M., A Review of the Methodologies Used in the Computer Simulation of Evacuation from the Built Environment, Building and Environment, Vol. 34, pp. 741-749, 1996. Gwynne S., Galea E. R., Owen M., Lawrence P. J. and Filippidis L., A Review of the Methodologies Used in the Computer Simulation of Evacuation from the Built Environment, Building and Environment, Vol. 34, pp. 741-749, 1999. Halpern J., A Generalized Dynamic Flows Problem, Networks, Volume 9, Issue 2, pp. 133-167, 1979. Hamacher H. W. and Tjandra S. A., Mathematical modeling of evacuation problems? a state of the art, in Pedestrian and Evacuation Dynamics, Springer, Berlin, pp. 227- 266, 2002. Hamza-Lup G. L., Hua K. A and Peng R., Leveraging E-Transportation in Real-time Traffic Evacuation Management, Electronic Commerce Research and Applications, Vol. 6, pp. 413-424, 2007. Han A. F., TEVACS?Decision Support System for Evacuation Planning in Taiwan, Journal of Transportation Engineering, Vol. 116, No. 6, pp. 821-830, Nov-Dec, 1990. Helbing D. and Molnar P., Social Force Model for Pedestrian Dynamics, Physical Review E, Volume 51, pp. 4282-4286, May, 1995. 158 Helbing D. and Farkas I., Freezing by Heating in a Driven Mesoscopic System, Physical Review Letters, Vol. 84, No. 6, pp. 1240-1243, February 2000. Helbing D., Isobe M., Nagatani T. and Takimoto K., Lattice Gas Simulation of Experimentally Studied Evacuation Dynamics, Physical Review E, Vol. 67, pp. 67-71, 2003. Helbing D. and Buzna L., Self-Organized Pedestrian Crowd Dynamics: Experiments, Simulations and Design Solutions, Transportation Science, Vol. 39, No.1, pp. 1-24, February 2005. Helbing D. and Jiang R., Analytical Investigation of Oscillations in Intersecting Flows of Pedestrian and Vehicle Traffic, Physical Review E, Vol. 72, pp. 046130, 2005. Helbing D. and Johansson A., Analytical Approach to Continuous and Intermittent Bottleneck Flows, Physical Review Letters, 97, pp. 168001, 2006 Hobeika A. G. and Jamei B., MASSVAC: A Model for Calculating Evacuation Times under Natural Disaster, in Proc. Conf. Computer Simulation in Emergency Planning, Society of Computer Simulation, La Jolla, CA, Vol. 15, No. 1, Jan 1985. Hobeika A. G., Radwan A. E. and Jamei B., Transportation Actions to Reduce Evacuation Times Under Hurricane/Flood Conditions: A Case Study of Virginia Beach City, Proceedings of the 64th Annual Meeting, Transportation Research Board, Washington D. C, 1985. 159 Hobeika A. G., Kim S. and Beckwith R. E., A Decision Support System for Developing Evacuation Plans around Nuclear Power Stations, Interfaces J., Vol. 24, No. 5, Sept/Oct, 1994. Hoogendoorn S. P., Bovy P. H. L., Pedestrian Route-Choice and Activity Scheduling Theory and Models, Transportation Research Part B, Vol. 38, pp. 169-190, 2004. Hoppe B., Tardos E. The Quickest Transshipment Problem, Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pp512-521, January 1995. Ishaque M. M., Noland R. B., Trade-offs between vehicular and pedestrian traffic using micro-simulation methods, Transport Policy, Vol. 14, pp. 124-138, 2007. Isobe M., Helbing D., Nagatani. T., Experiment, theory, and simulation of the evacuation of a room without visibility, Physical Review E, Vol. 69, 2004. Jeon G. Y., Kim J. Y, Hong W. H and Augenbroe G., Evacuation Performance of Individuals in Different Visibility Conditions, Building and Environment, Vol. 46, pp. 1094-1103, 2011. Jha M., Moore K. and Pashaie B., Emergency Evacuation Planning with Microscopic Traffic Simulation, Transportation Research Record, No. 1886, pp. 40?48, 2004. Jiang C. S., Li W., Hu C., Xiong Y., Ding H. and Chow W. K., Emergency Evacuation in Places for Public Entertainment in Mainland China, Building and Environment, Vol. 44, pp. 169-176, 2009. 160 Jiang C. S., Yuan F. and Chow W. K., Effects of Varying Two Key Parameters in Simulating Evacuation for Subway Stations in China, Safety Science, Vol. 48, pp. 445-451, 2010. Jiang R., Wu Q. S., Interaction between Vehicle and Pedestrians in a Narrow Channel, Physica A, Vol. 368, pp. 239-246, 2006a. Jiang R., Wu Q. S., The Moving Behavior of A Large Object in the Crowds in a Narrow Channel, Physica A, Vol. 364, pp. 457-463, 2006b. Kirchner A. and Schadschneider A., Simulation of Evacuation Processes Using a Bionics-Inspired Cellular Automaton Model for Pedestrian Dynamics, Physica A, Vol. 312, pp. 260-276, 2002. Kirchner A., Klupfel H., Nishinari K., Schadschneider A. and Schreckenberg M., Simulation of Competitive Egress Behavior: Comparison with Aircraft Evacuation Data, Physica A, Vol. 324, pp. 689-697, 2003. Kiosko T., Francis R. L. and Nobel C., EVACNET4 User?s Guide, University of Florida, http://www.ise.ufl.edu/kisko/files/evacnet/, 1998. KLD Associates, Formulations of the DYNEV and I-DYNEV Traffic Simulation Models Used in ESF, Rep. Prepared for the Federal Emergency Management Agency, Commack, N. Y, 1984. Kretz Tobias, Pedestrian Traffic: Simulation and Experiments, Ph.D. Dissertation, Vom Fachbereich Physik, der Universit?at Duisburg-Essen, 2007 161 Kuligowski E. D. and Peacock R. D., A Review of Building Evacuation Models, Technical Note 1471, National Institute of Standards and Technology, 2005. Lee D., Park J. H. and Kim H., A Study on Experiment of Human Behavior for Evacuation Simulation, Ocean Engineering, Vol. 31, pp. 931-941, 2004. Lee D., Kim H., Park J. H. and Park B. J., The Current Status and Future Issues in Human Evacuation from Ships, Safety Science, Vol. 41, pp. 861-876, 2003. Lewis D. C., September?s Great Escape: New Information System Helps Manage Hurricane Evacuations, Roads and Bridges, Vol. 39, pp. 40-42, 2001. Lin P., Lo S. M., Huang H. C. and Yuen K. K., On the Use of Multi-stage Time- Varying Quickest Time Approach for Optimization of Evacuation Planning, Fire Safety Journal, Vol. 43, pp. 282-290, 2008. Lindell M. K, Prater C.S., Perry R.W. and Wu J.Y., EMBLEM: An Empirically Based Large Scale Evacuation Time Estimate Model, Texas A&M University Hazard Reduction & Recovery Center, College Station, TX, Available at www.txdps.state.tx.us/dem/documents.htm, 2002a. Lindell M. K, Prater C. W., Wu J. Y., Hurricane Evacuation Time Estimates for the Texas Gulf Coast, Texas A&M University Hazard Reduction & Recovery Center, College Station, TX, Available at www.txdps.state.tx.us/dem/documents.htm, 2002b. Lindell M. K, EMBLEM2: An Empirically Based Large Scale Evacuation Time Estimate Model, Transportation Research Part A, Vol. 42, pp. 140-154, 2008. 162 Liu Y., Lai X. and Chang G. L., Cell-Based Network Optimization Model for Staged Evacuation Planning Under Emergencies, Transportation Research Record, No. 1964, pp. 127-135, 2006. Lo S. M. and Fang Z., A Spatial-Grid Evacuation Model for Building, Journal of Fire Science, Vol. 18, pp. 376-394, 2000a. Lo S. M, Fang Z., Zhi G. S. and Chen D. H., The Development of SGEM: An Evacuation Model for Fire Safety Design in Buildings, The Hong Kong Surveyor, Vol. 1, No. 8-14, 2000b. Lu Q., Huang Y., Shekhar S., Evacuation Planning: A Capacity Constrained Routing Approach, in: Proceedings of the First NSF/NIJ Symposium on Intelligence and Security Informatics, 111-125, 2003. Lu Q., George B. and Shekhar S., Capacity Constrained Routing Algorithms for Evacuation Planning: A Summary of Results, in: Proceedings of the Ninth International Symposium on Spatial and Temporal Databases, 2005. Mahmassani H.S., Peeta S., Hu T.Y., Ziliaskopoulos A.K., Dynamic traffic assignment with multiple user classes for real-time ATIS/ATMS applications. Large Urban Systems. Y. S. and S. A., U.S. DOT, pp. 91?114, 1993. Malone S., Miller C. A. and Neill D. B., Traffic Flow Models and the Evacuation Problem, UMAP J, Vol. 22, pp. 271-290, 2001. 163 Mitchell S. W and Radwan E., Heuristic Priority Ranking of Emergency Evacuation Staging to Reduce Clearance Time, Transportation Research Record, No. 1964, pp. 219-228, 2006. Moeller M. P., Urbanik T. and Desrosiers A. E., CLEAR (Calculates Logical Evacuation and Response): A Generic Transportation Model for Calculation of Evacuation Time Estimates, U. S. Nuclear Regulatory Commission, NUREG/CR- 2504, March 1982. Muckstadt J.A. and Wilson R.C., An Application of Mixed-Integer Programming Duality to Scheduling Thermal Generating Systems, IEEE Transactions, Vol. PAS-87, No. 12, pp. 1968-1978, Dec, 1968. Nagai R., Nagatani T., Isobe M. and Adachi T., Effect of Exit Configuration on Evacuation of a Room without Visibility, Physica A, Vol. 343, pp. 712-724, 2004. Nagai R., Fukamachi M. and Nagatani T., Evacuation of Crawlers and Walkers from Corridor through an Exit, Physica A, Vol. 367, pp. 449-460, 2006. Nagel K. and Schreckenberg M., A cellular automaton model for freeway traffic, J. Phys. I France, Vol. 2, pp. 2221-2229, 1992. Nelson H. E., McLennan H.A. (Eds.), Emergency Movement, The SFPE Handbook of Fire Protection Engineering, 3.286?3.295, (Section 3/Chapter 14), 1996. Newsom D. E., Madore M. A. and Robert T. J., Evacuation Modeling Near a Chemical Stockpile Site, Site Impact Traffic Assessment: Problems and Solutions 164 (Editors: Robert E Paaswell, Nagui Rouphail and Sutaria T. C), New York, ASCE, pp. 180-184, 1992. Ng M. W. and Waller S. T., Reliable Evacuation Planning via Demand Inflation and Supply Deflation, Transportation Research Part E, Vol. 46, pp. 1086-1094, 2010. Noor E., Shankar R. and Radwan E., Emergency Evacuation Planning and Preparedness of Transit Facilities, Transportation Research Record, No. 1992, pp. 121-126, 2007. Oak Ridge National Laboratory (ORNL), Oak Ridge Evacuation Modeling System (OREMS) User?s Guide, Center for Transportation Analysis, ORNL, Oak Ridge, Tenn, 1995. Olsson P. A. and Regan M. A., A Comparison between Actual and Predicted Evacuation Times, Safety Science, Vol. 38, pp. 139-145, 2001. Owen M., Galea E. R. and Lawrence P. J., The EXODUS Evacuation Model Applied to Building Evacuation Scenarios, Fire Engineers Journal, Vol. 56, pp. 26-30, 1996. Pan X., Han C. S., Dauber K. and Law K. H., A Multi-agent Based Framework for the Simulation of Human and Social Behaviors during Emergency Evacuations, AI Soc., Vol. 22, pp. 113-132, 2007. Papamichail K. N. and French S., Generating Feasible Strategies in Nuclear Emergencies-a Constraint Satisfaction Problem, Journal of the Operational Research Society, Vol. 50, pp. 617-626, 1999. 165 Papamichail K. N. and French S., Decision Support in Nuclear Emergencies, Journal of Hazardous Materials, Vol. 71, pp. 321-342, 2000. Paraskevi S. G., Ioannis A. P., Chris T. K., Nikolaos C. M., Modeling emergency evacuation for major hazard industrial sites, Reliability Engineering and System Safety , Vol. 92, pp. 1388?1402, 2007. Parisi D. R. and Dorso C. O., Microscopic Dynamics of Pedestrian Evacuation, Physica A, Vol. 354, pp. 606-618, 2005. Park B and Qi Hongtu, Development and Evaluation of a Procedure for the Calibration of Simulation Models, Transportation Research Record, No. 1934, pp. 208-217, 2005. Pearce V., Surface Transportation Security Lessons Learned from 9/11, ITE Journal, Vol. 72, pp. 38-43, September 2002. Phillips W. G. B., Simulation Models for Fire Risk Assessment, Fire Safety Journal, Vol.23, No.2, pp.159-169,1994. Pidd M., De Silva F. N. and Eglese R. W., A Simulation Model for Emergency Evacuation, European Journal of Operational Research, Vol. 90, pp. 413-419, 1996. Pielke R. A., Normalized Hurricane Damages in the United States: 1925-95, Weather and Forecasting, Vol. 13, pp. 621-631, September 1998. Pindyck R. S. and Rubinfeld D. L., Econometric Models and Economic Forecasts, 4th Edition, McGraw-Hill, N. Y., pp. 385-386, 1998. 166 Post, Buckley, Schuh & Jernigan, Inc. (PBS&J), Southeast Louisiana Hurricane Evacuation Study: Transportation Model Support Document, Tallahassee, Fla, 2001. PRC Voorhees, Evacuation Planning Package, Paper Presented at the 61st Annual TRB Meeting, Washington, D. C., 1982. Proulx G., Evacuation Time and Movement in Apartment Buildings, Fire Safety Journal, Vol. 24, pp. 229-246, 1995. Pursals S. C., Garzo F. G., Optimal building evacuation time considering evacuation routes, European Journal of Operational Research, Vol. 192, pp. 692?699, 2009. Quadstone, Paramics Software Home Page, http://www.paramics-online.com, 2002. Radwan A. E., Hobeika A. G. and Sivasailam D., A Computer Simulation Model for Rural Network Evacuation Under Natural Disasters, ITE Journal, Vol. 55, No. 9, pp. 25-30, September, 1985. Robinson R. M. and Khattak A., Route Change Decision Making by Hurricane Evacuees Facing Congestion, Transportation Research Record, No. 2196, pp. 168- 175, 2010. Sbayti H. and Mahmassani H., Optimal Scheduling of Evacuation Operations, Transportation Research Record, No. 1964, pp. 238-246, 2006. Shi C., Zhong M., Nong X., He L., Shi j. and Feng G., Modeling and Safety Strategy of Passenger Evacuation in a Metro Station in China, Safety Science, No. 9, In Press (Available online), 2010. 167 Shi J. Y., Ren A. Z. and Chen C., Agent-based Evacuation Model of Large Public Buildings under Fire Conditions, Automation in Construction, Vol. 18, pp. 338-347, 2009. Shreckenberg M., Neubert L. and Wahle J., Simulation of Traffic in Large Road Networks, Future Generation Computer Systems, Vol. 17, Issue. 5, 649-657, March, 2001. Sinuany-Stern Z., Stern E., Simulating the Evacuation of a Small City: the Effects of Traffic Factors, Socio-Economic Planning Science, Vol. 27, pp. 97-108, 1993. Sheffi Y. H., Mahmassani H. and Powell W. B., A Transportation Network Evacuation Model, Transportation Research Part A, Vol. 16A, No. 3, pp. 209-218, 1982. Shinozuka M., Moore J., Gordon P., Richardson H. W., Chang S. and Cho S. B., An Integrated Model of Highway Networks and the Spatial Metropolitan Economy: Towards a General Model of How Earthquake Losses Affect the Economy, NCEER Bulletin, Vol. 12, pp. 8-15, 1998. Sorensen J. H and Carnes S. A, An Approach for Deriving Emergency Planning Zones for Chemical Munitions Emergencies, Journal of Hazardous Materials, Vol. 30, pp. 223-242, 1992. Stahl FI. BFIRES-II: a behavior based computer simulation of emergency egress during fires. Fire Technology, Vol. 18, pp. 49-65, 1982. 168 Stern E., Sinuany-Stern Z., A Behavioral-based Simulation Model for Urban Evacuation, Papers of the Regional Science Association, Vol. 66, pp. 87-103, 1989. Stepanov A. and Smith J. M., Multi-objective Evacuation Routing in Transportation Networks, European Journal of Operational Research, Vol. 198, pp. 435-446, 2009. Thompson P. and Marchant E., A Computer Model for the Evacuation of Large Building Population, Fire Safety Journal, Vol. 24, pp. 131-148, 1995a. Thompson P. and Marchant E., Computer and Fluid Modeling of Evacuation, Safety Science, Vol. 18, pp. 277-289, 1995b. Kretz T., Pedestrian Traffic: Simulation and Experiments, Ph.D. Dissertation, Vom Fachbereich Physik, der Universit?at Duisburg-Essen, 2007. Tsukahara M., and Koshiba Y., Effectiveness of Downward Evacuation in a Large- scale Subway Fire using Fire Dynamics Simulator, Tunneling and Underground Space Technology, Vol. 26, pp. 573-581, 2011. Tufekci S., An Integrated Emergency Management Decision Support System for Hurricane Emergencies, Safety Science, Vol. 20, pp. 39-48, 1995. Urbanik T., Texas Hurricane Evacuation Study, Texas Transportation Institute, College Station, Tex, 1978. Urbanik T., Desrosier A., Lindell M. K. and Schuller C. R., Analysis of Techniques for Estimating Evacuation Times for Emergency Planning Zones, NUREG/CR-1745, U.S Nuclear Regulatory Commission, Washington D.C, 1980. 169 Urbanik T., Evacuation Time Estimates for Nuclear Power Plants, Journal of Hazardous Materials, Vol. 75, pp. 165-180, 2000. Urbina E. and Wolshon B., National Review of Hurricane Evacuation Plans and Policies: A Comparison and Contrast of State Practices, Transportation Research Part A, Vol. 37, pp. 257-275, 2003. Varas A., Cornejo M. D., Mainemer D., Toledo B., Rogan J., Munoz V. and Valdivia J. A., Cellular Automaton Model for Evacuation Process with Obstacles, Physica A, Vol. 382, pp. 631-642, 2007. Von Neumann J., Theory of Self-Reproducing Automata, Urbana: University of Illinois Press (ed. A.W. Burks), 1966. Wakabayashi H. and Kameda H., Network Performance of Highway Systems Under Earthquake Effects: A Case Study of the 1989 Loma Prieta Earthquake, Proceedings of the US-Japan Workshop on Earthquake Disaster Prevention of Lifeline Systems, Tsukuba Science City, Japan, pp. 215-232, 1992. Weckman H., Lehtimaki S. and Mannikko S., Evacuation of a Theatre: Exercise vs Calculations, Fire and Materials, Vol. 23, pp. 357-361, 1999. Weng W. G., Pan L. L., Shen S. F. and Yuan H. Y., Small-grid Analysis of Discrete Model for Evacuation from a Hall, Physica A, Vol. 374, pp. 821-826, 2007. Wahle J., Neubert L., Esser J., Schreckenberg M., A cellular automaton traffic flow model for online simulation of traffic. Parallel Computing, Vol. 27, No. 5, pp. 719- 735, 2001. 170 Werner S. D., Taylor C. E. and Moore J. E. II, Loss Estimation Due to Seismic Risks to Highway Systems, Earthquake Spectra, Vol. 13, pp. 585-604, 1997. Wolfram S., Statistical Mechanics of Cellular Automata, Reviews of Modern Physics, Vol. 55, No. 3, pp. 601?644, 1983. Wolshon B., Urbina E., Wilmot C. and Levitan M., Review of Policies and Practices for Hurricane Evacuation I: Transportation Planning, Preparedness, and Response, Natural Hazards Review, Vol. 6, No. 3, pp. 129-142, August 1, 2005. Wolshon B., Urbina E., Levitan M. and Wilmot C., Review of Policies and Practices for Hurricane Evacuation II: Traffic Operations, Management, and Control, Natural Hazards Review, Vol. 6, No. 3, pp. 143-161, August 1, 2005. Yamamoto K., Kokubo S., Simulation for Pedestrian Dynamics by Real-Coded Cellular Automata (RCA), Physica A, Vol. 379, pp. 654-660, 2007. Yang L. Z., Zhao D. L., Li J. and Fang T. Y., Simulation of the Kin Behavior in Building Occupant Evacuation Based on Cellular Automaton, Building and Environment, Vol. 40, pp. 411-415, 2005. Yang P.Z., Wang X. and Liu T., Agent-based Simulation of Fire Emergency Evacuation with Fire and Human Interaction Model, Safety Science, In press, 2011, doi: 10.1016/j.ssci.2011.03.003 Yao T., Mandala S. R. and Chung B. D., Evacuation Transportation Planning Under Uncertainty: A Robust Optimization Approach, Networks and Spatial Economics, Vol. 9, pp. 37-49, 2009. 171 Yazici A. and Ozbay K., Evacuation Network Modeling via Dynamic Traffic Assignment with Probabilistic Demand and Capacity Constraints, Transportation Research Record: Journal of the Transportation Research Board, No. 2196, Transportation Research Board of the National Academies, Washington, D.C., 11?20, 2010. Yuan W. and Tan K. H., An Evacuation Model Using Cellular Automata, Physica A, Vol. 384, pp. 549-566, 2007. Yuan F., Han L. D., Chin S. and Hwang H., Proposed Framework for Simultaneous Optimization of Evacuation Traffic Destination and Route Assignment, Transportation Research Record, No. 1964, pp. 50-58, 2006. Zhang J., Song W. and Xu X., Experiment and Multi-Grid Modeling of Evacuation from a Classroom, Physica A, Vol. 387, pp. 5901-5909, 2008. Zhang X. and Chang G. L., Optimal Control Strategies for Massive Vehicular Pedestrian Mixed Flows in the Evacuation Zone, Presented at the 89th Transportation Research Board Annual Meeting, 2010. Zheng H., Chiu Y. C., Mirchandani P. B. and Hickman M., Modeling of Evacuation and Background Traffic for Optimal Zone-Based Vehicle Evacuation Strategy, Transportation Research Record, No. 2196, pp. 65-74, 2010. Zhong M., Shi C., Tu X., Fu T. and He L., Study of the Human Evacuation Simulation of Metro Fire Safety Analysis in China, Journal of Loss Prevention in the Process Industries, Vol. 21, pp. 287-298, 2008. 172 Ziliaskopoulos A. K, Tuydes H and Barrett C, Impacts of Flood Induce Road Closures and Related Traffic Delays for Thorn Creek (DACW23-03-D-0001) prepared for USACE, Chicago District, May 2003 Ziliaskopoulos A. K., A Linear Programming Model for the Single Destination System Optimum Dynamic Traffic Assignment Problem, Transportation Science, Vol. 34, Issue. 1, pp. 37-49, 2000. Ziliaskopoulos A. K., Tuydes H. and Barrett C., Impacts of Flood Induce Road Closures and Related Traffic Delays for Chicago River-North Branche, prepared for USACE, Chicago District, March 2004. Zou N., Yeh S. T, Chang G. L., Marquess A. and Zezeski M., Simulation-Based Emergency Evacuation System for Ocean City, Maryland, During Hurricanes, Transportation Research Record, No. 1922, pp. 138-148, 2005.