DIMACS

Center for Discrete Mathematics & Theoretical Computer Science

DIMACS EDUCATIONAL MODULE SERIES

MODULE 03-2 Facility Location Problems

Date prepared: March 27, 2003

R. S. (Chuck) Tiberio^{1} Wellesley High School Wellesley, MA 02481 email: tiberio@tiac.net

DIMACS Center, CoRE Bldg., Rutgers University, 96 Frelinghuysen Road, Piscataway, NJ 08854-8018

TEL: 732-445-5928 • FAX: 732-445-5932 • EMAIL: center@dimacs.rutgers.edu

                       Web: http://dimacs.rutgers.edu/

Founded as a National Science Foundation Science and Technology Center and a Joint Project of Rutgers University,

Princeton University, AT&T Labs - Research, Bell Labs, NEC Laboratories America and Telcordia Technologies with affiliated members Avaya Labs, HP Labs, IBM Research, Microsoft Research.

1Written under the auspices of DREI98, supported by NSF Grant DMS 9412914

Module Description Information

• Title:

Facility Location Problems

• Author(s):

R. S. (Chuck) Tiberio

• Abstract:

This module investigates the placement of emergency and service facilities in a network of towns connected by roads. Criteria for placement and algorithms for implementation are also discussed.

• Informal Description:

Sometimes commonly used public facilities (like a fire station or a shopping mall) are built where there is available land. Perhaps it would be better to build them in places which would maximize their use by the general public or facilitate their use by emergency personel. This module will address such questions and discuss possible methods of solution.

• Target Audience:

The intended target audience is high school seniors of average mathematical ability who are taking a course in discrete mathematics. However the module would certainly be appropriate for college students in a similar course.

• Prerequisites:

Students should be comfortable with the concept of graph and using a graph to model a physical situation. They should be familiar with basic matrix operations. Ability to use a TI-83 calculator would also be helpful.

• Mathematical Field:

Graph Theory (including weighted graphs) Elementary Matrix Operations

• Applications Areas:

The author’s intended application for this module is pedagogical. A student with a basic understanding of graphs and matrices can now see how these can be applied in a ”real world” setting.

• Mathematics Subject Classification:

Primary Classification: 90B80, 05C85

• Contact Information:

R. S. Tiberio Wellesley High School 50 Rice Street Wellesley, MA 02481 email: tiberio@tiac.net

• Other DIMACS modules related to this module: None at this time

TABLE OF CONTENTS

Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 0 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1 The Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Distance in Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3 Calculating Distances in Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4 Placement of Emergency Facilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 5 Placement of Service Facilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6 More Realistic Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

ABSTRACT

This module investigates the placement of emergency and service facilities in a network of towns connected by roads. Criteria for placement and algorithms for implementation are also discussed.

0 Introduction

This module is primarily for the use of high school teachers of discrete mathematics and their students. Typical students in this course will be seniors of average ability who have completed pre-calculus/trigonometry but who may not have the interest or requisite skills necessary to take an advanced placement course in either calculus or statistics.

In this module, students will use graphs and weighted graphs to determine which of several sites is the best location for different types of facilities. The key ideas are that of the “center” and “median” of a graph. These will be found using the distance matrix which gives the “distance” between any two vertices. Different techniques for finding “distances” are used for the case of graphs, weighted graphs (with weights on edges), and general networks (with weights on both vertices and edges).

Students should be familiar with the concept of using a graph to model a physical situation and with basic matrix operations. Teachers may wish to extend this model by discussing Dijkstra’s algorithm or some other algorithm for computing distances in a general network.

Students should have a TI-82/83 calculator or equivalent. Familiarity with the matrix menus and matrix operations would be helpful.

1 The Problem

Several towns have pooled their resources and decided to build facilities to service the area. Where should these facilities be located so that they will be as convenient as possible for everyone?

To help in the analysis of this problem we will use a graph. Informally, a graph consists of points (called vertices) and line segments joining certain of these points (called edges). A picture of the graph resembles a map of the region with the vertices representing the towns and the edges representing the roads that join the various towns.

Figure 1

Figure 1 shows such a graph (called G) representing nine towns, labeled a, b, c, d, e, f, g, h, i, and various roads connecting them. Note that the points where the edge joining vertices b and e crosses other edges are not labeled as vertices, and are not considered as possible locations for the facilities. To assist in the analysis of the problem we would also want to know the distance along these roads from town to town (or the time it takes to get from town to town along these roads). This could be represented by a weight. A weight on an edge is a non-negative number placed on the edge to represent distance, time, cost, or perhaps some other attribute. For additional realism we could also place weights on the vertices. These non-negative numbers placed on the vertices could represent the populations of the towns or perhaps the demand for services in the towns.

Although a graph with weights on both vertices and edges (called a general network) is the most realistic model, analysis of this model might be obscured by all the weights. So in order to understand the basic terms and get a feel for what is happening we will make a simplifying assumption and start by using an unweighted graph. You can imagine that all the towns have roughly the same population (give each vertex a weight of 1) and that all roads connecting towns are roughly the same length (give each edge a weight of 1).

2 Distance in Graphs

Let’s consider the various types of facilities that might be placed in this region. One type is an emergency facility (such as a fire station, ambulance service, police station, hospital, etc.). A second type is a service facility (such as a shopping mall, post office, park or playground, etc.). Each of these two types of facilities has its own set of criteria as to what constitutes optimal placement for those people who use the facilities. In either case, it is clear that the distance (or time) from town to town is of great importance.

When we talk of distance between two points, we refer of course to the shortest distance as measured in terms of the edges of the graph. More formally we have the following:

Definition 2.1 If u and v are two vertices in a graph, then the distance from u to v, d(u, v), is the number of edges in a shortest path from u to v.

Example 2.2 In graph G (Figure 1), b − d − h and b − e − g − h are two paths from b to h. The distance, d(b, h), from b to h is 2 since there is a path from b to h that has 2 edges, but there is no path from b to h that has 1 edge.

Exercise 1 Given the following graph (assume all edges have weight 1): find: a) d(c, b) b) d(b, c) c) d(c, c)

d) d(b, a) e) d(c, a) f) d(c, b) + d(b, a).

Food for thought: what is d(b, g)?

In a disconnected graph, the distance between two vertices is not always defined, as in the graph of Exercise 1. In the graphs that we will be looking at, it is possible to get from any site to any other site, so henceforth all graphs will be connected. (A graph is connected if one can go from any vertex to any other vertex by moving along edges.) Examining your answers to Exercise 1 should remind you of the basic properties of distance in the “normal” sense. Any function proposed as a distance function should have these properties where u and v are “points”:

i) d(u, v) ≥ 0 with equality if and only if u = v ii) d(u, v) = d(v, u) (the symmetric property) iii) d(u, v) + d(v, w) ≥ d(u, w) (the triangle inequality).

It should be easy to see that our definition of distance between vertices satisfies all three of these properties.

3 Calculating Distances in Graphs

Referring to graph G (Figure 1) we see nine vertices. The distances can be recorded for convenience in a 9×9 matrix, D(G), the distance matrix in which the entry in the i^{th} row and j^{th} column is the distance from vertex i to vertex j. By properties i) and ii) we see that this is a symmetric matrix with zeros along the principal diagonal.

We now describe three different techniques for filling in the entries in this matrix.

Method 1

One approach is simple brute force. By trial and error, we can calculate the first row of this matrix (that is, the distances from vertex a to all other vertices):

0 1 1 2 2 3 2 3 4.

By property ii), this is also the first column of D(G).

Exercise 2 By trial and error, find:

a) the distances from vertex c to all other vertices (i.e., the third row).

b) the distances from all other vertices to vertex e (i.e., the fifth column).

If the graph is reasonably small then finding all distances by trial and error (whether the graph is weighted or not) is a relatively simple task. If the graph has many vertices then it becomes a bit tedious to use this method. So let’s look for another way.

Method 2

To generate the distances from each vertex to all other vertices we will construct a “tree” of distances. A tree is a special type of graph defined using circuits. A circuit is a sequence of distinct edges such that the initial vertex of the first edge is the same as the terminal vertex of the last edge. For example, in the diagram for Exercise 1, a−d−c−a is a circuit of length 3 while a−c−b−e−a is a circuit of length 4.

Definition 3.1 A tree is a connected graph with no circuits. A tree has the nice property that there is a unique path joining any two of its vertices.

To construct the tree of distances we will perform a breadth-first search (BFS). Given a starting (root) vertex, a BFS will list all vertices at a distance of one from the root and then examine the remaining vertices in turn, listing all that have a distance of two from the root (unless they already appear in the tree). This process continues until all vertices in the original graph are listed in the tree.

Refer again to Figure 1. Starting with b as a root vertex (d(b, b) = 0), we list all vertices adjacent to b in a row. These vertices (a, c, d, e) are at a distance 1 from b.

Figure 2

We then go across this row and for each vertex in the row list all vertices adjacent to it that do not already appear in the “tree”. For example, in Figure 1 we have that a is adjacent to both b and c. However both b and c are already in the tree. Therefore we do not list them again. Also from Figure 1, c is adjacent to a, b, d, e, and g. Of these, a, b, d, and e are already in the tree so only g is listed in a second row. These new vertices added to the tree are at a distance of 2 from b. Doing this for the vertices a, c, d, and e at the first level of the tree gives:

Figure 3

There are now 8 vertices in our tree. Only vertex i needs to be placed. It is adjacent to vertex h and is therefore at a distance 3 from vertex b and is listed in a third row or level. Here is our complete tree for the distances from b to all other vertices:

Figure 4

Notice in Figure 4 that h is adjacent to both d and g but, since we want the shortest distance, we only list it once. Therefore we list it only at level 2. Once we complete the diagram we can read off the second row (and second column) of the matrix D(G) by reading the numbers corresponding to the vertices in alphabetical order:

a b c d e f g h i 1 0 1 1 1 2 2 2 3

Exercise 3 Using a breadth first search, construct trees to find:

a) the distances from vertex c to all other vertices (i.e., the third row).

b) the distances from all other vertices to vertex e (i.e., the fifth column).

c) compare your answers with those you found in Exercise 2.

We can continue with either method (trial and error or breadth first search), using the facts that the matrix is symmetric and the principal diagonal is all zeros, and fill in the remaining entries:

D(G) = [ \begin{matrix}0 & 1 & 1 & 2 & 2 & 3 & 2 & 3 & 4 \\ 1 & 0 & 1 & 1 & 1 & 2 & 2 & 2 & 3 \\ 1 & 1 & 0 & 1 & 1 & 2 & 1 & 2 & 3 \\ 2 & 1 & 1 & 0 & 2 & 1 & 1 & 1 & 2 \\ 2 & 1 & 1 & 2 & 0 & 3 & 1 & 2 & 3 \\ 3 & 2 & 2 & 1 & 3 & 0 & 2 & 2 & 3 \\ 2 & 2 & 1 & 1 & 1 & 2 & 0 & 1 & 2 \\ 3 & 2 & 2 & 1 & 2 & 2 & 1 & 0 & 1 \\ 4 & 3 & 3 & 2 & 3 & 3 & 2 & 1 & 0 \end{matrix} ] .

Method 3

A third approach for obtaining the D(G) matrix uses certain interesting properties of the adjacency matrix A(G) that records which vertices are adjacent to each other in the graph G.

Definition 3.2 If G is a graph on n vertices then the adjacency matrix A(G) is an n × n matrix with a = 1 if vertex i is adjacent to vertex j and a = 0 otherwise.

Again referring to Figure 1, the adjacency matrix is

A(G) = [ \begin{matrix}0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{matrix} ] .

The i, j^{th} entry in A^{n}, the n^{th} power of the adjacency matrix, yields the number of paths of length n from vertex i to vertex j (including those that involve repeated edges). To understand this property, let’s consider a much simpler example. Look at K_{3}, a complete graph on three vertices. A complete graph is a graph where any two vertices are adjacent. Also, look at its adjacency matrix A, and its square and cube, A^{2}, and A^{3}.

A = \begin{matrix}a & b & c \\ \begin{matrix}a \\ b \\ c \end{matrix} & [ \begin{matrix}0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix} ] \end{matrix} A^{2} = [ \begin{matrix}2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{matrix} ] A^{3} = [ \begin{matrix}2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \end{matrix} ] .

In the matrix A^{2}, notice the 1 in the 2, 3 entry, that is, the row for vertex b and the column for vertex c. This 1 is the result of a dot product between the b row and c column of A. That is, it is

[1 0 1] · [ \begin{matrix}1 \\ 1 \\ 0 \end{matrix} ] = 1 · 1 + 0 · 1 + 1 · 0 = 1.

In the term 1 · 1 of the expression 1 · 1 + 0 · 1 + 1 · 0, the first 1 comes from the fact that b is connected to a. The second 1 comes from the fact that a is connected to c. Thus the product counts the fact that b is connected to c (through a) by a path (where we are allowed to repeat edges) of length 2.

In a similar way, look at the matrix A^{3}. Notice the 3 in the b row, c column. This 3 is the result of the dot product of the b row in matrix A times the c column in matrix A. That is

[1 0 1] · [ \begin{matrix}1 \\ 1 \\ 2 \end{matrix} ] = 1 · 1 + 0 · 1 + 1 · 2 = 3.

Reasoning as above, we see that there are 3 paths of length 3 from b to c — one path consists of the edge from b to a followed by the unique path from a to c of length 2; the other two paths consist of the edge from b to c followed by the two paths from c to c of length 2. We can extend this argument to show that the ij-entry of matrix A^{n} counts the number of paths of length n from vertex i to vertex j.

Exercise 4 Using the graph pictured above:

a) construct the adjacency matrix A(G).

b) how many paths of length 4 are there from vertex a to vertex a?

c) how many paths of either length 2 or length 3 are there from a to c?

There is another way to think about the construction of D(G). Let D(G) = [d_{ij}] be the distance matrix and A(G) = [a_{ij}] be the adjacency matrix. The distance between vertex i and itself is 0. For each distinct i and j, to determine the distance d_{ij} from vertex i to vertex j, look at the ij’th entry in each of the matrices A, A^{2}, A^{3}, A^{4}, … until you find one which is non-zero. If that happens first in A^{k}, then d_{ij} = k since there is a path from vertex i to vertex j which has length k, but there is no shorter path from vertex i to vertex j.

In a connected graph with n vertices, this procedure for obtaining D(G) must terminate when the exponent in A^{k} reaches n − 1 since if there is a path from i to j, then there is one that doesn’t repeat vertices, and paths which do not repeat any vertices all have length at most n − 1.

This procedure for describing D(G) can be realized by using the following algorithm to develop successive approximations of D(G).

1. Start with d_{ij} = 0 for all i, j.

2. For i ≠ j, if a_{ij} = 1 in A(G), let d_{ij} = 1 in D(G).

3. For i ≠ j, if a_{ij} = 0 in A^{k}(G) for k = 1, 2, …, m − 1 and a_{ij} > 0 in A^{m}(G) then

d_{ij} = m in D(G).

Exercise 4 (continued)

d) using the graph on the previous page, find D(G) using powers of the adjacency matrix.

4 Placement of Emergency Facilities

Now that we are able to compute the distance between vertices, we can return to our problem and consider criteria for the placement of the facilities.

Let’s consider the emergency facility (for example, an ambulance service). It is reasonable to assume that an ambulance is required (for medical reasons) to be able to reach any potential victim or accident scene within a certain maximum amount of time (or distance); it it takes longer than that to arrive, patients who could have been saved might instead die. Any town closer to the proposed site than this maximum would be properly served by an ambulance at the proposed site. In order to ensure that every town is properly served by an ambulance at the proposed site, we would have to calculate the distance from the proposed site of the emergency facility to the town that is farthest away. If this distance (or time) is less than the maximum required for medical reasons then the proposed site is now a possible site. If this distance is greater than the maximum then we need to search for a better site. For some graphs there may not be any site which will do this. In other words, we need to ensure that the worst possible case is less than some predetermined bound.

What we will do instead is find those sites for which the worst possible case is as good as possible. To do this, we will use our distance matrix, D(G), in order to find a “centrally located” vertex.

For each vertex we find the “worst case” by looking in each row and determining which vertex is furthest away. For each vertex this number is called its eccentricity. Formally, we have

Definition 4.1 The eccentricity e(v) of vertex v is

e(v) = max{d(v, u) : u ∈ V }.

Looking at the first row of D(G) we see that the vertex which is farthest from a is i. Since the distance from a to i is 4 then by our definition e(a) = 4. Now look at the fourth row (vertex d). The maximum distance in that row is 2 (from d to either a, e, or i). Therefore, e(d) = 2.

Exercise 5 Use the distance matrix D(G) to find the eccentricity of the other seven vertices in Figure 1.

To minimize these worst cases we take those vertices with minimum eccentricity. This collection of vertices is called the set of central vertices of the graph.

Definition 4.2 The central vertices CV (G) of a connected graph G is

CV (G) = {v ∈ V : e(v) is minimum}.

For our graph, CV (G) = {d, g}, since both e(d) and e(g) are equal to 2 and e(x) > 2 for all other vertices. That is, an emergency facility like a hospital or fire station should be located at either vertex d or g since the distance from any other vertex to either d or g is at most 2.

In the general situation, we could locate the emergency facility at any central vertex since such a vertex has the smallest possible eccentricity.

We need however compare the outcome of this analysis with the maximum bound M mandated by medical considerations. If the eccentricity of the central vertices is less than or equal to M, then locating the emergency facility at any central vertex would meet the requirements. Indeed any vertex whose eccentricity is less than or equal to M would be a reasonable site, even if it is not central. Many factors may be used to determine which of several acceptable sites is best. On the other hand, if the eccentricity of the central vertices is greater than M, no site is acceptable and the situation needs to be reevaluated.

Exercise 6 For the graph pictured on the next page:

a) Use any method to construct the distance matrix, D(G).

b) Find the eccentricity of all vertices.

c) Find the central vertices of the graph.

d) At which site should an emergency facility be located?

Our use of the word “central vertex” might make you think about how this definition compares with the usual definition of central vertex (center is the usual term) of a circle. Imagine all points on or inside a circle. For any point, P, on or inside the circle, draw a diameter passing through that point (See Figure 5).

Figure 5

Recalling our definition of eccentricity, if a point, P, is on the circle then eccentricity equals the maximum distance between P and any other point on the circle (i.e. diameter). If a point, P, is inside the circle then the eccentricity equals the length of the longer segment along that diameter (why is that the maximum distance from P to a point on the circle?). Since, by our definition, the center consists of those points which minimize the eccentricity, the one and only point in a circle satisfying that property is the center of the circle.

In keeping with this idea, let’s define two more terms which mimic similar terms relating to a circle.

Definition 4.3 The diameter of a connected graph is the maximum distance between two vertices of the graph; thus it is also the maximum eccentricity among all vertices.

For example, in graph G (figure 1), the diameter = d(a, i) = 4 = e(a) = e(i).

Definition 4.4 The radius of a connected graph is the minimum eccentricity among all vertices of the graph. For example, in graph G (Figure 1), the radius = d(d, g) = 2 = e(d) = e(g).

Exercise 7 (Note: These problems are difficult and may be omitted without breaking the continuity of the document.)

1. Verify that in any graph, diameter = 2 · radius.

2. Construct an example where the diameter of a graph is less than twice the radius.

3. Verify that a tree has either one central vertex or two central vertices which are adjacent.

5 Placement of Service Facilities

Now consider a service facility such as a post office or shopping mall. Although it may be an inconvenience for a person to travel a long distance to get to a post office or shopping mall, it is not a matter of life or death. Although for emergency facilities, minimizing the maximum distance is a good criterion, a more reasonable criteria for placement of a shopping mall might be to locate the facility so that the average distance from the facility to all users (towns) is minimized. To calculate the average distance from one town to all other towns we add up all distances and divide by the number of remaining vertices. As an example, refer again to Figure 1 and look at vertex a. The distance matrix D(G) has all the distances recorded so we can easily figure out the average distance from vertex a to all others. It is

\frac{1 + 1 + 2 + 2 + 3 + 2 + 3 + 4}{8} = 2.25.

Since the number of vertices is fixed, minimizing the averages is equivalent to minimizing the sum of the distances. This sum is called the status of a vertex.

Definition 5.1 The status s(v) of vertex v in graph G is

s(v) = ∑_{u∈G} d(v, u).

where the sum is taken over all vertices u ∈ G.

Note that d(v, v) = 0 so we can ignore d(v, v) whenever we calculate this sum. Therefore, in graph G (Figure 1), the status of vertex a is s(a) = 18. Looking at the fifth row (vertex e) of the distance matrix D(G) for graph G we get s(e) = 2 + 1 + 1 + 2 + 3 + 1 + 2 + 3 = 15.

Exercise 8 Find the status of the remaining seven vertices of Figure 1.

Although it is reasonably easy to just add up the entries in each row, there is a simple matrix operation that will produce the status for each vertex. Simply multiply D(G) by an n × 1 column matrix of all 1’s. The result will be an n × 1 column matrix containing the status of each vertex.

Those vertices with minimum status (that is, minimum sum of distances) will be the vertices whose average distance to all others will be as small as possible. These vertices are called the median of a graph.

Definition 5.2 The median of graph G is

M(G) = {v ∈ V : s(v) is minimum}.

Using your answers to Exercise 8, you see that s(d) = 11 gives the minimum status. Thus, M(G) = {d}. So a service facility like a shopping mall or post office could be located at vertex d. However, due to practical considerations — for example, the price of property at central locations might be rather high — the facility might not actually be located at the ideal site.

Exercise 9 1. For the graph pictured in Exercise 6:

a) Find the status of every vertex.

b) Find the median of the graph.

c) At which site should a service facility be located?

�

The status of the vertices can also be used to determine which of several possible sites for an emergency facility is best. Thus, for example, in Exercise 6, a number of vertices have eccentricity 3, and are all at the center of the graph — d, f, g, and j. If an ambulance were located at any one of these vertices, it could get to any other vertex at a cost of at most 3 units; in that sense, these four vertices are equivalent. However, a secondary criterion for placement of emergency services should be that if a number of sites all have minimum worst travel time, then choose the one that has lowest average travel time. In other words, if more than one vertex is in the center, choose one with lowest status or, in case of a tie, one of the vertices of lowest status. Thus, if this secondary criterion is used, the emergency vehicle should be located at vertex d whose status is 15.

You may have noticed that the center and median of our example contain a common vertex {d}. This does not always have to be the case.

Exercise 10 1. Construct a graph with disjoint center and median. (HINT: Think of a tree consisting of a path with lots of branches on one end.)

6 More Realistic Models

Now let us consider the situation where the edges have (possibly) different weights rather than all having the same weight of 1. Recall that edge weights might represent the actual length of a road segment, or time or cost to travel it. As before, the distance between vertices still means the length of the shortest path between them, but now the length of a shortest path is the lowest sum of the “weights” on its edges; as in the diagram below, the shortest path between u and v may involve more edges than some longer path.

The solutions for both types of facilities are found by using the same formulas as previously discussed.

For emergency types of facilities, we would find (for each vertex) the eccentricity e(v) = max{d(v, u) : u ∈ V } and let the set of central vertices of the graph CV (G) be the set of vertices with minimum eccentricity. For service types of facilities, we would find (for each vertex) the status

s(v) = ∑_{u∈G} d(v, u)

and let the median of the graph M(G) be the set of vertices with minimum status.

Exercise 11 For the graph pictured below:

1. Find the center of the graph.

2. Find the median of the graph.

3. Determine the optimal placement for an emergency facility.

4. Determine the optimal placement for a service facility.

You may also have noticed that for both types of location problems we have assumed (perhaps unrealistically) that the facility in question was to be built in a town (that is, at a vertex). This may not necessarily be the case. We can allow for the possibility that the facility should be built between two sites by simply adding a vertex between those sites, and reevaluating the graph with the extra vertex. Suppose that in the graph for Exercise 6 (where each edge has weight 1) there is a location on the road from d to g (called k) that is proposed as a possible site for a facility. This new site can be represented by adding a new vertex k to the graph of Exercise 6 and replacing the edge joining d and g by two edges, one joining d and k, and the other joining k and g; assuming that k is halfway between d and g, each of these edges is assigned the weight of 1/2. The resulting problem, whose graph is below, is used in Exercise 12.

Exercise 12 1. Add vertex k on the road between d and g in the graph for Exercise 6: a) Find the new distance matrix D(G).

b) Find the center of this graph.

c) Find the median of this graph.

d) How does the addition of the new vertex k along a pre-existing road affect the center and median of the graph, and how does this affect the potential location of emergency and service facilities.

2. (Note: This problem is difficult and may be omitted without breaking the continuity of the document.) Prove that if half or more of the users in a graph are located at the same vertex, then that vertex is a location with minimum sum of distances (and thus the unique median).

An even more realistic model involves weights on both the edges and vertices. Recall that vertex weights might represent the population at the town or the demand for services. Such a graph is called a general network. As an example, consider the following general network:

Figure 6

The solutions for both types of facilities will again be similar to those discussed in sections 4 and 5. The central vertices will again be those vertices with minimum eccentricity and the median will again be the set of vertices with minimum status.

Before we give the definitions of center and median in a general network and solve the Facility Location Problem for Figure 6, consider the following example (see Figure 7).

Figure 7

Where should we place an emergency facility? If, as before, we want to ensure that the worst case scenario is as good as possible, then we would want to place the facility at b, since the emergency vehicle would be able to get from b to either a or c in 10 minutes — in other words, since e(b) = 10 and e(a) = e(c) = 15, b has the minimum eccentricity and is therefore the unique central vertex of the graph.

On the other hand, one could argue that the emergency facility should be at c since a very high percentage of emergency calls will be from c. This amounts to saying that an emergency facility should be treated just like a service facility.

Now suppose (as discussed in section 5) that a service facility must be placed so that the average distance to the facility is minimized. We easily calculate the averages as follows:

If the facility is at vertex a then the average is

\frac{1 · 0 + 1 · 5 + 100 · 15}{102} = \frac{1505}{102} = 14.7549.

If the facility is at vertex b then the average is

\frac{1 · 5 + 1 · 0 + 100 · 10}{102} = \frac{1005}{102} = 9.8529.

If the facility is at vertex c then the average is

\frac{1 · 15 + 1 · 10 + 100 · 0}{102} = \frac{25}{102} = 0.2451.

Since the status of vertex c, s(c), is 25, this vertex has the lowest average distance and thus the median of the graph is M(G) = {c}.

How could the question be resolved? One way is if there is some recommended maximum time from an emergency facility. For example, if the guideline was that the emergency vehicle should be within 20 minutes from every site, then it would be fine to locate the emergency vehicle at c. If, on the other hand, the guideline was that the emergency vehicle should be within 10 minutes from every site, then, in order to ensure that every site could be reached within the recommended maximum time, the emergency vehicle would have to be located at b. (Note, however, that the benefits of getting to 100 potential customers much more quickly than this recommended maximum time — if the vehicle were at c — might outweigh the benefits of getting to 102 customers within the recommended maximum time — if the vehicle were at b.) And if the guideline was that the emergency vehicle should be within 12 minutes from every site, then it would probably be located somewhere between b and c.

Summarizing for a general network, we should continue to define the eccentricity of a vertex as before.

Definition 6.1 The eccentricity e(v) of vertex v is

e(v) = max{d(v, u) : u ∈ V }.

However, when using a general network, we should now use the weights on the vertices to determine the status.

Definition 6.2 The status s(v) of vertex v in general network G is

s(v) = ∑_{u∈G} w(u) · d(v, u).

where as before, the sum is taken over all vertices u ∈ G.

Note that we multiply d(v, u) by the vertex weight at the arrival vertex u. Why is that? Suppose we are dealing with a service facility (like a shopping mall) located at vertex v. Then the people living at u must travel to v to avail themselves of the service. Thus it is the demand for services at vertex u which is most important.

In making a decision about the placement of a service facility, we focus on the vertices of minimum status, that is, the median of the graph. On the other hand, in making a decision about the placement of an emergency facility, we may need to consider both the central vertices and the median vertices, as discussed above.

In order to determine both the status and eccentricity of the vertices of a graph, we need to be able to calculate the distance between any two vertices of a weighted graph — that is, we need to find the matrix for distance in graphs with weighted edges. If the general network is small enough then simple brute force will do. The adjacency matrix approach that we used with unweighted graphs will not work with weighted graphs.

Of the three methods used for unweighted graphs, this leaves only the breadth-first search tree. If you use exactly the same algorithm, it doesn’t quite work. Just because a vertex appears at (say) level two of the tree, that doesn’t preclude the same vertex appearing again at the next (or even lower) level and at a shorter distance to the root of the tree. The algorithm can be slightly modified however so that it will work properly. When this is done the algorithm turns out to be just a reworking of Dijkstra’s algorithm which is a very well known procedure for finding the shortest path between two vertices in a weighted graph.

There are other procedures for calculating distances in weighted graphs (see the bibliography). However Dijkstra’s algorithm is what is usually used.

Once we have this weighted distance matrix we take it and multiply by the vertex weight matrix. This matrix has vertex weights on the main diagonal and has zeros in all other positions. For the graph in Figure 6 the computations are as follows:

[ \begin{matrix}0 & 4 & 8 & 6 & 6 & 5 \\ 4 & 0 & 5 & 3 & 2 & 2 \\ 8 & 5 & 0 & 2 & 3 & 6 \\ 6 & 3 & 2 & 0 & 1 & 4 \\ 6 & 2 & 3 & 1 & 0 & 3 \\ 5 & 2 & 6 & 4 & 3 & 0 \end{matrix} ] · [ \begin{matrix}3 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 3 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 4 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} ] = [ \begin{matrix}0 & 8 & 24 & 6 & 24 & 5 \\ 12 & 0 & 15 & 3 & 8 & 2 \\ 24 & 10 & 0 & 2 & 12 & 6 \\ 18 & 6 & 6 & 0 & 4 & 4 \\ 18 & 4 & 9 & 1 & 0 & 3 \\ 15 & 4 & 18 & 4 & 12 & 0 \end{matrix} ] .

We now read off the eccentricities (the maximum in each row of the unweighted distance matrix):

e(a) = 8 e(b) = 5 e(c) = 8 e(d) = 6 e(e) = 6 e(f) = 6

and the statuses (the sum of each row of the weighted distance matrix):

s(a) = 67 s(b) = 40 s(c) = 54 s(d) = 38 s(e) = 35 s(f) = 53.

The center of the graph is {b} and the median of the graph is {e}. Thus (under our assumptions) an emergency facility should be located at vertex b while a service facility should be located at vertex e.

Exercise 13 For the network pictured below:

a) Find the weighted distance matrix.

b) Find the eccentricity of every vertex.

c) Find the status of every vertex.

d) Find the center and median of the network.

e) Where would you place a fire station? a shopping mall?

Solutions to Exercises

Exercise 1:

a) d(c, b) = 1  b) d(b, c) = 1  c) d(c, c) = 0
d) d(b, a) = 2  e) d(c, a) = 1  f) d(c, b) + d(b, a) = 3

Food for thought: d(b, g) is not defined since there is no path from b to g.

Exercise 2:

a) The third row is 1 1 0 1 1 2 1 2 3

b) The fifth column is 2 1 1 2 0 3 1 2 3

Exercise 3:

Exercise 4:

a) A(G) = [ \begin{matrix}0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \end{matrix} ] b) The entry in the a row, a column of A^{4} is 15.

c) The entries in the a row and c column of A^{2} and A^{3} are 1 and 5. Therefore, 1 + 5 = 6.

Exercise 4 (continued):

d) D(G) = [ \begin{matrix}0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 2 \\ 1 & 1 & 2 & 0 \end{matrix} ]

Exercise 5:

e(a) = 4  e(b) = 3  e(c) = 3  e(d) = 2  e(e) = 3
e(f) = 3  e(g) = 2  e(h) = 3  e(i) = 4

Exercise 6:

a) D(G) = [ \begin{matrix}0 & 1 & 2 & 1 & 1 & 2 & 2 & 4 & 3 & 3 \\ 1 & 0 & 1 & 2 & 2 & 3 & 3 & 4 & 3 & 2 \\ 2 & 1 & 0 & 1 & 2 & 3 & 2 & 3 & 2 & 1 \\ 1 & 2 & 1 & 0 & 1 & 2 & 1 & 3 & 2 & 2 \\ 1 & 2 & 2 & 1 & 0 & 1 & 2 & 4 & 3 & 3 \\ 2 & 3 & 3 & 2 & 1 & 0 & 1 & 3 & 2 & 3 \\ 2 & 3 & 2 & 1 & 2 & 1 & 0 & 2 & 1 & 2 \\ 4 & 4 & 3 & 3 & 4 & 3 & 2 & 0 & 1 & 2 \\ 3 & 3 & 2 & 2 & 3 & 2 & 1 & 1 & 0 & 1 \\ 3 & 2 & 1 & 2 & 3 & 3 & 2 & 2 & 1 & 0 \end{matrix} ]

b) e(a) = 4  e(b) = 4  e(c) = 3  e(d) = 3  e(e) = 4
e(f) = 3  e(g) = 3  e(h) = 4  e(i) = 3  e(j) = 3

c) center is {c, d, f, g, i, j}

d) An emergency facility should be located at any vertex in the center {c, d, f, g, i, j}.

Exercise 7: NOTE: As stated in the module, these proofs may be omitted without loss of continuity of the document if the instructor feels that the students are not quite ready to attempt them.

1. Prove: In any graph, the diameter is less than or equal to twice the radius.

Proof: Let G be a connected graph. Recall from Exercise 1 that if the graph is not connected then distances might not be defined.

Let v be a vertex having minimum eccentricity.

Let u be a vertex having maximum eccentricity.

Since u has maximum eccentricity, there exists a vertex w such that d(u, w) is maximum. That is, diameter = d(u, w).

Now consider d(u, v) and d(v, w). Each of these must be less than or equal to the radius since the radius has minimum eccentricity. Remember that it is the minimum among all vertices and also that eccentricity is the maximum distance from v to all other vertices. So we now have

2 · radius ≥ d(u, v) + d(v, w) ≥ d(u, w) = diameter.

Q.E.D.

2. One of the simpler graphs with this property is a circuit graph. Consider the graph C_{4}.

Constructing a distance matrix easily shows that e(a) = e(b) = e(c) = e(d) = 2. Thus diameter = radius = 2 and clearly diameter ≤ 2 · radius.

3. Prove: A tree has either one center or two adjacent centers.

Proof: Let T be any tree. If T is a single vertex (K_{1}) or two vertices joined by a single edge (K_{2}) then the result is trivial.

For all other trees we will describe a “pruning” procedure. Clearly the vertices having maximum eccentricity must be the “leaves” (vertices having degree 1). Prune all the leaves from the tree. That is, delete each vertex of degree 1 and its adjacent edge. This now leaves a tree T_{1} whose center is the same as T since all eccentricities have decreased by 1. Clearly this process must terminate with either a K_{1} or K_{2}. Q.E.D.

Exercise 8:

s(b) = 13  s(c) = 12  s(d) = 11  s(f) = 18
s(g) = 12  s(h) = 14  s(i) = 21

Exercise 9: 1.

a) s(a) = 19  s(b) = 21  s(c) = 17  s(d) = 15  s(e) = 19
s(f) = 20  s(g) = 16  s(h) = 26  s(i) = 18  s(j) = 19

b) M(G) = d

c) A service facility should be located at vertex d.

Exercise 10: 1. Here is one possible example. (There are others)

Exercise 11:

1. a) D(G) = [ \begin{matrix}0 & 1 & 2 & 1 & 1 & 2 & 3 & 5 & 4 & 3 & 2 \\ 1 & 0 & 1 & 2 & 2 & 3 & 4 & 4 & 3 & 2 & 3 \\ 2 & 1 & 0 & 1 & 2 & 3 & 3 & 3 & 2 & 1 & 2 \\ 1 & 2 & 1 & 0 & 1 & 2 & 2 & 4 & 3 & 2 & 1 \\ 1 & 2 & 2 & 1 & 0 & 1 & 2 & 4 & 3 & 3 & 2 \\ 2 & 3 & 3 & 2 & 1 & 0 & 1 & 3 & 2 & 3 & 2 \\ 3 & 4 & 3 & 2 & 2 & 1 & 0 & 2 & 1 & 2 & 1 \\ 5 & 4 & 3 & 4 & 4 & 3 & 2 & 0 & 1 & 2 & 3 \\ 4 & 3 & 2 & 3 & 3 & 2 & 1 & 1 & 0 & 1 & 2 \\ 3 & 2 & 1 & 2 & 3 & 3 & 2 & 2 & 1 & 0 & 3 \\ 2 & 3 & 2 & 1 & 2 & 2 & 1 & 3 & 2 & 3 & 0 \end{matrix} ]

b) C(G) = {c, f, j, k}

c) M(G) = {d} d) The median remains the same. The central vertices change with k joining the center and d, g, and i leaving.

NOTE: As stated in the module, this proof may be omitted without loss of continuity of the document if the instructor feels that the students are not quite ready to attempt it.

2. Prove: If half or more of the users in a graph are located at the same vertex, then that vertex is a location with minimum sum of distances (and thus the unique median).

Proof: Let u be the vertex with half or more of the users. Designate these users as A_{1}, A_{2}, …, A_{m}. Let the other users located at other vertices be O_{1}, O_{2}, …, O_{n}. Notice that since half or more of the users are at vertex u we then have m ≥ n. Pair up users from u with the other users (A_{1}, O_{1}), (A_{2}, O_{2}), …, (A_{n}, O_{n}). Notice that users A_{n+1} to A_{m} are not paired with anyone. Let d(A_{i}, O_{i}) be the distance from the vertex where A_{i} is to the vertex where O_{i} is. This distance function obeys the usual reflexive, symmetric, and transitive properties. Consider the following sum

S = d(A_{1}, O_{1}) + d(A_{2}, O_{2}) + … + d(A_{n}, O_{n}).

If the facility is placed at u then S represents the status of vertex u. Suppose we place the facility at another vertex, say vertex i. Then in the above sum we would replace d(A_{i}, O_{i}) with d(O_{i}, A_{i}) because A_{i} must now travel to where O_{i} is. For k ≠ i, we would replace d(A_{k}, O_{k}) with d(A_{k}, O_{i}) + d(O_{i}, O_{k}) since now both A_{k} and O_{k} must travel to where O_{i} is. Thus by the triangle inequality, the value of S would increase. In addition, all the users A_{n+1} to A_{m} would have to now travel some distance to O_{i}. Therefore, u is the vertex with minimum sum of distances and is thus the median. Q.E.D.

Exercise 12:

a) D(G) = [ \begin{matrix}0 & 3 & 4 & 4 & 5 & 7 & 9 \\ 3 & 0 & 3 & 1 & 2 & 4 & 6 \\ 4 & 3 & 0 & 2 & 3 & 5 & 7 \\ 4 & 1 & 2 & 0 & 1 & 3 & 5 \\ 5 & 2 & 3 & 1 & 0 & 2 & 4 \\ 7 & 4 & 5 & 3 & 2 & 0 & 2 \\ 9 & 6 & 7 & 5 & 4 & 2 & 0 \end{matrix} ]

b) We now multiply by the weights on the vertices to obtain our final matrix

[ \begin{matrix}0 & 3 & 4 & 4 & 5 & 7 & 9 \\ 3 & 0 & 3 & 1 & 2 & 4 & 6 \\ 4 & 3 & 0 & 2 & 3 & 5 & 7 \\ 4 & 1 & 2 & 0 & 1 & 3 & 5 \\ 5 & 2 & 3 & 1 & 0 & 2 & 4 \\ 7 & 4 & 5 & 3 & 2 & 0 & 2 \\ 9 & 6 & 7 & 5 & 4 & 2 & 0 \end{matrix} ] [ \begin{matrix}3 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 3 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 5 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 4 \end{matrix} ] = [ \begin{matrix}0 & 6 & 4 & 12 & 25 & 7 & 36 \\ 9 & 0 & 3 & 3 & 10 & 4 & 24 \\ 12 & 6 & 0 & 6 & 15 & 5 & 28 \\ 12 & 2 & 2 & 0 & 5 & 3 & 20 \\ 15 & 4 & 3 & 3 & 0 & 2 & 16 \\ 21 & 8 & 5 & 9 & 10 & 0 & 8 \\ 27 & 12 & 7 & 15 & 20 & 2 & 0 \end{matrix} ]

e(a) = 36  e(b) = 24  e(c) = 28  e(d) = 20  e(e) = 16

e(f) = 21 e(g) = 27

c) s(a) = 90 s(b) = 53 s(c) = 72 s(d) = 44 s(e) = 43 s(f) = 61 s(g) = 83

d) C(G) = {e} and M(G) = {e}

e) Both service and emergency facilities should be located at vertex e.

NOTE: Most of the material in this paper is adapted from the Buckley article [1] which is probably the easiest for a student to read.

References

[1] Buckley, F., Facility Location Problems, The College Mathematics Journal, 18 (1987) 24-32.

[2] Chartrand, G. and Lesniak, L., Graphs and Digraphs, 2nd ed., Wadsworth and Brooks/Cole, (1986) 29-30, 31-34.

[3] Christofides, N., Graph Theory, An Algorithmic Approach, Academic Press, (1975) 79-80, 106, 108.

[4] Gondran, M. and Minoux, M., Graphs and Algorithms, Translated by Steven Vajda, John Wiley & Sons, (1984) 57-59

[5] Harary, F. and Buckley, F., Distance in Graphs, Addison-Wesley, (1990), 31-50.