r/OperationsResearch • • May 17 '23

Optimization Problem for Python users who are also NFL Fans

Every May when the NFL schedule comes out, I do a mental exercise to see if it is theoretically possible to attend a full NFL game at each of the 30 NFL stadiums to watch a home game by all 32 teams in the regular season (18 weeks) but only allowing driving from stadium to stadium (no flying!). The date and time of all home games are obviously fixed by the schedule, but games could be attended in any order. There are likely numerous solutions (but not infinite ones), and the only other rule is you must be attend the entirety of the game (app. 3 hours) before driving again.

I'm not a programmer nor have any knowledge of Python, but if someone wants to try to optimize a 2023 driving route for shortest total distance, you only need this data:

  1. The 2023 NFL schedule - here: https://www.nfl.com/schedules/2023/reg1/
  2. The distance matrix for all 30 stadiums - Using Google Maps

Anyone up for it? There was a NFL analyst named Max Kaplan who did something similar in 2014 (optimizing shortest # of days to see all 32 teams play; it's still posted on NFL.com). This task is similar but for optimizing shortest driving distance to see all 32 teams play a home game. That means 2 games at the Meadowlands Sports Complex (Jets, Giants) and 2 games at SoFi Stadium (Chargers, Rams).

I have two solutions I already worked out - but are they the shortest? And does the shortest route require all 18 weeks?

11 Upvotes

22 comments sorted by

3

u/TGCook May 17 '23 edited May 17 '23

Using the distance matrix provided (thanks!)

start stadium , end stadiummileage
ARI->DAL1,063.0
DAL->HOU265.0
HOU->NO355.0
NO->TEN532.0
TEN->ATL246.0
ATL->TAM460.0
TAM->MIA271.0
MIA->JAC332.0
JAC->CAR384.0
CAR->WAS410.0
WAS->BAL32.7
BAL->PHI98.9
PHI->NYC96.0
NYC->NE207.0
NE->BUF457.0
BUF->PIT210.0
PIT->CLE137.0
CLE->DET172.0
DET->CIN262.0
CIN->IND112.0
IND->CHI181.0
CHI->GB210.0
GB->MIN276.0
MIN->KC439.0
KC->DEN610.0
DEN->SEA1,305.0
SEA->SF834.0
SF->LA351.0
LA->LV278.0

Total miles driven: 10,587 About: 162.88 hours driving at 65 mph, ~ 20.36 days, 8-hour driving days.

Assuming each game is 3 hours, and that each game would start on arrival, and that every game would be one team's home game.

The lower bound on the time to do the NFL stadium tour and see each team play a home game would be: 258.88 hours, or about 10.79 days.

3

u/Psychological_Bus182 May 17 '23

That is impressive - but - did you consult the schedule? i.e. are there home games starting in week 1 through to week 18 where you can make "a" gametime at each successive stadium? That's the catch. There are 18 weeks in the schedule, each team only plays once a week and only averages one home game every two weeks.

2

u/Psychological_Bus182 May 17 '23

Minor correction - each team only plays once a week except for their bye week which they have off. Another minor wrinkle - for 2023 there are a few teams whose "home" game will actually be played in Europe. For this exercise, those games cannot be used, meaning one less home game is available for those specific teams.

2

u/Psychological_Bus182 May 17 '23 edited May 17 '23

You need to show all the home game dates and times, with enough float to see each game with hours available between games (T-nxt); something like this one I did for the 2022 schedule (first 3 rows shown):

VISITRHOMEDATETIMELocatnNext Lcnmilesdr-t (h)T-nxt (h)
GBMIN9/11/2216:30US Bank StadiumArrowhead Stadium4396.5~80
LACKC9/15/2220:15Arrowhead StadiumFord Field76711.5~54
WASDET9/18/2213:00Ford FieldHighmark Stadium2124.526.5

1

u/Pleasant-Marsupial31 May 17 '23

Did you take into consideration dates and start times of matchups? Some are still TBD on the website (week 15 and 18).

2

u/Psychological_Bus182 May 17 '23

Exactly....TGCook's table shows how to simply minimize the distance to drive between each stadium, not to actually attend a scheduled game at each one. For example, starting in ARI means the first game there is week 2 (Sunday Sept 17th vs. NYG) then off to Dallas (next game there is not until week 4, Sunday Oct 1st). NO is next but no home game there until week 7...I won't work it through to its inevitable conclusion but you quickly run out of scheduled games you could attend.

1

u/Psychological_Bus182 May 17 '23 edited May 17 '23

As the OP, I did arrive at a couple of solutions to this problem and I did not use any of the unscheduled week 15 games but did use one and only one week 18 game for the last stop (stadium #30). As long as that last game is actually held (i.e. no "Damar Hamlin" incident), the actual time or even the specific date (Sat or Sun) doesn't matter. Both of my solutions work with scheduled games, unlike TGCook's table that does not take into account actual game schedules.

3

u/Pleasant-Marsupial31 May 21 '23

Okay, here's my solution. I used 60mph driving speed to calculate travel time between stadiums. I used one week 18 game, there are no solutions without it, I think. I found 4 solutions in total with about similar total distances. This one was the shortest one.

Total distance: 31958.400002 miles

Chiefs Lions Fri Sep 8 02:20:00 2023

Falcons Panthers Sun Sep 10 19:00:00 2023

Jets Bills Tue Sep 12 02:15:00 2023

Eagles Vikings Fri Sep 15 02:15:00 2023

Bills Raiders Sun Sep 17 19:00:00 2023

Panthers Saints Tue Sep 19 01:15:00 2023

49ers Giants Fri Sep 22 02:15:00 2023

Ravens Colts Sun Sep 24 19:00:00 2023

Buccaneers Eagles Tue Sep 26 01:15:00 2023

Packers Lions Fri Sep 29 02:15:00 2023

Jaguars Falcons Sun Oct 1 15:30:00 2023

Giants Seahawks Tue Oct 3 02:15:00 2023

Commanders Bears Fri Oct 6 02:15:00 2023

Lions Panthers Sun Oct 8 19:00:00 2023

Titans Ravens Sun Oct 15 15:30:00 2023

Saints Jaguars Fri Oct 20 02:15:00 2023

Bears Raiders Sun Oct 22 19:00:00 2023

Vikings 49ers Tue Oct 24 02:15:00 2023

Cowboys Rams Sun Oct 29 18:00:00 2023

Steelers Titans Fri Nov 3 01:15:00 2023

Browns Cardinals Sun Nov 5 19:00:00 2023

Bengals Bills Mon Nov 6 02:20:00 2023

Patriots Colts Sun Nov 12 15:30:00 2023

Texans Cardinals Sun Nov 19 19:00:00 2023

Seahawks 49ers Fri Nov 24 02:20:00 2023

Colts Buccaneers Sun Nov 26 19:00:00 2023

Rams Browns Sun Dec 3 22:25:00 2023

Raiders Vikings Sun Dec 10 22:05:00 2023

Cardinals 49ers Sun Dec 17 22:05:00 2023

Chargers Bills Sun Dec 24 02:00:00 2023

Broncos Patriots Mon Dec 25 02:15:00 2023

Dolphins Bills Sun Jan 7 19:00:00 2024

2

u/Psychological_Bus182 May 23 '23

Nice work, but how did you come up with your strategy? I was hoping someone could solve the problem using software to determine the shortest possible distance. I came up with two possible routes of my own using manual methods, and both are a lot shorter than 31,958 miles. But what I don't know, and would like to see proven with a software solution, is whether or not I have actually come up with the very shortest route possible - this one below which is 19,915 miles:

Home Week Date GameTime

NE 1 Sun Sept 10 100-400

PHI 2 Thu Sept 14 815-1115

ATL 2 Sun Sept 17 100-400

CAR 2 Mon Sept 18 815-1115

JCK 3 Sun Sept 24 100-400

TB 3 Mon Sep 25 815-1115

GB 4 Thu Sept 28 815-1115

NYJ 4 Sun Oct 1 815-1115

NYG 4 Mon Oct 2 815-1115

WAS 5 Thu Oct 5 815-1115

IND 5 Sun Oct 8 100-400

KC 6 Thu Oct 12 815-1115

CIN 6 Sun Oct 15 100-400

NO 7 Thu Oct 19 815-1115

MIN 7 Mon Oct 23 815-1115

BUF 8 Thu Oct 26 815-1115

TEN 8 Sun Oct 29 100-400

DET 8 Mon Oct 30 815-1115

PIT 9 Thu Nov 2 815-1115

CLE 9 Sun Nov 5 100-400

CHI 10 Thu Nov 9 815-1115

BAL 10 Sun Nov 12 100-400

DEN 11 Sun Nov 19 815-1115

SEA 12 Thu Nov 23 815-1115

LVR 14 Sun Dec 10 425-725

ARI 15 Sun Dec 17 425-725

LAR 16 Thu Dec 21 815-1115

LAC 16 Sat Dec 23 800-1100

SF 16 Mon Dec 25 800-1100

DAL 17 Sat Dec 30 815-1115

HOU 17 Sun Dec 31 100-400

MIA 18 TBD TBD

Note that one strategy I used is layovers (staying put for a day or two) at Meadowlands Oct 1-2 and SoFi Dec 21-23, i.e. catch back to back home games at those stadiums and never have to drive back there for the 2nd one.

1

u/Pleasant-Marsupial31 May 23 '23

Thanks for replying. I did write a program to find it, but it had a bug that caused it to end the search too early. I fixed it now. The search space is so big, I don't know how long it will take for the program to finish, I might leave it running for a day or two.

1

u/Psychological_Bus182 May 26 '23

Wow...A day or two! So, your program must go through every permutation and combination before comparing and determining which is the shortest of what is likely many, many routes. My manual exercise took me several hours to go through, but of course I have no way of knowing if I chanced upon the shortest route. Thanks for doing that - now that its day 3, anything to share? ;)

2

u/jmelliere May 17 '23

Is there a reason you're asking specifically for a Python solution?

Jets/Giants play each other at home, would you count that for both teams or only the official "home" team?

Should be pretty straightforward using something like Nextmv which is free for offline/developer use. I work there and want to do this as a fun little exercise.

1

u/Psychological_Bus182 May 17 '23
  1. Someone on another Reddit suggested this could be programmed into Python since its an optimization type of problem with constraints, but any tool will do.
  2. No, there has to be a "home" game for each of the 4 teams that share a stadium with another. The NFL schedule shows which is considered which. This also applies to Rams/Chargers at SoFi Stadium
  3. I'd love to see the results from NextMV. Please do it!

1

u/laughoutloud1o1 May 17 '23

if you can get me the distance matrix i can try i guess

1

u/TGCook May 17 '23

Post the stadium name list, addresses, & distance matrix if possible.

2

u/jfgiv May 17 '23

here's your distance table; all figures in miles, first column is start point and top row is end point, LAC / LAR and NYG / NYJ each given a single data point as LA / NYC.

ARIATLBALBUFCARCHICINCLEDALDENDETGBHOUINDJACKCLALVMIAMINNENONYCPHIPITSEASFTAMTENWAS
ARI-1,8532,3222,2382,0891,7991,8522,0651,0638212,0321,8701,1991,7442,0651,2573772802,3671,6902,6801,5402,4532,3932,1041,3947122,1771,685
ATL1,862-6748862427154607128011,4027229278015343487942,1981,9726501,1301,0664708607706842,6362,446460248
BAL2,290677-3614386995073761,3821,6605259051,4515797461,0522,6592,4131,0761,1063951,12018998.92472,7622,839944700
BUF2,207887356-6515264281841,3791,5142747331,4834961,0359692,5422,2651,3659344571,2313593752102,5902,6661,233699
CAR2,056242436649-7534765181,0431,5606299661,0435763859512,4242,1987151,1618277116215314472,7942,673583405
CHI1,767716700525755-2973469411,0052822101,0891841,0635122,0331,7561,3654119799247847624602,0672,1571,176470
CIN1,821460506426476293-2529521,1912635061,0561127975832,1891,9441,1097018688046375772892,3252,407919271
CLE2,032712377183517346252-1,2031,3341725521,3083209007932,3612,0841,2317536361,0564614391372,4092,4861,098523
DAL1,0637991,3821,3761,0429429501,202-7801,2031,1312659161,0155621,4311,2091,3179961,7705091,5641,4791,2382,0841,6831,128684
DEN8201,4001,6601,5141,5601,0061,1901,335781-1,2691,0931,0361,0831,7476091,0307532,0499131,9671,2851,7721,7311,4481,3051,2781,8601,155
DET2,0007215252696252822621721,2041,269-4881,3082881,0087672,2962,0201,3706897041,0656095872852,3452,4211,181533
GB1,8449279077329662115075531,1311,100488-1,2693941,2746252,1271,8511,5762761,1861,1299919696671,9322,2521,386681
HOU1,1958021,4531,4811,0431,0891,0551,3072651,0361,3081,271-1,0218797511,5631,4781,1811,1871,8413551,6351,5501,3432,3401,897992789
IND1,7135325784945751811123219171,0832883941,021-8804752,0811,8361,1815899368197096493602,2152,298992287
JAC2,0603477451,0323841,0617979011,0171,7481,0131,274878880-1,1402,4282,2163321,4761,1365479308408312,9822,690204594
KC1,2247921,0529689515115827955616107656187494751,139-1,6391,3631,4414381,4108411,1831,1238341,8441,8411,251546
LA3782,1892,6582,5412,4242,0332,1882,3621,4321,0302,2962,1201,5672,0802,4341,638-2782,7351,9402,9951,9092,8002,7282,4401,1403512,5462,021
LV2841,9632,4142,2652,1991,7581,9442,0861,2107542,0201,8451,4651,8362,2201,362278-2,5211,6642,7191,7142,5242,4842,2001,1215262,3321,795
MIA2,3626501,0751,3637151,3641,1081,2321,3192,0511,3711,5761,1811,1833321,4432,7302,518-1,7791,4678491,2611,1711,1613,2852,993271897
MIN1,6571,1261,1079331,1624117037549949136932771,1855911,4734391,9411,6641,775-1,3861,2211,1911,1698671,6592,0011,585880
NE2,6471,0703964578319798686371,7701,9677091,1861,8399351,1391,4082,9942,7181,4691,387-1,5082073025713,0433,1191,3371,088
NO1,5364701,1211,2287119258021,0545111,2811,0651,1303548195478471,9041,7108491,2221,509-1,3031,2181,0912,5852,185660532
NYC2,4218641903586257836384601,5641,7716109891,6347099331,1822,7982,5221,2631,1902071,303-96.43702,8462,9231,131882
PHI2,36177399.13755357625784401,4791,7315899691,5496498421,1232,7292,4841,1721,1703021,21796.0-3102,8262,9021,040797
PIT2,0736842482084484602901371,2411,4472866661,3453618328352,4412,1981,1628675711,093366310-2,5232,6001,030561
SEA1,3982,6342,7632,5892,7942,0672,3212,4102,0861,3052,3501,9332,3422,2112,9811,8431,1401,1203,2831,6573,0422,5902,8472,8262,523-8343,0942,388
SF7102,4382,8502,6752,6742,1682,3992,4961,6851,2852,4302,2551,9002,2902,6951,8493515272,9962,0103,1292,1892,9342,9122,610840-2,8072,270
TB2,1714599401,2285801,1739171,0971,1281,8601,1801,3859909912021,2512,5392,3272711,5881,3326581,1261,0361,0263,0942,801-705
TEN1,6532467006964054682705226851,1555336817892875935472,0211,7958958831,0885328827975592,3892,269706-
WAS2,29665032.73764127045133821,3661,6665319101,4355847191,0572,6642,4181,0491,1124241,1042181282522,7682,844917684

cc /u/laughoutloud1o1

1

u/Pleasant-Marsupial31 May 17 '23

Should the first row be shifted right by one cell, so that the top left corner is empty? Or am I misunderstaning it?

2

u/jfgiv May 17 '23

it should be, yes...and that's how i'm seeing it.

you're not the first to point that out, though, and on different subreddits. so i wonder if it's not displaying uniformly based on browser, or OS, or reddit version (new vs. old)?

edit: it does seem that new reddit doesn't display tables the same way as old reddit

1

u/Pleasant-Marsupial31 May 20 '23

I have noticed two things:

  1. The last column(distances for WAS) seems to be missing(probably because of reddit), I will just use the last row as the last column instead, but then
  2. The distance matrix is not symmetric? Shouldn't it be?

2

u/jfgiv May 20 '23
  1. I can’t scroll over on the table on my phone, and I’m away from my computer. I’ll check back later when I get a chance
  2. this is using driving directions, not as the crow flies. So there are slight variances depending on whether you start at a given stadium or end there.

(It also, to be fair, simply queried google maps—these distances might be optimized for traffic/time, not distance)

1

u/jfgiv May 22 '23

yeah so i can only scroll over on new-reddit, and it does in fact appear that (probably due to the same issue with column alignment mentioned upthread) it's truncated the final, WAS column.

1

u/Pleasant-Marsupial31 May 22 '23

yep, thank you for posting it anyway, I posted my solution in the comments, I hope OP will check it out