How to plan the most efficient route?

March 9, 2006 6:59 AM

I'm planning to visit every stop on a major metropolitan subway system in a single day (long story), and need to plan the most efficient route. Anyone know of useful technology/mathematical theories that help with route planning?
posted by jasonsmall to Travel & Transportation (16 answers total)

Google "Travelling salesman problem".
posted by orthogonality at 7:15 AM on March 9, 2006

This is um, not possible. It's NP-complete. That's actually true only if there are a lot of nodes though. It's probably doable in Los Angeles for example. Or Atlanta (few nodes / stations, and also simple paths between).
posted by zpousman at 7:34 AM on March 9, 2006

This is a pretty hard problem. Computational complexity theorists would call it NP-hard (err ... NP-complete). Wikipedia gives some good background.

As you'll find on the Wikipedia page, it's common to use a weighted graph to conceptualize the problem. Each station would be a vertex, connected by edges that represent subway routes, which edges are assigned costs based on the resources (time, money, total distance traveled, etc.) you'd like to conserve.

Aside from the difficulty in solving the general case, you have some specific limitations to overcome. Calculating the "cost" for any particular segment of the route seems difficult. Unless you know what the typical travel times are on each route, how long typical delays are at various stations, the prices of fares and transfers, etc., you probably don't have enough information to come up with a reasonable heuristic, let alone solve the problem.
posted by santry at 7:47 AM on March 9, 2006

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. I don't have any recommendations, though.
posted by Leon at 8:06 AM on March 9, 2006

More background and info: Dijkstra's algorithm.
posted by cadastral at 8:08 AM on March 9, 2006

I know SFA about the math involved, but I think I speak for a lot of people when I say... tell us the long story! You can't just say you're going to do something odd and not tell us why :P
posted by dirtynumbangelboy at 8:28 AM on March 9, 2006

[Assuming a subway system] It occurs to me that you can prune the problem down to only the stations that allow connections, by making the cost between each station the sum of the costs of the "inbetween" stations. That makes the problem a lot smaller (it might cut the number of nodes in half?)
posted by Leon at 9:24 AM on March 9, 2006

I think to do any optimal planning, you'd need to know all about the timing of the trains and stuff. I don't think it's practical. Besides in these sorts of situations the naive solution is usually not too much worse than the optimal one.

Posting flyers?
posted by joegester at 9:48 AM on March 9, 2006

Dijkstra's algorithm isn't quite applicable here — it would only be useful if you were going from one point to another and needed the quickest route. The classical "traveling salesman" problem isn't quite applicable here, either, since it assumes that you visit each vertex only once (in fancy jargon, it tries to find the most efficient Hamiltonian circuit.)

Can you freely choose your starting and ending locations, or is there a constraint on them?
posted by Johnny Assay at 10:21 AM on March 9, 2006

Uh, is this part of a Geocaching puzzle?

(We have some of those out here.. they involve blowing 2 days on local transit systems)
posted by drstein at 10:24 AM on March 9, 2006

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.
posted by jellicle at 11:19 AM on March 9, 2006

Response by poster: What I'm trying to do may be pratically 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.

Obviously, I'll have to pass through a number of stations more than once, and there is clearly no perfect solution, but I'd like to make up a route more efficient that what I'd come up with just using a large map and markers on my own. Given the complexity of the system, coming up with exact travel times for each leg is an impossibility, but I want to work up a rough estimate -- if only to see if the idea is feasible

jellicle, the cab idea is great, though I have to check if this violates the spirit of the bet.
posted by jasonsmall at 12:16 PM on March 9, 2006

656 miles of the New York subway in a day

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?
posted by mendel at 1:05 PM on March 9, 2006

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.
posted by generichuman at 2:57 PM on March 9, 2006

NYC subway in a day? Hmm. I think the total mileage is 230, because if there are five sets of track going through a station, you only have to go through it once. (I'm assuming that one pass through a station is fully-sufficient for your wager.) It should be theoretically possible, though you're talking a really long day. I'd be surprised if you could do it in much under 24 hours.

Getting the edges is going to be lots harder than getting the middle. The Bronx will take, say, 4 hours, maybe less if you can cab or bus between arms. Manhattan will take about 4-5 hours. Do Queens, end up at Jamaica Center, down into Brooklyn and start working your way through the arms of the A, S, L, 3.... Brooklyn is easily going to take ten hours or more. You might be able to cut that down by hopping between lines at the end of the various Coney Island arms. Add 6 hours or more for friction - waiting in stations, back-tracking to get odd stations. Wear comfortable shoes.

If you do this, be sure to bring a camera and extra memory card and lots of extra batteries, and put up a webpage with Google ads. Battery-powered clock, take a picture of every station name through the train window with the clock in the shot? Might be hard.
posted by jellicle at 6:25 PM on March 9, 2006

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.
posted by boudicca at 2:09 AM on March 10, 2006