www.impianti.dii.unipg.it

 

 

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à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 + (n-1) + (n-2)+….+ 2 + 1 à n2 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 fA(n) and fB(n) express the complexity of the 2 algorithms the A is better tha B if, by increasing n, fA(n) <=fB(n). 

 

  n=10 n=10000 n=1000000
n2 operations 0,1 ms 100 s 106 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(nd)   à 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

 2n+n ---> exponential complexity (to be avoided!)

 

n log2 n n*log2n n2 n3 2n
2 1 2 4 8 4
10 3,322 33,22 102 103 >103
102 6.644 664.4 104 106 >>1025
103 9.966 9996.0 106 109 >>10250
104 13.287 1328.7 108 1012 >>102500

 


 

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 NP-complete

A P1 problem is NP-complete 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 NP-complete 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. 37-85. 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 NP-hard 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 Pick-Up 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 = {T1, ... Tq} 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 Th cycle does not exceed the capacity Qh

The starting solution is constituted by n-1 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 Th and Tk creates the new tour T’={v1,vp(h),…,vu(h),vp(k),…,vu(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 sij 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 :

sij = d1i + d1j – dij

 

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 sij must be less the maximum working time wt 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 uth row, is added to the sequence of points belonging to the vth 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 not-served. 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 not-served 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. 411-456. 

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. 568-581. 

Fisher, J. H. (2001). Transportation Management and Shipment Planning. Handbook of Industrial Engineering. Technology and Operations Management. Chapter 79, pp. 2054-2069. 

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.125-145. 

The Traveling salesman problem. A guided Tour of Combinatorial optimization, pp. 37-85. Ed. Wiley.