www.impianti.dii.unipg.it

 Savings Matrix Example

here you can find the Italian version of the Matrix Savings Method with solution. 

The case was developed for the student of the course of Facility Management and Industrial Logistics

 

 

The Example

We would like to determinthe routing of a fleet of vehicles with different capacities.

A Distribution Center (point 1) can use up to 6 vehicles with known capacity (table 2) to deliver to 10 delivery points (points 2-11) known quantities (table 2) . You know all the distances between 10 points and (table 1).

  • Create the routing for each truck.
  • Calculate the total distances for each truc

 

DATA:

 

Table 1 the Distances Matrix

 

Table 2 Quantities to be delivered to each point.

 

 

Table 3 Trucks available and their capacity


The Execution

Generally speaking savings by joing together points i and j is:

sij = d1i + d1j – dij

For instance for points and 3we have:  s32 = d12 + d13 – d23 = 4565 + 4706 – 2919 = 6352

And so on for all the other combinations.

 

Table 4 The Savings Matrix

Then Savings and their relative Delivery Points to be linked are ordered

Savings Points to be Linked

10742 (7,11)

9359 (3,9)

9259 (5,6)

8635 (7,10)

8300 (9,10)

8114 (2,5)

8065 (7,9)

7925 (2,6)

7213 (3,10)

6668 (2,9)

6361 (3,7)

6352 (2,3)

5652 (5,9)

5493 (6,9)

5362 (3,5)

5275 (10,11)

5149 (3,6)

4360 (2,10)

4311 (3,8)

4263 (8,9)

4148 (2,8)

3993 (9,11)

3723 (5,8)

3541 (6,8)

3522 (8,10)

3463 (5,10)

3407 (2,7)

3225 (6,10)

3094 (3,11)

2785 (7,8)

2509 (5,7)

2270 (6,7)

1430 (4,10)

1389 (4,9)

1364 (3,4)

1328 (4,7)

1227 (4,8)

1217 (8,11)

1031 (2,4)

1004 (2,11)

901 (4,11)

858 (4,5)

782 (4,6)

496 (5,11)

340 (6,11)

table 5 Savings ranking list

 We can then create the routes. Trucks are filled in the order they are assigned (we will use as first truck 1, after truck 2 and so on).

Let us consider the first truck, with capacity:  t1=1300.

From table 5, it can be noted maximum savings are with points 7 and 11 (10742).

c7 = 1300

c11 = 700

c7 + c11 = 2000 > t1 = 1300

Then it is not possible to serve 7 and 11 with truck 1.

 

We consider then the second savings.

From table 5: points 3 and 9 with savings equal to 9359.

c3 = 1200

c9 = 250

c3 + c9 = 1450 > t1 = 1300

It is not possible to serve and 9 with truck 1.

 

We consider the following savings.

From table 5: points 5 and 6 with savings equal to 9259.

c5 = 200

c6 = 750

c5 + c6 = 950 < t1 = 1300

It is then possible to serve together points 5 and 6 with truck1.

Left available capacity of truck 1 is then: t1 - c5 + c6 = 350

We try to insert other points in the route.

From table 5: points 7 and 10 with savings equal to 8635.

c7 = 1300

c10 = 450

c7 + c10 = 1750 > Available Capacity

It is not possible to serve 7 and 10 with truck 1.

 We continue trying other points in the route.

From table 5: points 9 and 10 with savings equal to 8300

c9 = 250

c10 = 450

c9 + c10 = 700 > Available Capacity

It is not possible to serve 9 and 10 with truck 1.

We continue trying other points in the route.

From table 5: points 2 and 5 with savings equal to 811

c2 = 300

c5 = 200

Points 5 is already in the route so we insert only point 2. Its quantity is less than available capacity so it can be added.

Left capacity in only 50 and there are no points we such small quantity. The route for truck 1 is done.

At the end all the points have one arc in input and another in output, excepted two. Those two are the first and the last point of the route starting from DC and ending to DC. After reaching the first point it is straightforward to include all other points of the route:

1 ->2->5 ->6 ->1

 

This is the total distance:

1 -> 2: 4565

2 ->5:1200

5 -> 6: 828

6 ->1: 5338

 

Total distance: 11931

 

 

We consider now the second truck: t2=1500.

From Table 5,  maximum savings is with points and 11 (10742)

c7 = 1300

c11 = 700

c7 + c11 = 2000 > t2 = 1500

It is not possible to serve 7 and 11 with truck 2.

Let us consider the following savings.

From table 5Let us consider points and 9 with savings equal to 9359.

c3 = 1200

c9 = 250

c3 + c9 = 1450 < t2 = 1500

It is then possible to serve and 9 with truck 2.

Left available capacity is: t- c5 + c6 = 50.

This capacity is small than all the other quantities to be delivered, then the route for the truck 2 is over.

 

We can the build the sequence of the route of Truck 2.

 

1 ->3 ->9 -> 1

 

Total distance is:

1 -> 3: 4706

3 -> 9: 1407

9 -> 1: 6060

 

TOT_distance12173.

 

 

Let us consider the Truck 3t3=1300.

From table 5, maximum savings is for 7 anbd 11 (10742).c7 = 1300

c11 = 700

c7 + c11 = 2000 > t3 = 1300

It is not possible to serveand 11 with truck 3.

 

 

From 5: points 7 and 10 with savings equal to 8635.

c7 = 1300

c10 = 450

c7 + c10 = 1750 > t3 = 1300

Neither points 7 and 10 can be served by truck 3.

 

From table 5: we have points 10 and 11 with savings equal to5275.

c11 = 700

c10 = 450

c10 + c11 = 1150 < t3 = 1300

It is then possible to include points 11 and 10 with truck 3.

Left capacity is: t– (c11+ c10) = 150

 

Before looking for other points to be included within the truck 3,let us consider the remaining points: 4, 7, 8. None of the three points must receive an amount ≤ 150. Assign points 10 and 11 would result in a truck 3 not reaching the full load. For this reasons to the truck 3 it is assigned only point 7 with the delivered quantity of 1300.

 

Route is simply:

à 7 à 1

 

Truck 3 distance is then:

à 7: 8291

 

TOT_distance: 16582.

 

Let us consider now truck 4:  t4=1400.

 

From table 5 points 10 and 11 with savings equal to 5275.

c11 = 700

c10 = 450

c11 + c10 = 1150 < t4 = 1400

It is then possible to serve points 11 and 10 with truck 4.

Left capacity is then: t– (c11+ c10) = 250.

 

 

We try to insert other points in the route.

From table 5: points 8 and 10 with savings equal to 3522.

c8 = 200

c10 = 450

Point 10 is already in the route so we add only point 8, with a delivery quantity less than available capacity.

Left capacity is then 50 and there are not point with such small amount. The route of Truck 4 is then done.

 

 

The truck 4 route sequence is then:

 

à 8 à 10 à 11 à 1

 

Truck 4 distance is then:

à 8: 2223

à 10:3496

10 à 11: 8128

11 à 1: 8607

 

TOT_distance: 22454.

 

 

It si then left only point 4 with truck 5: t5=1200.

 

c4 =450 < t5 = 1200

 

 

Route is then:

à 4 à 1

 

Truck 5 distance is then:

à 4: 716

 

TOT_distance: 1432.

 

 

Finally:

 

Truck

Routing and Scheduling

1

àà 5 à 6 à 1

2

àà 9 à 1

3

à 7 à 1

4

à 8 à 10 à 11 à 1

5

à 4 à 1

6

Not used