Cracking the Vehicle Routing Problem using Google’s OR-Tools
Cracking the Vehicle Routing Problem [TECH]
Welcome to Flynd Product Series Article. This post kickstarts our series of product updates and a place for us to share more techy stuff with the general audience.
Being a technology-centered company, our development team always exploring ways to solve multiple complex processes and algorithms with performance, scalability, and development continuity in mind to provide our clients the best product they can get on the market.
In this first post, we are dedicating this to one of the most complex issues we try to tackle in the industry, route planning, or usually known as Vehicle Routing Problem (VRP).
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 vehicles (car, bikes, etc), while TSP usually described with a salesperson.
- VRP is, though it can be relative on a 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 an optimal solution, where TSP usually be the most locations visited, but VRP will be different from each need.
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
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 tool to solve optimization problems such as VRP, it’s very easy to setup with options of clients in Python, Java, or C++.
OR-Tools have their 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 point. 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 to solve this, others like VROOM also exist, it’s simply the most relatively popular. And VRP should cover other real-world constraints, such as the location’s service time window, pickup-and-deliveries, and so on.
There are many parts that cannot be covered in a single post, on how tools like OR-Tools works, finding solutions using heuristics (or metaheuristics), 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!