Solving a Multi-Attribute Vehicle Routing Problem in the freight delivery industry

L'industria del trasporto merci è caratterizzata da diversi problemi decisionali che devono essere affrontati dagli operatori al traffico. Non solo si deve realizzare la pianificazione delle rotte in anticipo, ma devono prendersi anche altri tipi di decisioni, in modo da far fronte ad eventi che possono dinamicamente presentarsi durante le operazioni, come ad esempio congestioni dovute al traffico o un guasto ad un veicolo. Ciascuna decisione può coinvolgere diversi aspetti: ad esempio, la negoziazione del prezzo di un ordine just-in-time dovrebbe tenere in considerazione lo stato corrente delle rotte e la loro pianificazione. I software di supporto alle decisioni disponibili sul mercato, seppur capaci di supportare il decisore in ciascuna area, tendono a mantenere i processi separati. Trans-Cel, una piccola azienda di trasporto merci a Padova (Italia), ha un ramo di Ricerca e Sviluppo dedicato alla creazione di una piattaforma cloud, chiamata Chainment, che contenga diversi sistemi di supporto alle decisioni comunicanti fra loro attraverso un sistema di condivisione dati. Questi sistemi si affidano a un motore algoritmico che include un ottimizzatore per il routing dei veicoli e sistemi di intelligenza artificiale. In particolare, il problema di routing unisce le esigenze delle consegne espresse, studiate solitamente in contesti urbani, a caratteristiche dei veicoli e delle rotte tipiche di trasporti su distanze medio-lunghe, presentando caratteristiche peculiari e di interesse nel contesto della Ricerca Operativa. In questa tesi ci concentriamo sullo sviluppo di un algoritmo di ottimizzazione capace di restituire una soluzione ad un nuovo Vehicle Routing Problem (VRP) ispirato dallo scenario di Trans-Cel, e che chiamiamo Express Pickup and Delivery in freight Trucking problem (EPDT). La formulazione classica del VRP prevede un insieme di clienti e una flotta di mezzi e vuole definire un insieme di rotte tali che tutti i clienti siano visitati esattamente una volta e allo stesso tempo la distanza complessiva delle rotte sia minimizzata. Nella letteratura scientifica, la definizione base del problema è stata generalizzata in modo da considerare ulteriori attributi che spesso nascono dagli scenari reali, come ad esempio la capacità dei mezzi, finestre temporali e ordini che prevedono operazioni di carico e scarico. Spesso, nei casi reali, i decisori devono affrontare problemi con molti attributi da considerare simultaneamente, dando origine a una classe di problemi di routing chiamata Multi-Attribute VRP (MAVRP), che include il problema EPDT. La tesi propone un algoritmo meta-euristico per la soluzione di EPDT, con lo scopo di integrarlo nel motore algoritmico di Chainment. Ai fini di essere compatibile con i requisiti della piattaforma, l'algoritmo è ideato in maniera che la soluzione venga restituita in pochi secondi. Il metodo proposto consiste di un'euristica a due livelli: nel primo livello, un algoritmo Tabu Search ibridato con una Variable Neighborhood Descent esplora le assegnazioni degli ordini ai veicoli, mentre il secondo livello fa uso di una Local Search per determinare la sequenza di clienti visitati e ottenere una valutazione delle rotte. L'efficienza dell'algoritmo è migliorata dall'uso di filtri nell'esplorazione dei vicinati, da procedure per la valutazione rapida delle soluzioni, e dall'implementazione parallela di alcune componenti algoritmiche. Questi elementi sono adattati agli specifici attributi di EPDT e sono tra i contributi della tesi. Il miglioramento in termini di tempi di calcolo è stato validato dai risultati sperimentali, che verificano i requisiti desiderati per l'integrazione nella piattaforma. La qualità delle soluzioni ottenute dall'algoritmo meta-euristico proposto è stata valutato sia sul campo, attraverso il confronto con operatori presso Trans-Cel, sia attraverso i bound ottenuti con metodi di programmazione matematica. A tale scopo, la tesi propone una formulazione di programmazione lineare intera per EPDT e un metodo di soluzione del suo rilassamento continuo basato su generazione di colonne. In particolare, la tesi presenta delle nuove procedure di pricing adatte ai diversi attributi di EPDT. I bound disponibili mostrano l'ottimalità o la quasi ottimalità delle soluzioni fornite dall'algoritmo euristico per le istanze reali. Inoltre, l'algoritmo è stato testato su benchmark di letteratura riguardanti il problema Pickup and Delivery Problem with Time Windows (PDPTW), mostrando soluzioni competitive con lo stato dell'arte. La tesi include anche uno studio preliminare di nuovi approcci per problemi di vehicle routing in contesti dinamici. In particolare, la tesi esplora la possibilità di trarre vantaggio dalla disponibilità di dati storici sugli ordini attraverso la predisposizione di opportune strategie anticipatorie (anticipatory algorithms). Una prima strategia si basa su metodi di clustering degli ordini per definire dei punti spazio-temporali che riassumono le informazioni sulla domanda futura. Una seconda strategia si basa sul concetto di accessibilità, come definito nella teoria della scelta discreta e della logistica territoriale, per rappresentare la capacità di una rotta di intercettare ordini futuri. L'algoritmo euristico proposto per EPDT è stato integrato nel motore algoritmico della piattaforma Chainment di Trans-Cel. La tesi descrive le modalità di integrazione e gli adattamenti apportati agli algoritmi di ottimizzazione per una corretta interazione con i diversi moduli nel contesto delle operazioni gestite dalla piattaforma, come, ad esempio, la pianificazione iniziale delle rotte dei veicoli, la risposta a eventi dinamici o la contrattazione dei prezzi degli ordini.