Euristiche di ottimizzazione guidate da tecniche di Machine Learning

This thesis will explore the use of neural networks for the prediction of moves to be used in heuristics for the optimisation of electric vehicle routing. Neural networks are a class of machine learning algorithms that have proven to be very effective in a wide range of applications, including classification, regression and content generation. Furthermore, in the field of optimisation, neural networks can be used to support heuristics, i.e. approximate methods for finding optimal solutions to problems where the exact solution is too expensive or impossible to calculate. The combination of neural networks and optimisation heuristics allows complex problems to be solved efficiently and effectively. In this thesis, various neural network architectures will be evaluated in order to find a valid method for classifying whether a certain move improves or worsens a certain objective function. Being able to appropriately classify whether a move increases or decreases the value of an objective function makes it possible to avoid having to test all possible combinations, restricting the testing field to only those moves that increase the objective function, the algorithm's moves having previously been classified as 'good' or 'bad'. The idea is to exploit classification techniques to support heuristics to optimise the delivery of goods using electric vehicles. The latter start from a depot and have to reach customers via charging stations.

In questa tesi verrà esplorato l'utilizzo di reti neurali per la predizione delle mosse da utilizzare in euristiche per l'ottimizzazione del routing di veicoli elettrici. Le reti neurali sono una classe di algoritmi di apprendimento automatico che hanno dimostrato di essere molto efficaci in una vasta gamma di applicazioni, tra cui la classificazione, la regressione e la generazione di contenuti. Inoltre, nel campo dell'ottimizzazione, le reti neurali possono essere utilizzate per supportare le euristiche, ovvero metodi approssimativi per trovare soluzioni ottimali in problemi in cui la soluzione esatta è troppo costosa o impossibile da calcolare. La combinazione di reti neurali ed euristiche di ottimizzazione permette di risolvere problemi complessi in maniera efficiente ed efficace. Nella tesi verranno valutate diverse architetture di reti neurali per trovare un metodo valido per classificare se una certa mossa migliora o peggiora una certa funzione obiettivo. Riuscire a classificare in maniera opportuna se una mossa accresce o riduce il valore di una funzione obiettivo permette di evitare di dover provare tutte le possibili combinazioni, restringendo il campo di test alle sole mosse che incrementano la funzione obiettivo, essendo le mosse dell'algoritmo precedentemente classificate come "buone" o "cattive". L'idea è quella di sfruttare le tecniche di classificazione per sostenere l'euristica, affinché si ottimizzi la consegna di merce che avviene utilizzando dei veicoli elettrici. Questi ultimi partono da un deposito e devono raggiungere dei clienti, passando per delle stazioni di ricarica.