East Coast Trucking provides service from Boston to Miami using regional offices located in Boston, New York, Philadelphia, Baltimore, Washington, Richmond, Raleigh, Florence, Savannah, Jacksonville, Tampa, and Miami. The number of miles between each of the regional offices and the numbers associated with each city are provided in the following table.

The company's expansion plans involve constructing service facilities in some of the cities where a regional office is located, such that each regional office is within 400 miles of at least one service facility. For instance, if a service facility is constructed in Richmond, it can provide service to regional offices located in New York, Philadelphia, Baltimore, Washington, Richmond, Raleigh, and Florence. Management would like to determine the minimum number of service facilities needed and where they should be located. (a) Formulate an integer linear program that can be used to determine the minimum number of service facilities needed and their location. (Let xi be the 0-1 variable, which is 1 if a service facility is constructed in city i, and 0 otherwise.)

Min

s.t.

Boston

New York

Philadelphia

Baltimore

Washington

Richmond

Raleigh

Florence

Savannah

Jacksonville

Tampa

Miami

x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12 = 0, 1

(b) Solve the linear program formulated in part (a). How many service facilities are required? Where should they be located? (Select all that apply.) Boston

New York

Philadelphia

Baltimore

Washington

Richmond

Raleigh

Florence

Savannah

Jacksonville

Tampa

Miami

(c) Suppose that each service facility can only provide service to regional offices within 300 miles. How many service facilities are required? Where should they be located? (Select all that apply.)

Boston

New York

Philadelphia

Baltimore

Washington

Richmond

Raleigh

Florence

Savannah

Jacksonville

Tampa

Miami

\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline & New York & Philadelphia & Baltimore & Washington & Richmond & Raleigh & Florence & Savannah & Jacksonville & Tampa & Miami \\ \hline Boston 1 & 211 & 320 & 424 & 459 & 565 & 713 & 884 & 1,056 & 1,196 & 1,399 & 1,669 \\ \hline New York 2 & & 109 & 213 & 248 & 354 & 502 & 673 & 845 & 985 & 1,188 & 1,458 \\ \hline Philadelphia 3 & & & 104 & 139 & 245 & 393 & 564 & 736 & 876 & 1,079 & 1,349 \\ \hline Baltimore 4 & & & & 35 & 141 & 289 & 460 & 632 & 772 & 975 & 1,245 \\ \hline Washington 5 & & & & & 106 & 254 & 425 & 597 & 737 & 940 & 1,210 \\ \hline Richmond 6 & & & & & & 148 & 319 & 491 & 631 & 834 & 1,104 \\ \hline Raleigh 7 & & & & & & & 171 & 343 & 483 & 686 & 956 \\ \hline Florence 8 & & & & & & & & 172 & 312 & 515 & 785 \\ \hline Savannah & & & & & & & & & 140 & 343 & 613 \\ \hline Jacksonville & & & & & & & & & & 203 & 473 \\ \hline Tampa & & & & & & & & & & & 270 \\ \hline Miami 14 & & & & & & & & & & & \\ \hline \end{tabular}