Already back in the 1950s, the Dutch researcher Edsger Dijkstra, pictured on a tandem bicycle (taken from: Edsger W. Dijkstra: a Commemoration), found a way to determine the fastest route between two points in an efficient way. Nevertheless, the scale of this problem with 3,739,585 cycling edges in the Netherlands and 1.6 billion point-to-point paths it becomes a much larger challenge. Directly using the Dijkstra algorithm would be very time consuming.
The key in speeding up the computations is by efficiently preprocessing the map. In our case, we use natural boundaries that show up in road maps. For instance, rivers and lakes divide the Netherlands in several components connected by a limited number of bridges and ferries as shown on the map. On a smaller level, you can further subdivide, leading to a hierarchical decomposition. For example, Amsterdam in components formed by various canal sections. For a shortest path computation, each component that does not contain A or B can be replaced by a simpler representation containing only a few edges without losing optimality of the shortest path. Dividing the Netherlands in the right components is a computation task that took us about an hour. We ended up with 37,771 components for this cycling map. When we have this map, we can compute the all the distance pairs. During the computations, we make a decision which part of routes to remember (cache in computer terms) for routes that are not yet computed. This helps us to avoid double computations for distance pairs that overlap.
At CQM we use point-to-point distances for various applications ranging from efficient routings within warehouses, to last-mile optimization. For example, every day we compute the most efficient way to combine taxi rides for elderly and disabled people who cannot use regular means of transport. These are about 2,500 rides on quiet days, up to 15,000 rides on Christmas day. For the computation of good solutions, we also need many point-to-point distances. If you want to know more about this application, you can check out the video of the online talk Analytics to improve mobility for elderly and disabled citizens given for the Analytics for a Better World initiative (August 2020).
This page was written by Frans de Ruiter, September 2021.