[GraphHopper] Matrix calculations with CH

[me]

Hi,

What is the current support for matrix calculations (i.e. n source points to n target points) using contraction hierarchies in the open source graphhopper code?

I found this post from last year

https://lists.openstreetmap.org/pipermail/graphhopper/2013-July/000254.html

I think I understand the principle behind caching each shortest path tree from your n source points - it's similar to what they do in the paper 'Computing Many-to-Many Shortest Paths Using Highway Hierarchies' by Knopp et al.

This way you should be able to just run 2 x n shortest path tree calculations with contraction hierarchies - one for each direction as CH is bi-directional, yes?

As the caching, combining of results etc is probably quite complex, is this currently implemented in graphhopper or will it be in the near future?

Many thanks,

Phil


Sent from Samsung Mobile

-------- Original message --------
From: Emux <devemux86 at gmail.com> 
Date:  
To: GraphHopper Java routing engine <graphhopper at openstreetmap.org> 
Subject: Re: [GraphHopper] Cruiser (mapsforge) and GraphHopper 
 
Cruiser 1.2.4
Cruiser Beta 1.3.12

Now both have offline routing via GraphHopper.


On 27/4/2014 21:08, emux wrote:
Cruiser is an Android map and navigation application using offline vector maps (Mapsforge).

Cruiser Beta 1.3.9 (mapsforge rescue-exp 0.5.0 & render theme v4)

- Offline routing (GraphHopper)

The graph folder can be defined at 'Settings' - 'Navigation'.
Cruiser supports graphs with contraction hierarchies enabled or disabled.

From Wiki:
Contraction hierarchies is a post-import process which makes routing         faster (bidirectional algorithms).
At the moment only one travel mode (usually car) can be used if contraction hierarchies is enabled.
A more flexible routing (but slower) with multiple travel modes (car, bike, foot) requires graphs with contraction hierarchies disabled.

I have created contraction hierarchical graphs for some regions.
http://www.talent.gr/public/graphs/
There are also some no contraction hierarchical graphs, having the suffix '_vehicles'.

You can email me if you need more graphs.

-- 
Emux
Cruiser - Atlas
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20140521/ce57a198/attachment.html>