Problemi di routing e solver commerciali: panoramica di un caso studio

In questa tesi si analizzano i principali problemi di routing, che fanno capo al Vehicle Routing Problem. Maggiore approfondimento viene dedicato al Pick up and Delivery Problem, che costituisce la tipologia di problemi di routing più affrontata nell'azienda di riferimento. Dopo aver descritto le formulazioni di questi problemi, si analizza il problema reale, con le sue sfaccettature e differenze rispetto al problema descritto in letteratura. Dunque viene effettuato un approfondimento sul funzionamento dei solver per problemi di routing, prima in generale sugli algoritmi ALNS e poi nello specifico su quello utilizzato in azienda. Il corpo della tesi riguarda la descrizione di un altro solver, di tipo commerciale, del quale si andranno a valutare le prestazioni confrontandole con quello aziendale. Si parte dall'analisi dello script Python di default per la risoluzione di problemi di pick up and delivery adatto a elaborare istanze di letteratura, specificando le modalità di utilizzo del solver commerciale e descrivendo la forma e il contenuto delle istanze di letteratura. Dunque si approda all'adattamento dello script a istanze reali utilizzate effettivamente in azienda. Dopo aver descritto dettagliatamente ogni sezione dello script modificata, si va ad eseguire l'analisi dei risultati computazionali ottenuti. Nel caso delle istanze di letteratura, viene eseguito un confronto col solver aziendale basato sull'eventuale raggiungimento delle best known solutions o sul distacco percentuale da esse. Per i casi reali si analizzano direttamente le soluzioni ottenute, tenendo conto di una condizione migliorativa e una peggiorativa a cui è stato sottoposto il solver commerciale rispetto a quello aziendale.