Project h. e.r.o. 257 Project HERo Hurricane evacuation route Optimization Nathan gossett Barbara hess Bethel College St. Paul, MN Advisor: William m. Kinne Introduction Through modeling and computer simulation we established an evacuation plan for the coastal region of South Carolina in the event of an evacuation order We derive nine evacuation routes running from the coastal region inland Based on geography, counties are given access to appropriate routes. Com bining flow theory with geographic, demographic, and time constraints,we formulate a maximum flow problem. Using linear optimization, we find a fea sible solution This solution serves as a basis for our evacuation model. The validity of the model is confirmed through computer simulation. A total evacuation(1. 1 million people)in 24 to 26 hours is possible only if all traffic is reversed on the nine evacuation routes Terms and definitions Flow F: the number of cars that pass a given point per unit time(cars per hour per lane, unless otherwise specified) Speed s: the rate of movement of a single car(mph, unless otherwise specified) Density k: the number of cars per unit length of roadway(cars per mile per lane, unless otherwise specified) The UIMAP Journal 22 (3)(2001)257-269. @Copyright 2001 by COMAP, Inc. All rights reserved Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice. Abstracting with credit is permitted, but copyrights for components of this work owned by others than COMAP must be honored. To copy otherwise, to republish, to post on servers, or to redistribute to lists requires prior permission from COMAP
Project H.E.R.O. 257 Project H.E.R.O.: Hurricane Evacuation Route Optimization Nathan Gossett Barbara Hess Michael Page Bethel College St. Paul, MN Advisor: William M. Kinney Introduction Through modeling and computer simulation, we established an evacuation plan for the coastal region of South Carolina in the event of an evacuation order. We derive nine evacuation routes running from the coastal region inland. Based on geography, counties are given access to appropriate routes. Combining flow theory with geographic, demographic, and time constraints, we formulate a maximum flow problem. Using linear optimization, we find a feasible solution. This solution serves as a basis for our evacuation model. The validity of the model is confirmed through computer simulation. A total evacuation (1.1 million people) in 24 to 26 hours is possible only if all traffic is reversed on the nine evacuation routes. Terms and Definitions Flow F: the number of cars that pass a given point per unit time (cars per hour per lane, unless otherwise specified). Speed s: the rate of movement of a single car (mph, unless otherwise specified). Density k: the number of cars per unit length of roadway (cars per mile per lane, unless otherwise specified). The UMAP Journal 22 (3) (2001) 257ñ269. c Copyright 2001 by COMAP, Inc. All rights reserved. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice. Abstracting with credit is permitted, but copyrights for components of this work owned by others than COMAP must be honored. To copy otherwise, to republish, to post on servers, or to redistribute to lists requires prior permission from COMAP
258 The UMAP Journal 22.3 (2001) Headway distance hd: the space between the back of the leading car and the front of the immediately trailing car(ft).(Note: This is not a standard defi nition of headway distance.) Headway time h: the time required to travel headway distance Car Length C: length from front bumper to rear bumper of a single car( feet) G oals Our first priority is to maximize the number of people who reach safety; in terms of our model, we must maximize the flow of the entire system. A secondary goal is to minimize the total travel time for evacuees; this means that we must maximize speed. As we establish, these goals are one and the same Assumptions Vehicles hold 2 people on average. This seems reasonable, based on the percentage of the population who would be unable to drive themselves and those who would carpool Vehicles average 17 ft in length. This is based on a generous average fol lowing a quick survey of car manufacturers Web sites Vehicles have an average headway time of 3 s. This is based on numbers for driver reaction time, found in various driving manuals 50 mph is a safe driving spee Merging of traffic does not significantly affect our model. See the Ap- pendix for justification Highways 26, 76/328, and 501 are 4-lane. [Rand McNally 1998 Safety is defined as 50 mi from the nearest coastal point. Counties that lie beyond this point will not be evacuated [SCAN21 20011 Only the following counties need to be evacuated: Allendale, Beaufort, Berkeley, Charleston, Colleton, Dorchester, Georgetown, Hampton, Horry, Jasper, Marion, Williamsburg, and a minimal part of Florence County(based on the previous assumption) Myrtle Beach will not be at its full tourist population during a hurricane warning. This seems reasonable because tourists do not like imminent bad weather
258 The UMAP Journal 22.3 (2001) Headway distance hd: the space between the back of the leading car and the front of the immediately trailing car (ft). (Note: This is not a standard defi- nition of headway distance.) Headway time ht: the time required to travel headway distance. Car Length C: length from front bumper to rear bumper of a single car (feet). Goals Our first priority is to maximize the number of people who reach safety; in terms of our model, we must maximize the flow of the entire system. A secondary goal is to minimize the total travel time for evacuees; this means that we must maximize speed. As we establish, these goals are one and the same. Assumptions • Vehicles hold 2 people on average. This seems reasonable, based on the percentage of the population who would be unable to drive themselves and those who would carpool. • Vehicles average 17 ft in length. This is based on a generous average following a quick survey of car manufacturersí Web sites. • Vehicles have an average headway time of 3 s. This is based on numbers for driver reaction time, found in various driving manuals. • 50 mph is a safe driving speed. • Merging of traffic does not significantly affect our model. See the Appendix for justification. • Highways 26, 76/328, and 501 are 4-lane. [Rand McNally 1998] • Safety is defined as 50 mi from the nearest coastal point. Counties that lie beyond this point will not be evacuated [SCAN21 2001]. • Only the following counties need to be evacuated: Allendale, Beaufort, Berkeley, Charleston, Colleton, Dorchester, Georgetown, Hampton, Horry, Jasper, Marion, Williamsburg, and a minimal part of Florence County (based on the previous assumption). • Myrtle Beach will not be at its full tourist population during a hurricane warning. This seems reasonable because tourists do not like imminent bad weather
Project h. e.r.o. 259 The evacuation order will be given at least 24 to 26 h prior to the arrival of a hurricane. This is based on the timeline of the 1999 evacuation [Intergraph 2001l Boats, trailers, and other large vehicles will be limited from entering the main evacuation routes. Being able to evacuate people should have a higher priority than evacuating property If we can get everyone on a road within 24 h and keep traffic moving at a reasonable speed, everyone should be at a safe zone within 25 to 26 h. This is based on our assumption of what a safe zone is and our assumption of average speed Developing the Mode Abstracted Flow Modeling Upon inspecting the evacuation route map, we decided that there are only nine evacuation routes. There appear to be more, but many are interconnected and in fact merge at some point. By identifying all bottlenecks, we separated out the discrete paths Using this nine-path map in combination with the county map, we con- structed an abstracted flow model with nodes for each county, merge point, and destination so as to translate our model into a form for computer use a Brief discussion of flow The flow F is equal the product of density and speed: F= ks [Winston 1994]. We can find the density k of cars per mile by dividing 1 mi=5, 280 ft by the sum C+hd, the length of a car plus headway distance(in ft),so 5280s F=k Using the fact that headway distance hd is speed s(ft/s)times headway time h(sec),we 5280s 5280 +ht Increasing s increases F. This result is exciting, because it shows that max- imizing flow is the same as maximizing speed. The graph of F versus s gives even more insight(Figure 1). Increases in speed past a certain point benefit F less and less. So we might sacrifice parts of our model to increase low speeds but not necessarily to increase high speeds
Project H.E.R.O. 259 • The evacuation order will be given at least 24 to 26 h prior to the arrival of a hurricane. This is based on the timeline of the 1999 evacuation [Intergraph 2001]. • Boats, trailers, and other large vehicles will be limited from entering the main evacuation routes. Being able to evacuate people should have a higher priority than evacuating property. • If we can get everyone on a road within 24 h and keep traffic moving at a reasonable speed, everyone should be at a safe zone within 25 to 26 h. This is based on our assumption of what a safe zone is and our assumption of average speed. Developing the Model Abstracted Flow Modeling Upon inspecting the evacuation route map, we decided that there are only nine evacuation routes. There appear to be more, but many are interconnected and in fact merge at some point. By identifying all bottlenecks, we separated out the discrete paths. Using this nine-path map in combination with the county map, we constructed an abstracted flow model with nodes for each county, merge point, and destination, so as to translate our model into a form for computer use. A Brief Discussion of Flow The flow F is equal the product of density and speed: F = ks [Winston 1994]. We can find the density k of cars per mile by dividing 1 mi = 5,280 ft by the sum C + hd, the length of a car plus headway distance (in ft), so F = ks = 5280s C + hd . Using the fact that headway distance hd is speed s (ft/s) times headway time ht (sec), we have F = 5280s C + sht = 5280 C s + ht . Increasing s increases F. This result is exciting, because it shows that maximizing flow is the same as maximizing speed. The graph of F versus s gives even more insight (Figure 1). Increases in speed past a certain point benefit F less and less. So we might sacrifice parts of our model to increase low speeds but not necessarily to increase high speeds
260 The UMAP Journal 22.3 (2001) 1000 600 400 00 igure 1. Flow vs speed According to our assumptions, we have C= 17 ft and ht =3 sec, and converting to units of miles and hours, we ge 5280s11200 200F 52801200-F At our assumed maximum safe speed of s= 50 mph, we have F=1114 cars/h Determining bounds We combined our knowledge of county populations with the 24-h deadline and generated a minimum output flow for each county. We also determined the maximum flow for each node-to-node segment, based on the number of lanes. It would be unrealistic to assume that each segment would reach optimal flow, so we set maximum flow at 90% of optimal flow. This reduction in flow is meant to cover problems that arise from accidents, slow drivers rong Pm? ideal merging conditions, or other unexpected road conditions. Putting F 0.9 Fopt=(0.9 )(1113.92)into(1), we find s a 19.6 mph. We decided that this is an acceptable minimal speed Finding a Feasible Solution We used the linear optimizing program lindo to find a feasible solution the solution takes 26h. Since this scenario does not take into account geograph- ical convenience, we did some minor hand-tweaking. The final product is in the appendix
260 The UMAP Journal 22.3 (2001) 20 40 60 80 200 400 600 800 1000 Figure 1. Flow vs. speed. According to our assumptions, we have C = 17 ft and ht = 3 sec, and converting to units of miles and hours, we get F = 1 17 5280s + 1 1200 , or s = 17 5280 · 1200F 1200 − F . (1) At our assumed maximum safe speed of s = 50 mph, we have F = 1114 cars/h. Determining Bounds We combined our knowledge of county populations with the 24-h deadline and generated a minimum output flow for each county. We also determined the maximum flow for each node-to-node segment, based on the number of lanes. It would be unrealistic to assume that each segment would reach optimal flow, so we set maximum flow at 90% of optimal flow. This reduction in flow is meant to cover problems that arise from accidents, slow drivers, less than ideal merging conditions, or other unexpected road conditions. Putting F = 0.9Fopt = (0.9)(1113.92) into (1), we find s ≈ 19.6 mph. We decided that this is an acceptable minimal speed. Finding a Feasible Solution We used the linear optimizing program LINDO to find a feasible solution; the solution takes 26 h. Since this scenario does not take into account geographical convenience, we did some minor hand-tweaking. The final product is in the Appendix
Project h. e.r.o. 261 The simulation To confirm the feasibility of our model, we conducted a computer simula- tion using Arena simulation software. The simulation encompassed 24 h of traffic flow on the nine evacuation routes assuming 90% flow efficiency. The model assumed that there was an unlimited number of vehicles ready to enter the simulation in all counties. The time headway between entering vehicles was considered to be normally distributed with a mean of 3 s and a standard deviation of 1 s. The simulation verified our model Implementation Requirements For optimal performance of our model Evacuees must follow the evacuation routes. The State of South Carolina should notify specific communities or households which route to take Flow must be monitored on all evacuation routes; this requires metering entry of evacuees onto the evacuation routes. Allowing vehicles to enter an evacuation route too quickly may result in congestion at bottlenecks Advance notification that there will be ticketing by photograph could en- force the restriction on towing boats and trailers, which might otherwise be Applying the e mode Requirement 1 If an evacuation order included both Charleston and Dorchester counties 24 h prior to the predicted arrival of a hurricane, it would be necessary to reverse all four lanes of I-26 to ensure the evacuation of the entire population of the two counties. In our simulation runs all of the exit routes from charleston and Dorchester ran at full capacity(all lanes reversed, 90% of maximum flow for 24 h to evacuate the counties completely. If the lanes are not reversed, it is doubtful that the two counties could evacuate in a timely fashion Requirement 2 To optimize use of the available bandwidth while ensuring that the entire population is displaced inland within 24 h, we opted for a simultaneous evac uation strategy: All counties begin evacuation at the same time Since hurricanes typically arrive in South Carolina moving northward, a staggering strategy would evacuate southernmost counties first. Our model
Project H.E.R.O. 261 The Simulation To confirm the feasibility of our model, we conducted a computer simulation using Arena simulation software. The simulation encompassed 24 h of traffic flow on the nine evacuation routes assuming 90% flow efficiency. The model assumed that there was an unlimited number of vehicles ready to enter the simulation in all counties. The time headway between entering vehicles was considered to be normally distributed with a mean of 3 s and a standard deviation of 1 s. The simulation verified our model. Implementation Requirements For optimal performance of our model: • Evacuees must follow the evacuation routes. The State of South Carolina should notify specific communities or households which route to take. • Flow must be monitored on all evacuation routes; this requires metering entry of evacuees onto the evacuation routes. Allowing vehicles to enter an evacuation route too quickly may result in congestion at bottlenecks. • Advance notification that there will be ticketing by photograph could enforce the restriction on towing boats and trailers, which might otherwise be ignored. Applying the Model Requirement 1 If an evacuation order included both Charleston and Dorchester counties 24 h prior to the predicted arrival of a hurricane, it would be necessary to reverse all four lanes of I-26 to ensure the evacuation of the entire population of the two counties. In our simulation runs, all of the exit routes from Charleston and Dorchester ran at full capacity (all lanes reversed, 90% of maximum flow) for 24 h to evacuate the counties completely. If the lanes are not reversed, it is doubtful that the two counties could evacuate in a timely fashion. Requirement 2 To optimize use of the available bandwidth while ensuring that the entire population is displaced inland within 24 h, we opted for a simultaneous evacuation strategy: All counties begin evacuation at the same time. Since hurricanes typically arrive in South Carolina moving northward, a staggering strategy would evacuate southernmost counties first. Our model