In the maximum covering problem, we assumed that all facilities cost the same amount to build. We also did not worry about demands that could not be covered. Often, these are not good assumptions....

In the maximum covering problem, we assumed that all facilities cost the same amount to build. We also did not worry about demands that could not be covered. Often, these are not good assumptions. First, in many cases, it makes sense to consider a model in which we minimize the sum of the construction costs (e.g., the construction costs for fire stations) and a penalty cost for not covering demands in the desired time, T⁰. Assume that the costs and penalties (f_j
and p_i) are defined in commensurable terms. Second, we may require that all demands be covered within a time T¹, where T¹
> T⁰.

Formulate such a model using the following:

Inputs

I = set of demand nodes

J = set of candidate locations

T⁰
= desired coverage time (demands not covered within this time will be penalized in the objective function)

T¹
= required coverage time (T’ > T⁰
and all demands must be covered by at least one facility within time T
¹)

= travel time from demand node i
 I to candidate site j
 J

hi = demand at node i
 I

f_j
= fixed cost of locating a facility at node j
 J

p_i
= penalty cost per unit demand not covered at demand node i
 I

Decision Variables

Formulate the following problem:

MINIMIZE Total facility location costs þ penalty costs

SUBJECT TO: Relationship between coverage within T⁰
and location decisions

All demands covered within T¹

Integrality