Overview

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.

Request for Funding

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.

Request for Quotes

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.

Links

• https://github.com/DennisOSRM/Project-OSRM
• http://algo2.iti.kit.edu/schultes/hwy/esaHwyHierarchies.pdf

Why is this important?

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.

How could/would it work?

There are probably a few different architectures that would allow this to be integrate. This technology requires two separate components:

1. Build Graph - This will be the graph preparation step. It will read the edges data and prepare the data for use. * reads data from postgresql database, other reads may be added later. The goal here is to be data neutral, ie: load any data. * writes prepared data to a filesystem file * maybe adds a record to a metadata table about the file, coverage area, data source, min/max node ids, edge ids, etc. Might not be needed.
2. Route extraction tools - these will query the prepared data and extract routes, driving directions, distance matrices, etc. * this is a standalone service that accesses the required file and runs the appropriate query on that file * we write a C wrapper function for postgresql that can connect to the service and run appropriate queries and then format the results back to SQL * optional, wrappers to access service directly from PHP, Perl, Python, .NET, etc.

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.

What needs to be done?

• review existing OSRM code and make a plan for this conversion
• decide if we can do this with the ProjectOSRM or it needs to be a fork
• prototype a service and access the issues of accessing it from postgresql
• extract the graph builder
• extract the request handler
• designs, tech docs, apis, tests
• coding, testing, admin docs, user docs, etc