Fastest route to get between numerous locations

RastaManBob

RastaManBob

RastaManBob

Associate
Joined
30 Dec 2003
Posts
2,254
Hello!

I have been asked to help work out the fastest route between a number of locations, all within the M25. I'd like to find the fastest route to get between all locations, using public transport and/or walking.

I think there are probably around 15 locations at the last count and so working every possible combination out is out not a sensible option. Even considering areas that are geographically close by does not really help as sometimes it can be faster (let's say) to go further to a different location on the same tube line for example.

I'm sure this must be the sort of thing others have tried to work out before - Does anybody know of any good websites that might be able to help calculate this given the post codes, for example?

Thank you! :)
 
Google matrix does this, not sure if it's still publicly accessible but if not the API is so you could make something...
 
This is quite a famous Decision Maths problem called "The Travelling Salesman" problem.

Googling around for that key word may help you more.
 
Still struggling to find something that will do exactly what I want... MapQuest seems the best so far (very easy to use and supports multiple locations) however it does not seem to be able to use public transport. I suppose driving is a possibility but I'd rather avoid this (especially if the only reason I'd be doing so is because of the journey planner!).

Then again, given the difficulties of the travelling salesman problem (thanks again for the links) I can understand why there might not be any websites that do this!
 
Indeed, no known polynomial time solution to TSP exists (if I'm not mistaken proving that such a solution exists would essentially be proving that P = NP) so it will be incredibly slow for a big problem with lots of nodes and edges.
 
well as you're mixing up tube. walking etc.. you're not strictly trying to solve for just distance and so those road related apps/websites won't be of much use, this traveling salesman solver might help though as you can input the 'price'(time) between each location in a matrix:

http://tspsg.info/

then again are you just looking for a quick answer or do you need to formulate a solution yourself?

If so start reading up on graph theory, optimization etc..
 
dowie said:
well as you're mixing up tube. walking etc.. you're not strictly trying to solve for just distance and so those road related apps/websites won't be of much use, this traveling salesman solver might help though as you can input the 'price'(time) between each location in a matrix:

http://tspsg.info/

then again are you just looking for a quick answer or do you need to formulate a solution yourself?

If so start reading up on graph theory, optimization etc..
Click to expand...

Just a quick answer :) This is not for studies etc but just to help try and work out how to keep around as many places of interest in a day as possible! Thanks :).
 
PhysicsMan94 said:
Indeed, no known polynomial time solution to TSP exists (if I'm not mistaken proving that such a solution exists would essentially be proving that P = NP) so it will be incredibly slow for a big problem with lots of nodes and edges.
Click to expand...

The problem grows Factorially.

But as I said above, for any given degree of approximation to the optimal solution you can design a polynomial time algorithm. The state of the art does quite well for problem sizes encountered in everyday routing tasks.
 
You must log in or register to reply here.
Back
Top Bottom