Contraction Hierarchies

Hi all,

recently we have proudly released our new version of Intertour 6.0 including our brandnew routing approach for very fast matrix calculation. This new routing approach called Contraction Hierarchies is based on the development of  ITI (http://i11www.iti.uni-karlsruhe.de/ ) at the University Karlsruhe (KIT  http://www.kit.edu/) and had been refined and adapted for matrix calculation in a collaboration of PTV AG with the  ITI.

The contraction hierarchies routing approach recently became famous in several tech talks and press releases as the world’s fastest route calculation approach. The approach uses a special preprocessing which has to be performed only once for each vehicle profile that should be used (e.g. CarFast). After such a preprocessing , you are able to calculate very large matrices with up to 5000×5000 locations all over Europe or even bigger in an incredible time of about 1 minute on a current PC. In comparison, the same calculation of such a matrix using our former technology took ages (… more than 20 hours) on the same machine.

This means we now have a speed-up factor of about 1200 for a matrix calculation of 5000×5000 locations. Even if we would add the time for the one-time preprocessing job of about 1 hour for a mid-european city road network to the query calculation time we still would get a speed-up of factor of about 20 for large matrices.

This entry was posted in PTV xServer by Martina Beck. Bookmark the permalink.

About Martina Beck

Martina Beck has been working for PTV since 2000. As certified computer scientist she was originally responsible for providing customers with technical support and she later moved on to the Product Management division. Since 2011 she has been working for PTV as an online marketing manager in international marketing with an emphasis on social media (et al. Facebook, Twitter, Google+, YouTube). The PTV Developer Blog is the PTV Developer Components' lead channel. The posts on important topics and trends originate from close cooperation with developers, the product management and other experts.

2 thoughts on “Contraction Hierarchies

  1. Hi Cosmin,
    currently we are focussing on the ch-development in the xServer. If and when contraction hierachies will be in the MapServer is not planned yet.
    BR
    Sven

Comments are closed.