Two local search heuristic approaches for solving the biomedical sample transportation problem. A case study based on Quebec healthcare system

Biomedical tests play a crucial role in helping physicians to make accurate diagnoses. To perform these tests, thousands of samples are transported daily from healthcare facilities where they are collected to laboratories where they are analyzed. In this thesis we consider the particular case of the province of Quebec, Canada, where the Ministry of Health and Social Services aims of improving the efficiency of samples’ transportation system. Inspired by this context, we study the Biomedical Sample Transportation Problem, a variant of the Vehicle Routing Problem with time windows, which is challenging due to the perishable nature of transported samples and the interdependence between pickups. We first adapt a linear programming formulation for the Biomedical Sample Transportation Problem. Then, in order to efficiently solve it in case of real size instances, we develop two heuristic approaches. The first one, deeply developed in the thesis, is a matheuristic approach, consisting of a Clustering based Decomposition coupled with a variant of the Variable Neighborhood Search algorithm. The decomposition is based on a spatio-temporal clustering method that takes into account both the travel times between centers and their collection periods’ compatibility. Then, a Fix-and-Optimize Variable Neighborhood Search is applied to improve the solution: exploring areas of different sizes, the algorithm identifies, if any, solutions that are better than the current one and it moves in the direction of the best improvement. The second one, preliminary investigated, is the adaptation to our specific problem of a Genetic Algorithm based on the evolutionary ideas of natural selection and genetics: in order to solve an optimization problem, it simulates the survival of the solutions that fit better the problem itself and that, generation after generation, result to be better suited to their environment. The performance of the proposed methods is assessed over a large number of realistic instances based on the laboratories network in the province of Quebec. Results show good quality solutions and the capability of the two heuristics to solve real size instances in a reasonable time.

I test biomedici svolgono un ruolo cruciale nell’aiutare i medici a fare diagnosi accurate. Per effettuare tali test, migliaia di campioni sono trasportati ogni giorno dalle strutture sanitarie dove vengono prelevati ai laboratori di analisi. In questa tesi consideriamo il caso particolare della provincia di Quebec, Canada, dove il Ministero della Sanità e dei Servizi Sociali ha l’obiettivo di migliorare l’efficienza del sistema di trasporto di campioni biomedici. Ispirati da questo contesto, affrontiamo il Biomedical Sample Transportation Problem, una variante del Vehicle Routing Problem con finestre temporali, resa complicata dalla deperibilità dei campioni trasportati e dall'interdipendenza tra le visite. Per prima cosa adattiamo la formulazione di un modello lineare per il Biomedical Sample Transportation Problem. Per risolverlo efficientemente in caso di istanze reali, sviluppiamo due euristiche. La prima, testata ampiamente nel corso della tesi, è una mateuristica composta da una Clustering based Decomposition seguita da una variante dell'algoritmo di Variable Neighborhood Search. La fase di decomposizione si basa su un metodo di clustering spazio-temporale che considera sia la distanza spaziale tra i centri che la loro compatibilità negli orari di raccolta. In seguito, per migliorare ulteriormente la soluzione, applichiamo una Fix-and-Optimize VariableNeighborhood Search: esplorando aree di diversa dimensione, l’algoritmo identifica, se presenti, soluzioni migliori rispetto alla corrente, muovendosi nella direzione di massima crescita. La seconda, per la quale proponiamo qualche test preliminare, è l’adattamento di un Algoritmo Genetico basato sull’idea evoluzionistica di selezione naturale: per risolvere un problema di ottimizzazione, l’algoritmo simula la sopravvivenza, generazione dopo generazione, delle soluzioni che si adattano meglio al problema. Le performance dei metodi proposti sono testate su un ampio numero di istanze reali basate sulla rete di laboratori e strutture sanitarie nella provincia di Quebec. I risultati mostrano soluzioni di buona qualità e la capacità dei metodi euristici analizzati di risolvere istanze reali in tempi ragionevoli.