Biomedical sample transportation problem : an iterative time decomposition scheme with fix and optimize techniques

In the medical-health context, in order to correctly define the clinical picture of each patient, the collection and analysis of biological material is crucial. However, not all sample collection centers are adequately equipped with the necessary supplies. Therefore, biological material has to be transported daily from the sampling laboratories to a central analysis laboratory. This is the case of the medical biology laboratories of the province of Québec, Canada, which are considered in this thesis. In particular, the Ministry of Health and Social Services has developed the Optilab project, created to cope with the proliferation of autonomous laboratory entities which has created some difficulties with regard to the development and organization of this branch. In fact, the transport procedure, if not adequately controlled by a central organization, can lead to the deterioration of the biological material, that becomes unusable, and also to high costs. Given a network of sampling laboratories, the procedure of planning the pickup routes can be translated into a Vehicle Routing Problem, notably a Biomedical Sample Transportation Problem, due to the specific nature of the transported material. The problem is also characterized by time windows in which collection visits to medical centers can be performed. Moreover, the perishable nature of the transported material on one hand makes it necessary in many cases to make more than a single visit to each center and on the other hand it constrains the duration of the itineraries, making the visits interdependent. Finally, in our work, we consider a flexibility in the opening hours of medical collection centers. This partly adds flexibility to the problem, but it also increases its complexity and, to the best of our knowledge, no work in the literature considers a transportation network with interdependent multi pickups, also optimizing the opening hours of the collection centers. In this thesis, firstly, the problem of our interest was adapted to a linear formulation for the Biomedical Sample Transportation Problem. Using the solver CPLEX, the formulation was applied to 50 instances of the Canadian province. Given the long computational times, a metauristic algorithm was then developed to obtain solutions in shorter times. Specifically, a time decomposition approach was used, in order to obtain a solution of the problem by decomposing it into smaller and easier to solve sub-problems. In particular, the approach was applied iteratively, alternating different temporal decomposition criteria. Four techniques have been developed to divide the problem: two of these have parametric nature, while the other two are based on the analysis of solutions found during the algorithm. The goal is to build sub-problems as much as possible dependent on the characteristics of each specific instance. Furthermore, since the sub-problems are linked by a sequential nature, the use of Fix and Optimize techniques has been introduced within the iterative scheme. This is done with the dual purpose of speeding up the optimization process and exploring different spaces of the problem feasibility region. The method, tested on the real instances of the Canadian province, produces solutions in a reasonable time, whose quality is on average comparable to the one of the solutions of the exact formulation after hours of computation.

Nel contesto medico sanitario, al fine di definire correttamente il quadro clinico di ogni paziente risulta determinante la raccolta e l'analisi di materiale biologico. Tuttavia, non tutti i centri di prelievo sono adeguatamente provvisti delle necessarie attrezzature. Pertanto, si deve trasportare ogni giorno materiale biologico dai laboratori di prelievo a un laboratorio centrale di analisi. È questo il caso dei laboratori di biologia medicale della provincia di Québec, Canada, che vengono considerati in questa tesi. In particolare, il Ministero della Sanità e dei Servizi Sociali canadesi ha sviluppato il progetto Optilab, nato per far fronte alla proliferazione di enti di laboratorio autonomi che ha creato alcune difficoltà per quanto riguarda lo sviluppo e l’organizzazione di questo settore. Infatti, la procedura di trasporto, se non adeguatamente controllata da un’organizzazione centrale, può portare al deperimento del materiale biologico che diventa così inutilizzabile e anche ad alti costi. Data una rete di laboratori di prelievo, la pianificazione del trasporto si traduce in un Vehicle Routing Problem, in particolare un Biomedical Sample Transportation Problem, data la specifica natura del materiale trasportato. Il problema è inoltre caratterizzato da finestre temporali in cui è possibile effettuare le visite di raccolta ai centri medici. Per di più, la natura deperibile del materiale trasportato da un lato rende in molti casi necessario effettuare più di una singola visita presso ogni centro e dall’altro vincola la durata degli itinerari, rendendo le visite tra loro interdipendenti. Infine, nel nostro lavoro, considereremo una flessibilità di apertura dei centri medici di prelievo. Questo in parte aggiunge elasticità al problema, dall’altra ne aumenta la complessità e, al meglio delle nostre conoscenze, nessun lavoro in letteratura considera una rete di trasporto con multi-visite interdipendenti ottimizzando anche gli orari di apertura dei centri di prelievo. In questa tesi, inizialmente, si è adattato il problema di nostro interesse a una formulazione lineare per il Biomedical Sample Transportation Problem. Tramite il solver CPLEX, la formulazione è stata applicata a cinquanta istanze della provincia canadese. Dati i lunghi tempi computazionali, si è poi sviluppato un algoritmo di metauristica per ottenere soluzioni in tempi più brevi. Nel farlo, si è usato un approccio di decomposizione temporale che fosse capace di risolvere il problema decomponendolo in sotto-problemi più piccoli e di più facile risoluzione. In particolare, l’approccio è stato applicato iterativamente, alternando diversi criteri di decomposizione temporale. Si sono sviluppate quattro tecniche per suddividere il problema: due di queste sono di natura parametrica, mentre altre due si basano sull’analisi di soluzioni trovate durante l’algoritmo. L’obiettivo è quello di costruire sotto-problemi in modo più possibile dipendente dalle caratteristiche di ogni specifica istanza. Inoltre, dato che i sotto-problemi sono legati da una natura sequenziale, all’interno dello schema iterativo, si è introdotto l’utilizzo di tecniche di Fix and Optimize. Questo è fatto con il duplice scopo di rendere più veloce il processo di ottimizzazione e di esplorare spazi diversi della regione di ammissibilità del problema. Il metodo, testato sulle istanze reali della provincia canadese, produce soluzioni in tempi ragionevoli, la cui qualità è mediamente equiparabile a quella delle soluzioni della formulazione esatta dopo ore di computazione.