You are Here:Home>>Business>>How To: Clarke and Wright Heuristic – Part 1

How To: Clarke and Wright Heuristic – Part 1

By | 2017-06-11T21:00:26+00:00 Jan 6, 2017|Business|

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.

Distances Matrix

Lisbon Beja Évora Setúbal Alcácer do Sal
Origin = Sines 165 107 140 132 72
Lisbon 178 132 50 91
Beja 80 144 97
Évora 99 101
Setúbal 58
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.

Original Scenario 

Sines / Lisbon 330
Sines / Beja 214
Sines / Évora 280
Sines / Setúbal 264
Sines / Alcaçer do Sal 144
Total 1232

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.

Savings Matrix

Lisboa Beja Évora Setúbal Alcácer do Sal
Lisboa 94 173 247 146
Beja 230 38 44
Évora 125 140
Setúbal 142
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.

S1 Lisboa To Setúbal = 247
S2 Beja To Évora = 230
S3 Lisboa To Évora = 173
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
S7 Évora To Setúbal = 125
S8 Lisboa To Beja = 94

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.

About the Author:

A father, a husband and a geek... Biitlog Founder, The Tech Labs founder, among other projects.

Leave a Reply