Indice
Sommario 3
1 Descrizione del problema 5
1.1 Introduzione al servizio di Home Care . . . 5
1.1.1 Classi cazione delle tipologie di ADI . . . 7
1.1.2 Fasi del processo assistenziale . . . 7
1.2 Descrizione del problema . . . 9
1.3 Modelli proposti . . . 11 1.3.1 Dati di input . . . 11 1.3.2 Variabili . . . 11 1.3.3 Vincoli . . . 12 1.3.4 Vincoli di routing . . . 13 1.3.5 Funzione obiettivo . . . 13
1.3.6 Funzione obiettivo alternativa . . . 14
1.4 Formulazione alternativa . . . 15
2 Rassegna della letteratura 17 2.1 Panoramica generale . . . 17
2.2 A. Trautsamwieser, M. Gronalt, P. Hirsch. Securing home health care in times of natural disasters [1] . . 20
2.3 M. S. Rasmussen, T. Justesen, A.Dohn, J. Larsen. The Home Care Crew Scheduling Problem: Preference-Based Visit Clustering and Temporal Dependencies [2] . . . 27
2.4 Y. Kergosien, C. Lenté, J. Billaut. Home health care problem - An extended multiple Traveling Salesman Problem [12] . . . 30
2.5 B. Elbenani, J.A. Ferland, V. Gascon. Mathematical Programming Approach for Routing Home Ca-re Nurses [10] . . . 33
2.6 S. Bertels, T. Fahle. A hybrid setup for a hybrid scenario: combining heuristics for the home health care problem [7] . . . 36
2.7 D. Bredström, M. Rönnqvist.
Combined vehicle routing and scheduling with temporal
pre-cedence and synchronization constraints [8] . . . 41
2.8 P. Eveborn, P. Flisberg, M. Rönnqvist. LAPS CARE - an operational system for sta planning of home care [11] . . . 44
2.9 Ulteriori lavori in ambito Home Care . . . 47
2.10 Tabella riassuntiva . . . 54
3 Indagine sperimentale 55 3.1 Piano della sperimentazione . . . 55
3.2 Generazione delle istanze . . . 57
3.3 Esecuzione di CPLEX . . . 61
3.4 Presentazione delle prove . . . 63
3.5 Prove al crescere del numero dei pazienti . . . 64
3.6 Prove al crescere del numero di visite palliative . . . 67
3.7 Prove su richieste generate a consuntivo . . . 69
3.7.1 Pattern generati con procedura random . . . 69
3.7.2 Pattern generati a consuntivo . . . 71
3.7.3 Prove al crescere della percentuale di visite di skill 2 . 73 3.8 Considerazioni . . . 75
A CPLEX Concert Technology 76 A.1 Concert Technology utilizzando C++ . . . 76
A.2 Struttura di un'applicazione Concert Technology con C++ . . 78
A.3 Terminazione di CPLEX . . . 79
B Sviluppo 80 B.1 Struttura del codice . . . 80
Conclusioni 83
Ringraziamenti 84
Sommario
In questo lavoro di tesi viene analizzato il problema della schedulazione e del routing degli operatori, qui considerati come infermieri ordinari e specia-lizzati, in contesti di Home Care o Assistenza Domicilare Integrata (ADI), come viene de nita nel nostro Paese.
I modelli proposti presentano formulazioni originali, mai studiate nora, ba-sate su orizzonti temporali di una settimana. Le visite vengono ordinate secondo pattern preimpostati secondo determinati piani di cura. Gli obietti-vi mirano a bilanciare il carico di lavoro degli operatori coinvolti. Le distanze di percorrenza dei tragitti vengono calcolate tramite le Google Distance API. Il Capitolo 1 presenta una descrizione accurata del problema studiato, for-nendo un quadro sull'organizzazione del contesto di Home Care relativo al territorio italiano e illustrando i modelli di Programmazione Lineare Intera[31] proposti.
Nel Capitolo 2 è mostrata una dettagliata panoramica sullo stato attua-le degli studi nell'ambito dell'Home Care, evidenziandone attua-le caratteristiche principali. È stato selezionato un insieme di lavori rilevanti di cui vengono presentati i modelli proposti e le relative sperimentazioni.
Il Capitolo 3 è relativo alle sperimentazioni intraprese per valutare l'an-damento dei modelli alla luce di istanze reali o generate casualmente alla base di dati realistici. Viene descritto l'ambiente di lavoro illustrando le caratteristiche del solver CPLEX ed il suo utilizzo.
È presente una descrizione della struttura organizzativa di uno dei mag-giori provider di Home Care italiani, di cui sono stati forniti gentilmente alcuni dati. Alla base di tali dati viene descritta in dettaglio la procedura di generazione delle istanze. In base alle istazne generate vengono quindi lanciate alcune prove allo scopo di mostrare il comportamento del solver re-lativamente a diverse con gurazioni dei dati in input.
In Appendice A vengono mostrate le caratteristiche della Concert Technolo-gy di C++, che sono state utilizzate per poter utilizzare CPLEX via C++.
In ne in Appendice B è presentata una breve descrizione del codice svilup-pato per la generazione dei modelli relativi alle istanze ed avviare su di esse il solver.
Capitolo 1
Descrizione del problema
1.1 Introduzione al servizio di Home Care
Secondo la Seconda Assemblea Mondiale delle Nazioni Unite sull'Invecchia-mento, tenutasi a Madrid nell'Aprile 2002, l'Italia è collocata al secondo posto, dopo il Giappone, tra i paesi più longevi al mondo. La percentuale di over 60 è stata stimata essere circa il 24,5%, con la tendenza ad aumentare con il passare del tempo.
Per far fronte a questa continua crescita, e dunque all'aumento di pato-logie legate all'età che essa comporta, non si può fare a damento alle sole strutture ospedaliere presenti nel nostro Paese. Esse non possono garantire i posti letto e le risorse umane per soddisfare tutte le necessità. Inoltre gli an-ziani, oltre a dover sostenere situazioni economiche di un certo peso, devono fare i conti con un allontanamento dall'ambiente familiare.
Sono state pertanto intraprese azioni come il potenziamento delle strut-ture residenziali o forme alternative di attività socio-assistenziali che possano portare anche vantaggi di natura economica. A tale scopo l'Italia, come tan-ti altri paesi industrializzatan-ti, sta sviluppando servizi di Home Care che si stanno man mano espandendo su tutto il territorio nazionale.
L'Home Care, o più comunemente in Italiano Assistenza Domiciliare Inte-grata (ADI), è una forma di assistenza rivolta a soddisfare le esigenze degli anziani, dei disabili e dei pazienti aetti da malattie cronico-degenerative parzialmente, totalmente, temporaneamente o permanentemente non auto-su cienti, aventi necessità di un'assistenza continuativa, che può variare da interventi di tipo sociale (pulizia dell'appartamento, invio di pasti caldi, supporto psicologico, etc) ad interventi socio-sanitari (attività riabilitative, assistenza infermieristica, etc).
Il suo obiettivo é quello di erogare un servizio di buona qualità, lasciando al proprio domicilio l'ammalato, consentendogli di rimanere il più a lungo possibile all'interno del suo ambiente di vita domestico e diminuendo
note-volmente, in questo modo, anche i costi dei ricoveri ospedalieri.
Generalmente si accede all'Assistenza Domiciliare Integrata attraverso una segnalazione al Centro di Assistenza Domiciliare dell'Azienda Sanitaria Lo-cale di appartenenza, da parte del medico di base o del sanitario del reparto ospedaliero di dimissione del paziente. A seconda delle necessità, verranno stabiliti gli interventi domiciliari da garantire all'utente che si trova in stato di bisogno. Il servizio è gratuito e di solito viene erogato per almeno 5 giorni la settimana.
Il portale www.socialinfo.it fornisce informazioni sull'ADI in Italia, e ne divide l'erogazione dei servizi in tre livelli, secondo un diverso impiego delle risorse, che siano umane o materiali:
• Primo livello Assistenza destinata a persone parzialmente non au-tosu cienti o a rischio di emarginazione, che richiedono interventi di sostegno psico-sociale o di cura della persona (fornitura pasti, lavaggio biancheria, igiene personale etc).
• Secondo livello Assistenza di natura sanitaria. Ne usufruisco-no persone usufruisco-non autosu cienti o di recente dimissione ospedaliera che necessitano di prestazioni infermieristiche, mediche o riabilitative. • Terzo livello Si tratta di una fusione dei due livelli precedenti e
riguarda le situazioni più complesse dell'ADI.
Il terzo livello è il più oneroso, per i provider, in quanto può richiedere risorse anche superiori alla somma delle risorse utilizzate dagli altri due li-velli per la necessità di coordinare persone con competenze molto diverse.
1.1.1 Classi cazione delle tipologie di ADI
Analogamente vengono delineate anche delle categorie secondo cui suddivi-dere i pazienti in base alle loro patologie e necessità:
• Convalescenza da patologie acute e riabilitazione Generalmen-te per questa tipologia di pazienti il servizio di ADI viene attivato in seguito a dimissioni ospedaliere protette. Lo scopo è quello di far sì che il paziente riacquisti autonomia nel proprio ambiente familiare. • Assistenza per patologie croniche gravi e cure polmonari
Per questa tipologia di pazienti è prevista una lunga permanenza nel sistema con un'alta intensità di cure. L'obiettivo del servizio è quello di evitare ricoveri in strutture sanitarie residenziali.
• Cure palliative I pazienti appartenenti a questa categoria sono in genere malati terminali. Il personale di assistenza deve possedere un adeguato livello di specializzazione. Tale servizio viene fornito allo scopo di permettere ai malati di trascorrere gli ultimi mesi di vita a contatto con la propria famiglia.
• Assistenza per patologie croniche non gravi Questa categoria è caratterizzata da visite da eettuare con bassa frequenza per un lungo periodo di tempo. Lo scopo è quello di prevenire il peggioramento delle condizioni di salute.
• Assistenza domestica generica I pazienti classi cati in base a que-sta tipologia non necessitano di cure mediche, ma di servizi assistenziali generalmente di breve durata.
In Tabella 1.1 si riassumono le caratteristiche delle categorie sopra citate.
1.1.2 Fasi del processo assistenziale
Il servizio di Home Care segue normalmente dei passi prede niti per la presa in carico di un paziente. Tali passi vengono illustrati brevemente nel seguente elenco:
• Segnalazione del paziente Normalmente un paziente è segnalato ad un sistema di ADI da parte del medico di medicina generale o dagli ospedali nel periodo immediatamente successivo alla dimissione da un ricovero. Anche i privati possono comunque fare richiesta diretta del servizio.
• Valutazione preliminare del bisogno Si basa sulla documenta-zione del paziente fornita al momento della domanda di ammissione e su interviste telefoniche ai pazienti o ai loro familiari.
Tipologia di bisogno Durata stimata
del servizio Intensitàservizio del Personale impiegato Convalescenza da
patologie acute e riabilitazione
Medio/lunga Alta Medici specialisti,
infermieri Assistenza per
pato-logie croniche gravi e cure polmonari
Lunga Alta Medici specialisti,
infermieri
Cure palliative Media Alta Medici specialisti
Assistenza per pa-tologie croniche non gravi
Lunga Media Infermieri
Assistenza
domesti-ca generidomesti-ca Breve Bassa Infermieri
Tabella 1.1: Classi cazione delle tipologie di servizi di ADI
• Valutazione approfondita del paziente Viene eettuata in se-guito a visite sul paziente e colloqui con i familiari. In base ai riscontri vengono decise le gure professionali coinvolte .
• Presa in carico e de nizione del Piano di Assistenza Indivi-duale Una volta decisa l'ammissione del paziente viene stablilito il piano di cura. Si piani ca il numero di visite mensili, si stima la durata della cura e l'assegnazione delle visite alle gure professionali coinvolte. In questa fase vengono de niti anche gli obiettivi e i referenti.
• Veri ca dei risultati della cura Avviene secondo riunioni, sta-bilite ad intervalli regolari, tra il personale curante e quello dedicato al coordinamento. Si stabilisce se il piano di cura deve essere mante-nuto o modi cato, in modo da soddisfare dinamicamente i bisogni del paziente.
• Conclusione dell'intervento Avviene con il raggiungimento degli obiettivi assistenziali, con il passaggio ad un diverso livello assisten-ziale o con il decesso del paziente. Può prevedere anche assistenza ai familiari come il supporto da parte di uno psicologo in caso di decesso.
1.2 Descrizione del problema
Per presentare il problema oggetto di studio è opportuno introdurre il proble-ma di ottimizzazione conosciuto in letteratura come Vehicle Routing Problem (VRP)[19], posto alla base del contesto del problema studiato, del quale il problema studiato costituisce una generalizzazione.
Una tipica applicazione del problema è quella della distribuzione di beni ad un insieme di clienti, da parte di un insieme di veicoli, localizzati in uno o più depositi, in una rete stradale.
La soluzione di un problema di tipo VRP è composta da un insieme di tour, uno per veicolo, che iniziano e niscono nel deposito. Nel caso siano previsti più depositi i tour iniziano e niscono nel deposito al quale è associato il veicolo.
La rete stradale è generalmente descritta attraverso un grafo completo, i cui archi rappresentano le strade e i nodi le locazioni dei clienti. Gli archi possono essere orientati o non orientati, la scelta dipende dalla speci ca implementazione. Ad essi è associato un costo, che tipicamente rappresenta il tempo di percorrenza dell'arco.
Il problema è a sua volta una generalizzazione del Traveling Salesman Problem (TSP)[19], in cui il numero di viaggiatori, cioè i veicoli, può essere maggiore di uno.
Possono essere associate al problema diverse caratteristiche, controllate da opportuni vincoli, per far fronte alle diverse necessità dei problemi spe-ci ci. Le caratteristiche più comuni, condivise da gran parte dei modelli utilizzati in letteratura, sono l'utilizzo di nestre temporali (time windows) e il rispetto delle ore lavorative contrattuali. Le nestre temporali possono essere associate sia ai veicoli che ai clienti e indicano il limite inferiore e superiore della porzione di tempo in cui il veicolo può arrivare dal cliente.
Anche la funzione obiettivo può presentare delle varianti, generalmente si tende a minimizzare i tempi di percorrenza ma può anche essere richiesto un bilanciamento dei carichi di lavoro o minimizzare le eventuali penalità causate dal mancato soddisfacimento di alcuni vincoli.
Il problema studiato, in particolare, estende una variante nota in lette-ratura come Skill VRP[20]. Tale variante è utilizzata in contesti in cui degli operatori devono eettuare degli interventi alle locazioni dei clienti per cui può essere richiesto un determinato livello di quali ca (skill).
Ciascun operatore avrà assegnato un valore di skill di tipo intero in base alle proprie competenze. Ad ogni richiesta da parte dei clienti è associato un valore indicante la skill necessaria per essere soddisfatta. Solo gli operatori con un valore di skill maggiore o uguale al valore della richiesta possono transitare e quindi operare sul nodo in cui essa è richiesta.
Nel seguente problema viene presentato il problema dello scheduling e del routing degli operatori (infermieri ordinari o specializzati) in un contesto di Home Care.
I pazienti da visitare sono visti come nodi di un grafo completo G=(N, A), a cui può accedere un solo operatore per volta. In base al piano di cura sta-bilito per ciascun paziente le visite richieste possono essere di tipo palliativo o non palliativo. Non tutti gli operatori sono abilitati ad eettuare tutte le visite. Ogni operatore, per poter visitare un paziente, necessita di un ade-guato livello di quali ca (skill) richiesto dal paziente, altrimenti non viene assegnato. A tale scopo a ciascuna visita è associato un valore, 1 o 2, che indica il livello di skill necessario. Il tour di ogni operatore deve iniziare e terminare in un nodo origine, assunto essere il nodo 0, corrispondente non ad un paziente, ma alla sede del provider di Home Care.
La piani cazione viene eettuata considerando un orizzonte temporale set-timanale, festivi esclusi, e per ogni giornata lavorativa viene rispettata la durata massima delle ore di lavoro, variabile per ogni operatore, nel caso ad esempio di operatori part time o che impieghino altre ore di lavoro in maniera diversa.
Le richieste dei pazienti sono modellate come vettori a due componenti, che indicano il numero di richieste settimanali di ogni paziente j per tipo di visi-ta (palliative e non). Per schedulare visi-tali richieste nell'arco della settimana, il modello proposto utilizza pattern a 5 componenti, corrispondenti ai giorni lavorativi della settimana. Ogni componente è a valori discreti (0,1 e 2) e indica se è richiesta la visita (0 signi ca visita non prevista) e l'eventuale skill necessaria. A ciascun paziente viene associato un solo pattern e tutte le visite da esso previste devono essere eettuate.
Viene assegnato il valore di skill 1 agli infermieri ordinari e 2 agli infer-mieri specializzati. Questi ultimi possono anche eettuare visite di skill 1. Il numero di operatori che può eettuare visite a ciascun paziente viene limitato superiormente da un valore stabilito in precedenza. Nelle prove ef-fettuate abbiamo considerato tale valore pari a 2. Tali vincoli sono dovuti al disagio che i pazienti possono avvertire se vengono visitati da persone sco-nosciute.
La correttezza dei tour è determinata da dei vincoli di routing che fanno uso di variabili di usso. A ciascun tour viene assegnata una quantità di usso corrispondente al numero di richieste da soddisfare. Viene lasciata un'unità di usso per ogni visita eettuata e quando l'operatore termina il tour il valore del usso rimanente sarà pari a 0.
La funzione obiettivo si occupa di bilanciare il carico di lavoro degli ope-ratori, massimizzando una variabile che ha lo scopo di limitare inferiormente il coe ciente di utilizzo di cascun operatore. È stata inoltre formulata una funzione obiettivo alternativa allo scopo di minimizzare anche la durata dei
singoli tour.
Il problema presenta una formulazione originale che non è mai stata uti-lizzata nora. Sono stati presentati dei modelli per risolvere problemi simili ma spesso si riferivano a orizzonti temporali di un giorno e che comunque non facevano l'uso dei pattern per organizzare le visite. Una accurata de-scrizione della letteratura è presentata nel Capitolo 2.
1.3 Modelli proposti
1.3.1 Dati di input
G=(N, A) grafo completo corrispondente alla mappa dei pazienti O insieme degli operatori disponibili
Od⊆ O insieme degli operatori disponibili il giorno d
P insieme dei pattern disponibili
p ∈ P pattern di tipo [x1, x2, x3, x4, x5] xi ∈ {0, 1, 2}, ∀i ∈ {1, . . . , 5}
st valore di skill dell'operatore t
tij tempo di spostamento dal nodo i al nodo j
t0ik tempo di servizio sul paziente i in base alla skill k Dt durata massima di una giornata lavorativa del tecnico t
T numero massimo di operatori per paziente in una settimana W numero di giorni lavorativi per settimana
rj visite richieste del paziente j, di tipo [x1, x2] xi∈ N
1.3.2 Variabili
zjp=
1 se il pattern p è assegnato al paziente j
0 altrimenti j ∈ N, p ∈ P
xtdij =
1se l'operatore t percorre (i, j) durante il giorno d 0altrimenti
t ∈ Od, 1 ≤ d ≤ W , (i, j) ∈ A
utj =
1 se l'operatore t è assegnato al paziente j
0 altrimenti t ∈ O, j ∈ N
1.3.3 Vincoli X i∈N X t:st≥1 xtdij ≤ 1 ∀j ∈ N \ {0}, ∀1 ≤ d ≤ W, t ∈ Od (1.1) In una giornata ciascun paziente può essere visitato da al più un operatore.
X i∈N X t:st=2 xtdij ≥ X p:p(d)=2 zjp ∀j ∈ N \ {0}, ∀1 ≤ d ≤ W, t ∈ Od (1.2)
Se un paziente richiede una visita di skill 2 durante il giorno d almeno un operatore dotato di skill 2 deve visitare quel paziente in quel giorno.
X i∈N X t:st≥1 xtdij ≥ X p:p(d)=1 zjp ∀j ∈ N \ {0}, ∀1 ≤ d ≤ W, t ∈ Od (1.3)
Se un paziente richiede una visita di skill 1 durante il giorno d almeno un operatore deve visitare quel paziente in quel giorno.
X i∈N X t∈Od xtdij ≤ X p:p(d)≥1 zjp ∀j ∈ N \ {0}, ∀1 ≤ d ≤ W (1.4)
Il numero di operatori che visita un paziente durante il giorno d è limitato superiormente dal numero di richieste per quel determinato giorno.
X
p∈P
zjp= 1 ∀j ∈ N \ {0} (1.5)
Ad ogni paziente deve essere assegnato un solo pattern. X
t∈O
utj ≤ T ∀j ∈ N \ {0} (1.6)
Non possono essere assegnati più di T operatori a ogni paziente.
xtdij ≤ utj ∀i ∈ N, ∀j ∈ N \ {0}, ∀t ∈ Od, ∀1 ≤ d ≤ W (1.7)
Un operatore può andare da un paziente solo se è stato assegnato ad esso. Dtd= X (i,j)∈A tij· xtdij + X j∈N \{0} t0j1·X i∈N xtdij ≤ Dt ∀t ∈ Od, ∀1 ≤ d ≤ W (1.8) I tempi di lavoro e di spostamento non possono eccedere la durata massima di una giornata lavorativa.
X
i∈N
xtdij =X
i∈N
xtdji ∀j ∈ N, ∀t ∈ Od, ∀1 ≤ d ≤ W (1.9)
Per ogni paziente gli operatori in entrata sono gli stessi in uscita. rj(1) = X p∈P X d:p(d)=1 zjp ∀j ∈ N \ {0} (1.10) rj(2) = X p∈P X d:p(d)=2 zjp ∀j ∈ N \ {0} (1.11)
Il numero di visite di tipo 1 o 2 deve coincidere con la richiesta corrispon-dente. 1.3.4 Vincoli di routing X j∈N \{0} y0jd = X j∈N \{0} X p:p(d)≥1 zjp ∀1 ≤ d ≤ W (1.12)
Il usso uscente dal nodo origine corrisponde alla somma delle richieste del pazienti. X i∈N yijd −X i∈N yjid = X p:p(d)≥1 zjp ∀j ∈ N \ {0}, 1 ≤ d ≤ W (1.13)
Se vi è una richiesta dal paziente j il usso entrante sarà maggiore di quello uscente di 1 unità, altrimenti rimane invariato.
yijd ≤ (n − 1)X
t∈Od
xtdij ∀i, j ∈ N, 1 ≤ d ≤ W (1.14) La quantità di usso che può transitare in un arco è limitata superiormente dal numero di nodi del grafo.
1.3.5 Funzione obiettivo max m (1.15) W X d=1 Dtd W · Dt ≥ m ∀t ∈ O (1.16)
Viene massimizzato il minimo coe ciente di utilizzo settimanale degli ope-ratori, cioè il rapporto tra ore di lavoro e ore lavorative totali nell'arco della settimana.
1.3.6 Funzione obiettivo alternativa max M ∗ m − v (1.17) W X d=1 Dtd W · Dt ≥ m ∀t ∈ O (1.18) W X d=1 X (i,j)∈A xtdij · tij ≤ v ∀t ∈ O (1.19)
In questa funzione obiettivo viene tenuto in considerazione anche il tem-po impiegato dagli operatori esclusivamente negli stem-postamenti. Lo scotem-po è quello di favorire i tour di durata minima, in modo da ottimizzare il tempo impiegato dagli operatori per eettuare le visite. È stato comunque utiliz-zato un peso, M, per evitare che la durata dei tour in uisca troppo nelle soluzioni.
1.4 Formulazione alternativa
Nella fase di progettazione è stata considerata un'ulteriore formulazione del modello, poi scartata a causa dell'elevato numero di variabili prodotte nella fase di test.
In tale contesto le variabili decisionali xtd
ij a 4 indici sono state
rimpiazza-te da variabili decisionali a 5 indici xtds
ij , dove s corrisponde al valore di skill
dell'operatore t. Lo scopo di queste variabili è quello di speci care se la visita che verrà eettuata sul paziente j sarà di tipo palliativo o non palliativo. A conseguenza di ciò il numero di tali variabili raddoppia nel caso di operatori con valore di skill pari a 2.
Formalmente: xtdsij =
1 se l'operatore t percorre (i, j) durante il giorno d ed eettua una visita di skill s su j
0 altrimenti
t ∈ Od, t : s(t) ≥ s, 1 ≤ d ≤ W , (i, j) ∈ A
Vengono modi cati conseguentemente anche tutti i vincoli in cui compa-iono tali variabili. In alcuni casi tali vincoli vengono rimpiazzati da altri vin-coli, in altri le variabili xtd
ij vengono sostituite da un OR del tipo (xtd1ij +xtd2ij ).
Nello speci co:
I vincoli (1)(4) vengono rimpiazzati dai due seguenti gruppi di vincoli: X i∈N X t:st≥1 xtd1ij = X p:p(d)=1 zjp ∀j ∈ N \ {0}, ∀1 ≤ d ≤ W (1.20)
In un determinato giorno il numero di operatori che eettua visite di skill 1 su un paziente sarà uguale al numero di pattern assegnati a quel paziente. X i∈N X t:st=2 xtd2ij = X p:p(d)=2 zjp ∀j ∈ N \ {0}, ∀1 ≤ d ≤ W (1.21)
In un determinato giorno il numero di operatori che eettua visite di skill 2 su un paziente sarà uguale al numero di pattern assegnati a quel paziente.
Ai restanti vincoli viene applicato l'OR. I vincoli (7) diventano:
(xtd1ij + xtd2ij ) ≤ utj ∀(i, j) ∈ A, ∀j ∈ N \ {0}, ∀t ∈ Od, ∀1 ≤ d ≤ W
(1.22) Un operatore può visitare un paziente solo se è stato assegnato ad esso.
I vincoli (8): Dtd = X (i,j)∈A tij · (xtd1ij + xtd2ij ) + X j∈N \{0} t0j1·X i∈N xtd1ij + X j∈N \{0} t0j2·X i∈N xtd2ij ≤ Dt ∀t ∈ Od, ∀1 ≤ d ≤ W (1.23) I tempi di lavoro e di spostamento non possono eccedere la durata massima di una giornata lavorativa.
I vincoli (9): X i∈N (xtd1ij +xtd2ij ) =X i∈N (xtd1ji +xtd2ji ) ∀j ∈ N \{0}, ∀t ∈ Od, ∀1 ≤ d ≤ W (1.24) Per ogni paziente gli operatori in entrata sono gli stessi in uscita. I vincoli (19): W X d=1 X (i,j)∈A (xtd1ij + xtd2ij ) · tij ≤ v ∀t ∈ O (1.25)
Capitolo 2
Rassegna della letteratura
In questo capitolo vengono descritti in dettaglio gli articoli alla base dello studio intrapreso. È presentata una discussione generale sullo stato attuale della letteratura, le problematiche arontate e le soluzioni proposte, e in seguito viene presentata una descrizione dettagliata degli articoli ritenuti più signi cativi seguendo un ordinamento cronologico a ritroso, analizzando quindi prima gli articoli di più recente pubblicazione.
Degli articoli selezionati vengono riportati i modelli proposti.
Il resto dei lavori viene discusso in forma meno dettagliata in una sezione successiva, seguando sempre un ordinamento cronologico a ritroso.
2.1 Panoramica generale
I problemi di scheduling e routing in contesti di Home Care rappresentano una famiglia abbastanza nuova nell'ambito dell'ottimizzazione. Il primo mo-dello di PLI formulato allo scopo speci co è stato proposto da Begur et al.[6] nel 1997. Tale modello prevedeva, similmente al nostro, orizzonti temporali settimanali e l'utilizzo delle skill e dei pattern. Contrariamente però al mo-dello formulato in questa tesi la piani cazione è decomposta in piani cazioni giornaliere tra loro indipendenti. Lo scopo dei pattern era quello di coor-dinare 5 diversi modelli, ciascuno relativo ad ogni singolo giorno lavorativo della settimana.
Borsani et al.[17] presentano invece un modello di solo scheduling, trala-sciando il routing, in cui le visite non vengono coordinate mediante pattern pre-esistenti, ma in base ai giorni preferenziali dei pazienti. In questo caso le visite possono anche essere eettuate in giorni dierenti, ma sarà necessario aggiungere una penalità alla funzione obiettivo. Un altro tema interessante introdotto in questo articolo è quello del out. La sindrome da burn-out è causata dall'elevato stress che può portare un infermiere a non essere
in grado di poter eettuare il proprio lavoro e addirittura licenziarsi. Nel modello viene indicato il massimo livello di stress sopportabile da parte di ciascun operatore e la quantità di stress apportata da ciascun paziente in base alle proprie patologie.
Nella maggior parte dei lavori l'attenzione si sposta su orizzonti temporali di una singola giornata, tralasciando dai modelli la gestione dei piani di cura a lungo termine. Questo aspetto permette di trattare in maniera più speci ca delle situazioni che possono veri carsi in contesti come quello dell'Home Ca-re. Generalmente è possibile che siano eettuate più visite nell'arco di una singola giornata, anche da parte di più operatori. In Bredström et al.[8] viene trattato il problema prevedendo visite sincronizzate. Alcune visite possono necessitare di più operatori, e a questo scopo si deve gestire la sicronizzazione tenendo conto anche dei tempi di spostamento in fase di scheduling.
Il tema delle visite sincronizzate è arontato anche in Kergosien et al.[12], in cui sono previste anche visite sincronizzate su tempi diversi. Lo scopo di ciò è dovuto alla necessaria sincronizzazione di diverse attività, a cui cor-rispondono visite da parte di operatori assegnati a diverse mansioni. Un esempio può essere quello di un operatore incaricato alle pulizie che deve raggiungere il paziente dopo una particolare visita.
Sono stati anche arontati problemi che trattano casi speci ci del contesto di Home Care.
Elbenani et al.[10] presentano un modello che prevede, oltre a visite ge-neriche non classi cate, la gestione di visite relative a prelievi di sangue. Tali visite devono essere eettuate esclusivamente la mattina e comportano il ri-torno degli operatori che le eettuano alla sede di Home Care entro un'ora dal prelievo. Gli orari di ritorno sono preimpostati (10 AM e 11 AM).
Un altro caso speci co è presentato da Chahed et al.[9], in cui viene trat-tato il problema della chemioterapia a domicilio. Viene trattata in dettaglio la fase di progettazione degli eventuali modelli, considerando lo scheduling della produzione dei farmaci e il routing degli operatori, che possono svolge-re le mansioni di consegna dei farmaci o di visita infermieristica. Il modello proposto è semplice, prevede l'utilizzo di un solo operatore con la nalità di consegnare i medicinali in tempo.
Trautsamwieser et al.[1] forniscono un lavoro degno di nota, poichè trat-ta diverse problematiche relative alla gestione dei pazienti in caso di disastri naturali, basandosi sui dati delle alluvioni che hanno colpito il nord dell'Au-stria nel 2002. Oltre alle skill relative alla quali ca degli infermieri sono considerati anche altri valori di skill relative alla lingua parlata. I pazienti in cura possono essere stranieri e necessitano operatori che sappiano parlare la loro lingua. È inoltre trattato il caso in cui determinate strade possano essere a rischio, considerando dunque gli eventuali ritardi causati dalla scarsa percorribilità.
Gran parte dei lavori utilizza le cosidette time windows, nestre temporali de nite allo scopo di speci care l'intervallo di tempo in cui possono essere eettuate le visite. In Cheng et al.[4] viene mostrato un lavoro in cui ven-gono paragonati due modelli formulati per risolvere lo stesso problema, con e senza l'utilizzo delle time windows, illustrandone i vantaggi e gli svantaggi delle due versioni.
Le sperimentazioni relative ai modelli trattati generalmente portano a so-luzioni decisamente migliori rispetto alle soso-luzioni correnti, mediamente del 15-20%. Rasmussen et al.[2] presentano prove relative sia ad istanze reali che ad istanze generate casualmente. I test sono stati svolti risolvendo il modello matematico, mentre in casi come Thomsen et al.[13] o Akjiratikarl et al.[5] sono state utilizzate delle metaeuristiche.
Tutti i modelli n qui discussi sono formulazioni di PLI basate su VRP. Bertels et al.[7] propongono una formulazione che utilizza elementi di PLI ed elementi di Constraint Programming ed applica le euristiche Simulated Annealing[21] e Tabu Search[22], mentre Eveborn et al.[11] arontano il problema basandosi sul modello di set partitioning[24] utilizzando la meta-euristica Repeated Matching[25].
Oltre alla letteratura relativa ai problemi di scheduling e routing sono stati analizzati anche dei lavori come Koeleman et al.[3] ed i lavori di Lanzarone et al.[14][15][16], che trattano in dettaglio l'ammissione dei pazienti al sistema e lo scheduling delle visite secondo catene di Markov[26].
In ne vale la pena citare Blais et al.[18] in cui viene trattato accurata-mente il problema della divisione territoriale in distretti, analizzando il caso reale relativo ad una zona della città di Montreal, in Canada, in cui l'aumen-to demogra co ha causal'aumen-to la necessità di una riorganizzazione terril'aumen-toriale. In tale zona la precedente ripartizione in 4 distretti è stata rimpiazzata da una ripartizione a 6 distretti.
2.2 A. Trautsamwieser, M. Gronalt, P. Hirsch.
Securing home health care in times of natural
disasters [1]
Viene presentato un modello basato su VRPTW[19] (TW sta per Time Windows) ideato sulla base del trattamento dei pazienti in caso di disastri naturali. Viene modellato secondo PLI.
Il modello presenta alcuni elementi comuni con quello trattato nella pre-sente tesi, si occupa dello scheduling e del routing degli operatori. Similmente al nostro modello è presente il livello di quali ca degli operatori, usata in ma-niera simile a come vengono trattate le skill. Tale valore varia in base alle necessità delle istanze. Inoltre viene eettuato un controllo della lingua par-lata da pazienti e operatori, facendo in modo che i pazienti vengano visitati da operatori che parlano la stessa lingua.
Punti degni di nota: orari preferenziali di visita, lingua parlata (pazienti e operatori), possono essere presenti diversi nodi deposito, a seconda che l'operatore inizi il tour dalla propria abitazione o dalla sede. La piani cazione è relativa solamente al singolo giorno. Non è dunque presente il concetto di pattern. Possono inoltre essere eettuate più visite allo stesso paziente nello stesso giorno.
É possibile che in alcune strade più a rischio il tempo di spostamento venga aumentato notevolmente a causa della scarsa percorribilità.
Funzione obiettivo: minimizza la somma di diversi fattori, come i tempi di spostamento, il livello di insoddisfazione (sia di pazienti che di operatori), i tempi di visita oltre la previsione e le visite eseguite da operatori di quali ca maggiore del necessario. L'insoddisfazione può dipendere da fattori quali ritardi o visite più lunghe del previsto.
Le prove sono state svolte su istanze reali e generate. Viene mostrato un paragone tra la risoluzione basata sulla metaeuristica VNS (Variable Neigh-borhood Search)[23] e quella ottenuta utilizzando il solver Xpress 7.0. I test sono stati eseguiti su un Intel Core2quad 2,66 Ghz con 6 GB di RAM.
I test sulle istanze generate sono stati svolti su due dataset (rispetti-vamente 30 pazienti, 6 operatori e 100 pazienti, 20 operatori) al variare di diversi parametri, quali tempi di percorrenza o penalità dovuta all'insoddi-sfazione. Sono state provate anche istanze più grandi, ma il solver non riesce a trovare una soluzione ottima. Le soluzioni euristiche sono distanti al più il 2% rispetto alle soluzioni ottime calcolate dal solver.
Nei test eettuati sui casi reali si nota che le istanze più grandi vengono risolte più velocemente delle istanze piccole, complice forse il fatto che al crescere delle dimensioni dell'istanza vi è una suddivisione dei pazienti e degli operatori in base a diversi livelli di skill. Vengono presi in considerazione 3 dataset (regioni), relativi ad una suddivisione territoriale del Nord Austria, per ciascuno dei quali vengono generate 2 istanze, una con un numero di
visite normale (scenario N) e una con un numero di visite estremo(scenario E), cioè vengono fatte tutte le visite possibili. I test sono stati svolti con la metaeuristica VNS limitando le iterazioni a 106, non sono dunque presenti
confronti con un'eventuale soluzione ottima trovata dal solver.
Regione Scenario Clienti Visite Operatori Soluzione Tempo
1 N 86 86 13 122.00 2647 min 1 E 140 140 13 282.70 4119 min 2 N 204 226 39 1231.20 1599 min 2 E 291 351 39 2435.40 2056 min 3 N 305 350 75 1850.90 1191 min 3 E 411 512 75 3497.50 1623 min
Nell'articolo è anche riportata una tabella simile con dati relativi al caso speci co dell'alluvione che ha coinvolto la zona Nord dell'Austria nel 2002.
Viene solamente accennato che in un'istanza di dimensione maggiore non viene trovata soluzione.
Modello proposto
Notazioni
P Insieme dei pazienti
V Insieme delle visite
V0 Insieme delle visite incluse le visite al nodo deposito
O Insieme degli operatori
R Insieme dei tour
E Nodo pausa pranzo
D Insieme di operatori che iniziano il tour dal nodo deposito H1 Insieme di operatori che iniziano il tour dalla propria
abitazione
H2 Insieme di operatori che iniziano il tour dall'abitazione del
primo paziente
∆ Numero di lingue considerate
T Massimo tempo di lavoro
W Tempo di lavoro dopo il quale è obbligatoria una pausa M Costante a cui è associato il valore dei minuti di una giornata
(1.440)
w1...w7 Pesi associati alla funzione obiettivo
sv Livello di skill di una visita v ∈ V
s0n Livello di skill di un operatore n ∈ O
φv Operatore di preferenza per svolgere la visita v ∈ V
rv Ri uto degli operatori per svolgere la visita v ∈ V
rn0 Ri uto di una visita da parte dell'operatore n ∈ O πij Skill del paziente i ∈ P per la lingua j
πnj0 Skill dell'operatore j ∈ O per la lingua j Ωn Ore contrattuali di un operatore n ∈ O
tij Tempi di spostamento da i ∈ O ∪ V0 a j ∈ O ∪ V0
dv Tempo di servizio per una visita v ∈ V
pk Tempo della pausa pranzo nel tour k ∈ R
αv, βv Limite minimo e massimo della hard time window di una
visita v ∈ V
α0v, βv0 Limite minimo e massimo della soft time window di una visita v ∈ V
Ak, Bk Limite massimo e minimo della soft time window del tour
k ∈ R
AEk, BEk Limite massimo e minimo della soft time windows delle pause
del tour k ∈ R
θ(k) Funzione che assegna il tour k ∈ R ai rispettivi operatori ω(v) Funzione che associa la visita v ∈ V ai rispettivi pazienti xkij Variabile binaria, è uguale a 1 se la visita j ∈ V è eettuata
t0kv Tempo di inizio della visita v ∈ V sul tour k ∈ R t0Ek Tempo di inizio della pausa sul tour k ∈ R Sk, Fk Tempo di inizio e ne del tour k ∈ R
yk Variabile binaria, è uguale a 1 se è stata fatta una pausa sul
tour k ∈ R, 0 altrimenti
on Durata dello straordinario per un operatore n ∈ O
lv, uv Valore minimo e massimo per cui è violata la durata di una
visita v ∈ V
Lk, Uk Valore minimo e massimo per cui è violata la durata di un
tour k ∈ R
LEk, UEk Valore minimo e massimo per cui è violata la durata di una
Modello min w1 X k∈R (Fk− Sk− pkyk) − X j∈V dj (2.1) +w2 X n∈O on (2.2) +w3 X i∈V0 X j∈V X k∈R:φj=θ(k) (1 − xkij)dj (2.3) +w4 X j∈V (lj + uj) (2.4) +w5 X k∈R (Lk+ Uk+ LEk+ U Ek) (2.5) +w6 X i∈V0 X j∈V X k∈R:sj<s0θ(k) djxkij (2.6) +w7 X k∈H2 X j∈V (tθ(k)jxk0j+ tjθ(k)xkj0) (2.7) xkij ≤ min s 0 θ(k) sj , max(π0θ(k)1πω(j)1, ...,πθ(k)∆0 πω(j)∆), |θ(k) − rj|, |j − r0θ(k)| ∀i ∈ V0, ∀j ∈ V, ∀k ∈ R (2.8) xkij ≤ max 0, βj+ 1 − (αi+ di+ tij) ∀i, j ∈ V, ∀k ∈ R (2.9) X i∈V0 X k∈R xkij = 1 ∀j ∈ V (2.10) X i∈V xkiE= yk ∀k ∈ R (2.11) X i∈V xk0j ≤ 1 ∀k ∈ R (2.12) X i∈V xki0≤ 1 ∀k ∈ R (2.13) X i∈V0 xkij = X h∈V0 xkjh ∀j ∈ V, ∀k ∈ R (2.14)
xkEj = xkjE ∀j ∈ V, ∀k ∈ R (2.15) xkEj ≤X i∈V xkij ∀j ∈ V, ∀k ∈ R (2.16) t0ik+ (tij+ di)xkij ≤ t0jk+ βi(1 − xkij) ∀i, j ∈ V, ∀k ∈ R (2.17) t0Ek+ pkxkEj ≤ t 0 jk+ M (1 − xkEj) ∀i, j ∈ V, ∀k ∈ R (2.18) t0ik+(tij+di)(xkij+xkjE) ≤ t 0 jk+βi(2−xkij−xkjE)+tij+di ∀i, j ∈ V, ∀k ∈ R (2.19) Sk+ t0jxk0j ≤ t 0 jk+ M (1 − xk0j) ∀j ∈ V, ∀k ∈ D (2.20) Sk+ tθ(k)jxk0j ≤ t 0 jk + M (1 − xk0j) ∀j ∈ V, ∀k ∈ H1 (2.21) Sk≤ t0jk+ M (1 − xk0j) ∀j ∈ V, ∀k ∈ H2 (2.22) t0jk+ (tj0+ dj)xkj0 ≤ Fk+ βj(1 − xkj0) ∀j ∈ V, ∀k ∈ D (2.23) t0jk+ (tjθ(k)+ dj)xkj0 ≤ Fk+ βj(1 − xkj0) ∀j ∈ V, ∀k ∈ H1 (2.24) t0jk+ djxkj0≤ Fk+ βj(1 − xkj0) ∀j ∈ V, ∀k ∈ H2 (2.25) Fk+ pk≤ Sl ∀k, l ∈ R : k < l, θ(k) = θ(l) (2.26) X k∈R:θ(k)=n (Fk− Sk− pk) ≤ T ∀n ∈ O (2.27) αj X h∈V0 xkjh ≤ t0jk ≤ βj X h∈V0 xkjh ∀j ∈ V, ∀k ∈ R (2.28) t0Ek≤ min(W + Sk, Myk) ∀k ∈ R (2.29)
Fk− Sk− W W ≤ yk≤ Fk− Sk W ∀k ∈ R (2.30) on≥ X k∈R:θ(k)=n (Fk− Sk− pkyk) − Ωn ∀n ∈ O (2.31) lj ≥ αj0 − X k∈R t0jk ∀j ∈ V (2.32) uj ≥ X k∈R t0jk− βj0 ∀j ∈ V (2.33) LEk≥ (Ak+ AEk)yk− t0Ek ∀k ∈ R (2.34) U Ek≥ t0Ek− (Ak+ BEk) ∀k ∈ R (2.35) Lk≥ Ak− Sk ∀k ∈ R (2.36) Uk≥ Fk− Bk ∀k ∈ R (2.37) on≥ 0 ∀n ∈ O (2.38) lj ≥ 0 ∀j ∈ V (2.39) uj ≥ 0 ∀j ∈ V (2.40) LEk≥ 0 ∀k ∈ R (2.41) U Ek≥ 0 ∀k ∈ R (2.42) Lk≥ 0 ∀k ∈ R (2.43) Uk≥ 0 ∀k ∈ R (2.44) xkij ∈ {0, 1} ∀i, j ∈ V0∪ E, ∀k ∈ R (2.45) yk ∈ {0, 1} ∀k ∈ R (2.46)
2.3 M. S. Rasmussen, T. Justesen, A.Dohn, J.
Lar-sen.
The Home Care Crew Scheduling Problem:
Preference-Based Visit Clustering and Temporal
Depen-dencies [2]
Viene presentato un modello di scheduling degli operatori, basato su Set Partitioning[24]. Per il routing viene utilizzato VRPTW. Anche in questo caso è un problema di PLI.
Le prove sono state svolte su istanze reali e generate. Per le istanze più grandi il problema è stato risolto mediante visit clustering, tramite delle procedure spiegate in dettaglio nell'articolo.
Lo scheduling è relativo alla singola giornata. La politica di scheduling è basata su visite preferenziali. Vi è anche una gerarchia di preferenza sugli operatori per ciascun paziente.
Non è presente il concetto di skill, gli operatori vengono scelti solo in base alla preferenza.
Funzione obiettivo: minimizzare il numero di visite non coperte e il costo totale, massimizzare il numero di visite preferenziali. I criteri sono combinati in una funzione obiettivo che include le tre sommatorie alle quali vengono moltiplicati dei pesi per stabilire una priorità tra gli obiettivi.
Le prove sono state svolte proponendo un algoritmo esatto di tipo Branch and Price, de nito a partire dal modello matematico proposto. Sono state trattate 4 istanze reali e 60 generate. Le dimensioni delle istanze vanno dai 6 ai 15 operatori e dai 60 ai 150 pazienti (tranne un solo caso con 4 operatori e 20 pazienti). Il solver utilizzato è COIN-OR, open source, e le prove hanno avuto durata massima di 1 ora ciascuna. I risultati sono migliori del 6% rispetto a quelli relativi al modello presentato da Bredstrom e Ronnqvist nel 2007, che hanno fornito 30 istanze per il paragone.
Modello proposto
Notazioni
O Insieme degli operatori
P Insieme dei pazienti, e analogamente delle visite
[αi, βi] Time window della visita i ∈ P
Nk= P ∪ {0k, nk} Insieme delle visite potenziali per l'operatore k ∈ O, 0k e nk
sono le visite di inizio e ne tour per l'operatore k [α0k, β0k] = [αnk, βnk] Time window dell'operatore k ∈ O
tk
ij Tempo di spostamento dal paziente i ∈ P al paziente j ∈ P ,
dipende dal mezzo utilizzato dall'operatore k ∈ O
ckij Costo del viaggio dal paziente i ∈ P al paziente j ∈ P ,
dipende dal mezzo utilizzato dall'operatore k ∈ O
ρki Variabile binaria, è 1 se k ∈ O può essere assegnato alla
visita i ∈ P , 0 altrimenti δk
i Costo della visita i ∈ P compiuta dall'operatore k ∈ O
γi Priorità della visita i ∈ P
τi Tempo di inizio della visita i ∈ P
τij0 Intervallo di tempo tra l'inizio della visita i ∈ P e della visita j ∈ P
xkij Variabile binaria di routing, è 1 se l'operatore k ∈ O si sposta direttamente da i ∈ P a j ∈ P , 0 altrimenti
t0ki Variabile di scheduling, indica il tempo che l'operatore k ∈ O impiega per iniziare la visita i ∈ P
yi Variabile binaria di copertura, è 1 se la visita i ∈ P non è
assegnata ad alcun operatore, 0 altrimenti w1, w2, w3 Pesi associati alla funzione obiettivo
Modello min w1 X k∈O X i∈Nk X j∈Nk ckijxkij + w2 X k∈O X i∈P X j∈Nk δkijxkij + w3 X i∈P γiyi (2.47) X k∈O X j∈Nk xkij + yi = i ∀i ∈ P (2.48) X j∈Nk xkij ≤ ρki ∀k ∈ O, ∀i ∈ P (2.49) X j∈Nk xk0kj = 1 ∀k ∈ O (2.50) X j∈Nk xkink = 1 ∀k ∈ O (2.51) X i∈Nk xkih− X j∈Nk xkhj = 0 ∀k ∈ O, ∀h ∈ P (2.52) αi X j∈Nk xkij ≤ t0ki ≤ βi X j∈Nk xkij ∀k ∈ O, ∀i ∈ P ∪ {0k} (2.53) αnk ≤ t0knk ≤ βnk ∀k ∈ O (2.54) t0ki + tkijxkij ≤ t0ki + βi(1 − xkij) ∀k ∈ O, ∀i, j ∈ Nk (2.55) αiyi+ X k∈O t0ki + tau0ij ≤X k∈O t0kj + βjyj ∀(i, j) ∈ P (2.56) xkij ∈ {0, 1} ∀k ∈ O, ∀i, j ∈ Nk (2.57) t0ki ∈ Z+ ∀k ∈ O, ∀i ∈ Nk (2.58) yi ∈ {0, 1} ∀i ∈ P (2.59)
2.4 Y. Kergosien, C. Lenté, J. Billaut.
Home health care problem - An extended
mul-tiple Traveling Salesman Problem [12]
Anche in questo lavoro vengono trattati i problemi di scheduling e di routing. Il modello alla base è sempre il VRP, anche se qui viene chiamato mTSP (multiple traveling salesman problem), con time windows.
Non c'è un solo nodo deposito, ma ogni operatore inizia e termina il tour nella propria sede. Le time windows non sono sse, ciascun operatore ha la propria. Anche le visite hanno le proprie time windows. Le visite ad uno stesso paziente all'interno della stessa time window da parte di più operatori, che possono avere skill diverse, sono considerate visite sincronizzate. Alcuni operatori hanno la possibilità di poter ritardare di qualche minuto in quanto dedicati a mansioni successive.
Il modello matematico, PLI, presenta caratteristiche molto simili a quello nostro, ma con orizzonte di piani cazione giornaliero.
La funzione obiettivo ha il compito di minimizzare il costo totale degli spostamenti.
Dopo il modello è presentata una breve sezione con dei tagli che permet-tono di migliorare il tempo di risoluzione. Nello speci co viene assicurato che:
• Due servizi con due time windows sovrapposte richiedono due diversi operatori.
• Due visite che fanno parte di una visita sincronizzata devono essere assegnate a due operatori distinti, con skill adeguate alle skill associate alle visite. Lo stesso vale per un numero di visite sincronizzate che sia maggiore di 2.
• Si assegnano i tour più lunghi agli operatori con costo minore, aggiun-gendo un'ulteriore sommatoria alla funzione obiettivo.
Per i test sono state de nite delle categorie in base al numero di visite (10, 20, 30 o 40) e ai livelli di skill (1, 2 o 3). Per le categorie selezionate sono state generate 200 istanze in modo casuale. Il numero di operatori è generato per ogni istanza in modo che ognuno venga impegnato al 70% circa. Il solver è CPLEX lanciato su un Pentium IV a 2,8 Ghz. Ad ogni prova è stato dato un tempo limite di 10 minuti.
La seguente tabella indica, per ogni categoria, il tempo medio di risolu-zione, la percentuale di soluzioni ottime trovate e il valore medio del gap. Le colonne 3, 4 e 5 indicano l'andamento del modello standard mentre le colonne 6, 7 e 8 l'andamento del modello modi cato con i tagli descritti in precedenza.
Visite Skill Tempo (sec.) % sol. ottime Gap Tempo (sec.) % sol. ottime Gap 10 3 0,03 100,0 0,03 100,0 10 2 0,06 100,0 0,05 100,0 10 1 0,45 100,0 0,42 100,0 20 3 1,14 100,0 1,65 100,0 20 2 10,1 100,0 8,8 100,0 20 1 220,6 58 18,2 181,7 58 16,1 30 3 41,0 90,0 9,1 46,8 89,5 9,7 30 2 144,1 63,5 9,8 136,2 66,5 10,0 40 3 167,9 52,0 7,0 107,4 57,0 5,8 Modello proposto Notazioni
O = {1, ..., m} Insieme degli operatori
sk Valore di skill dell'operatore k ∈ O
D Insieme dei domicili degli operatori
Dk Domicilio dell'operatore k ∈ O
[αDk, βDk] Time window relativa al domicilio dell'operatore k ∈ O V = {1, ..., n} Insieme dei servizi
s0i Skill necessaria per il servizio i ∈ V [αi, βi] Time window relativa al servizio i ∈ V
pi Durata del servizio i ∈ V
tij Tempo di percorrenza tra le locazioni del servizi i ∈ V
e j ∈ V
Ω = {ω1, ..., ωr} Insieme dei trattamenti che necessitano più di un
operatore
t00ij Tempo che intercorre tra l'inizio del servizio j ∈ V e il servizio i ∈ V
Φ = {φ1, ..., φo} Insieme di servizi che non devono essere eettuati
simultaneamente
Γ = {γ1, ..., γs} Insieme di servizi che devono essere eettuati dalla
stessa persona
πi Numero di persone pre-assegnate al servizio i ∈ V
ckij Costo del transito da i ∈ V a j ∈ V da parte
dell'operatore k ∈ O
xkij Variabile binaria, è 1 se l'operatore eettua il servizio i ∈ V e successivamente il servizio j ∈ V , 0 altrimenti yij Variabile binaria, è 1 se il servizio i ∈ V è eettuato
prima del servizio j ∈ V
Modello min X k∈O X i∈V X j∈V \i ckijxkij (2.60) X k∈O X i∈V \j xkij = 1 ∀j ∈ V (2.61) X j∈V \i xkji= X j∈V \i xkij ∀k ∈ O, ∀i ∈ V (2.62) X i∈V \Dk xkDki ≤ 1 ∀k ∈ O (2.63) xkDki(αDk + tDki) ≤ t 0 i ∀k ∈ O, ∀i ∈ V (2.64) t0i+ tij+ pi ≤ t0j+ HV (1 − X k∈O xkij) ∀i, j ∈ V, i 6= j (2.65) t0i+ tiDk + pi ≤ x k iDk(lDk− L) + L ∀k ∈ O, ∀i ∈ V (2.66) t0i = t0j+ t00ij ∀ωh ∈ Ω, ∀i, j ∈ ωh, i 6= j (2.67) yij = 1 − yji ∀φh∈ Φ, ∀i, j ∈ φh, i 6= j (2.68) t0i+ pi≤ t0j + HV (1 − yij) ∀φh ∈ Φ, ∀i, j ∈ φh, i 6= j (2.69) X l∈V \i xkli= X l∈V \j xklj ∀γh ∈ Γ, ∀i, j ∈ γh, i 6= j, ∀k ∈ O (2.70) X l∈V \i xπi li = 1 ∀i ∈ V : πi 6= 0 (2.71)
2.5 B. Elbenani, J.A. Ferland, V. Gascon.
Mathematical Programming Approach for
Rou-ting Home Care Nurses [10]
Viene presentato un modello di scheduling e routing basato su VRPTW. Gli operatori hanno la caratteristica di poter eettuare dei prelievi di sangue, quindi devono eettuare spesso ritorni al nodo deposito, poichè il campione deve essere consegnato entro un'ora.
L'orizzonte di piani cazione è giornaliero e non si fa uso delle skill. La sola dierenza tra gli operatori è la suddivisione di essi in tre categorie di costo, ma tale suddivisione è legata alla tipologia di contratto.
Tra i pazienti vi è anche un sottoinsieme, i pazienti in terapia, che ne-cessitano maggiormente di altri della continuità di cura, che se non viene rispettata associa alla funzione obiettivo una penalità maggiore.
La funzione obiettivo si occupa di minimizzare i costi dei tour e il numero di operatori associati ai pazienti per i prelievi di sangue.
Per la risoluzione è stato utilizzato un approccio meta-euristico basato su Tabu Search[22]. É stato provato CPLEX 9 ma non è stato in grado di risolvere le istanze reali. Non sono stati forniti dati relativi alle prove, quali migliori soluzioni trovate e tempo di esecuzione. I test si sono svolti su 3 istanze reali, i cui dati vengono mostrati nella seguente tabella. Viene anche indicata la percentuale di pazienti su cui verrà eettuato il prelievo di sangue.
Pazienti Operatori Operatori Jolly % pazienti per prelievo di sangue Pazienti in terapia
84 9 4 34.5 34
92 13 3 45.6 38
82 9 6 23.1 34
In tutti i casi la soluzione trovata è migliore di una media del 10,9% ri-spetto alla piani cazione reale e vengono inoltre utilizzati il 12,8% (in media) di operatori.
Modello proposto
Notazioni
P = {1, ..., n} Insieme dei pazienti
P+ ⊂ P Insieme dei pazienti che necessitano un prelievo di
sangue
O = Or∪ Ol∪ Of Insieme degli operatori, i tre sottoinsiemi
rappresen-tano rispettivamente operatori regolari, di riserva e ttizi
Cr, Cl, Cf Costo giornaliero per le tre categorie di operatori, dove
Cr< Cl Cf
N Insieme di nodi, rappresentano i pazienti e i nodi 0, D,
p10 e p11 relativi alla clinica
0, D ∈ N Nodi relativi rispettivamente all'origine e alla
destina-zione dei tour
p10, p11 Nodi relativi al ritorno dei campioni di sangue,
rispettivamente entro le 10 e le 11
ri Durata della visita al paziene i ∈ P
[αi, βi] Time window relativa al nodo i ∈ N
tij Tempo di spostamento tra il nodo i ∈ N e j ∈ N
A = {(i, j) ∈ N × N |αi+ ri+ tij ≤ βj} Insieme degli archi ammissibili
xkij Variabile binaria, è 1 se l'operatore k ∈ O si sposta
lungo l'arco (i, j) ∈ A
t0ki Tempo di arrivo dell'operatore k ∈ O al nodo i ∈ N
t0kp10, t0kp11 Tempo di ritorno alla clinica per il rilascio dei campioni di sangue
yki Variabile binaria, è 1 se l'operatore k ∈ O visita
durante il suo tour il paziente i ∈ P
ckij Costo associato al percorso dell'arco (i, j) ∈ A per
Modello min X k∈O X (i,j)∈A ckijxkij +X k∈O X j∈P+ yjk (2.72) X k∈O X j∈N xkij = 1 ∀i ∈ P (2.73) X j∈N xkij −X j∈N xkji= 0 ∀i ∈ N \{0, D}, k ∈ O (2.74) X j∈P xk0j ≤ 1 ∀k ∈ O (2.75) X j∈Ns xkjD = X j∈Ns xk0j ∀k ∈ Os (2.76) t0ki + ri+ tij− t0kj ≤ M (1 − xkij) ∀(i, j) ∈ A, ∀k ∈ O (2.77) αi ≤ t0ki ≤ βi ∀i ∈ N, ∀k ∈ O (2.78) 1+(H10−t0ki ) ≤ M (X j∈P xkjp10+1− X j∈P ∪{p10} xkij) ∀i ∈ P+, ∀k ∈ O (2.79) 1+(t0ki −t0kp10) ≤ M (X j∈P xkjp11+1− X j∈P ∪{p11} xkij) ∀i ∈ P+, ∀k ∈ O (2.80) 1+(t0ki −H10) ≤ M (X j∈P xkjp11+1− X j∈P ∪{p11} xkij) ∀i ∈ P+, ∀k ∈ O (2.81) H10 − t0ki ≤ M (X j∈P+ yjk) ∀i ∈ P+, ∀k ∈ O (2.82) t0kp10≤ M + (H10 − M )(X j∈P+ yjk) ∀k ∈ O (2.83) t0ki − t0kp10 ≤ M (1 − yk i) ∀i ∈ P+, ∀k ∈ O (2.84) t0kp11≥ t0ki ∀i ∈ P+, ∀k ∈ O (2.85)
2.6 S. Bertels, T. Fahle.
A hybrid setup for a hybrid scenario:
combi-ning heuristics for the home health care
pro-blem [7]
Anche in questo lavoro le problematiche coprono sia lo scheduling che il rou-ting. Viene presentato il nucleo del software PARPAP, composto di elementi di programmazione lineare e meta-euristiche e come tali componenti vengo-no utilizzati. La formulazione proposta è un birido di PLI e CP (Constraint Programming) e vengono utilizzate le euristiche Simulated Annealing[21] e Tabu Search[22].
Ad ogni paziente viene associato un insieme di visite, che possono anche essere più di una al giorno. L'orizzonte di piani cazione è giornaliero, quindi non vengono utilizzati i pattern. Il concetto di skill è presente ed utilizzato in maniera simile alla nostra. Sia per il rispetto della time window, sia per il rispetto delle skill vengono segnalati alcuni vincoli hard e altri soft. I primi servono a mettere delle restrizioni sulle quali non si può transigere, i secon-di possono essere violati aggiungendo delle penalità alla funzione obiettivo. Tali vincoli caratterizzano i turni degli operatori ed in base ad essi vengono considerate due diverse time windows, anche esse soft e hard.
Sia n il numero di operatori, una soluzione è vista come l'insieme delle ntabelle dei turni, dove ogni turno è visto come la coppia (visita, orario). Per ogni operatore quindi la tabella dei turni rappresenta la sequenza delle visite che devono essere eettuate da lui.
La funzione obiettivo ha il compito di minimizzare la somma totale dei tempi di spostamento, tenendo conto delle penalità relative ai vincoli soft violati.
Vengono fornite diverse euristiche, spiegate in dettaglio, e vengono eet-tuate diverse prove, con e senza applicare tali euristiche.
I test sono stati fatti su 120 istanze generate, contenenti da 20 a 50 operatori, da 80 a 200 pazienti e da 200 a 600 visite per giorno. Per risolvere la formulazione PLI è stato utilizzato ILOG CPLEX 7.5, per quella CP ILOG SOLVER 5.2. É anche stato implementato un approccio Simulated Annealing con ParSA.
Il modello PLI e' stato implementato via Cplex, ma non sono fornite indicazioni su qualità delle soluzioni calcolate da Cplex e relativi tempi di CPU, in quanto è stato preferito avere a disposizione varie soluzioni raccolte più velocemente.
Le 120 istanze sono state raggruppate in 12 classi da 10 istanze ciascuna. Su prove da 900 secondi in tutti i casi la soluzione migliore è quella prodot-ta da Constraint Programming + Tabu Search. Buoni risulprodot-tati sono sprodot-tati ottenuti combinando Constraint Programming e Simulated Annealing. La seguente tabella mostra il valore della migliore soluzione trovata entro i 900
secondi tra le 10 istanze del relativo gruppo. I tre valori della colonna Dim. indicano rispettivamente il numero degli operatori, dei pazienti e delle visite. Tra parentesi compare il numero di soluzioni non trovate per il gruppo in questione. Dim. CP SA TS CP+SA CP+TS 20-80-200 0.239 0.197 0.340 0.202 0.171 20-80-220 0.272 0.370 (2) 0.683 (6) 0.229 0.194 20-80-240 0.312 0.475 (3) (10) 0.277 0.226 30-120-300 0.245 0.280 (1) (10) 0.220 0.180 30-120-330 0.264 0.301 (1) (10) 0.266 0.209 30-120-360 0.301 0.701 (6) (10) 0.309 0.234 40-160-400 0.241 0.364 (2) (10) 0.211 0.192 40-160-440 0.272 0.690 (6) (10) 0.264 0.218 40-160-480 0.307 (10) (10) 0.312 0.251 50-200-500 0.245 0.441 (3) (10) 0.213 0.209 50-200-550 0.277 0.613 (5) (10) 0.262 0.235 50-200-600 0.293 0.927 (9) (10) 0.295 0.266
Modello proposto
Notazioni
O = {1, ..., n} Insieme degli operatori
P = {1, ..., p} Insieme dei pazienti
V = {1, ..., z} Insieme delle visite
Vp ⊆ V Insieme delle visite associate al paziente p ∈ P
hbV, heV inizio e ne della hard time window di una visita
sbV, seV inizio e ne della soft time window di una visita
dV Durata di una visita
hbO, heO inizio e ne della hard time window di un operatore
sbO, seO inizio e ne della soft time window di un operatore
mintimeO Minimo tempo di lavoro di un operatore
maxtimeO Massimo tempo di lavoro di un operatore
S Insieme di tutte le skill o quali che
qualiV Skill richieste per una visita
qualiO Skill possedute da un operatore
sc Variabile binaria, è 1 se l'operatore n ∈ O viola un vincolo
soft nell'eettuare la visita j ∈ V
trtime Tempo di spostamento tra le locazioni associate a due visite R = [(v1, t1), ..., (vk, tk)] Tabella dei turni e contiene l'associazione tra le visite vi∈ V
e il rispettivo tempo di inizio ti ≥ 0
U Btraveltime, UBtraveltime Limite minimo e massimo della somma dei tempi lavorativi
per tutti gli operatori
vil Visita numero l nella tabella relativa all'operatore i ∈ O
ki Indice dell'ultima visita della tabella relativa all'operatore
Modello min obj(R1, ..., Rn) (2.86) obj(R(1), ..., R(n)) = w1 Po i=1 Pki−1 l=1 trtime(vil, vil+1) − LBtraveltime U Btraveltime− LBtraveltime+ (2.87) +w2 1 n P o∈n(toko+ dVv o ko− t o 1) − LBworktime U Bworktime− LBworktime+ (2.88) +w3 1 v X v∈V p0V(v) + w4 1 n X o∈O p0O(o) (2.89) +w5 1 n X o∈O p0sc(o) (2.90) w1+ ... + w5= 1 wi ≥ 0 (2.91) ∪ni=1∪ki l=1{v i l} = V (2.92) (i = i0)∧(l = l0) ∀1 ≤ i, i0≤ n, 1 ≤ l ≤ ki, 1 ≤ l0 ≤ ki0 : (vi l = vi 0 l0) (2.93) hbV(vil) ≤ til≤ heV(vil) i = 1, ..., n, l = 1, ..., ki (2.94) til+ dV(vil) + trtime(vli, vl+1i ) ≤ til+1 i = 1, ..., n, l = 1, ..., ki− 1 (2.95) mintimeO(i) ≤ tiki+ dV(v i ki) − t i 1 i = 1, ..., n (2.96) maxtimeO(i) ≥ tiki+ dV(v i ki) − t i 1 i = 1, ..., n (2.97) hbO(i) ≤ ti1 ∧ tiki+ dV(v i ki) ≤ heO(i) i = 1, ..., n (2.98)
qualiV(vil) ⊆ qualiO(i) i = 1, ..., n, l = 1, ..., ki (2.99)
earlyV(v) = ( 0 sbV(v) = hbV(v) sbV(v)−tv sbV(v)−hbV(v) a.m. (2.100)
lateV(v) = ( 0 heV(v) = seV(v) tv−seV(v) heV(v)−seV(v) a.m. (2.101) p0V(v) = max{earlyV(v), lateV(v, 0} (2.102) earlyO(o) = ( 0 sbO(o) = hbO(o) sbO(o)−t1
sbO(o)−hbO(o) a.m.
(2.103) lateO(o) =
(
0 heO(o) = seO(o) tko+dV(vko)−seO(o)
heO(o)−seO(o) a.m.
(2.104) p0O(o) = 1
2max{earlyO(o), 0} + max{lateO(o), 0} (2.105)
p0sc(o) = 1 k k X l=1 sc(o, vt) o = 1, ..., n (2.106)
2.7 D. Bredström, M. Rönnqvist.
Combined vehicle routing and scheduling with
temporal precedence and synchronization
con-straints [8]
Viene presentato un modello matematico per lo scheduling e il routing, se-condo il modello VRPTW. Caratteristiche del modello sono la possibilità di sincronizzazione delle visite e l'organizzazione di esse mediante relazioni di precedenza. Oltre al contesto di Home Care vengono presentati anche scena-ri relativi a piani cazione aeroportuale e controllo forestale. Mi soermo nel contesto Home Care per ovvi motivi. Le visite, anche qui, dipendono dalla skill dell'operatore e dalla necessità del paziente, e sono organizzate in modo che le stesse tipologie di visite vengano eseguite durante la stessa fascia ora-ria (es. pulizia dalle 8 alle 15, cucina dalle 10:30 alle 11:30 etc). L'orizzonte di piani cazione è giornaliero, quindi non vengono utilizzati pattern.
La funzione obiettivo si occupa, tramite opportuni pesi, di minimizzare tempi di trasporto, preferenze e sincronizzazioni.
Per i test è stato utilizzato CPLEX 10, ma per le istanze di dimensione maggiore si è preferito passare ad un approccio euristico, per via dei lun-ghi tempi in cui vengono trovate soluzioni. Sono state testate 10 istanze, appartenenti a 3 categorie: 20 visite, 4 operatori e 2 visite sincronizzate (le uniche risolte da CPLEX), 50 visite, 10 operatori e 5 visite sincronizzate e 80 visite, 16 operatori e 8 visite sincronizzate. Per lo svolgimento delle prove la funzione obiettivo viene modi cata rispetto a quella proposta nel modello. Vengono proposte quattro alternative, utilizzando dunque solo in parte la funzione obiettivo originaria: minimizzare le preferenze, minimizzare i tem-pi di percorrenza, minimizzare il massimo carico di lavoro o le ultime due combinate.
Sono state testate 75 istanze su CPLEX, con un tempo limite di 1 ora. Sono inoltre state eettuate 20 prove paragonando le soluzioni di CPLEX con quelle trovate con l'euristica e in tutti i casi le soluzioni trovate me-diante l'approccio euristico si sono rivelate migliori o paragonabili a quelle individuate da Cplex entro il limite temporale di un'ora.
Modello proposto
Notazioni
O Insieme dei veicoli, a cui corrispondono gli operatori
G = (N, A) Grafo diretto
N = {o, d, 1, ..., n} Insieme dei nodi
A = {(i, j)|i 6= j, i ∈ N \{d}, j ∈ \{o}} Insieme degli archi
o Nodo origine
d Nodo destinazione
P = {1, ..., n} Insieme dei nodi che rappresentano i pazienti
[αi, βi] Time window per il paziente i ∈ P
Di Durata della visita associata al paziente i ∈ P
[αki, βik] Time window per la disponibilità del veicolo k ∈ O
tij Tempo di percorrenza dal nodo i ∈ N al nodo j ∈ N
Psync ⊂ P × P Insieme di coppie di visite sincronizzate
Pprec ⊂ P × P Insieme di coppie di nodi con vincoli di precedenza
Tij Tempo richiesto per eettuare la visita j ∈ N dopo la
visita i ∈ N
xkij Variabile binaria di routing, è 1 se il veicolo k ∈ O
percorre l'arco (i, j) ∈ A, 0 altrimenti
t0ik Variabile di scheduling, indica il tempo necessario al
veicolo k ∈ O per arrivare al paziente i ∈ P
Wijk Variabile sperimentale, può essere considerata di
valore uguale a tij o Di a seconda dei casi
Modello min wP X k∈O X (i,j)∈A cikxkij + wT X k∈O X (i,j)∈A tijxkij + wB (2.107) X k∈O X j:(i,j)∈A xkij = 1 ∀i ∈ P (2.108) X j:(o,j)∈A xkoj = X j:(j,d)∈A xkjd = 1 ∀k ∈ O (2.109) X j:(i,j)∈A xkij− X j:(j,i)∈A xijd = 0 ∀i ∈ P, ∀k ∈ O (2.110) t0ik+ (tij+ Di)xkij ≤ t0jk+ βi(1 − xkij) ∀k ∈ O, ∀(i, j) ∈ A (2.111) αi X j:(i,j)∈A xkij ≤ t0ik ≤ βi X j:(i,j)∈A xkij ∀k ∈ O, ∀i ∈ P (2.112) αki ≤ t0ik ≤ βik ∀k ∈ O, ∀i ∈ {o, d} (2.113) X k∈O t0ik= X k∈O t0jk ∀(i, j) ∈ Psync (2.114) X k∈O t0ik≤ Tij + X k∈O t0jk ∀(i, j) ∈ Pprec (2.115) X (i,j)∈A Wijk1x k1 ij − X (i,j)∈A Wijk2x k2 ij ≤ w ∀k1∈ O, ∀k2∈ O\{k1} (2.116)
2.8 P. Eveborn, P. Flisberg, M. Rönnqvist.
LAPS CARE - an operational system for sta
planning of home care [11]
Viene descritto il sistema di supporto alle decisioni Laps Care. Mi limito a descrivere le fasi di modellazione e di testing, tralasciando l'interfaccia gra ca e i database.
La modellazione è stata basata sul modello di set partitioning[24]. Tale scelta è dovuta al fatto che si tratta solo lo scheduling, anche se la distanza percorsa in uisce sul costo. Per la risoluzione è stata utilizzata la meta-euristica repeated matching[25]. Il concetto di skill viene utilizzato, vengono trattate diverse tipologie, quali skill mediche, linguistiche etc. Sono previste visite multi-operatore e si opera rispettando la time window.
Gli spostamenti si possono dierenziare in base alla tipologia del mezzo di trasporto utilizzato, bicicletta, auto o a piedi. Il mezzo spesso dipende dal quartiere dove si opera.
La piani cazione è giornaliera, non sono dunque presenti i pattern. Ogni paziente ha il suo piano di cura personalizzato e viene rispettata la continuità di cura, quando possibile.
La funzione obiettivo ha il compito di minimizzare i costi. Per costi non si intende esclusivamente il costo in denaro, ma, secondo una certa con gurazione di pesi, vari fattori quali il tempo di spostamento, il costo del carburante, il rispetto dell'orario di visita etc. Tali dati sono raccolti nel database del sistema.
I test sono stati svolti su quattro istanze reali e ci si soerma sopratutto sui risultati forniti dal repeated matching all'incrementare delle iterazioni, mostrati accuratamente in degli istogrammi. Non sono presenti informazioni riguardo la risoluzione computazionale del modello matematico. Sono stati usati due diversi metodi per il repeated matching: Exact Method e Repeated Assignment. Non è stato possibile stabilire quale fosse migliore tra i due poichè i risultati variano di istanza in istanza.
I miglioramenti sono stati del 7% sul tempo di lavoro e del 20% sui tempi di spostamento rispetto ai valori della soluzione reale adottata.
Modello proposto
Notazioni - Scheduling O Insieme di operatori
Jk Insieme di elenchi compatibili con l'operatore k ∈ O
V Insieme di visite
xkj Variabile binaria, è 1 se l'operatore k ∈ O usa l'elenco j ∈ Jk, 0 altrimenti
ckj Costo per l'utilizzo dell'elenco j ∈ Jk da parte
dell'operatore k ∈ O
ykjv Variabile binaria, è 1 se l'operatore k ∈ O eettua la visita v ∈ V nell'elenco j ∈ Ji
Notazioni - Repeated Matching
A = a1, ..., ak Insieme di elementi su cui verrà fatto il matching
dij Costo del matching tra ai ∈ Ae aj ∈ A
zij Variabile binaria, è 1 se avviene il matching tra ai ∈ A
Modello - Scheduling min z =X k∈O X j∈Jk cijxkj (2.117) X j∈Jk xkj = 1 k ∈ O (2.118) X k∈O X j∈Jk yjvkxkj = 1 v ∈ V (2.119) xkj ∈ {0, 1} k ∈ O, j ∈ Jk (2.120)
Modello - Repeated Matching min k X i=1 k X j=1 dijzij (2.121) k X j=1 zij = 1 i = 1, ..., k (2.122) k X i=1 zij = 1 j = 1, ..., k (2.123) zij = zji i, j = 1, ..., k (2.124) zij ∈ {0, 1} i, j = 1, ..., k (2.125)
2.9 Ulteriori lavori in ambito Home Care
P.M. Koeleman, S. Bhulai, M. van Meersbergen.
Optimal patient and personnel scheduling policies for care-at-home service facilities [3]
Viene trattato lo scheduling dei pazienti secondo catene di Markov[26]. I pazienti vengono classi cati in gruppi, caratterizzati dal numero di ore di visita necessarie.
I pazienti che non possono essere schedulati possono essere messi in lista di attesa o ri utati. In base a ciò vengono proposte due varianti del modello: con o senza lista di attesa.
Funzione obiettivo: minimizza il numero di pazienti ri utati o rimandati. Dalla sperimentazione risulta che vengono schedulati prima i pazienti con il minor periodo di cura previsto.
Le prove sono state svolte con o senza euristiche. Le prove euristiche distano dalla soluzione ottima per valori che vanno dallo 0,52% allo 1,82%. Non abbiamo informazioni se le prove sono relative a casi reali o generati e sono in numero limitato (solo 5).
E. Lanzarone, A. Matta.
A cost assignment policy for home care patients [14]
Viene presentato uno studio sull'ammissione in un sistema di Home Care di nuovi pazienti e su come questi siano assegnati ad i relativi operatori di riferimento.
Inizialmente ad ogni operatore viene associato un carico di lavoro dal valore stocastico. Vengono considerate nell'analisi dei costi solo le visite che vengono eseguite in aggiunta a quelle previste nella piani cazione. Il costo iniziale di un operatore è cacolato in base ad una funzione alla base del carico di lavoro e della capacità massima. Quando un nuovo paziente viene introdotto nel sistema lo si assegna all'operatore disponibile con costo più basso. L'obiettivo è quello di minimizzare tale incremento di costo, sia nel caso deterministico che stocastico.
Vengono dimostrati diversi lemmi e teoremi sui quali si basano le politi-che di assegnamento del sistema. L'enunciato del teorema generale stabilisce che un paziente deve essere assegnato all'operatore con costo più basso e disponibilità più alta, indipendentemente dalla domanda del paziente. Se-guendo questo principio si ha come conseguenza, oltre al risparmio dei costi, anche un bilanciamento dei carichi di lavoro. Vale la pena citare [15], in cui viene presentato in due pagine, concisamente, il problema appena descritto ed una sua applicazione pratica.
