Turn cost support in DijkstraOneToMany

Open Source Routing Engine
1

I’m trying to create some distance (or weight) matrices. I’m currently using DijkstraOneToMany, and have created my own method (to avoid extracting a path):

public double calcWeight(int from, int to) {
    fromNode = from;
    endNode = findEndNode(from, to);
    return weights[endNode];
}

All’s working well - it creates a matrix for my country in about four hours.

However, I now want to add in turn costs - my expectation is that the path weight will now include a (customisable?) penalty for each turn/intersection along the route. However, I can’t seem to get anything different to the current results. That is, I get the same weights for the following (no turn costs)

encoder = new CarEncoder(5, 5, 0);
hopper = new GraphHopperOSM();
hopper.setDataReaderFile("...")
hopper.setGraphHopperLocation("...")
tMode = TraversalMode.NODE_BASED;
hopper.setEncodingManager(new EncodingManager(encoder));
hopper.getCHFactoryDecorator().setEnabled(false);
hopper.importOrLoad();
Weighting weighting = new FastestWeighting(encoder);
...

algo = new DijkstraOneToMany(hopper.getGraphHopperStorage(), weighting, tMode));

and this (my attempt at turn costs) - only changed lines shown:

encoder = new CarEncoder(5, 5, 1);
...
weighting = hopper.createTurnWeighting(hopper.getGraphHopperStorage().getBaseGraph(), new FastestWeighting(encoder), tMode);

Does DijkstraOneToMany not support turn costs, or am I doing something wrong?

2

Ok, apparently turn costs aren’t supported with traversal mode NODE_BASED - it sneakily just reverts to the super weighting, without telling you. (@karussell, wouldn’t an exception be preferred to avoid misunderstandings like this?)

Setting to EDGE_BASED_2DIR seems to be doing something different … but now DijkstraOneToMany runs out of memory (even after bumping up to 16G or so):

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at java.util.Arrays.copyOf(Unknown Source)
	at com.graphhopper.apache.commons.collections.IntDoubleBinaryHeap.ensureCapacity(IntDoubleBinaryHeap.java:209)
	at com.graphhopper.apache.commons.collections.IntDoubleBinaryHeap.insert_(IntDoubleBinaryHeap.java:84)
	at com.graphhopper.routing.DijkstraOneToMany.findEndNode(DijkstraOneToMany.java:167)
	at com.datamine.twodegrees.dmatrix.WeightOnlyDijkstraOneToMany.calcWeight(WeightOnlyDijkstraOneToMany.java:16)
	at com.datamine.twodegrees.dmatrix.DistanceMatrix.createAndWrite(DistanceMatrix.java:105)
	at com.datamine.twodegrees.dmatrix.DistanceMatrix.createOrLoad(DistanceMatrix.java:57)
	at com.datamine.twodegrees.dmatrix.DistanceMatrixMain.main(DistanceMatrixMain.java:31)

@karussell - not sure if this is a bug or because I’m not meant to use it DijkstraOneToMany with turn costs. I’ve had a quick look, and even though I’ve got under a million nodes, the heap balloons out to billions (hence the memory issue). It looks like the weights are coming out as infinite, and I’m guessing that’s mucking with the heap.

3

DijkstraOneToMany does not support edge based traversal. But have a look into a recent pull request: Turncost for Contraction Hierarchies by b3nn0 · Pull Request #912 · graphhopper/graphhopper · GitHub

Where one part of the change is a hopefully proper edge based implementation.

@karussell, wouldn’t an exception be preferred to avoid misunderstandings like this?

yes

4

Thanks @karussell - PR submitted.