Algoritmi meta-euristici per l'ottimizzazione dei sistemi di trasporto a chiamata

Scopo di questa tesi di dottorato è l’ottimizzazione dei sistemi di trasporto a chiamata in cui, ogni cliente, specifica un luogo di partenza (A) e uno di arrivo (B) con le rispettive finestre temporali. Si deve pertanto trovare un insieme di rotte, a costo minimo, ciascuna assegnata a un veicolo, per soddisfare le richieste sotto vincoli temporali, di precedenza ed accoppiamento: A precede B ed entrambi appartengono alla stessa rotta. Il problema è stato studiato come Pickup and Delivery Problem with Time Windows (PDPTW) e come Dial-a-Ride Problem (DARP). Dopo una ricerca bibliografica sugli aspetti modellistici e metodologici, si è esaminata una formulazione di Programmazione Lineare Intera Mista e si è approfondita l’analisi delle meta-euristiche, tra cui quella di un Algoritmo Genetico (AG). Con riferimento all’AG, si è definito e implementato un algoritmo per il tuning dei suoi parametri d’input, basandosi su una tecnica di Racing (F-RACE). I risultati computazionali, condotti su istanze di benchmark, hanno mostrato che l’AG, opportunamente settato, in diversi casi, raggiunge il Best Known. Si è proposta, inoltre, una versione del DARP bi-obiettivo per minimizzare il tempo totale di attesa dei veicoli presso clienti raggiungi in anticipo rispetto alla loro finestra temporale e il tempo di viaggio della rotta più lunga. Per tale problema, si è, quindi, progettato un approccio risolutivo a due stadi: dapprima, usando l’AG e un’euristica ibrida (Tabu Search- Simulated Annealing), si è generato un insieme di rotte ammissibili, fornito in input, successivamente, a una formulazione matematica bi-obiettivo di set-partitioning con vincoli aggiuntivi, risolta mediante l’approccio epsilon-vincolato. La bontà di questo approccio risolutivo è stata valutata confrontando le prestazioni con quelle del metodo della somma pesata. Gli esperimenti numerici hanno mostrato che l’approccio proposto è in grado di fornire una buona approssimazione della frontiera paretiana