|
I want to calculate all the possible distances between all the large towns and cities in the UK (about 2,500 places - my matrix will be about 6.3 million items) How should I go about this? I am on a windows machine. All distances can be approximated to the nearest mile. Why: My hosting site has gigs of disc space but won't let me run a route finder. |
|
Look at the Floyd-Warshall algorithm for finding the shortest path betwean all nodes in a graph in O(n^3) time. I am not sure what performence you might get out of the implementation and how well it will work on the OSM data but it is worth a shot. You might want to filter all non-routable elements and simplefy the ways (keeping the distance) to minimize the cost. |
|
Please email me at nroets@gmail.com. The Osm.org Routing Demo has lots of spare computing power and I think it will have the answer in a few weeks. Also note that the plain Dijkstra routing algorithm can find the shortest route from one point to many other points at the same cost of finding the route between that point and the farthest point. Running Dijkstra 2500 times on the UK network should not take more than 1 hour on a mere netbook. Which software would you use for that? I tested gosmore on a pak file covering Germany on an Atom D510 @ 1.66 Ghz with 2 GB of Ram available.
(28 Feb '11, 08:43)
petschge
The routing server takes 2.24 CPU seconds and uses 1.8GB RAM to calculate the 1400km route route across the UK. http://goo.gl/Shc8f It will certainly run a little bit faster and use less memory using a UK extract. So perhaps 2 or 3 hours on a netbook is more accurate, but certainly not years. Gosmore does not support point to multipoint. Perhaps other routers do.
(28 Feb '11, 09:13)
Nic Roets
That's why I asked which software you'd use for point to multipoint.
(28 Feb '11, 11:06)
petschge
|
|
The problem is a cross country route might very well take a minute or more to generate. So for 6.3 million entries your are looking at several CPU years to generate all routes. So how do other sites do this? They must cache the results to some degree... do they just cache the M and A roads? Or if they are doing it in real time, how?
(24 Feb '11, 23:33)
monkeboy
Basically they just generate the route on the fly. Main routes will generate in a few seconds and users wont mind to wait for that. Long routes across the whole country take a but longer but users will in general understand if they feel that it is a long trip. But even at a second each 6.3 million routes take 10 weeks to generate. Of course the site will cache the generated routes for some time, but cache hit rate will be rather low as most routing services offer more then 2500 places to choose from and the number of potential routes simply explodes.
(25 Feb '11, 06:16)
petschge
|
could you be a little more specific about "My hosting site [...] won't let me run a route finder"? what exactly don't they allow, and what do they? do they let you run a postgis database? sqlite/spatialite? especially the latter could be an alternative to having to precompute all 6.3 million combinations.