Solving Traveling Salesman Problems Using Excel Solver Evolutionary Algorithm
Did you know you can simply get the optimized route for your delivery by using Excel? We will cover it up in this tutorial.
Traveling Salesman Problem
The Traveling Salesman Problem (TSP) has been around for quite some time. I provided a brief explanation of TSP in another post here, so make sure to check it out. Solving TSP has been a challenge because it is an NP-Hard problem, so it becomes more difficult as you have more cities in your dataset. The search space will grow at a rate of 2n! (N is the total number of cities or destinations).
There are a number of alternatives when you don’t really have the urgency to obtain the best optimal solution but rather want a good solution within a short time. One of the tools that can be leveraged is Excel’s built-in Solver, which can provide the solution.
Preparedness!
Before we dive into it, please prepare your data. You will need the distance matrix to solve TSP. You can obtain the accurate distances by using the Google Maps API or Bing Maps API (basic programming language knowledge is required). Alternatively, you can manually retrieve the distances from Google Maps.
For this tutorial, I will be using the data provided below. You can download the Excel files here.
We will then make named range of distmatrix in Excel for range “B2:L11”.
Solve the Problem
Before continuing, make sure you have activated the Excel Solver. Check here for the steps.
Next, we need to add the following for our calculation of the optimized route and our objective value.
The column of Order will be our decision variable.
The column of Distance will be our distance calculation for the total distance taken. Then we will want to sum of all our distance, this will be minimized in the model.
We will add the calculation for distance by using Index function.
For the first and last destination, we add the index of each other. The formula is as follows = @index(distmatrix; firstnodes;lastnodes that precedence the firstnodes).
You can add the basic vlookup function on the left for better readibility.
Don’t forget to add the sum of distances.
Open Solver by going to Data > Solver.
Notice that we are using Alldif, which makes the order will be always different, and Evolutionary Algorithm, which basically genetic algorithm. You can change the mutation rate to 0.5 by going to Options > Evolutionary Algorithm. Set the time limit without improvement to 30s.
The Interpretation
Click solve and wait for the result to come up.
So we get the optimized total distance of 132 km, if we visit the city with this order: Serpong → Larangan Indah →Kedoya Utara → Grogol → Pademangan →Pegangsaan Dua →Rawamangun → Ps. Rebo → Depok → Tangerang.
Closing
Thanks for reading, you can download the completed excel files here. Be sure to follow and like this tutorial.
