Ottimizzazione della composizione della flotta e delle rotte nella distribuzione della carta stampata

In this thesis work an innovative fleet optimization problem has been introduced and solved in the field of printed paper distribution inspired by the case of ADP srl, a company operating in the distribution logistics sector and specialized in the delivery of editorial publications. The optimization problem consists in minimizing the cost associated with the dependent drivers and common carriers involved in the distribution. For this purpose, two different Operational Research approaches were used: the first exact and the second heuristic. In the exact approach, an ad hoc model has been formulated which, in compliance with demand constraints, time windows and geographical positions of the newsstands served and vehicle capacity, provides the solution to the problem at a minimum cost. Since the problem addressed belongs to the class of Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), it is of the NP-Hard type, that can be solved in relatively long computing times. Therefore, to solve the problem in a reasonable time it was necessary to develop also a heuristic approach, based on the cluster-first, route-second method. This method involves an initial phase of grouping (clustering) of the newsstands to be served in limited areas, followed by a second phase of routing, that is, the definition of the routes of each cluster using a model of the Travel Salesman Problem (TSP) type. The heuristic thus defined, selects the most convenient alternative between dependent transporter and common carrier for each route, providing a sub-optimal solution, in a short time. Both methods, implemented in AMPL and solved through the CPLEX optimization software, were applied and compared in the case study of ADP srl.

Nel presente elaborato di tesi è stato introdotto e risolto un innovativo problema di ottimizzazione della flotta nell’ambito della distribuzione della carta stampata ispirato al caso di ADP srl, azienda operante nel settore della logistica distributiva e specializzata nella consegna di pubblicazioni editoriali. Il problema di ottimizzazione consiste nella minimizzazione del costo associato ai trasportatori dipendenti e padroncini coinvolti nella distribuzione. A tale scopo sono stati utilizzati due approcci diversi della Ricerca Operativa: il primo esatto e il secondo euristico. Nell’approccio esatto è stato formulato un modello ad hoc che, nel rispetto dei vincoli di domanda, delle finestre temporali e delle posizioni geografiche delle edicole servite e di capacità dei veicoli, fornisce la soluzione a costo minimo del problema. Poiché il problema affrontato appartiene alla classe dei Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), esso è di tipo NP-Difficile, cioè risolvibile in tempi di calcolo relativamente lunghi. Perciò per risolvere il problema in tempi ragionevoli è stato necessario sviluppare anche con un approccio di tipo euristico, basato sul metodo cluster-first, route-second. Tale metodo prevede una fase iniziale di raggruppamento (clustering) delle edicole da servire in aree limitate, seguita da una seconda fase di routing, ossia di definizione delle rotte di ogni cluster tramite un modello del tipo Travel Salesman Problem (TSP). L’euristica così definita, seleziona per ogni rotta l’alternativa più conveniente tra trasportatore dipendente e padroncino, fornendo una soluzione sub-ottima, in tempi brevi. Entrambi i metodi, implementati in AMPL e risolti tramite il software di ottimizzazione CPLEX, sono stati applicati e confrontati nel caso studio di ADP srl.