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?