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.