Performance penalty for multiple-route search

Developers
1

Hi there,

I am building a big-data solution to compute a massive number of routes in Uk. (About 350 million routes). As we are currently using Spark platform, GH is a very convenient solution since it is done in Java.

As you can imagine, I am particularly worried about performance.

I have observed a dramatic performance penalty when running GH for multiple routes alternatives:

  • Setup to use Contraction Hierarchies (only computes the shortest path) -> it computes around 100 routes / second (per core)
  • Setup to use “alternative paths” -> around 0.3 routes per second.

My question are:

  • Are this difference reasonable?
  • Is there any plan in the roadmap to implement “multiple route computation” using CH?

Thanks in advance.
A

My code to create GH:

forServer()
setGraphHopperLocation(tmpFolder)
setOSMFile(osmFile)
val encoder = new CarFlagEncoder()
setEncodingManager(new EncodingManager(encoder))

if (alternativePaths) setCHEnabled(false) // This is the only difference in the setup

importOrLoad()

val req: GHRequest = new GHRequest(start.latInDegrees, start.lonInDegrees, stop.latInDegrees, stop.lonInDegrees)
    .setWeighting("fastest")
    .setVehicle("car")
    .setLocale(Locale.US)

if (alternativePaths) { // This is the only difference in the quert
  req.setAlgorithm(Parameters.Algorithms.ALT_ROUTE)
  req.getHints().put(Parameters.Algorithms.AltRoute.MAX_PATHS, "10")
}
2

Are this difference reasonable?

Yes, as it is not CH.

BTW: with ALT we have soon a faster algo which could be used for alternative routes but this is not yet done

Is there any plan in the roadmap to implement “multiple route computation” using CH?

Not yet

3

For reference the related issue with alternative routes improvements:

4

Thanks a lot for your help.