Following our last How-To article on how to use the Clarke & Wright Heuristic to solve a routing problem exercise, we will show now, how to do the same thing, but in a bit easier and quicker way, by using the Microsoft Solver Foundation Excel Add-in.
Solver is a very practical tool when it comes to deal with optimization models. And apart from the use as an add-on, it can be also used within the software or web development environment. If you want to know more, go to Microsoft Solver Foundation page.
To complete this tutorial, you will need:
- Understand the Clarke & Write Heuristic – read the first tutorial
- Microsoft Excel
- Excel Solver Add-in – Download
Before starting, you will need to install the Solver add-in in Excel. Just go to the link above, download it and install it. Open Excel, check data tab in the top ribbon. You should see it under Analyze. In case you can’t find it, go to File -> Options -> Add-Ins. Check under Inactive or Disable Add-ins. Select it and click Go button. A dialog box will open. Check box, click Ok. It should be visible now.
Step 1 – Prepare Matrix
As we have seen in the last tutorial, we were working with a symmetric matrix, where the distance between point A -> B, is the same as B -> A. Although for that exercise we have only populated top half of the cells.
In this case, we will need to populate it at 100%. As they are symmetric, it is easy. Just full fill the columns, in the same way, you see the rows.
We will also need to add Origin to the columns. At the end table should be like the bellow:
|O/D||Sines||Lisboa||Beja||Évora||Setúbal||Alcácer do Sal|
|Alcacer do Sal||72||91||97||101||58||0|
Now we will need to use a new row, separated from the table, well we will use numbers to identify each of the locations columns.
Being Sines, 1; Lisboa, 2; …; Alcácer do Sal, 6 and add 1 for the origin, as we will need the vehicle to come back to the initial point. In order to be easier to consult the places, I’ve added this values on the top row, above the table and repeated on 10th row and on H10 add the same value as cell b10. In this case H10 = B10 = 1.
As we did in the last tutorial, we need to calculate the distance between points. In this case, we will to use the Index formula to do it.
In the B12 cell insert:
The B$3:$G$8, refers to the whole matrix, that includes all the distances between all points. Then we need to point the rows and the columns that intercept each other, in order to return the value.
Example: The distance between Sines and Lisbon is C3.
Now copy the formula to the next cells, till you have 6 cells populated. Leave the 7th cell blank and then in the next one sum all the distances.
Excel sheet should looks like the bellow.
So, the total distance in the original scenario would be 652 km. Remember that we had a restriction where the maximum distance allowed to travel in one day would be 500 km.
Step 2 – How-to use Solver
Once completed the step 1, we are ready to use solver.
Go to Data -> Solver. A dialog box should open. In the objective, we will set it as our Sum cell I13. Because this is what we want to minimize.
As we need to minimize, we should be sure to choose it in the To: options fields.
Next, we must inform which are the variables that can change. We will choose the cells from 1 to 6. This is what Solver will change the order till finding a solution.
Then we must tell to solve if there are any restrictions or constraints. We have two:
Except for the origin that must be equal to the final destination, all the intermediary points must be visited only once. So, they must be all different.
The second restriction is that total distance of the route must be equal or below 500 km.
As we are talking about a simple problem, you can set to 5 or 10 seconds the time solving limit. Click solve.
You should get 499 km. So it is the same as our finding in the first tutorial.
Although, most probably, it returned an origin point other than Sines. Well, the point is that in this kind of exercise, you are able to get the optimal distance between all points, x times = to x points. In this case, we are able to get the same solution having the six places and origin as well.
You can try and click solve several times and it will give you every time a new solution under the same distance result.
Stay tuned for the next How-To article on Route Optimization, where we are going to show how to use the NorthWest Corner Method a Transportation Algorithm in Linear Programming.