Robust optimization approach for location-allocation problems under demand uncertainty

The Location-Allocation (LA) problem consists of locating a set of new facilities such that an optimal number of facilities have to be placed in an area of interest in order to satisfy the customer demand. Location-allocation problems are interested with: - location decisions: which facility to open and where to locate it; - allocation decisions: from which facility to serve a specific demand point. This problem occurs in many practical settings where facilities provide services such warehouses, distribution centers, communication centers, schools, hospitals, health care centers, and so on. Location and allocation decisions will strongly influence the service provided to the customers, which can be critical in the health care field. Indeed, in health care systems, the ability to adequately serve the population promptly can have a crucial impact on patient's health and medical outcomes. This is particularly true in life-threatening situations. For this reason, Optimization models have been adopted to find optimal solutions to these situations. Traditionally, LA models assume that the demand for service is deterministic. However, in many real life situations it is highly variable and stochasticity should not be neglected. Thus, it is fundamental to develop methodologies to support decision making in such challenging context. In this thesis we investigate the location-allocation problem when customer demand is subject to uncertainty. Two specific problems arising in the health care field are studied: - the Biomedical Samples Laboratories Network Problem, which describes the logistic issues related to the design, management and optimization of a network of clinical laboratories; - the Ambulance Relocation and Pre-assignment Problem, which considers the location of a fleet of ambulances in a city environment. We focus on a specific kind of model where each candidate site has not an opening cost and there are no assignment costs. Each candidate site can cover a subset of customers and has a given level of capacity. We assume that the demand of each customer is independent from the other ones and that it follows a symmetric but unknown probability distribution. Demand uncertainty is dealt with the Cardinality-Constrained robust optimization approach: it consists in considering a worst case scenario for each candidate site, among all those where at most Gamma demands simultaneously take their worst value. This technique is also known as cardinality-constrained method. Among the others, such an approach seems suitable because of allowing a trade-off between the level of robustness and the cost of the solution, and an easy implementation that can be understood by clinicians and planners. To the best of our knowledge, this work represents the first example of application of the Cardinality-Constrained approach to a location-allocation problem with uncertain data in the health care field. Furthermore, the considered models require the use of particular techniques. Uncertain parameters are in fact present in more than a set of constraints or in the objective functions: this requires a new approach that we will explain in the following. We test and compare the robust models on a group of realistic instances provided by the Laval University of Quebec City, Canada, based on real life data. The robustness of the solutions is also evaluated through a scenario testing. Results show that our models solutions are better than the ones of the deterministic model in term of feasibility, when tested on real life scenarios. A final discussion on the price of robustness points out that the resulting increase in the objective function is widely affordable.

Il problema di Location-Allocation (LA) consiste nel determinare la posizione di un insieme di nuove strutture, tale da soddisfare la domanda dei clienti di una determinata area. Problemi di location-allocation sono interessati da: - decisioni di location: quale struttura aprire e dove posizionarla; - decisioni di allocation: da quale struttura servire un certo punto di domanda. Questo problema si verifica in molti contesti pratici dove le strutture forniscono servizi, come magazzini, centri di distribuzione, centri di comunicazione, scuole, opsedali, servizi sanitari, e così via. Per questo motivo, modelli di Ottimizzazione sono stati adottati per trovare soluzioni ottimali a queste situazioni. In genere, i modelli LA assumono che la domanda per un certo servizio sia deterministica. Tuttavia, in molte situazioni reali essa è altamente variabile e la sua stocasticità non deve essere trascurata. Pertanto, è fondamentale sviluppare metodologie per supportare il processo decisionale in questo difficile contesto. In questa tesi si indaga il problema Location-Allocation quando la domanda è soggetta a incertezza. Due problemi specifici sono studiati: - il Biomedical Samples Laboratories Network, che descrive i problemi logistici legati alla progettazione, gestione e ottimizzazione di una rete di laboratori clinici; - l'Ambulance Relocation and Pre-assignment Problem, che considera il posizionamento di una flotta di ambulanze in un ambiente urbano. Ci concentriamo su uno specifico tipo di modello in cui ogni sito candidato non ha un costo di apertura e non ci sono costi di assegnamento. Ogni sito candidato può comprendere un sottogruppo di clienti e ha un dato livello di capacità. Si assume che la domanda di ogni cliente è indipendente dalle altre e che segua una distribuzione di probabilità simmetrica ma sconosciuta. L'incertezza della domanda è trattata con un approccio di ottimizzazione robusta introdotto da Bertsimas e Sim: consiste nel considerare lo scenario peggiore per ogni sito candidato, tra tutti quelli in cui al massimo Gamma domande assumono contemporaneamente il loro valore peggiore. Questa tecnica è anche conosciuto come metodo di vincolo di cardinalità (Cardinality-Constrained in inglese). Al confronto di altri, tale approccio sembra adatto poiché rappresenta un compromesso tra il livello di robustezza e il costo della soluzione, e la sua facile implementazione può essere compreso da medici e progettisti. Al meglio delle nostre conoscenze, questo lavoro rappresenta il primo esempio di applicazione dell'approccio di Bertsimas e Sim a un problema di location-allocation con dati incerti in campo sanitario. Inoltre, i modelli considerati richiedono l'uso di tecniche particolari. I parametri incerti sono infatti presenti in più di un insieme di vincoli o nelle funzioni obiettivo: ciò richiede un nuovo approccio che spiegheremo nel seguito. I modelli robusti sviluppati sono testati su un gruppo di istanze realistiche fornite dall'Università Laval di Quebec City, Canada, sulla base di dati di situazioni reali. La robustezza delle soluzioni viene valutata anche attraverso test su vari scenari. I risultati mostrano che le soluzioni dei nostri modelli sono migliori di quelle del modello deterministico in termini di feasibility, quando sono testate su scenari di vita reale. Una discussione finale sul prezzo della robustezza sottolinea che il conseguente aumento del valore della funzione obiettivo è ampiamente ragionevole.