Ottimizzazione di un sistema collaborativo di consegna dell'ultimo miglio : modelli ed euristiche

E-commerce is spreading more and more, both in Italy and abroad, leading to an increase in the amount of goods that are transported within the cities. In this context, the problem of the Last Mile Vehicles, which involves determining an efficient way to deliver goods to recipients, becomes increasingly important. In particular, in this thesis is studied the application of the problem in areas with strong accessibility constraints, such as for example the “area C” in Milan. The dissertation identifies two sub-problems: one, in the long term, about the dimensioning of the fleet of last mile vehicles to be used, and the other concerning operational choices, such as the daily routing of these vehicles. The choices to be made concern aspects such as the unloading of goods from long haul transporters in urban satellite platforms, their assignment to final vehicles and the determination of routes, taking into account various objectives, including eco-sustainability and minimization of the duration of routes. For the two sub-problems, we propose a mixed integer linear programming model and a randomized greedy algorithm with local search. The quality of the solutions provided by the heuristic is evaluated on instances of 50 and 100 products, and are presented and discussed also results on real instances based on the data of deliveries in the C area of Milan provided by a transport company.

L’e-commerce si sta diffondendo sempre più, sia in Italia che all’estero, aumentando quindi la quantità di merci che sono trasportate all’interno delle città. In tale contesto, il problema della Consegna dell’Ultimo Miglio, che riguarda la determinazione di un modo efficiente per consegnare le merci ai destinatari, diventa sempre più importante. In questa tesi si studia l’applicazione del problema in zone con forti vincoli di accessibilità, come ad esempio l’area C di Milano. In particolare, vengono definiti due sotto-problemi: uno, a lungo termine, di dimensionamento della flotta di ultimo miglio da utilizzare, ed un altro operativo, riguardante l’instradamento quotidiano di tali veicoli. Le scelte da compiere riguardano aspetti quali lo scarico delle merci dai veicoli di lungo raggio in piazzole satelliti urbane, il loro assegnamento ai veicoli finali e la determinazione delle rotte di quest’ultimi, tenendo conto di vari obiettivi, tra cui l’ecosostenibilità e la minimizzazione della durata dei percorsi. Per i due sotto-problemi sono proposti dei modelli di programmazione lineare mista intera e degli algoritmi euristici di tipo greedy randomizzato con ricerca locale. La qualità delle soluzioni fornite dall’euristica è valutata su istanze da 50 e 100 prodotti, e sono poi presentati e discussi risultati su istanze reali basate su dati di consegne nell’area C di Milano forniti da una società di trasporti.