Analisi e sviluppo di algoritmi per il Multi-trip Vehicle Routing Problem applicato alla raccolta di rifiuti ingombranti

Abstract

In questa tesi sono stati sviluppati due algoritmi per il problema di instradamento di veicoli multi-trip e con time windows, applicati alla raccolta di rifiuti ingombranti. I due algoritmi, sviluppati in linguaggio C#, hanno l'obiettivo di trovare i percorsi per servire tutti i clienti in modo tale da minimizzare la distanza totale percorsa e il tempo totale di servizio. Il primo utilizza le API della libreria Google OR-Tools e implementa una logica per risolvere la variante multi-trip che non è gestita dalla libreria. Il secondo implementa la metaeuristica di Simulated Annealing: genera delle soluzioni iniziali che rispettino le finestre temporali e le capacità dei veicoli, seleziona la soluzione migliore e a partire da questa applica la logica della Simulated Annealing. Per testare e confrontare gli algoritmi sono state generate delle istanze di 8, 12, 20, 40, 60, 80 e 100 nodi. Queste sono state salvate in file Excel che vengono letti dai due programmi. Inoltre, come interfaccia utente, è stato realizzato un Excel Add-in tramite il quale possono essere inseriti i dati di input necessari all'esecuzione delle due euristiche e visualizzati i percorsi che i vari veicoli devono effettuare.

In this thesis two algorithms for the multi-trip vehicle routing problem with time windows applied to bulky waste collection have been developed. The goal of the two algorithms is to find the paths to serve a set of customers minimizing the total distance travelled and the total service time. The first one uses the Google OR-Tools APIs and implements a logic to solve the multi-trip variant that is not managed by OR-Tools. The second one implements the metaheuristic of Simulated Annealing: it generates some initial solutions that respect the time windows and the vehicles capacities, selects the best solution and applies the Simulated Annealing’s logic. To test and compare algorithms, some instances of 8, 12, 20, 40, 60, 80 and 100 nodes have been generated. An Excel Add-in has been implemented as user interface through which the input data can be entered and results, obtained by the execution of the programs, can be displayed.