We often have very large problems with 500 jobs or more. We use Graphhopper to get the routes between the jobs and workers to determine costs.
We currently cache the Graphhopper response between two locations, so the next time we try to get the same costs we get the cached version.
I came across this blog post, which appears to be describing the same problem we have with the time it takes to calculate a matrix of routes. The article mentions that the time was able to be reduced drastically. Does anyone know how this was achieved?