Question

Western Airlines wants to design a hub system in the United States. Each hub is used for connecting flights to and from cities within 1500 miles of the hub. Western runs flights among the following cities: Atlanta, Boston, Chicago, Denver, Houston, Los Angeles, New Orleans, New York, Pittsburgh, Salt Lake City, San Francisco, and Seattle. The company wants to determine the smallest number of hubs it needs to cover all these cities. A city is covered if it is within 1500 miles of at least one hub. The table on the left lists actual distances between cities.

Find the location of the hubs.Where are the hub(s) located?

Input data Mile limit Background: Western Airlines wants to design a hub system in the United States. Each hub is used for connecting flights to and from cities within 1500 miles of the hub. Western runs flights among the following cities: Atlanta, Boston, Chicago, Denver, Houston, Los Angeles, New Orleans, New York, Pittsburgh, Salt Lake City, San Francisco, and Seattle. The company wants to determine the smallest number of hubs it needs to cover all these cities. A city is covered if it is within 1500 miles of at least one hub. The table on the left lists actual distances between cities. Find the location of the hubs. Distance from each city to each other ty AT 0 1037 674 1398 789 2182 479 841 687 1878 2496 2618 BO 1037 0 1005 1949 1804 2979 1507 222 574 2343 3095 2976 CH 674 1005 0 1008 1067 2054 912 802 452 1390 2142 2013 DE HOLANO NY 1398 789 2182 479 841 1949 1804 2979 1507 222 1008 1057 2054 912 802 0 1019 1059 1273 1771 1019 0 1538 356 1608 1059 1538 0 1883 2786 1273 356 1883 0 1311 1771 1608 2786 1311 0 1411 1313 2426 1070 368 504 1438 715 1738 2182 1235 1912 379 2249 2934 1307 2274 1131 2574 2815 I SLSF 687 1878 2496 574 2343 3095 452 1390 2142 1411 504 1235 1313 1438 1912 2426 715 379 1070 1738 2249 368 2182 2934 0 1826 2578 1826 0 752 2578 752 0 2465 826 808 SE 2618 2976 2013 1307 2274 1131 2574 2815 2465 836 808 0 Distance between cities. 1 if within miles limit, otherwise. City AT BO C H DE HOLA NO NY PI SL SE SE SL Decisions: location of hubs. 1 If a dty is used as a hub, O otherwise. AT BO Used as hub? 01 DE HOLA NO NY PI SL SF SE Constraints: each city must be covered by at least one hub Requirement: At least Covered by how covered by how many City many hubs hubs

Answer 1

Solution: An integer programming problem has been formulated and solved with Excel solver. Following are the snapshots of Excel model and solver window:

Total_Hubs - X fx Western Airlines Hubs Planning Solver Parameters A Western Airlines Hubs Planning Set Objective: Total_Hubs 3 Input Data To: O Max Min value of: 5 0 AT BO By Changing Variable Cells: Hub Locations CH DE HO LA 1 037 1037 TO 674 1005 1398 1949 789 1804 2182 2979 4791507 841222 687 574 1878 2343 674 1005 0 1008 1067 2054 912 802 452 1390 DE HOLA NO NY PI SL SF SE 1398 789 2182 479 841687 1878 2496 2618 1949 1804 2979 1507 222 574 2343 3095 2976 1008 1067 2054 912 802 452 1390 2142 2013 0 1019 1059 1273 1771 1411 504 1235 1307 1019 0 1538 356 1608 1313 1438 1912 2274 10591538 0 1883 2786 2426 715 379 1131 1273 356 1883 0 1311 1070 1738 2249 2574 1771 1608 2786 13110 368 2182 2934 2815 1411 1313 2426 1070 368 0 1826 2578 2465 504 1438 715 1738 2182 1826 0 752 836 1235 1912 379 2249 2934 2578 752 0 808 1307 2274 1131 2574 2815 2465 836 808 0 Subject to the Constraints: Covered_Hubs >= Least_Hubs Hub_Locations = binary Add NO Change NY PI SL SF Delete SE 2618 2976 2013 17 Reset All SF SE Load/Save 20 AT 0 Make Unconstrained variables Non-Negative Select a Solving Simplex LP Method: Options O 18 Distance between cities = 1, if within Miles Limit, O, if not. 19 Hub Miles Limit = 1,500 AT BO CH DE HOLA NO NY PI SL 1 1 1 1 1 01110 во 1 1 1 0 0 0 0 1 1 0 CH | 1 1 1 1 1 | 11 0 1 1 1 1 DE 101 1 1 1 1 0 1 1 HO 0 1 11 1 0 1 1 LA 0 0 0 0 0 0 1 NO 1 1 1 1 0 NY 1 1 1 1 PI11 111 SLO 0 0 0 1 SF 0 0 0 0 SE 0 0 0001 1 O O 0 Solving Method Select the GRG Nonlinear engine for Solver Problems that are smooth nonlinear. Select the LP Simplex engine for linear Solver Problems, and select the Evolutionary engine for Solver problems th Help [ Solve close Sheet1 Point + 80%

X f r Total_Hubs - A Solver Parameters B 0 Western Airlines Hubs Planning C D E F G H 0 0 0 1 0 I 0 J 0 K 1 L 1 M 1 SE Set Objective: Total_Hubs 33 Decision Variables AT = 1, If Used as a hub, o, otherwise. C H DE HOLANO NY PI SL SF SE 0 1 0 0 0 0 0 0 0 0 To: O Max O Mio BO 110 O Value Of: 35 Used as a hub? 36 37 Objective Function 38 Total Hubs (Minimize) By Changing Variable Cells: Hub Locations 39 Subject to the Constraints: Covered_Hubs >= Least_Hubs Hub Locations - binary Add Change Delete 40 Constraints 41 1. All Decision variables are binary (0,1). 42 2. Each city must be covered by at least one hub. 43 City Covered by Hubs Least Hubs Reqd. AT Во 1 2 CH DE 2 HO 22 LA 1 2 NO NY PI SL SF Reset All Load/Save Make Unconstrained Variables Non-Negative Select a Solving Method: Simplex LP Options SE Solving Method Select the GRG Nonlinear engine for Solver problems that are smooth nonlinear. Select the LP Simplex engine for linear Solver Problems, and select the Evolutionary engine for Solver problems that are non-smooth 57 Range Names 58 Within_Hub 59 Hub_Locations 60 Total_Hubs 61 Covered_Hubs 62 Least_Hubs Sheet1 Point om =$B$20:$M$31 =$B$35:$M$35 $B$38 $B$44:$B$55 =$D$44:$D$55 Help o solve a close Close + 8096

Following snapshots show the formulas used in various cells:

F G H I J K L M E Western Airlines Hubs Planning wN AT сн O 3 Input Data Distance between cities AT BO CH DE 0 HO LA NO 1037 6 74 1398 789 2182 479 841 687 1878 2496 2618 1037 674 1005 10050 1949 1008 1804 1067 2979 2054 1507 912 222 802 574 1452 2343 1390 3095 2142 2976 2013 DE HOLLANO NY PI SL SF SE 1398 7892182479841687 1878 2496 2618 1949 1804 2979 1 507 222 574 2343 3095 2976 1008 1067 2054 912 802 452 13902142 2013 o 1019 1059 1273 1771 1411504 1 2351307 1019 0 1 538 356 1608 1313 1438 1912 2274 10591538 0 188327862426 715 379 1131 1273 356 1883 0 1311 1070 1738 2249 2574 1771 1608 2786 13110 368 2182 2934 2815 14111313 2426 1070 368 0 1 826 25782465 504 1438 715 1738 2182 1826 o 752 836 1235 1912 379 2249 2934 2578 752 0 808 1307 2274 1131 2574 2815 2465 836 808 0 NY SL SF SE Distance between cities Hub Miles Limit -1,500 AT BO CH DE HO LA NO NY AT =IF(B5<=1500,1,0) =IF(B6<=1500,1,0) =IF(B7<=1500,1,0) =IF(B8<=1500,1,0) =IF(B9<=1500,1,0) =IF(B10<=1500,1,0) =IF(B11<=1500,1,0) =IF(B12<=1500,1,0) =IF(813<=1500,1,0) =IF(B14<=1500,1,0) =IF(B15<=1500,1,0) =IF(B16<=1500,1,0) BO I CH =IF(C5<=15 =IF(D5<=1500,1,0) =IF(C6<=15=IF(D6<=1500,1,0) =IF(C7<=15 =IF(D7<=1500,1,0) =IF(C8<=15 =IF(D8<=1500,1,0) =IF(C9<=15 =IF(D9<=1500,1,0) =IF(C10<= 1 =IF(D10<=1500,1,0) =IF(C11<=1=IF(D11<=1500,1,0) =IF(C12<=1=IF(D12<=1500,1,0) =IF(C13<=1 =IF(D13<=1500,1,0) =IF(C14<=1 =1F(D14<=1500,1,0) =IF(C15<=1 IF(D15<=1500,1,0) =IF(C16<=1 =1F(D16<=1500,1,0) = 1, if within Miles Limit, O, if not. DE HOLA NO NY I PISLI SF SE =IF(E5<=15 =IF(F5<=15 =IF(G5<=15 =IF(H5<=15 =IF(15<=150=IF(J5<=150=1F(K5<=15 =IF(L5<=15 =IF(M5<=1 =IF(E6<=15 =IF(F6<=15 =IF(G6<=15 =IF(H6<=15 =IF(16<=150 =IF(J6<=150=IF(K6<=15 =IF(L6<=15 =IF(M6<=15 | FIF(E7<=15 - IF(F7<=15 =IF(G7<=15=IF(H7<=15 =1F(17<=150 =1F(J7<=154 =IF(K7<-15 FIF(L7<=15 -IF(M7<=15 =IF(E8<=15=IF(F8<=15=IF(G8<=15 =IF(H8<=15 =IF(18<=15=IF(J8<=15° =IF(K8<=15 =IF(L8<=15 =IF(M8<=1 =IF(E9<=15 =IF(F9<=15 =IF(G9<=15 =IF(H9<=15 =IF(19<=150 =IF(19<=150=1F(K9<=15 =IF(L9<=15 =IF(M9<=15 =IF(E10<=1 =IF(F10<=1 =IF(G10<=1=IF(H10<= 1 =IF(110<=15=IF(J10<=19=IF(K10<=1 =IF(L10<=1=IF(M10<= =IF(E11<=1 =IF(F11<=1 =IF(G11<=1=1F(H11<=1 =1F(111<=1$ =IF(J11<=15=IF(K11<=1=IF(L11<=1 =IF(M11<= =IF(E12<=1 =IF(F12<=1 =1F(G12<=1=IF(H12<=1 =IF(112<=1$ =IF(J12<=1=IF(K12<=1 =IF(L12<=1 =IF(M12<= =IF(E13<=1 =IF(F13<=1=IF(G13<=1=IF(H13<= 1 =IF(113<=15 =IF(J13<=15=IF(K13<=1 =IF(L13<=1 =IF(M13<= =IF(E14<=1 =1F(F14<=1 =IF(G14<=1=IF(H14<= 1 =1F(114<=15 =IF(J14<=1=IF(K14<=1 =IF(L14<=1 =IF(M14<= IF(E15<=1 IF(F15<=1=IF(G15<=1=IF(H15<=1 IF(115<=15=IF(J15<=15 IF(K15<=1=IF(L15<=1=IF(M15<= =IF(E16<=1 =IF(F16<=1 =1F(G16<=1=IF(H16<= 1 =1F(116<=15 =IF(J16<=1=1F(K16<=1 =1F(L16<=1 =IF(M16<= PI SL Sheet1 Ready a U -- + 80%

E F G H I T K L M - IF(E16<=1 IF(F16<=1 -IF(G16<1 -IF(H16<1 -IF(116<=1 =1F(J16<=1 IF(K16<=1 -IF(L16<=1 IF(M16 SE -IF(B16<=1500,1,0) =IF(C16<=1 -1F(D16<=1500,1,0) www 33 Decision Variables = 1, if Used as a hub, o, otherwise. DE HOLANONY PISL SESE AT | ВО CH 35 Used as a hub? 36 37 Objective Function 38 Total Hubs (Minimize) SUM(Hub Locations) Least Hubs Reqd. 2 40 Constraints 41 1. All Decision variables are binary (0,1). 42 2. Each city must be covered by at least one hub. 43 City 44 AT Во CH DE HO LA NO NY PI Covered by Hubs SUMPRODUCT(B20:M20, Hub_Locations) ESUMPRODUCT(B21:M21, Hub_Locations) SUMPRODUCT(B22:M22,Hub Locations) SUMPRODUCT(B23:M23,Hub Locations) SUMPRODUCT(B24:M24,Hub_Locations) SUMPRODUCT(B25:M25,Hub Locations) SUMPRODUCT(B26:M26, Hub_Locations) -SUMPRODUCT(B27:M27, Hub_Locations) SUMPRODUCT(B28:M28,Hub Locations) =SUMPRODUCT(B29:M29, Hub_Locations) SUMPRODUCT(B30:M30,Hub_Locations) SUMPRODUCT(B31:M31,Hub Locations) 2 1 SL SF SE 2 1 57 Range Names 58 Within_Hub 59 Hub_Locations 60 Total_Hubs 61 Covered_Hubs 62 Least Hubs Sheet1 Ready $B$20:$M$31 -$B$35:$M$35 =$B$38 =$B$44:$B$55 $D$44:$D$55 - + 80%

Answer: As we see in the optimized state of the model (in the snapshots), the recommended hub locations are Atlanta and Denver.