L'esecuzione di CPLEX può terminare secondo varie circostanze. L'esecuzio- ne si arresta quando viene trovata la soluzione ottima oppure viene esaminato tutto lo spazio di ricerca.
L'utente può de nire delle circostanze di terminazione de nendo dei limi- ti. Possono garantire la terminazione i limiti imposti al tempo di esecuzione, al numero di nodi, alla dimensione dell'albero di branching e al numero di soluzioni intere.
I parametri corrispondenti a tali limiti vengono riassunti nella seguente tabella.
Risorsa da limitare Parametro della Concert Technology
Tempo di esecuzione TiLim
Dimensione dell'albero di branching TreLim
Numero di nodi NodeLim
Appendice B
Sviluppo
B.1 Struttura del codice
Il codice è stato scritto nella sua interezza in C++. Sono state utilizzate le librerie di CPLEX, facenti parte della Concert Technology, introdotta in Appendice A.
I dati sono stati organizzati secondo una struttura ad oggetti.
A partire dal le testuale in input descritto nella Sezione 3.3 vengono in primo luogo assegnate a variabili globali le dimensioni dell'insieme dei pazienti, degli operatori, dei comuni e dei pattern.
Successivamente si passa ad istanziare gli oggetti Paziente, Operatore e Pattern.
Paziente
Vengono istanziati per primi secondo l'ordine del le testuale. I parametri del costruttore sono esattamente i dati forniti dalle righe relative ai pazienti in input. I pazienti istanziati saranno allora organizzati in array di puntatori ad oggetti Paziente. Ogni oggetto paziente avrà a disposizione i metodi get per fornire i dati necessari al codice.
Operatore
Successivamente verranno istanziati gli operatori in maniera del tutto simile ai pazienti. Inoltre ad ogni operatore verrà assegnato un array di 5 valori binari, allo scopo di indicare i giorni di disponibilità lavorativa. Abbiamo assunto in tutte le prove che gli operatori siano sempre disponibili.
Pattern
è l'array a 5 valori relativo alla piani cazione settimanale. L'oggetto Pat- tern avrà un metodo get che, dato in input un intero da 1 a 5, restituisce il valore del pattern nel giorno corrispondente. Sono presenti inoltre metodi per fornire il numero di visite di skill 1 e 2 relative al pattern.
Viene inoltre presa la tabella dei tempi di spostamento e memorizzata in un array bidimensionale. È stato implementato un metodo per selezionare il tempo di percorrenza da due identi catori di comune associati ai pazienti, che corrisponderanno univocamente agli indici di riga e colonna della tabella. Avendo tutte le istanze degli oggetti a disposizione si passa alla genera- zione del modello. Fino a questo punto non sono state necessarie le librerie della Concert Technology, trattandosi di codice C++ nella sua versione più classica.
Secondo quanto previsto dalla Concert Tecnology il primo passo della co- struzione di un modello consiste nell'inizializzazione delle variabili. Secondo opportuni metodi sono state create volta per volta tutte le famiglie necessa- rie, speci candone la loro quantità, a dando loro la corretta nomenclatura e i corretti indici e impostandone eventuali valori di minimo e massimo. Poi- chè i modelli testati sono modelli di Programmazione Lineare Intera (PLI) gran parte delle variabili saranno di tipo intero e avranno di conseguenza il tipo IloInt.
Si passa quindi alla generazione dei vincoli.
È stato implementato un metodo per ciascuna famiglia di vincoli. Il procedimento generale consiste nell'annidamento di cicli for secondo i quan- ti catori di ciascuna famiglia di vincoli, generando un vincolo per ciascuna iterazione. Ad esempio un vincolo che deve essere soddisfatto per ogni ope- ratore equivale ad un vincolo generato per ogni iterazione di un ciclo for che itera sul numero di operatori.
A ciascun vincolo sarà assegnato un identi catore che ne denota la fami- glia ed un indice numerico.
Similmente ai vincoli viene creata la funzione obiettivo. Esclusivamente in questo caso le due variabili utilizzate, m e v, non vengono de nite intere, avranno quindi tipo IloNum. I metodi sono simili a quellu utilizzati per la generazione dei vincoli, ma viene speci cato se è un problema di minimo o massimo secondo i ag IloMinimize o IloMaximize.
Solo dopo aver generato i vincoli e la funzione obiettivo vengono deallocate le risorse dedicate agli oggetti.
A questo punto viene invocato il solver per la risoluzione del modello. Il solver seguirà un comportamento dettato dall'impostazione di opportuni parametri, quali, ad esempio, durata della prova o allocazione della memoria
di lavoro.
Non sono stati modi cati parametri relativi alle politiche di branching o agli algoritmi utilizzati per trovare le soluzioni, seguendo le impostazioni di default di CPLEX.
Dopo aver terminato l'esecuzione vengono creati due le testuali, uno che fornisce il modello relativo all'istanza, e l'altro che fornisce i valori assegnati alle variabili per la miglior soluzione trovata. Il secondo le è molto utile se si vogliono analizzare i tour intrapresi dagli operatori e le assegnazioni dei pattern.
Conclusioni
In questo lavoro sono stati presentati dei modelli di Programmazione Lineare Intera formulati allo scopo di risolvere problemi di Home Care. Tali problemi assumono un ruolo sempre più importante nell'ambito dell'ottimizzazione in campo sanitario. Prova di ciò ne sono i tanti articoli che vengono pubblicati negli ultimi anni, con frequenza sempre maggiore.
Sono stati visionati diversi lavori attinenti e, come dimostrato dalle pro- ve, sebbene la formulazione non sia mai stata trattata nello stesso modo, i risultati ottenuti sono decisamente soddisfacenti. Sono comunque previste prove che sfruttano l'utilizzo di tecniche euristiche e tecniche di ottimizza- zione per ridurre i costi delle computazioni.
È evidente che con opportune modi che i modelli proposti si possano adat- tare per risolvere problemi relativi ad altri contesti, come ad esempio la distribuzione di merci o la salvaguardia dell'ambiente.
Possono essere integrate varie componenti, traendo spunto dalle necessità speci che delle situazioni, quali la gestione della sindrome da burn-out, do- vuta allo stress che possono causare allontanamenti da parte degli operatori o la presenza di diversi livelli di skill, ad esempio oltre alla quali ca infermie- ristica si può considerare l'idoneità a guidare determinate categorie di veicoli. Gli eventuali sviluppi futuri propongono innumerevoli scenari alternativi, che grazie alle tecnologie attuali possono essete studiati con maggiore e cienza rispetto al passato, anche recente.
Ringraziamenti
Un ringraziamento speciale va alla mia famiglia, che mi ha sempre supporta- to (e sopportato), sia moralmente che materialmente, negli anni relativi agli studi universitari ed in particolare nel periodo di tesi.
Ringrazio la Prof.ssa Maria Grazia Scutellà per avermi seguito costantemen- te nei mesi relativi al lavoro, sapendo fornire il giusto materiale per darmi una adeguata preparazione sugli argomenti trattati e la pazienza dimostrata nei miei momenti di di coltà.
Ringrazio la Prof.ssa Paola Cappanera, senza la quale non avrei mai do- mato quel mostro che si è rivelato essere il solver CPLEX.
Meritano un ringraziamento anche il Prof. Andrea Matta del Politecnico di Milano, per avermi illustrato la situazione dell'Home Care in Italia ed avermi messo in contatto con il Dott. Ettore Lanzarone e il Dott. Semih Yalcindag, che ringrazio in egual misura per avermi fornito i dati su cui ho generato le istanze per il mio lavoro.
Un ultimo ringraziamento va a qualsiasi lettore di questa tesi, sperando che il mio lavoro possa essergli stato di aiuto.
Bibliogra a
[1] A. Trautsamwieser, M. Gronalt, P. Hirsch. Securing home health care in times of natural disasters. Springer-Verlag, OR Spectrum, 2011. [2] M. S. Rasmussen, T. Justesen, A.Dohn, J. Larsen. The Home Care
Crew Scheduling Problem: Preference-Based Visit Clustering and Tem- poral Dependencies. Department of Management Engineering, Technical University of Denmark, 2010.
[3] P.M. Koeleman, S. Bhulai, M. van Meersbergen. Optimal patient and personnel scheduling policies for care-at-home service facilities. University of Amsterdam, Faculty of Sciences, 2011. To appear in EJOR.
[4] E. Cheng, J.L Rich. A Home Health Care Routing And Scheduling Problem. Department of Mathematical Sciences, Oakland University, 1998.
[5] C. Akjiratikarl, P. Yenradee, P. R. Drake. PSO-based algorithm for home care worker scheduling in the UK. Computers & Industrial Engineering, 53, pp. 559583, Elsevier, 2007.
[6] S. V. Begur, D. M. Miller, J. R. Weaver. An Integrated Spatial DSS for Scheduling and Routing Home-Health-Care Nurses.INTERFACES, 27, pp. 358, INFORMS, 1997.
[7] S. Bertels, T. Fahle. A hybrid setup for a hybrid scenario: combining heuristics for the home health care problem. Computers & Industrial Engineering, 33, pp. 28662890, Elsevier, 2006.
[8] D. Bredström, M. Rönnqvist. Combined vehicle routing and scheduling with temporal precedence and synchronization constraints. Division of Optimization, Linköping Institute of Technology, Department of Fi- nance and Management Science, Norwegian School of Economics and Business Administration, 2006.
[9] S. Chahed, E. Marcon, E. Sahin, D.Feillet, Y.Dallery. Exploring new operational research opportunities within the Home Care context: the
chemotherapy at home. Health Care Manag Sci, 12, pp. 179191, Springer, 2009.
[10] B. Elbenani, J.A. Ferland, V. Gascon. Mathematical Programming Ap- proach for Routing Home Care Nurses. Industrial Engineering and Engineering Management, pp. 107111, 2008.
[11] P. Eveborn, P. Flisberg, M. Rönnqvist. LAPS CAREan operational system for sta planning of home care. European Journal of Operational Research, 171, pp. 962976, Elsevier, 2006.
[12] Y. Kergosien, C. Lenté, J. Billaut. Home health care problem An ex- tended multiple Traveling Salesman Problem. Multidisciplinary Interna- tional Conference on Scheduling : Theory and Applications (MISTA 2009), 2009.
[13] K. Thomsen. Optimization on Home Care. Tesi M.Sc., Department of Informatics and Mathematical Modelling, Technical University of Denmark, 2006.
[14] E. Lanzarone, A. Matta. A cost assignment policy for home care patients. Springer Science+Business Media, LLC 2011.
[15] E. Lanzarone, A. Matta. Stochastic assignment of patients in home care services. Dipartimento di Meccanica, Politecnico di Milano, 2011. [16] E. Lanzarone, A. Matta, G. Scaccabarozzi. A patient stochastic model
to support human resource planning in home care. Production Planning & Control, 21, pp. 325, Taylor & Francis, 2010.
[17] V. Borsani, A. Matta, G. Beschi, F. Sommaruga. A Home Care Scheduling Model For Human Resources. Service Systems and Service Management, pp. 449454, 2006.
[18] M. Blais, S. D. Lapierre, G. Laporte. Solving a home-care districting pro- blem in an urban setting. Journal of the Operational Research Society, 54, pp. 11411147, Palgrave, 2003.
[19] R. Baldacci, E. Bartolini, A. Mingozzi, R. Roberti. An exact solution framework for a broad class of vehicle routing problems. Comput Manag Sci, DOI 10.1007/s10287-009-0118-3, Springer-Verlag, 2009.
[20] P. Cappanera, L. Gouveia, M. G. Scutellà. The skill vehicle routing problem. INOC'11 Proceedings of the 5th international conference on Network optimization, ISBN: 978-3-642-21526-1, Springer-Verlag, 2011. [21] S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi. Optimization by Simulated
[22] D. Cvijovic, J. Klinowski. Taboo search - an approach to the multiple minima problem. Science, 267, pp. 664666, 1995.
[23] N. Mladenovic, P. Hansen. Variable Neighborhood Search. Computers Ops Res, 24, pp. 10971100, Elsevier, 1995.
[24] R. S. Gar nkel, G. L. Nemhauser. The Set-Partitioning Problem: Set Covering With Equality Constraints. Operations Research, 17, pp. 848 856, 1969.
[25] P. Wark, J. Holt. A Repeated Matching Heuristic for the Vehicle Routing Problem. The Journal of the Operational Research Society, 45, pp. 1156 1167, 1994.
[26] O. Häggström. Sequencing and scheduling: Algorithms and complexity, in logistics of production and inventory. Cambridge University press, 2002.
[27] E.L. Lawler, J.K. Lenstra, A.H.G. Rinnoy-Kan, and D.B. Shmoys. Fi- nite Markov Chains and Algorithmic Applications. Handbooks in Ope- rations Research and Management Science, vol. 4, Graves, Rinnoy Kan and Zipkin (Eds.), Elsevier Science Publishers, 1993, pp. 445522. [28] M. Gendreau, A. Hertz, G. Laporte, M. Stan. A Generalized Inser-
tion Heuristic for the Traveling Salesman Problem with Time Windows. Operations Research, vol. 46, no. 3, pp 330-335, 1998.
[29] A. H. Land, A. G. Doig. An automatic method of solving discrete programming problems. Econometrica, 28, pp. 497520, 1960.
[30] G. Cornuejols. Revival of the Gomory Cuts in the 1990s. Annals of Operations Research, Vol. 149, pp. 6366, 2007.