# How does Mapquest work? **URL:** \ **Category:** Factual Questions\ **Created:** [June 26, 2003, 8:55pm UTC](https://boards.straightdope.com/t/how-does-mapquest-work/184619 "2003-06-26T20:55:42Z")\ **Posts on this page:** 13\ **Page:** 1
**Author:** ![Mike\_B](https://avatars.discourse-cdn.com/v4/letter/m/977dab/32.png) [@Mike\_B](https://boards.straightdope.com/u/Mike_B)\ **Post date:** [June 26, 2003, 8:55pm UTC](https://boards.straightdope.com/t/how-does-mapquest-work/184619/1 "2003-06-26T20:55:42Z")
Does anyone know how Mapquest works? I do a lot of programming myself, and I can’t figure out for the life of me how they would code that. I understand they have a giant DB with roads, intersections, etc, but how do they actually figure which is the shortest route? ---
**Author:** ![Q.E.D](https://avatars.discourse-cdn.com/v4/letter/q/51bf81/32.png) [@Q.E.D](https://boards.straightdope.com/u/Q.E.D)\ **Post date:** [June 26, 2003, 8:59pm UTC](https://boards.straightdope.com/t/how-does-mapquest-work/184619/2 "2003-06-26T20:59:00Z")
My guess is that they use some sort of successive approximation algorithm, and apply the law of diminishing returns to get a route that, though it may not be _the_ shortest, is still pretty close. ---
**Author:** ![William\_Ashbless](https://avatars.discourse-cdn.com/v4/letter/w/a87d85/32.png) [@William\_Ashbless](https://boards.straightdope.com/u/William_Ashbless)\ **Post date:** [June 26, 2003, 10:09pm UTC](https://boards.straightdope.com/t/how-does-mapquest-work/184619/3 "2003-06-26T22:09:35Z")
Massive Dijkstra’s algorithm? Given that the map is two dimensional, and given you know the length of the road segments, I wouldn’t imagine a shortest-path graph algorithm faring too badly. ---
**Author:** ![Fang](https://avatars.discourse-cdn.com/v4/letter/f/96bed5/32.png) [@Fang](https://boards.straightdope.com/u/Fang)\ **Post date:** [June 26, 2003, 10:21pm UTC](https://boards.straightdope.com/t/how-does-mapquest-work/184619/4 "2003-06-26T22:21:02Z")
> [@](#): > > \*Originally posted by William\_Ashbless \* > \*\*Massive Dijkstra’s algorithm? > > Given that the map is two dimensional, and given you know the length of the road segments, I wouldn’t imagine a shortest-path graph algorithm faring too badly. \*\* That’s what I was thinking, but if you imagine the number of road segments in the US, it gets to be pretty damn big, and Mapquest usually returns results within a second or two. Perhaps they have some kind of localization feature added in to speed up the most common cases? ---
**Author:** ![William\_Ashbless](https://avatars.discourse-cdn.com/v4/letter/w/a87d85/32.png) [@William\_Ashbless](https://boards.straightdope.com/u/William_Ashbless)\ **Post date:** [June 26, 2003, 10:31pm UTC](https://boards.straightdope.com/t/how-does-mapquest-work/184619/5 "2003-06-26T22:31:15Z")
You might want to look up a technique called A\*, which can bias the search based on some measure of how close a choice gets you. It turns out that with a properly constructed ‘acceptable’ heuristic, you can still get an optimal solution. It just gets there faster. If you design a poor heuristic, you might get a suboptimal solution… but if you’re not far off from acceptable, you’ll get a nearly optimal one. Constrained to a 2d map, distance covered could be a good heuristic. It would bias the search very directly between the two points. But there are other ways to optimize it too, and maybe even weight the paths on other than drive distance to complicate matters. 🙂 ---
**Author:** ![enipla](https://avatars.discourse-cdn.com/v4/letter/e/54ee81/32.png) [@enipla](https://boards.straightdope.com/u/enipla)\ **Post date:** [June 26, 2003, 11:44pm UTC](https://boards.straightdope.com/t/how-does-mapquest-work/184619/6 "2003-06-26T23:44:27Z")
I’m a GIS programmer. Never set up any routing, but deal a lot with linear data. Most of my work is with polygons, which of course is made of lines. These lines have endpoints that can intersect with other lines. They also have vertices that do not intersect with other lines. All of these have X,Y coordinates. Also, the origination, and the to destination have X.Y coordinates. I don’t know how it’s done, but this is how I would take a shot at it. Buffer the straight line between the origination and destination. A buffer selection allows you to select all lines (roads/records) within a certain distance of the ‘crow flies’ line. For a thousand mile trip, buffer 250 miles, or whatever. This could be adjusted based on road density for an area. Or scenic route or speed or whatever. Every line or road segment is a record that carries all these attributes. At this point, you have eliminated 99% of the database. Now it’s pretty easy to make some calculations, and re-buffer if need be. It’s an excersise in diminishing returns. ---
**Author:** ![enipla](https://avatars.discourse-cdn.com/v4/letter/e/54ee81/32.png) [@enipla](https://boards.straightdope.com/u/enipla)\ **Post date:** [June 27, 2003, 12:33am UTC](https://boards.straightdope.com/t/how-does-mapquest-work/184619/7 "2003-06-27T00:33:57Z")
A database always need some item, some field, some link to be able to communicate with other information. Every ‘thing’ has a location. The lowest common denominator is where that item is. Where it is physically located. GIS can relate a fire plug to a house. And does. Nothing similar, other than where they are located. Fun stuff. Now if I can only get this chip out of my head…… ---
**Author:** ![amarone](https://avatars.discourse-cdn.com/v4/letter/a/e0b2c6/32.png) [@amarone](https://boards.straightdope.com/u/amarone)\ **Post date:** [June 27, 2003, 1:30am UTC](https://boards.straightdope.com/t/how-does-mapquest-work/184619/8 "2003-06-27T01:30:31Z")
> [@](#): > > \*Originally posted by enipla \* > \*\*Buffer the straight line between the origination and destination. A buffer selection allows you to select all lines (roads/records) within a certain distance of the ‘crow flies’ line. For a thousand mile trip, buffer 250 miles, or whatever. This could be adjusted based on road density for an area. Or scenic route or speed or whatever. Every line or road segment is a record that carries all these attributes. > > At this point, you have eliminated 99% of the database. > > Now it’s pretty easy to make some calculations, and re-buffer if need be. It’s an excersise in diminishing returns. \*\* That makes sense to me. I once used MapQuest to calculate the route to two different houses on the same street in a subdivision. There was only one road into the subdivision. However, it gave two completely different routes to the entrance to the subdivision. So the route calculation must have been using an algorithm including the geographical location of the destination rather than just adding up the bits of road to get there. ---
**Author:** ![enipla](https://avatars.discourse-cdn.com/v4/letter/e/54ee81/32.png) [@enipla](https://boards.straightdope.com/u/enipla)\ **Post date:** [June 27, 2003, 1:55am UTC](https://boards.straightdope.com/t/how-does-mapquest-work/184619/9 "2003-06-27T01:55:24Z")
> [@](#): > > That makes sense to me. Thank you, thank you, thank you. It’s just data, with a little geography on the side. North is up, right? 😃 ---
**Author:** ![kniz](https://avatars.discourse-cdn.com/v4/letter/k/c37758/32.png) [@kniz](https://boards.straightdope.com/u/kniz)\ **Post date:** [June 27, 2003, 2:40am UTC](https://boards.straightdope.com/t/how-does-mapquest-work/184619/10 "2003-06-27T02:40:04Z")
Hamsters, it is all done with hamsters running around until they all congregate on a given point. Driving instructions are done the same way only with two teams of hamsters. One team starts at the start position and the other team starts at the destination. They run around until they hook up. Absolutely amazing, don’t you think? 😉 ---
**Author:** ![dwc1970](https://avatars.discourse-cdn.com/v4/letter/d/a183cd/32.png) [@dwc1970](https://boards.straightdope.com/u/dwc1970)\ **Post date:** [June 27, 2003, 3:15am UTC](https://boards.straightdope.com/t/how-does-mapquest-work/184619/11 "2003-06-27T03:15:38Z")
Straight from Mapquest’s [About Mapquest](http://www.mapquest.com/about/main.adp) page: > [@](#): > > How MapQuest Got Started > R.R. Donnelley &Sons founded the Company in Lancaster, Pennsylvania, in the 1960s as a cartographic services division that was responsible for creating road maps given to gas station customers for free. By the 1970s, MapQuest became a leading supplier of custom maps to reference, travel, textbook, and directory publishers. In 1991, R.R. Donnelley combined custom mapping expertise with advanced **spatial technology** to pioneer next generation electronic publishing software for interactive mapping applications. Throughout the early 1990s, MapQuest established a large number of significant partnerships with leading information-publishing companies around the globe and developed numerous electronic applications. In February 1996, MapQuest launched the first consumer-focused interactive mapping site on the Web, [www.mapquest.com](http://www.mapquest.com). With an innovative business model and first-of-its-kind Web site, [MapQuest.com](http://MapQuest.com) captured the attention of the Internet consumer and business market. It doesn’t go into any further details on “spatial technology”, but it would seem that **enipla** ’s description would be similar to this. ---
**Author:** ![sailor](https://avatars.discourse-cdn.com/v4/letter/s/a587f6/32.png) [@sailor](https://boards.straightdope.com/u/sailor)\ **Post date:** [June 27, 2003, 9:22am UTC](https://boards.straightdope.com/t/how-does-mapquest-work/184619/12 "2003-06-27T09:22:16Z")
They have a scaled model of the map. They put a bunch of hamsters it the starting point and a piece of cheese at the finish point and note the route the fastes hamster took. That is why they have a disclaimer that the system is not always accurate: sometimes a hamster is tired or not hungry. 🙂 ---
**Author:** ![enipla](https://avatars.discourse-cdn.com/v4/letter/e/54ee81/32.png) [@enipla](https://boards.straightdope.com/u/enipla)\ **Post date:** [June 27, 2003, 2:55pm UTC](https://boards.straightdope.com/t/how-does-mapquest-work/184619/13 "2003-06-27T14:55:33Z")
> [@](#): > > It doesn’t go into any further details on “spatial technology”, but it would seem that enipla’s description would be similar to this. Yep, we call them spatial databases. I’m working on address ranges for a road network at the moment. This will allow us to ‘geo-code’ an address database. In other words, it will relate an x,y coordinate for a paticular address. We will then be able to link it to a reverse 911 application. This gives us a way to select an area on a map and send out an automated phone call to all those folks that live in that area. Good for natural disasters and such.