Question

QDM Question 2 There are 6 cities in Kilroy County.  The county must determine where to build central fire stations.  The county wants to build the minimum number of central fire stations needed to ensure that at least two fire stations are within 20 minutes (driving time) of each city.  The times (in minutes) required to drive between the cities in Kilroy County are given in the table. Formulate a model that will tell Kilroy how many fire stations should be built and where they should be located.

From	To
	City 1	City 2	City 3	City 4	City 5	City 6
City 1	0	10	20	30	30	20
City 2	10	0	25	35	20	10
City 3	20	25	0	15	30	20
City 4	30	35	15	0	15	25
City 5	30	20	30	15	0	14
City 6	20	10	20	25	14	0

Decision variables (1 mark):

Objective function (1 mark):

Constraints :

Additional constraint : Either City 1 or City 2 (or both) must be selected to build a fire station in if both City 3 and City 4 are selected to build fire stations in.

Answer 1

List of cities within 20 minutes driving time of each city is as follows:

City	Cities within 20 minute reach
1	1,2,3,6
2	1,2,5,6
3	1,3,4,6
4	3,4,5
5	2,4,5,6
6	1,2,3,5,6

---------------------------------------------------------------------------

1) Decision variables:

Let Xi = 1, if a fire station is built in city i, otherwise Xi = 0

2) Objective function:

Minimize X1+X2+X3+X4+X5+X6

3) Constraints:

X1+X2+X3+X6 >= 2   (at least 2 fire stations within 20 minutes reach of city 1)

X1+X2+X5+X6 >= 2   (at least 2 fire stations within 20 minutes reach of city 2)

X1+X3+X4+X6 >= 2   (at least 2 fire stations within 20 minutes reach of city 3)

X3+X4+X5 >= 2   (at least 2 fire stations within 20 minutes reach of city 4)

X2+X4+X5+X6 >= 2   (at least 2 fire stations within 20 minutes reach of city 5)

X1+X2+X3+X5+X6 >= 2   (at least 2 fire stations within 20 minutes reach of city 6)

Xi = {0,1} (binary constraint)

4) Additional constraint:

X1+X2-X3-X4 >= -1  (additional constraint: Either City 1 or City 2 (or both) must be selected to build a fire station in if both City 3 and City 4 are selected to build fire stations in.)