Don’t hesitate to contact us:
Forum: discuss.graphhopper.com
Email: support@graphhopper.com
Update: there is an update of this update 😉
Our customers send us thousands of vehicle routing and traveling salesman problems every day to solve them. To do this we always need to calculate a distance matrix at the beginning. This should be fast. If you have 10 drivers that deliver 100 parcels, we have to find the distances and travel times between all the locations up-front. Only with this information we can find out which driver delivers which parcel and which sequence is the most efficient one.
When we speak about a “distance matrix”, we actually mean a matrix with distance and time information to estimate the total cost of a route.
A simple approach of determining such a matrix is to calculate every single point-to-point route and extract the time and distance information from it: A to B, A to C, A to D, B to C, B to D and so forth. How fast can this be? Let us assume that an average route has a length of 100km. Given this we could handle roughly 600 route requests per second per thread. A 100×100 matrix would then take approx. 17 seconds. Not bad for 10K routes with time, distance and geometry information as well as turn instructions – some tools need hours for this!
A vehicle routing problem with more than 100 locations is not uncommon and so we need even faster procedures to calculate the underlying distance matrices. Already a few years ago, we had implemented a fast matrix algorithm that caches shortest path trees. This has speeded up matrix calculation considerably – as you can see in the table below:
| matrix size | point-to-point | old matrix |
|---|---|---|
| 100² | 17s |  2.4s |
| 500² | ~7min |  40s |
| 1000² | ~28min |  148s=2.5min |
| 2000² | ~2h | 575s=~9.5min |
The computations times are now a magnitude faster, for example, a 500×500 matrix only takes 40 seconds as opposed to 7 minutes with the point-to-point route approach. Nevertheless, a 1000×1000 matrix takes more than 2 minutes. This can be further improved just by adding hardware and dividing a large matrix into smaller matrices and calculating them concurrently.
But what if we could speed-up the matrix calculation even further? That’s what we did just recently in addition to the parallelization. The impacts of this new matrix approach are summarized in the following table (single thread):
| matrix size | old matrix | new matrix |
|---|---|---|
| 100² | 2.4s |  1.2s |
| 500² | 40s |  4s |
| 1000² | 148s=2.5min |  8s |
| 2000² | 575s=~9.5min |  22s |
A 1000×1000 matrix can now be determined in 8 seconds rather than 2.5 minutes. To put it in other words and figures, this new approach allows us to calculate over 181 000 road distances every second!
It helped us to reduce the overall computation time of solving a vehicle routing problem significantly. It reduces delays and increases our throughput, especially for the time-dependent route optimization where each single vehicle routing problem requires a number of distance matrices.
Do you want to try this out? Sign up for an API key and read more about the GraphHopper Route Optimization API.
Happy Routing!
