
small (250x250 max)
medium (500x500 max)
Large
Extra Large
large ( > 500x500)
Full Resolution


Managing Evacuation Routes Stella K. So and Carlos F. Daganzo WORKING PAPER UCB ITS VWP 2009 9 September 2009 Managing Evacuation Routes Stella K. So and Carlos F. Daganzo ∗ Institute of Transportation Studies Department of Civil and Environmental Engineering University of California, Berkeley, CA 94720, USA August 12, 2009 Abstract This paper shows that evacuation routes, such as a building’s stairwell or an urban freeway, may discharge inefficiently if left unmanaged, and that setting priority rules can speed up egress. Therefore, a simple control strategy is proposed. The strategy is decentralized and adaptive, based on readily available real time data. The strategy is shown to be optimal in two senses: ( i) it finishes the evacuation in the least possible time, and ( ii) it evacuates the maximum number of people at all times. In both cases, it favors the people most at risk. The results shed light on other traffic problems. Keywords: InFO, innermost first out, evacuation routes, evacuation models, morning commute, ramp metering, user equilibrium 1 Introduction This paper proposes an adaptive strategy for evacuations along routes such as freeways, tall buildings, or shipping channels. Although the paper uses freeway terminology, as many past research efforts have done, its results are general. Reviewed below, these past efforts fall into two categories: flow based optimizations and computer simulations. Optimization techniques have been applied widely. These works treat evacuations as flowbased traffic assignment problems. Though they have considered broad scenarios including features such as shelter locations ( Sherali et al., 1991), household trip chain sequencing ( Murray Tuite and Mahmassani, 2004), and stochastic routing ( Shen et al., 2009), models in this class require much detailed data and are not adaptive. Simulation models were created in the 70s for the emergency planning of communities near nuclear power plants in the U. S. These models illustrate how traffic flows within a network under specific evacuation scenarios. Two pioneer evacuation simulation models are the micro simulator NETSIM ( Peat, Marwick, Mitchell & Co., 1974) and macro simulator ∗ Author for correspondence. E mail: daganzo@ ce. berkeley. edu 1 NETVACl ( Sheffi et al., 1982). These models used adhoc numerical schemes, which have since been superseded by more systematic methods: cellular automata for microscopic simulation ( Nagel and Schreckenberg, 1992) and the cell transmission model ( CTM) for macroscopic simulation ( Daganzo, 1994, 1995). One CTM application related to evacuations is Ziliaskopoulos ( 2000), which develops a detailed optimization algorithm for the single destination traffic assignment problem on a queued network. But as before, this model and others in its class require much data and are not adaptive. In summary, most existing models are too inflexible, data hungry and complicated to be used in real emergencies. Two works that alleviate these shortcomings are Daganzo and Lin ( 1993), which analyzes the morning commute problem for a homogeneous freeway, and Lovell and Daganzo ( 2000), which considers single destination freeway networks. Daganzo and Lin ( 1993) shows that a laissez faire strategy where queues are allowed to grow in a homogeneous freeway minimizes the time to serve everybody. This strategy however, gives priority to downstream residents who may be less at risk, and is not necessarily optimal for heterogeneous freeways. Lovell and Daganzo ( 2000) presents a real time strategy that minimizes total time in a network for a special case in which queues are only allowed at the network’s access points. The strategy however, is not decentralized, is sub optimal in the general case where queues are allowed in the network, and may not be appropriate for an evacuation because it does not recognize that some residents may be more at risk than others. Subsequent sections present a strategy for heterogeneous freeways that is decentralized, adaptive and quick: it maximizes at all times the number of evacuees from any population group within any given distance from the threat. Section 2 gives the definitions and assumptions for analysis; Section 3 develops a performance benchmark; Section 4 illustrates what traffic control can do; Section 5 introduces the control strategy; and Section 6 discusses the results. 2 Definitions and Assumptions Figure 1 depicts the generic freeway analyzed here. Ramps and links are numbered from 1 to I in the upstream direction. An exit separating danger from safety is located at i = 0, just downstream of link 1.1 Note that off ramps are ignored since traffic flows leaving the system at intermediate locations are assumed negligible. The following time invariant parameters characterize the freeway. For link i just downstream of ramp i: li .= link length, ci .= capacity flow, and ui .= free flow travel speed. Note that the exit capacity is c1. For ramp i: di .= ramp discharge capacity, and pi .= population to be evacuated. An unknown of interest is: τi .= the time at which ramp i is finished evacuating. Also define ˜ ci = min j ≤ i cj as the capacity of the most restrictive freeway link downstream of ramp i. For the remainder of this paper, ˜ ci is called the “ downstream capacity” ( d capacity) for i, and the corresponding freeway link the “ downstream bottleneck” ( d bottleneck) for i. Now ∀ i ∈ [ 1, I], let “ nest i” be the set of ramps from i to I. Then Pi = I j= i pj .= the population nested inside of ramp i, and an unknown of interest is: 1 The distribution of evacuees downstream of the exit is outside the scope of this paper. It is assumed that there is always sufficient capacity downstream of i = 0 to absorb all evacuating traffic. 2 Figure 1: Freeway Illustration Ti =. the time at which nest i is finished evacuating. Note that P1 and T1 define the total population and the total evacuation time of the system. The following time dependent variables are also defined. For any time t, t ≤ T1, pi( t) shall be the remaining population to be evacuated from ramp i ( so pi = pi( 0)). Also, ri( t) =. the flow discharged by ramp i, and qi( t) .= the flow on link i at t. Since there is no outflow at intermediate locations, the conservation equations are: qi( t) = ri( t) , for i = I; and ri( t) + qi+ 1( t) , for i ∈ [ 1, I − 1]. ( 1) The following assumptions are made to simplify analysis: 1. The clocks at every location along the freeway are started with the passage of a reference vehicle moving with the free flow speed. This has the effect of setting ui = ∞, ∀ i, without any loss of generality. 2. The evacuation starts with the passage of the reference vehicle ( at t = 0), and at this time the freeway is empty. 2 3. People try to evacuate so quickly that whenever pi( t) > 0, on ramp i will have a queue. These assumptions are rough, but reasonable in view of recent events. In a large scale evacuation, it can easily take more than one day to discharge all city residents even though it may only take a fraction of an hour to traverse the city at free flow. Personal interviews with emergency officials in New Orleans in October 2008 ( Sneed et al., 2008) revealed that authorities prefer starting an evacuation in the morning. At that time the freeway can be assumed nearly empty. Moreover, people are expected to flood all freeway entrances throughout an evacuation, therefore creating a queue at the on ramps at all times. 2The state of the freeway at t = 0 has a negligible impact on the time for evacuation if the pi are so large that each τi greatly exceeds the free flow travel time from i to the exit. This is typical in evacuations. 3 Figure 2: Capacity and d Capacity Curves 3 A Lower Bound Figure 2 depicts the functions ci and ˜ ci, approximated as continuous curves. Observe that ˜ ci ≤ ˜ ci− 1, ∀ i. Also, from the definition of a nest, the following can be noted: ( i) Pi ≤ Pi− 1; ( ii) Ti ≥ Pi/ ˜ ci since all residents in nest i must evacuate past the d bottleneck with capacity ˜ ci; and ( iii) Ti ≥ Tj since nest i cannot finish evacuating before nest j, ∀ j ≥ i. Thus, the following can be stated: Lemma 1. A lower bound for Ti is: TL i = max j≥ i Pj ˜ cj . ( 2) Proof. Since Ti ≥ Tj , ∀ j ≥ i, it follows that Ti ≥ maxj≥ i Tj. But Tj ≥ Pj/ ˜ cj , ∀ j. Therefore, Ti ≥ maxj≥ i Pj/ ˜ cj . Note that for i = 1, ( 2) gives a lower bound for the complete system. The next section shows that the evacuation time of an uncontrolled freeway may exceed ( 2). 4 Benefit of Control Refer to Figure 3. In this example, l1 = l2 = l ; c1 = 2c2 = 2c ; p1 = p2 = p ; and di > ci for i = 1, 2. As mentioned, free flow travel time is negligible, so u1 = u2 = ∞. For maximum simplicity, ramp traffic is also assumed to have absolute priority over freeway traffic if left uncontrolled. Under these conditions, the lower bound ( 2) for the system is TL 1 = p/ c. Now if the freeway is uncontrolled, users from ramp 2 would have to wait until all users from ramp 1 have finished evacuating before they can advance past ramp 1. While users from ramp 1 can pass the exit at the maximum rate 2c, the capacity restriction on link 2 implies that ramp 4 Figure 3: A Two Link Heterogeneous Freeway 2 users can only exit at rate c. Thus, the total evacuation time with no control, TN 1 , is: TN 1 = p/ 2c + p/ c = 1.5( p/ c). This exceeds the lower bound by 50%. Imagine now that a meter is placed on ramp 1, giving absolute priority to users coming from ramp 2 but allowing people from ramp 1 to use all the residual capacity of link 1. In this case, users from ramp 2 will evacuate in time p/ c. During this time, users from ramp 1 will discharge at the residual rate 2c − c = c. Since there are p users from ramp 1, they too will finish discharging at time p/ c. So the evacuation time with this form of control, TC 1 , is: TC 1 = p/ c = TL 1 . Hence, the control is optimal and reduces by 33% the evacuation time with no control. This happens because by giving priority to upstream residents, the freeway’s capacity is better utilized. In short, priority matters: when unmanaged, a heterogeneous freeway may evacuate inefficiently. The next section presents a generalized version of the scheme in this example and shows that it is optimal for a broad class of systems. 5 The Innermost First Out ( InFO) Control Strategy For large systems, it is expected that many ramps lie between successive d bottlenecks. If these ramps are aggregated and treated as a single ramp, their combined discharge capacity would exceed the capacity of the downstream d bottleneck. Thus, it is assumed here that ramps are grouped, so di ≥ ˜ ci, ∀ i. The “ innermost first out” ( InFO) policy instructs an unfinished ramp i to discharge according to the following rule: ri( t) = ˜ ci , if pi( t) > 0, for i = I; and ˜ ci − qi+ 1( t) , if pi( t) > 0, for i ∈ [ 1, I − 1]. ( 3) This rule specifies that every unfinished ramp should release just enough evacuees to fill the residual capacity of its d bottleneck. Thus, under InFO, upstream freeway flows receive 5 priority over ramp flows, freeway queues do not form, and evacuees travel at ∞ speed while on the freeway. The following two lemmas establish some additional InFO properties. Lemma 2. Under InFO, if pi( t) > 0, then qi( t) = ˜ ci and the d bottleneck for i is saturated at time t. Proof. For pi( t) > 0, inserting ( 3) in ( 1) yields qi( t) = ˜ ci, ∀ i. Since ui = ∞, this implies that the d bottleneck for i is saturated at t. Lemma 3. The evacuation time of ramp i under InFO control, τ I i , satisfies τ I i ≤ Pi ˜ ci . ( 4) Proof ( by contradiction). Note that ∀ t ∈ [ 0, τI i ), pi( t) > 0. By virtue of Lemma 2, qi( t) = ˜ ci, ∀ t ∈ [ 0, τI i ). Then the cumulative number of vehicles passing link i during [ 0, τI i ) ( i. e., τI i t= 0 qi( t) dt) must be: τ I i ˜ ci. Now assume that τ I i ˜ ci > Pi ( i. e., the lemma is false). This would mean that the number of vehicles passing i ( τ I i ˜ ci) exceeds Pi, which is impossible. Now let TI i be the evacuation time of nest i under InFO. The theorem below shows that InFO control minimizes the evacuation time for every nest. Theorem 1. InFO control satisfies TI i = TL i , ∀ i. Proof. A nest’s evacuation time is determined by its last to finish ramp; i. e., Ti = maxj≥ i τj . Now substitute ( 4) into this expression, and compare the result with ( 2) to find: TI i ≤ maxj≥ i Pj/ ˜ cj ≡ TL i . This shows that TL i is an upper bound to TI i . Since TL i is also a lower bound, as shown in ( 2), it follows that TI i = TL i . Since nest i = 1 includes all the ramps, it follows that: Corollary 1. InFO control minimizes the evacuation time for the complete system. Sometimes a disaster approaches too quickly for everyone to be evacuated. In such cases, one may want to evacuate as many people as possible before the disaster strikes. Theorems 2 and 3 below show that InFO control also achieves this alternative objective. Lemma 4. Under InFO control, at least one d bottleneck on the freeway is saturated while the evacuation is in progress, i. e., while t ∈ [ 0, TI 1 ). Proof. Since pi( t) > 0 for some i if t ∈ [ 0, TI 1 ), it follows from Lemma 2 that qi( t) = ˜ ci and the d bottleneck for i is saturated at time t. The most downstream of these saturated d bottlenecks is called from now on the “ critical bottleneck”. Note that the critical bottleneck may change with time. Lemma 5. Under InFO control, at any given time, all ramps downstream of the critical bottleneck have finished evacuating. 6 Proof ( by contradiction). If the lemma is false, a ramp j downstream of the critical bottleneck at some time t would not have finished discharging by time t, and therefore pj( t) > 0. By virtue of Lemma 2, the d bottleneck for j would have to be saturated. But this is impossible since this bottleneck is downstream of the critical bottleneck. To prove the final theorems, let Nx+( t) .= the number of residents upstream of a location x who have evacuated by time t; Nx−( t) .= the number of residents downstream of x who have evacuated by t; and N( t) = Nx+( t) + Nx−( t) .= the total number of evacuees by t. The superscript I shall be added to these variables to indicate InFO control. Theorem 2. InFO control maximizes the number of evacuees at any time. Proof. Since everyone is evacuated when t ≥ TI 1 , only the case t < TI 1 needs to be considered. Consider now any such instant. Let δ index the ramp just upstream of the critical bottleneck at t. Then there must be a ramp i ≥ δ that is saturating the critical bottleneck, i. e., with qi( t) = ˜ ci = ˜ cδ. For this ramp, pi( t) > 0, and since pi( t ) is non increasing in t , pi( t ) > 0 for t ∈ [ 0, t]. Now, by Lemma 2, qi( t ) = ˜ ci = ˜ cδ for t ∈ [ 0, t], implying that the critical bottleneck, which is the d bottleneck for i, is always saturated during [ 0, t]. Thus, the number of upstream evacuees at t under InFO is: NI δ+( t) = ˜ cδ · t. Also, by Lemma 5, NI δ− ( t) = δ− 1 i= 1 pi. Therefore, the total number of evacuees under InFO is: NI ( t) = NI δ+( t) + NI δ− ( t) = ˜ cδ · t + δ− 1 i= 1 pi. ( 5) Obviously, for any strategy, Nδ+( t) ≤ ˜ cδ · t and Nδ−( t) ≤ δ− 1 i= 1 pi. Therefore, N( t) = Nδ+( t) + Nδ−( t) ≤ ˜ cδ · t + δ− 1 i= 1 pi = NI( t). So NI ( t) is an upper bound for the total number of evacuees that can be achieved by time t. Let NI i ( t) now denote the total number of evacuees from nest i by time t under InFO. Theorem 3. InFO control maximizes the number of evacuees from every nest at any time. Proof. Again, since everyone is evacuated when t ≥ TI 1 , only the case t < TI 1 needs to be considered. As before, let δ be the ramp just upstream of the critical bottleneck at t. Now note from ( 3) that the only downstream influence on the flow from an unfinished ramp i ≥ δ comes from ˜ ci. Thus, NI i ( t) remains invariant if pj is set equal to 0, ∀ j < i. In this case, ( 5) would yield NI ( t) = ˜ cδ · t, with all the discharge coming from nest i. Thus, NI i ( t) = ˜ cδ · t. But i ≥ δ and ˜ cδt is the maximum number of people that can discharge past δ in time t. Hence, NI i ( t) is bounded above by ˜ cδ · t. Obviously then, since NI i ( t) equals its upper bound, it must be the maximum possible. In summary, this section shows that InFO control is optimal in light of two evacuation objectives: minimizing evacuation time and maximizing the number of evacuees at any time. Theorems 1 and 3 also show that InFO could be socially acceptable as it evacuates all nests in the least possible time and prioritizes upstream residents. 7 Finally, InFO control is easy to implement. Only two pieces of easily observed data are required: the downstream capacities and oncoming traffic flows. No predictive information on demand is needed. Furthermore, if incidents change the link capacities, recipe ( 3) can be updated in real time. With the ˜ ci known, the ramp controller ( a police officer, perhaps) only needs to observe the arriving flow, and then release the appropriate amount without any need for central control. 6 Discussion 6.1 Freeways with Limited Inputs InFO may not be optimal if the assumption di ≥ ci, ∀ i, is violated. Figure 4 is an example. It shows a simple freeway similar to the one in Figure 3. Once again, ramps are assumed to have priority at the merges if uncontrolled. Also, c1 = 2c, c2 = c, and d2 > c. Now, however, ramp 1 has a population of 3p, and its input flow is limited to ( 3/ 2) c. Because of its limited capacity, each ramp i now requires at least pi/ di time units to discharge its population. In addition, people from i still need at least Pi/ ˜ ci time units to evacuate to the exit as in Lemma 3. Thus, a tighter lower bound for the evacuation time is now: TL 1 = max i ( pi/ di, Pi/ ˜ ci). For this example, the result is TL 1 = 2p/ c. Under InFO control, ramp 2 has priority and discharges at rate c while ramp 1 discharges at the residual rate 2c− c = c. When ramp 2 finishes at t = p/ c, 2p residents still remain at ramp 1, which now can discharge with flow ( 3/ 2) c. This second phase takes an additional ( 4/ 3)( p/ c) time units. Therefore: TI 1 = ( 7/ 3)( p/ c) > TL 1 . It turns out that TL 1 can be achieved for this example if priority is given to the downstream ramp. In this case, ramp 1 would discharge at its capacity ( 3c/ 2) while ramp 2 would discharge at the residual rate of c/ 2 from the start of evacuation. Both ramps would fully saturate the exit and finish at the same time. Thus, InFO is sub optimal. Although good solutions for freeway problems with limited inputs can be found by modifying the objective function in Lovell and Daganzo ( 2000), the resulting algorithms would be neither decentralized nor necessarily optimal if one allows solutions with queues. Thus, an open question is whether a policy exists that could simplify matters and still yield nearoptimal results. Remember, however, that the basic InFO strategy is already quite good for most long freeways, since the aggregate capacity of all the ramps between successive d bottlenecks usually exceeds their d capacity. 6.2 Downstream Effects The results of this paper assume that the exit can seamlessly absorb all the evacuating traffic. To make this happen, downstream queues should be prevented from spilling back and blocking the exit. The off ramps downstream of the exit and the surrounding surface streets must be carefully managed. 8 Figure 4: A Freeway with Limited Inputs This is particularly important when there is a popular destination ( such as a public shelter) located just downstream of the exit. Demand in this case could greatly exceed the offramp capacity, causing a queue to grow rapidly upstream. To avoid this problem, drivers should be diverted to other off ramps via dynamic signage; or more forcefully with manual instructions given by police personnel. The number of off ramps managed in this way should be much greater than the number of lanes on the freeway. Although the precise number would depend on the background traffic flow on the surrounding surface streets and the associated signal timings, it is safe to say that the management region for an evacuation should usually extend beyond the freeway exit for a distance greater than the freeway itself. 6.3 Driver Adaptation Theorems 1 and 3 guarantee that if assumption 3 of Section 2 is satisfied during an evacuation, then the populations that end up evacuating from each nest could not have been served any quicker; i. e., that InFO is optimal a posteriori. However, if there are parallel alternative routes ( unlikely for a building but likely for a freeway) and these routes allow people to backtrack in the upstream direction, people may switch ramps because InFO gives people an incentive to move to higher priority upstream ramps if they are underused. Could these moves hinder InFO’s performance? The theoretical answer to this question is yes: it should be clear that the evacuation time could increase considerably due to adaptation if people overreact, for example, by moving en masse to the most upstream ramp of the system. On the other hand, the Appendix shows that for every problem there always are forms of adaptation that do not change at all the total evacuation time, even if people are only allowed to switch in the upstream direction. 3 The total evacuation time under these forms of equilibrium matches the lower bound and is therefore minimized. The conditions of the Appendix are fairly realistic and are only sufficient, not necessary. This suggests that InFO could perform rather well in real applications where adaptation is possible. 3 Downstream switches would effectively expand the freeway capacity. 9 6.4 Future Work The analysis framework and results of this paper can be applied to other traffic problems. For example, InFO could be used to reduce the driving time on a heterogeneous freeway going to a single destination during a morning commute. InFO, however, does not allow freeway queues to develop. This is a disadvantage because freeway queues that do not reduce freeway discharge flow can relieve traffic congestion from the surrounding surface streets. So an interesting research question is determining whether the same results as InFO can be achieved while allowing queues on the freeway. The answer to this question is positive for homogeneous freeways, as shown in Daganzo and Lin ( 1993), but the general answer appears to be unknown. In the future, the search for adaptive strategies should be extended to more complex, twodimensional transportation systems. In a network with many streets and therefore routing options, an evacuation strategy of this type should take into account that people can change routes and may not utilize the network efficiently. Acknowledgements This work was jointly funded by the Volvo Center of Excellence at UC Berkeley and the University of California Transportation Center. Appendix: Driver Adaptation Results This Appendix describes the idea of InFO user equilibrium, shows that it exists and how it can arise. Notation. Let K .= the number of d bottlenecks in the system. Now, group all ramps sharing the same d bottleneck, and number these groups in the upstream direction from 1 to K. Brackets shall be used for parameters and variables associated with these groups, and the superscript A for equilibrium results after adaptation. So, for example, { τ} I, A k =. the evacuation time of group k under InFO assuming adaptation. Finally, the most downstream ramp group to finish the non adaptive InFO evacuation at TI 1 ( i. e., at the last possible time) is denoted k∗. Note that { T} I k∗ = { T} I 1 = TI 1 . Equilibrium definition. Assume that all populations are pre staged at the on ramps at t = 0, that ramp switching takes no time, and that all ramp switches occur at t = 0. Then, the resulting ramp populations pAi are said to be a user equilibrium under InFO ( InFO UE) if evacuees at the end of each queue cannot reduce their evacuation time by switching to an upstream ramp. Lemma A1. Under the InFO UE, a ramp i of group k is used only if i is the most upstream ramp in group k. Proof ( by contradiction). If a ramp that is not the most upstream in the group was used, it would finish after the most upstream ramp in the group. Therefore, it could not be in 10 equilibrium. In view of Lemma A1, it is assumed from now on and without loss of generality that each group has only one ramp. Lemma A2. If people from k < k∗ do not cross k∗, an equilibrium for all the groups k ≥ k∗ is: { p} Ak = { T} I k∗ · ({ c} k − { c} k+ 1). In this equilibrium all these groups finish concurrently in time { T} I k∗ . Of course this time does not exceed { T} I 1 . Proof. Recall that the { c} k are the capacities of d bottlenecks, so { c} k −{ c} k+ 1 > 0. In the beginning, all ramps k ≥ k∗ discharge at rate { c} k − { c} k+ 1 until one of them is finished. This happens at tk = min { p} Ak /({ c} k −{ c} k+ 1) which equals { T} I k∗ by construction. Since this value is independent of k, all ramps finish concurrently and the populations are in equilibrium. Lemma A3. The nested populations in the equilibrium of Lemma A2 satisfy: { P} Ak ≥ { P} k, for k ≥ k∗. Proof ( by contradiction). Note that for k ≥ k∗, { P} Ak = j≥ k{ p} Aj = { T} I k∗{ c} k = { T} I 1{ c} k, where the RHS is the maximum number of vehicles that can discharge past d bottleneck k in the non adaptive evacuation time, { T} I 1 . Now, if the lemma is false, there would be a k ≥ k∗ such that { P} k ≥ { P} Ak . But this is impossible since it would mean that { P} k would exceed this maximum number of vehicles that can discharge past d bottleneck k in the allotted time. Lemma A3 guarantees that the equilibrium of Lemma A2 can be achieved even though people can only flow upstream. The final theorem extends these results to the complete freeway. Theorem A1. Under InFO, there is a user equilibrium with { P} Ak ≥ { P} k, ∀ k, that does not change the total discharge time. Proof. If k∗ = 1, the result is obvious. Otherwise, Lemma A2 shows that if people downstream of k∗ do not backtrack past k∗, the upstream residents could take the same time to discharge with and without adaptation. Consider now the downstream residents ( assuming k∗ > 1). Note that the upstream influence on these residents is the same as before: bottleneck k∗ is always saturated throughout the evacuation ( before and after adaptation), thereby effectively reducing all downstream freeway capacities by { c} k∗ . Populations downstream of k∗ are conserved. Hence, if these residents do not adapt, their evacuation time is the same as before. They would discharge in a time { T} I 1 < { T} I k∗ = { T} I 1 , and have no incentive to shift to k ≥ k∗. So their behavior can be understood by means of a reduced problem that ignores all upstream residents ( i. e., only includes groups 1, . . . , k∗ − 1) and uses reduced freeway capacities { c} k = { c} k − { c} k∗ . This reduced problem is of the same type as the one in Lemmas A2 and A3, and therefore can be treated in the same way with the same conclusions: there will be a new k ∗ < k∗ and the new discharge time for residents in k ≥ k ∗ will not exceed { T} I 1 = TI 1 . Furthermore, { P} Ak ≥ { P} k, ∀ k ≥ k ∗. So, again, if k ∗ = 1, the problem is solved. Otherwise, repeat this step enough times until the last group to discharge is k = 1. 11 This theorem shows that if there are parallel routes that allow people to backtrack in the upstream direction, then: ( i) a user equilibrium that is system optimum exists, and ( ii) this can be achieved. The results are derived assuming that people switch ramps at t = 0, but consideration also shows that this form of equilibrium can also arise if people adapt gradually while the evacuation is in progress, provided they do not overreact. References C. F. Daganzo. The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory. Transportation Research Part B: Methodological, 28( 4): 269– 287, 1994. C. F. Daganzo. The cell transmission model, part II: Network traffic. Transportation Research Part B: Methodological, 29( 2): 79– 93, 1995. C. F. Daganzo and W. H. Lin. The spatial evolution of queues during the morning commute in a single corridor. California Partners for Advanced Transit and Highways ( PATH). Research Reports: Paper UCB ITS PWP 93 7, 1993. Presented at the Transportation Research Board meeting of 1994. D. J. Lovell and C. F. Daganzo. Access control on networks with unique origindestination paths. Transportation Research Part B, 34( 3): 185– 202, 2000. P. M. Murray Tuite and H. S. Mahmassani. Transportation network evacuation planning with household activity interactions. Transportation Research Record, 1894: 150, 2004. K. Nagel and M. Schreckenberg. A cellular automaton model for freeway traffic. Journal de Physique I, 2( 12): 2221, 1992. Peat, Marwick, Mitchell & Co. Network flow simulation for urban traffic control system  phase II. Technical Report FHWA RD 73 87, US Department of Transportation, 1974. Y. Sheffi, H. Mahmassani, and W. B. Powell. A transportation network evacuation model. Transportation Research Part A: General, 16( 3): 209– 218, 5 1982. Z. J. Shen, T. S. Tsoi, J. Pannala, and R. Rai. Modeling Transportation Networks During Disruptions and Emergency Evacuations. TRB 88th Annual Meeting Compendium of Papers. 2009. H. D. Sherali, T. B. Carter, and A. G. Hobeika. A location allocation model and algorithm for evacuation planning under hurricane/ flood conditions. Transportation Research Part B: Methodological, 25( 6): 439– 452, 12 1991. J. Sneed, M. Kallmyer, T. Ignelzi, and J. DeMartini. Interview with the New Orleans Office of Emergency Preparedness, 30 Sep 2008. New Orleans City Hall, 1300 Perdido Street, New Orleans, LA 70112. A. K. Ziliaskopoulos. A linear programming model for the single destination system optimum dynamic traffic assignment problem. Transportation Science., 34( 1), 2000. 12
Click tabs to swap between content that is broken into logical sections.
Rating  
Title  Managing evacuation routes 
Subject  TA1001.C795 no. 20099; Evacuation of civiliansMathematical models.; Traffic flowMathematical models. 
Description  Performed by UC Berkeley Center for Future Urban Transport.; "A Volvo Center of Excellence."; "March 2009."; Includes bibliographical references (leaf 12). 
Creator  So, Stella. 
Publisher  Institute of Transportation Studies, University of California, Berkeley 
Contributors  Daganzo, Carlos.; UC Berkeley Center for Future Urban Transport.; University of California, Berkeley. Institute of Transportation Studies. 
Type  Text 
Language  eng 
Relation  Also available online.; http://www.its.berkeley.edu/publications/UCB/2009/VWP/UCBITSVWP20099.pdf; http://worldcat.org/oclc/489555269/viewonline 
DateIssued  [2009] 
FormatExtent  12 leaves : ill. ; 28 cm. 
RelationIs Part Of  Working paper ; UCBITSVWP20099; Working paper (UC Berkeley Center for Future Urban Transport) ; UCBITSVWP20099. 
Transcript  Managing Evacuation Routes Stella K. So and Carlos F. Daganzo WORKING PAPER UCB ITS VWP 2009 9 September 2009 Managing Evacuation Routes Stella K. So and Carlos F. Daganzo ∗ Institute of Transportation Studies Department of Civil and Environmental Engineering University of California, Berkeley, CA 94720, USA August 12, 2009 Abstract This paper shows that evacuation routes, such as a building’s stairwell or an urban freeway, may discharge inefficiently if left unmanaged, and that setting priority rules can speed up egress. Therefore, a simple control strategy is proposed. The strategy is decentralized and adaptive, based on readily available real time data. The strategy is shown to be optimal in two senses: ( i) it finishes the evacuation in the least possible time, and ( ii) it evacuates the maximum number of people at all times. In both cases, it favors the people most at risk. The results shed light on other traffic problems. Keywords: InFO, innermost first out, evacuation routes, evacuation models, morning commute, ramp metering, user equilibrium 1 Introduction This paper proposes an adaptive strategy for evacuations along routes such as freeways, tall buildings, or shipping channels. Although the paper uses freeway terminology, as many past research efforts have done, its results are general. Reviewed below, these past efforts fall into two categories: flow based optimizations and computer simulations. Optimization techniques have been applied widely. These works treat evacuations as flowbased traffic assignment problems. Though they have considered broad scenarios including features such as shelter locations ( Sherali et al., 1991), household trip chain sequencing ( Murray Tuite and Mahmassani, 2004), and stochastic routing ( Shen et al., 2009), models in this class require much detailed data and are not adaptive. Simulation models were created in the 70s for the emergency planning of communities near nuclear power plants in the U. S. These models illustrate how traffic flows within a network under specific evacuation scenarios. Two pioneer evacuation simulation models are the micro simulator NETSIM ( Peat, Marwick, Mitchell & Co., 1974) and macro simulator ∗ Author for correspondence. E mail: daganzo@ ce. berkeley. edu 1 NETVACl ( Sheffi et al., 1982). These models used adhoc numerical schemes, which have since been superseded by more systematic methods: cellular automata for microscopic simulation ( Nagel and Schreckenberg, 1992) and the cell transmission model ( CTM) for macroscopic simulation ( Daganzo, 1994, 1995). One CTM application related to evacuations is Ziliaskopoulos ( 2000), which develops a detailed optimization algorithm for the single destination traffic assignment problem on a queued network. But as before, this model and others in its class require much data and are not adaptive. In summary, most existing models are too inflexible, data hungry and complicated to be used in real emergencies. Two works that alleviate these shortcomings are Daganzo and Lin ( 1993), which analyzes the morning commute problem for a homogeneous freeway, and Lovell and Daganzo ( 2000), which considers single destination freeway networks. Daganzo and Lin ( 1993) shows that a laissez faire strategy where queues are allowed to grow in a homogeneous freeway minimizes the time to serve everybody. This strategy however, gives priority to downstream residents who may be less at risk, and is not necessarily optimal for heterogeneous freeways. Lovell and Daganzo ( 2000) presents a real time strategy that minimizes total time in a network for a special case in which queues are only allowed at the network’s access points. The strategy however, is not decentralized, is sub optimal in the general case where queues are allowed in the network, and may not be appropriate for an evacuation because it does not recognize that some residents may be more at risk than others. Subsequent sections present a strategy for heterogeneous freeways that is decentralized, adaptive and quick: it maximizes at all times the number of evacuees from any population group within any given distance from the threat. Section 2 gives the definitions and assumptions for analysis; Section 3 develops a performance benchmark; Section 4 illustrates what traffic control can do; Section 5 introduces the control strategy; and Section 6 discusses the results. 2 Definitions and Assumptions Figure 1 depicts the generic freeway analyzed here. Ramps and links are numbered from 1 to I in the upstream direction. An exit separating danger from safety is located at i = 0, just downstream of link 1.1 Note that off ramps are ignored since traffic flows leaving the system at intermediate locations are assumed negligible. The following time invariant parameters characterize the freeway. For link i just downstream of ramp i: li .= link length, ci .= capacity flow, and ui .= free flow travel speed. Note that the exit capacity is c1. For ramp i: di .= ramp discharge capacity, and pi .= population to be evacuated. An unknown of interest is: τi .= the time at which ramp i is finished evacuating. Also define ˜ ci = min j ≤ i cj as the capacity of the most restrictive freeway link downstream of ramp i. For the remainder of this paper, ˜ ci is called the “ downstream capacity” ( d capacity) for i, and the corresponding freeway link the “ downstream bottleneck” ( d bottleneck) for i. Now ∀ i ∈ [ 1, I], let “ nest i” be the set of ramps from i to I. Then Pi = I j= i pj .= the population nested inside of ramp i, and an unknown of interest is: 1 The distribution of evacuees downstream of the exit is outside the scope of this paper. It is assumed that there is always sufficient capacity downstream of i = 0 to absorb all evacuating traffic. 2 Figure 1: Freeway Illustration Ti =. the time at which nest i is finished evacuating. Note that P1 and T1 define the total population and the total evacuation time of the system. The following time dependent variables are also defined. For any time t, t ≤ T1, pi( t) shall be the remaining population to be evacuated from ramp i ( so pi = pi( 0)). Also, ri( t) =. the flow discharged by ramp i, and qi( t) .= the flow on link i at t. Since there is no outflow at intermediate locations, the conservation equations are: qi( t) = ri( t) , for i = I; and ri( t) + qi+ 1( t) , for i ∈ [ 1, I − 1]. ( 1) The following assumptions are made to simplify analysis: 1. The clocks at every location along the freeway are started with the passage of a reference vehicle moving with the free flow speed. This has the effect of setting ui = ∞, ∀ i, without any loss of generality. 2. The evacuation starts with the passage of the reference vehicle ( at t = 0), and at this time the freeway is empty. 2 3. People try to evacuate so quickly that whenever pi( t) > 0, on ramp i will have a queue. These assumptions are rough, but reasonable in view of recent events. In a large scale evacuation, it can easily take more than one day to discharge all city residents even though it may only take a fraction of an hour to traverse the city at free flow. Personal interviews with emergency officials in New Orleans in October 2008 ( Sneed et al., 2008) revealed that authorities prefer starting an evacuation in the morning. At that time the freeway can be assumed nearly empty. Moreover, people are expected to flood all freeway entrances throughout an evacuation, therefore creating a queue at the on ramps at all times. 2The state of the freeway at t = 0 has a negligible impact on the time for evacuation if the pi are so large that each τi greatly exceeds the free flow travel time from i to the exit. This is typical in evacuations. 3 Figure 2: Capacity and d Capacity Curves 3 A Lower Bound Figure 2 depicts the functions ci and ˜ ci, approximated as continuous curves. Observe that ˜ ci ≤ ˜ ci− 1, ∀ i. Also, from the definition of a nest, the following can be noted: ( i) Pi ≤ Pi− 1; ( ii) Ti ≥ Pi/ ˜ ci since all residents in nest i must evacuate past the d bottleneck with capacity ˜ ci; and ( iii) Ti ≥ Tj since nest i cannot finish evacuating before nest j, ∀ j ≥ i. Thus, the following can be stated: Lemma 1. A lower bound for Ti is: TL i = max j≥ i Pj ˜ cj . ( 2) Proof. Since Ti ≥ Tj , ∀ j ≥ i, it follows that Ti ≥ maxj≥ i Tj. But Tj ≥ Pj/ ˜ cj , ∀ j. Therefore, Ti ≥ maxj≥ i Pj/ ˜ cj . Note that for i = 1, ( 2) gives a lower bound for the complete system. The next section shows that the evacuation time of an uncontrolled freeway may exceed ( 2). 4 Benefit of Control Refer to Figure 3. In this example, l1 = l2 = l ; c1 = 2c2 = 2c ; p1 = p2 = p ; and di > ci for i = 1, 2. As mentioned, free flow travel time is negligible, so u1 = u2 = ∞. For maximum simplicity, ramp traffic is also assumed to have absolute priority over freeway traffic if left uncontrolled. Under these conditions, the lower bound ( 2) for the system is TL 1 = p/ c. Now if the freeway is uncontrolled, users from ramp 2 would have to wait until all users from ramp 1 have finished evacuating before they can advance past ramp 1. While users from ramp 1 can pass the exit at the maximum rate 2c, the capacity restriction on link 2 implies that ramp 4 Figure 3: A Two Link Heterogeneous Freeway 2 users can only exit at rate c. Thus, the total evacuation time with no control, TN 1 , is: TN 1 = p/ 2c + p/ c = 1.5( p/ c). This exceeds the lower bound by 50%. Imagine now that a meter is placed on ramp 1, giving absolute priority to users coming from ramp 2 but allowing people from ramp 1 to use all the residual capacity of link 1. In this case, users from ramp 2 will evacuate in time p/ c. During this time, users from ramp 1 will discharge at the residual rate 2c − c = c. Since there are p users from ramp 1, they too will finish discharging at time p/ c. So the evacuation time with this form of control, TC 1 , is: TC 1 = p/ c = TL 1 . Hence, the control is optimal and reduces by 33% the evacuation time with no control. This happens because by giving priority to upstream residents, the freeway’s capacity is better utilized. In short, priority matters: when unmanaged, a heterogeneous freeway may evacuate inefficiently. The next section presents a generalized version of the scheme in this example and shows that it is optimal for a broad class of systems. 5 The Innermost First Out ( InFO) Control Strategy For large systems, it is expected that many ramps lie between successive d bottlenecks. If these ramps are aggregated and treated as a single ramp, their combined discharge capacity would exceed the capacity of the downstream d bottleneck. Thus, it is assumed here that ramps are grouped, so di ≥ ˜ ci, ∀ i. The “ innermost first out” ( InFO) policy instructs an unfinished ramp i to discharge according to the following rule: ri( t) = ˜ ci , if pi( t) > 0, for i = I; and ˜ ci − qi+ 1( t) , if pi( t) > 0, for i ∈ [ 1, I − 1]. ( 3) This rule specifies that every unfinished ramp should release just enough evacuees to fill the residual capacity of its d bottleneck. Thus, under InFO, upstream freeway flows receive 5 priority over ramp flows, freeway queues do not form, and evacuees travel at ∞ speed while on the freeway. The following two lemmas establish some additional InFO properties. Lemma 2. Under InFO, if pi( t) > 0, then qi( t) = ˜ ci and the d bottleneck for i is saturated at time t. Proof. For pi( t) > 0, inserting ( 3) in ( 1) yields qi( t) = ˜ ci, ∀ i. Since ui = ∞, this implies that the d bottleneck for i is saturated at t. Lemma 3. The evacuation time of ramp i under InFO control, τ I i , satisfies τ I i ≤ Pi ˜ ci . ( 4) Proof ( by contradiction). Note that ∀ t ∈ [ 0, τI i ), pi( t) > 0. By virtue of Lemma 2, qi( t) = ˜ ci, ∀ t ∈ [ 0, τI i ). Then the cumulative number of vehicles passing link i during [ 0, τI i ) ( i. e., τI i t= 0 qi( t) dt) must be: τ I i ˜ ci. Now assume that τ I i ˜ ci > Pi ( i. e., the lemma is false). This would mean that the number of vehicles passing i ( τ I i ˜ ci) exceeds Pi, which is impossible. Now let TI i be the evacuation time of nest i under InFO. The theorem below shows that InFO control minimizes the evacuation time for every nest. Theorem 1. InFO control satisfies TI i = TL i , ∀ i. Proof. A nest’s evacuation time is determined by its last to finish ramp; i. e., Ti = maxj≥ i τj . Now substitute ( 4) into this expression, and compare the result with ( 2) to find: TI i ≤ maxj≥ i Pj/ ˜ cj ≡ TL i . This shows that TL i is an upper bound to TI i . Since TL i is also a lower bound, as shown in ( 2), it follows that TI i = TL i . Since nest i = 1 includes all the ramps, it follows that: Corollary 1. InFO control minimizes the evacuation time for the complete system. Sometimes a disaster approaches too quickly for everyone to be evacuated. In such cases, one may want to evacuate as many people as possible before the disaster strikes. Theorems 2 and 3 below show that InFO control also achieves this alternative objective. Lemma 4. Under InFO control, at least one d bottleneck on the freeway is saturated while the evacuation is in progress, i. e., while t ∈ [ 0, TI 1 ). Proof. Since pi( t) > 0 for some i if t ∈ [ 0, TI 1 ), it follows from Lemma 2 that qi( t) = ˜ ci and the d bottleneck for i is saturated at time t. The most downstream of these saturated d bottlenecks is called from now on the “ critical bottleneck”. Note that the critical bottleneck may change with time. Lemma 5. Under InFO control, at any given time, all ramps downstream of the critical bottleneck have finished evacuating. 6 Proof ( by contradiction). If the lemma is false, a ramp j downstream of the critical bottleneck at some time t would not have finished discharging by time t, and therefore pj( t) > 0. By virtue of Lemma 2, the d bottleneck for j would have to be saturated. But this is impossible since this bottleneck is downstream of the critical bottleneck. To prove the final theorems, let Nx+( t) .= the number of residents upstream of a location x who have evacuated by time t; Nx−( t) .= the number of residents downstream of x who have evacuated by t; and N( t) = Nx+( t) + Nx−( t) .= the total number of evacuees by t. The superscript I shall be added to these variables to indicate InFO control. Theorem 2. InFO control maximizes the number of evacuees at any time. Proof. Since everyone is evacuated when t ≥ TI 1 , only the case t < TI 1 needs to be considered. Consider now any such instant. Let δ index the ramp just upstream of the critical bottleneck at t. Then there must be a ramp i ≥ δ that is saturating the critical bottleneck, i. e., with qi( t) = ˜ ci = ˜ cδ. For this ramp, pi( t) > 0, and since pi( t ) is non increasing in t , pi( t ) > 0 for t ∈ [ 0, t]. Now, by Lemma 2, qi( t ) = ˜ ci = ˜ cδ for t ∈ [ 0, t], implying that the critical bottleneck, which is the d bottleneck for i, is always saturated during [ 0, t]. Thus, the number of upstream evacuees at t under InFO is: NI δ+( t) = ˜ cδ · t. Also, by Lemma 5, NI δ− ( t) = δ− 1 i= 1 pi. Therefore, the total number of evacuees under InFO is: NI ( t) = NI δ+( t) + NI δ− ( t) = ˜ cδ · t + δ− 1 i= 1 pi. ( 5) Obviously, for any strategy, Nδ+( t) ≤ ˜ cδ · t and Nδ−( t) ≤ δ− 1 i= 1 pi. Therefore, N( t) = Nδ+( t) + Nδ−( t) ≤ ˜ cδ · t + δ− 1 i= 1 pi = NI( t). So NI ( t) is an upper bound for the total number of evacuees that can be achieved by time t. Let NI i ( t) now denote the total number of evacuees from nest i by time t under InFO. Theorem 3. InFO control maximizes the number of evacuees from every nest at any time. Proof. Again, since everyone is evacuated when t ≥ TI 1 , only the case t < TI 1 needs to be considered. As before, let δ be the ramp just upstream of the critical bottleneck at t. Now note from ( 3) that the only downstream influence on the flow from an unfinished ramp i ≥ δ comes from ˜ ci. Thus, NI i ( t) remains invariant if pj is set equal to 0, ∀ j < i. In this case, ( 5) would yield NI ( t) = ˜ cδ · t, with all the discharge coming from nest i. Thus, NI i ( t) = ˜ cδ · t. But i ≥ δ and ˜ cδt is the maximum number of people that can discharge past δ in time t. Hence, NI i ( t) is bounded above by ˜ cδ · t. Obviously then, since NI i ( t) equals its upper bound, it must be the maximum possible. In summary, this section shows that InFO control is optimal in light of two evacuation objectives: minimizing evacuation time and maximizing the number of evacuees at any time. Theorems 1 and 3 also show that InFO could be socially acceptable as it evacuates all nests in the least possible time and prioritizes upstream residents. 7 Finally, InFO control is easy to implement. Only two pieces of easily observed data are required: the downstream capacities and oncoming traffic flows. No predictive information on demand is needed. Furthermore, if incidents change the link capacities, recipe ( 3) can be updated in real time. With the ˜ ci known, the ramp controller ( a police officer, perhaps) only needs to observe the arriving flow, and then release the appropriate amount without any need for central control. 6 Discussion 6.1 Freeways with Limited Inputs InFO may not be optimal if the assumption di ≥ ci, ∀ i, is violated. Figure 4 is an example. It shows a simple freeway similar to the one in Figure 3. Once again, ramps are assumed to have priority at the merges if uncontrolled. Also, c1 = 2c, c2 = c, and d2 > c. Now, however, ramp 1 has a population of 3p, and its input flow is limited to ( 3/ 2) c. Because of its limited capacity, each ramp i now requires at least pi/ di time units to discharge its population. In addition, people from i still need at least Pi/ ˜ ci time units to evacuate to the exit as in Lemma 3. Thus, a tighter lower bound for the evacuation time is now: TL 1 = max i ( pi/ di, Pi/ ˜ ci). For this example, the result is TL 1 = 2p/ c. Under InFO control, ramp 2 has priority and discharges at rate c while ramp 1 discharges at the residual rate 2c− c = c. When ramp 2 finishes at t = p/ c, 2p residents still remain at ramp 1, which now can discharge with flow ( 3/ 2) c. This second phase takes an additional ( 4/ 3)( p/ c) time units. Therefore: TI 1 = ( 7/ 3)( p/ c) > TL 1 . It turns out that TL 1 can be achieved for this example if priority is given to the downstream ramp. In this case, ramp 1 would discharge at its capacity ( 3c/ 2) while ramp 2 would discharge at the residual rate of c/ 2 from the start of evacuation. Both ramps would fully saturate the exit and finish at the same time. Thus, InFO is sub optimal. Although good solutions for freeway problems with limited inputs can be found by modifying the objective function in Lovell and Daganzo ( 2000), the resulting algorithms would be neither decentralized nor necessarily optimal if one allows solutions with queues. Thus, an open question is whether a policy exists that could simplify matters and still yield nearoptimal results. Remember, however, that the basic InFO strategy is already quite good for most long freeways, since the aggregate capacity of all the ramps between successive d bottlenecks usually exceeds their d capacity. 6.2 Downstream Effects The results of this paper assume that the exit can seamlessly absorb all the evacuating traffic. To make this happen, downstream queues should be prevented from spilling back and blocking the exit. The off ramps downstream of the exit and the surrounding surface streets must be carefully managed. 8 Figure 4: A Freeway with Limited Inputs This is particularly important when there is a popular destination ( such as a public shelter) located just downstream of the exit. Demand in this case could greatly exceed the offramp capacity, causing a queue to grow rapidly upstream. To avoid this problem, drivers should be diverted to other off ramps via dynamic signage; or more forcefully with manual instructions given by police personnel. The number of off ramps managed in this way should be much greater than the number of lanes on the freeway. Although the precise number would depend on the background traffic flow on the surrounding surface streets and the associated signal timings, it is safe to say that the management region for an evacuation should usually extend beyond the freeway exit for a distance greater than the freeway itself. 6.3 Driver Adaptation Theorems 1 and 3 guarantee that if assumption 3 of Section 2 is satisfied during an evacuation, then the populations that end up evacuating from each nest could not have been served any quicker; i. e., that InFO is optimal a posteriori. However, if there are parallel alternative routes ( unlikely for a building but likely for a freeway) and these routes allow people to backtrack in the upstream direction, people may switch ramps because InFO gives people an incentive to move to higher priority upstream ramps if they are underused. Could these moves hinder InFO’s performance? The theoretical answer to this question is yes: it should be clear that the evacuation time could increase considerably due to adaptation if people overreact, for example, by moving en masse to the most upstream ramp of the system. On the other hand, the Appendix shows that for every problem there always are forms of adaptation that do not change at all the total evacuation time, even if people are only allowed to switch in the upstream direction. 3 The total evacuation time under these forms of equilibrium matches the lower bound and is therefore minimized. The conditions of the Appendix are fairly realistic and are only sufficient, not necessary. This suggests that InFO could perform rather well in real applications where adaptation is possible. 3 Downstream switches would effectively expand the freeway capacity. 9 6.4 Future Work The analysis framework and results of this paper can be applied to other traffic problems. For example, InFO could be used to reduce the driving time on a heterogeneous freeway going to a single destination during a morning commute. InFO, however, does not allow freeway queues to develop. This is a disadvantage because freeway queues that do not reduce freeway discharge flow can relieve traffic congestion from the surrounding surface streets. So an interesting research question is determining whether the same results as InFO can be achieved while allowing queues on the freeway. The answer to this question is positive for homogeneous freeways, as shown in Daganzo and Lin ( 1993), but the general answer appears to be unknown. In the future, the search for adaptive strategies should be extended to more complex, twodimensional transportation systems. In a network with many streets and therefore routing options, an evacuation strategy of this type should take into account that people can change routes and may not utilize the network efficiently. Acknowledgements This work was jointly funded by the Volvo Center of Excellence at UC Berkeley and the University of California Transportation Center. Appendix: Driver Adaptation Results This Appendix describes the idea of InFO user equilibrium, shows that it exists and how it can arise. Notation. Let K .= the number of d bottlenecks in the system. Now, group all ramps sharing the same d bottleneck, and number these groups in the upstream direction from 1 to K. Brackets shall be used for parameters and variables associated with these groups, and the superscript A for equilibrium results after adaptation. So, for example, { τ} I, A k =. the evacuation time of group k under InFO assuming adaptation. Finally, the most downstream ramp group to finish the non adaptive InFO evacuation at TI 1 ( i. e., at the last possible time) is denoted k∗. Note that { T} I k∗ = { T} I 1 = TI 1 . Equilibrium definition. Assume that all populations are pre staged at the on ramps at t = 0, that ramp switching takes no time, and that all ramp switches occur at t = 0. Then, the resulting ramp populations pAi are said to be a user equilibrium under InFO ( InFO UE) if evacuees at the end of each queue cannot reduce their evacuation time by switching to an upstream ramp. Lemma A1. Under the InFO UE, a ramp i of group k is used only if i is the most upstream ramp in group k. Proof ( by contradiction). If a ramp that is not the most upstream in the group was used, it would finish after the most upstream ramp in the group. Therefore, it could not be in 10 equilibrium. In view of Lemma A1, it is assumed from now on and without loss of generality that each group has only one ramp. Lemma A2. If people from k < k∗ do not cross k∗, an equilibrium for all the groups k ≥ k∗ is: { p} Ak = { T} I k∗ · ({ c} k − { c} k+ 1). In this equilibrium all these groups finish concurrently in time { T} I k∗ . Of course this time does not exceed { T} I 1 . Proof. Recall that the { c} k are the capacities of d bottlenecks, so { c} k −{ c} k+ 1 > 0. In the beginning, all ramps k ≥ k∗ discharge at rate { c} k − { c} k+ 1 until one of them is finished. This happens at tk = min { p} Ak /({ c} k −{ c} k+ 1) which equals { T} I k∗ by construction. Since this value is independent of k, all ramps finish concurrently and the populations are in equilibrium. Lemma A3. The nested populations in the equilibrium of Lemma A2 satisfy: { P} Ak ≥ { P} k, for k ≥ k∗. Proof ( by contradiction). Note that for k ≥ k∗, { P} Ak = j≥ k{ p} Aj = { T} I k∗{ c} k = { T} I 1{ c} k, where the RHS is the maximum number of vehicles that can discharge past d bottleneck k in the non adaptive evacuation time, { T} I 1 . Now, if the lemma is false, there would be a k ≥ k∗ such that { P} k ≥ { P} Ak . But this is impossible since it would mean that { P} k would exceed this maximum number of vehicles that can discharge past d bottleneck k in the allotted time. Lemma A3 guarantees that the equilibrium of Lemma A2 can be achieved even though people can only flow upstream. The final theorem extends these results to the complete freeway. Theorem A1. Under InFO, there is a user equilibrium with { P} Ak ≥ { P} k, ∀ k, that does not change the total discharge time. Proof. If k∗ = 1, the result is obvious. Otherwise, Lemma A2 shows that if people downstream of k∗ do not backtrack past k∗, the upstream residents could take the same time to discharge with and without adaptation. Consider now the downstream residents ( assuming k∗ > 1). Note that the upstream influence on these residents is the same as before: bottleneck k∗ is always saturated throughout the evacuation ( before and after adaptation), thereby effectively reducing all downstream freeway capacities by { c} k∗ . Populations downstream of k∗ are conserved. Hence, if these residents do not adapt, their evacuation time is the same as before. They would discharge in a time { T} I 1 < { T} I k∗ = { T} I 1 , and have no incentive to shift to k ≥ k∗. So their behavior can be understood by means of a reduced problem that ignores all upstream residents ( i. e., only includes groups 1, . . . , k∗ − 1) and uses reduced freeway capacities { c} k = { c} k − { c} k∗ . This reduced problem is of the same type as the one in Lemmas A2 and A3, and therefore can be treated in the same way with the same conclusions: there will be a new k ∗ < k∗ and the new discharge time for residents in k ≥ k ∗ will not exceed { T} I 1 = TI 1 . Furthermore, { P} Ak ≥ { P} k, ∀ k ≥ k ∗. So, again, if k ∗ = 1, the problem is solved. Otherwise, repeat this step enough times until the last group to discharge is k = 1. 11 This theorem shows that if there are parallel routes that allow people to backtrack in the upstream direction, then: ( i) a user equilibrium that is system optimum exists, and ( ii) this can be achieved. The results are derived assuming that people switch ramps at t = 0, but consideration also shows that this form of equilibrium can also arise if people adapt gradually while the evacuation is in progress, provided they do not overreact. References C. F. Daganzo. The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory. Transportation Research Part B: Methodological, 28( 4): 269– 287, 1994. C. F. Daganzo. The cell transmission model, part II: Network traffic. Transportation Research Part B: Methodological, 29( 2): 79– 93, 1995. C. F. Daganzo and W. H. Lin. The spatial evolution of queues during the morning commute in a single corridor. California Partners for Advanced Transit and Highways ( PATH). Research Reports: Paper UCB ITS PWP 93 7, 1993. Presented at the Transportation Research Board meeting of 1994. D. J. Lovell and C. F. Daganzo. Access control on networks with unique origindestination paths. Transportation Research Part B, 34( 3): 185– 202, 2000. P. M. Murray Tuite and H. S. Mahmassani. Transportation network evacuation planning with household activity interactions. Transportation Research Record, 1894: 150, 2004. K. Nagel and M. Schreckenberg. A cellular automaton model for freeway traffic. Journal de Physique I, 2( 12): 2221, 1992. Peat, Marwick, Mitchell & Co. Network flow simulation for urban traffic control system  phase II. Technical Report FHWA RD 73 87, US Department of Transportation, 1974. Y. Sheffi, H. Mahmassani, and W. B. Powell. A transportation network evacuation model. Transportation Research Part A: General, 16( 3): 209– 218, 5 1982. Z. J. Shen, T. S. Tsoi, J. Pannala, and R. Rai. Modeling Transportation Networks During Disruptions and Emergency Evacuations. TRB 88th Annual Meeting Compendium of Papers. 2009. H. D. Sherali, T. B. Carter, and A. G. Hobeika. A location allocation model and algorithm for evacuation planning under hurricane/ flood conditions. Transportation Research Part B: Methodological, 25( 6): 439– 452, 12 1991. J. Sneed, M. Kallmyer, T. Ignelzi, and J. DeMartini. Interview with the New Orleans Office of Emergency Preparedness, 30 Sep 2008. New Orleans City Hall, 1300 Perdido Street, New Orleans, LA 70112. A. K. Ziliaskopoulos. A linear programming model for the single destination system optimum dynamic traffic assignment problem. Transportation Science., 34( 1), 2000. 12 



B 

C 

I 

S 


