Il problema dei cammini bilanciati ha interessanti applicazioni in diversi campi

Introduzione

In questa tesi si affronta il problema del calcolo di cammini bilanciati in una rete. Per dare un’idea iniziale al lettore, il problema in generale può essere così formulato:

data una rete G ai cui archi sono associati costi interi e non negativi

e dati un nodo origine s e un nodo destinazione t, si vogliono calcolare k cammini distinti da s a t in modo tale da minimizzare la differenza in costo tra il cammino più costoso e quello meno costoso.

Il problema ha diverse versioni che dipendono sia da proprietà del grafo G, che può es- sere orientato o non orientato, sia da proprietà che devono avere i k cammini cercati, ad esempio può essere richiesto che i cammini non abbiano alcun nodo o alcun arco in co- mune (si parla di cammini node-disjoint nel primo caso e arc-disjoint nel secondo).

Il problema dei cammini bilanciati ha interessanti applicazioni in diversi campi. Nel campo del trasporto ad esempio, spesso, per risolvere il problema della determinazione dei turni di lavoro settimanali o mensili dei membri di un equipaggio, si fa uso di grafi e di cammini per rappresentare i turni di lavoro. In questo caso, se il costo di un cammino rappresenta in qualche modo il carico di lavoro del turno ad esso associato, trovare k cammini bilanciati significa trovare dei turni per i membri dell’equipaggio in cui il cari- co di lavoro sia distribuito il più uniformemente possibile tra tutti i membri. Il costo di un turno può essere semplicemente la durata in tempo del turno stesso o può tenere in conto altri fattori come il numero di giorni di trasferta che questo richiede o il numero di soste necessarie per caricare e scaricare un dato mezzo di trasporto. Anche se i problemi di assegnamento dei turni possono differire da una compagnia di trasporto ad un’altra, ad esempio per le regole o per i costi presi in considerazione per rappresentare il carico di lavoro, la caratteristica che li accomuna è la necessità di assegnare i turni mensili o settimanali distribuendo il carico di lavoro tra i dipendenti in maniera bilanciata.

Tipici problemi di trasporto in cui è estremamente importante bilanciare il carico di la- voro sono l’assegnazione dei turni ai piloti nelle compagnie aeree o agli autisti nelle compagnie di trasporto pubblico urbano. Tuttavia il problema della distribuzione del ca- rico di lavoro non è tipico solo dei problemi di trasporto, ma si presenta in generale in tutti quei campi in cui bisogna assegnare i turni di lavoro di un dato orizzonte temporale ai membri di uno staff, come ad esempio a medici e infermieri negli ospedali.

Altro interessante campo di applicazione è quello delle reti di telecomunicazioni dove ci sono applicazioni, come ad esempio le video conferenze, che richiedono una buona tol- leranza ai fallimenti della rete. In questo campo la ricerca di cammini disgiunti nasce spesso dalla necessità di minimizzare l’impatto che la caduta di un link o di un nodo della rete può avere su una connessione stabilita. In tali reti la ricerca di cammini bilan- ciati (possibilmente disgiunti) si applica, ad esempio, nel caso in cui si debba suddivide- re uno stesso messaggio in più componenti, le quali devono arrivare tutte a destinazione entro un margine di tempo sufficientemente limitato.

I problemi affrontati finora in letteratura, che hanno alcune caratteristiche del problema presentato nella tesi, sono principalmente di due tipi:

• problemi di bilanciamento

• problemi di ricerca di cammini su grafi.

Il primo tipo di problemi ha in comune proprio l’idea di bilanciamento. Si tratta di pro- blemi, infatti, in cui gli elementi base hanno un costo associato e si cerca un insieme ammissibile di elementi per cui sia minimizzata la differenza in costo tra l’elemento più costoso e quello meno costoso in esso contenuto, si cerca cioè l’insieme più “uniforme”

rispetto ai costi. In [13] è stato affrontato il problema dell’assegnamento bilanciato, mentre Camerini et al. in [4] hanno affrontato il problema del bilanciamento di diverse strutture di grafo. Un esempio di struttura analizzata in [4] è l’albero radicato più uni- forme: in questo caso in input vengono forniti un grafo orientato, con un costo intero positivo associato ad ogni arco, e un nodo radice r, e si cerca un albero di copertura T orientato e radicato in r tale che sia minimizzata la differenza in costo tra il cammino più costoso e quello meno costoso in T.

Per quanto riguarda la seconda famiglia di problemi sopra citata, la similarità con il pro- blema descritto nella tesi non è tanto nel tipo di funzione obiettivo utilizzata, bensì nelle caratteristiche che i cammini cercati devono avere. Ad esempio in [12] si affronta il problema di calcolare, in un grafo pesato G, due cammini disgiunti da una super origine s a una super destinazione t in modo che sia minimizzato il costo del cammino più co- stoso. Nel problema affrontato in [14] da Perl e Shiloach, invece, sono dati in input un grafo G e due coppie di suoi nodi e si cercano due qualsiasi cammini disgiunti che con- nettano le due coppie di nodi specificate.

Nella tesi, il problema dei cammini bilanciati viene innanzitutto formulato e studiato come in [6], analizzando il caso di reti acicliche. Viene poi studiata la sua generalizza- zione al caso di grafi di input generici, mostrando come gli approcci proposti per reti a- cicliche possano essere utilizzati per definire una famiglia di algoritmi euristici in grado di individuare efficientemente soluzioni di buona qualità.

Più precisamente, il problema può essere descritto nel modo seguente. Sia G = (V, E) un grafo orientato e aciclico con #V = n e #E = m. Per ogni arco (i, j) ∈ E sia il co- sto ad esso associato. Siano inoltre dati k nodi sorgente

Cij∈¥

{s s1, 2,...,s_k}e k nodi destina- zione {t t1, ,...,2 t_k} con k . Il problema dei cammini bilanciati su G è il problema di determinare k cammini che connettano le k sorgenti e le k destinazioni date minimiz- zando la differenza in costo tra il cammino più costoso e quello meno costoso. Ogni sorgente può essere connessa a una qualsiasi destinazione e nessun nodo sorgente o de- stinazione può rimanere escluso. Aggiungendo a V due ulteriori nodi s e t e inserendo in E i 2k archi di costo zero (

≥2

)

, _i

s s e ( )t ti^, per i = 1, 2, …, k, ci si può ricondurre ad una formulazione del problema con un’unica sorgente s ed un’unica destinazione t, in cui i k cammini bilanciati cercati devono connettere s a t e devono contenere tutti gli archi del tipo (s s^, i) e tutti quelli del tipo ( )t ti^, . Nella formulazione del problema si può anche richiedere che i k cammini individuati siano node-disjoint o arc-disjoint oltre che bilan- ciati.

In [6] è stato dimostrato che il problema dei cammini bilanciati è NP-arduo e che le versioni node-disjoint e arc-disjoint sono NP-ardue in senso forte. Nel caso in cui G sia aciclico e non si impongano vincoli sulla disgiunzione di nodi o archi, è stato proposto un algoritmo pseudopolinomiale per la risoluzione del problema. Nel caso in cui k è , utilizzando il metodo per la ricerca di cammini semplici basato sulla colora- zione dei nodi descritto in [1], con l’algoritmo proposto si può risolvere anche il caso node-disjoint. Nel lavoro di tesi verrà mostrato che tale algoritmo può essere adattato al caso in cui il grafo di input G contenga cicli. Tale estensione dell’algoritmo pseudopoli- nomiale costituisce il nucleo di una famiglia di algoritmi euristici per il problema dei cammini bilanciati, il cui progetto, implementazione e sperimentazione è il risultato principale conseguito durante questo lavoro di tesi.

(^{log n}

Ο )

Durante la descrizione degli algoritmi di risoluzione verrà messo in evidenza come, con l’apporto di piccole modifiche che non hanno alcun effetto sulla complessità computa- zionale delle procedure, si possa risolvere anche la versione del problema in cui sono fornite in input k coppie di nodi origine-destinazione, e in cui i k cammini bilanciati da individuare devono connettere ogni origine con la rispettiva destinazione.

La variante arc-disjoint del problema non verrà affrontata direttamente, ma verrà mo- strato come i risultati che si ottengono per la variante node-disjoint possano essere otte- nuti anche per il caso arc-disjoint tramite riduzioni in tempo polinomiale da una varian- te all’altra.

Durante il lavoro di tesi, lo studio teorico è stato affiancato dallo sviluppo in C++ di una libreria che implementa alcuni degli algoritmi proposti. Lo sviluppo del software nasce dall’esigenza di testare le euristiche proposte. L’esperienza computazionale è sta- ta effettuata su circa 80 istanze reali relative al mondo delle reti di telecomunicazione.

Per ogni istanza è stato analizzato sia il caso in cui ogni sorgente può essere connessa ad una qualsiasi destinazione, sia il caso in cui i nodi origine e destinazione in input sono forniti a coppie e i cammini bilanciati da individuare devono connettere ogni origine con la rispettiva destinazione.

Nel primo capitolo viene fornita una formulazione del problema dei cammini bilanciati nel caso di grafi aciclici, si analizza la complessità computazionale in tempo di tale pro- blema e viene descritto con completezza un algoritmo di risoluzione. Successivamente si affrontano e si analizzano i casi node-disjoint e arc-disjoint, e si descrive come adat- tare l’algoritmo precedentemente descritto per poter risolvere le due varianti del pro- blema. In questo primo capitolo il problema viene affrontato seguendo l’approccio de- scritto in [6].

Nel secondo capitolo si presenta la generalizzazione del problema al caso di grafi di in- put generici. Si mostrerà come l’algoritmo per reti acicliche descritto nel primo capito- lo possa essere adattato al caso in cui il grafo di input contenga cicli e si mostrerà come tale approccio possa essere utilizzato per progettare una famiglia di algoritmi euristici che guidi efficientemente nella ricerca di soluzioni di buona qualità.

Nel terzo capitolo vengono descritte le principali scelte implementative effettuate nelle fasi di progettazione e realizzazione del software che implementa l’approccio euristico proposto.

Il quarto capitolo è dedicato alle sperimentazioni. In questo capitolo viene descritto il dataset utilizzato per effettuare i test e il formato utilizzato per descrivere le istanze del problema. Vengono inoltre riportati i criteri con cui sono state condotte le sperimenta- zioni, i risultati ottenuti con il software da noi prodotto e il confronto con i risultati otte- nuti mediante il software commerciale per problemi di Programmazione Lineare Intera (P.L.I.) CPLEX 9.1.

Il quinto capitolo, infine, contiene le conclusioni e i possibili sviluppi futuri di questo lavoro di tesi.