gregfeliu/the_subway_challenge

Finding the fastest way to visit each subway station using the existing MTA schedule.

The_Subway_Challenge

The Subway Challenge is a challenge for a participant to reach every station in the NYC subway network in as little time as possible. The fastest time someone was able to reach all 469 stations was set in 2016 by Matthew Ahn at a time of 21 hours and 28 minutes. Since then, three new stations have opened (72nd Street, 86th Street and 96th Street) as part of the Second Avenue Subway extension. Technically, therefore, the Subway Challenge has yet to be completed for the current 472-stop MTA system. And since Matthew Ahn has kept his route secret (we only know the beginning and end of his route), one is left to wonder: what route should someone take to reach every station in the NYC subway system? How long would it take? Could the slightly-outdated record be broken, even with more stations to visit?

Process

This project attempts to answer a seemingly simple question: what's the quickest way to visit all 472 NYC subway stations? The process to answering this question will go something like this:

1. Gather data on expected train times for a specific period: In other words, we'll consider a typical amount of time for a train route and then use that in our calculations. The train routes all follow expected train lines. For example, if a train regularly runs between station A and station B this will be a valid edge of the graph.
2. Build the NYC subway network: Once we have the amount of time between each staiton (node) on our graph, we will treat the distance between each point (including any transfers) as the distance (weight) between nodes on this graph.
3. Run a Graph Traversal Algorithm to find shortest "distance" to visit all nodes: This is a well studied problem in computer science because of the challenge to limit the processing time needed to find the (near) optimal solution.
4. Complete the Travelling Salesman Problem: This classic computer science problem attempts to visit all nodes in a graph, starting and ending at the same node, as efficiently as possible. Although the task here does not include the constraint of starting and ending at the same node, the fact that there are many easily available implementations (Google's OR-Tools was the one used here) of this problem mean it will greatly simplify building the route.

Results

After running the Travelling Salesman Problem implementation, we found a route that starts in Far Rockaway Beach and ending in Van Cortlandt to be the fastest possible route.