Antonio Sforza » 18.Ottimizzazione su rete: Problemi di percorso

Schema della lezione

In questa lezione si descrive il problema di minimo percorso.

Si formula inizialmente il modello relativo ad una singola coppia di vertici origine/destinazione. Si presenta la classificazione dei problemi e degli algoritmi e vengono descritti i principali algoritmi utilizzabili per la soluzione dei problemi definiti nella classificazione.

I problemi di determinazione di percorsi ottimi sono tra i più noti problemi di ottimizzazione su rete. Essi si presentano in innumerevoli campi, nella pianificazione dei trasporti e nella gestione del traffico, nelle telecomunicazioni, nell’ingegneria dell’informazione, nella gestione aziendale.

Il modello del minimo percorso per una coppia di vertici origine/destinazione

Il problema può essere formulato attraverso un modello in programmazione intera binaria. Indicando con o e d i vertici origine e destinazione del percorso minimo da individuare, con c_ij il costo associato all’arco generico ij (ij∈A) e con x_ij una variabile binaria pari a 1 se l’arco ij appartiene al percorso minimo, pari a 0 altrimenti, il modello assume la seguente configurazione, nella quale ∑_i sta per ∑_i:ij∈A:

Min z = ∑_ij∈A c_ij x_ij
s.a.

∑_k x_ok = 1

∑_i x_id = 1

∑_k x_jk – ∑_i x_ij = 0 (∀j ≠ o,d)
x_ij = 0/1

Il primo vincolo esprime la condizione che uno solo degli archi uscenti dall’origine o può appartenere ad un percorso e quindi una sola delle corrispondenti variabili può essere pari ad 1. Analogamente il secondo vincolo esprime la condizione che uno solo degli archi entranti nella destinazione d può appartenere ad un percorso. Il terzo vincolo va scritto per ogni vertice j diverso da o e d ed esprime una condizione di bilancio: nel vertice generico j se c’è un arco uscente appartenente ad un percorso, ci deve essere anche un arco entrante appartenente ad un percorso, se non c’è un arco uscente non c’è neanche un arco entrante. Le soluzioni riportate in tabella sono le uniche soluzioni che rispettano questi vincoli. L’algoritmo risolutivo sceglierà tra esse la migliore.

Classificazione dei problemi di minimo percorso

Si individuano in generale le seguenti classi di problemi nella determinazione del minimo percorso:

• da un vertice ad un altro vertice della rete
• da un vertice a tutti gli altri vertici della rete (o a un sottoinsieme)
• da tutti i vertici a tutti gli altri vertici (o da un sottoinsieme di vertici ad un altro sottoinsieme di vertici), cioè per tutte le coppie di vertici individuabili sulla rete

Il problema della classe (a), per il quale è stato formulato il modello della slide precedente, è chiaramente contenuto nella classe (b), che, a sua volta, è contenuta nella classe (c). La soluzione del problema (a) genera, come si è detto, un valore di costo minimo C_od per la singola coppia o-d. La soluzione del problema (b) genera valori di costo minimo C_ok da un vertice o a tutti i vertici k della rete. La soluzione del problema (c) genera tutti i valori di costo minimo C_od da tutti i vertici origine a tutti i vertici destinazione. È possibile quindi definire una matrice C delle distanze minime (o dei costi minimi) il cui generico elemento C_od fornisce il valore del minimo percorso tra i vertici o e d.

Classificazione degli algoritmi di minimo percorso

Il problema delle classi (b) e (c) viene risolto nelle pratiche applicazioni mediante algoritmi “ad hoc” che sono disponibili in grande varietà (la letteratura degli algoritmi di minimo percorso è veramente sterminata). Questi algoritmi possono essere classificati in base al problema che risolvono. La distinzione che più di frequente si adotta è tra:

1) algoritmi arborescenti e 2) algoritmi matriciali.

I primi si definiscono in questo modo perché una singola implementazione dell’algoritmo genera l’arborescenza (l’albero) dei minimi percorsi da un vertice origine a tutti gli altri vertici assunti come destinazione. Essi risolvono dunque la classe (b) dei problemi e quindi naturalmente anche la classe (a). La costruzione dell’arborescenza dei minimi percorsi con origine nel vertice i generico fornisce la riga i-esima della matrice C delle distanze minime. I secondi invece risolvono la classe (c) dei problemi e dunque forniscono in una singola implementazione la matrice C delle distanze minime tra tutte le coppie di vertici individuabili sulla rete. Non c’è naturalmente una rigida corrispondenza tra classe di problema e tipo di algoritmo idoneo a risolverlo. È possibile infatti applicare un algoritmo arborescente per ciascuno dei vertici origine della rete (dunque al limite v volte) per risolvere il problema (c) del cammino minimo per tutte le coppie di vertici, così come sarebbe possibile applicare un algoritmo matriciale ed utilizzare solo parte dei risultati ottenuti per dare risposta ad un problema del tipo (b). Nelle slide che seguono si schematizzano su un esempio i fondamentali algoritmi arborescenti e matriciali utilizzati per la soluzione del problema.

Algoritmi arborescenti, label setting e label correcting

Il problema della determinazione dei minimi percorsi da un vertice o della rete R(V, A, C) a tutti gli altri vertici, può essere ricondotto quindi a quello della determinazione di una arborescenza con radice in O. I metodi proposti per la soluzione di questo problema sono metodi di etichettamento dei vertici e possono essere divisi in due classi:

• metodi “label setting“

• metodi “label correcting“

I metodi del tipo label setting ad ogni iterazione fissano il valore del minimo percorso dalla origine ad uno o più vertici della rete. Questi algoritmi forniscono ad ogni iterazione il valore definitivo del minimo percorso dall’origine fino ad un vertice destinazione. I risultati intermedi dell’algoritmo hanno quindi significato e possono essere utilizzati.

I metodi del tipo label correcting ad ogni iterazione aggiornano il vettore dei minimi percorsi da O a tutti gli altri vertici. Forniscono risultati intermedi provvisori che non hanno alcun significato pratico e dunque non possono essere utilizzati. Solo dopo l’ultima iterazione determinano simultaneamente i minimi percorsi tra l’origine fissata e tutti gli altri vertici.

Nel seguito si schematizzano tre algoritmi arborescenti: l’algoritmo di Dantzig, del tipo label setting, l’algoritmo di Dijkstra, di tipo misto (label setting-correcting), l’algoritmo di Ford-Moore-Bellman, di tipo label correcting.

Algoritmo di Dantzig

L’algoritmo di Dantzig è un algoritmo arborescente del tipo label setting. Sia o il vertice origine. Si supponga di conoscere al k° stadio della procedura i cammini minimi da o a k vertici. Si indichi questo insieme di vertici con S. Poiché gli algoritmi arborescenti generano progressivamente un albero di minimi percorsi, i vertici di S sono collegati in modo da costituire un albero parziale. L’insieme V dei vertici può essere dunque suddiviso in due sottoinsiemi: S, contenente i vertici etichettati definitivamente con il valore di minimo costo dall’origine o, e (V-S), contenente i vertici per i quali il minimo percorso non è stato ancora determinato e quindi non hanno ancora una etichetta definitiva.

Si indichi con:

i → il generico vertice foglia in S; δ_i la distanza minima di i dall’origine o
j_i → il vertice più vicino ad i, non in S, collegato ad i da un arco i, j_i
a_i →  la lunghezza dell’arco i, j_i

Tra tutti i vertici j_i si sceglierà come vertice da inserire in S il vertice (o i vertici) j_r, tale che δ_r + a_r = Min_i=1,k (δ_i + a_i). Il valore δ_r+a_r fornisce certamente il valore minimo del percorso da o a j_r in quanto ogni altro percorso da o a j_r utilizzerebbe un vertice t non in S avente una distanza minima da o pari a δ_t + a_t > δ_r + a_r. A maggior ragione quindi si verificherebbe δ_t + a_t + a_t,r > δ_r + a_r. Questo step fondamentale dell’algoritmo si itera inserendo ogni volta uno o più nuovi vertici nell’insieme S. L’algoritmo termina quando tutti i vertici del grafo fanno parte di S.

Algoritmo di Dantzig

Algoritmo di Dantzig

Esempio numerico

Grafo G e costi c_ij

Esempio numerico

Si consideri il grafo orientato con 8 vertici e 13 archi riportato in figura. Si vuole calcolare l’arborescenza dei minimi percorsi con origine nel vertice 1. In tabella si riportano le liste degli archi uscenti dai vertici ordinate per costo crescente.

L’insieme S contiene inizialmente il solo vertice 1 cui si associa un valore del minimo percorso pari a 0. Gli archi “uscenti” dall’insieme S sono gli archi uscenti dal vertice 1: 1-2 e 1-3. Tra essi si sceglie l’arco 1-2, cui corrisponde il costo minimo, e si associa al vertice 2 un valore di cammino minimo pari a 0+1=1. Si cancellano dalle liste tutti gli archi che eventualmente hanno destinazione nel vertice 2. Il vertice 1 viene memorizzato come precedessore del vertice 2. L’insieme S contiene i vertici 1 e 2. Le possibilità di “uscita” dall’insieme S sono riportate di seguito:

Esempio numerico

All’arco 1-3 corrisponde il costo minimo e quindi il vertice 3 entra nell’insieme S, con precedessore 1, con un valore di cammino minimo pari a 2. L’insieme S contiene ora i vertici 1, 2, 3. A questo punto si determinano le seguenti possibilità:

Entrano in S i vertici 4 e 5, cui si associa un valore del cammino pari a 4. Predecessore del vertice 5 è il vertice 2. Predecessore del vertice 4 è il vertice 2. Si cancellano tutti gli archi che hanno come destinazione i vertici 4 e 5. L’insieme S contiene ora i vertici 1, 2, 3, 4, 5. Si ha pertanto:

Algoritmo di Dijkstra

L’algoritmo di Dijkstra assegna a ciascuno dei v vertici del grafo dei valori di tentativo, che costituiscono dei limiti superiori al valore del cammino minimo dal vertice origine ad essi. In ciascuna iterazione dell’algoritmo un valore di etichetta viene reso definitivo. Dopo un numero di iterazioni al massimo pari a quello dei vertici destinazione, le etichette diventano tutte definitive e forniscono i valori dei cammini minimi dal vertice origine a tutti gli altri. Questo algoritmo presenta quindi un meccanismo misto nella determinazione delle etichette. Può essere definito quindi un algoritmo arborescente del tipo label setting-correcting. Si assegna inizialmente al vertice origine il valore definitivo 0 ed a tutti gli altri vertici il valore di tentativo ∞. Si parte quindi dall’origine e si va negli altri vertici calcolando il valore del costo del percorso come somma dell’etichetta dell’origine e del costo dell’arco utilizzato (∞ qualora l’arco non esista). Per ciascun vertice si confronta il valore così calcolato con l’etichetta precedente. Il valore minore viene assunto come nuovo valore di tentativo del minimo percorso verso quel vertice. Tra i v-1 valori di tentativo ottenuti si sceglie il minore e lo si assume come etichetta definitiva del vertice cui corrisponde. Si supponga essere k il vertice etichettato definitivamente nel passo di procedura precedente. Si parte quindi dal vertice k e si va negli altri vertici non ancora etichettati definitivamente, calcolando il valore del costo del percorso come somma dell’etichetta del vertice k e del costo dell’arco utilizzato (∞ qualora l’arco non esista). Per ciascun vertice si confronta il valore così calcolato con l’etichetta precedente ed il valore minimo viene assunto come nuovo valore di tentativo. Tra i v-2 valori di tentativo ottenuti si sceglie il minore e lo si assume come etichetta definitiva del vertice cui corrisponde, per esempio j, assumendolo come punto di partenza per un ulteriore step della procedura. A differenza di quanto avviene nell’algoritmo di Dantzig, in ogni iterazione ci si muove dunque dall’ultimo vertice etichettato definitivamente e non da tutto l’insieme dei vertici etichettati definitivamente. Dopo al massimo v-1 iterazioni (nel caso in cui ad ogni iterazione venga etichettato definitivamente un solo vertice) tutti i vertici sono etichettati definitivamente e il procedimento ha termine.

Algoritmo di Dijkstra

Algoritmo di Bellman

L’algoritmo di Ford-Moore-Bellman è un algoritmo arborescente del tipo label correcting che opera sulla matrice di adiacenza della rete. Supponendo di essere giunti alla k-esima iterazione, l’etichetta f_i^(k) associata al generico vertice i rappresenta il valore del cammino minimo che congiunge il vertice origine al vertice i con un numero di archi al più pari a k+1. L’insieme delle etichette f_i^(k), per i=1,..v, costituisce il vettore f^(k). Indicando con 1 l’origine dell’arborescenza, l’algoritmo viene inizializzato ponendo f₁⁽⁰⁾ = 0; f_i⁽⁰⁾ = c_1i (i≠1). Ad ogni iterazione viene applicata la seguente relazione: f_i^(k) = min_j≠i [ f_j^(k-1) + c_ji] ……. ∀i = 2, 3,…, v; j = 1, 2,…,v ….. (12.1). In base a questa relazione f_i^(k) viene calcolato con la cosiddetta operazione di minisomma tra il vettore f^(k-1) e la colonna i della matrice dei costi associati agli archi. Tale operazione consiste nel sommare gli elementi di posto omologo dei due vettori e nello scegliere tra le somme ottenute il valore minimo. L’esistenza di accoppiamenti a somma non nulla e finita indica infatti l’esistenza di cammini al più di ordine k+1 tra l’origine ed il vertice i. Tra questi si sceglie quello di costo minimo. La procedura termina quando si verifica [ f^(k-1) = ff_i^(k), i= 1,...,v], ovvero quando, in due iterazioni successive, i valori delle etichette assegnate ai vertici non variano. A questo punto i valori di tutte le etichette vengono dichiarati definitivi. Poiché un cammino può essere costituito al massimo da v-1 archi, le iterazioni sono al più v-2, v essendo il numero dei vertici.
La individuazione della composizione dei cammini minimi può essere ottenuta memorizzando ad ogni iterazione per ciascun vertice i il valore di j in corrispondenza del quale è stato determinato f_i^(k). In questo modo ad ogni iterazione si ottiene un vettore delle precedenze che viene aggiornato nelle iterazioni successive tutte le volte in cui si verifica un aggiornamento dei valori f_i^(k).

Algoritmo di Bellman - Matrice dei costi della rete

Valori di f ^(k) nelle iterazioni dell’algoritmo

Algoritmi matriciali, label correcting

Gli algoritmi matriciali lavorano su tutta la matrice del grafo e generano i valori dei minimi percorsi per tutte le coppie origine/destinazione. Sono algoritmi del tipo label correcting.

Algoritmo di Floyd

L’algoritmo matriciale più comunemente usato è l’algoritmo di Floyd. Esso lavora su una matrice C, di dimensioni pari al numero di vertici. Tale matrice, inizialmente coincidente con la matrice di adiacenza vertice-vertice, viene modificata nelle successive iterazioni. La k-esima di tali matrici può essere interpretata come quella che fornisce il costo dei cammini minimi per tutte le coppie di vertici della rete, caratterizzati dalla proprietà di utilizzare soltanto i vertici numerati da 1 a k. Alla fine del procedimento la matrice contiene quindi i valori dei cammini minimi tra tutte le coppie di vertici del grafo che utilizzano tutti i vertici del grafo. Un algoritmo matriciale è quindi per definizione un algoritmo label correcting.

L’algoritmo viene inizializzato ponendo C_ii = 0 ed inoltre per i≠j:

C_ij(0)= c_ij se l’arco ij esiste; …. Cij = ∞ se l’arco ij non esiste

Alla k+1-esima iterazione i valori di C vengono aggiornati utilizzando la seguente relazione, in cui compaiono i valori di costo calcolati utilizzando i vertici numerati da 1 a k: C_i,j^(k+1) = min [C_i,j^(k); C_i,k+1^(k) + C_k+1,j^(k)]

indicando con: C_i,j^(k) il costo minimo da i a j; C_i,k+1^(k) il costo minimo da i a k+1; C_k+1,j è il costo minimo da k+1 a j.

Se l’utilizzazione del vertice k+1 consente di produrre un cammino di costo inferiore a quello di cui già si disponeva, si sostituisce C_i,j^(k) con il nuovo valore ottenuto. Dopo la (k+1)-esima iterazione il generico elemento C_ij^(k+1) fornisce, dunque, il valore del minimo percorso tra i vertici i e j ottenuto utilizzando i vertici il cui indice non sia superiore a k+1. Se v è il numero di vertici l’algoritmo effettua esattamente v iterazioni sulla matrice A.

Algoritmo di Floyd

Rete e matrice di adiacenza ≡ C⁰

Algoritmo di Floyd

Rete

Step 1 - Matrice C ¹

Algoritmo di Floyd

Rete

Step 2 - Matrice C ²

Algoritmo di Floyd

Rete

Step 3 - Matrice C ³

Algoritmo di Floyd

Rete

Richiesta di memoria degli algoritmi di minimo percorso

Step 4 - Matrice C ⁴