So back in my college days, I took a few computer science courses, and I remember learning about best-path networking and routing, and it seemed interesting to a point, but never fascinating. Then along comes Mapquest, and WOW! Every time I use it (well, maybe not every time), I wonder two things:
Who programmed/populated the database? Did someone hire a bunch of cartographers to go out and measure exit ramp distances and check side street speed limits? Was this a high-paying job? Did they only hire OCD types?
How does it do it so fast? There are a LOT of roads in the U.S. I imagine the highway system helps a lot to minimize side-street distractions, but still…it took less than five seconds to map the trip from Santa Cruz to my hometown of Skaneateles, NY.
It must have been very fun to be the first person/programmer to see Mapquest in action.
IAAProgrammer, and while I don’t know exactly how they do it, it’s not that hard to represent the network on which the critical paths are based.
Think about the basic principle, which is to say "You can get from Point A to Point B by traversing these intermediate points. How would you do that? You could represent a road in a database table as the set of locations the the road traverses. A second table could link each location to its successor, with each record comprising one location and the next location up the road. During the initial load, as the program goes through the successors, it’s clear that for each successor, the predecessor is the location that you just linked it to. So when you go through them all you’ve got all the points of the road connected in both directions.
Do all the roads, then if two points on different roads share a successor, the roads meet there.
To the best of my knowledge there are only one or two different companies that produce the databases, they are usually taken directly from the US TIGER system. Or were originally, I’m sure that by now they have had people tell them when there are mistakes. The distances are done by taking each segment of the line and giving it a distance, not very hard since the computer does the math. Speed limits are given an average speed, so highways are generally given one speed, probably 60-65, US highways are given another and side streets another. You don’t need to give every street a speedlimit, just a good guess.
I can assure you, since I worked in the field, though not doing exactly those maps, it is not a high paying job.
I’m making a WAG here, but I think that it looks at the places you will go first, then throws out all the places you will not go. So going from Santa Cruz to NY, if you’re not going to Arizona then it has no need to look there and try and find those distances. I would say it probably finds highways first. I can only go on my own usage of older programs though. I know there are a couple of the first programs that would take hours to do a route, even on the faster computers.
You can if you really wanted to, and had a ton of money to spend, get the entire roadway system of the US which also includes county lines, city lines and anything else you could ever want for $15-20,000. The ones I used came on 10 CDs though that could be more now.
I vaguely recall reading an article about the people who update the map data. I think it was just a couple of people in a car, and they have a laptop with GPS with them. Every time they come to an exit, they hit a button to record the location and type in the exit name. Same deal for other features. So they do generate some of their own data.
I’ll see if I can dig it up. Maybe it was in Wired?
My guess is that they have the most likely routes already built – those that involve inrterstates, and other major roads. Then it says something like, for a trip from City A to City B, you use Interstates X and Y. That reduces the problem to getting onto Interstate X in City A, and off Interstate Y in City B. (A specific example would be Chicago to New York City: it would know that the best way between those metro areas is Interstate 80, and it would just need to get you on and off I-80.)
If you think Mapquest is fast, you shoyld try a local app, like Microsoft’s Streets and Trips. It always blows me away how it can calculate the distance from my place in Charlotte, NC to say… the Space Needle in Seattle in like .2 seconds!
When I took an AI class in 1971, directions were one of the possible future applications, so I’m especially impressed that this is so available now.
Judging from getting local directions, I think you are right. There is a bias towards interstates, even when local roads are likely to be better. I suspect the big roads get a higher priority in moving from close to the source to close to the destination, and then the algorithm recursively looks for slightly smaller roads to get there.
I just did some trip planning on the Rand McNally website (which appears to use much the same technology), and while I can’t be certain because the image link was broken, it appears that the site was trying to display an actual picture of the highway exit sign for a particular junction. If so, that’s an interesting little bit of bonus content, specific to that site.
I think the real priority of routes is forcing the driver through business districts.
I realize I am creating a zombie thread, sorry about that
I have recently been completely bewildered by some of the routes that Google’s website, and Mapquest, and Streets And Trips generate.
I have a regular destination from North Indianapolis to South Indianapolis; Mapquest insists I take a route on Mass Avenue, a small business district that has poorly signed “five corners” intersections. If I “Avoid” Mass Avenue, then the entire route is scrapped and I am directed to interstate highways. My desired route is not College, then Mass Ave, but Central, which is 2-3 blocks west, and Mapquest refuses to generate it.
Streets And Trips “kinda” generates the route, but sends me through Monument Circle (think the town square of Mayberry N.C.) and fails to properly indicate street names.
If you think I have some perverse idea of routes, my route usually has a dozen cars within my vision, either behind me or in front of me.
Google’s website is atrocious, even with Chrome. You can’t use your scroll wheel without blowing up the map, you can’t zoom without losing the center of the map, perhaps others like it, but it’s horrible for me.
I am giving up and buying a GPS.
Regarding the latest version of Mapquest, where you can drag the route to your favorite streets, that only works until you need to zoom/scroll, then it seems to reset itself to its idea of the correct route.
If you expect a dedicated GPS to give you fewer strange routes than the online mapping services do, I think you’re in for a surprise. I have two cars with built-in GPS, as well as two standalone Garmin units of different vintages. And I’ve used Hertz’s Magellan-based system a ton of times. All of them occasionally send me some weird way.
I’m not sure if you were joking, but what incentive would Google have to route you through a business district? It’s not like they get a cut of the revenue from that. They have a much larger incentive to give you the best routing possible, because otherwise you’re likely to stop using the service, which definitely would cost them money.
The Navigate app on my Android phone is obsessed with freeways. I’ve had it try to give me routes that took me miles off the most direct course to my destination to put me on a freeway.
From a mathematical point of view - route-finding is an application of graph theory. Road networks consist of nodes and segments (some segments are directed, such as one way roads), and segments (which include distance and direction) can have additional weighting (including possible multiple weightings based on time of day, tolls etc). Shortest network path algorithms are then applied to find the best route.
Si
A* search is a variant on Breadth First search, which searches all possible paths from the start point until it reaches the goal. A* adds a heuristic (sort of like a rule-of-thumb) to prioritize which paths to look at first which can improve search times dramatically. The depth limited part is a way of stopping the algorithm tracing complex routes which string together hundreds of side streets.
You might be interested in Universal Navigation on Smartphones from Springer books (ISBN 978-1-4419-7741-0). It has a nice description of the database, accuracy routing, keeping to the “path” vs. actual GPS locations etc. Although it focuses on smartphones (sidewalk paths!) it includes road mapping as well.
NAVTEQ (now owned by Nokia) provides a lot of the data used in MapQuest, Bing, Yahoo!, Flickr, Amazon, Oracle and a few other products. (Google and Apple devised their own, but I do not know whether they re-created all their own data or originally bought it from an earlier database creator.)
Interestingly, the history section refers to a 1985 start-up. I was working at a trucking company in 1983, and they had already developed a system that could tell drivers best routes, speeds, distances, and fuel locations for over-the-road hauling at that time. (It required a dial-in CICS connection to an IBM 4380 with a small printer for text directions, but the data was being plotted at that time.) It seems that a number of outfits were working toward the same goal in that era.
That’s me. I’ll answer briefly, although I know this is a zombie.
There are two different aspects to this question: Gathering the map data, and creating an algorithm for finding the best route.
There are now several companies involved in gathering map data for car navigation. The two oldest and best known were Navteq, now owned by Nokia, and Tele Atlas, now owned by Tom Tom. Those two provide the vast majority of commercial digital maps for navigation devices. There is also Google, which collects their own data, but I don’t think they sell it to any other services.
Collecting map data is very time and labor intensive, because a map that works for navigation needs a lot of detailed information. Especially for modern navigation systems. Things like street names, traffic signs, turn restrictions, lane connectivity, house numbers, etc. Typically these are collected in three different ways: Aerial or satellite imagery gets the basic geometry. Special vehicles on the ground equipped with mulitple cameras (such as the famous Google map cars) collect the signs, house numbers, and traffic restrictions. Then the most detailed information, yet the most problematic as well, comes from crowdsourcing. That’s how hundreds of businesses and other points of interest can get onto a map. The data is huge but it requires curating to be sure it is correct.
Once the data is there, then algorithms can be designed to take advantage of it. There have been shortest/best path algorithms described in the mathematical literature for decades. The first famous one was published back in the 1950s, I believe. Any computer science major can easily write a basic one. The problem is to create one that works well in the real world. The problem that shows up immediately is that the basic algorithms take far too long. So all modern routing algorithms use technques to decide when to drop certain roads from consideration. Too soon and you miss the best route. Too late and the algorithm is too slow.
