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

The aim of this Ph.D. thesis is to address the optimization of dial-a-ride transportation systems, where each customer specifies the service as an origin (A) and a destination (B), together with the related time windows. To optimize such a system means to find a set of routes, each assigned to a vehicle, at minimum routing cost, in order to satisfy all the customer requests under time windows, precedence and pairing constraints, i.e., A and B belong to the same route and A always precedes B. The problem has been already addressed in the literature as both a Pickup and Delivery Problem with Time Windows (PDPTW) and a Dial-a-Ride Problem (DARP). After a literature review focused on both the modelling and the methodological aspects, a Mixed Integer Linear Programming formulation has been examined and particular emphasis has been devoted to the meta-heuristics, among which a Genetic Algorithm (GA). In particular, an algorithm for tuning the input parameters of GA, based on a racing technique (F-Race), has been designed. The computational results, carried out on benchmark instances, have shown that GA, combined with the F-Race, in several cases, reaches the Best Known. Moreover, a bi-objective DARP has been proposed minimizing, at the same time, the Total Waiting Time of the vehicles arriving at customers before the left side of their time window and the Maximum total Ride Time. The problem has been solved through a two-step approach: in the first step, a set of feasible routes has been generated by using both the GA and a Tabu embedded Simulated Annealing meta-heuristic. This set has been used in the second step for defining a bi-objective set partitioning formulation with additional constraints, solved through an epsilon-constraint method. Numerical results have also been aimed to compare the proposed approach with the Weighted Sum method and they have shown that it provides the decision makers with a better approximation of the Pareto front.

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.