'RENCE

STATES ENTOF ERCE

\TION

NBS TECHNICAL NOTE 774

/

Location-Allocation Models

U.S.

TMENT

OF

WIERCE

Jational — au

of

ds

753

3
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 — Mechanics — Heat — Optical Physics —

Linac Radiation - — Nuclear Radiation - — Applied Radiation - — Quantum

Electronics ;l — Electromagnetics ' — Time and Frequency '' — Laboratory

Astrophysics '' — Cryogenics 3

. 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 a Center for Building Technology and the following

divisions and offices: Engineering and Product Standards—Weights and Measures—Invention and

Innovation—Product Evaluation Technology—Electronic Technology—Technical Analysis—Measurement Engineering—Building Standards and Code Services4—Housing Technology4 —Federal Building Technology4—Structures, Materials and Life Safety4—Building Environment4—Technical Evaluation and

Application4—Fire Technology.

THE INSTITUTE 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.

1 Part of the Center for Building Technology.
M r—<$ OF ST

£>3

7 S3

17<J

Fire Service

Location-Allocation Models

Donald Coiner and David Gilsinn

Institute for Applied Technology

^t{<^/ National Bureau of Standards

Washington, D.C. 20234

£-

NBS Technical Notes are designed to supplement the Bureau's regular publications program. They provide a means for making available scientific data that are of

transient or limited interest. Technical Notes may be

listed or referred to in the open literature.

5< °>4,

U.S. DEPARTMENT OF COMMERCE, Frederick B. Dent, Secretary

NATIONAL BUREAU OF STANDARDS, Richard W. Roberts, Director

Issued June 1973
National Bureau of Standards Technical Note 774

Nat. Bur. Stand. (U.S.), Tech. Note 774, 46 pages (June 1973) CODEN: NBTNAE

For sale by the Superintendent of Documents, U.S. Government Printing Office, Washington, D.C. 20402 (Order by SD Catalog No. 03.46:774).

Price $0.75 domestic postpaid or $0.50 G.P.O. Bookstore
TABLE OF CONTENTS

Page

1.0 INTRODUCTION 1

1.1 Purpose of Report 1

1 .

2

The Problem 2

1 .

3

Report Content 2

2.0 MAJOR LOCATION-ALLOCATION STUDIES 4

2.1 Valinsky's Study 4

2.2 Jane Hogg's Study 5

2.3 East Lansing Study 7

3.0 LOCATIONAL CONCEPTS 9

3.1 Concept of Unit 9

3.2 Concept of Jurisdiction 10

3.3 Concepts of Demand Zones and Focal

Points 13

4.0 LOCATIONAL MODELS 17

4.1 Initial Assumptions 17

4.2 Weighted Time Models 18

4.2.1 Basic Model 20

4.2.2 Availability Model 21

4.2.3 Multiple Dispatch Model 24

4.3 Time-Constrained Models 24

4.4 Balanced Workload Model 26

5.0 MODEL HEURISTICS AND ALGORITHMS 29

5.1 Complete Enumeration 29

5.2 The Maranzana Heuristic 29

5.2.1 Application to Models II, IIC. . 30

5.2.2 Application to Models IV, IVC . . 31

5.3 Model V Algorithm "... 3 5

5.4 Model VII Heuristic 26

6.0 SUMMARY 3 9

REFERENCES 40
LIST OF TABLES

Page

Table 1. Fire Department Budgets, 1967, 1970 3

LIST OF FIGURES

Figure 1. Phoenix County, Division into Areas on

the Basis of Political and Natural

Boundaries Without Mutual Aid 11

Figure 2. Sparks City, Division into Areas

on the Basis of Qualitatively

Distinct Firefighting Problems

Without Mutual Aid 12

Figure 3. Phoenix County and Sparks City,

Division into Areas that Cross

Political Boundaries With Mutual

Aid 14

Figure 4 . Fire Demand Zones and Focal Points

in Sparks City 16

Figure 5. Basic Fire Suppression Unit Response

Times 19

Figure 6. Response Districts for Two Units 22

Figure 7. First and Second-Due District 33
FIRE SERVICE LOCATION-ALLOCATION MODELS

Donald R. Coiner

David E. Gilsinn

This paper compiles the various types of locationallocation 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.

Key words: Algorithms; fire station location;

heuristics; location-allocation models; location

analysis; resource allocation analysis; transportation network analysis.

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 locationallocation 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 Revelle, Marks, and

Liebman [1] * 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 performed by fire departments by

consulting their training manuals [2]

.

figures in brackets indicate the literature references at

the end of this paper.

1
1.2 The Problem

City governments are being confronted 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.

Therefore, 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 facilities and their current locations. The models

which address this problem are called location-allocation

models. The difficulties of location-allocation analysis

are dual. First, what is meant by the "level of service" or

"effectiveness" of the fire department must be defined.

Second, analytical means must be found to assess the relative

benefits of different locational patterns.

1.3 Report Content

This report consists of six sections including the introduction

Section 2 gives brief summaries of three historic locationallocation 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 continued

attention from the OR profession.

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.
Table 1

Fire Department Budgets [3]

1967, 1970

City

1967 F.D. 1970 F.D. 1970 Fire 1970

Budget % Budget % Expenditures Salaries

of General of General (in % of F.D

Revenue Revenue thousands) Budget

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, Mo. 8 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
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. [4] 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 study consisted of four major tasks. First, Valinksy

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

materials 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 intially

determined 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-ofquarters was calculated, and the distribution of fire incidence

by time and borough of New York was determined. Averages

and absolute ranges of indicators of work performance such

as the relation of unnecessary 2 alarms to working alarms by

area were determined, as was the time consumed in runs.

As a result, more companies were 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. Various indices were studied, including:

1. The distribution of multiple alarms

2. Fire losses

3. Fire fatalities

4. Probabilities of extreme fire situation.

The study determined the density of alarms by geographic

location and time of occurrence, 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's Study

In 1958, the Home Office in 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, there was a wide choice

of possible station locations.

Jane Hogg, of the Scientific Advisor's Branch of the Home

Office, chose the objective function of minimizing the total

travel-time of all the engines traveling to fires, including

both first responding engines and any reinforcements.

"Unnecessary alarms" include malicious false alarms, good

intent alarms, and accidental alarms.

5
Hogg indicated [5] that the response time to a fire depends

on at least three factors:

1. The locale of the fire; i.e., the pattern

of fire incidence

2. The location of the nearest station

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 travel-time.

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

sub-areas 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. 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 times between the subareas and all possible station

locations were computed.

Jane Hogg determined a set of locations from the set of

possible sites which was a good choice for the total number

of engines (in this case 41) . She then eliminated the one

site whose elimination increased the total response time by

the least amount. Next, she eliminated a second site using

the same criteria. The previously rejected site was compared

with each of the retained sites. An exchange was made if it

would reduce the total travel-time. The same procedure was

repeated until the number of sites remaining equaled the

number of units to be located. On each iteration, only

single exchanges were allowed. As a result, the solution

arrived at by this procedure was not necessarily the optimum

solution.

6
2.3 East Lansing Study

Early in 1968, the International City Managers 1 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 [6] 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 effort was

essentially a districting, [7] rather than a location

procedure. The model outputs gave information helpful in

determining boundary changes which might lead to more

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 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 determine 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 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 judgment value to the characteristics

of each structure.
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, [8] some assume that it is the fire company, and

still others the engine companies [9]. 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 - That unit of apparatus,

usually called an engine or pumper, complete with

assigned manpower, in a particular jurisdictional

area, whose primary function is the control and

extinguishment of fires

2. Fire Rescue Unit - 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 - That unit of personnel or

special apparatus and equipment used to support the

other types of units in conducting their missions.

Pumper companies, however, often conduct salvage, overhaul,

and rescue activities in addition to fire suppression.

Similarly, ladder companies often do ventilation, salvage,

and overhaul. 3 The definitions are intended to abstract

the basic functional units from the various particular

apparatus and manpower configurations

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
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.

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 hypothetical Phoenix County 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 a 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 area separately.

The geographical divisions described above might be appropriate

in rural counties 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 hypothetical Sparks City. The downtown

sector of the city contains many high-rise buildings which

necessitate ladders and rescue equipment, as well as a large

capacity for water delivery. 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, it is assumed that such weightings can be

determined .

)

10
Figure 1

Phoenix County

Division into Areas on the Basis of Political

and Natural Boundaries Without Mutual Aid

Boundary between

fire protection

areas

11
Figure 2

Sparks City

Division into Areas on the Basis of Qualitatively

Distinct Firefighting Problems Without Mutual Aid

Boundary between fire protection

areas

12
The previous examples have indicated two ways (quantitative

and geographic) of partitioning jurisdictions for locational

analysis. A jurisdiction, such as Sparks City, may require

division by both methods.

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

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 drawbridges.

The fire departments must consider the possibility of a drawbridge 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 demand zones and focal points

A fire demand zone represents an area of a 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 demand zones and focal points are

analogous to the concepts of traffic demand zones and 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.

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.

13
Figure 3

Phoenix County and Sparks City

Division into Areas that Cross Political Boundaries

With Mutual Aid

Boundary

between Phoenix

County and Sparks City

Boundary between fire

protection areas

14
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.

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 2 , Z 3

, Z h , Z 5 , Z 6, each have a focal point, f 17 f z , f 3, f^, f 5 , f 6

* 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.

15
Figure 4

Fire Demand Zones and Focal Points in Sparks City

Shopping Center

Farm CommunityGas Station in a Suburban Community

Church in a Farm Community

Grain Storage Elevator

Farm Community

16
4.0 LOCATIQNAL MODELS

This section describes the major variations of location

models proposed for fire suppression unit location, and

provides a discussion of their relationships.

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.

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 T- • , 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 location

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.

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.'4

'

(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 alarm

while on patrol, or from any other place than their

fixed locations

1+ The assumptions will be lettered (a), (b) , etc., so that

the required assumptions for a particular model can be

referred to by letter rather than repeated.

17
(b) The units are 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.

(d) A given fire demand zone focal point is served

from the closest unit location. This assumption

reflects the usual practice of the fire services.

(e) Alarms, or calls for service, will originate

at a finite collection of focal points, f-j_; i=l , 2,

. .., n, (n being the total number of focal points

chosen to represent the fire demand zones)

.

(f) Potential locations for the basic fire suppression

units are restricted to a finite set of points in

the network denoted by E = {e-; j = 1, 2, ..., m}

,

called stations (or more precisely , "potential fire

station locations") . Generally, m <_ n.

(g) The travel-time Tj_- _> 0, required for a unit at e- to respond to an alarm at the focal point f j , is

known for all i and j . These travel times are

illustrated in Figure 5.

4.2 Weighted Time Models

The models in this section attempt to minimize the disutility

associated with selection of stations for a given number of

serving units. If f^ is to be served by a unit at e • , the

disutility associated with this assignment is assumed to be

of the form:

W . T . . i ID

where W. 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:

18
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

ll

Time from e-. to f

19
(h) W. = the expected number of alarms at the focal

point f. over a specified length of time,

for example a year, is known.

To facilitate the exposition, it is necessary to introduce

some notations. 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 (,.)

5 subsets of the set of possible station

locations consisting of M distinct elements; that is, the

number of different ways of choosing M locations from m

possible sites. For notational purposes let:

Let E^ represent the k subset of the M subsets of E which

consist of exactly M distinct stations. That is, k indexes

a particular subset, called Ej,, of the set {e.: : j = 1, 2, ..., m} , where k = 1, 2, ..., Mm . For notational purposes

let:

e, = the j element in subset E, . k. J k

: 4.2.1 Basic Model

First consider a special case in which a fire department

jurisdiction, represented by n focal points, {f .: i = 1, 2, ..., n}. 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

Min n

Kj<m 7 W. T. . . [Model I]

i=l

5 (..) is the binomial coefficient: ( ) = m - M M (m-M) !M!

20
Model I assumes (a-c) and (e-h) , as well as:

(i) A fire suppression unit is available whenever

one is required.

and

(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.

A logical extension of Model I is the location of several

fire suppression units. For this model, assumptions (a-j)

are used and the total travel time for the M basic fire

suppression units is minimized. Thus, the objective function

of Model II is

Min n

1 < k < M Y w. Min {T e e E }. [Model II]

i=l ik k k

j

This model is relevant to residential communities which

require large numbers of stations, and which have sufficient

resource availability to insure the validity of assumptions

(d) and (i) . Two constraints on Model II are obvious; namely, the

assumptions that the closest unit is available, and that

only one unit responds to each alarm. The next subsection

discusses a procedure for relaxing the first assumption.

4.2.2 Availability Model

This formulation uses the locations determined by the basic

model and divides the region to be served into districts, each

of which is served exclusively by one station. The districts

are determined so as to minimize the total expected travel

time.

Carter, Chaiken, and Ignall have constructed a simple model

in which the nearest unit is not assumed to be always

available. Their model describes a region served by two

units at fixed locations 1 and 2 as illustrated in Figure 6.

In addition to the previous assumptions (a-h) and (j) , they

assume that:

(k) The arrival of alarms is a Poisson process.

21
Figure 6

Response Districts for Two Units

S

ft

D, , First-Due District for Unit #i

= A, Availability District for Unit #1

= Fire Station

K = Distance of Shift in Boundary Line

22
(1) 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.

Under the previous assumptions, Carter et al . showed that the

area (or focal points) to be included in district A in order

to minimize the total expected travel time is:

A = {f . e R|T. n - T. n

< K} [Model III]

i il i2 -

where

n _-, n

K = Xn_ (I W±

) (I (T - T

i2 ) W±

) A-y i=l i=l

A = mean arrival rate of alarms

y = mean service time.

This model is not directly applicable to most resource

location problems because of the limitation on the number of

units considered. 6

6 NeW results relaxing this constraint have been announced by

Chaiken and Larson at the 40th National ORSA meeting, Oct.

27-29, 1971. However, these results have not yet been

published

23
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 Model II are modified to allow for a probability, q.j_ , that a second unit will be required at f j_

,

and that 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:

Min n

1 < k < Mm I W±

min {T. k

+ q.T. k

| ek

,eke E

R

, r ft s}.

i=l r s r s

[Model IV]

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 j_ . The probability of

requiring the second unit on an alarm at fj_ is

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-Constrained Models

The conventional approach to the fire station location problem

is derived from 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 demand zone and

its serving unit(s) are of interest. Mitchell [10] suggests one

feasible approach to modeling these constraints using time

rather than distance as a consideration.

Assume that there is a maximum allowable travel time associated

with each focal point:

(o) Tj_ - Maximum time constraint for a response to f j_ :

-J- -L, /L. f ..., II .

7Under assumption (i) , it is implicitly included that the

first and second nearest units are available whenever required

24
In order to insure compliance with these constraints, define

a penalty function, G, in the following manner:

if t < Tj_

G(i, t) =

a if t > T^; where a is a large value.

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:

n

(IC) Min I (W.T. 4

'+ -G(i, T. .))

l<j<m i=l X lj ^

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

n

(IIC) Min T W, Min {T., + G(i, T ) e, e E, }

llfcIMm i=1 3 lk

j J

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

n

(IVC) Min I W Min {T. +q-T- k +G(i, T ik ) Kk<M i=l x lK

r

1

s r — — m

S

k ' ek

£ E

k'

r * sK

r s

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., . Furthermore, alternative

s functional forms for the penalty function, G, could be

analyzed in place of the {o, a} function.

A different approach to the time-constrained model has been

suggested by Toregas , et al . [11]. 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:

25
b.: = the upper bound on the initial response time of

a first due unit to focal point f j_ , where i = 1,

The objective of this approach is to minimize the number of

units required to satisfy the time constraints.

In order to formulate the model, additional definitions are

required

U = the set of possible unit locations

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

3 e- e U. :

N. = (j e U | T . . <_ b. }, i = 1, 2, ..., 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 can provide the desired level of service

can be formulated as

n Min I Y. [Model V]

j=l :

subject to £ Y. _> 1, i = 1, 2, ...,n

:eN±

D

where Y . = 1 or , for j - 1, 2, . .., n.

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

.

4.4 Balanced Workload Model

The balanced workload model (Model VI) is a variation on the

weighted time model (Model II) . The principal difference

between these two models is the rule for determining which

fire suppression unit will respond at each of the FDZ's.

In the weighted time model this rule follows from the

assumption that an alarm is serviced from the closest unit

location. In the balanced workload model this assumption is

replaced by:

A similar formulation has been suggested to the authors by

Dr. William Horn, Applied Mathematics Division, National

Bureau of Standards.

26
(p) The workload at f^ is directly proportional to W^

,

and each fire suppression unit will be assigned the

same total workload.

The model requires the following definitions:

W. = weight associated with the workload at focal point

£•; l 1 , z r

. • . , n

,

T. . = shortest average route time between focal point f

13 and unit j at e • , where e- is location of the j-tn

unit.

Y. . = the fraction of the workload at focal point f-: 13 . '*. assigned to unit j at e .

If it is assumed that each incident represents one unit of

work for the unit servicing the incident, the expected

frequency of incidents at f^ can be used for the value of Wj_

If however, the average service time required differs significantly for the different FDZ's, a more complex interpretation

of the W ' s is required. This discussion assumes that the

number of incidents served by a unit measures the work

accomplished by that unit.

If the locations for M units are given, the problem of

drawing the district boundaries so as to minimize the total

travel time while balancing the workload can be formulated

as follows:

n M

Min V T T..W.Y.., [Model VI]

, L . , L . 1-1 1 1-1 i=l j=l

M

subject to I Y. . = 1/ i = 1 , 2, ...,n,

j=l 13

n In

I W. Y. . = - T W. , j = 1, 2, . . . , M.

. L

n 1 I] M • \ 1

J 1=1 J 1=1

where, Y. . = the fraction of the workload at focal point f^

assigned to the unit located at e •

27
The assumptions for Model VI are (a-c) , (e-j) and (p)

.

Model VI is not a location model; it is only an allocation

model. The extension of Model VI to a location-allocation

model is described below as Model VII. Model VI is solvable. 9 However, the solution may require that the workload at one or

more of f j_ ' s be divided among fire suppression units in order

to insure a balanced workload.

The extension of Model VI to a location-allocation model

requires the selection of locations for M units from a set

of m possibilities so as to minimize Model VI. The new

problem can be formulated as a quadratic program:

n m

Min J7 T. . W. Y. . X. [Model VII]

i=l j=l J J

subject to

m

V Y..X. =1; 1=1,2, . . . , n

,

j = l

m

I

X-j 1 M,

j=l

n in

I W Y . . X . < - I W, ; j = 1 , 2 , . . . , m,

i=l ± J J M i=l

where X. =1 if a unit is located at j, and otherwise

9 The solution method is discussed in Section 5.4 as the

districting step in the heuristic for Model VII.

28
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. Despite

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 possible 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 [12] 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 alternative, the

alternatives can be ranked. This process identifies not

only the best choice, but also the second, third, and fourth

best choices and differences in the value of their objective

functions

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

Several authors have suggested the use of a heuristic

developed by Maranzana [13] for models such as Model II [14]

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. 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

29
serving the district. 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

.

5.2.1 Application to Models II, IIC

More precisely, with respect to Model II, the heuristic

consists of the following steps

1

.

Initialize

Make an initial arbitrary selection,

E

1 = {e | j = 1, 2, . . ., M>

of M of the m possible station locations in E.

2

.

District

Assign each f. to one and only one of the stations in

E-, in order to form districts . Let p be an index

representing one of the units. Form the p-th district as

follows: Define,

Dp = {f il T n 1 T n ; J = 1/ 2, ..., M},

P J where p = 1 , 2, . . . , M. That is, assign each focal point

to the nearest serving unit. Furthermore, suppose that

unit location e n is associated with district D-i ; e-, , is X

l 1

2

associated with T>2'> etc. If some focal point should be

equidistant from two or more units, arbitrarily assign

this point to the district of the unit that appears first

in the list.

3

.

Move

Examine the set of possible unit locations, {e-}.

3 3=1

for a new set of M locations which best serve each district

D ; p = 1, 2, . . . , M. This is done by choosing the

locations in order to satisfy:

Min

(*) l<j<M I W. Min {T e e E }

f • e D

1 ik . k. k

1 p 3 3

30
This procedure may be accomplished by a complete enumeration

Let E ? be the set of M new unit locations which satisfy

condition (*) , where

E„ = (e

2

|j = 1/ 2, ..., M>

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

A variation on the Maranzana heuristic is also applicable

to Models IV and IVC. In order to make this extention

of the heuristic, it is necessary to supplement the concept

of district, Dn , defined above. In this section, D„, is

2

P

defined as the "first-due district," and D is defined

as the "second-due district." In an intuitive manner,

a second-due district can be thought of as a set of next

nearest focal points to a basic suppression unit, say Unit 1.

Thus, there would be a set of focal points falling in the

first-due district of some other fire suppression unit; e.g.

Unit 2, but closer to Unit 1 than to Units 3, 4, ..., M.

2 Formally, define D ; p=l, 2, . . . , M as follows:

ir

D

2

{ f .

| f • £ D

D

an<3 f or some p', (p' =j= p, 1 <_ p

f <_ M) , p i' i T P

f

±

£D , and T . , < T ir , (r + p , 1 £ r £ M) }

—

Although this is a formal mathematical definition, it can

be given an operational interpretation. A focal point f^

2 belongs to the second-due district D of some unit indexed

p, provided

1. f. is not in the first-due district D^ of the

i P

unit p, but falls in the first-due district of some

other unit p', D

p

, where p

1 =|= p,

2. the following condition on the response times to

focal point fj_ is satisfied:

T ip 1T ip'l T ij'

where j e {1, 2, ..., M>, (p^P 1 ).

31
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^ , D 2

, D 3' are delineated

by solid lines. The second due district for Unit 1, D, , is represented by the shaded area. Thus, the shaded area in

D

2 is nearer to Unit 1 than to Unit 3, and the shaded area

in D^ is nearer to 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 as follows

1

.

Initialize

Make an arbitrary selection of M possible unit locations

from the possible locations {e-} 1^^. As before, designate

this set as E^ = {e, |j = 1, 2, . .., M} . These will be the

J initial locations for the M units.

2

.

District

For each unit p p = 1, 2, ...,M, partition the focal

points into first-due districts.

D = {f I T < T , j = 1, 2, ..., M},

P J-J-p

j

where D is the first-due district for unit p; p = 1, 2, P

.'..., M. Also, partition the focal points into second-due

districts 1 °

D

2 = {f. f. £ D and for some p', (p ' ^ p, l<p'<M),

p

1 1 P — —

f. £ D , and T. ,< T. , (r^p, l<r<M)}. 1 p ip — ir' r *' - -

1 B Again, it is necessary to consider the case in which a focal

point is equidistant from two or more units in order to ensure

2 that the D (also D ) sets partition the focal points. When

p p - this is the case, this focal point is arbitrarily assigned to

the unit with the smallest unit number p.

32
Figure 7

First and Second-Due Districts

1, 2, 3: Unit locations

D, , D

2

, D_: First-Due Districts for Units 1, 2, 3,

respectively

2

D,: Second-Due District - Unit 1

33
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 the points served by unit p.

This objective is given by:

Min

(**) 1 < j < m ( I W T. + I 2 W.q-T..).

f. e D

1 1D f. £ D

X J l p i p

Let E2 be the set of M new unit locations which satisfy

condition (**) , where:

E

2 = ^ e

2

I ^ = 1 ' 2/ ' "' M ^

*

2 Again e is associated with D and D ; e , is associated

1

2

2

with D

2

and D~; etc. If e2 ^ e-, , move unit e to e . 1

1

P P P P

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.

This heuristic may also be applicable to Model IV with

condition (**) replaced by the new objective:

Min

('***) l£j<m ( I [W.T. . +- G(i, T. .)] + J W.q.T- •) . f e D

X 1D 1: f.eD„ X J i p IP

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.

l lAgain, the objective function at e

2

must be less than the value

P

of the objective function at e and not equal. Otherwise

P

the heuristic may cycle and not converge.

34
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 [11])

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 I Y-,

subject to l j _> 1 ; i = 1 , 2 ,..'., n f jeNi

where y. = 1 or for j = 1, 2, . .., n, and

3 N.; i = 1/ 2, ..., n have been defined

as in Section 4.3.

Step 2 : Apply a linear program to the problem. 12

Step 3 : If the solutions y. are all integers, the

problem is solved. If one or more of y.

are not integers, define M , the number of

units required, by:

n

j£i 3

If M is an integer while one or more of the y. are non-integral,

the algorithm fails to produce a solution to Model V. However,

Toregas, et al . , report never encountering this situation in

12 Toregas, et al , report that a mathematical programming code

is available for an IBM S/360.

35
their experience with the algorithm.

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

The new problem is

n Minimize £ y,

j=l 3

subject to 1 y .

' J >_ 1, y-. >_ for each i; i = 1,

f.i jeN.

z r. . „ / n

,

n and T y. > [Ml + 1,

where [M«] is the largest integer which is smaller than M-

.

Continue the algorithm by repeating steps 2 and 3

.

This algorithm cannot continue indefinitely since on each

n iteration \ y must increase beyond the next integer greater

j=l J n

than \ y., but cannot increase beyond m.

j=l :

5.4 Model VII Heuristic

One approach to Model VII has been suggested 1 ? which makes

direct use of the transportation problem. In this formulation, begin by assigning a portion W- of the workload (W^)

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

n m

minimize ) T T. .W.

.

i-i j=i 1D 13

1 3By Dr. George Suzuki, Technical Analysis Division, National

Bureau of Standards.

36
n subject to l W-. = W. for each i; i = 1, 2, . .., n

n n .1 W

± and 7 W. . < izi

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

n m

where the values of the W. have been determined by solving

the transportation problem.

One method of solving Model VII would be to compute the

1c m

costs, D ; k = 1, 2, ...,(..), associated with each subset ' m M

' containing M of the possible fire station locations using

the method described by Srinivasan and Thompson {15]. 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. = y 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 locations until only

M stations remain.

Another heuristic for Model VII has been programmed.

This program is referred to as REDIST [16] , and the general steps

of the heuristic are given as follows:

1. Estimate the initial locations of the units to

be placed.

37
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. Although

this process usually destroys the equal distribution

workload, it 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.

38
6 . 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 terminology 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.

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.

39
REFERENCES

[1] C. Revelle, D. Marks, and J. Leibman, "An Analysis of

Private and Public Sector Location Models/' Management

Science , XVI (1970)

.

[2] See, for example:

(a) J. F. Casey, ed., The Fire Chief's Handbook , Third Edition (New York: The Reuben J.

Donnelley Corp., 1968).

(b) L. W. Erven, Fire Company Apparatus and

Procedures (Beverly Hills, California:

Glencoe Press, 1969).

[3] International City Management Association, The Municipal

Year Book (Washington, D. C: International City

Management Association, 1967, 1971).

[4] 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" (New

York, Chicago, San Francisco: National Board of Fire

Underwriters, 1956, with 1963 and 1964 amendments).

[5] Jane M. Hogg, "The Deployment of the Fire Services in

Glasgow in 1980," Needs of the Fire Services , Proceedings

of a Symposium Oct. 1968 (Washington, D. C: Committee

on Fire Research, Div. of Engl., National Research

Council, National Academy of Sciences, 1969).

Jane M. Hogg, "The Siting of Fire Stations,"

Operational Research Quarterly , XIX (1968), 275-87.

[6] Louis Santone and Geoffrey Berlin, "Location of Fire

Stations," Systems Analysis for Social Problems

(Washington, D. C: Operations Research Council, 1970),

pp. 81-91.

[7] 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, XIII (1965), 998-1006.

40
(b) Crond, Inc. , REDIST, Version 3.3, Program

Description and User Manual (New York:

National Municipal League, 1967)

[8] L. C. Santone, G. Berlin, Location of Fire Stations , Presented at WORC Symposium on "Systems Analysis for

Social Problems," May 26-28, 1969.

[9] D. Valinsky, "A Determination of the Optimum Location

of Fire Fighting Units in New York City," Operations

Research , III (1955) , 494-512.

E. Nilsson, J. Swartz, "Applications of Systems Analysis

to the Alexandria, Virginia Fire Department," NBS Report

10 454, January, 1972.

[10] P. S. Mitchell, "Efficient Allocation of Fire Department

Resources," Fire Technology , 1971, pp. 242-327.

[11] Toregas, Revelle, Swain, and Bergman, "The Location of

Emergency Service Facilities," Operations Research , Sept. -Oct. , 1971.

[12] L. C. Santone, G. Berlin, Location of Fire Stations , Presented at WORC Symposium on "Systems Analysis for

Social Problems," May 26-28, 1969.

[13] F. E. Maranzana, "On the Location of Supply Points to

Minimize Transport Cost," Operations Research Quarterly , XV (1964) , 261-70.

[14] Also see Richard Jordan, et al., Systems Analysis of

Inland Consolidation Centers for Marine Cargo , NBS

Technical Note #530, Nov. 1970.

[15] V. Srinivasan and F. L. Thompson, "A Fortran V Code for

Transportation Algorithms," Carnegie-Mellon University,

Pittsburg, Pennsylvania, June 1971.

[16] Copies can be obtained from the National Municipal

League, 47 E. 68th St., New York, N.Y. 10021.

U. S. GOVERNMENT PRINTING OFFICE : 1973 —511-326/26

41

NBS TECHNICAL PUBLICATIONS

PERIODICALS JOURNAL OF RESEARCH reports National Bureau of Standards research and development in

physics, mathematics, and chemistry. Comprehensive

scientific papers give complete details of the work,

including laboratory data, experimental procedures,

and theoretical and mathematical analyses. Illustrated with photographs, drawings, and charts. Includes

listings of other NBS papers as issued.

Published in two sections, available separately:

• Physics and Chemistry (Section A)

Papers of interest primarily to scientists working in these fields. This section covers a broad range of

physical and chemical research, with major emphasis on standards of physical measurement, fundamental

constants, and properties of matter. Issued six times a year. Annual subscription: Domestic, $17.00; Foreign, $21.25.

• Mathematical Sciences (Section B)

Studies and compilations designed mainly for the mathematician and theoretical physicist. Topics in mathematical statistics, theory of experiment design,

numerical analysis, theoretical physics and chemistry,

logical design and programming of computers and

computer systems. Short numerical tables. Issued quarterly. Annual subscription: Domestic, $9.00; Foreign,

$11.25.

TECHNICAL NEWS BULLETIN

The best single source of information concerning the Bureau's measurement, research, developmental, co- operative, and publication activities, this monthly

publication is designed for the industry-oriented

individual whose daily work involves intimate contact with science and technology

for engineers, chemists,

physicists, research managers, product-development

managers, and company executives. Includes listing of

all NBS papers as issued. Annual subscription: Domestic, $6.50; Foreign, $8.25.

N0NPERI0DICALS Applied Mathematics Series. Mathematical tables, manuals, and studies. Building Science Series. Research results, test methods, and performance criteria of building materials, components, systems, and structures. Handbooks. Recommended codes of engineering

and industrial practice (including safety codes) de- veloped in cooperation with interested industries,

professional organizations, and regulatory bodies. Special Publications. Proceedings of NBS conferences, bibliographies, annual reports, wall charts, pamphlets, etc. Monographs. Major contributions to the technical

literature on various subjects related to the Bureau's

scientific and technical activities. National Standard Reference Data Series.

NSRDS provides quantitative data on the physical

and chemical properties of materials, compiled from

the world's literature and critically evaluated. Product Standards. Provide requirements for sizes, types, quality, and methods for testing various industrial products. , These standards are developed co- operatively with interested Government and industry groups and provide the basis for common understanding of product characteristics for both buyers and

sellers. Their use is voluntary.

Technical Notes. This series consists of communications and reports (covering both other-agency and

NBS-sponsored work) of limited or transitory interest. Federal Information Processing Standards

Publications. This series is the official publication

within the Federal Government for information on

standards adopted and promulgated under the Public

Law 89—306, and Bureau of the Budget Circular A-86

entitled, Standardization of Data Elements and Codes

in Data Systems.

Consumer Information Series. Practical information, based on NBS research and experience, cover- ing areas of interest to the consumer. Easily understandable language and illustrations provide useful background knowledge for shopping in today's tech- nological marketplace.

BIBLIOGRAPHIC SUBSCRIPTION SERVICES

The following current-awareness and literature-survey bibliographies are issued periodically by the Bureau

Cryogenic Data Center Current Awareness Service (Publications and Reports of Interest in Cryogenics).

A literature survey issued weekly. Annual subscription: Domestic, $20.00; foreign, $25.00.

Liquefied Natural Gas. A literature survey issued quarterly. Annual subscription: $20.00. Superconducting Devices and Materials. A literature survey issued quarterly. Annual subscription : $20.00. Send subscription orders and remittances for the preceding bibliographic services to the U.S. Department

of Commerce, National Technical Information Service, Springfield, Va. 22151. Electromagnetic Metrology Current Awareness Service (Abstracts of Selected Articles on Measurement

Techniques and Standards of Electromagnetic Quantities from D-C to Millimeter-Wave Frequencies). Issued monthly. Annual subscription: $100.00 (Special rates for multi-subscriptions). Send subscription order and

remittance to the Electromagnetic Metrology Information Center, Electromagnetics Division, National Bureau

of Standards, Boulder, Colo. 80302. Order NBS publications (except Bibliographic Subscription Services)

from: Superintendent of Documents, Government Printing Office, Washington, D.C. 20402.
U.S. DEPARTMENT OF COMMERCE

National Bureau of Standards

Washington, D.C. 20234

OFFICIAL BUSINESS

Penalty for Private Use. $300

POSTAGE AND FEES PAID

U.S. DEPARTMENT OF COMMERCE COM-215