Capitolo 5
Conclusioni
In questo lavoro di tesi è stato presentato il problema dei cammini bilanciati
node-disjoint nel caso di reti acicliche, ne è stata studiata una generalizzazione al caso di grafi
di input generici ed è stata progettata e implementata una famiglia di algoritmi euristici che guida efficientemente nella ricerca di soluzioni di buona qualità.
Sono state descritte le principali scelte implementative effettuate nella fase di progetta-zione e realizzaprogetta-zione dell’approccio euristico e tre distinte versioni utilizzate nella fase di sperimentazione.
Nel quarto capitolo sono stati messi in evidenza i punti di forza e i punti critici dell’ap-proccio euristico proposto mettendo a confronto i risultati ottenuti mediante il nostro software con quelli ottenuti mediante il solutore commerciale CPLEX.
Su 162 istanze del problema risolte nel 61% dei casi la versione esatta dell’approccio euristico “con time limit di un’ora” ha prodotto la soluzione ottima in tempi minori di CPLEX. Nella versione “con scaling dei costi” nell’88% dei casi esiste almeno un valo-re del parametro ε tra quelli testati in corrispondenza del quale il nostro softwavalo-re ha pro-dotto la soluzione ottima in tempi minori o uguali a CPLEX; tale versione dell’approccio euristico si è quindi rivelata molto efficiente per trovare e certificare più rapidamente delle altre versioni soluzioni ottime e inoltre è risultata essere uno strumen-to efficace per la generazione di buone e molteplici soluzioni ammissibili.
Tutte le versione dell’approccio euristico testate, sulle 162 istanze risolte, nel 97% dei casi hanno prodotto una soluzione ammissibile iniziale in tempi estremamente rapidi (in media 0.01 secondi).
5.1 Ulteriori sviluppi
Durante la fase di sperimentazione abbiamo provato ad usare il software prodotto per generare i turni di lavoro per i membri dell’equipaggio di una linea aerea in un dato o-rizzonte temporale. Come riportato in [5], il problema della generazione dei turni può essere formulato come un problema di cammini bilanciati node-disjoint, e si può quindi pensare di utilizzare l’approccio euristico proposto per determinare dei turni di lavoro in cui il carico di lavoro sia distribuito tra i membri dell’equipaggio in maniera equilibrata. In particolare, nel caso di studio analizzato si devono stabilire i turni di k piloti di una compagnia aerea in un orizzonte temporale predefinito di un mese. Il problema può es-sere modellizzato mediante un grafo orientato aciclico i cui archi rappresentano le attivi-tà da svolgere; il costo associato ad ogni arco indica le ore di servizio richieste dall’attività che l’arco stesso rappresenta. Ogni cammino su tale grafo, a partire da un nodo che rappresenta l’inizio del turno di un pilota fino ad un nodo che rappresenta in-vece la fine del turno, descrive il turno di uno dei k piloti per il mese in analisi, e il costo del cammino rappresenta le ore di servizio totali richieste dal turno. Il bilanciamento dei
k cammini cercati serve per garantire che non ci siano grandi disparità nel numero di ore
di servizio svolte dai k piloti: si vuole cioè che i piloti siano tutti impegnati più o meno per lo stesso numero di ore.
La sperimentazione preliminare condotta su questo caso di studio ha individuato alcuni punti critici, che pensiamo richiedano una variante dell’approccio euristico che sia “ad hoc” per questa specifica applicazione.
I problemi riscontrati sono legati al fatto che, in questo contesto, i cammini in realtà de-vono essere parzialmente disgiunti perché ci sono attività, come i giorni di riposo, che possono essere svolte da più piloti. Ciò significa che gli archi che rappresentano tali at-tività possono essere comuni a più cammini e, nella fase di colorazione del grafo, ad es-si deve essere assegnato il colore neutro. Il numero di tale archi nel grafo di input è ele-vato e lo è a maggior ragione nel grafo espanso. Nell’attuale implementazione dell’algoritmo di programmazione dinamica utilizzato nel software per il calcolo di cammini minimi vincolati, descritto in 3.2, questo genera problemi di occupazione di memoria non indifferenti. Per poter utilizzare l’approccio euristico per questo caso di
studio è quindi necessario progettare, nell’algoritmo di programmazione dinamica, una diversa gestione delle etichette associate a quei nodi del grafo espanso che hanno colore neutro. Tale progetto e relativa implementazione potrebbero risultare un interessante sviluppo dei risultati contenuti in questo lavoro di tesi.
Inoltre, in questo caso di studio, occorre trattare una serie di vincoli imposti dalla nor-mativa della compagnia di trasporto e occorrerebbe anche massimizzare la copertura delle attività.
