Prove al crescere della percentuale di visite di skill 2

Qui vengono mostrate, analogamente alla precedente sezione, le prove al cre- scere della percentuale di visite di skill 2. Tali visite sono state generate in modo random a partire dal numero di visite ricavato dal consuntivo. In totale sono state create 3 istanze su cui sono state eettuate le prove sia con la funzione obiettivo descritta nel Paragrafo 1.3.5 (1, 3 e 5) che con la funzione obiettivo descritta nel Paragrafo 1.3.6 (2, 4 e 6). Per la generazione dei pattern è stata utilizzata la stessa procedura descritta nella Sezione 3.2, che denisce un pattern casualmente ogni quattro occorrenze di una certa coppia di visite.

Per tutte le prove sono stati allocati 10 GB per l'albero di branching, dei quali sono stati utilizzati solo 0.01 MB nelle istanze lanciate con la funzio- ne obiettiva originale, mentre rispettivamente 96.43 MB e 1673.88 MB nelle istanze 10 e 12. La durata è di 3 ore in tutti i casi.

In Tabella 3.14 vengono elencate le dimensioni delle istanze selezionate, in- dicate come numero di pazienti, di operatori di skill 1, di operatori di skill 2, di pattern e la percentuale delle visite di skill 2 generate.

Istanza Pazienti Op. Skill 1 Op. Skill2 Pattern % Visite Skill

9 129 8 3 13 10 10 129 8 3 13 10 11 129 8 3 15 20 12 129 8 3 15 20 13 129 8 3 16 30 14 129 8 3 16 30

Tabella 3.14: Dimensione istanze relative alla prima settimana di Gennaio 2006 con visite di skill 2 generate a caso

La Tabella 3.15 indica i valori ottenuti dalla risoluzione delle istanze selezionate. Tutte le prove sono terminate con esito positivo, ad esclusione della prova 13 della quale viene risolto solo il rilassamento continuo. Nessuna soluzione è stata certicata dal solver come soluzione ottima.

Le colonne indicano: l'indice di istanza, il tempo necessario per risolvere il rilassamento, il valore della funzione obiettivo del rilassamento, il valore della funzione obiettivo, il coeciente di utilizzo degli operatori e il gap tra la soluzione del problema e del suo rilassamento.

Istanza Tempo Ril. F.O. Ril F.O. Int m Gap

9 2443.63 sec 0.2904 0.286667 0.286667 1.30%

10 2173.08 sec 25.1867 24.5417 0.285417 2.63%

11 1281.61 sec 0.2897 0.28875 0.28875 0.32%

12 4347.14 sec 25.0620 24.6833 0.286667 1.53%

13 1032.35 sec 0.2551 no sol. no sol. no sol.

14 851.70 sec 22.0267 21.7333 0.254167 1.35%

Tabella 3.15: Dettagli rilassamento continuo e soluzione intera In Tabella 3.16 vengono mostrate le dimensioni dei modelli generati dal solver. In questo caso particolare le dimensioni corrispondono esattamente per ogni coppia di prove relativa alla stessa istanza.

Le colonne sono relative al numero di righe, di colonne, di variabili bina- rie, di variabili generali, al tempo necessario per trovare i tagli e il numero di tagli candidati.

Istanza Righe Colonne Var. Binarie Var. Generali Tempo Tagli Candidati

9 89009 811279 737800 73478 20.19 sec 200 10 89020 811280 737800 73478 30.37 sec 200 11 86471 683966 611713 72252 20.16 sec 200 12 86506 683967 611713 72252 20.27 sec 200 13 91211 602463 524422 78040 20.23 sec 200 14 91222 602464 524422 78040 20.22 sec 200

3.8 Considerazioni

Nelle prove precedenti abbiamo eettuato delle sperimentazioni relative a diversi scenari. Allo stato attuale esistono pochi modelli che si occupano di problemi di scheduling e routing con orizzonti temporali di una settimana. Inoltre è stata fornita una formulazione che prevede l'utilizzo di pattern per stabilire i giorni esatti di visita ed un limite massimo di due operatori asse- gnati a ciascun paziente.

Le prove eettuate, considerando quelle con durata di 3 ore, hanno for- nito soluzioni il cui gap tra il valore della funzione obiettivo intera e del rilassamento continuo va dallo 0,34% al 2,63%.

In pochi casi non è stata trovata soluzione, ma spesso si tratta di casi particolari:

• Tabella 3.4, prova 6  Tale prova è relativa ad un'istanza di grandi dimensioni a cui è stato assegnato un tempo di 300 secondi. Si nota dalla prova 7 della stessa tabella, relativa alla stessa istanza, che il tempo necessario a risolvere il rilassamento continuo è maggiore dei 300 secondi assegnati.

• Tabella 3.6, prova 3  Tale istanza prevede un elevato numero di visite di skill 2, viene risolta nella prova 4 della medesima tabella incrementando di 1 il numero di operatori di skill 2.

• Tabella 3.6, prove 5 e 6  Prove con il 50% di richieste di tipo pallia- tivo, chiaramente irrisolvibili considerato l'esiguo numero di operatori specializzati.

• Tabella 3.10, prove 1 e 2  Istanze relative ad una settimana in cui nel caso reale molti operatori erano in ferie ed i pazienti in diversi casi vengono seguiti da 3 o più operatori.

• Tabella 3.13, prove 5 e 6  Prove relative alle stesse istanze citate sopra.

Solo la prova 13 di Tabella 3.15 non viene risolta in circostanze accettabili, ma in compenso viene risolta la prova 14, relativa alla stessa istanza, ma con la funzione obiettivo altenativa. La soluzione può essere considerata idonea anche per la prova 13, poichè sono presenti esattamente gli stessi dati in input, vale a dire operatori, pazienti e pattern.

Appendice A

CPLEX Concert Technology

A.1 Concert Technology utilizzando C++

Abbiamo scelto di fare uso delle librerie della Concert Technology usando il linguaggio C++.

Gli oggetti forniti nelle librerie possono essere divisi in due categorie: • Oggetti di Modellizzazione  Sono usati per denire il problema di

ottimizzazione. Generalmente un'applicazione crea diversi oggetti per specicare il problema. Tali oggetti vengono raggruppati in un oggetto IloModel che rappresenta il problema di ottimizzazione completo. • Oggetti IloCplex  Sono utilizzati per risolvere i problemi creati con gli

oggetti di modellizzazione. Un oggetto IloCplex legge un modello e ne estrae i dati per una rappresentazione appropriata per l'ottimizzatore. Quindi l'oggetto IloCplex è pronto per risolvere il modello estratto e può essere chiamato per fornire informazioni sulla risoluzione.

Dunque, le parti di modellizzazione e ottimizzazione di un'applicazio- ne sono rappresentati da un gruppo di oggetti C++ creati e controllati all'interno dell'applicazione stessa.

In Figura A.1 viene mostrata un'applicazione che utilizza CPLEX con Concert Technology per risolvere problemi di ottimizzazione.

Figura A.1: Schema tipico di un'applicazione CPLEX con Concert Technology

A.2 Struttura di un'applicazione Concert Techno-