DMS201 Module-3

Location Problems

A production plant is to be located. Five potential locations, labelled as 1, 2, 3, 4, and 5, have

been shortlisted. The production process requires two parts in large volumes, 1000 and 2500
units daily. Suppliers of these parts are located at 1 and 2, respectively. Outputs from the
plant are to be sent to warehouses located at 1, 3, and 5 for onward distribution. The daily
requirements at the warehouses are 500, 1000, and 2000, respectively. We need to locate the
plant such that the total transportation cost is minimized. Transportation cost is proportional
to the distance travelled and the quantity transported. Compared to output, the parts consume
less transportation resource, 75% and 60%, respectively, of an output unit.

The network diagram to the right shows

the road links between different pairs of
locations. Nodes represent the locations,
and edges represent direct link between a
pair of locations. The number associated
with an edge is the distance of the road
link (in hundreds of kilometers). Where
should we locate the plant?

The above problem can be easily solved if we know the shortest distance between every pair
of locations. We can identify the shortest paths and their distances by visual inspection. The
table below lists the shortest paths and distances.

1 2 3 4 5 Quantity
1 --; 0 1-2; 5 1-5-3; 10 1-5-4; 14 1-5; 4 1250
2 2-1; 5 --; 0 2-3; 7 2-3-4; 12 2-5; 6 1500
3 3-5-1; 10 3-2; 7 --; 0 3-4; 5 3-5; 6 1000
4 4-5-1; 14 4-3-2; 12 4-3; 5 --; 0 4-5; 10 0
5 5-1; 4 5-2; 6 5-3; 6 5-4; 10 --; 0 2000

The total weighted transportation quantity for each location is shown in the above table. The
value of 1250 for location 1 is obtained as: 1000 × 0.75 + 500 = 1250 units (in terms of the
output). Other values are obtained in a similar manner. If we locate the plant at 1, total
transportation cost is: 0 × 1250 + 5 × 1500 + 10 × 1000 + 14 × 0 + 4 × 2000 = 25,500.
For options 2, 3, 4, 5, the costs are 25,250, 35,000, 60,500, 20,000, respectively. Clearly,
location 5 is the best choice for setting up the plant.

Shortest path: The above solution approach relies on the identification of shortest paths using
visual inspection. This is useful only for ‘classroom size’ problems. Industry grade problems
have more location options, more suppliers, and more warehouses. This increases the number
of nodes in the network diagram, which makes identification of shortest paths difficult. So,

DMS201 Notes prepared by Dr. Avijit Khanra

we discuss the Floyd’s algorithm for systematically identifying the shortest paths, actually the
shortest distances, between every pair of nodes in the network.

The algorithm starts with noting the edge distances in a tabular form. The 1st table mentions
(0)
these distances. 𝑑𝑖𝑗 denote the distance of the edge (𝑖, 𝑗). If edge (𝑖, 𝑗) is not present in the
(0)
network, 𝑑𝑖𝑗 = ∞, else it is finite. We add a row at the bottom of the table by copying the
first row. We also add a column in the right by copying the first column. Suppose there are 𝑚
nodes in the network. Then the distance matrix is of size 𝑚 × 𝑚 and we added 𝑚 + 1st row
(0)
and column. Now, 𝑑𝑖𝑗 is defined for 𝑖, 𝑗 = 1,2, … , 𝑚 + 1.

(0) 1 (1)
𝑑𝑖𝑗 1 2 3 4 5 𝑑𝑖𝑗 1 2 3 4 5 2
1 0 5 ∞ ∞ 4 0 1 0 5 ∞ ∞ 4 5
2 5 0 7 ∞ 6 5 2 5 0 7 ∞ 6 0
3 ∞ 7 0 5 6 ∞ 3 ∞ 7 0 5 6 7
4 ∞ ∞ 5 0 10 ∞ 4 ∞ ∞ 5 0 10 ∞
5 4 6 6 10 0 4 5 4 6 6 10 0 6
1 0 5 ∞ ∞ 4 2 5 0 7 ∞ 6

(1) (0) (0) (0)

We obtain distances in the 2nd table as: 𝑑𝑖𝑗 = min{𝑑𝑖𝑗 , 𝑑𝑖,𝑚+1 + 𝑑𝑚+1,𝑗 } for 𝑖, 𝑗 = 1,2, …,
(1) (0) (0) (0) (0) (0) (0)
𝑚. For example, 𝑑2,5 = min{𝑑2,5 , 𝑑2,6 + 𝑑6,5 } = min{𝑑2,5 , 𝑑2,1 + 𝑑1,5 } = min{6,5 + 4} =
(1)
6. Note that 𝑚 + 1 = 6 is 1 here. So, 𝑑𝑖𝑗 records the better of direct travel from 𝑖 to 𝑗 and
travel from 𝑖 to 𝑗 via 1. Then we add a row and column copying the second row and column,
completing the 2nd table. We obtain the 3rd table in a similar manner and continue this way
(𝑚) (5)
until we obtain 𝑑𝑖𝑗 , which is 𝑑𝑖𝑗 here.

(2) (3) 4
𝑑𝑖𝑗 1 2 3 4 5 3 𝑑𝑖𝑗 1 2 3 4 5
1 0 5 12 ∞ 4 12 1 0 5 12 17 4 17
2 5 0 7 ∞ 6 7 2 5 0 7 12 6 12
3 12 7 0 5 6 0 3 12 7 0 5 6 5
4 ∞ ∞ 5 0 10 5 4 17 12 5 0 10 0
5 4 6 6 10 0 6 5 4 6 6 10 0 10
3 12 7 0 5 6 4 17 12 5 0 10

(𝑘)
𝑑𝑖𝑗 for 𝑖, 𝑗 = 1,2, … , 𝑚 and 𝑘 ≥ 0 captures the shortest distance from 𝑖 to 𝑗 either directly or
via some or all of the nodes 1,2, … , 𝑘. We get the edge distance when 𝑘 = 0. In the next step,
(𝑘+1) (𝑘) (𝑘) (𝑘) (𝑘) (𝑘) (𝑘)
𝑑𝑖𝑗 = min{𝑑𝑖𝑗 , 𝑑𝑖,𝑚+1 + 𝑑𝑚+1,𝑗 } = min{𝑑𝑖𝑗 , 𝑑𝑖,𝑘+1 + 𝑑𝑘+1,𝑗 } tried to improves shortest
(𝑚)
distance by including node 𝑘 + 1. When we reach 𝑑𝑖𝑗 , we get the shortest distance.

DMS201 Notes prepared by Dr. Avijit Khanra

 (4) 5 (5)
𝑑𝑖𝑗 1 2 3 4 5 𝑑𝑖𝑗 1 2 3 4 5
1 0 5 12 17 4 4 1 0 5 10 14 4
2 5 0 7 12 6 6 2 5 0 7 12 6
3 12 7 0 5 6 6 3 10 7 0 5 6
4 17 12 5 0 10 10 4 14 12 5 0 10
5 4 6 6 10 0 0 5 4 6 6 10 0
5 4 6 6 10 0

1-median problem: Locating a facility in a network consisting of 𝑚 nodes, where each node
is characterized by a non-negative quantity 𝑞𝑗 for 𝑗 = 1,2, … , 𝑚, is known as the 1-median
problem. First, we find the shortest distance between every pair of nodes, denoted by 𝑑𝑖𝑗 for
𝑖, 𝑗 = 1,2, … , 𝑚. Then we obtain the cost of locating the facility at node 𝑖 as: 𝑐𝑖 = ∑𝑚
𝑗=1 𝑑𝑖𝑗 𝑞𝑗 .
∗
We locate the facility at node 𝑖 = arg min{𝑐𝑖 : 𝑖 ∈ 𝐹}, where 𝐹 ⊆ {1,2, … , 𝑚} denotes the set
of feasible nodes for locating the facility. A generalized version of the problem, known as the
𝑛-median problem, locates 𝑛 (< 𝑚) facilities. There, we need to make assignment decisions
(i.e., which facility serves which nodes) as well.

1-center problem: The 𝑛-median problem is a good model for the plant location problem. It
focuses on cost minimization, where distances and quantities both play a role. For service
facilities, the quantity associated with a node is the number customers present at the node.
Therefore, distances and quantities do not contribute to the cost of the organization. Rather,
∑𝑚𝑗=1 𝑑𝑖𝑗 𝑞𝑗 represents total distance travelled by the customers for availing the service if the
facility is located at node 𝑖. We may still consider minimizing it by choosing suitable 𝑖, but a
better choice would be to minimize the maximum distance that a customer needs to travel for
availing the service. We may consider weighted distances as well. We may as well replace
the distances by travel times if seems appropriate.

In the 1-center problem, we locate a facility in a network consisting of 𝑚 nodes such that the
maximum (weighted) distance of the nodes from the facility is minimized. First, we find the
shortest distance between every pair of nodes. Then we obtain “cost” of locating the facility
at node 𝑖 as: 𝑑𝑖𝑚𝑎𝑥 = max{𝑑𝑖𝑗 : 𝑗 = 1,2, … , 𝑚} or max{𝑑𝑖𝑗 𝑞𝑗 : 𝑗 = 1,2, … , 𝑚}. We locate the
facility at node 𝑖 ∗ = arg min{𝑑𝑖𝑚𝑎𝑥 : 𝑖 ∈ 𝐹}. For the example, 𝑑𝑖𝑚𝑎𝑥 = 14, 12, 10, 14, 10 for
𝑖 = 1,2,3,4,5 without weights and 10000, 12000, 12500, 20000, 9000 with weights. Then
nodes 3 and 5 are best choice without weights and node 5 is best with weights. A generalized
version of the problem, known as the 𝑛-center problem, locates 𝑛 (< 𝑚) facilities and makes
the node-facility assignments decisions as well.

Covering problem: We noted that the 𝑛-center problem is a good model for service facility
location. However, there is a class of service facilities location problem where the 𝑛-center
problem does not fit well. Consider the problem of locating an emergency service facility
such as the fire stations. Here, the key criterion is quick response, i.e., the service must reach
the customer within a designated time. With a fixed number of facilities, there is no guarantee

DMS201 Notes prepared by Dr. Avijit Khanra

that the quick response criterion can be met. We need to redefine the problem. It is about
locating the least number of facilities in a network such that every node is “covered” by at
least one facility, i.e., the quick response criterion is met for each node by some facility. This
problem is known as the (set) covering problem. In this problem, travel time matters, not the
distance travelled. It is the other way around for the 𝑛-median problem, while the 𝑛-center
problem considers both travel time and distance travelled.

Here, we present a greedy heuristic for the covering problem. First, we find the shortest travel
time between every pair of nodes. Then we construct the “coverage matrix” using the quick
response criterion. In the example, suppose that the numbers represent travel times, and the
criterion is that a facility must be reachable within 6 units. We obtain the coverage matrix by
replacing 𝑑𝑖𝑗 with 𝑐𝑖𝑗 = 𝟙(𝑑𝑖𝑗 ≤ 6), i.e., by 1 if 𝑑𝑖𝑗 ≤ 6, else by 0.

𝑐𝑖𝑗 1 2 3 4 5 The coverage matrix for the example is shown to

1 1 1 0 0 1 the left. We interpret its rows as customer nodes
2 1 1 0 0 1 and columns as potential facility locations. We
3 0 0 1 1 1 obtain ∑𝑚 𝑖=1 𝑐𝑖𝑗 , the number of nodes covered by

4 0 0 1 1 0 a facility at 𝑗 (if setup), for all 𝑖. ∑𝑚

𝑖=1 𝑐𝑖𝑗 = 3, 3,
5 1 1 1 0 1 3, 2, 4 for 𝑗 = 1,2,3,4,5.

It makes sense to locate a facility at node 5 as it covers the greatest number of nodes. Then
we “remove” the rows (representing customer nodes) covered by the facility at node 5. This
is shown by a light grey shade in the table. This leaves us with only the fourth row, i.e., an
uncovered customer at node 4. A second facility either at node 3 or at node 4 covers all the
customers. In general, the greedy heuristic works in a progressive manner by selecting the
location that covers the greatest number of uncovered nodes and then removing the nodes
covered by it. It stops when all the nodes are covered.

Further reading: Chapter 7, Facility Layout and Location – An Analytical Approach by

Francis, McGinnis, and White.

DMS201 Notes prepared by Dr. Avijit Khanra