Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP

Loading…

Truncation errors in edge-weights can lead to suboptimal routes #324

Closed
tyrasd opened this Issue · 2 comments

3 participants

Martin Raifer Emil Tin Dennis Luxen
Martin Raifer

When calculating the weights of edges in extractor.cpp, the exact weight (expressed in tenths of seconds) is simply casted (thus floored) to integer.
This is a systematic error, which later on leads to a bias towards routes with more but shorter edges against straight routes (as there occurs more truncation in the first case). This could lead to osrm routing over a winding mountain pass instead of the motorway around it.

This is solved by rounding instead of flooring the exact weight to integer:

int intWeight = std::max(1, (int)std::floor(0.5+ (edgeIT->isDurationSet ? edgeIT->speed : weight)) );

Also, this rounding errors are quite large. (I did a very quick&rough estimation with some osm-data: I found the truncated weight to be a few %, typically; but it can be more than 20% in worst case!)
As it doesn't harm to use centi- or milliseconds for the weight of an edge (or does it?) I would consider to do that:

double weight = ( distance * 1000. ) / (edgeIT->speed / 3.6);

Examples of affected routes:
http://map.project-osrm.org/NN
http://map.project-osrm.org/Pu

Emil Tin
Collaborator

might be related to #246 ?

Dennis Luxen
Owner

Yes, may be related to issue #246. Investigating this right now.

Dennis Luxen DennisOSRM referenced this issue from a commit
DennisOSRM Implements issue #324. Thanks tyrasd. 4118039
Dennis Luxen DennisOSRM closed this
Kirill Zhdanovich referenced this issue from a commit in Zhdanovich/Project-OSRM
DennisOSRM Implements issue #324. Thanks tyrasd. 87abc51
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.