Riassunto analitico
Il problema affrontato in questo studio riguarda la raccolta efficiente di campioni biologici (come provette di sangue) dai centri di raccolta e la loro consegna ai laboratori di analisi associati utilizzando veicoli dedicati.
Il problema rappresenta una variante complessa del problema di multiple pickup and delivery con time windows interdipendenti. I componenti principali sono veicoli, centri di raccolta e laboratori di analisi. I veicoli iniziano e terminano i loro turni in un deposito. Ogni centro di raccolta ha i propri orari di apertura e tempi di servizio per i ritiri, con i campioni che devono essere consegnati al laboratorio designato entro un tempo specificato per evitare il deterioramento.
Anche il processo di consegna nei laboratori ha tempi di servizio fissi. Il tempo di deterioramento impone finestre temporali interdipendenti. Più nel dettaglio, ogni centro di raccolta viene visitato più volte durante la giornata, e la finestra temporale associata a ciascuna visita dipende dall'orario in cui è stata effettuata la visita precedente.
Un numero considerevole di articoli è stato proposto nella letteratura su questo argomento. Doerner et al. [1] hanno studiato un problema molto simile ma hanno considerato un solo laboratorio per i test, invece di più laboratori come nel nostro caso. Hanno proposto un modello e diversi metodi di soluzione per ottimizzare il ritiro dei campioni con finestre temporali dipendenti dalle politiche di spedizione.
In questo studio, sviluppiamo un modello matematico utilizzando una formulazione multi-commodity insieme a un algoritmo euristico mirato a minimizzare i costi totali. Entrambe le metodologie sono state ampiamente testate dal punto di vista computazionale e applicate a casi reali per una validazione pratica.
Il problema è classificabile come multi-passage Vehicle Routing Problem for pickup and delivery with multiple interdependent time windows for perishable goods (mVRPPDmiTWfPG), Vehicle Routong Problem multi-passaggio per raccolta e consegna con finestre temporali multiple interdipendenti per beni deperibili.
1. Doerner, K.F., Gronalt, M., Hartl, R.F., Kiechle, G., Reimann, M.: Exact and heuristic algorithms for the vehicle routing problem with multiple interdependent time windows. Computers & Operations Research 35(9), 3034–3048 (2008)
|
Abstract
The problem addressed in this study involves efficiently collecting biological samples (such as blood vials) from collection centers and delivering them to associated analysis laboratories using dedicated vehicles.
The problem is a challenging variant of the multi-pickup and delivery problem with interdependent time windows. Its key components include vehicles, collection centers, and analysis laboratories. Vehicles start and end their shifts at a depot. Each collection center has its own working hours and service times for pickups, with samples needing to be delivered to the designated laboratory within a specified time to prevent degradation.
The delivery process at laboratories also has fixed service times. The degradation time imposes inter-dependent time windows. In more detail, each collection center is visited multiple times during the day, and the time window associated with a visit depends on the time at which the previous visit was performed.
A considerable number of articles have been proposed in the literature about this topic. Doerner et al.[1] studied a very similar problem but considered just a single laboratory for the tests, instead of multiple laboratories as in our case. They proposed a model and different solution methods to optimize the pickup of samples with time windows dependent on dispatching policies.
In this study, we develop a mathematical model utilizing a multi-commodity formulation alongside a heuristic algorithm aimed at minimizing total costs. Both methodologies are then extensively computationally tested and applied to real-world instances for practical validation.
The problem can be classified as a multi-passage Vehicle Routing Problem for pickup and delivery with multiple interdependent time windows for perishable goods (mVRPPDmiTWfPG).
1. Doerner, K.F., Gronalt, M., Hartl, R.F., Kiechle, G., Reimann, M.: Exact and heuristic algorithms for the vehicle routing problem with multiple interdependent time windows. Computers & Operations Research 35(9), 3034–3048 (2008)
|
