DennisOSRM/Project-OSRM — Issue #81: adding a viapoint to route leads sometimes to a duration way to high, while the distance is correct
Author: DrVanScott
Created: 2012-01-18 11:24:17+00:00
State: open

first of all i cannot reproduce this problem on http://map.project-osrm.org , only with my local installation, which is based on your current development branch.

The route produced by

/viaroute&start=49.464478210352,11.149670375707&dest=49.437419461439,11.765135420685&z=13&output=json&jsonp=showResultsRoute&geomformat=cmp&instructions=true

is reasonable, distance and duration are correct. (53km, 36min). After adding a via point, the request

/viaroute&start=49.464478210352,11.149670375707&dest=49.437419461439,11.765135420685&via=49.40734,11.76091&z=13&output=json&jsonp=showResultsRoute&geomformat=cmp&instructions=true

produces also a reasonable route. Distance is again correct (57.5km). But now the duration is 1h 10min, which is abolutly wrong. If i calculate two seperate routes start->via and via->end, the sums are good: (57.6km, 39min).

I tried to track down the problem by comparing SearchEngine::ComputeRoute and SearchEngine::ComputeViaRoute. I have to admit that i do not really understand that code up to now. But the following lines came to my attention:

In ComputeViaRoute:

_forwardHeap->Insert(phantomNodePair.startPhantom.edgeBasedNode, distance1-phantomNodePair.startPhantom.weight1, phantomNodePair.startPhantom.edgeBasedNode);

In ComputeRoute:

_forwardHeap->Insert(phantomNodes.startPhantom.edgeBasedNode, -phantomNodes.startPhantom.weight1, phantomNodes.startPhantom.edgeBasedNode);

There are 4 similar lines in ComputeViaRoute. The term "distance1-phantomNodePair.startPhantom.weight1" is not really clear to me (which may be because i don't understand the whole thing... ;-) ). So i changed the code that it looks like ComputeRoute in this detail (changing 4 lines!). Et voilà: The route is correct, and also distance and duration: 57.6km, 39min

One other thing i noticed: In ComputeViaRoute the variables 'middle1' and 'middle2' are initialized with UINT_MAX outside of the foreach loop. If i understand correctly, the value UINT_MAX should be a signal for failure (?) of SearchEngine::_RoutingStep. Shouldn't be they initialized within that loop?