The Subway Challenge
I do not understand why some people get so excited about either trains or mathematics, but when these two forces collide, as so often happens, the normal, everyday world recedes to be replaced by your typical Terry Gilliam dream sequence:
“How to Plan the Most Efficient Route?” (Ask MetaFilter, March 9th)
Jason: What I’m trying to do may be pratically [sic] impossible, but I lost a bet and now have to attempt to ride the entire 656 miles of the New York subway in a day, passing through every one of the ~468 stations at least once. I live in Brooklyn and I know the subway pretty well (it’s not like I ride the JMZ all that often), but the sheer size of the system makes planning tough.
Sure, okay. Tough to plan; sheer size of the system. Metaphysics be damned. He’s doing it, so the only question is how. Now, it seems that most participants in the discussion fall into one of two camps:
The theory-heads:
Leon: NP complete doesn’t mean impossible, it just means it (probably) can’t be solved in polynomial time. Finding a near-optimal route through a mass transit system (the London Underground only has 275 stations) should only take a few minutes on a modern PC.
What you have here isn’t exactly the classical Travelling Salesman Problem, as you have to visit some nodes more than once. and you probably have asymmetric edge costs. I’d bet that you could solve this in Mathematica, or find some commercial route-planning software.
(which point I’m glad Leon brought up, because if he didn’t I was going to), and the hard-core-(in the context of riding the whole New York subway in a day)-pragmatists:
Jellicle: I don’t think you need theory here—you need experience. A friend who rides the subway and can tell you how to go and where to switch trains. Also—can you leave the subway system, travel to another stop, and reenter? I think little bits of knowledge that a local subway rider will have will decrease the total time taken by more than any theoretical analysis will.
My advice, without knowing which system you intend to do: most subway systems look like a spider. You will spend a lot of time riding out to the end of each arm and back into the middle. Look for places where you can ride out on arm A, take a cab, and ride back in on arm B.
proving that it takes a “think local” attitude to assess the nitty gritty facts of a given situation. I’m following all of this, not meaning to take sides, when suddenly a voice of skepticism emerges in the debate and I realise that’s what I am (skeptical):
Mendel: Ok, I’ll bite. The average speed of New York subways is apparently under 20 mph; how do you cover 656 miles of anything, regardless of route, at 20 mph in a day?
Not quite the degree of skepticism—I’m suddenly realising—that I have been longing for, but at least on the right track, so to speak. But nobody else is giving ground on the core idea. It’s when Gene speaks his piece that I realise, yet again, just how naive I am about the Things People Do. Jason’s problem, it turns out, is not new:
Gene: If I can chime in, don’t disregard using surface transit as connections unless it violates the rules of whatever you’re trying to do by riding the whole system.
Some friends attempted a similar challenge in Toronto, (much smaller system, though.) They used surface routs like buses/streetcars/LRT’s to connect the extreme points of the subways. Although the arrangement of the NYC subway might make that harder, it’s something to factor into any calculations you make.
I feel vaguely ashamed for, in fact, completely disregarding the New York surface transit system side of the equation, even though I’m only following along with the discussion after the fact. Nevertheless, surface transit had not occurred to us Dude. More to the point though, is probably what emerges as this story’s primary take-home message: first seek out the wisdom of others who have ridden entire subway systems in a day across the globe. And while I’m sure we could all learn a thing or two from the Canadians, the British, as it turns out, have organised a competition to take care of this problem:
Boudicca: You might want to look at Geoff Marshall’s Tube Challenge site. He’s made 8 attempts at visiting all the stations on the London Underground which are well documented on his site and you might find some ideas which transfer to New York. Geoff is the current World Record Holder for visiting all the London Underground stations in the fastest time.
Geoff’s site seems to be down, but a few more Google clicks and I’m confronted with the official web site of the London Tube Challenge. Inside, the History of the Tube Challenge section provides more evidence than I will ever need. This is when it happens, the moment I clap my eyes on the smiling visage of 1965 challenger Bill Hayles. The death of skepticism. People have been doing this in an organised manner for over 40 years.
There’s nothing left to do then but ponder, with dull amazement, the sheer number of things I don’t know. To me that number is simply x, which I doubt can be solved in polynomial time, but then who am I to be so skeptical?