Algoritmi esatti ed euristici per problemi di vehicle routing, scheduling, e localizzazione

Questa tesi di dottorato è incentrata sullo sviluppo di algoritmi esatti ed euristici per risolvere problemi logistici relativi al vehicle routing, allo scheduling e alla localizzazione di servizi. La tesi è strutturata in un breve capitolo introduttivo, cinque capitoli di ricerca, e una breve conclusione. La prima parte della ricerca è focalizzata su un nuovo problema di bin packing con vincoli di precedenza che generalizza alcuni problemi della letteratura, tra cui il problema di bilanciamento delle linee di montaggio. Per risolvere il problema, proponiamo un semplice e efficace algoritmo di Iterated Local Search (ILS) che integra in modo innovativo procedure costruttive e strutture di vicinato per guidare la ricerca alle soluzioni ottime locali. La seconda parte è dedicata al problema di localizzazione di p centri con vincoli di capacità, che consiste nella selezione di p impianti da un gruppo di candidati per servire un numero di clienti, al fine di minimizzare la distanza massima tra un cliente e l'impianto a cui è associato e nel rispetto di vincoli di capacità. Il problema è risolto mediante algoritmi di ricerca che, iterativamente, cercano la distanza ottimale risolvendo sotto-problemi più semplici ad ogni iterazione. Inoltre, presentiamo diverse formulazioni matematiche per i sotto-problemi e li miglioriamo attraverso varie disuguaglianze valide, tra cui una basata sulla disgiunzione 0-1 e sulla soluzione dei problemi di subset sum. La terza parte presenta un problema di instradamento di veicoli basato su un problema pratico di distribuzione affrontato da un’azienda italiana responsabile della consegna di farmaci alle aziende sanitarie. Questo problema si caratterizza per la grande quantità di dettagli e vincoli, tra cui le consegne periodiche (multi-period), l'esistenza di depositi multipli (di due tipi diversi), l'incompatibilità tra alcuni veicoli ed alcuni clienti, la presenza di finestre temporali ed altri. Il problema è risolto mediante algoritmi euristici basati sul ILS e su large neighborhood search. Esperimenti computazionali sono eseguiti su istanze realistiche fornite dall'azienda, nonché su istanze artificiali, per dimostrare l'efficienza degli algoritmi proposti. Le ultime due ricerche sviluppate nella tesi sono incentrate sul pollution-routing problem (PRP), che è una variante del problema d'instradamento di veicoli che considera la minimizzazione delle emissioni di CO2 nella funzione obiettivo. Il primo studio risolve il PRP con un algoritmo di ottimizzazione dei tempi di partenza e delle velocità per minimizzare il costo di un percorso fisso. Inoltre, è presentata una prova dell'ottimalità per l'algoritmo proposto. Gli esperimenti computazionali condotti su istanze della letteratura mostrano il contributo della flessibilità nella scelta dei tempi di partenza sulla riduzione delle emissioni di CO2. Nel secondo contributo sul PRP, viene affrontata una versione bi-obiettivo del problema, in cui due obiettivi contrastanti, ovvero i costi di viaggio e le emissioni di CO2, sono minimizzati mediante un metodo euristico di ricerca locale di Pareto. Esperimenti computazionali sulle istanze di riferimento esistenti mostrano che l'approccio proposto porta a risultati migliori rispetto a quelli ottenuti con metodi multi-obiettivo standard. In conclusione, la tesi mostra come moderni algoritmi, sia esatti che euristici, possano essere usati per ottimizzare in modo efficiente problemi di produzione e di logistica che appaiono in ambiti diversi.