Rich Vehicle Routing Problems: models, algorithms and applications.

The Vehicle Routing Problem (VRP) is one of the most central transportation problems in Operations Research. Introduced by Dantzing et al.(1959), the problem aims to find the optimal routes for a fleet of vehicles to serve customers. The traditional version of the VRP and its variants have been extensively studied in the academic literature. However, recent years have witnessed a surge in the application of optimization models by businesses and organizations. This shift in focus aims to address real-world complexities by introducing novel features and constraints. The family of these extended problems is called Rich VRP (RVRPs). RVRPs extend the traditional academic formulations of VRPs by incorporating problem-specific constraints that closely mirror decisions made at both tactical and operational levels in practical settings. This thesis delves into the study of RVRPs in healthcare and logistics. We provide efficient mathematical model formulations, exact and heuristic resolution approaches, and a comprehensive analysis of the computational results. Our research addresses critical issues within the Nurse Routing Problems (NRPs) in healthcare. Our goal is to enhance logistic outcomes for healthcare organizations while simultaneously improving the working conditions of healthcare providers and the quality of care delivered to patients. To achieve this, we introduce the concept of fairness into NRPs, along with quality-enhancing constraints such as nurse-patient consistency and time window specifications. Our analysis begins by examining several fairness metrics, considering patients and nurses within a Single-Objective Single-Period NRP framework. We provide a set of objective functions that can be interchanged to assess the interaction between different metrics and their cost implications. Next, we extend our investigation on fairness by inserting new measures and providing a Multi-Objective formulation of the previous NRP. Employing a lexicographic approach, we simultaneously consider multiple objective functions, selecting triplets of functions to represent the interests of each stakeholder (hospital, nurses, and patients). Furthermore, we present a Dynamic Multi-Period NRP with Consistency Constraints in which the temporal distribution of patient requests is unknown. Objective of the problem is to decide nurse-patient assignments over several days based on newly revealed daily requests. We propose two approaches: a pure myopic dynamic method, which lacks future event information, and a scenario-based optimization method that leverages historical data to forecast future developments. We propose two essential problem formulations in the logistics domain: the Last Mile Logistic Delivery Problem with Parcel Lockers (LMDP-LS) and the Attended Home Delivery Problem with Recovery Options (AHDP-RO). In the LMDP-LS, we evaluate the environmental impact of parcel lockers when the ecological footprint of consumers is taken into account. The problem aims to derive meaningful insights into the environmental impact of both the company and the consumers in the switch from a door-to-door delivery service to a locker-based one. In the AHDP-RO, we also model and solve the traditional attended home delivery service, which mandates the customer's presence at home to avoid delivery failures. Specifically, we model the probability of finding the customer at home through availability profiles, plotting the probability of successful deliveries during the working day. We introduce the possibility for couriers to take recovery actions when customers are unavailable, with associated penalties included in the objective function. The overarching objective is to plan daily courier routes to minimize routing and penalty costs. Throughout our research, we provide the results of small-size instances solved to optimality and we employ the Adaptive Large Neighborhood Search (ALNS) meta-heuristic to obtain good quality solutions for large-size ones.

I Vehicle Routing Problems (VRPs) sono una branca di problemi centrali nella Ricerca Operativa. Introdotto da Dantzig et al (1959), il problema mira a trovare le rotte ottimali per una flotta di veicoli per servire i clienti. Negli ultimi anni si è assistito a un incremento nell'applicazione dei modelli di ottimizzazione da parte di aziende e organizzazioni. Questo cambiamento di focus mira ad affrontare le complessità del mondo reale introducendo caratteristiche e vincoli innovativi. La famiglia di questi problemi estesi è chiamata Rich VRP (RVRPs). I RVRPs estendono le formulazioni tradizionali dei VRP incorporando vincoli specifici del problema che riflettono decisioni prese sia a livello tattico che operativo in contesti pratici. Questa tesi approfondisce lo studio dei RVRPs nel settore sanitario e logistico. Forniamo formulazioni di modelli matematici efficienti, approcci di risoluzione esatti ed euristici, e un'analisi comprensiva dei risultati computazionali. La nostra ricerca affronta questioni critiche all'interno dei Nurse Routing Problems (NRPs) nel settore sanitario. Il nostro obiettivo è migliorare i risultati logistici per le organizzazioni sanitarie migliorando contemporaneamente le condizioni di lavoro dei fornitori di assistenza e la qualità dell'assistenza fornita, Per raggiungere questo scopo, introduciamo il concetto di equità negli NRPs, insieme a vincoli che migliorano la qualità come la coerenza infermiere-paziente e le specifiche delle finestre temporali. La nostra analisi inizia esaminando diverse metriche di equità, fornendo un insieme di funzioni obiettivo che possono essere scambiate per valutare l'interazione tra diverse metriche e le loro implicazioni sui costi. Successivamente, estendiamo la nostra indagine sull'equità inserendo nuove misure e fornendo una formulazione Multi-Obiettivo del precedente NRP in cui selezioniamo triplette di funzioni per rappresentare gli interessi di ogni stakeholder. Inoltre, presentiamo un NRP Dinamico Multi-Periodo con Consistenza in cui la distribuzione temporale delle richieste dei pazienti è sconosciuta. L'obiettivo del problema è decidere le assegnazioni infermiere-paziente per diversi giorni basandosi su richieste rivelate giornalmente. Proponiamo due approcci: un metodo dinamico puramente miope, che manca di informazioni sugli eventi futuri, e un metodo di ottimizzazione basato su scenari che sfrutta i dati storici per prevedere sviluppi futuri. Nel dominio logistico proponiamo il Last Mile Delivery Problem with Locker Selection (LMDP-LS) e l’Attended Home Delivery Problem with Recovery Options (AHDP-RO). Nel LMDP-LS, valutiamo l'impatto ambientale dei locker per pacchi tenendo conto dell'impronta ecologica dei consumatori. Nell'AHDP-RO, modelliamo e risolviamo anche il servizio tradizionale di consegna a domicilio assistita, modellando la probabilità di trovare il cliente a casa attraverso profili di disponibilità e tracciando la probabilità di consegne riuscite durante la giornata lavorativa. Introduciamo la possibilità per i corrieri di intraprendere azioni di recupero quando i clienti sono indisponibili, con penalità associate incluse nella funzione obiettivo. L'obiettivo generale è pianificare le rotte giornaliere dei corrieri per minimizzare i costi di routing e di penalità. Nel corso della nostra ricerca, forniamo i risultati di istanze di piccole dimensioni risolte all'ottimalità e impieghiamo la meta-euristica di Adaptive Large Neighborhood Search (ALNS) per ottenere soluzioni di buona qualità per quelle di grandi dimensioni.