Sets s "stadiums" / BUF,MIA,NE,NYJ,BAL,CIN,CLE,PIT,HOU,IND,JAX,TEN,DEN,KC,LV,LAC,DAL,NYG,PHI,WAS,CHI,DET,GB,MIN,ATL,CAR,NO,TB,ARI,LAR,SF,SEA / i "game indices" / 1 * 9 / g(i,s) "games" / #i.#s / legal(i,s,i,s) "legal connections from one game to another" magic(i,s,i,s) "travel backwards in time - used for subtour elimination" illegal(i,s,i,s) "travel involving a game that does not exist,ex. index 9 for a team with only 8 home games" / (9.MIN,9.NE,9.NYG,9.ARI,9.CAR,9.SF,9.GB,9.TEN,9.DAL,9.WAS,9.BUF,9.KC,9.DET,9.TB,9.ATL,9.JAX,9.SEA,9.LAR,9.NO,9.CHI,9.PHI).(1*8.MIN,1*8.NE,1*8.ARI,1*9.LAC,1*8.CAR,1*8.SF,1*9.BAL,1*8.GB,1*9.NYJ,1*9.IND,1*8.TEN,1*8.WAS,1*8.BUF,1*9.CLE,1*9.LV,1*8.KC,1*9.DEN,1*9.MIA,1*8.ATL,1*8.LAR,1*8.CHI,1*8.NYG,1*9.PIT,1*9.CIN,1*8.DAL,1*8.DET,1*8.TB,1*8.JAX,1*8.SEA,1*8.NO,1*9.HOU,1*8.PHI), #i.#s.(9.MIN,9.NE,9.NYG,9.ARI,9.CAR,9.SF,9.GB,9.TEN,9.DAL,9.WAS,9.BUF,9.KC,9.DET,9.TB,9.ATL,9.JAX,9.SEA,9.LAR,9.NO,9.CHI,9.PHI) / ; Alias (g,gg); Alias (s,ss); Alias (i,ii); Scalar gameLength / 240 / ; Scalar overnight / 700 / ; ; * travel time in minutes between each pair of teams Table travelTime(s,ss) BUF MIA NE NYJ BAL CIN CLE PIT HOU IND JAX TEN DEN KC LV LAC DAL NYG PHI WAS CHI DET GB MIN ATL CAR NO TB ARI LAR SF SEA BUF 0 1211 412 355 381 386 169 191 1351 445 934 629 1343 865 2005 2249 1234 355 372 405 481 274 668 841 795 603 1091 1118 1965 2249 2361 2292 MIA 1211 0 1292 1088 922 945 1083 1029 1010 1011 282 760 1761 1240 2201 2352 1151 1088 1013 892 1179 1181 1365 1524 547 611 714 230 2019 2352 2635 2876 NE 414 1298 0 208 379 789 572 546 1657 847 1021 994 1745 1267 2403 2652 1602 208 295 409 884 661 1071 1244 987 766 1361 1206 2367 2652 2763 2695 NYJ 355 1093 208 0 175 595 420 348 1453 657 817 790 1570 1077 2228 2476 1398 0 91 205 708 551 895 1068 783 562 1157 1001 2177 2482 2588 2519 BAL 380 925 375 171 0 481 350 235 1288 544 649 625 1485 964 2145 2372 1233 171 96 38 639 481 826 999 615 395 992 834 2064 2372 2518 2450 CIN 384 952 785 592 474 0 225 265 969 104 705 246 1042 521 1702 1929 852 592 533 482 270 237 457 629 413 449 709 796 1621 1929 2112 2077 CLE 169 1081 570 420 351 227 0 126 1192 286 804 469 1177 705 1840 2089 1075 420 404 358 316 159 503 676 636 473 932 989 1805 2089 2195 2127 PIT 194 1029 545 349 236 269 131 0 1234 332 753 511 1273 752 1933 2160 1117 349 290 243 419 262 606 779 641 422 974 937 1852 2160 2299 2230 HOU 1344 1015 1659 1455 1290 962 1186 1226 0 926 767 728 931 692 1289 1362 238 1455 1381 1273 979 1184 1161 1074 709 932 321 858 1029 1362 1657 2104 IND 447 1015 848 660 542 104 289 333 925 0 768 258 946 425 1606 1833 808 660 601 549 173 265 360 532 476 543 720 859 1525 1833 2015 1983 JAX 935 283 1016 812 646 700 808 754 764 766 0 515 1515 995 1955 2107 906 812 737 616 933 928 1120 1279 302 336 469 196 1774 2107 2390 2630 TEN 624 761 994 790 626 242 466 505 730 255 514 0 1005 484 1574 1783 613 790 717 609 423 477 609 768 222 380 466 605 1474 1783 2008 2120 DEN 1346 1757 1746 1574 1478 1037 1181 1269 933 943 1510 1000 0 525 666 920 707 1574 1537 1486 885 1114 976 797 1219 1376 1161 1601 768 915 1136 1179 KC 865 1239 1266 1078 960 519 707 751 692 425 992 482 528 0 1194 1437 490 1078 1019 967 457 682 568 389 700 858 772 1083 1139 1437 1624 1643 LV 2002 2200 2403 2230 2137 1696 1838 1928 1282 1602 1952 1566 665 1184 0 254 1057 2230 2196 2145 1542 1771 1633 1453 1721 1940 1510 2044 272 254 480 1032 LAC 2250 2357 2651 2477 2359 1918 2086 2150 1363 1824 2110 1772 913 1432 254 0 1252 2477 2418 2367 1790 2019 1881 1701 1927 2146 1664 2201 348 0 327 1063 DAL 1224 1154 1597 1393 1228 842 1066 1106 237 806 907 608 708 489 1063 1252 0 1393 1319 1211 859 1064 1032 866 706 932 465 998 919 1252 1497 1881 NYG 355 1094 208 0 175 595 420 348 1453 657 817 790 1570 1077 2233 2482 1398 0 91 205 708 551 895 1068 783 562 1157 1001 2177 2482 2588 2519 PHI 374 1019 293 89 100 539 408 292 1381 602 742 719 1542 1021 2207 2429 1326 89 0 131 695 538 882 1056 708 487 1086 927 2122 2430 2575 2506 WAS 405 894 407 203 37 489 358 243 1270 552 617 608 1493 972 2153 2380 1216 203 128 0 647 489 834 1006 583 363 975 802 2072 2380 2526 2458 CHI 481 1181 882 710 640 270 317 416 979 173 934 424 879 460 1542 1791 862 710 693 647 0 254 193 366 642 706 804 1025 1569 1791 1897 1817 DET 274 1185 656 552 482 237 159 258 1185 265 928 479 1113 686 1776 2024 1068 552 536 489 254 0 441 614 646 597 942 1029 1785 2024 2131 2065 GB 669 1368 1070 898 828 457 505 604 1161 359 1121 610 973 570 1636 1884 1034 898 881 835 194 441 0 246 829 892 987 1211 1697 1884 1991 1697 MIN 839 1522 1240 1067 998 625 675 773 1074 528 1275 764 792 389 1455 1704 866 1067 1051 1005 363 611 247 0 983 1060 1083 1365 1516 1704 1764 1457 ATL 790 547 984 780 614 408 632 643 704 474 300 223 1223 703 1723 1932 708 780 705 584 641 643 828 987 0 232 409 390 1616 1932 2158 2338 CAR 602 611 760 556 390 444 475 421 926 539 335 379 1379 858 1947 2156 933 556 481 360 705 595 892 1064 230 0 631 520 1841 2156 2381 2494 NO 1087 718 1361 1157 993 704 928 968 319 718 470 466 1157 772 1512 1661 462 1157 1084 976 803 940 986 1084 412 635 0 561 1329 1661 1946 2329 TB 1121 232 1202 998 833 791 994 940 856 857 195 606 1607 1086 2047 2198 997 998 924 803 1025 1027 1211 1371 393 522 560 0 1865 2198 2481 2722 ARI 1956 2026 2357 2169 2051 1610 1798 1842 1031 1516 1778 1464 764 1137 270 349 920 2169 2110 2058 1560 1774 1693 1514 1617 1838 1332 1869 0 349 643 1292 LAR 2250 2357 2651 2477 2359 1918 2086 2150 1363 1824 2110 1772 913 1432 254 0 1252 2477 2418 2367 1790 2019 1881 1701 1927 2146 1664 2201 348 0 327 1063 SF 2349 2634 2750 2577 2507 2096 2184 2283 1656 2002 2387 2000 1127 1611 482 328 1491 2577 2561 2515 1888 2118 1980 1759 2155 2374 1945 2478 641 328 0 782 SEA 2289 2873 2690 2518 2448 2075 2125 2224 2102 1978 2626 2116 1179 1641 1039 1065 1877 2518 2501 2455 1814 2062 1697 1456 2334 2492 2330 2717 1298 1065 785 0 ; * starting time for each game, counting in minutes from the first kickoff of the season Parameter startTime(i,s) / 1.KC = 0 (1.ATL,1.BAL,1.CLE,1.IND,1.MIN,1.NO,1.PIT,1.WAS) = 3880 (1.CHI,1.DEN,1.LAC,1.NE,1.SEA) = 4085 1.NYG = 4320 1.NYJ = 5755 1.PHI = 10075 (2.ATL,1.BUF,1.CIN,1.DET,1.HOU,1.JAX,1.TB,1.TEN) = 13960 (1.ARI,1.LAR) = 14145 (1.DAL,2.DEN) = 14165 2.NE = 14400 1.CAR = 15775 2.PIT = 15835 1.SF = 20155 (1.MIA,2.BAL,2.CLE,2.DET,1.GB,2.JAX,2.MIN,2.NYJ,2.WAS) = 24040 2.SEA = 24225 (2.ARI,2.KC) = 24245 1.LV = 24480 2.TB = 25855 2.CIN = 25915 2.GB = 30235 (2.TEN,2.BUF,2.CAR,2.CHI,3.CLE,2.HOU,2.IND,2.NO,2.PHI) = 34120 2.LAC = 34305 (2.DAL,2.SF) = 34325 3.NYJ = 34560 2.NYG = 35995 3.WAS = 40315 (3.ATL,3.DET,3.IND,2.MIA,3.NE,3.PIT) = 44200 (3.ARI,2.LAR) = 44385 (3.DEN,3.MIN) = 44405 3.SF = 44640 2.LV = 46075 3.KC = 50395 (3.JAX,4.ATL,3.CHI,3.CIN,4.CLE,3.HOU,3.MIA,3.TB) = 54280 3.LV = 54465 (3.LAR,4.NYJ) = 54485 3.BUF = 54720 3.LAC = 56155 3.NO = 60475 (4.IND,3.BAL,4.CHI,4.NE,3.NYG,4.TB) = 64360 (4.LAR,3.SEA) = 64545 (4.DEN,4.KC) = 64565 3.PHI = 64800 4.MIN = 66235 4.BUF = 70555 (3.GB,3.CAR,3.DAL,5.IND,4.MIA,4.NYG,4.PIT,3.TEN,4.WAS) = 74440 4.SEA = 74625 (4.ARI,5.DEN,4.SF) = 74645 4.LAC = 74880 4.DET = 76315 5.PIT = 80635 (5.CLE,5.ATL,4.BAL,4.GB,4.HOU,5.NE,4.NO) = 84580 4.CAR = 84765 (4.LV,4.PHI) = 84785 4.CIN = 85020 5.NYJ = 86455 5.CHI = 90775 (5.CIN,5.BAL,4.JAX,5.MIN,6.PIT,5.TB) = 94660 (5.ARI,5.LAC) = 94845 (4.DAL,5.SEA) = 94865 5.LV = 95100 5.BUF = 96535 6.BAL = 100855 (5.WAS,5.CAR,6.CLE,5.DET,5.GB,5.HOU,5.JAX,5.MIA) = 104740 5.SF = 104925 (6.BUF,5.LAR) = 104945 6.DEN = 105180 5.KC = 106615 6.DET = 110470 5.DAL = 110710 6.SEA = 110940 6.NYJ = 112060 (6.ATL,6.CIN,6.HOU,6.IND,5.NYG,4.TEN) = 114820 (7.DEN,6.ARI) = 115005 (6.LV,5.PHI) = 115025 6.LAC = 115260 6.MIN = 116695 6.DAL = 121015 (6.NE,5.NO,7.NYJ,7.PIT,6.TB,5.TEN,6.WAS) = 124900 7.HOU = 125085 (6.LAR,6.PHI) = 125105 6.GB = 125340 6.JAX = 126775 8.PIT = 131095 (7.ATL,7.BAL,6.CHI,7.CIN,7.CLE,6.NO,8.NYJ) = 134980 (7.LV,6.SF) = 135165 (6.KC,7.LAC) = 135185 7.DAL = 135420 (6.MIA,6.NYG) = 136855 8.LV = 141175 (6.CAR,8.CIN,8.CLE,7.DET,7.GB,7.IND,7.MIA,7.NO,6.TEN) = 145060 (7.ARI,7.LAR) = 145245 (7.BUF,7.SEA) = 145265 7.JAX = 145500 7.NE = 146935 8.LAR = 151255 9.PIT = 153910 8.LAC = 154120 (8.ATL,7.CAR,8.HOU,7.MIN,9.NYJ,7.TEN) = 155140 7.TB = 155325 (7.CHI,8.MIA) = 155345 8.DEN = 155575 7.KC = 156580 7.PHI = 156790 7.SF = 157015 9.CLE = 161335 8.DAL = 164215 (8.BAL,8.BUF,8.CHI,9.HOU,8.IND,8.JAX,7.NYG,8.PHI,8.TB,7.WAS) = 165220 8.SEA = 165405 (9.DEN,8.KC) = 165425 8.MIN = 165660 (9.BAL,8.CAR,9.CIN,8.DET,8.GB,9.IND,9.MIA,8.NE,8.NO,8.NYG,8.TEN,8.WAS) = 175300 8.ARI = 175485 (9.LAC,9.LV,8.SF) = 175505 / ; * magic arcs are any going backwards in time magic(i,s,ii,ss)$(startTime(ii,ss) < startTime(i,s)) = yes; * but not if they connect the same stadium magic(i,s,ii,s) = no; * and not if they involve illegal game indices magic(illegal) = no; * legal arcs connect forwards in time, as long as the travel time is shorter than the difference between start times legal(i,s,ii,ss)$(startTime(ii,ss) > startTime(i,s) AND ( (travelTime(s,ss) < (startTime(ii,ss) - startTime(i,s) - gameLength)) * or if the two games are on different days, then a flight is OK OR overnight < (startTime(ii,ss) - startTime(i,s)))) = yes; * but not if they connect the same stadium legal(i,s,ii,s) = no; * and not if they involve illegal game indices legal(illegal) = no; *finally, mark any other arcs as illegal illegal(i,s,ii,ss) = not(magic(i,s,ii,ss) + legal(i,s,ii,ss)); Binary Variables * x is a decision variable with a value of 1 if travel from game 1 to game 2 is part of the solution x(i,s,i,s) Free Variables mileage; Equations obj "objective function" remove(i,s,i,s) "disallow illegal edges" leave(s) "depart each stadium once" arrive(s) "arrive each stadium once" balance(i,s) "arrive and depart each game equal number of times" subtour "subtour elimination"; obj.. mileage =e= sum(legal(i,s,ii,ss),travelTime(s,ss)*x(legal)); leave(s).. sum((i,gg),x(i,s,gg)) =e= 1; arrive(s).. sum((i,gg),x(gg,i,s)) =e= 1; balance(g).. sum(gg,x(g,gg)) =e= sum(gg,x(gg,g)); remove(illegal).. x(illegal) =e= 0; subtour.. sum(magic,x(magic)) =e= 1; Model nfl /all/ ; option reslim = 28500; option solprint = off ; Solve nfl using mip minimizing mileage; Display x.l ;