Incheon Line 2 Route Optimizer
A time-dependent TSP solver that takes the real Incheon Line 2 timetable and returns the visit order that minimizes total time — wait + travel + dwell.
Overview
Mapping apps optimize the path between two points. If you need to visit four stations on the same subway line and return, the order itself affects total time — because direction-specific headway gaps mean the "obviously shorter" geographic ordering can be slower than a longer one that lines up better with the timetable.
During my military service at Gajeong Station on Incheon Line 2, I regularly had to visit multiple stations along the line and return — a task none of the major mapping platforms (Naver Map, Kakao Map) handle, because they optimize point-to-point routes, not multi-stop sequences with return. The interesting observation that kept coming up: the order of stops, not just the choice of stops, materially changes total time. Visiting station B before C might leave you waiting eight minutes for the train back; visiting C before B might give you a two-minute wait. I built this tool to model the real Incheon Line 2 timetable, search all visit orderings exhaustively, and return the one with minimum total time — what I call the Wait-Time Paradox: shorter geographic distance isn't shorter total time when headway gaps are large.
Stack
The Problem
Multi-stop transit is missing from mapping platforms — and on a single subway line, visit order alone can swing total time by 10+ minutes.
The standard mapping-app abstraction is "shortest path between A and B." But the actual operational task — "visit A, B, C, and D, then return to start" — is a different problem, and one that nobody on Naver, Kakao, or Google Maps lets you solve. On a single subway line, the problem is sharper than it first appears: train headways aren't symmetric in both directions, off-peak gaps can stretch to ~9 minutes, peak frequencies drop to ~3 minutes. That asymmetry means the optimal visit order depends on when you arrive, not just where you're going. A naive "nearest-neighbor" sequence routinely loses to an ordering that geographically backtracks but waits less.
A → C → B path: after finishing at City Hall (C), only 2-minute wait for the northbound train to Geomam (B).
Result: A → C → B → A is faster overall, despite being "longer" geographically.
Methodology
A Time-Dependent TSP (TD-TSP) on the real timetable, solved by brute force because the realistic input size makes exhaustive enumeration both faster to implement and provably optimal.
Input: start station Sstart, visit set V = {v1, …, vn}, start time Tstart. Output: permutation P over V that minimizes total time Ttotal. Constraints: minimum work time at each stop (default 5 min), minimum wait/buffer for boarding (default 2 min), and "next train" defined by the actual schedule rather than nominal headway.
Why brute force: TD-TSP is NP-hard in general and there's a deep literature of approximation algorithms — but my actual input size is 4–6 stations per trip, where brute force is both faster to implement and provably optimal. A heuristic would have been more code, fewer guarantees, and pointless overhead at this scale.
| Decision | Why |
|---|---|
| Brute-force search over permutations | n ≤ 6 ⇒ ≤ 720 permutations per query. Provably optimal in milliseconds; no heuristic-tuning required. |
| Time-dependent edge weights | Standard TSP assumes fixed edge cost. The whole point of this problem is that Twait depends on arrival time, so edges have to be recomputed per candidate path. |
| 2-minute boarding buffer | The "next train" lookup excludes trains that would arrive at the platform too soon to realistically board. |
| Both-direction headways modeled | Up-line and down-line schedules are not symmetric. Treating them as the same headway would erase the Wait-Time Paradox entirely. |
Pipeline
Lean TypeScript codebase — single-page Vite app with a deterministic search engine on the front-end.
One enumeration loop generates all permutations of the visit set. For each candidate path, the engine walks station-by-station: at each transition it (1) computes arrival time, (2) looks up the next eligible train in the relevant direction (with the 2-minute buffer), (3) adds wait + travel + dwell, (4) accumulates into a running total. The minimum-total-time path wins, and the UI surfaces the per-leg breakdown so the user can see why the chosen order beat the obvious one.
Findings
A working, deployed tool that out-performs sequential ordering on the line I actually used it on.
The Wait-Time Paradox isn't hypothetical — for real trips I needed to take during my service, the optimizer returned visit orders that were meaningfully faster than the nearest-neighbor sequence I'd have picked by intuition. The tool is deployed and usable today; it covers Incheon Line 2 specifically because that's the line I had the use case for, not because the algorithm is line-specific.
Limitations
- Single line. Multi-line routing introduces transfers — transfer wait + walking time + line-switching delay — which significantly complicates the cost function. Input size also grows past where brute force is comfortable.
- Static timetable, not real-time. Uses the published Incheon Line 2 schedule. Doesn't account for delays, service changes, or single-train cancellations. The Incheon Transit Corporation has an open-data API that would close this gap; not yet integrated.
- Bounded by realistic input. Brute force is fine at n ≤ 6 (720 permutations). At n = 8 (40,320 permutations) or higher it would slow noticeably — but the use case is "a few stops along one line," so the bound is practical, not theoretical.
- No transfer-friendly cost model. Even within a single line, edge cases like end-of-day service changes or rare express trains aren't separately modeled.
Lessons Learned
Matching algorithm to actual problem size matters more than choosing the most sophisticated algorithm. Brute force on 720 permutations gives provable optimality in milliseconds; a heuristic would have been more code, fewer guarantees, and no real speed benefit at this scale.
What worked. Writing out the time-dependent cost function explicitly before picking an algorithm. The TD-TSP framing made it obvious that ordering mattered (cost depends on arrival time, not just adjacency), and once that was clear, the brute-force decision was easy to justify.
What didn't. I initially modeled the timetable as an unsorted list of trains. For 720 permutations × multiple stop transitions, the cost of unsorted lookup added up. Switching to a sorted-by-time representation with binary-search lookup was a small refactor that made the search noticeably snappier.
What I'd do differently. Build a small comparison view from day one showing "your route under naive ordering" vs. "optimized order" with the time difference. That's what makes the Wait-Time Paradox visible to users; without it, the tool just shows an answer without showing why the answer is non-obvious.