Determinazione di cammini pareto-ottimali su grafi pesati

Obiettivo di questa tesi è stato quello di trovare l’insieme dei cammini pareto-ottimali, rispetto alla lunghezza e alla capacità, per un grafo orientato e connesso ed ovviamente pesato sugli archi con lunghezza e capacità.
A tale scopo si è utilizzato il linguaggio di programmazione Pascal.
La risoluzione di tale problema è di grande utilità pratica. Un esempio è quello del trasporto urbano, dove dato un certo numero di strade (il verso dell’arco indica il senso unico) si vogliono trovare quei cammini che portano da un punto di partenza (origine) ad un punto di arrivo (destinazione), minimizzando la lunghezza ed avendo massima capacità.
Oltre al parametro relativo alla lunghezza abbiamo considerato anche il parametro relativo alla capacità poiché i cammini che hanno una capacità maggiore di altri possono essere utilizzati da un più grande numero di utenti; inoltre, alcuni utenti hanno la possibilità di utilizzare solo strade con grande capacità.
Una volta trovati tutti i cammini pareto-ottimali del grafo, si è proceduto a determinare la misura della loro centralità. L’indice di centralità fornisce un’indicazione dell’utilità del cammino per gli utenti, che sono stati considerati uniformemente distribuiti nei vari nodi del grafo. Un cammino che si trova a breve distanza da tutti i nodi del grafo, e avente quindi un indice di centralità piuttosto basso, avrà un’utilità maggiore rispetto a quella di un cammino che ha un alto indice di centralità.

Conclusioni
Come abbiamo detto in precedenza, il problema di cammino minimo può essere generalizzato introducendo ulteriori parametri in aggiunta a quello della lunghezza. La scelta di quali parametri introdurre dipende dal tipo di problema che si deve risolvere.
Una conseguenza che deriva dall’aumento dei parametri associati agli archi è il fatto che non si troverà più un unico cammino minimo, ma si troveranno una serie di cammini pareto-ottimali, ognuno dei quali sarà ottimo per i criteri che avremo definito per la ricerca dei cammini.
Il programma che si è sviluppato può quindi essere variato in modo da considerare oltre alla capacità e alla lunghezza degli archi anche altri parametri.
Un indice utile per la valutazione di un cammino è quello relativo alla sua centralità. Il cammino che presenta la misura di centralità più bassa è quello “complessivamente” più vicino a tutti i nodi del grafo e che risulta quindi il più utile.
Le prestazioni del programma, così come ci si attendeva data la complessità di ordine polinomiale, sono ottime. Il programma, utilizzando un processore di tecnologia pentium, applicato ad un grafo con un numero limitato di nodi e con capacità non tanto grandi, produce i cammini pareto-ottimali del grafo in ingresso quasi istantaneamente.