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.

asked 24 Feb '11, 13:56

monkeboy's gravatar image

monkeboy
1111
accept rate: 0%

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.

(25 Feb '11, 12:27) axk

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.

permanent link

answered 27 Feb '11, 21:52

Nic%20Roets's gravatar image

Nic Roets
58391219
accept rate: 6%

edited 27 Feb '11, 21:54

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.

permanent link

answered 24 Feb '11, 19:57

petschge's gravatar image

petschge
8.0k207196
accept rate: 21%

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

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.

permanent link

answered 28 Feb '11, 12:59

Gnonthgol's gravatar image

Gnonthgol ♦
13.6k15101198
accept rate: 16%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×139

question asked: 24 Feb '11, 13:56

question was seen: 6,030 times

last updated: 28 Feb '11, 12:59

powered by OSQA