Optimisation algorithms for a food surplus collection problem.

L’obiettivo di questa tesi è quello di approfondire il Vehicle Routing Problem (VRP). Il Vehicle Routing Problem è una generalizzazione del problema del commesso viaggiatore. Nel VRP, l’obiettivo è quello di trovare l’insieme ottimale di percorsi per una flotta di veicoli che trasportano merci o servizi da varie località. Questa tesi presenta un problema di raccolta di eccedenza alimentare proposto da una organizzazione di beneficenza che si chiama FoodCycle e opera a Bath (Regno Unito) nella chiesa di Santa Maria a Bath. L’obiettivo è quello di raccogliere una quantità di cibo necessario per soddisfare la richiesta settimanale dell’ente di beneficenza. La qualità degli ingredienti richiesti è stata classificata in due gruppi: ingredienti freschi e ingredienti di qualità accettabile. Il problema modellato in questa tesi è considerato come un problema di instradamento di veicoli statici e la sua funzione obiettivo è composta di due parti che sono rispettivamente l’obiettivo primario e l’obiettivo secondario. L’obiettivo primario è più importante dell’obiettivo secondario. La prima parte della funzione obiettivo massimizza il numero totale di ingredienti, menzionati prima, e il numero di ingredienti freschi raccolti. L’ultimo termine della funzione obiettivo è composta dalla variabile di penalità per gli ingredienti che non vengono rinvenuti nei supermercati. L’obiettivo principale di questa tesi è quindi, quello di definire un modello matematico e implementare un algoritmo esatto scritto in C ++ con l’utilizzo della libreria CPLEX. Il codice implementato è stato sperimentalmente testato e valutato risolvendo una istanza reale.