Cracking the Vehicle Routing Problem using Google’s OR-Tools
Vehicle Routing Problem (VRP) is classified an NP-hard problem, which simply said the bigger your options, the cost of finding the best solution will grow tremendously.
In the center, VRP can be said as an optimization problem, which usually goes like this:
Given my capacity of N fleet, and a set of M locations that needs to be visited, how can I achieve the best combination possible?
Now while the problem sounds very similar to TSP, it differs in several points:
- VRP involves multiple moving actors, in this case a fleet of vehicle (car, bikes, etc), while TSP usually described with 1 sales.
- VRP is, though it can be relative on case by case basis, be subject to multiple constraints, be it on the vehicle’s capabilities (capacity, skills, size, etc) or even the visited location (serving time window, location, etc).
- The definition of optimal solution, where TSP usually be the most locations visited, but VRP will be different with each needs.
Now how do we solve it then?
The simplest way, and the one which will yield the best result, is to iterate all possible solutions and by appointing scores on each, pick the solution with the highest score!
How hard can it be, right?
Well, again, it’s NP-hard. Specifically in this particular problem, the complexity is at the very least “N!” (read, N factorial where N being the number of locations).
So if we’re going to find the best solution with brute iterations, we’ll be lucky if the number of locations is ≤9 which gives us 362.880 of possibilities. Going to 10 locations, we start talking in millions, 3.628.800 to be precise. And even only 25 locations, it already yields 15.511.210.043.330.985.984.000.000 possibilities, heck I don’t even know how to spell it, let’s not even mention >100 locations.
If you’re not keen to wait that long for the best result, and decided that you can be satisfied with the near-best result that is actually achievable, that’s where Google’s OR-Tools came in.
It’s an amazing open source tools with the goal of solving optimization problems such as VRP, it’s very easy to setup with options of clients in Python, Java, or C++.
OR-Tools have it’s own set of pages on how to solve VRP, but to simplify it, all we need to do is to provide a square matrix of distances and time to travel between each points. So for example, if I have 5 locations say Central Park, Wisma Barito, UOB Plaza, Plaza Bapindo, and District 8, I would have to provide the following matrices:
To generate the matrix, there are multiple ways, some can be paid such as Google’s Direction Service or Mapbox’s Direction API, or some can be done using open source such as OpenRouteService, or you can even calculate the Great Circle Distance between the coordinates.
Of course OR-Tools is not the only open source project aiming on solving this, others like VROOM also exists, it’s simply the most relatively popular. And VRP should covers other real world constraints, such as the location’s service time window, pickup-and-deliveries, and so on.
There are many parts which cannot be covered in a single post, on how tools like OR-Tools works, finding solutions using heuristics (or meta heuristics), road limitations, and so on. Hopefully we can cover those other cases on the next time.
Would love to hear any input, or discussions on this, thanks for reading!
