Highway Hierarchies is a technique of preprocessing the graph that allows for extremely fast (2-3 orders of magnitude faster) extraction of routes. This is being used by Google, OSRM and other projects. This model does not fit well with the general structure and philosophy of pgRouting, so this is a proposal for how we could integrate it. Second key point is that the source has been released under an AGPL license which is generally incompatible with our needs, but OSRM has create a new implementation under a BSD license.
This is one man's proposal for tackling this. The goal is to start a discussion and put more content and design behind it to move it forward into reality, whatever that may be.
We are looking for users, companies, schools that might be able to help fund this effort. Please contact Stephen Woodbridge or Daniel Kastl if you are interested.
We are also looking for developers that would be interested in contributing to this effort. Please look over the links, ask us questions and discuss your interests.
There are a lot of use cases where we do not need to dynamically define the graph and use cases where we need to pull many routes out in millisecond time frames like building distance matrices for TSP or VRP problems, or generating routes through via points, generating routes over Continental distances, etc. Without this technology we will never be able achieve quick results for these use cases.
There are probably a few different architectures that would allow this to be integrate. This technology requires two separate components:
We could store the prepared data in blobs in the database, but detoasting them is time consuming and would slow down performance. There is little intrinsic value in this approach that offsets the performance hit.