When managing your transportation as a supply chain manager, you will certainly encounter a scenario where you need to find an efficient and effective combination of routes that minimizes the total distance traveled from your warehouse to your different local stores. One way to do that is by solving the Vehicle Routing Problem (VRP). In this article, we will be using the basic and classical version of the VRP, which is the Capacitated Vehicle Routing Problem (CVRP). The latter considers the limited capacity of delivery vehicles.
The Vehicle Routing Problem
The VRP is a combinatorial optimization and integer programming problem that answers the question: “Which is the optimal set of routes and trips that our vehicles should travel in order to satisfy the demand of our set of customers?”.
The aim of the CVRP, like many other common transportation problems, is to reduce transportation costs, and it does that by choosing an optimal set of routes to be performed by vehicles with limited capacity to serve the demand of customers.
One more important thing to consider here is that stores or customers must get their delivery exactly once by one vehicle and that each vehicle starts and ends its round trip at the warehouse.
Mathematical Model*
After this brief description of the CVRP, it becomes easy to understand the mathematical model of the problem.
Our objective function is to minimize the total distance traveled, which is equal to the sum of all the distances of the chosen routes and trips. The first and the second constraint require that each store should be served only once. The third constraint ensures the conservation of the flow, which means that the outflow of a store is equal to its inflow minus its demand. To avoid sending a truck with more units than it’s needed, we add the fourth constraint that ensures the trucks will return empty to the warehouse. The fifth constraint means that if a route is part of the optimal round trips, then the quantity carried by the vehicle should not exceed its capacity. And finally, the last constraint is that xij variables must be integers.
Information needed
Here is a list of information that we need in order to solve our CVRP:
- The distribution network with warehouse and stores in place
- Product demand at each store or for each customer
- Distance matrix that aggregates all the distances between every two facilities
- The maximum capacity of vehicles
Below is the network design we are going to use. It’s a simple network with one warehouse and the other six facilities are Stores. Facilities are put on the map using SCM Globe software.
Moving to Excel*
Before moving to model our problem, let’s first enter our data to excel. We start by entering the demand of each store, vehicles capacity (C), and distance matrix (dij). In our example, we have a total demand of 125 and a vehicle capacity of 70. The screenshot below shows exactly this.
Something to keep in mind here is that those distances are not round trip distances, and so if you are using SCM Globe to simulate your supply chain, then you should divide the distances provided by the software by two.
The next step now is to add our decision variables to the excel template. As mentioned earlier, the decision variables are the binary variables xij that are equal to one if the route between the facilities i and j will be traveled and zero if not. The second decision variable is the quantity qij of units moving between two facilities i and j. These two decision variables will help us know which routes are parts of our optimal trips and what quantity should a vehicle carry for each of these trips.
The column “Out” in the “xij matrix“ is equal to the sum of each row, which means it’s equal to the number of vehicles leaving each facility. The row “In” in the same matrix is equal to the sum of each column, which is actually equal to the number of vehicles entering each store. The column and the row will help us add the first and second constraints of our model to the excel solver. Of course, these numbers should be equal to one for stores and not necessarily the case for the warehouse because we may have different round trips starting and ending at the warehouse.
Concerning the second decision matrix, we added four columns: “Outflow”, “Inflow”, “balance” (which is equal to the Inflow minus the Outflow), and “Demand”. We did that so we can add quickly and easily the flow conservation constraint in Solver.
For the fourth constrain of our model, we will add another matrix that calculates “qij-C*xij” for each route and the values must be less than or equal to zero.
Now that we completed our spreadsheet template, and before creating and running the solver model, it’s time to define the total distance formula. As mentioned earlier, the total distance traveled is equal to the sum of all the distances of the chosen routes and trips. The excel formula for the total distance cell is then “SUMPRODUCT(xij Matrix;qij Matrix)”. In our example, it’s equal to “SUMPRODUCT(G5:M11;G14:M20)”.
Creating and Running the Solver Model
To create the solver model, first, go to the “Data” tab, and click on the “Solver” button that can be found on the right side. [If you have not installed the Solver yet visit this link to learn how to install it: https://www.solver.com/excel-solver-how-load-or-start-solver.]
Once the solver tab opens, we have to set the objective. In our case, we select the “C12” cell in orange; this is our total distance. The variables that we are changing are grouped in the two yellow matrices, and so we select these matrices in the second block.
Concerning the constraints, we have to click on the “Add” button. The six constraints created are shown in the figures below. After adding all these constraints, we have first to make unconstrained variables non-negative by selecting the checkbox. By respecting these installed constraints we can run our Solver model by selecting the Simplex LP (a solving method since our model is linear).
The model is now ready, and so we can click on the “Solve” button before seeing results.
N.B: The Excel Solver may take some time to do the calculations before you can see the results. If you have a lot of stores, let’s say 30 for example, the excel solver will not be able to solve your problem. One way to overcome this is to install OpenSolver, and fix a calculation time as a stop criterion. This way, you may get a good feasible solution, but generally not the optimal one.
We can translate these results by drawing the trips and the quantity moving in each route. We start from the warehouse, and we link facilities i and j where xij is equal to 1.
We can see that there are two different round trips to different stores, the first one in dark blue and the second one in red. These trips can be traveled by one vehicle in two separate deliveries, or by two different vehicles. This model gives us good results since the demand is satisfied and we have empty trucks entering the warehouse.
Final thoughts
In your original SCM Globe supply chain model, try to do the same thing with the data provided and solve the problem. If your supply chain problem is a little bit different, consider adding or changing constraints. or the objective function to customize the mathematical model to your specific needs. When you get a solution from the solver, implement that solution in the supply chain model and run a simulation to see what happens. This will help you to make judgments and sometimes find further opportunities to improve the solution.
Answers from equations such as the mathematical solver model presented here will point you in the right direction. But human judgment is still required to adjust and fine-tune these answers to account for factors in the real world not covered by the equations.
Remember, supply chain management is both an art and a science, and simulations bring the two together. Simulations show how well a given course of action will work (science), and human judgment can then adjust the course of action to get the best overall results (art).
See also our blog post “How to Solve Transportation Problems Using Excel Solver” – https://www.scmglobe.com/how-to-solve-transportation-problems-using-excel-solver/
* The mathematical model and the excel template were inspired by this video’s example: Vehicle Routing Problem (VRP) – Example Hard Mixed-Integer Linear Programming Problem
Featured image by: José Martín Ramírez Carrasco on Unsplash