I grabbed the list of payphones from Payphone Go's API, then deduped listings and plumbed them all into Valhalla, a routing engine, to get an all-to-all distance matrix in terms of driving time from payphone A to payphone B. Since one-way streets, traffic signals, etc can cause asymmetry in driving time one way vs the other, and standard traveling salesman problem (TSP) solvers like 2-opt generally operate on symmetric cost matrices, Claude suggested using the JV transform to convert the asymmetric NxN matrix into a symmetric (2N, 2N) one with ghost nodes, so standard 2-opt Just Works.

The TSP solver is standard 2-opt, implemented as a Rust crate compiled to WASM so it's blazing fast. It's not optimal but very close to optimal, and doesn't take an eternity like the constraint satisfaction based solvers do.

Now, once we have our route, we want to show the actual street route to be taken from point to point. Instead of dynamically fetching route segments from Valhalla, which has unpredictable latency esp. if the server is under load (e.g. when my roommate is playing League on it), we literally precompute the turn-by-turn routes for every single pair of payphones, one way and the other way. It comes out to around 17GB of gzipped blobs in a sqlite db, which is honestly a decent compute-storage tradeoff.

And yeah, that's about it! I might add some more features later but this was a fun project with my claud.