The NYC Subway Challenge - A Hierarchical MDP Approach

A reinforcement learning approach to solving the NYC subway challenge: finding an optimal (or near-optimal) route to visit all subway stations as fast as possible.

Problem Statement

Find the fastest path through all NYC subway stations. This is a variant of the Traveling Salesman Problem (TSP) with two key differences:

• Stations can be revisited (minimizing revisits is the goal)
• No requirement to return to start (minimum-cost covering walk)

The raw graph is too large for direct MDP solving, so we use graph reduction and hierarchical decomposition.

Solution Approach: Hierarchical MDP

Graph Reduction Pipeline

1. Duplicate Collapse: Merge walkable duplicate stations (e.g., connected transfer points)
2. Corridor Removal: Remove degree-2 nodes (corridor stations with no decision points), bridging their endpoints
3. Result: ~80 core decision-point stations from 472 original stations

Two-Level Hierarchical MDP

Level 1 - Low-Level (Cluster Solver):

• Betweenness-based clustering divides reduced graph into ~14 clusters of 3-18 nodes
• Per-cluster MDP with state (currentNode, visitedNodes)
• Solved via value iteration for each (entry, exit) boundary pair

Level 2 - High-Level (Cluster Sequencing):

• State: (currentCluster, currentBoundaryNode, visitedClusters)
• Actions: Move to neighboring unvisited cluster
• Solved via value iteration using pre-computed cluster policies

Project Structure

project/
├── main.py               # Main execution script
├── adjMatrixSetup.py     # Graph loading, preprocessing, reduction
├── clustering.py         # Betweenness-based clustering
├── lowMDP.py             # Low-level cluster solver (value iteration)
├── highMDP.py            # High-level cluster sequencing
├── viz.py                # Plotly visualizations
├── masterStations.csv    # Station metadata (names, coordinates)
├── gephiSubway_generated.csv  # Subway edge list
└── results.txt           # Generated route output

Output

results.txt contains:

• Route statistics (total steps, unique stations, revisits)
• Graph reduction statistics
• Cluster sizes and boundary nodes
• Full route with station IDs and names

Visualizations (HTML files):

• 01_original.html - Original subway graph
• 02_collapsed.html - After duplicate collapse
• 03_reduced.html - After corridor removal
• 04_clusters.html - Clustered graph with boundary nodes
• 05_cluster_route.html - High-level cluster sequence
• 06_full_route.html - Final expanded route

Reward Structure

• -1 per step (scaled by edge weight for compressed edges)
• +10 for visiting a new station
• +100 for completing a cluster
• gamma=1.0 (no discounting - all steps equally weighted)

Usage

pip install numpy pandas networkx plotly
python3 main.py

Key Parameters

In main.py:

• targetClusterSize, maxClusterSize, minClusterSize - Clustering constraints
• stepReward, visitReward, completeReward - MDP rewards