Il problema del cammino minimo in reti multiobiettivo

Università degli studi di Genova

Corso di laurea in

Economia marittima e dei trasporti

Il problema del cammino minimo in reti multiobiettivo

Anna Sciomachen

Relatrice: Silvio Villa

Candidato: Dedicato a:

Coloro che in me hanno sempre creduto

E a coloro che, guardando oltre l’apparenza di un abito, hanno generosamente elargito conforto, calore, amicizia.

Va un grazie dovuto a quelle persone che mi hanno restituito forza e audacia per arrivare alla fine della corsa.

Introduzione

Questo lavoro tratta sinteticamente alcuni aspetti del problema del cammino minimo in reti urbane.

La ristrettezza 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 matematica al corso di studi svolto, applicando la stessa al settore dei trasporti.

Ho scelto altresì di fornire un’adeguata introduzione storica all’argomento, ritenendo particolarmente importante questa dimensione della matematica, spesso 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’introduzione di ipotesi e vincoli, allo studio di un problema che rappresenti, in modo 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 algoritmi in questione possiedono un certo grado di sofisticatezza matematica, tale da richiedere un’analisi approfondita; per questo motivo, e perché lo stesso lavoro rappresenta l’ultimo ritrovato in materia, ho preferito incentrarmi su questa “promessa di pubblicazione”. L’innovazione proposta dai due scienziati è stata l’introduzione dell’analisi multicriterio in reti stocastiche e variabili rispetto 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’analisi 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 Introduzione al problema MSTV - 1.7 Relazioni tra i cammini Pareto-ottimali a priori e adattivi

1.1 L’origine della teoria dei grafi

Benché già precedentemente si fosse ragionato in termini di grafi, la nascita della teoria dei grafi si può far risalire alla prima metà del secolo XVIII.

Leonhard Euler (1707 – 1783) introdusse alcuni simboli comunemente utilizzati quali π, elegantemente rappresentati insieme nella formula più affascinante della storia della matematica: e^iπ + 1 = 0.

Oltre all’introduzione dei logaritmi di numeri negativi, Euler si rese protagonista 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 ripreso 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 reazioni del mondo matematico nei suoi confronti. Bisognerà aspettare il russo Lobač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 negano il quinto postulato, tra cui vale la pena ricordare il modello di Beltrami (Eugenio, 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 matematici furono concentrati a ricercare una geometria che negasse il quinto postulato, la teoria dei grafi, già così come formulata da Euler rappresentava una geometria non euclidea; questa però partiva dalla negazione del terzo postulato, portando risultati per nulla trascurabili. In questa geometria, ad esempio, non è necessariamente vero che la somma di due lati di un triangolo sia maggiore 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), nella 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 Kneiphof”, 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 situata dopo la suddivisione del fiume era collegata con un ponte per ogni sponda e con un altro all’isola. V

Gli abitanti di Königsberg si chiedevano se esistesse un cammino che attraversasse 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 certezza di averli elencati tutti; quindi, se anche tutti i cammini elencati non risolvessero 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

Un grafo è un insieme ordinato e finito di (punti) nodi legati tra loro da un insieme finito di relazioni (archi).

In questo tipo di geometria non valgono molte delle regole proprie della geometria euclidea; il concetto che risente maggiormente 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 sé raffigurabile attraverso la rappresentazione grafica.

In termini formali si definisce grafo:

G = (V, E), dove

V = {v₁, v₂,..., v_n} = insieme dei nodi

E = {e₁, e₂,..., e_m} = insieme degli archi

Un grafo si dice orientato se i suoi archi possono essere percorsi solo in una determinata 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_ij ∈ E, il nodo i è detto predecessore del nodo j, ed il nodo j è detto successore del nodo i. Quindi, il nodo C è successore di A e predecessore di E.

Un grafo è completo quando esiste almeno un arco tra ogni coppia di nodi; viene 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 destinazione (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 necessario 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.

VIII

La rappresentazione grafica di un grafo è visivamente molto efficace ed immediata 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:

La matrice di adiacenza A = [a_ij]_{n × n} tale che:

a_ij = 1 se (i, j) ∈ E

a_ij = 0 se (i, j) ∉ E

Se il grafo è pesato, viene definita la matrice dei pesi D = [d_ij]_{n × n} tale per cui:

d_ij = w_ij se (i, j) ∈ E, con w_ij peso associato all’arco

d_ij = +∞ se (i, j) ∉ E

La matrice di incidenza B = [b_ia]_{n × m} tale per cui:

b_ia = 1 se i è nodo iniziale dell’arco a_r,s

b_ia = −1 se i è nodo finale dell’arco a_r,s

b_ia = 0 se l’arco a_r,s non incide sul nodo i

Il vantaggio di una rappresentazione attraverso le matrici consiste nella possibilità di applicare algoritmi iterativi o ricorsivi mediante l’uso di calcolatori elettronici.

Attraverso i grafi è possibile rappresentare molteplici tipi di situazioni: ad esempio una serie di attività legate da precise relazioni causa-effetto, anche se l’applicazione più comune e più intuitiva a cui questa geometria si presta è associata al problema del trasporto. Altri importanti problemi possono essere quello dell’allocazione di centri di servizio, oppure la progettazione di cicli di attività complesse quali quelle presenti nel campo dell’elettronica; recentemente, lo sviluppo delle reti neurali sta assumendo importanza sempre maggiore. IX

1.3 Il problema del cammino minimo

Applicando la teoria dei grafi alle reti di trasporto, uno dei problemi più comuni è quello di trovare quel cammino che consenta di giungere da un certo nodo origine ad un nodo destinazione minimizzando il costo (la durata, la distanza).

In letteratura sono presenti diversi algoritmi per risolvere il problema, noto come shortest path problem, oltre alla possibilità di risolvere questo problema attraverso la programmazione lineare.

Il problema posto dalla programmazione lineare consiste nella sua limitata applicabilità a reti di piccole dimensioni, in quanto la complessità computazionale è elevatissima in termini di risorse necessarie per effettuare il calcolo.

Il modello di programmazione lineare necessita la matrice dei costi e la creazione di tante variabili binarie quanti gli archi esistenti che assumano valore 1 se l’arco rappresentato appartiene al cammino soluzione e 0 altrimenti; chiamando O il nodo origine e D il nodo destinazione, il modello consiste nella seguente espressione:

min z = ∑_i,j c_ijx_ij

∑_j x_Oj = 1

∑_i x_iD = 1

∑_ix_ik − ∑_jx_kj = 0 ∀ k ≠ O, D

x_ij ∈ {0, 1}

In questa formulazione, il primo vincolo indica che, tra tutti gli archi uscenti dall’origine, solo uno può appartenere al cammino soluzione.

Al pari della condizione precedente, il secondo vincolo impone che uno solo degli archi entranti nel nodo destinazione possa essere attivo, quindi appartenere al cammino soluzione. X

Il terzo vincolo impone che, se in un nodo esiste un arco uscente, necessariamente deve esisterne anche uno entrante. k

Il quarto vincolo è la condizione che specifica che le variabili x_ij sono binarie.

È facile intuire come il problema assuma immediatamente dimensioni molto rilevanti dal punto di vista della complessità computazionale.

Esistono invece molteplici e differenti algoritmi in letteratura che risolvono il problema del cammino minimo, tra cui si possono distinguere diverse categorie.

Gli algoritmi arborescenti generano, attraverso una singola implementazione, l’albero dei percorsi minimi da un determinato nodo origine a tutti gli altri nodi. Applicando algoritmi di questo tipo a tutti i nodi assunti come origine, si ottiene una matrice, dove ogni applicazione dell’algoritmo costituisce la i-esima riga, che rappresenta il peso di ogni percorso minimo tra due nodi qualsiasi.

Generalmente gli algoritmi proposti fanno riferimento all’etichettatura dei nodi e si possono suddividere in due categorie a seconda che si tratti di algoritmi basati sull’attribuzione di etichette (label setting) o sulla correzione delle etichette (label correcting).

I primi ricercano, ad ogni iterazione, il percorso con il costo minimo dall’origine ad uno o più nodi della rete e, ad ogni passaggio, sono aggiornati con l’aggiunta di un nodo e del rispettivo arco che lo collega alla rete. L’algoritmo termina quando tutti i nodi sono stati connessi al nodo origine. La caratteristica di questo tipo di algoritmi è data dal fatto che ad ogni iterazione è fornito un risultato definitivo, cioè tutti i cammini tra l’origine ed i nodi attivi fino a quel momento sono ottimi. L’importanza di questa caratteristica si riflette in applicazioni pratiche, poiché non è necessario attendere il termine del processo per utilizzare già parte dei risultati.

I secondi invece effettuano l’aggiornamento ad ogni iterazione incrementando o modificando gli archi della soluzione, ma non garantiscono che il percorso ottenuto alla fine di ogni iterazione sia ottimo finché il processo non è terminato.

La distinzione tra queste categorie non è sempre netta, come nel caso del noto algoritmo di Dijkstra che è di tipo misto, cioè label setting-correcting. XI