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 are provided in the EastCoast.xlsx data file.

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 x_i be the 0-1 variable, which is 1 if a service facility is constructed in city i, and 0 otherwise. Let Boston be city 1, New York be city 2, Philadelphia be city 3, Baltimore be city 4, Washington be city 5, Richmond be city 6, Raleigh be city 7, Florence be city 8, Savannah be city 9, Jacksonville be city 10, Tampa be city 11, and Miami be city 12.)

Min _______

s.t.

Boston ______

New York ______

Philadelphia _______

Baltimore _______

Washington _______

Richmond _______

Raleigh _______

Florence _______

Savannah _______

Jacksonville _______

Tampa _______

Miami _______

x_i = 0, 1 for i = 1, 2, , 12

(b)

Solve the integer linear program formulated in part (a). How many service facilities are required?

______ facilities

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. Re-solve the integer linear program with the 300-mile requirement. How many service facilities are required?

_____ facilities

Where should they be located? (Select all that apply.)

Boston

New York

Philadelphia

Baltimore

Washington

Richmond

Raleigh

Florence

Savannah

Jacksonville

Tampa

Miami

East Coast Trucking
	Boston	New York	Philadelphia	Baltimore	Washington	Richmond	Raleigh	Florence	Savannah	Jacksonville	Tampa	Miami
Boston	0	211	320	424	459	565	713	884	1056	1196	1399	1669
New York	211	0	109	213	248	354	502	673	845	985	1188	1458
Philadelphia	320	109	0	104	139	245	393	564	736	876	1079	1349
Baltimore	424	213	104	0	35	141	289	460	632	772	975	1245
Washington	459	248	139	35	0	106	254	425	597	737	940	1210
Richmond	565	354	245	141	106	0	148	319	491	631	834	1104
Raleigh	713	502	393	289	254	148	0	171	343	483	686	956
Florence	884	673	564	460	425	319	171	0	172	312	515	785
Savannah	1056	845	736	632	597	491	343	172	0	140	343	613
Jacksonville	1196	985	876	772	737	631	483	312	140	0	203	473
Tampa	1399	1188	1079	975	940	834	686	515	343	203	0	270
Miami	1669	1458	1349	1245	1210	1104	956	785	613	473	270	0