www.impianti.dii.unipg.it

 In the following a simple example shows that Matrix of Savings can be better tha nearest neighbor heuristics:

 

Consider the following point to be sequenced in a classical TSP:

 

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

 

 

 O is the Distribution Center, so the Root must start and end there.  The Coordinated are the following:

 

Points X Y
O 0
A 1 1
B 1 2
C -1 2
D 5 0

 

By using the rule of nearest neighbor the, starting  from O  and ending in O and not visiting more than once each point., we obtain:

  

 

Bound

O-A

A-B

B-C

C-D

D-0

Tot

Distance

1.41

1.00

2.00

6.32

5.00

15.73

 In the following figure the route is shown:

 Figure 1 Nearest Neighbor rule based Route


 

It is quite straightforward that the following route should be better: 

Figure 2 Nearest NeighBor improved

 

 

Bound

O-A

A-C

C-B

B-D

D-0

Total

Distance

1.41

2.24

2.00

4.47

5.00

15.12

 


 

 But by using the Saving Matrix Method we have:

  

 

 

A

B

C

D

A

0.00

 

   

B

2,65

0.00

   

C

1.41

2.47

0.00

 

D

2.29

2.76

0.91

0.00

 

 Savings Matrix

 

 

So the cost is less than for near neighbor rule. In figure the route is shown

 

Savings Matrix Method based Route