I am using the Google OR Tools vehicle routing implementation and am trying to incorporate traffic times into my time matrix by using the Google Maps API. However, the Google Maps API has limitations on how big of time matrices it can build, how many requests can be done in certain amounts of time, etc.
I know that the Google OR Tools VRP expects this time matrix, but I don't need the travel times between all combinations of all origins and destinations. For example, I am inputting pickup/dropoff pairs, for which it does not make sense to calculate the travel time from each dropoff to its assigned pickup. Additionally, perhaps I could also not calculate the travel time between locations that are far away (I'd establish some maximum distance) from one another. It would reduce the computational complexity to not have to call the API for these combinations and instead have certain constants as placeholders in the time matrix for these combinations.
Can this routing model be run in loops, such that for the first iteration I only calculate the travel times between the most likely assignments and inside each loop each driver gets assigned a pickup/dropoff pair and then in the next loop the travel times between already made assignments don't need to be calculated anymore? I don't even know if this would change the computation time.
Has anyone else had this problem before? I'd be interested in hearing any advice and/or additional heuristics to use.
VRP travel matrix required input is all the possible distance between visit location. You can reduce the complexity of the problem by assuming the distance between A to B is equal to B to A, this will also reduce the API call to the Google Map API. To be noted, the travel matrix shape must always be symmetrical.
The distance between locations is required for the VRP solving heuristic to find the next optimal nodes to be visited.
If you are certain that there are some locations that will not be visited after visiting some location, you can set the distance between those locations as Big M (i.e, sys.maxsize()). However, be careful with the direction constraint (pickup dropoff constraints), if you set Big M between the 2 locations that are linked by the constraint, the solver will definitely fail.
Google OR Tools VRP with time windows and Google Maps API