Il problema del cammino minimo in reti multiobiettivo

Introduzione

uesto lavoro tratta sinteticamente alcuni aspetti del problema

q del cammino minimo in reti urbane.

La ristre

ttezza degli spazi concessi ha fatto sì che il lavoro sia

limitato ad un aspetto topico del problema, a mio giudizio

importante, ma non unico.

Poiché, secondo le più comuni interpretazioni della riforma dei corsi di laurea,

appare che questo “breve elaborato scritto” debba rappresentare una forma di

relazione finale con cui lo studente “chiude” il proprio ciclo di studi, ho ritenuto

adeguato seguire, durante l’elaborazione di questa tesi, le linee guida apprese

dal mio corso di studi.

Ho scelto di trattare una materia matematica per via del personale interesse

verso la materia, trovando un ottimo mezzo per unire l’utile al dilettevole.

La ricerca operativa mi ha permesso di unire la mia passione verso la matemati-

ca al corso di studi svolto, applicando la stessa al settore dei trasporti.

Ho scelto altresì di fornire un’adeguata introduzione storica all’argomento, ri-

tenendo particolarmente importante questa dimensione della matematica, spes-

so erroneamente trascurata.

Il primo capitolo introduce la materia, la teoria dei grafi ed il problema del

cammino minimo, passando, dall’analisi del problema banale, attraverso l’intro-

duzione di ipotesi e vincoli, allo studio di un problema che rappresenti, in mo-

do il più possibile verosimile, la situazione reale.

Nel secondo capitolo, sono analizzati nel dettaglio tre algoritmi proposti da due

ricercatori del dipartimento di ingegneria civile dell’università del Maryland;

nel momento in cui questa tesi è scritta, il lavoro dei ricercatori americani è in

fase di pubblicazione sul “European Journal of operational research”. Gli algo-

ritmi in questione possiedono un certo grado di sofisticatezza matematica, tale

da richiedere un’analisi approfondita; per questo motivo, e perché lo stesso la-

voro rappresenta l’ultimo ritrovato in materia, ho preferito incentrarmi su que-

I

sta “promessa di pubblicazione”. L’innovazione proposta dai due scienziati è

stata l’introduzione dell’analisi multicriterio in reti stocastiche e variabili rispet-

to al tempo.

Nel terzo capitolo sono passato ad analizzare il lavoro svolto da Paola Modesti

e Anna Sciomachen nel 1998, che tratta un problema simile da un punto di vista

leggermente diverso.

La mia tesi si risolve quindi con l’analisi delle criticità dei due lavori, con un

confronto tra gli stessi e con le considerazioni personali sul problema dell’anali-

si multicriterio. Questa rappresenta infatti il fulcro del mio lavoro, in cui sono

gettati i presupposti per possibili nuovi sviluppi dell’argomento, considerata

l’opera di sintesi svolta attraverso la discussione dei lavori analizzati.

Con la speranza che questa conclusione possa tradursi nell’inizio di una nuova

affascinante esperienza in ambito matematico.

Silvio Villa, Genova, febbraio 2005. II

CAPITOLO

UNO

Multicriteria Stochastic

Time-Varying networks

Capitolo 1

Multicriteria Stochastic Time-Varying networks

Sommario: 1.1 L’origine della teoria dei grafi - 1.2 Introduzione alla teoria dei

grafi - 1.3 Il problema del cammino minimo - 1.4 Algoritmi euristici - 1.5 Il

problema del cammino minimo nelle reti urbane - 1 .

6 Introduz i one al problema

MSTV - 1.7 Relazioni tra i cammini Pareto-ottimali a priori e adattivi

1.1 L’origine della teoria dei grafi

b enché già precedentemente si fosse ragionato in termini di gra-

fi, la nascita della teoria dei grafi si può far risalire alla prima

metà del secolo XVIII.

Leonhard Euler (1707 – 1783) introdusse alcuni simboli comu-

π , elegantemente rappresentati insieme nella for-

nemente utilizzati quali e

, , i π + = .

mula più affascinante della storia della matematica: i

e 1 0

Oltre all’introduzione dei logaritmi di numeri negativi, Euler si rese protagoni-

sta della formalizzazione di una teoria di cui già Leibniz (Gottfried Wilhelm,

1646 – 1716) aveva parlato, tuttavia senza un preciso formalismo matematico: la

teoria dei grafi.

Per oltre un secolo, questa teoria non fu ulteriormente sviluppata e si fermò al

punto in cui era rimasta con gli studi di Euler; lo studio di questa teoria fu ri-

preso a partire dalla seconda metà del secolo XIX in Inghilterra, dove diversi

problemi vennero formulati attraverso la teoria dei grafi.

Nel 1733, il gesuita Girolamo Saccheri (1677 – 1733) pubblica “Euclides ab omni

naevo vindicatus”, in cui, cercando di dimostrare il 5° postulato di Euclide per

assurdo, getta le basi per le geometrie non euclidee. IV

Successivamente, Lambert (Johann Heinrich, 1728 – 1777) e Legendre (Adrien-

Marie, 1752 – 1833) riprendono il lavoro di Saccheri, ma infruttuosamente;

Gauss (Karl Friedrich, 1777 – 1855) nel 1824 afferma che una geometria basata

sui primi 4 postulati di Euclide e sulla negazione del quinto è possibile e non

contraddittoria, ma non pubblica i risultati dei suoi studi per paura delle rea-

zioni del mondo matematico nei suoi confronti. Bisognerà aspettare il russo Lo-

bačevskij (Nicolaj Ivanovič, 1793 – 1856) nel 1829 perché sia formalizzata la

prima geometria non euclidea basata sulla negazione del quinto postulato: la

geometria iperbolica. Nel XIX secolo, Riemann (Georg Friedrich Bernhard, 1826

– 1866) formula la geometria ellittica, postulando che due rette hanno sempre in

comune almeno un punto, negando quindi l’esistenza di rette parallele.

In seguito, altri studi verranno effettuati sulle geometrie non euclidee che nega-

no il quinto postulato, tra cui vale la pena ricordare il modello di Beltrami (Eu-

genio, 1835 – 1900), con cui lo studioso giunge alla definizione delle geodetiche,

ed il modello di Klein (Felix, 1849 – 1925).

L’ironia della sorte volle che, mentre in tutti questi anni, gli sforzi di grandi ma-

tematici furono concentrati a ricercare una geometria che negasse il quinto po-

stulato, la teoria dei grafi, già così come formulata da Euler rappresentava una

geometria non euclidea; questa però partiva dalla negazione del terzo postula-

to, portando risultati per nulla trascurabili. In questa geometria, ad esempio,

non è necessariamente vero che la somma di due lati di un triangolo sia mag-

giore del terzo lato.

Solo in epoca relativamente recente ci si è accorti del fatto che la teoria dei grafi

rappresenta una geometria non euclidea, e più precisamente la prima ad essere

stata formalizzata.

Tutto ebbe inizio nel 1735, nella cittadina di Königsberg (oggi Kaliningrad), nel-

la Prussia orientale. La città, che diede i natali ad Immanuel Kant, è attraversata

dal fiume Pregolya e un suo quartiere sorge su un’isola chiamata “der Knei-

phof”, oltre la quale, il fiume si divide in due diramazioni. A quei tempi, l’isola

era collegata con ciascuna delle due sponde da due ponti, mentre la sponda si-

tuata dopo la suddivisione del fiume era collegata con un ponte per ogni spon-

da e con un altro all’isola. V

Gli abitanti di Königsberg si chiedevano se esistesse un cammino che attraver-

sasse tutti i ponti una ed una sola volta.

Fig. 1: Königsberg

Il quesito può essere affrontato direttamente per tentativi ma, vista la quantità

elevata di possibili soluzioni, i cittadini non avrebbero comunque avuto la cer-

tezza di averli elencati tutti; quindi, se anche tutti i cammini elencati non risol-

vessero il problema, restava il dubbio di averli elencati tutti.

Generalizzando il problema, e ricorrendo alla modellizzazione possibile grazie

alla teoria dei grafi, Euler riuscì ad uscire da quella situazione. Si pose infatti il

problema di fornire una condizione generale di risolvibilità per quel genere di

problemi; fu quindi in grado di fornire la soluzione: il problema non ammette

soluzioni.

Il risultato fu presentato all’Accademia di San Pietroburgo nell’agosto del 1736

e pubblicato nell’opera “Solutio Problematis ad geometriam situs pertinentis”. VI

1.2 Introduzione alla teoria dei grafi

u n grafo è un insieme ordinato e finito di (punti) nodi legati tra

loro da un insieme finito di relazioni (archi).

In que

sto tipo di geometria non valgono molte delle regole

proprie della geometria euclidea; il concetto che risente mag-

giormente della negazione del terzo postulato di Euclide è quello di distanza.

Qui non si può, infatti, parlare di “distanza euclidea”.

Il concetto di distanza nella teoria dei grafi ha senso solo in termini numerici e

non è di per se raffigurabile attraverso la rappresentazione grafica.

In termini formali si definisce grafo:

( ) , dove

G V E

, { }

= insieme dei nodi

V v , v ,..., v

1 2 n

{ }

= insieme degli archi

E e , e ,..., e

1 2 m

Un grafo si dice orientato se i suoi archi possono essere percorsi solo in una de-

terminata direzione, mentre si dice non orientato se i suoi archi non hanno un

senso di percorrenza e possono pertanto essere percorsi indifferentemente in

entrambe le direzioni.

Grafo non orientato Grafo orientato

A B A B

C

C D D E

E Fig. 2: Esempi di grafi VII

Due nodi si dicono adiacenti se sono connessi tra loro da un arco. Nell’esempio

di Fig. 2, i nodi B ed E sono tra loro adiacenti, mentre i nodi B e D non lo sono.

Parallelamente, si dicono adiacenti due archi se hanno un nodo in comune; ad

esempio, gli archi BE e AB sono adiacenti, mentre AB e DE non lo sono.

∀ ∈E , il nodo è detto predecessore del nodo , ed il

In un grafo orientato, e i j

ij

nodo è detto successore del nodo . Quindi, il nodo C è successore di A e

j i

predecessore di E.

Un grafo è completo quando esiste almeno un arco tra ogni coppia di nodi; vie-

ne definito planare se è possibile disegnarlo su un piano senza intersezioni tra

gli archi.

Questa definizione è importante in ambito di reti urbane, poiché non possono

rappresentarsi reti urbane non planari, in quanto ad ogni incrocio corrisponde

un nodo, eliminando, di fatto, la possibilità che due archi possano intersecarsi.

Si parla inoltre di archi multipli, quando due nodi sono collegati tra loro da più

di un arco, come in figura 3 a.

A B A

Fig. 3 a Fig. 3 b

I loops o cappi, sono archi per cui il nodo origine coincide con il nodo destina-

zione (fig. 3 b).

Un grafo che non contiene loops e archi multipli si definisce semplice.

Con il termine cammino si definisce una sequenza finita di archi nel quale il

nodo finale di un arco è il nodo iniziale del successivo.

Se un cammino ha il nodo origine che coincide con il nodo destinazione, si ha

un cammino chiuso, chiamato anche circuito.

Come già accennato, il concetto di distanza assume un significato particolare in

questa geometria; un grafo si definisce pesato se ad ogni arco viene attribuito

un valore definito “peso”. Questo attributo può rappresentare il tempo necessa-

VIII

rio per percorrere l’arco, la distanza tra i due nodi, il costo per passare da un

nodo all’altro, il flusso massimo consentito per unità di tempo, o qualsiasi altro

significato.

La rappresentazione grafica di un grafo è visivamente molto efficace ed imme-

diata ma, quando il numero di elementi, siano nodi o archi, è consistente, per

rappresentare il grafo è preferibile servirsi di opportune matrici.

Le matrici più comunemente associate ai grafi sono generalmente tre:

( ) ∈

⎧⎪ E

1 se i , j

⎡ ⎤

= =

tale che:

La matrice di adiacenza ⎨

A a a

⎣ ⎦ ( )

× ∉

n n ij ij ⎪⎩

0 E

i j

se , ⎡ ⎤

= tale per cui:

Se il grafo è pesato, viene definita la matrice dei pesi D d

⎣ ⎦

×

n n ij

( ) ∈

⎧⎪ E

w i j

se , ( )

=

= con peso associato all’arco

ij

⎨ w

d i , j

( )

∞ ∉

ij ij

⎪⎩

+ E

i j

se , ⎡ ⎤

=

La matrice di incidenza tale per cui:

B b

⎣ ⎦

×

n m ia

r , s

⎧ se è nodo iniziale dell'arco

1 i a

r , s

⎪

= − se è nodo finale dell'arco

⎨

b 1 i a

ia r , s

r , s ⎪ se l'arco non incide sul nodo

0 a i

⎩ r , s

Il vantaggio di una rappresentazione attraverso le matrici consiste nella possibi-

lità di applicare algoritmi iterativi o ricorsivi mediante l’uso di calcolatori elet-

tronici.

Attraverso i grafi è possibile rappresentare molteplici tipi di situazioni: ad e-

sempio una serie di attività legate da precise relazioni causa-effetto, anche se