Sviluppo di un algoritmo per un problema di vehicle routing multi-trip con pickup e delivery, finestre temporali e soste opzionali applicato al trasporto urbano di passeggeri

Abstract

In questo elaborato di tesi è stato modellato un problema di VRPPDTW Multi-D&T con pause di sosta opzionale, tramite lo sviluppo di una metauristica basata su ALNS. Questo si è dimostrato essere un buon metodo di risoluzione delle problematiche nel contesto reale considerato, caratterizzato dal considerare le normative nell'ambito del trasporto pubblico che richiedono che gli autisti facciano delle pause dopo un tempo prolungato di guida. Sono stati tutti i metodi utilizzati al fine di ottenere una completa metauristica che risolvesse un problema reale e che potrebbe essere utilizzato per un progetto realistico in corso. L'idea di utilizzo della ALNS è motivato dai suoi eccellenti risultati su problemi di routing complessi. La differenza principale di questo studio rispetto ad altri esistenti consiste nella gestione delle pause che effettua ciascun autista tramite l'utilizzo di predefinite zone di sosta. Inoltre viene tenuto conto che devono sostenere dei tempi massimi di guida e dei tempi di sosta prima di riprendere la guida del veicolo. Inoltre in questo elaborato vengono definiti dei nuovi metodi di inserimento e delle aree di sosta nelle rotte. Un altro importante fattore di questo studio è la gestione delle finestre temporali: ogni cliente che vuole prenotare la propria richiesta, avrà a disposizione un orario di scelta e due orari di tolleranza minimo e massimo in cui deve essere prelevato e depositato. Per valutare l'algoritmo, è stato utilizzato un set di benchmark realizzato da un generatore di dati casuali derivanti dalla configurazione di un set di parametri definiti. Grazie a questi set siamo riusciti a fare delle sperimentazioni ed a confrontare le varie istanze sia sullo stesso numero che su un numero diverso di richieste.

In this thesis a problem of VRPPDTW Multi-D&T with optional pauses has been modeled through the development of a metauristics based on ALNS. Has proved that it is a good method to resolve problems in the real context considered, characterized by considering the regulations in public transport sector where drivers must take breaks after a prolonged time of driving. All methods are used in order to obtain a complete metaheuristic that can solve a real problem which could be used for a realistic project in progress. The idea of ​​using ALNS is motivated by its excellent results on complex routing problems. The main difference of this study compared to other existing ones, consists in the management of the breaks that each driver carries out through the use of predefined rest areas. It is also taken into account that they must sustain maximum driving times and minimum parking times before resuming driving the vehicle. Furthermore, in this paper, new methods of insertion and parking areas in the routes are defined. Another important factor of this study is the management of the time windows: each customer who wants to book his/her request, will have a choice time and a minimum and a maximum tolerance times in which it must be withdrawn and deposited. To evaluate the algorithm, a set of benchmarks made by a random data generator resulting from the configuration of a set of defined parameters was used. Thanks to these sets we are able to experiment and to compare various instances on the same and different number of requests.