In questa sezione mostriamo come il modello appena presentato rappresenta una generalizza- zione di svariati problemi d’instradamento NP-Hard. Ne segue che l’HHCP eredita la notevole complessità computazionale necessaria per trovare soluzioni ammissibili, ottime o bound.
1.3.1
Multiple Traveling Salesman Problem
Visitare tutti i nodi di un grafo una e una sola volta è detto “problema del ciclo hamiltoniano”. Se il grafo è pesato, ossia ad ogni arco corrisponde un peso, trovare tra tutti i cicli hamilto- niani quello di costo minore è detto “problema del commesso viaggiatore” (Traveling Salesman Problem, TSP). Se il nodo di partenza può essere visitato più di una volta, allora il problema è detto multiple Traveling Salesman Problem (m-TSP) (Bektas, 2006).
Riduciamo l’HHCP ad un m-TSP impostando come segue i parametri: con Wmax = ∞non
si limita il tempo di viaggio di un singolo turno; con α0 = α1 = α2 = 0 e α3 = 1 si desidera
minimizzare solo il tempo totale di viaggio; fs= 1 e es= −1 richiedono che un servizio è svolto
una volta sola; per avere massima disponibilità, potendo svolgere sempre il servizio in qualsiasi giorno della settimana, gh
s = 1 ∀s∀h.
In letteratura, ci sono varie trasformazioni che permettono di ricondurre l’m-TSP al TSP nelle diverse varianti relative a diverse proprietà del grafo di partenza (Lenstra e Rinnooy Kan, 1975; Hong e Padberg, 1977; Rao, 1980; Jonker e Volgenant, 1988; Laporte e Nobert, 1980; Bellmore e Hong, 1974). Queste trasformazioni permettono di avvalersi di efficienti risolutori ad hoc per il TSP (Applegate et al., 2006).
1.3.2
Distance Constrained Vehicle Routing Problem
Il problema di instradamento di veicoli con capacità (Capacited Vehicle Routing Problem; CVRP), è un m-TSP ove ad ogni veicolo è associata una capacità che non deve essere superata (Toth e Vigo, 2001). Invece, quando abbiamo un m-TSP con un tempo limite L per tornare al deposito allora ci si riferisce al problema dell’instradamento di veicoli con distanza vinco- lata (Distance Constrained Vehicle Routing Problem; DVRP) (Laporte et al., 1987). Poiché il problema dell’instradamento dinamico di veicoli (Dynamic Vehicle Routing Problem), con omonima sigla, ha ricevuto maggiore attenzione in letteratura, è usuale riferirsi al DVRP come al problema d’instradamento con capacità e distanza vincolata (Distance Constrained Capaci- ted Vehicle Routing Problem; DCVRP) (Laporte et al., 1985), rilassando il vincolo di capacità.
1.3 Sottoproblemi Uniformandoci alla letteratura, in questo lavoro al posto di DVRP useremo il termine DCVRP sottintendendo il rilassamento del vincolo di capacità. L’HHCP può essere ridotto al DCVRP con gli stessi parametri usati per l’m-TSP e con Wmax = 0, per limitare i tempi di viaggio
totali dei tour.
Il DCVRP è un problema dove ad ogni nodo corrisponde una stessa finestra temporale di visita [0, L]. La generalizzazione del DCVRP è data da un problema d’instradamento con finestre temporali (Vehicle Routing Problem with Time Windows; VRPTW) (Kolen et al., 1987), dove le finestre temporali relative ai nodi sono di dimensioni eterogenee. Riguardo alla ricerca di un lower bound per il DCVRP la letteratura è molto limitata. Al meglio della nostra conoscenza, non esiste un riscontro del successo dell’applicazione al DCVRP dei metodi ottimi, o di approssimazione, proposti per il VRPTW, sebbene quest’ultimo problema abbia ricevuto maggiore attenzione.
Come confermano altri autori (Mendoza, 2009), abbiamo constatato che, dal 1985 ad oggi, il DCVRP ha avuto scarsa attenzione in letteratura. Tuttavia, nella nostra esperienza (Boccafoli et al., 2011) il problema trova svariate applicazioni reali derivate dal rispetto dei limiti di tempo di lavoro. Sebbene esistano proposte che affrontano la soluzione del problema DCVRP mediante approcci euristici, è arduo comprendere a priori la bontà di un metodo, poiché l’insieme delle istanze di un caso reale raramente presenta le stesse caratteristiche di un altro caso reale.
Talvolta, il vincolo della massima durata di un turno è incluso in un modello con finestre temporali (Steeg, 2008). In questo caso, rispetto al DCVRP il dominio delle soluzioni diminuisce poiché il limite viene assorbito dalla finestra temporale [lv, uv]del nodo v, in quanto la finestra
temporale [0, L] è l’elemento neutro dell’operazione di intersezione: [lv, uv] ∩ [0, L] = [lv, uv].
In altre parole, un VRPTW con vincolo di massima durata del turno L mantiene la stessa complessità di un VRPTW. Diversamente, si osservi che nell’HHCP, fissando il giorno di ciascun servizio, per ogni giornata il sottoproblema è un DCVRP: pertanto, la disponibilità del giorno di servizio gh
s, che condiziona il valore di yjhs nel vincolo (1.16), non riduce la complessità del
sottoproblema di DCVRP.
1.3.3
Periodic Vehicle Routing Problem
Il problema d’instradamento periodico di veicoli (Periodic Vehicle Routing Problem; PVRP) è un problema di instradamento nel quale il servizio viene ripetuto più volte in un orizzonte temporale (Tan e Beasley, 1984; Mourgaya e Vanderbeck, 2006). Per ridurre l’HHCP al PVRP occorre impostare i parametri come segue: si minimizza solo il tempo totale di viaggio (ponendo α0 = α1 = α2 = 0 e α3 = 1), non si impone un tempo limite per turno (Wmax = ∞), non si
prevede alcun intermezzo prima di una ripetizione (es = −1). La disponibilità ghs è compresa in
molti modelli del PVRP, tuttavia è usuale semplificare il modello scegliendo di svolgere sempre il servizio in qualsiasi giorno della settimana, cioè assume gh
s = 1 ∀s∀h.
In due articoli recenti (Mourgaya e Vanderbeck, 2007; Francis et al., 2008), il metodo della generazione di colonne è stato proposto per risolvere in modo esatto il problema PVRP. Per la potenza di calcolo attualmente a disposizione, è improponibile applicare tale metodo al
1. IL PROBLEMA DELL’ASSISTENZA SANITARIA DOMICILIARE
sottoproblema del HHCP, perché qui le dimensioni delle istanze dei casi reali sono cinque o sei volte più grandi.
Sovente la generalizzazione dei problemi aggiunge vincoli e variabili, che la rendono inap- plicabile per l’aumento sensibile delle dimensioni della matrice dei vincoli. Ad esempio, in Ribeiro e Ramalhinho Dias Lourenço (2001) modellano una generalizzazione del PVRP, il Mul- ti Objectives Multi Period Distribution Management Problem. Gli autori documentano che non hanno ottenuto soluzioni ammissibili dopo due giorni di calcolo con un istanza minimale (|H| = 4, |N| = 2, |P | = 5). In altre circostanze, il metodo di programmazione matematica è inapplicabile al caso reale poiché le proprietà che lo caratterizzano, ad esempio disuguaglianza triangolare, non sono mantenute.
Oltre alle prime euristiche per il PVRP (Tan e Beasley, 1984; Christofides e Beasley, 1984), ne sono state proposte altre, tra le quali citiamo l’approccio multifase (Russell e Gribbin, 1991), il tabu search (Cordeau et al., 2001), il VNS (Hemmelmayr et al., 2009), l’ALNS e programmazione vincolata (Costraing Programming, CP) (Steeg, 2008).
Capitolo 2
Carico di lavoro
Nell’ambito di attività a contatto con il pubblico, l’aspetto dell’esaurimento da lavoro, conosciu- to come fenomeno di burnout, richiede particolare attenzione. L’osservazione di tale fenomeno in psicologia ha trovato correlazione con varie cause e dà origine a svariate conseguenze. Parti- colarmente delicato è il contesto delle cure mediche, dove l’operatore è a contatto con persone e con malattie (Deckard et al., 1994). Tra le conseguenze del fenomeno c’è il degrado emotivo, che si riperquote in famiglia e sul lavoro. La quantità di persone incontrate, la quantità di tempo lavorativo medio settimanale e la rotazione del personale, sono tra le cause del fenome- no. La priorità data alla qualità delle vite dell’operatore e del paziente si traduce nell’avere come obiettivi primari la limitazione della quantità di ore di straordinario e il bilanciamento del carico di lavoro del personale.
Vi sono varie metriche per misurare il carico di lavoro (Hughes, 1999). Alcuni lavori (Proc- ter, 1992; Vitacca et al., 2000) osservano la correlazione tra il carico di lavoro ed il tempo lavorativo, e motivano l’interesse della gestione di questo aspetto. In questa sezione mostriamo le formulazioni del carico di lavoro (workload) nei vari settori, osservando quali di esse sono opportune per l’HHCP.
2.1
Contesto generale
Da almeno tre decenni (Stecke, 1983), la pianificazione è l’ambito applicativo dove il carico di lavoro suscita maggiore interesse, come dimostra l’ampia letteratura. Il settore più astratto della pianificazione spazia tra problemi di base, ad esempio i problemi di zaino (Martello e Toth, 1990; Mathur, 1998), e problemi arricchiti, ad esempio on-line load (Azar, 1998). Le applicazioni in casi reali sono svariate, come la distribuzione del carico di lavoro in una rete di computer (Rajakumar et al., 2004), o la distribuzione dell’elettorato (Bozkaya et al., 2003). Non esiste una nomenclatura uniforme. Talvolta è possibile trovare lavori nei quali al posto di ‘bilanciamento’ vengono usati i termini: “distribuzione uniforme”, “equiripartizione”, “equilibrio” (Blais et al., 2003). Esistono proposte di gestione del carico di lavoro applicabili a settori differenti: ad esempio l’equilibrio della distribuzione dell’elettorato in un distretto (Bozkaya et al., 2003) è applicato all’equilibrio del carico di lavoro nel servizio di assistenza sanitaria a domicilio
2. CARICO DI LAVORO
(Blais et al., 2003). Una sintesi della varietà di modelli per bilanciare il carico di lavoro può essere riassunta nelle tecniche riportate in recenti lavori per l’identificazione e la descrizione di vincoli per la programmazione vincolata (Pesant e Régin, 2005; Monette et al., 2007; Schaus et al., 2007), alle quali si aggiunge un approccio stocastico (Lanzarone e Matta, 2011). Occorre tuttavia entrare nel dettaglio per valutare l’applicabilità di tali metodi all’HHCP.
Una prima indagine è stata svolta nel campo della pianificazione dei turni delle infermiere (Nurse Rostering Problem), nel quale non si tiene conto della parte di routing. L’articolo di Ibrahim et al. (2010) aggiunge il riferimento ad alcune euristiche relative al bilanciamento di carico (Burke et al., 2004). Spesso i metodi sono relativi alla turnazione di un servizio in strutture ospedaliere, pertanto non gestiscono i tempi di spostamento tra pazienti. Il carico di lavoro è inteso talvolta come quantità di turni svolti in un orizzonte temporale, talvolta come numero di pazienti assegnati (Lahrichi, 2008), altre volte come tempo di lavoro.
Il carico di lavoro per l’HHCP ha ricevuto attenzione sin dai primi articoli (Begur et al., 1997b). Tuttavia, la complessità di gestire la soluzione di due sottoproblemi NP-Hard richiede spesso un’approssimazione, come per esempio l’uniformità dei tempi di viaggio e di servizio (Borsani et al., 2006), che porta a gestire il bilanciamento come quantità di servizi svolti. Nel seguito di questa sezione, riportiamo alcune tecniche modellistiche usate per problemi d’instradamento, osservando la loro applicabilità all’HHCP.