Question

2. A large restaurant chain is planning to place 2 new locations in a new town. After some mar- keting analysis, the chain identifies 4 main neighborhoods in the town with potential customers Amber Heights, Borhouse Circle, Clarke's Marina, and Downtown. The distances between the neighborhoods are given by Table 2 (a) Formulate an integer program to help the restaurant chain plan where its new locations should be built so that the maximum distance traveled by customers is minimized (b) Before ground can be broken on the new locations, the city council comes to the chain and tells them development costs in Amber Heights, Borhouse Circle, Clarke's Marina, and Downtown wil be $150,000, $75,000, $200,000, and $125,000 respectively. If the chain is interested in both minimizing distance traveled by customers and development costs, how should they change the formulation from the previous part of the question? Neighborhood |A B C D 0 10 20 15 0 255 0 20 0 Table 2: Distances Between Neighborhoods

Answer 1

(a) Integer program is following:

Let

Yi = 1, if a new location is built at neighborhood i, otherwise Yi = 0, where i = {A,B,C,D}

Xij = 1, if customers from neighborhood j travel to the new location at i, otherwise Xij = 0, where i, j = {A,B,C,D}

Min 10Xab+20Xac+15Xad+10Xba+25Xbc+5Xbd+20Xca+25Xcb+20Xcd+15Xda+5Xdb+20Xdc

s.t.

Xaa+Xba+Xca+Xda=1

Xab+Xbb+Xcb+Xdb=1

Xac+Xbc+Xcc+Xdc=1

Xad+Xbd+Xcd+Xdd=1

Xaa+Xab+Xac+Xad-4Ya <= 0

Xba+Xbb+Xbc+Xbd-4Yb <= 0

Xca+Xcb+Xcc+Xcd-4Yc <= 0

Xda+Xdb+Xdc+Xdd-4Yd <= 0

Yi, Xij binary

(b) The integer program in part (a) Would be changed as below:

Min 10Xab+20Xac+15Xad+10Xba+25Xbc+5Xbd+20Xca+25Xcb+20Xcd+15Xda+5Xdb+20Xdc+150000Ya+75000Yb+200000Yc+125000Yd

s.t.

Xaa+Xba+Xca+Xda=1

Xab+Xbb+Xcb+Xdb=1

Xac+Xbc+Xcc+Xdc=1

Xad+Xbd+Xcd+Xdd=1

Xaa+Xab+Xac+Xad-4Ya <= 0

Xba+Xbb+Xbc+Xbd-4Yb <= 0

Xca+Xcb+Xcc+Xcd-4Yc <= 0

Xda+Xdb+Xdc+Xdd-4Yd <= 0

Yi, Xij binary