Locating Fire Protection Services the Location Set Covering
Model
1. Locating fire protection services: the location set covering model One problem faced by many communities is where to locate fire stations. Even though most people do not want to live next to a station, they do want fire protection services nearby. The value of fire services is time critical. If a crew at a station takes more than 10 minutes to reach a house fire, there are significant chances that the fire will consume major portions of the house and threaten occupants. Most fires can be easily put out with a timely response with the right equipment and crew. The trick is to make a quick response before a fire gets out of control. Sometimes the occupant can contain the fire with water or an extinguisher, but fires can get out of hand very quickly. After a fire has been detected and it can’t be put out with a simple maneuver, then the person is best to notify the fire department, help evacuate others and fight the fire only when they do not place themselves at risk. To protect people and structures, it is necessary to establish a network of stations with appropriate equipment so that all areas of a city can be reached from the nearest station within a short distance, say one and a half miles, or a maximal response time of say 8 minutes. If a station is within a maximum response distance or time of a neighborhood, then we say that the station “covers” that neighborhood. Many cities in the United States have fire station networks that “cover” all areas of the city within easy reach. Typically a city is divided into small zones, called fire demand zones. Each zone is a small geographically contiguous area, or neighborhood. There may be hundreds of such zones. Each zone is represented by a geographically centered point. The center point of the zone is used to represent the zone and is often defined at a central intersection within the zone. Since the zone is usually quite small, travel times across the zone are quite small. It is assumed that if the center point of a
References: for models involving a covering objective Batta, R., and N.R. Mannur (1990). “Covering-Location Models for Emergency Situations that Require Multiple Response Units.” Management Science 36, 1623. Beasley, J.E. (1987). “An Algorithm for the Set Covering Problem.” European Journal of Operational Research 31, 85-93. Church, R., and C. ReVelle (1974). “The Maximal Covering Location Problem.” Papers of the Regional Science Association 32, 101-118. Church, R.L., and J.R. Weaver (1986). "Theoretical Links Between Median and Coverage Location Problems." Annals of Operations Research 6, 1-19. Chvatal, V. (1979). “A Greedy Heuristic for the Set-Covering Problem.” Mathematics of Operations Research 26, 233-235. Location Theory & Modeling 21 R.L. Church Current, J., and M. O’Kelly (1992). “Locating Emergency Warning Sirens.” Decision Sciences 23, 221-234. Daskin, M. (1983). “A Maximum Expected Covering Location Model: Formulation, Properties and Heuristic Solution.” Transportation Science 17, 4869. Daskin, M.S., K. Hogan, and C. ReVelle (1988). “Integration of multiple, excess, backup, and expected covering models.” Environment and Planning B: Planning and Design 15, 15-35. Downs B.T., and J.D. Camm (1996). “An Exact Algorithm for the Maximal Covering Problem.” Naval Research Logistics 43, 435-461. Eaton, D.J., R.L. Church, V.L. Bennett, B.L. Hamon, and L.G.V. Lopez (1981). “On the Deployment of Health Resources in Rural Valle Del Cauca, Colombia.” TIMS Studies in the Management Sciences 17, 331-359. Hogan, K., and C. ReVelle (1986). "Concepts and Applications of Backup Coverage." Management Science 32, 1434-1444. Plane, D. R., and T.E. Hendrick (1974). “Mathematical programming and the location of fire companies for the Denver fire department,” Management Scinec Report Series, University of Colorado, Bolder, Colorado. (also published in Operations Research). Roth, R. (1969). "Computer Solutions to Minimum-Cover Problems." Operations Research 17, 455-465. Toregas, C. (1970). "A Covering Formulation for the Location of Public Service Facilities." M.S. Thesis, Cornell University, Ithaca, NY. Toregas, C. (1971). "Location Under Maximal Travel Time Constraints." Ph.D. Dissertation, Cornell University, Ithaca, NY. Toregas, C., and C. ReVelle (1972). "Optimal Location Under Time or Distance Constraints." Papers of the Regional Science Association 28, 133-143. Toregas, C., and C. ReVelle (1973). "Binary Logic Solutions to a Class of Location Problem." Geographical Analysis 5, 145-155. Underhill, L. (1994). "Optimal and Suboptimal Reserve Selection Algorithms." Biological Conservation 70, 85-87. Location Theory & Modeling 22 R.L. Church