3

I've been working for quite a while now on a service that generates optimal routes for a given set of addresses and vehicles (Vehicle routing problem / traveling salesman problem).

Now it's all working fine, but the bottleneck is getting the distance/time between two addresses used for calculation. Currently we use webservices like google/mapquest to request the distance and store the result for caching. So we only request the distances once.

At the moment we have about 100milion records in cache and it made me wonder: How does google do this for every address in the world? We are talking about hundreds of billions of combination.

Even just storing every corner in a street map and then calcalate each straight road with a haversine formule and adding the results would result in massive amounts of data.

Now I understand google can handle massive amounts of data, but there are also a lot of small companies providing distance/street information. Do they all store all this data on their own or is there some magical method of calculation i'm missing?

1

You start out using A* with intersections as nodes. GPS units in the 90s had enough memory and processing power to do that. You don't have to store the distance from every intersection to every other intersection. Just to the next intersection over.

A* uses heuristics to avoid searching possibilities that are unlikely to be on the shortest path. If you're driving from New York to LA, it's not going to search paths that go through Florida. You'd be surprised how efficiently it works on real-world data, even just using crow-flies distance as the heuristic.

Google has made many proprietary tweaks to improve its heuristics to favor interstates and major thoroughfares, take traffic into account, not take weird detours through side streets, etc. They probably also do a hierarchical search for really long trips, using different heuristics for local and interstate travel, basically using one search to get onto the interstate, another to get to your destination city using a database with only major intersections, and then a local search to get to your hotel, the same way a human would plan a trip.

For individual addresses, you interpolate. 200 E. Main is at the intersection of 2nd and Main. 300 E. Main is at the intersection of 3rd and Main. So you know 250 E. Main is halfway between. You don't have to store every individual household.

5

TL;DR: Yes, there is something you are missing.

Google appears to calculate a true minimum-time route based on their estimate of travel times over every road segment in the area. The time to calculate a perfectly optimal route between two points in a network is linear in the number of edges in the network, so even through a dense street network it is possible to calculate an optimal route fairly quickly. In my experience, Google does this very well -- they seem to really consider all the possible routes, and sometimes calculate routes over surface streets that few people would have considered.

  • They don't realy consider every option, thats impossible. They provide the way to calculate the quickest route in Google OR-Tools, which we even use ourselfs. But even there we need every distance between point A-B to calculate what is shortest. My question is "Do they actually store every distance or is there some magic math equation or something else" – Hugo Delsing Oct 16 '15 at 7:38
  • Of course they don't store the route for every origin and destination. They calculate it on demand, and then recalculate it when traffic conditions change. It is possible to calculate the absolutely best route between two points in a large network (say a million edges) in a couple of seconds. – kevin cline Oct 16 '15 at 8:23
  • You cant even calculate the absolute best route for 20 nodes in any practical application. That requires the knowledge of 20*19*18*17...*3*2*1=2,43290200817664e+18 distances to find out the best. Read up on the traveling salesman problem.\ – Hugo Delsing Oct 16 '15 at 8:31
  • Regarding your edit. In a Least Cost Routing you need to know the COST for every route, to determine which is the cheapest. To use the same thing on a map, you need the COST (distance) between each node on a map. Considering openstreetmap has almost 3.000.0000 nodes, they can't just store the COST between every node. But calculating the cost on the fly between every node can't be dont either. – Hugo Delsing Oct 16 '15 at 8:37
  • @HugoDelsing "Cheapest route between A and B" is a completely different problem from "Cheapest route between N points". The first has some pretty good applicable heuristics ("never move sufficiently straight back to A" would be one), the second is NP-complete. – Vatine Oct 16 '15 at 9:15
1

Simple. Google uses divide and conquer techniques. If you take long road trips, you almost certainly use the interstate. Due to their common use in performing calculations, a lot of such calculations are simply lookups. What is the distance between say Tennessee and Florida? Calculate the interstate route and lookup the respective distance between these two points on the interstate.

Anything else is simply a matter of calculating shortest distance from the starting point to the interstate and later from the interstate to the final destination, which reduces a potentially thousand mile journey calculation into two 10 mile journeys and a table lookup.

  • According to quickfacts Florida has 9.000.000 housing units. Considering there could be one-way streets the distance from A-B is different than B-A. So just for every distance between housing units in Florida we need 9.000.000*9.000.000 different distances. That's not simple at all. – Hugo Delsing Oct 16 '15 at 7:31
  • 1
    @HugoDelsing that's just a A* run using the interstate as a long hop as a shortcut – ratchet freak Oct 16 '15 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.