Clarke and Wright Heuristic is a very common and known model to solve an open vehicle routing problem (OVRP).
This is a similar problem to capacitated vehicle routing problem (CVRP), which relates the capacity and the needs of a range of customers (supply/offer), which we will talk about in future articles.
The point of C&W Heuristic is to minimize the cost of the total route distances and number of vehicles to be used. Not always is possible to have only one vehicle to call all points, or to run the total distance in a single day and therefore, we might conclude more than one route.
This simple example will explain how to use this very use tool to improve and get the best routing option.
In the following map, you will see a route of distribution without any filtering. We have just chosen the origin (O – Sines, PT) and the locations we need to visit (Lisbon, PT; Beja, PT; Évora, PT; Setúbal, PT and Alcácer do Sal, PT). We don’t really care about the sort of the locations other than be sure about the origin point. All the remaining can be in whatever position, as at the end of this exercise we will get the best and possible alternative to use.
Please be aware that using this model, capacity is not taken in mind, only distance cost.
This route looks a bit confusing with lot of intersections. Maybe at the end it will look better…
In order to get it a bit more complex, we will add a distance restriction, this is, a truck is not able to run over 500km in a day. So how many trucks and points will we be able to visit?
In order to start, we will need to build a board like the bellow with the distances between points. In this model we acknowledge that the matrix is symmetric, meaning that the distance between point A to B = B to A.
|Lisbon||Beja||Évora||Setúbal||Alcácer do Sal|
|Origin = Sines||165||107||140||132||72|
|Alcácer do Sal||–|
In this example i’ve used google maps to measure the distances and build the above matrix. This will be helpful as we can at the end easily sort the points in the same order and compare whether the results are similar or not.
So, the original picture would be going from origin to each of those locations and return. In this case we would have a total of 1232 km and the need to use 3 trucks, as we have implemented a restriction of 500 km / day.
|Sines / Lisbon||330|
|Sines / Beja||214|
|Sines / Évora||280|
|Sines / Setúbal||264|
|Sines / Alcaçer do Sal||144|
After writing down the distances matrix, we will need to calculate the savings between points. The savings are calculated by combining two points within the same route and their distance to the origin.The formula is:
Doi + Doj – Dij
Doi – the distance between origin and point i;
Doj – the distance between origin and point j;
Dij – the distance between point i and j;
For instance, to calculate the Sines – Lisbon – Beja – Sines route saving, we sum the distance between origin and each point, minus the distance between both points, this is:
165 km + 107 km – 178 km = 94 km
In the Savings Matrix you add the 94 km savings in the Lisbon / Beja cell. Calculate the following routes and you should get a matrix similar to the one bellow.
|Lisboa||Beja||Évora||Setúbal||Alcácer do Sal|
|Alcácer do Sal||–|
Now with the savings, we have a better picture on those where we have more savings by using it. The first rule is to start with the biggest saving.
In order to be easier to sort out the decreasing order of the savings you can make a new board like the one bellow.
|S4||Lisboa||To||Alcaçer do Sal||=||146|
|S5||Setúbal||To||Alcaçer do Sal||=||142|
|S6||Évora||To||Alcaçer do Sal||=||140|
As mentioned we will start by the biggest saving which is S1 – 247km
Sines 165 km + Lisboa 50 km + Setúbal 132 km + Sines = 347 km
Now we should add S2, although, none of the points are common to S1, therefore we are not able to use this saving at the moment. Lets check S3.
S3 is composed by Lisbon and Évora. Lisbon is a common location with S1. So we can use it. We will need to add Évora between Sines (Origin) and Lisbon.
Sines 140 km + Évora 132 km + Lisboa 50 km + Setúbal 132 km + Sines = 454 km
Now we can check back S2, since Évora is already in our route.
Sines 107 km + Beja 80 km + Évora 132 km + Lisboa 50 km + Setúbal 132 km + Sines = 501 km
We notice that we have passed the restriction. Although since there is only one location left, we can try and see if adding it to the routing if we are able to decrease the total distance or not.
We must now use a route that includes Alcacer do Sal. For that we have S4, S5 and S6. Although, we can only add additional points between origin and a location, this is, in the beginning or at the end. Therefore, we should choose S5 and add it to the end.
Sines 107 km + Beja 80 km + Évora 132 km + Lisboa 50 km + Setúbal 58 km + Alcácer do Sal 72 km + Sines = 499 km
So our final solution is below the 500 km restriction which makes it as a valid solution. We conclude then, that we are capable to use only one truck to visit all the locations in one single day.
We can now check back the google maps and sort the locations in the same way and see if the result is similar. It is noticeable that result is similar. We also see that the route is now much more simple and clear.
Feel free to comment and, or add additional examples for OVRP solving models.