Comment by sa46
5 months ago
Somewhat related, I looked at a bunch of solvers for vehicle routing with time windows. One thing that surprised me was that the SaaS-based distance matrix calculations were prohibitively expensive. Google charged $0.01 per matrix element.
How do folks normally get the distance matrix? I ended up just using the Mapbox Optimization API instead of using a solver.
It is always a question of accuracy / convenience. You can start with straight / geodesic distance. One step up is to use open street maps with an offline open source router [1]. But if you want the accurate driving distance with the latest closures / traffic data the big vendors are the only choice.
[1] https://wiki.openstreetmap.org/wiki/Routing/offline_routers
Take a look at OSRM. For the Timefold Field Service Routing REST APIs, we have a maps service that runs OSRM under hood by default, but supports alternative map providers too. It calculates both travel time and distance matrixes.
Our maps service does do a bunch of additional optimizations (caching, incremental requests, ...) to assist any solver model we run that request maps information.
I've had to solve this in a number of ways. The fastest I've found is to precompute a hash map at a low-granularity (well, update on batch cycle regularly). Graphhopper with OSRM + OpenStreetMap data are useful in this domain, to the point where relatively dense polygons can be mapped on 16 CPU hours in a 100km by 100km block.
The GraphHopper Matrix API has an (IMO) attractive pricing especially for large matrices. The pricing is credit based and for large matrices we do not charge for every matrix cell but instead we only charge "locations*10". E.g. for a 200x200 matrix we only charge 2000 and not 40 000 credits as our underlying algorithm is very efficient (scales nearly linear). And let's say you need this calculation 25 times a day (using the premium package) then this leads to $0.016 for 1000 matrix elements. Of course even cheaper for larger matrices.
And larger packages will furthermore include a volume discount.
Disclaimer: I'm one of the founders.