With thousands of roads and millions of possible routes, how do driving direction services calculate the best path between two points in mere fractions of a second?
A lot of software engineers, myself included, work on exactly that problem their whole careers.
The fundamental problem was solved in 1959 by Edsger Dijkstra.
However, his algorithm is too slow for real world applications. A better algorithm, commonly known as the “A-star” algorithm, was developed in 1968.
But even that is too slow. Since that time, many computer scientists and others have developed their own versions of their algorithms, which often must be combined with special information built into the data. It is an extremely complex field; there are probably hundreds of patents just covering this one topic. It is also very competitive: Among car navigation systems, an algorithm that produces good paths (the most important factor) very fast is highly prized.
For a good starting point, look at the Wikipedia list under Routing Algorithms.
Thank you. I tried reading the Wikipedia articles, but they didn’t make a whole lot of sense. Wanna give a shot at dumbing the gist of it down to layman’s terms?
For what it’s worth, Google keeps improving their algorithms. I’ve been driving Camden, AR to Tulsa, OK once every two months or so for the past two years.
At first, the only route it would return would be through Little Rock. About a year ago it started returning through Little Rock and through the Ozarks up Highway 71. Then it added a path directly west into Oklahoma then directly north pretty much making two legs of a right triangle.
Just now in the past couple months it’s started defaulting to the Hwy 71 route, offering a route which goes through more the Oklahoma side than Arkansas, and the Little Rock route is listed third.
This is about consistent with reality: the first two sides are roughly the same travel time, the Little Rock path is about 15-30 minutes longer.
suranyi if you work for Google maps, thanks. I’ve used your product to plan just about any trip, and have sunk many hours into it daydreaming about possible road trips.
Sometimes they don’t, of course. I was once advised by Mapquest to get from Queens to Westchester by traveling to Iowa and back again.
The Wiki articles on this are not easy to read. Basically, Google maps has a representation of the road network. It knows the length of each road, has a figure for average speed down it, and knows where the roads intersect. To find a route between two points, it needs to search a lot of possibilities to find the quickest one. The simplest search algorithm looks something like this:
- Find the road for the starting point (e.g. A10).
- For every intersection on the starting road, generate a partial route and add to a working list (e.g. A10->A444, A10->M25).
- If any of the route end at the destination, remove from working set and add to a list of possible routes.
- Remove any routes that contain loops (go through the same road more than once).
- Generate a new set of partial routes from the working set by finding any intesections on the last road in each route (e.g. A10->A414->M11, A10->M25->M11).
- Repeat steps 3-5 until you run out of roads.
- From the list of routes that reach the generation choose the shortest or quickest one.
It’s pretty trivial to do this kind of search with a computer, but the problem is doing so efficiently. The algorithm above would work fine with a very small road network, but with a real one it might generate millions of possible routes. Most of these would be pointless, taking you from one end of the country and back again. Enhanced versions of this search algorithm use a heuristic (estimate) to prune unpromising routes from the search tree, greatly reducing the number of possibilities the computer needs to check, and vastly improving search speed.
When traffic is bad on the Major Deegan that’s often the shortest way.
What sort of heuristics are used? As a layperson I can think of a couple off the top of my head (ignore all side roads pointing away from the destination, ignore side roads once you’re on arteries, ignore most everything once you’re on expressways (unless expressways are too circuitous). What do these sorts of programs actually do? Granted, I suppose every algorithm will have some unique tricks, but I’d guess that there are some standard shortcuts which are commonly used.
Yes, for North America, part of the database ought to be a model of the interconnections on the interstate system, so you know the fastest routes between every important intersection there.
For example, you’d want to know the fastest route between a point on I-90 in SE Chicago, and each major intersection on I-95 between Elizabeth NJ and Fort Lee NJ, because one of those routes will be on the fastest route between almost any point in Chicago (and places north, like Wisconsin), and New York City.
Once you have that, then you just need to get from the starting point and the destination to the interstate system, if they are far enough apart. You wouldn’t want to check every back road in Indiana, Ohio and Pennsylvania – you know that a journey from Illinois to New York City will spend all its time on interstates (or possibly a few major roads filling gaps) in those intermediate states.
uncheck ‘take the scenic route’ option.
This problem was assigned as homework in one of my computer science classes in the 1970s, albeit in a simpler form. A related one is the delivery driver problem: Given deliveries at these six addresses, what’s the best order to do them?
The heuristics vary from computer to computer or device to device. My GPS will often try to route me through fields, ditch access roads, private drives, and virtually impassible dirt roads when driving in rural Montana and Wyoming. Google maps sometimes does the same, but it’s much better, largely (I think) because it has so much more computing power, and probably a deeper database to start with.
It’s an estimate of how long it will take to travel down a section of road (distance/average speed for that road).
One way teh search can be made more efficient is by discarding more expensive routes. Once the routing algorithm has found one route to the destination it can safely ignore any incomplete routes that take more time.
I don’t know exactly how the routing in Google maps works, but I suspect they do something to split up the road network. Something like this would work fairly well:
- Use the search I described in my last post to find a route from the starting point to the closest major road.
- Use the same search to find a route from the destination to the closest major road.
- Do another search to find a route between the two major roads, ignoring any side roads along the route.
Once one route has been found, a more comprehensive search could be performed.
I don’t work for Google Maps, but I work in the mapping and navigation industry. I’d rather not say what company I work for. But I have close ties to many of the major players.
One thing I can say is that it is true that people working in this field ARE constantly trying to improve their algorithms. The hard part of any routing algorithm is for it to be both good and fast. The original one by Dijkstra was good, but very slow.
Actually, the really big thing going on now is real-time routing. That is, to give the best route given the current traffic situation. Several car navigation systems now have this capability. Google maps does not (yet) although it can display current traffic.
There are lots of types of heuristics, and typically they are among the most complicated parts of the algorithm. In general you’re right, but it’s not as simple as just ignoring side roads once you’re on arteries. It’s more like: ignore side roads once you’re on ENOUGH arteries. Or at least that’s one way to do it.
As an algorithms person, it’s a great field because it’s constantly evolving, yet it has down-to-earth, real world applications. New ideas are invented all the time. Someone who used to work with us had a great idea just a few years ago for a new routing algorithm he called “Reach-Based Routing” (waring – PDF). I’m not aware of any company using this algorithm, but it sure looks interesting.
Isn’t that the same as the traveling salesman problem? Assuming, of course, that you already know the distance between any pair of addresses.
And six addresses seems like a poor test… That’s small enough that you can still easily brute-force it, which means you’re not teaching any of the non-brute-force methods that become necessary for larger sets.
And of course they have different goals then you, you want to get their fast, they wanna save gas, UPS doesn’t do left turns because of the waiting and idleing, this saves them hundreds of thousands of dollars in gas a year
Right, that’s the traveling salesman problem, which is related, but not the same. In order to solve the traveling salesman problem, you already need to know how to find the best path between a given pair of points.
I recently took a trip from Little Rock through Memphis and down into Mississippi. I filled up and reset my cars trip meter. I was very, very impressed that Mapquest nailed my driving distance to within 1/2 mile.
I’m even more impressed that it got my driving time within 15 minutes. I don’t know how it figured the time within Memphis. There’s traffic lights and several speed limit changes. Somehow Mapquest does it. For Free 
And… data data data. The best routing system won’t do squat without good information. It can’t.
Absolutely. I work with people on that side as well.