What does the distance metric measure?

[GoogleCodeExporter]

How is the distance metric printed after each routing calculated.
I would expect it to be the distance in meters between start and target
but it does not make any sense. Is it the time it takes to travel along the 
route?

It would be helpful to be able to calclate both the distance and time of a 
route.

Best regards
Erik Rosen
erik.rosen@gmail.com

Original issue reported on code.google.com by erik.ro...@gmail.com on 6 Sep 2010 at 2:02

[GoogleCodeExporter]

The distance metric used is the travel time metric as specified in the OSM 
Importer settings.

Getting the distance in meters could be achieved by two means:
[a] store additional data with each edge and pre-unpacked shortcut in the 
Contraction Hierarchies plugin. This would definitely slow down the route 
computation and take up additional storage space.
[b] Compute the distance between the coordinates of the route's path. This 
would be kinda slow as trigonometric calculations would be involved.

I some reservation on implementing [a] especially as I already plan to include 
more data into the routing data structure to allow for way name / type 
retrieval and turn restrictions / penalties.
Most likely I will add [b] as an option as it is achieved with little 
modification to the code and most likely not much slower than [a]. Furthermore 
a simple approximation parameter could be added to consider X coordinates at 
most. The approximation's result would be slightly smaller than the correct 
distance, e.g., for very long zig-zag ways.

What to you need the distance in meters for? How speed critical is it? How 
exact does it have to be?

Original comment by veaac.fd...@gmail.com on 6 Sep 2010 at 2:15

• Changed state: Accepted

[GoogleCodeExporter]

I need the distance to compute location clusters.
It is very speed critical (that is why I tried monav in the first place :) 
but it does not have to be very exact. +-5% is probably ok.

I did a test where I imported some osm data with all speeds set to 36 km/h = 10 
m/s and all average to 100%
and no penaltys, and I expected to get the travelled distance divided by a 
factor 10 but that does not
seem to work. I get approximately the half value of what I excpected. Do you 
why? Should it work?

Another question I have is that for some coordinates I get very long routes. 
See for instance the route between
58.906270148202545,17.94330183929527 and 
59.0352518373894, 17.966983464440222

and in the opposite direction i get no route at all.
Is this a problem with the data or with the algorithm?

Regards
Erik

Original comment by erik.ro...@gmail.com on 7 Sep 2010 at 11:40

[GoogleCodeExporter]

I have tested this with r231 and 
http://download.geofabrik.de/osm/europe/sweden.osm.bz2 and the attached speed 
profile as well as checked "Ignore Maxspeed Tag" and unchecked "Determine Speed 
within Cities with approximate City Boundaries" and cannot reproduce your 
result:

The result I get is 1848.6 * 10m = ~18km. This is the same as Google Maps 
computes:
http://maps.google.com/maps?f=d&source=s_d&saddr=59.0352518373894,+17.9669834644
40222&daddr=Centralgatan+26,+149+32+Nyn%C3%A4shamn,+Sweden&hl=en&geocode=FXTOhAM
dhycSAQ%3BFYjWggMdJ8sRASmDm6nqKFxfRjEy5IeEvwFMmw&mra=ls&sll=58.906906,17.941918&
sspn=0.009663,0.027251&ie=UTF8&ll=58.968951,17.945824&spn=0.16017,0.42469&z=12

The reverse direction is fine as well. 

Which revision did you try? How did you compute the route? Manually or using 
the RoutingDaemon or using the plugins in your own code? Have you maybe 
forgotten to set the speed for some highway entries?

With regards to your application: You say you want to compute location 
clusters? Does this involve computing huge distance tables? There exists a 
Contraction Hierarchies variant that can compute very large ( 10000x10000 ) 
distance tables in a short time. If your are interested I could point you to 
the corresponding papers.

Greetings

Christian Vetter

Original comment by veaac.fd...@gmail.com on 7 Sep 2010 at 1:34

Attachments:

• distance.spp

[GoogleCodeExporter]

Ok I have checked out r236 and downloaded the sweden.osm and now it works fine.
I get 1840 both ways.

Probably there was a problem with my dataset, I had downloaded a bounded box of 
osm data and
the boundaries might have been a bit too tight...
Thank you for testing.

I have now encountered another issue:

When I route with these coordinates I get the following error:
59.32403090128917, 18.448843808221554
to
59.08756054502774, 17.570472828856577

MoNavC: binaryheap.h:165: void BinaryHeap<NodeID, Key, Weight, Data, 
IndexStorage>::DecreaseKey(NodeID, Weight) [with NodeID = unsigned int, Key = 
int, Weight = int, Data = ContractionHierarchiesClient::_HeapData, IndexStorage 
= MapStorage<unsigned int, unsigned int>]: Assertion `key != 0' failed.
Aborted

Regards
Erik

Original comment by erik.ro...@gmail.com on 7 Sep 2010 at 9:30

[GoogleCodeExporter]

I found the error. It occurred whenever the source / target are positioned on a 
loop. It was introduced in r228 when I started to interpret whole ways as edges 
and not just their segments.

Please try whether r239 fixes this. As I also fixed a small error in the 
OSMImporter you have to repeat the preprocessing.

Thanks for reporting this.

Original comment by veaac.fd...@gmail.com on 8 Sep 2010 at 9:04

[GoogleCodeExporter]

Please try r245 instead of r239

Original comment by veaac.fd...@gmail.com on 8 Sep 2010 at 7:53

[GoogleCodeExporter]

Ok now I run r247 and it works fine most of the time.

For a few coordinates I get distance=-1 (or -0.1 before multiplying by 10) even 
though the 
router->GetRoute() returns true. Does this indicate that no route was found?

Try for instance:
59.31571551130793, 17.999882902324654
to
59.37897183186112, 17.835483405972024

/Erik

Original comment by erik.ro...@gmail.com on 9 Sep 2010 at 9:10

[GoogleCodeExporter]

Should be fixed in r248

Original comment by veaac.fd...@gmail.com on 9 Sep 2010 at 9:38

[GoogleCodeExporter]

No route is found in this case because the nearest routing edge is a linving 
street that is not connected to any road surrounding it:

http://www.openstreetmap.org/browse/way/37589851

Original comment by veaac.fd...@gmail.com on 9 Sep 2010 at 9:46

[GoogleCodeExporter]

Ok, so that is basically a data problem. An edge that is not connected to a 
road should probably not be accessible by motorcar. I have to find a workaround 
for this problem...

By the way it would be interesting to read the papers you mentioned. I do 
compute very large distance tables.

/Erik 

Original comment by erik.ro...@gmail.com on 9 Sep 2010 at 11:40

[GoogleCodeExporter]

You could try to remove all nodes that are not connected to the largest 
component in the graph.

In regard to distance tables:
The original Contraction Hierarchies diploma thesis ( 
http://algo2.iti.kit.edu/1094.php ) mentions the use case of many-to-many 
searches.

The basic principle is:
Contraction Hierarchies queries are bidirectional queries consisting of a 
forward search space and a backwards search space. Both search spaces are very 
small, usually a few hundred nodes for large graphs. When computing shortest 
paths from a set of nodes S to a set of nodes T you perform a backwards search 
for each node t in T and permanently store this search space's information with 
each node in a bucket. Next you perform forward search from each node s in S 
and check for each node encountered in which backward search spaces it is, 
updating the distance to the responding target nodes.

This means you have to perform one search for each source / target node only. 
The most expensive part is scanning the information stored in the buckets.

The diploma thesis mentions that a 20000 * 20000 tables in the European data 
set could be computed in ~37s.

As this technique is completely independent of the preprocessing step it can 
also be used with MoNavs parallelized and simplified and less demanding 
preprocessing. Nevertheless, the query would have to be modified to perform the 
many-to-many queries.

Furthermore you might consider using Contraction Hierarchies with a graph class 
that loads the complete data set into RAM. MoNav uses an external memory 
approach that only needs few hundreds of kilobytes, but is slower than a RAM 
based graph by a factor 3 to 6. Also, if your are not interested in the actual 
route's path, much of the data MoNav stores can be dropped, i.e., each edge 
would only need a forward and backward flag as well as its length. MoNav stores 
additional information to replace shortcuts with their description.

Original comment by veaac.fd...@gmail.com on 9 Sep 2010 at 12:25

• Changed state: Fixed

[GoogleCodeExporter]

I implemented the above mentioned many-to-many algorithm for the closely 
related OSRM [1] project. Although the code is not yet in trunk, I am sure it 
is fairly easy to port it to MoNav once it is there. 

It computes a distance table of size 10000*10000 in about half a minute for 
sweden.osm and about a minute for a fairly large road network like the U.S.

[1] http://routed.sf.net

Original comment by dennis.l...@gmail.com on 15 Sep 2010 at 9:11