a slightly different use of contraction hierarchies
Fletcher
I'm a PhD student at UC Berkeley in the states and work in the field
of urban simulation (http://urbansim.org/). I have a question about
contraction hierarchies and the code you have available. Let me
explain to you my problem.
In planning we often do what are called "accessibility" queries as
opposed to "routing" queries. Instead of having a specific
destination in mind, we want to know how much employment, population,
or whatever are reachable in a certain amount of time. So instead of
looking for a single node in the street network, we want to know all
of the nodes within, for example, 30 minutes of driving time. In
theory, the concept which leads to contraction hierarchies should
still be useful, as people will tend to use arterials, highways, etc
for the "trunk" part of the transport. First of all, since you are an
expert in the field, do you think contraction hierarchies will help
our type of query? And second, is your code adaptable for this sort
of thing?
Just so you know, we use open streetmap data for our simulations, and
have travel times available for all the links in the network. Also,
we don't do any work on mobile devices yet - these queries have access
to multiple processors and the OSM data structure is all stored using
BGL (Boost Graph) in memory.
What do you think? And thanks in advance!
Fletcher
Christian Vetter
First of all, sorry that it took me so long to answer you.
On Sat, Jun 4, 2011 at 12:55 AM, Fletcher <fscot...@gmail.com> wrote:
> Hi there -
>
> In planning we often do what are called "accessibility" queries as
> opposed to "routing" queries. Instead of having a specific
> destination in mind, we want to know how much employment, population,
> or whatever are reachable in a certain amount of time. So instead of
> looking for a single node in the street network, we want to know all
> of the nodes within, for example, 30 minutes of driving time. In
> theory, the concept which leads to contraction hierarchies should
> still be useful, as people will tend to use arterials, highways, etc
> for the "trunk" part of the transport. First of all, since you are an
> expert in the field, do you think contraction hierarchies will help
> our type of query? And second, is your code adaptable for this sort
> of thing?
Yes, Contraction Hierarchies can be used in this case. However, they
will only bring you a significant advantage over a Dijkstra's search
if your search radius is large enough. E.g., if your search result
yields less than 50 vertices it might not be worth it.
The basic approach: You are doing a forward search until you'll hit
the search radius and then do a combined downward search from all
discovered vertices at once. The advantage is, that you do not have to
use a proper priority queue for the downward search, since you are
dealing with a DAG. If your search radius is huge ( or your data
organized to support locality ) this means you'll simply scan the
vertices in order. This can easily be parallelized. You should take a
look at the paper(s) about PHAST [1], where they tried that approach,
ported it to GPUs and supported one-to-all queries in the whole
network of Europe in about 2ms / search tree.
> Just so you know, we use open streetmap data for our simulations, and
> have travel times available for all the links in the network. Also,
> we don't do any work on mobile devices yet - these queries have access
> to multiple processors and the OSM data structure is all stored using
> BGL (Boost Graph) in memory.
In this case I would advise you to take a look at OSRM instead. It
shares some CH code with MoNav, but is optimized for server usage. It
is licensed under the AGPL license.
Feel free to write again if you have some questions. Also I'm
interested in the results, should you try to pursue this approach.
Best regards,
Christian Vetter
[1]: http://research.microsoft.com/apps/pubs/default.aspx?id=144834
[2]: http://project-osrm.org/