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

Freight transportation industry is characterized by several decisional problems that operations managers have to cope with. Not only the routes planning must be realized before their execution, but also other types of decisions must be taken, in order to answer events that may dynamically occur during operations, as for instance road network congestion or vehicle failures. Each decision can involve different aspects: for instance, the price negotiation of a just-in-time order should take into consideration the current routes status and planning. Off-the-shelf decision support software, although able to independently support the decision makers in each area, tend to keep tasks compartmentalized. Trans-Cel, a small trucking company in Padova (Italy), has a Research and Development branch developing a cloud-based platform, called Chainment, able to host different decision support tools that can communicate through a data sharing system. These tools rely on an algorithmic engine that includes a routing optimization algorithm and artificial intelligence systems. In particular, the routing problem combines express couriers requirements, generally studied in urban contexts, with routes and vehicle features typical of medium- and long-haul trips, showing interesting characteristics that are worth of study in the Operation Research field. In this thesis, we focus on the design of an optimization algorithm able to provide a solution to a Vehicle Routing Problem (VRP) inspired by the Trans-Cel scenario, that we name Express Pickup and Delivery in freight Trucking problem (EPDT). The classical VRP definition includes a set of customers and a fleet of vehicles and aims to define a set of routes such that all customers are visited exactly once while minimizing the overall distance traveled. In the scientific literature, the basic definition of the problem has been generalized in order to consider additional attributes, often rising from real-world scenarios, as for instance capacity of vehicles, time windows and orders with both pickup and delivery operations. Often, in real-world cases, decision makers must simultaneously deal with a large number of attributes, thus defining a class of routing problems called Multi-Attribute VRP (MAVRP), which includes EPDT. The thesis proposes a meta-heuristic algorithm for the solution of EPDT, with the aim of embedding it in the algorithmic engine of Chainment. In order to comply with the platform requirements, the algorithm is designed so that a solution is returned within few seconds. The solution method we propose consists of a two-level heuristic: at the first level, a Tabu Search algorithm hybridized with a Variable Neighborhood Descent explores the order-to-vehicle assignments, while, at the second level, it makes use of a Local Search to determine the sequence of customers visited and obtain an evaluation of routes. The algorithm efficiency is enhanced by the use of a granular exploration, by procedures for fast evaluation of solutions in the neighborhoods, and parallel implementation of specific algorithmic components. These elements are adapted to the specific attributes of EPDT and represent some of the thesis contributions. The improvement in computational times have been validated by the experimental results, verifying the desired requirements for the platform integration. The quality of the solutions obtained with the proposed meta-heuristic algorithm has been assessed both on the field, by comparison with Trans-Cel operations managers, and through bounds obtained with mathematical programming methods. To this purpose, the thesis proposes an Integer Linear Programming formulation for EPDT and a solution method for its continuous relaxation based on Column Generation. In particular, the thesis presents new pricing procedures suitable for the specific EPDT attributes. The available bounds show optimality or near-optimality of solutions provided by the heuristic algorithm for real instances. Moreover, the algorithm has been tested on literature benchmarks related to the Pickup and Delivery Problem with Time Windows (PDPTW), providing solutions that are competitive with the state-of-the-art. The thesis also proposes a preliminary study of new approaches for vehicle routing problems in dynamic contexts. In particular, the thesis explores the possibility of taking advantage from the availability of historical data on orders by means of anticipatory strategies. The first strategy is based on clustering methods that are applied to the orders to define space-time points that aggregate the information on future demand. A second strategy is based on the concept of accessibility, as defined in the discrete choice theory and urban logistic, to represent the route capability of intercepting future orders. The heuristic algorithm proposed for EPDT has been integrated in the algorithmic engine of the Chainment platform at Trans-Cel. The thesis describes integration and the adaptation of the proposed optimization algorithms for a proper interaction with the different modules in the operational context handled by the platform, as, for instance, initial routes planning, reacting to dynamic events or order price negotiation.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