You can find here the case of Saving Matrix Method In Italian
here you can find an example of Saving Matrix Method with solution.
Here you can find the matlab source code for Saving Matrix
Here you can find an elementary comparisions between Savings Matrix and Nearest Neighbor
The case was developed for the student of the course of Facility Management and Industrial Logistics
The Management of Deliveries
The Savings Matrix Method
Release 2.0 July 2014
Case Study by:
Prof. Stefano Saetta
Dr. Valentina Caldarelli
Department of Engineering University of Perugia – Italy
Copyrights to Stefano Saetta and Valentina Caldarelli
Distribution System
Distribution System is the part of the Logistics systems responsible of facilities and operations that include Finite products warehouses, Distribution Centers, Distribution Channel and final client delivery.
The subject is the final product and the goal is to deliver it to the final client in the right time.
The delivery goals depend on the caractheristics of the final product: perishability, high technological content, etc.
For every company it is necessary to plan the distribution system
In the following figure we have an example for the food industry:
Figure 1 Food Supply Chain
The Distribution System in the Food industry is an interesting issue because of tight requirements in terms of safety, perishability, traceability etc.
We will study the Distribution Center Network, that includes suppliers in the inbound transportations and clients (retailers, restaurants etc.) in the outbound.
The Case Considered
The case considered is the "Filiera dei Piccoli" in Umbria, a network in the food sector (here for more information, here in Italian).
Figure 2 Case considered
2 A simple case by hand and Google Maps
Let us consider 5 nodes, where the first one (1) is the DC the starting and the ending point of the route.
Those are the data of the considered points.
Table 1 nodes data
Name 
Town 
Address 

1 
SA.FO.LAT SAS 
Perugia 
Via Ottavio Prosciutti 25 
2 
ALIMENTARI BARTOCCINI 
Perugia 
Strada Trasimeno Ovest 161/F 
3 
CENTRO FRUTTA DUE S.A.S. 
Perugia 
Via Romeo Gallenga 8 
4 
PASTAFRESCA DUERRE 
Perugia 
Via Giuseppe Frenguelli 49/D 
5 
ROSTICCERIA ELLERA SNC 
Corciano 
Via Antonio Gramsci 53 
Position on the map is the following (source ©2014 Google).
Figure 3 In red the distribution Center and the delivery points (in blue)
In this simple version nor vehicle capacities nor quantities to be delivered are considered nor time windows constraints..
By inserting in Google Maps^{@} in the table 1 the following routing is obtained(30.2 km).
Figure 4 The starting route
We must decide, with the support of Google Maps, the optimal routing. This is a classical TSP (traveling salesman problem), where we should sequence the order of visits to the delivery points.
It is possible to go in a systematic manner, by trial and error method, by changing the order of visits (taking into account that DC is always the starting and the ending point).
Figure 5 changing the sequence order of points
There are, obviously many possible configuations. In the following or the possibilities and their global distance are shown (the optimal one is highlighed):
1à2à3à4à5à1 30.2 km
1à2à3à5à4à1 24.4 km
1à2à4à3à5à1 32.8 km
1à2à4à5à3à1 33.8 km
1à2à5à3à4à1 22.1 km
1à2à5à4à3à1 28.6 km
1à3à2à4à5à1 30.4 km
1à3à2à5à4à1 19.5 km
1à3à4à2à5à1 28.1 km
1à3à4à5à2à1 29 km
1à3à5à2à4à1 22.3 km
1à3à5à4à2à1 34 km
1à4à2à3à5à1 23.9 km
1à4à2à5à3à1 22.4 km
1à4à3à5à2à1 22.3 km
1à4à3à2à5à1 18.6 km
1à4à5à3à2à1 24.7 km
1à4à5à2à3à1 19.8 km
1à5à2à3à4à1 19.1 km
1à5à2à4à3à1 28.4 km
1à5à3à4à2à1 33.5 km
1à5à3à2à4à1 24.1 km
1à5à4à2à3à1 30.8 km
1à5à4à3à2à1 30.6 km
Figure 6 Optimal Routing
It is easy to understand that there are [ n! ] combinations.
This a quick complexity increasing problem with n, the number of deliveries points.
Computational Complexity
The complexity is the measure of the time and the memory required to execute an algorithm to solve the problem
An algorithm is a procedure to solve a problem. In this sense it makes sense to:
A. To determine the algorithm efficiency to solve a problem
B. Try to evaluate the difficulty of a problem.
A. To determine the algorithm efficiency
We should estimate the required time to solve a problem for an algorithm. The goodness of the algorithm is based on the minimum quantities of required resources for the solution:
 Required time to execute the elementary actions.
 Time: global number of elementary actions (aritmetical, logical, comparisons, assignements) as function of the n dimensions of input data
 Memory space required to store and manipulate the data.
More interesting resource is the time. It is not meaningful to measure the computation time on the basis of requrired seconds on a specific machine. This required time depend on:
 Input data
 Programming language
 Quality of conversion in bit instructions
 Computer processing unit speed
A good measure of efficiency should be independent of the used machine. It is important an measure teoric that considers the resolution method of the algorithm
Examples:
 Find the minimum of n numbers. Starting from the first number and comparing it with others à n comparisons.
 To order n numbers. We find a subset and find the mimum. I repeat by considering smaller and smaller subsets. à n + (n1) + (n2)+….+ 2 + 1 à n^{2} comparisons
So algorithm efficiency can be measured by a function of n variable n f(n).This function express the number of operations to make and it represents the computation complexity of the algorithm
If A and B are 2 algorithms to solve the same problem P and if f_{A}(n) and f_{B}(n) express the complexity of the 2 algorithms the A is better tha B if, by increasing n, f_{A}(n) <=f_{B}(n).
n=10  n=10000  n=1000000  
n^{2} operations  0,1 ms  100 s  10^{6} s 
n*log n op  23 μs  92 ms  13,8 s 
Table increasing time with n (1 operation in 10^{6} s)
One algorithm is polinomial if it needs, in the worst case an elementar number of operations:
f(n) = O(n^{d}) à polinomial
Kind of complexity:
log n > logaritmic complexity (n logn : to order numbers)
c1*n+c2 > linear complexity (n complexity: sequential order)
n2+n > quadratic complexity
nk +c3*n > polinomial complexity
2^{n}+n > exponential complexity (to be avoided!)
n  log_{2} n  n*log_{2}n  n^{2}  n^{3}  2^{n} 
2  1  2  4  8  4 
10  3,322  33,22  10^{2}  10^{3}  >10^{3} 
10^{2}  6.644  664.4  10^{4}  10^{6}  >>10^{25} 
10^{3}  9.966  9996.0  10^{6}  10^{9}  >>10^{250} 
10^{4}  13.287  1328.7  10^{8}  10^{12}  >>10^{2500} 
B. Evaluate the complexity of a problem
A problem P is polinomial (“easy”) if it exists a polinomial algorithm that gives the optimal solution (for instance minimal paths)
Kinds of problems:
 Decisions problems: Answers Yes/No (for instance.: Does it exist a pathway with a data lenght?)
 Search problem: find a solution (for instance: to find a pathway of lenght less than k)
 Enumeration problems: To count the solutions (for instance: how many pathways of lenght less than k are there?)
 Optimization problems: To find a solution respect a goal (for instance to find a pathway of minimal lenght)
For optimazion problems the best algorithms need a number of elementary operations that increases exponentially with the instance dimension (instance: specific case of the problem, the input dataset).
Example: In TSP the travel sales man must visit each of n towns exaclty once and go back to the starting point as soon as possible (shortest time). You must find a minimal cost circuit that visti exactly one each node. A circuit is Hamiltonian if it pass exactly once in each node. One all hamiltonian circuits are found, you choose the one with minimal cost.
This is a decision problem (answer yes/no): Does exist a hamiltonian circuit with minimal costs? If I ask if the lenght of that circuit is less than L, this is an optimization problem.
Complexity class P
A problem that can be solve in a polinomial time.
For this problem it exists an algorithm that allows me to answer yes or no to my problem once given the input data, with a polinomial time.
The TPS is of P class because in polinomial time I can verify if a sequence of nodes belongs to an hamiltonian circuit with length less than L.
Complexity class NP
This is the class of problems for which if you have a positive instance of that problem it is possible to support a certificate from which it is possible to verify in polinomial time that this instance is affermative.
To compare decisiona problems and to define the hardest the concept of polinomial reduction is introduced.
P1 and P2 are NP problem, P1 can be polinomial reduced to P2 if a P1 istance can be reformulated in polinomial time as a P2 instance and the instance of the P1 problem is affermative if and only if the instance of P2 problem is affermative. (the solution of the P2 problem can supply a solution of the P1 problem).
If P1 can be reduced to P2, it means that solving P2 also P1 can be solved.
Complexity class NPcomplete
A P1 problem is NPcomplete if it is of NP class and it exist a P2 problem also NP, in the manner that P2 can be polinomially reduced to P1.
If a problem NPcomplete P1 can be solved in polinomial time, then all NP problems could be solved. In other words P=NP (the P class will be the same of the NP class). Up to now this should be not possible.
Figure 7 Complexity classes
References
Agnetis A. . Appunti Introduttivi sulle classi di complessità. Dipartimento di Ingegneria dell’Informazione – Università di Siena.
Amaldi E. . Cenni di teoria della complessità computazionale. Fondamenti di Ricerca Operativa Politecnico di Milano.
Frigioni D. . Algoritmi e Strutture Dati – Analisi. Dipartimento di Ingegneria e scienze dell'informazione e matematica. Università degli Studi dell’Aquila.
Johnson D. S., Papadimitriou, C. H. (1992). Computational complexity. The Traveling salesman problem. A guided Tour of Combinatorial optimization, pp. 3785. Ed. Wiley.
Penzo W. . Complessità Computazionale. Department of Computer Science and Engineering. Faculty of Engineering  University of Bologna.
TSP, VRP e CVRP
The TSP: traveling salesman problem concern a the situation where you should visit a set of points by the shortest route. It si an optimizaton problem where we want to minimixe the total distance. You should find the Hamiltonian Circuit of minimal cost.
The application of this problem concern:
 Delivery planning to the clients
 The picking in automated warehouse
 Job scheduling in a machine with setup times/costs sequence dependent
 …
IL TSP is a NPhard problem and Effective and efficient algorithm are not known. Euristics are efficient by not effective algorithms.
Figure 8 TSP example
The Vehicle Routing Problem (VRP) extends TPS by including other factors:
 Capacity of used vehicules
 Timing and Time windows to reach the nodes
 Dinamic Routing: stop times and double passes
 Casualities and contigencies
VRP aim is to find the optimal routing, by including some constraints (times, capacities etc).
There are several types of VRP:
 Vehicle Routing Problem with Time Windows (VRPTW)
 Vehicle Routing Problem with PickUp and Delivery (VRPPD)
 Capacitated Vehicle Routing Problem (CVRP)
The objective is to find the optimal solution by reaching all the nodes within the constraints and with minimal cost. The problem is complex, so we use heuristics. These can be constructive (it builds the solution step by step each time increasing the solution of a node) or iterative (the algorithm goes to iteratively improve the complete set of solutions).
Finding the optimal solution is not a simple problem, therefore we resort to heuristics.
CLARKE – WRIGHT (1964)  SAVINGS MATRIX
We want to determine the optimal routing of a fleet of vehicles of different capacities from a distribution center. You want to allocate loads to the vehicles in order to obtain the minimum path length.
The heuristic under consideration is sequential, that is based on the progressive establishment of routes, namely the construction of a new route whenever any customer not served can become part of the route that is currently under construction.
At each step the current solution is given by a family T = {T_{1}, ... T_{q}} of disjoint oriented cycles (except for the deposit) such that:
 Each node belongs to a cycle
 The deposit belongs to all cycles
 The sum of the claims of outlets associated with a T_{h} cycle does not exceed the capacity Q_{h}
The starting solution is constituted by n1 cycles consist of the deposit and from a single point of sale
Figure 9 starting configuration
At each iteration the algorithm try to merge two routes in order to minimize the objective function, that represents the total distance.
Figure 10 Separated Routes
The merging of T_{h} and T_{k} creates the new tour T’={v_{1},v_{p}(h),…,v_{u}(h),v_{p}(k),…,v_{u}(k)}
Merging can be allowed only if it generates savings:
Figure 11 The new route
Solution procedures:
First of all the distance matrix is generated.
On the basis of DC and delivery points geographic coordinates, the algorithm creates a matrix D with dimensions (n+1) (n+1) with the distances between any possible couple between delivery points and DC..
The value of Dij represents the eucledian distance between clients i and j:
Afterwards the Savings matrix is build.
The saving s_{ij} is an arc between points (i,j) and it represents the savings achievable in the case points i and j belongs to the same route. Sij savings are :
s_{ij} = d_{1i} + d_{1j} – d_{ij}
The building of a new route starts by looking to the couple (i,j) of clients with maximum of savings in the matrix of Savings S. It client i belongs to route u while client j belongs to route v, they can be merged if the following constraints are satisfied:
then:
 The total of the delivered quantities in route u and v can not be greater than vehicule capacity cv;
 The sum distances of u and v, substracted by the savings s_{ij} must be less the maximum working time w_{t} of the vehicules.
If the above conditions are satisfied, points i and j are served and the R matrix of Routes is updated, ie, in correspondence of the u_{th} row, is added to the sequence of points belonging to the v_{th} row.
The algorithm proceeds by adding customers to the path u, until there are no more paths v able to satisfy the constraints. More specifically, it seeks the maximum saving from the end nodes of the path to all other nodes notserved. If the constraints are satisfied, the customer is added to the route corresponding to this maximum saving. If all customers are served, the phase of creation and extension of paths ending. If there are no clients are able to satisfy the constraints then path under consideration can not be extended anymore. We will create, in this case, new path, by trying again the maximum savings from the end nodes of the path to all other nodes in notserved and so on.
The case MATLAB resolution
As mentioned, the Clarke and Wright was implemented in Matlab (here).
In INPUT you need the following data:
 The number of the nodes n;
 Trucks with their capacity;
 Quantities to be delivered to the nodes;
 Matrix of distances.
References
Boccia, M. Problemi di Distribuzione (Vehicle Routing). Dipartimento di Ingegneria. Università del Sannio.
Chopra, S., Meindl, P., (2004). Supply Chain Management. Transportation in the Supply Chain. Chapter 14, pp. 411456.
Clarke, G., Wright, J. W. (1964). Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operation Research, Vol. 12 N. 4, pp. 568581.
Fisher, J. H. (2001). Transportation Management and Shipment Planning. Handbook of Industrial Engineering. Technology and Operations Management. Chapter 79, pp. 20542069.
Pesenti, R. (2001). Routing. Cenni di TSP e VRP. Department of Management. University Ca' Foscari Venezia.
Rand, G. K. (2009). The life and times of the Savings Method for Vehicle Routing Problems. ORiON, Vol. 25 N. 4, pp.125145.
The Traveling salesman problem. A guided Tour of Combinatorial optimization, pp. 3785. Ed. Wiley.