Capacitated Vehicle Routing Optimization
Optimization: Optimization is an act/process of making a process behave in the best possible way. It is a method to find the best solution to either minimize or maximize a certain parameter. Minimizing the cost for a product or maximizing the productivity of a machine is an optimization problem.
There are different variables which may impact the process and those variables have to be considered when we think of optimization. It is one of the most interesting topics for mathematicians and scientists and there are many algorithms that deep dives into different type of optimization problems.
Optimization mostly focuses on two components:
· Objective function: There must be a parameter that has to be optimized, the said parameter can be input as a function to maximize or minimize
· Constraints: Constraints are some restrictions that must not be breached to solve the problem. I will detail them, further in the blog.
In this blog, I will be writing about a specific type of optimization problem called “Travelling Salesman Problem” and its variants. The Travelling Salesman Problem requires finding the shortest path in which a person must travel so that he passes through all the destinations at least once.
To solve a TSP, the simplest method that can be followed is the brute force method where we calculate the distance in each route and finally select the route with the lowest distance/time/cost.
However, this method doesn’t generalize well when the number of locations increases. For 3 destinations,6 routes are possible but as number of locations increases to 15,it becomes 130767436800 and will keep increasing as the number of patterns will be N! (N factorial), this will make the solver run for days and years without even finding an answer. To resolve this there are many algorithms that work to find an optimal solution. Methods to solve the TSP and definition can be found here. Explanations of these methods in detail are beyond the scope of the article and can be found easily over a quick search.
In this blog, we will discuss how to solve TSP and a variant of it using Python. There are many solvers available in python to solve optimization problems like pulp, or tools, concorde, etc. We will use OR-tools to create a program that solves the TSP.
OR-Tools:
OR-Tools is an open-source software for combinatorial optimization, which seeks to find the best solution to a problem out of a very large set of possible solutions. OR-Tools solve linear optimization, routing problem, bin packing, scheduling, etc. It is developed by developers at Google and is open source. For solving routing problems similar to TSP,it uses constraint base programming on top of an SAT solver. The Paper for the same can be found here. We will solve a version of TSP call CVRP(capitated vehicle routing problem) which have multiple vehicles with a defined capacity trying to visit all the node at least once. If we solve this TSP will be a subset of above-defined problem where the vehicle is one.
Data Requirements:
To Solve the TSP, the primary data requirement is the distance matrix. The distance matrix provides the distance between locations and can be calculated in multiple ways. We can use Euclidean and Manhattan distance or can use the available distance matrix API from google/MS or any other provider to calculate the distance. Below are the methods to calculate the distance matrix-
Scipy distance matrix:
Distance has to be an integer and not a float as the solver accepts only integers and any float input will generate error.
Distance matrix API:
Below code can calculate distance between two location using distance matrix API. Documentation can be found here.
The other inputs that are required are the demand at each location and capacity of the vehicle (in case of constraint on the capacity of vehicle), the depot or the starting location, and the run time for the algorithm.
To get the data we will create a function that will set the data. We will create a dictionary that will have all the information required to solve the problem like distance matrix, locations, depot, vehicle capacity, etc. we will also make sure we only consider those locations where the demand is more than 0, this will avoid vehicle going to empty nodes.
Once the data is set is ready we will create two function named print_solution and compute model.
Compute Model: This function will first initialize the routing manager which will be responsible for optimization. Then we have to create a call back for the distance object which has to be optimized. Similarly, if we want to have the demand as a constraint we have to create a call back for it. Any additional constraints like return or time will be added here. Finally, the call back would be added to the routing model which will run to optimize the cost of the routes. Finally, we have to set some parameters like the solution strategy, algorithm run time, etc., they can either be set manually to try different strategies (there are multiple strategies to solve TSP/VRP) or can be set as default as per the requirement.
Print Solution: This function is used to print the output and create different type of output we need. We may want to show the outputs in different format like chart, edge graphs, print statement etc. We can even add different outputs here to show as insights.
How the solution works: In case of 1 source multiple destination problem for example, we have location 1 as depot and 2,3,4 as different location with 1 vehicle the solver will create a new location say 5 which is a replica of the depot 1. So now we can treat the problem as to start from 1, visit 2,3,4 in the best order and then go to 5. In case of multiple vehicle, the replica of depot will be created no of vehicle time. The solution is a meta heuristic algorithm on top of SAT solver which tries to minimize the cost for each arc.
Conclusion:
The above solution can be used to solve TSP as well as VRP and capacitated VRP to solve the last mile delivery problem in supply chain. If the time matrix(time taken to travel between locations) is used in place of the distance matrix it will optimize the time taken for each vehicle for the delivery. A similar solution can be applied for different delivery use cases. The above output can be shown in a network graph to show the path clearly. We can also leverage the google APIs to create maps on top of the output to show the path of different vehicle clearly. The solution has many use cases in real life and can be scaled and applied to different problems.
References:
https%3A%2F%2Flink.springer.com%2Fchapter%2F10.1007%2F0-306-48126-X_8
