NATIONAL BUREAU OF STANDARDS REPORT

10 833

FIRE SERVICE LOCATION-ALLOCATION MODELS

Prepared for

The Fire Research Program

National Bureau of Standards

U.S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
NATIONAL BUREAU OF STANDARDS

The National Bureau of Standards1 was established by an act of Congress March 3, 1901. The Bureau’s overall goal is to strengthen and advance the Nation’s science and

technology and facilitate their effective application for public benefit. To this end, the

Bureau conducts research and provides: (1) a basis for the Nation’s physical measure- ment system, (2) scientific and technological services for industry and government, (3) a technical basis for equity in trade, and (4) technical services to promote public safety.

The Bureau consists of the Institute for Basic Standards, the Institute for Materials

Research, the Institute for Applied Technology, the Center for Computer Sciences and

Technology, and the Office for Information Programs.

THE INSTITUTE FOR BASIC STANDARDS provides the central basis within the

United States of a complete and consistent system of physical measurement; coordinates

that system with measurement systems of other nations; and furnishes essential services

leading to accurate and uniform physical measurements throughout the Nation’s scientific community, industry, and commerce. The Institute consists of a Center for Radiation Research, an Office of Measurement Services and the following divisions: Applied Mathematics—Electricity—Heat—Mechanics—Optical Physics—Linac

Radiation2—Nuclear Radiation2—Applied Radiation2—Quantum Electronics3—

Electromagnetics3—Time and Frequency3—Laboratory Astrophysics3—Cryogenics3

. THE INSTITUTE FOR MATERIALS RESEARCH conducts materials research lead- ing to improved methods of measurement, standards, and data on the properties of

well-characterized materials needed by industry, commerce, educational institutions, and

Government; provides advisory and research services to other Government agencies;

and develops, produces, and distributes standard reference materials. The Institute consists of the Office of Standard Reference Materials and the following divisions: Analytical Chemistry—Polymers—Metallurgy—Inorganic Materials—Reactor

Radiation—Physical Chemistry.

THE INSTITUTE FOR APPLIED TECHNOLOGY provides technical services to pro- mote the use of available technology and to facilitate technological innovation in industry and Government; cooperates with public and private organizations leading to the

development of technological standards (including mandatory safety standards), codes

and methods of test; and provides technical advice and services to Government agencies

upon request. The Institute also monitors NBS engineering standards activities and

provides liaison between NBS and national and international engineering standards

bodies. The Institute consists of the following divisions and offices: Engineering Standards Services—Weights and Measures—Invention and

Innovation—Product Evaluation Technology—Building Research—Electronic

Technology—Technical Analysis—Measurement Engineering—Office of Fire

Programs.

THE CENTER FOR COMPUTER SCIENCES AND TECHNOLOGY conducts re- search and provides technical services designed to aid Government agencies in improving cost effectiveness in the conduct of their programs through the selection, acquisition,

and effective utilization of automatic data processing equipment; and serves as the principal focus within the executive branch for the development of Federal standards for

automatic data processing equipment, techniques, and computer languages. The Center

consists of the following offices and divisions: Information Processing Standards—Computer Information—Computer Services —Systems Development—Information Processing Technology.

THE OFFICE FOR INFORMATION PROGRAMS promotes optimum dissemination

and accessibility of scientific information generated within NBS and other agencies of

the Federal Government; promotes the development of the National Standard Reference

Data System and a system of information analysis centers dealing with the broader

aspects of the National Measurement System; provides appropriate services to ensure

that the NBS staff has optimum accessibility to the scientific information of the world,

and directs the public information activities of the Bureau. The Office consists of the

following organizational units: Office of Standard Reference Data—Office of Technical Information and

Publications—Library—Office of International Relations.

1 Headquarters and Laboratories at Gaithersburg, Maryland, unless otherwise noted; mailing address Washington, D.C. 20234.

2 Part of the Center for Radiation Research.

3 Located at Boulder, Colorado 80302.
NATIONAL BUREAU OF STANDARDS REPORT

NBS PROJECT

4314162 April 1972

NBS REPORT

10 833

FIRE SERVICE LOCATION-ALLOCATION MODELS

Donald Coiner

David Gilsinn

Approved: jAtVyf

Technical Analysis division

IMPORTANT NOTICE NATIONAL BUREAU OF STA

for use within the Government. B and review. For this reason, the whole or in part, is not authoriz Bureau of Standards, Washington

the Report has been specifically p

Approved for public release by the

Director of the National Institute of

Standards and Technology (NIST)

on October 9, 2015.

> accounting documents intended

ubjected to additional evaluation

listing of this Report, either in Office of the Director, National

the Government agency for which

pies for its own use. <NBS>

U.S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS

ABSTRACT

This paper compiles the various types of location-allocation

models which analyze the impact of varying the number and location

of fire stations. The assumptions of each model, the relationships

between models, and possible heuristics and algorithms are discussed.

In addition, a methodology of spatial concepts analogous to those

used in transportation planning is presented.

TABLE OF CONTENTS

Page

1.0 INTRODUCTION ~T~

1.1 Purpose of Report 1

1.2 The Problem 2

1.3 Report Content 4

2.0 MAJOR LOCATION-ALLOCATION STUDIES 5

2.1 Val insky 5

2.2 Jane Hogg 7

2.3 East Lansing 10

3.0 LOCATIONAL CONCEPTS 13

3.1 Concept of Unit 13

3.2 Concept of Jurisdiction 14

3.3 Concepts of Demand Zones and Focal Points 20

4.0 LOCATION MODELS 24

4.1 Initial Assumptions 25

4.2 Weighted Time Models 28

4.2.1 Basic Model 29

4.2.2 Availability Model 30

4.2.3 Multiple Dispatch Model 33

4.3 Time Constraint Model 34

4.4 Balanced Workload Model 37

5.0 MODEL HEURISTICS AND ALGORITHMS 39

5.1 Complete Enumeration 39

5.2 Maranzana Heuristics 40

5.2.1 Application to Models II, IIC 40

5.2.2 Application to Models IV, IVC 42

5.3 Model V Algorithm 47

5.4 Model VI Heuristics 49

6.0

SUMMARY 52

1.0 INTRODUCTION

1.1 Purpose of Report

The purpose of this report is to provide such technical people

as operations researchers, mathematicians, and planners with a

perspective on analytical approaches to the fire station location

problem.

The objective is to present generic classes of location-allocation

models which use different objective functions as indicators of the

level of service provided. This paper does not provide a detailed

state-of-the-art review on location theory, since there are adequate

reviews in the literature. In particular, the paper by Revel le, Marks,

and Liebman—^ presents a general survey of the literature through

1969. To detail the various facets of fire service activities

goes beyond the scope of this report, but the interested reader

can gain some appreciation of the extensive and involved functions

2 / performed by fire departments by consulting their training manuals.—

T7— C. Revelle, D. Marks, and J. Liebman, "An Analysis of Private and

Public Sector Location Models," Management Science, Vol. 16,

No. 11, 1970. —^See, for example:

a. J. F. Casey, (Ed.), The Fire Chief’s Handbook , Third Edition,

New York: The Reuben H. Donnelley Corp, 196$.

b. L. W. Erven, Fire Company Apparatus and Procedures , Beverly Hills,

California: (jlencoe Press, 1969.

1
1 . 2 The Problem

City governments are being faced with new and greater demands for

public services at the same time as the cost of providing such services

is steadily increasing. There are some indications, as noted in Table 1,

that the fire service function is appropriating an increasingly larger

portion of the overall city budget. Consequently, there is a pressing

need for tools to analyze the delivery of fire services and find means

to increase their efficiency and effectiveness.

As cities grew from small communities , new facilities for fire services were gradually added at heavy demand points. Consequently, the

fire stations often are not optimally located for the city as it currently

exists. Similarly, as different parts of the city decay and suffer a

negative growth rate, there is a need to re-examine the locational pattern

of facilities.

Some method, more objective than the widely accepted usage of insurance ratings, by which a city can assess the adequacy of its level of

fire protection is urgently needed. A necessary part of an objective

approach would be the consideration of where facilities should be located

and a measurement of the level of service provided, as a function of the

number of the facilities and their current locations. The models which

address the above problem are called location-allocation models . The

difficulties of location-allocation analysis are dual. First, what is

meant by "level of service" or "effectiveness" of the fire department

must be defined. Second, analytical means must be found to assess the

benefits of different locational patterns.

2
Table 1

3/ Fire Department Budget

: 1967, 1970

(Selected Cities of 100,000 or over Population)

1967

F.D. Budget

% of

General

1970

F.D. Budget

% of

1970 1970 Salaries

F.D. Expenditure % of

City Revenue General Revenue (in thousands) F.D.

Chicago, 111. 10 12 $ 68,478 98

Los Angeles, Cal. 12 12 62,348 98

New York City, N.Y. 3 4 233,296 100

Atlanta, Ga. 8 10 8,544 89

Pittsburgh, Pa. 10 13 11,181 98

St . Louis , Mo8 9 12,211 98

Washington, D. C. 3 4 22,683 94

Cincinnati, Ohio 5 5 11,215 96

Long Beach, Cal. 7 10 8,137 96

Miami, Fla. 13 19 7,619 100

Portland, Ore. 16 14 8,857 95

San Jose, Cal. 10 12 6,855 87

Wichita, Kan. 12 12 4,445 91

Baton Rouge, La. 12 10 3,246 89

Columbia, S.C. 15 18 1,391 94

Lansing, Mich. 27 13 3,325 91

Montgomery, Ala. 21 19 2,503 96

Richmond, Va. 5 7 5,620 77

Wichita Falls, Tex. 7 8 962 92

3 / — International City Management Association, The Municipal Year Book

Washington, D. C., 1967, 1971.

3
1.3 Report Content

This report consists of six sections including the introduction.

Section 2 gives brief summaries of three historic location-allocation

studies. These studies demonstrate that the difficult problem of

how many fire stations a city should have and where they should be

located has received attention from the OR profession for a long

time.

Section 3 determines what is to be located, (facilities,

companies , equipment, or men) , and provides a terminology for

spatial characteristics to be used in the models. Section 4 describes

several different types of location models ; Section 5 discusses

methods of providing solutions to these models. Section 6 summarizes

the contributions of this paper.

4
2.0 MAJOR LOCATION -ALLOCATION STUDIES

This section describes three location-allocation studies which

represent milestones in the application of location theory to the fire

services. The Valinsky study was done in the early 1950’s for the city

of New York. It used the A. I. A.— schedule as a constraint to determine

the number and location of fire stations, supplemented by: (a) a crude

hazard analysis, (b) availability analysis, and (c) a historical analysis

of extreme situations of resource utilization to determine the risk of all

units being used simultaneously. Jane Hogg’s contribution was the use of

an analytical model based upon network travel times and weighted demand

points to locate stations. The Berlin -Santone study developed methodologies

for (a) evaluating different location patterns, (b) hazard assessment, and

(c) service districting.

2 . 1 Valinsky’s Study

In 1951 David Valinsky was assigned to New York City’s Mayor's

Committee on Management Survey to examine the efficiency of fire company

locations and determine whether or not statistical methods could usefully

be applied to the entire problem of location. — The American Insurance Association Standard Grading Schedule for

determining the level of fire protection in a city. See: "Standard

Schedule for Grading Cities and Towns of the United States with Reference

to their Fire Defenses and Physical Conditions," National Board of Fire

Underwriters, New York, Chicago, San Francisco, 1956, with 1963 and 1964

Amendments

The Standard Schedule is also reproduced in the 1969 Municipal yearbook , op . cit . , page 1

5
The study consisted of four major tasks. First, Valinsky referenced the A. I. A. Standard Grading specifications for the location of

apparatus and constructed an initial set of locations for the distribution

of engine and ladder companies in New York that met the A. I. A. specifications.

Since these standards were based primarily on the size of the areas to be

protected with little consideration of such characteristics as population

density and high-rise structures, the general A. I. A. specifications had

to be reconsidered in the light of local conditions of special concern from

a fire protection point of view.

The second task in the study was an analysis of burnable material

concerning the physical characteristics of structures and the special fire

hazards of their occupancies . A block-by -block study of the entire area

was required in order to determine the special characteristics which

differentiate areas of similar geographic proportions as to their inherent

risk potential. This phase of the study demonstrated that the distribution

of companies as initially deteimined by the A. I. A. specifications was not

totally adequate to meet the requirements of certain high hazard areas

.

Additional companies were located in such areas.

The third part of the study statistically analyzed the work load of

the companies in order to determine the expected availability of the

companies initially placed in the first two parts of the study. The geographic distributions of work performed were determined by studying the

average number of runs, sizeable fires, and amount of time spent at work

per year. Next, the amount of time at work and out -of- quarters was

calculated, and the distribution of fire incidence by time and borough of

6
New York was detemined. Averages and absolute ranges of indicators

of work performance such as the relation of unnecessaiy* alarms to working alaims by area were deteimined, as was the time consumed in runs.

The study resulted in more companies being added to the ones located in

the first two phases.

The final phase of the study was an analysis of the problems of

mass response. In particular, consideration was given to probabilistic

questions of the form "What might happen?". These questions led to

studying:

1. The distribution of multiple alaims

2. Fire losses

3. Fire fatalities

4. Probabilities of extreme fire situation.

The study deteimined the density of alarms area-by-area and hour-byhour, and evaluated the historical and anticipated incidence of multiple

alarms with high loss potential. The probabilities inherent in these high

loss situations were computed and resulted in the repositioning of some

companies

2.2 Jane Hogg f s Study

In 1958, the Home Office, London, England, received a request from

Glasgow, Scotland, to help plan fire station locations. Since central

Glasgow was to be virtually flattened and rebuilt by the 1980 f s, nearly

*' Unnecessary alaims" include malicious false alaims, good intent alarms,

and accidental alaims

7
all of the stations were to be relocated. Therefore, there was a wide

choice of possible station locations.

Jane Hogg, of the Scientific Advisor’s Branch, Home Office, chose

the objective function of minimizing the total -journey-time of all the

engines traveling to fires, including both first responding engines and

any reinforcements

.

Jane Hogg points out—^ that the response time to a fire depends on

at least three factors:

1. Where the fire occurs; i.e., the pattern of fire

incidence

2. Where the nearest station is located

3. The type of road network, and possible travel speed

along the network.

The study first designated a large number of possible (initial) sites

for stations, determined in such a way that political constraints were

satisfied. The sites were fairly evenly scattered over Glasgow. Hogg chose

to locate only one engine per location in order to obtain a lower total

joumey-time.

— Jane M. Hogg, ’’The Deployment of the Fire Services in Glasgow in 1980,”

Needs of the Fire Services, Proceedings of a Symposium Oct. 1968, The

Committee on Fire Research, Div. of Eng., National Research Council,

National Academy of Sciences, Washington, D. C. , (1969).

Jane M. Hogg, ’’The Siting of Fire Stations,” Operational Research

Quarterly , Vol. 19, No. 3, 1968, pp. 275-287,

Jane M. Hogg, ”A Distribution Model for an Emergency Service: Masters

of Science Thesis,” University of London, Imperial College of Science

and Technology, Sept. 1970.

8
Next, she created a map depicting the projected incidence pattern

in 1980, obtained through a regression analysis associating fire

incidence with residential and working class populations. The map

of the city was then divided into subareas composed of several one

square kilometer cells of the map grid. She formed as many subareas

as were feasible, yet large enough so that there would be a sufficient

number of fires to enable the frequency distribution of engines called

for service to be estimated.

Topographical features such as rivers, canals, and railway lines

were considered in the creation of the subareas wherever they appeared

to be barriers to passage. These boundary lines represented lines

of low fire incidence. Furthermore, each of the possible station

sites was identified with a particular subarea.

Once the subareas had been delineated, the center of gravity

of calls for each of the subareas was determined, and the travel

(or journey) time between the subareas and all possible station

locations was computed.

Jane Hogg determined those locations from the whole set of

possible sites which were best for the total number of engines (in

this case 41) . She then eliminated the one site which increased the

total response time by the least amount. There were now 40 engines.

i This procedure was repeated. The previously rejected site (number 40)

was compared with each of the retained sites. If an exchange would

minimize the total -journey-time, then one was made. The same analysis

was repeated for station number 39 and the procedure continued until

no sites were rejected.

9
2 . 3 East Lansing Study

Early in 1968, the International City Managers’ Association, the

American Society of Planning Officials , the Fels Institute at the University

of Pennsylvania, and the Technical Analysis Division of the National Bureau

of Standards initiated a Housing and Urban Development Department sponsored

project to consider the applicability of systems analysis to the resolution

of urban problems. The objective of the project was to demonstrate how

city staffs, given adequate technical assistance and guidance, could use

the methods of systems analysis to solve their particular problems. A

study was conducted in East Lansing, Michigan, to show how systems analysis

could be applied to solving planning problems in fire departments. In

particular, a computer model was developed by the Technical Analysis

Division and the city’s staff—^ as a tool for the city to use in planning

the number and locations of fire stations.

The city staff and NBS analysts agreed that response time was an

important factor to consider in planning the location of fire stations. It

was determined that response time could be reduced both by increasing the

number of fire stations and by strategically locating individual fire stations within their districts of responsibility.

The model, as developed, did not rigorously determine the number of

fire stations required; however, it provided a means to evaluate the effectiveness of a particular configuration of fire district boundaries . The

- Louis Santone and Geoffrey Berlin, ’’Location of Fire Stations,” Systems

Analysis for Social Problems, Washington Operations Research Council^

1970, pp. 81-91

.

10
7 / effort was essentially a districting procedure,— rather than strictly

a location procedure. The model outputs give infoimation helpful in

determining boundary changes which might lead to a better balanced

coverage by the fire stations

The city of East Lansing was described by a highway network consisting of nodes and links, and by an indexed listing of all structures. Each

structure was associated with one of the nodes of the network and represented a potential source of demand. The candidate fire station locations

to be evaluated were located at a subset of the network nodes.

The study team developed an approach to explicitly rank alternative

fire station locations. Once the specific locations had been chosen, the

model would evaluate the objective function and detemine service districts.

The objective function was based on a combination of travel times from the

proposed fire station locations to the node of demand and the demand for

fire protection at these nodes.

The travel times were estimated on the basis of shortest path travel

throughout the street network. The demand for service at each node was

defined as the sum of the demands at each individual structure assigned to

a node. The demand for service at each structure was defined as the product

77— The methodology of districting has been used in political nonpartisan

voter redistricting. See, for example:

a. S. W. Hess, J. B. Weaver, H. J, Siegfeldt, J . N. Whelan and P. A. Zitlan,

'’Nonpartisan Political Redistricting by Computer , ' ' Operations Research , Vol. 13, No. 6, 1965, pp. 998-1006.

b. Crond, Inc., BEDIST, Version 5.3, Program Description and User Manual , National Municipal League, New York, N.V., 1967.

11
of the probability that a fire would occur in that structure during a

given interval of time (for example, a year), and the expected loss that

would result from the fire. The probability of a fire occurring was

estimated from fire history data and a regression model that included

such variables as age, size, and construction type of buildings. The

number of people at risk and the value of the building and contents was

implicit in these variables . A similar approach was used to estimate the

expected losses. Since the available data concerning losses to property

referred to losses that occurred after a certain response time, travel

time from the known fire station was incorporated as a variable in the

function predicting the amount of loss.

The project team hypothesized a linear form for the demand for service

at individual buildings, but made no attempt to define expected damage.

Instead, the function was intended to reflect the relative importance of

providing rapid response to a fire in a particular building. The variables

in the linear function were determined by members of the city staff and

analysts from the National Bureau of Standards. The values of the coefficients were determined, at a two -day session attended by city and fire department personnel, by ranking the importance of protecting typical structures

such as schools, churches, and single family dwellings on a value scale.

A set of linear equations was formulated relating the average judgement

value to the characteristics of each structure.

12
3.0 LOCATIONAL CONCEPTS

In order to develop location-allocation models, it is necessary to

discuss what is to be located and what spatial characteristics need to

be considered.

3.1 Concept of Unit

Some writers assume that it is the fire station that must be

located—^, some assume that it is the fire company, and still others the

9/ engine companies.—7 These may be entirely different problems to fire

departments. One fire station, for instance, may contain several pumper

and ladder companies

Using a functional breakdown of fire department services, the following three categories of basic units are defined:

1. Fire Suppression Unit (FSU) - That unit of apparatus,

usually called an engine or pumper, complete with assigned

manpower, however configured (i.e., numbers of men assigned),

in a particular jurisdictional area, whose primary function

is the control and extinguishment of fires.

— L. C. Santone, G. Berlin, Location of Fire Stations, Presented at WORC

Symposium on "Systems Analysis for Social Problems,” May 26-28, 1969 . Also see National Bureau of Standards Report #10 093.

9 / — D. Valinsky, MA Determination of the Optimum Location of Fire Fighting

Units In New York City,” Operations Research , Vol. 3, 1955, pp. 494-512.

E. Nilsson, J. Swartz, ’’Applications of Systems Analysis to the Alexandria,

' Va. Fire Department,” NBS Report 10 454, January, 1972.

13
2. Fire Rescue Unit (FRU) - That unit of apparatus, usually

called a ladder or a truck, whose primary function is the

rescue of persons from sites above the first floor level.

3. Special Support Unit (SSU) - That unit of personnel or

special apparatus and equipment used to support the FSU

and FRU in conducting their missions.

Pumper companies, however, often conduct salvage, overhaul, and rescue

activities in addition to fire suppression. Similarly, ladder companies

10 / often do ventilation, salvage, and overhaul. —- The motivation for formulating the definitions was to abstract the basic functional units from the

various particular apparatus and manpower configurations.

3.2 Concept of Jurisdiction

It is assumed that a fire department serves a bounded geographical

jurisdiction made up of contiguous subareas separated by natural or man-made

boundaries . A jurisdiction is defined as a bounded geographic area that may

or may not be internally separated by such things as mountain ranges, rivers,

or railroad tracks

.

X07 ; — Ventilation, salvage, overhaul, and rescue are technical fire department

terminology. Ventilation is the planned and systematic removal of smoke,

gases, and heat from a structure. Salvage refers to the covering or

removal of goods which may be damaged by fire or water. Overhaul refers

to the practice of searching for any sparks, embers, or fire that may

remain in a building, or in any structure, place, or thing that may have

been subject to a fire. Rescue refers to extracting and caring for persons trapped and/or injured in structures, vehicles, traffic accidents,

train wrecks, airplane crashes, floods, wind storms, and earthquakes.

14
Natural barriers may divide a geo-political region into areas

which the fire department views as unconnected. To illustrate this

point, a hypothetical city and county will be described. Figure 1 shows

Phoenix County (hypothetical) divided by a river and a mountain range.

Frequent flooding in the spring and summer prevents fire apparatus

from using the bridges often enough that the fire department will not

consider an engine company on one side of the river as offering

protection to the other side. The mountain range cannot be crossed

in less than fifteen minutes. Therefore, the two sides of the river

may be considered as disconnected for the purpose of locational analysis,

and a separate location study performed for each side of the river.

Finally, suppose the region of the county below the mountain range

is essentially divided into two areas because of a lack -of connecting

roads. Each of the above considerations makes it either necessary

(as in the case of the Smoky River) , or desirable (from the computational

point of view) , to analyze each of these areas separately. The

geographical divisions described above might be appropriate in

rural county jurisdictions which do not have mutual aid agreements

with surrounding jurisdictions.

A region can also be divided for analysis into areas with

qualitatively different fire problems. Figure 2 illustrates the

situation in Sparks City (hypothetical) . The downtown part of the

city contains many high-rise buildings which necessitate ladders and

rescue equipment, as well as a large capacity for water delivery.

15
Area II

Phoenix County

Division into Areas on the Basis of Political and Natural Boundaries

Without Mutual Aid
Area II

Boundary between fire

protection areas

Figure 2

Sparks City

Division into Areas on the Basis of Qualitatively Distinct Firefighting Problems

Without Mutual Aid

17
The companies in the industrial area, on the other hand, need foam

capability and larger water supplies than the residential part of the

city. The area divisions in this example affect the locational

analysis in the sense that a greater importance will be assigned

to one area than another. As Figure 2 indicates, Sparks City

is affected by both a geographical division, and the qualitative

fire problem division. An analyst might perform two location analyses

in this example, one for each side of the river. On the side of the

river containing Areas I and III, he would perform a single location

analysis, weighting the demands from Area I in a different manner

from those of Area III. (For the example, that such weightings can

be determined will be assumed.)

The previous examples have indicated two ways (quantitative

or geographic) of partitioning jurisdictions for locational analysis.

A jurisdiction, as in Sparks City’s case, may require both divisions

applied to its problems.

If Phoenix County and Sparks City have a mutual aid agreement

which makes the nearest engine company responsible for responding

to alarms without regard to geo-political boundaries, analysis areas

which cross political boundaries are feasible. This situation might

be partitioned as in Figure 3.

18
Division into Areas that Cross Political Boundaries

With Mutual Aid

19
Although the references to Phoenix County and Sparks City are

entirely hypothetical, such instances are typical. For example,

Dade County, Florida, exhibits some of these problems. Dade County

consists of 27 jurisdictions without central dispatch to all areas,

so that individual jurisdictions cannot always rely on mutual aid.

A further complication arises from the causeways across to Miami

Beach which have draw bridges. The fire departments must consider

the possibility of a draw bridge being raised at a critical time;

namely, when a fire engine is responding to an alarm.

3. 3 Concepts of Demand Zones and Focal Points

It is necessary to develop means for specifying the spatial

distribution of demand for service within a given jurisdiction.

The models in this paper are based on the two concepts of fire

service demand zones and focal points.

A demand zone represents an area of the city with relatively

homogeneous land use. The demand for fire service for the zone is

assumed to occur at one point called the focal point. The concepts

of fire service demand zones and focal points are analogous

to the concepts of traffic demand zones amd centroids used in the

transportation sciences

.

These concepts can be made operational in the following manner:

1. The ultimate size of the fire demand zone should be related

to a non-critical travel time. For example, if the city

considers that 30 seconds is a critical response time, the fire

demand zone should not be larger than 30 seconds driving time.

20
2. A fire demand zone can be a single complex of buildings;

e.g. , a factory producing or using hazardous materials,

a church or a hospital, or an area of relatively homogeneous

structures.

3. The focal points are chosen to be points within the fire

demand zone representing the principal hazard for that

zone, or the centroid of the zone computed by weighting

all hazards in the zone. A hospital, as a significant

entity within a residential area, could be treated in two

ways. First, an area of the residential community containing

the hospital satisfying the travel time criteria for that

particular city could be marked off, and the focal point for

that zone placed at the hospital. Second, the hospital

may be treated as a separate fire demand zone within another

fire demand zone representing the residential area. In this

case, two focal points would be placed, one at the hospital

and another, perhaps at the centroid, for the residential area.

4. A street network is assumed to exist for the jurisdiction,

and a focal point will generally be a node of the street

network

5. A measure of importance is associated with, each focal point.

Different measures are needed for various models. For example,

the measure could be the number of calls for service originating

at the focal point, or a sum of the different types of calls

weighted by the hazard to life or property represented by that

type.

21
The resource and time constraint models will require

a measure which gives a maximum travel time from the

nearest facility to the focal point, or a measure

requiring K basic suppression units to respond within

L minutes.

Figure 4 illustrates how fire demand zones and focal points

might appear in the residential area of Sparks City without mutual

aid (see Figure 2). The fire demand zones, , Z^, Z^, Z^, Z^, Z^,

each have a focal point, f^, f

2

> f^, f^, fg, f^. This is only an

illustration of how one area could be partitioned. For example, the

high value area of Sparks City may have much smaller fire demand

zones, possibly on the order of a block in size, indicating the

importance of a response to the associated focal points.

22
Figure 4

Fire Demand Zones and Focal Points in Sparks City

Shopping Center

Farm Community

Gas Stations in a Suburban Community

Church in Farm Community

Grain Storage Elevator

Farm Community

23
4 . 0 LOCAT IONAL MODELS

This section describes the major variations of location models

proposed for fire suppression unit location and provides a discussion

of how they relate to each other.

First, an initial list of assumptions to be used in the models

is presented. The remaining subsections discuss variations of the

basic weighted-time model, time constrained models, and balanced

workload models, respectively.

All of the models considered share several general characteristics.

All of the models rely on the response times of the units involved,

rather than on their response distances as used in the A. I. A. Standard

Grading approach. The response time in the models will notationally

be identified by , where T^ refers to the shortest average travel

time from facility location j to the focal point of fire demand

zone i. These times can be generated by applying shortest path

algorithms to specific city street networks.

The models evaluate alternative locations of a finite number

of existing and potential fire suppression unit locations in terms

of the given objective function. The locations are assumed to be

coincident with nodes in the city’s transportation network. Finally,

all of the models weight the fire demand zones by the degree and type

of hazards represented by the land use pattern of the zones. Some

of the models employ the weights directly in the function to be

optimized,while others employ weights implicitly as time constraints.

24
4.1 Initial Assumptions

This section furnishes a fundamental list of the assumptions

made in applying the location models. Additional assumptions

necessary for some of the models are discussed in context. ii/

(a) Each fire suppression unit is assigned to one station

at a fixed location (node) , and that unit responds to

all calls for service from its assigned station.

Consequently, the models considered in this report do

not apply to units which respond to an alaim while on

patrol, or from any other place than their fixed location.

(b) The units are assumed to be indistinguishable and

equivalent.

(c) The units are indivisible. In many fire departments,

the fire suppression units consist of more than one

piece of apparatus. In some situations, the unit can be

split and each of the sub-units used at a different

location. This tactic is particularly useful in

fighting brush fires and fires where there is exposure

to other buildings. The models described in this paper,

however, assume that each unit will be engaged in its

entirety, at a single location. — The assumptions will be lettered (a) , (b) , etc. , so that the required

assumptions for a particular model can be referred to by letter and need

not be repeated.

25
(d)

(e)

(f)

(g)

A given fire demand zone focal point is served from

the closest unit. This assumption represents the

usual practice of the fire services.

Alarms, or calls for service, will originate from a

finite collection of focal points, f^, i=l, 2, ..., n,

(n being the total number of focal points chosen to

represent the fire demand zones)

.

Potential locations for the basic fire suppression units

are restricted to a finite set of points in the network

denoted by e . , j = 1 , 2 ,

. .

.

,

m, called stations (or

more precisely, "potential fire station locations”)

.

Generally 9 m <_ n.

The travel -time Ty > 0, required for a unit at e_. to

respond to an alarm at the focal point f^ , is known

for all ij . These travel times are illustrated in

Figure 5.

26
Figure 5

Basic Fire Suppression Unit Response Times

£. = Locations of the focal points

for the fire demand zones,

i = 1, 2, 3, 4, 5, 6 = Proposed fire station location

T. . = Time from to f.

ll 1 i

27
4.2 Weighted Timed Models

All of the models in this section attempt to minimize the disutility

associated with selection of stations for a given number of serving units

.

If fj is to be served by a unit at e^ , the disutility associated with this

assignment is assumed to be of the form:

W.T. . 1 rj

where is some measure of the importance of providing a rapid response

at f^. In particular, it is assumed for those models with a disutility

function that:

(h) = the expected number of alarms at the focal point f^

over a specified length of time, for example, a year.

The "disutility" is also linear in T^

.

To facilitate the exposition, it is necessary to introduce some

notations. In particular, for the location of M units (where M is the

actual number of basic fire suppression units to be located) from m

possible locations, e^ , j = 1, 2, . .

.

,

m, M < m, and one unit is to be

assigned to each location.

There are ^ subsets of the set {e^ : j = 1, 2, ..., m} consisting

of M distinct elements, that is, the number of different ways of choosing

M locations from m possible sites. For notational purposes let

TTTZ

(TM) is the binomial coefficient: (m-M)TMT

28
th

Let E^ represent the k subset of the M subsets (i.e., k indexes

a particular subset, called E^, of the set {e^ : j = 1, 2, m}, where

k = 1, 2, M ) . The subsets E^ are each distinct. For notational

purposes let

th

e^' = the j element in subset E^.

4.2.1 Basic Model

First consider a very special case in which a fire department jurisdiction, represented by n focal points, {f . ; i = 1, 2, ..., n} is to be

served by a single FSU stationed at one of m possible locations, (e^; j = 1,

2, ..., m}. If it is assumed that alarms occur at such times that the fire

suppression unit is always available when required, then the unit can be

located by determining that location among the m possible choices which

will satisfy

n

Min l W.T. .

[Model I]

1<_ j<_ m i=l 1

It is clear that in this special approach (Model I) it is assumed that

as well as (a-h)

,

(i) A fire suppression unit is available whenever one is required.

(j) Only one unit is required to respond to each alarm.

This model may seem naive, but it is appropriate for many small communities in the United States.

29
A logical r.-den: ion ol Model I is the location ol several fire

Mippn

( ot a 1

Thus

,

.sion mills. I

; o i (Ins model, assumptions (a

(ravel time I'm l he M basu fire suppression

tho objective I miction of Model II is:

n Min V W,

i=i

1 Min IT.,

I K

j ) are used and the

units is m i n i mi zed

.

[Model III

This model is relevant to residential communities with a high resource

a\ a i I abi lily, low > I rue til re density, and low I i le and property hazards.

(liven the restricting .'0- sump t ions ol Model ll, two constraints on

(hr model are obvious; nameLy, the assumptions that the closest unit is

available, and that only one unit responds to each alarm. The next sub

section di cusses a procedure lor relaxing the lirst assumption.

.| . .! . Avti liability Mode I

this lo nrni 1 a t i on use:, the locations determined by the basic model

and divides the region to he served into districts, each served exclusively

b) one station. The districts, aie determined so as to minimize the total

expected travel time.

darter, Chaiken, and Ignall have constructed a simple model in which

the nearest unit is not assumed to be always available. Their model dos

tribes a region served by two units at fixed locations I and 1 as il distracted in Figure t>. In addition to the previous assumptions (ah), (j),

they assume that:

fk) The arrival of alarms is a Poisson process.

30
(l) The mean service time is independent of the location of

the alarm and the basic fire suppression unit servicing

the alarm.

(m) A part of the region R (Figure 6) has been identified as

the district assigned to a unit located at 1. The district

assigned to unit 1 will be called A, the district assigned

to unit 2 will be referred to as B. Furthermore , these

two units are assumed to be dispatched according to the

following rules:

(1) The two units will respond only to alarms

in the region.

(2) A unit, if available, will respond to all

alarms in its own district.

(3) A unit, if available, will respond to an

alarm in the other unit’s district whenever that unit is unavailable.

(4) When both units are unavailable, alarms

will be served by units outside of B.

Let there be no focal points in region B. Ihen, under the previous

assumptions. Carter, et al., showed that the area for focal points) to

be included in district A to minimize the total expected travel time is

31
Figure 6

Response Region for Two Units

32
n A = <

X

X-y

where

X = mean arrival rate of alarms

y = mean service time.

n

I W.

i=i 1

n

I i=l

T.,) W.}

\ 2

J 1

[Model III]

This model is not directly applicable to most resource location

problems because of the limitation on the number of units considered. 13/

4.2.3 Multiple Dispatch Model

In this section, a model will be discussed which relaxes the assumption that only one unit is required on all alarms. If the assumptions of

(II) are modified to allow for a probability a second unit will be

required at f^, and the unit will be available when required, the total

travel time for a given number of units can be minimized by stationing

these units at the locations which satisfy:

n

Min

1 < k < M — — m

l M min {T

1=1 r

ik. I e. , ek

£ Ej^, r + s} . r s

[Model IV]

—/.New results relaxing this constraint have been announced by Chaiken

and Larson at the 40th National ORSA meeting, October 27-29, 1971,

ORSA Bulletin, p. B238. However, these results are not yet published.

33
14/ Model IV includes assumptions (a-j),

7 and the new assumption:

(n) A second basic fire suppression unit may be required on

an alarm at f^. The probability of requiring the second

unit on an alarm at ffis designated by q^.

Model IV could clearly be extended to include probabilities that

three or more units are required for each alarm.

4.3 Time Constraint Models

The conventional approach to the fire station location problem is

given by the A. I. A. standards which require that a station be located

within a given number of miles of each focal point. (The required distances may vary with the ’Value” of the fire demand zone.) Therefore,

models which constrain the maximum allowable distance between a fire

15/ demand zone and its serving unit(s) are of interest. Mitchell— suggests

one feasible approach to modeling these constraints taking time rather

than distance into consideration.

Assume that there is a maximum allowable travel time associated with

each focal point:

(o) T^ = Maximum time constraint for a response to f^, i = 1, 2, ..., n.

In order to insure compliance with these constraints, define a penalty

function, G, in the following manner:

f 0 if t< T.

G(i, t) =

( a if t> T. ; where a, is a large value.

55^Under assumption (i) , the assumption is implicitly included that the

first and second nearest units are available whenever required. —V. S. Mitchell, "Efficient Allocation of Fire Department Resources,"

Fire Technology , (1971)

,

pp. 327-242.

34
This penalty function can be appended to the objective function in

Models I, II, or IV, in order to create time constrained versions of

these models as follows:

(IC) Min l (WT

G(i, T )).

1< j <m i=l 1 ^

Assumptions for (IC) : (a-j), (o)

n

(IIC) Min

1< k<M — — m

I Wi MinIT. k

+ G(i, T. k ) 1=1

J J

e

k.

£ E

k

}

Assumptions for (IIC): (a-k) , (o)

n

(IVC) Min l W. Min{T- k

+ q^T., + G (i, Ta ) I ^ } ev e E,, r f s}

1< k<M

m

i=l 1 1K

r

1 1K

s

1 r K

r ks k

Assumptions for (IVC) : (a-k) , (n,o)

Model IVC could be extended by appending a second penalty function

associated with the travel time of the second closest basic fire suppression

unit, T^

k

. Furthermore, alternative functional forms for the penalty

s function G could be analyzed in place of the {o, a} function.

A different approach to the time constraint model has been suggested

by Toregas, et al .—

—^Toregas, ReVelle, Swain, and Bergman, ,TThe Location of Emergency Service

Facilities Operations Research , Sept. -Oct., (1971).

35
They formulate the problem as locating the minimum number of fire

suppression units in order to insure that each focal point, f^, lies

within a prespecified service time b^. In particular, define:

b^ = the upper bound on the initial response time of a first

due unit to focal point f^, where i = 1, 2, n.

The objective of this approach is to minimize the number of units required

to satisfy the time constraints.

In order to formulate the model f additional definitions are required:

U = the set of possible unit locations

Y. = 1 if a unit is located at e. and 0 otherwise

,

J J where e. e U.

J N. = (j c U T. . < b. }, i = 1, 2

ij - i

’ ’

. , n, and T. . is the

shortest path time from focal point f^ to unit location e^ . N is not an empty set for all i.

The problem of identifying the minimum number of unit locations which

17/

can provide the desired level of unit service can be formulated as: —

n

Min l Y.

j=l J

subj ect to l Y . _> 1 , i = 1 , 2 ,

. . .

,

n

jeN

i

3

where Y^ = 1 or 0, for j = 1, 2, ..., n.

The assumptions for Model V are (a~g) , (i) , and (o)

.

[Model V]

—^A similar formulation has been suggested to the authors by Dr. William

Horn, Applied Mathematics Division, National Bureau of Standards.

36
4.4 Balanced Workload Model

The balanced workload model attempts to balance the workloads while

minimizing the total travel time. The general problem (of selecting M

locations from a set, E, of m possible locations) is usually unsolvable.

The first model formulated below is a feasibly solvable problem.—

The general idea is to begin with a fixed set of M locations. For the

purposes of notation, let E represent the fixed set of locations. The

problem to be solved is to determine the fraction of the workload at

each focal point, f . , to be assigned to unit j. In particular, this

model makes assumptions (a-1) and in addition it assumes:

Cp) workload at f^is proportional to W^.

The model requires the following definitions:

= weight associated with the workload at focal point

f

2. > i 1 ^ >

• • • » ^ > T^ . = shortest average route time between focal point

and unit j in E^,

Y. . = the fraction of the workload at focal point f

ij i

assigned to unit j in Eq.

The problem can be formulated:

n M

Min 7 l

T. . W. Y. .

,

[Model VI]

Ti j=i

^ 1 ^

jj/y. Srinivasan and G . l\ Thompson, ’’A. Fortran V Code for Transportation

Algorithms, M Graduate School of Industrial Administration, Carnegie -Mellon

University, Pittsburgh, Pennsylvania, June 1971.

37
subject to

M

l Y. . = 1 , i = 1, 2, . n,

3-i J

n

I i=l

W- Y. . =

i ij

1 n

M 2.

i=l

W.

l

3 - 1 , 2 M.

The problem that is usually unsolvable but which describes the

general locational problem can be formulated in the notation of Model

VI where:

Ty = shortest average route time between focal point

f. and unit j in E,

i

J 9

Y. . = the fraction of the workload at focal point

1J

X

3

f^ assigned to unit j in E,

1 if a unit is located at j ,and 0 otherwise.

The new problem can be formulated as a quadratic program:

n m

Min Y 7 T. . W. Y. . X.

i=i j=i ^ 1 ^ j

[Model VII]

subject to

m

I Y. . X. = i , i = 1, 2, n,

j=l J J m

I X f M,

3=i J

n , n

Y W. Y. . X. = 4 y W. , i = 1, 2

i

:

1

i iJ 1 M 1

9 * .. , m.

38
5.0 MODEL HEURISTICS AND ALGORITHMS

Each of the models discussed above can be associated with an

algorithm or a heuristic which will select locations for the units according to their respective criteria. In spite of the large number of models

presented, a small number of solution techniques can accommodate all of

them.

These techniques are:

1 . Complete enumeration

2. Maranzana heuristic

3 . Integer Programming

4. Transportation Algorithm.

5.1 Complete Enumeration

When the number of choices is small, it is feasible to calculate the

value of the objective function for each of the alternatives. This approach

has been used by Berlin and Santone—^ in applying Model I . Note that in

Model I the number of alternatives is m; i.e., the number of possible locations at which to locate the one unit.

Complete enumeration, where feasible, has an important advantage over

more sophisticated computational procedures for identifying the optimum

locations. If the value of the objective function is computed for each of

—^L. C. Santone, G. Berlin, Location of Fire Stations Presented at WORC

Symposium on "Systems Analysis for Social Problems," May 26-28, 1969.

See also National Bureau of Standards Report #10 093.

39
the alternatives, the alternatives can be ranked. In doing this not

only the best choice is identified, but also the second, third, and

fourth best choices and differences in the value of the objective function among these choices

.

It should be noted that Models II, IIC, IV, AND IVC may also be

solved by complete enumeration as long as M , the number of alternatives

,

does not get so large as to make the required number of computations too

time consuming.

5 . 2 The Maranzana Heuristic

5.2.1 Application to Models II, IIC

Several authors have suggested the use of a heuristic developed by

Maranzana— for models such as Model II.—/ The heuristic consists of

locating basic fire suppression units at an arbitrary initial selection

of M of the m stations, then partitioning the focal points into districts

such that all points in a district are served from the same location.

7(77 —' F. E. Maranzana, H0n the Location of Supply Points to Minimize Transport

Costs," Operations Research Quarterly , 15, (1964), pp. 261-270. —^Also see Richard Jordan, et al . , Systems Analysis of Inland Consolidation

Centers for Marine Cargo, NBS TechnicaT Note #*530, Nov. 19707

This report uses a Maranzana type approach and presents an extensive

analysis of using different starting centers and different types of

constraints. The running times on a UNIVAC 1108 computer were of the

order of 1-3 minutes per iteration for a problem of 1400 shippers, 12

inland centers, and 3 ports.

Also see Arnold Weber, Documentation of LOC Models, (NBS Report to be

published), for experience in using these approaches.

40
Next, for each district the set of possible station locations is examined

to determine if the value of the objective function in that district can

be reduced by selecting one of the alternative locations for the unit

serving the district, (Model I). Finally, if new locations are chosen

for some of the units, the redistricting is repeated and the process is

continued until it fails to recommend new locations for the units. More

precisely, with respect to Model II, the heuristic consists of the following steps:

1 . Initialize

Make an initial arbitrary selection of M of the possible

station locations {e.}1?,, say = {e^ | j = 1, 2, ..., M}.

2

District

Assign each f^ to one and only one of the M serving basic fire

suppression units in order to form districts . Let p be an index representing one of the units. Form the p-th district as follows: Define

D = {f.

P i

T

il i

T

il , J = 1, 2, ..., M},

P j

where p

= 1, 2, . .

.

,

M. That is, assign each focal point to the nearest

serving unit. Futhermore, suppose that unit location e^ is associated

with district D , e , is associated with D

? , etc. If some focal point

1 1

2

should be equidistant from two or more units, arbitrarily assign this point

to the district of the unit that appears first in the list.

41
3 . Move

Examine the set of possible unit locations {e^}? _ ^ for a new

set of M locations which best serve each district D , p = 1. 2. .. . M.

p

> r > f

• • • >

• This is done by choosing the locations in order to satisfy:

(*) Min T W.T. .

.

1< j <m f.eD 1 13 ~~ 1 p

This procedure may be accomplished, by a complete enumeration. Let E^ be

the set of M new unit locations which satisfy condition (*)

,

where

E

2 = {e2

I j = 1, 2, ML

j

4. Terminate

If the unit location has been changed in any of the districts,

return to step 2, otherwise stop.

5.2.2 Application to Models IV and IVC

In this section, a variation on the Maranzana heuristic is presented

which is applicable to Models IV and IVC discussed in Section 4.4. In

order to make this extension of the heuristic, it is necessary to supplement

the concept of district D , defined above. In this section, D will be

referred to as the ’’first-due district,” and the ’’second-due district,” is

2 defined as D . In an intuitive manner, a second-due district can be

P

thought of as a set of next nearest focal points to a basic suppression

unit, say unit 1. Thus, they would be a set of focal points falling in

42
the first-due district of some other fire suppression unit, say unit 2,

but closer to unit 1 than to units 3, 4, . .

.

,

M. Formally, define

0^^, p

= 1, 2, . .

.

,

M, as follows:

2

DP-LJ-p = {f: |f= i D and for some p", (p'^ p, l<p'<M), f.eD , and IP

T

ip 1

T

ir > O t V', 1 <r <M)>.

Although this is a foimal mathematical definition, it can be given

an operational interpretation. A focal point belongs to the second

2 due district of some unit indexed p, provided:

1. f^ is not in the first due district of the unit p, but falls

in the first due district of some other unit p"r D

’ p

5 where p" f p,

2. the following condition on the response times to focal

point f^ is satisfied:

T. < T. ,< T. .

,

ip - ip - ij >

where j e {1, 2, M}, {p, p"}.

Figure 7 displays an intuitive pictorial view. The figure depicts

three units located at points 1, 2, 3, in a circular jurisdiction with

distances measured by straight lines. The associated first-due districts,

D^, Dp Dp are delineated by the solid lines. The second due district for

2 unit 1, Dp is represented by the shaded area. Thus, the shaded area in D^

is nearer to unit 1 than to unit 3, and the shaded area in D^ is nearer to

43
unit 1 than to unit 2. Similar shadings could be constructed for units

2 and 3.

Using this definition the Maranzana heuristic can be reformulated

to apply to Model IV:

Step 1 . Initialize

Make an arbitrary selection of M possible unit locations from

the possible locations {e^}TM^. As before, designate this set as

E

1 =

^ e

lj I j = M}. These will be the initial locations for the

M units.

Step 2 . District

For each unit p, p

= 1, 2, M, partition the focal points

into first -due districts

D

P

= { h I Vi i

T

ii.> j = 2 > •••> M} >

where is the first-due district for unit p, p

= 1, 2, ...,M.

Also, partition the focal points into second-due districts—

D = (f. I f. ft D and for some p", (p^ p, 1 < p' < M) , f. e D

p l'l^p > i p

and T. < T.

ip — lr

(r f p " , 1 <r< M) }

.

227

; —-Again, it is necessary to consider the case in which a focal point is

^ equidistant from two or more units in order to ensure that the (also D ) sets partition the focal points. When this is the case, this focal point

is arbitrarily assigned to the unit with the smallest unit number p.

44
Figure 7

First and Second-Due Districts

1 , 2 , 3 : Unit Locations

D, , D

?

, D^: First-Due Districts for

Ujiits 1, 2, 3, respectively

2

D-^ : Second-Due District - Unit 1

45
Step 3 . Move

As in Section 4.2.1, look for an alternative location for

each unit. Unit p will be moved to a new location if there is some station

in the list {e . which reduces the value of the objective function for

J J- 1

J the points served by unit p. This objective is given by

(**) Min ( I W T + l 2

W q T )

1< j

< m f.e D

1 1 J f.eD^ 1 1 ^ ~ J 1 Ip f.e D

i P

Let be the set of M new unit locations which satisfy condition (**)

,

where

^2 ^ e

2

I j ~ M}

.

j

2 2 Again is associated with and Dp e ? , is associated with D

2

and D^,

1 2

etc., and if f > then move unit e^ to e

2

P P P P

23/

Step 4. Reiterate

If none of the units have been moved in step 3, the heuristic

terminates, otherwise, return to step 2 and continue.

As with the Maranzana algorithm this heuristic does not necessarily

achieve an absolute minimum for the objective function. It does achieve

some form of a ’’local” minimum.

737 ; -—Again, care must be taken that the objective function e

2

is less than

P

the value of the objective function at e^ and not equal. Otherwise

P

the heuristic may cycle and not converge.

46
This heuristic may also be applicable to Model IV with condition

(**) replaced by the new objective

(***) Min

1 <j <m

c l

f.eD

i P

[W.T. . 1

G(i, T. .)] ij l 2

f

i

eD

p

W.q.T. 0 iHi xy

However, it is possible that this heuristic will fail in step 2. In fact,

the value of the objective function in (***) may be infinity for all

possible locations for one of the units. This may occur in cases where

there is a solution for Model IVC with no finite value of the objective

function. This difficulty may be overcome by replacing the arbitrary selection of initial locations in step 1 with an initial selection of locations

based on Model V. This can be accomplished to insure a finite value for each

of the objective functions (***) for some values of M. A computational procedure for accomplishing this will be explained in the next section.

5.3 Model V Algorithm

Toregas , ReVelle, Swain, and Bergman (see footnote 16) describe a

simple algorithm for solving Model V in some of the cases where the number

of units required to serve each focal point is one. Their algorithm consists of applying a linear program to Model V, with additional cuts if

necessary:

Step 1: Let the problem be described by:

n

Min l y.

,

j=l J

47
subj ect to £ j>_l, i-l»2,

j eN. J 1

where y • = 1 or 0 for j — 1, 2, •••> ri, and

N-, i = 1, 2, .

n

have been defined as in section 4.3

1

24/

Step 2 : Apply a linear program to the problem.

Step 3 : If the solutions y_. are all integers, the problem is

solved. If one or more of y. are not integers, define Mq, the number

of units required, by

n

If Mq is an integer while one or more of the

y^

are non- integral

,

the algorithm fails to produce a solution to Model V. (Toregas , et al.,

report never encountering this situation in their experience with the

algorithm.

)

If M

q

is not an integer, add an integral cut to the problem.

The new problem is:

n

Minimize £ y.

j=l J

subject to l y. > 1, y-^0 for each i

jeN. 3 1

J 1

1, 2, . . • j n,

n

and l y. >_ [M_] + 1,

j-1 J

where [Mq] is the largest integer which is smaller than Mq. Continue

the algorithm by repeating steps 2 and 3.

This algorithm cannot continue indefinitely since on each iteration

n n

l y. must increase beyond the next integer greater than £ y-,

j=i 3 j=i 3

but cannot increase beyond m. —i^Toregas, et al., report that a mathematical programming code is available

for an IBM ^360,

48
5.4 Model VII Heuristic

One approach to Model VII has been suggested —^ which makes

direct use of the transportation problem. In this formulation,

begin by assigning a portion of the workload (Wj_) of each

focal point to each of the possible fire station locations ,e^

,

which constrain the utilization of each location. This can be

accomplished by solving the transportation problem for the values

of W. • which:

il

n m

minimize 5* I T. .W. . i=l j=l u V

n

subject to 7 W. . = W. for each i

jh 1

1 y 2 y

• • • ,n

n

, 5 „ l w. and > W. . < . S i

- 11 — 1=1

i=l J M

Define the cost of this system of m fire stations to be

n m

D = y y T. .W. . , m ii ij i=l 3=1 J J

where the values of the have been determined by solving the

transportation problem.

—/ By Dr . George Suzuki, Technical Analysis Division, National Bureau of

Standards

49
One method of solving Model VII would be to compute the costs,

k m

D , k = 1, 2, (j^) , associated with each subset containing M of the

possible fire station locations using the method described by Srinivasan

25/ and Thompson—- . The set of M locations of least cost solves Model VII.

However, this approach may prove impractical because of the computation

times required. For example, if a problem requiring the selection of the

best 10 out of 20 possible locations takes ten seconds to evaluate each

possibility, it would take 21 days to evaluate all of the possibilities.

As a result, it is necessary to investigate heuristics for solving

Model VII.

One method for arriving at a set of M stations consists of first

solving the transportation problem for the m stations as described above,

and defining the utilization

n

U. = T W.

.

3 i=l ^

associated with each location. The set of possible locations is reduced

by eliminating the least utilized location. This procedure is repeated

on the remaining m-1 locations until only M stations remain.

Another heuristic for Model VII was programmed by Crond, Inc. This

program is referred to as REDIST,—^ and the general steps of the

heuristic are given as follows: —/ See footnote 18. — CROND , Inc. RED! ST, Version 3.3

? Program Description and User Manual . Copies can be obtained from National Municipal League, 47 E. 68th St.

,

New York, N.Y.

,

10021.

50
1 . Estimate the initial locations of the units to be placed.

2. Use a transportation algorithm to assign focal points to

fire suppression units in order to minimize the sum of

the weighted response times. This is the districting step.

3. Adjust these assignments so that each focal point lies

entirely within one unit district. This process usually

destroys the equal distribution workload, but uniquely

defines districts.

4. Reassign focal points between districts in order to

improve workload equality.

5. Compute new unit locations within each district as new

trial locations. The program returns to step 2 until the

solution converges.

51
6.0 SUMMARY

The objective of this paper has been to compile and review tools

that can be used in locating fire suppression units. The specific

contributions of this paper are:

1. A methodology of spatial concepts to use in

locational analysis

.

2. A specification of different types of locationallocation models and their assumptions.

3. A discussion of how each type of model relates

to the others.

4. Discussions of heuristics and algorithms to be

used with the models

.

An analyst concerned with fire suppression unit locations should

be able to select the type of model most appropriate to his particular

problem. In addition, it is hoped that the paper will stimulate work

on more efficient algorithms and on relating the locational problems to

overall resource allocation problems.

52
BIBLIOGRAPHY

1. Bishop, Robert L., George L. Peterson, and Geoffrey N. Berlin,

'Towards A Methodology for Evaluation of Fire Protection Systems

In Appalachia," Socio-Econ. Plan. Sci., Vol. 5. (1971)

pp. 145-158. ~~

2. Carter, Grace and Edward Ignall, "A Simulation Model of Fire

Department Operations: Design and Preliminary Results," The New

York City Rand Institute, R-632-NYC, December, 1970.

3. Carter, Grace M. , Jan M. Chaiken and Edward Ignall, "Response Areas

for Two Emergency Units," The New York City Rand Institute,

R- 53 2 -NYC/HUD, March, 1971.

4. Chaiken, Jan M. and Richard C. Larson, "Methods for Allocating

Urban Emergency Units," The New York City Rand Institute,

R-680-HUD/NSF, May, 1971.

5. Chaiken, Jan M. and Richard C. Larson, "Methods for Allocating

Urban Emergency Units: A Survey," New York City Rand Institute.

6. Cooper, Leon, "Location-Allocation Problems ," Operations Research,

Vol. 11, (1963), pp. 331-343.

7. Cooper, Leon, "Solutions of Generalized Locational Equilibrium

Models," Journal of Regional Science , Vol. 7, No. 1, (1967).

8 . CROND , Inc . , Conflicts Among Possible Criteria for Rational

Districting , (1969)

9. CROND, Inc., REDIST 3.3, Program Description and User Manual , (1969).

10. Garfinkel, R. , "Set Covering: A Survey," presented at the XVIII

International Conference of the Institute of Management Sciences,

London, July, 1970.

11. Garfinkel, R. S. and G. L. Nemhauser, "Optimal Political Districting

by Implicit Enumeration Techniques," Oper. Res. 17 , (1969), pp. 848.

12. Garfinkel, R. S. and G. L. Nemhauser, "The Set Partitioning Problem:

Set Covering with Equality Constraints," Operations Research, 17,

(1969), pp. 838-856.

13. Goldman, A. J. and C. J. Witzgall, "A Localization Theorem for

Optimal Facility Placement," Transportation Science, Vol. 4, No. 4,

(1970), pp. 406-409.

53
14. Goldman, A. J. , "Approximate Localization Theorems for Optimal

Facility Placement," Paper FA3.5, 40th ORSA meeting, Oct., 1971.

15. Hakimi, S. L. , "Optimum Locations of Switching Centers and the

Absolute Centers and Medians of a Graph," Operations Research, 12,

(.1964) , pp. 450-459.

16. Hakimi, S. L. , "Optimum Distribution of Switching Centers in a Communications Network and Some Related Graph -Theoretical Problems,"

Operations Research , 13, (1965), pp. 462-475.

17. Hess, S. W. , J. B. Weaver, H. J. Siegfeldt, J. N. Whelan, and

P. A. Zitlan, "Non-Partisan Political Redistricting by Computer,"

Presented at Joint TIMS-ORSA Meeting, Minneapolis, Minnesota,

October 7, 1964.

18. Hogg, Jane M. , "The Siting of Fire Stations," Operational Research

Quarterly , Vol. 19, No. 3, pp. 275-287. _

19. Hogg, Jane M. , "The Development of the Fire Services in Glasgow

in 1980," Needs of the Fire Services, Proceedings of a Symposium

Oct. 1968, The Committee on Fire Research, Div. of Eng., National

Research Council, National Academy of Sciences, Washington, D. C.

,

(1969)

.

20. Larson, Richard C., "Response to Emergency Units: The Effects of

Barriers, Discrete Streets, and One-Way Streets," The New York City

Rand Institute, R-675-HUD, April, 1971.

21. Larson, Richard C. and Keith A. Stevenson, "On Insensitivities in

Urban Redistricting and Facility Location," The New York City Rand

Institute, R-533-NYC/HUD, March, 1971.

22. Maranzana, F. E., "On the Location of Supply Points to Minimize

Transport Costs," Operational Research Quarterly, Vol. 15, (1964),

pp. 261-270.

23. Mitchell, Phillip S. , "Efficient Allocation of Fire Department

Resources - Part I^"Fire Technology , (1971), pp. 237-242.

24. "Needs of the Fire Services," Proceedings of a Symposium, October,

1968, The Committee on Fire Research, National Research Council,

National Academy of Sciences.

25. Pierce, John, "Application of Combinatorial Programming to a Class

of All-Zero-One Integer Programming Problems," Management Science , Vol. 15, No. 3, (1968), pp. 191-206.

54
26. Revelle, C. and R. Swain, "Central Facilities Location,"

Geographical Analysis , Vol. 2, No. 1 (1970), pp. 30-42.

27. Revelle, Charles, David Marks, and Jan C. Liebman, "An Analysis

of Private and Public Sector Location Models," Management Science,

Vol. 16, No. 11 (1970), pp. 692-707.

28. Salzberg, F., A. J. Pintar, F. J. Vodvarka, "Description of Urban

Areas for Fire Analysis," Final Report, Contract No. DCA-8, I IT

Research Institute, Chicago, March, 1965.

29. Santone, Louis C. and Geoffrey N. Berlin, "A Computer Model for the

Evaluation of Fire Station Location," NBS Report No. 10093, National

Bureau of Standards , (1969)

30. Santone, Louis C. and Geoffrey Berlin, "Locations of Fire Stations,"

Systems Analysis for Social Problems, Washington Operations Research

Council, (1970), pp. 81-91.

31. Srinivasan, V. and G. L. Thompson, "A Fortran V Code for the

Transportation Algorithm," Graduate School of Industrial Administration,

Carnegie -Mellon University, Pittsburgh, Pa., June, 1971.

32. "Standard Schedule for Grading Cities and Towns of the United States

with Reference to their Fire Defenses and Physical Conditions,"

National Board of Fire Underwriters, New York, (1956 edition).

33. Toregas, Constantine and Charles ReVelle, "Optimal Location Under

Time or Distance Constraints," The 1970 North American Meeting of

the Regional Science Association, Ann Arbor, Michigan, November, 1971.

34. Toregas, C, C. ReVelle, "Location in Space and Time" presented at the

North American Meeting of Regional Science Association, November, 1971.

35. Toregas, ReVelle, Swain, and Bergman, "The Location of Emergency

Service Facilities," Operations Research , Sept. -Oct., (1971)

36. Valinsky, David, "A Determination of the Optimum Location of Fire

Fighting Units in New York City," Operations Research, 3, (1955),

pp. 494-512.

55
. i