Improved Isochrone Calculation released in openrouteservice v6.3.0

With the release of openrouteservice v6.3.0 at HeiGIT, we are presenting a new and improved speed-up technique that makes it possible to calculate much larger isochrones than with the existing algorithm. An isochrone is an area on the map that can be reached from a starting point within a time or distance limit specified by the user.
How does the improved algorithm work?
By utilizing the topological properties of our road network, we can identify cells of the network that are connected to other cells only via very few roads. With this process called partitioning, it is possible to drastically reduce the computational time needed for finding all roads that can be reached within a certain time limit.

Baden-Württemberg bike graph partitioned into cells
Baden-Württemberg partitioned into cells

A 5h isochrone around the town of Tübingen is calculated as an example. With the old isochrones algorithm, this request takes more than 35s to process. The new, partitioning-based implementation returns the same result within just 3.5s. More than a 90% decrease in processing time!

Bike isochrone of 5h around the town of Tübingen
Bike isochrone of 5h around the town of Tübingen

The ORS API restrictions due to openrouteservice’s old algorithm, a maximum of one hour driving time for car or trucks and five hours for walking and biking, are therefore not necessary anymore. Now, it is possible to calculate isochrones for hours of traveling time in just seconds.
The new algorithm is currently only available on self-hosted instances of openrouteservice, but will be enabled on our live API soon.

The algorithm is adapted from “Fast Computation of Isochrones in Road Networks” by Valentin Buchhold.

Further details on the implementation can be found in the openrouteservice GitHub repository, while more news concerning openrouteservice can be found under http://giscienceblog.uni-hd.de/tag/openrouteservice/.


Posted

in

,

by