# Route Planners

Ranch Hand
Posts: 154
So how do these route planner thingies work then?
Amazing how they find a route from Lands End to John 0' Groats in just a few seconds.
I quite fancy writing one, does anyone have any links to the algorithms used or are they truly magic?

HS Thomas
Ranch Hand
Posts: 3404
I guess GPS systems work best.
Enter destination and point of departure. The route planner gets fed traffic details between the two points and works the best route for you.
It constantly updates the time it will take. And sometimes overiding the instructions and taking a different detour turns out to be quicker for some insane reason.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
I don't know what exact algorithms are used, but if I were designing a system from scratch I'd try to make use of tables of precalculated "best routs" between major cities or junctions. So that for example if I want to get from Long Beach, California (Los Angeles area) to Harvard Square (Boston area), first look up Los Angeles to Boston and get a quick list of the major rods to take in the precalculated best route. Then for each endpoint, do a more detailed (and thus time-intensive) search for how to best connect (from where you actually are) to that "best route". Actually the same algorithm can be applied at other scales - major metropolitan areas like LA and Boston are complex enough that they probably deserve their own tables of best routes, for internal travel within those areas. So after you've found that the best route out of LS is on I-15 North, look up the best route from Long Beach to I-15 North in the Los Angeles table. Once you've got that route, do a more careful search for the best route from whatever street address you're on in Long Beach to some point on the route to I-15.
In practice it will sometimes happen that the best route from A to M is not so good for B (near A) to N (near M). If there's more than one way from A to M which is close in total length, then when you look up A to M in your table you might want to return precalculated results for several major alternatives. Then when you look at how to connect from B, which alternative are you really closest to? And connecting from N, same question. This may be a bit complex, but my point is that you should still be able to make use of precalculated results to avoid having to do a tree search of all the nodes in your map, which would doubtless be hugely expensive to compute.

Ranch Hand
Posts: 154
Thanks for your time and replies chaps.
I'm off to start designing!
Think I'll try a tube/subway/metro program first that might be a bit easier to start with

David Weitzman
Ranch Hand
Posts: 1365
My guess is that route planners do a sort of breadth first search with some careful evaluation to choose what order paths should be examined in (favor big roads, roads that actually move towards the destination, perhaps avoid toll roads, etc).
I see an unexpected similarity to something I was working on recently: game intellegence. A chess engine which aims to find mate eventually can't actually look at all possible moves infinately deep. It can, however, evaluate a given board position to determine if it's favorable and try to maintain the board in a favorable state. Any modern chess engine will do "pruning" -- ignoring paths that can't possibly be as good as one that's already been found. I have a feeling that the same sort of ideas that go into chess engines could be applied to route finding as well. The main difference is that in chess you don't (and can't) always calculate to the end of the game. I think if you can find at least one semi-decent path to the destination using heuristics, you can improve upon it with a more exhaustive search that prunes obviously poor choices.

Arjun Shastry
Ranch Hand
Posts: 1901
1
One might want to look at This.Developed by students.

HS Thomas
Ranch Hand
Posts: 3404
You have route planners built into your mobile phones too.(forget what they are called)
Finding the nearest cinema for example. So you can plan a drive and stop-overs , or plan a holiday outright ?

Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
I think some of the maze algorithms in this forum a few months ago apply. Google for route algorithms and if Knuth comes up, give it a try.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
You have route planners built into your mobile phones too.
I expect in most cases, the algorithms are built into a server somewhere; the mobile phone just connects to that. I actually have no data to back that up; just seems like a good design choice.

Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
Ah, I remembered the name of a classic variation. Google on "traveling salesman algorithm". The problem is usually to visit all of the salesman's clients with the least driving. The point-to-point problem is different becase it doesn't have to visit all points known to it.

HS Thomas
Ranch Hand
Posts: 3404
Originally posted by Jim Yingst:
You have route planners built into your mobile phones too.
I expect in most cases, the algorithms are built into a server somewhere; the mobile phone just connects to that. I actually have no data to back that up; just seems like a good design choice.

Suppose someone wanted to track moose-sightings - things of the transient variety.Does a server need to be in place. I'll have to find that article again on route maps and mobile phones. You could be right, though,
in the name of keeping statistics of some sort.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Suppose someone wanted to track moose-sightings - things of the transient variety.Does a server need to be in place.
I'd think so - that is, it would still be a preferred solution. If we're dealing with transient data, that might reduce the usefulness of precalculated results such as I described previously. But you still need (a) a lot of data about where things are, and (b) the computational power to churn through it and find the best solution. I'd think it would be much easier to put this on a server rather than require all the cell phones to carry around that much RAM and computing power. And where does this transient data come from? The cell phone doesn't have sensors to detect moose locations (or whatever) directly; there must be a server somewhere which is collecting data from [wherever the data comes from] and makes it available to the cell phone. Which means the phone would need to keep querying for updates of the transient data, consuming bandwith. Seems much easier to give the cell phone just enough intelligence to specify start and endpoints, and let the server to most of the work in figuring out how to connect.

HS Thomas
Ranch Hand
Posts: 3404
JY : The cell phone doesn't have sensors to detect moose locations (or whatever) directly; there must be a server somewhere which is collecting data from [wherever the data comes from] and makes it available to the cell phone.
Man with mobile phone with camera would be sensor enough, IMHO. But to be useful to anyone else the phone could send the location to other mobile parties directly and perhaps download the location and image to a server.
And why can't the other phones serve that data to others that don't know anything about the server. Like telephone calls get deleted after a while that transient data get's automatically deleted. Besides current servers are notorious for crashing. The use of transient data may be severley limited in certain cases.
I am rambling .... I am not sure what third generation (3G) mobile networks are really meant for.I guess if doing a lot of route planning you may want the tech on your phone.
I've read of a case where staff at a hospital have mobile phones that detect each other in passing. In case of a breakout its easy to work out who was in contact with whom. That information would be downloaded along with other work overnight. Transient but not critically so.
[ December 19, 2003: Message edited by: HS Thomas ]
[ December 19, 2003: Message edited by: HS Thomas ]

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Ok, if the [transient] data you're talking about is from other cell phones, it may be more efficient to exchange the data directly rather than through a server. Whereas data from other sources, or data that requires a lot of processing, is probably better put on a server. Especially if others can benefit from that processing.

Mark Herschberg
Sheriff
Posts: 6037
This is basic graph theory: shortest path algorithm. The traveling salesman problem is a variation on this problem, in which you must visit each node exactly once and return to the initial node, at minimal cost (measured by traveled edge weight).
Dijkstra's Algorithm solves this in the general case. More specialized algorithms have also been developed over the years.
--Mark

Jim Yingst
Wanderer
Sheriff
Posts: 18671
This is basic graph theory: shortest path algorithm.
True; I should have mentioned that previously. I was thinking more about how to implement this efficiently in cases where the graph is reused a lot for many different endpoints; hence the interest in precalculating results. Something like Dijkstra's algorithm would be good for finding those precalculated best routes in the first place - and also maybe for connecting each endpoint to one of those best routes, for a specific route query.
I should also note that it's not necessarily a requirement that the system find the absolute shortest route in all cases. If the system occasionally overlooks obscure side roads, but still finds a route that is pretty close to the best possible route, then users probably won't notice in most cases. While if the system is slow, users will notice that - regardless of how accurate the results are. So I can imagine some systems may use algorithms that don't necessarily guarantee the most accurate results, but do deliver good response times.

Mark Herschberg
Sheriff
Posts: 6037
Originally posted by Jim Yingst:
This is basic graph theory: shortest path algorithm.
True; I should have mentioned that previously. I was thinking more about how to implement this efficiently in cases where the graph is reused a lot for many different endpoints; hence the interest in precalculating results.

I wasn't trying to disagree with Jim. For those not familiar with this area of computer science, algorithms are generally optimized for minimal calculations (think big O notation). These are theoretical operations. Practically speaking, many problems in complexity theory have variations which are more practical (dealing with issues like using, but minimizing, memory).
I'm sure many of you are familiar with Akamai (the basis of the company is Danny Lewin's research). Their algorithms basically quickly route an HTTP request to one of many servers, based on a combination of closeness and server load.
--Mark

David Weitzman
Ranch Hand
Posts: 1365
Certainly you can't just run unmodified Dijkstra on the entire map of, say, the United States. Being an all-points-shortest-path algorithm and a dynamic programming algorithm it might take an obscene amount of time. Even if it doesn't, it will certainly take an unnecessary amount of time and memory -- probably enough to be impractical on less powerful computers. Until you've found the destination by at least one path and you can prune obviously dumb solutions, you would need to examine all of the paths that lead anywhere N miles away before you could find a solution to paths N + 1 miles away. That means that finding the shortest path from Maine to California would involve finding all the shortest paths from Maine to Florida. Finding the shortest path to a place that you can't actually get to would requiring finding the shortest path to every intersection in America. The time wasted doing this, particularly for large paths across a country, is unnecessary and should be quite large. It would also be impratical to implement optimizaiton across multiple variable (road type, path length in time, path length in miles, avoid construction, etc). Route finding just doesn't seem as simple as finding a shortest path. We need to take advantage of the fact that maps are planer graphs.
Dijkstra may be a useful subroutine used on reasonable portions of a map, but you can't just run it on the whole map.
[ December 21, 2003: Message edited by: David Weitzman ]

Tony Collins
Ranch Hand
Posts: 435
This is very interesting to me,as I went for an Interview this week where the company wanted to develop a piece of software which could calculate the cheapest leased line between two points in Britain.
Going directly to hubs is often not the cheapest route, so the named algorithm may be useful. But how do you prune the thing, tough question.