Antonio Sforza » 20.Ottimizzazione su rete: Problemi di progetto, circuito e localizzazione su rete

Schema della lezione

In questa lezione si descrivono i problemi di progetto, di circuito e di localizzazione su rete. Si tratta di problemi di ottimizzazione “difficili” dal punto di vista computazionale, rispetto ai problemi di percorso e di flusso che sono stati descritti nelle lezioni precedenti, che fanno parte tradizionalmente di corsi avanzati Ricerca Operativa.

Si descrive il modello matematico del problema generale di progetto e il caso particolare del problema dell’albero minimo, con due algoritmi risolutori.

Si descrivono poi i problemi di circuito, con riferimento ai problemi di circuito hamiltoniano minimo e circuito euleriano, e il noto problema del commesso viaggiatore (Travelling Salesman Problem).

Si descrivono infine i problemi di localizzazione su rete, attraverso le definizioni fondamentali delle misure di centralità di una rete e i problemi di centro e p-centro, mediana e p-mediana di una rete.

Progetto delle reti

Con l’espressione “progetto delle reti” si suole indicare quella classe di problemi nei quali, assegnato un insieme di vertici sede di attività che generano e/o attraggono flusso oppure generano una domanda di trasporto, e assegnato un insieme di archi potenziali per il collegamento dei vertici, è necessario determinare la configurazione della rete che ottimizza una funzione di prestazione legata ai costi di utenza e/o ai costi di costruzione.

I problemi di progetto delle reti intervengono in numerosi campi di applicazione, dalla pianificazione dei trasporti di persone e merci (nei vari possibili modi, stradale, ferroviario, aereo, navale) alla pianificazione delle risorse idriche, dalla logistica della distribuzione alle telecomunicazioni.

Nel seguito si presenta un modello generale di progetto della rete ed il problema dell’albero minimo risolto con l’algoritmi di Kruskal e l’algoritmo di Sollin.

Il modello di progetto di una rete

Assegnata una rete R(V, A, C, H), con V insieme di vertici, A insieme di archi, C insieme dei costi di spostamento e H insieme dei costi di costruzione, sia D_od la domanda di spostamento per la generica coppia o/d della rete e sia F l’insieme dei vertici destinazione. Le variabili del modello sono associate agli archi: variabili continue f_ij associate ai flussi e variabili discrete y_ij associate alle decisioni di progetto. Le variabili di progetto possono essere di due tipi: variabili binarie legate alla assenza/presenza dell’arco ( y_ij = 0/1) oppure variabili intere legate alla sua capacità ( y_ij = 0, 1, 2,…).
Se c_ij è il costo di spostamento su un arco (c_ij ∈ C) ed h_ij è il costo di costruzione dell’arco (h_ij ∈ H), si possono definire due funzioni di costo:
z₁ =∑_ij∈A c_ij f_ij, costo totale di utenza, z₂ = ∑_ij∈A h_ij y_ij, costo totale di costruzione.

Queste due voci di costo sono in conflitto tra loro perché quanto più alto è il numero di archi della rete tanto più alto sarà il costo di costruzione, ma tanto più basso, in generale, sarà il costo di utenza.

La funzione obiettivo, da minimizzare, può essere costituita dalla combinazione delle due componenti. Solitamente si ottimizza una delle due voci di costo e la seconda funzione di prestazione si trasferisce in vincolo, imponendo un limite superiore al costo di costruzione o al costo di utenza.

I vincoli del modello sono di tre tipi, vincoli di rete, analoghi a quelli già presenti nei modelli di flusso, vincolo di budget, in cui le variabili di progetto sono vincolate a rispettare il limite superiore B delle risorse disponibili, e vincoli di congruenza tra variabili di flusso e variabili di progetto.

Il modello di progetto

Vincoli di rete

Vincolo di budget

Il problema dell’albero minimo

Il problema dell’albero minimo è un problema di progetto in cui la rete da costruire è vincolata ad essere un albero. Si ricordi che un albero è un grafo non orientato, connesso e senza cicli. Esso pertanto ha v vertici e v-1 spigoli. Si ricordi inoltre che l’eliminazione di uno spigolo fa perdere la connessione e l’aggiunta di uno spigolo tra due vertici non adiacenti crea un ciclo.
Sia quindi R = (V, S, H) una rete connessa e non orientata, in cui V è l’insieme dei vertici, S l’insieme degli spigoli e H= {h_ij} un insieme di pesi associati agli spigoli, corrispondenti al costo di costruzione, installazione o gestione dell’arco. Il modello dell’albero minimo è il seguente:

Min z = ∑_ij∈S h_ij y_ij
s.a.
∑_ij∈S y_ij = v – 1 (1)
∑_i∈N ∑_j∈N y_ij ≤ |N|-1, ∀N: 2 ≤|N| ≤ v (2)

La funzione obiettivo esprime la minimizzazione del costo di costruzione dell’albero. Il vincolo (1) impone che il numero di spigoli sia pari a v-1. Il gruppo di vincoli (2) impone l’assenza di sottocicli tra i vertici del grafo. Esso impone infatti che comunque si prenda un sottoinsieme N dell’insieme V di vertici della rete, di cardinalità compresa tra 2 e v, il numero degli archi che connette i vertici di N sia al massimo pari a |N|-1. In tal modo questi archi costituiscono un albero tra i vertici di N e quindi sicuramente non chiudono ciclo.

Per la soluzione di questo problema si utilizzano algoritmi su rete esatti, molto semplici, come l’algoritmo di Kruskal o l’algoritmo di Sollin, descritti nelle slide successive.

Algoritmo di Kruskal

L’algoritmo di Kruskal effettua preliminarmente un ordinamento degli spigoli della rete per valore crescente del peso h_ij.

Se i primi v-1 spigoli della lista formano un albero essi costituiscono sicuramente la soluzione ottima del problema. Se ciò non avviene il valore di costo totale associato ai primi v-1 spigoli della lista costituisce sicuramente un limite inferiore al valore di costo dell’albero minimo.

Per determinare la soluzione ottima l’algoritmo inserisce nella soluzione ottima il primo ed il secondo spigolo della lista ordinata che sicuramente non costituiscono ciclo.

L’algoritmo scandisce quindi la lista ed esamina in successione uno spigolo per volta.

Se lo spigolo preso in esame non forma ciclo con gli spigoli già inseriti nella soluzione ottima viene inserito anch’esso nell’insieme di spigoli dell’albero minimo, altrimenti viene scartato.

L’algoritmo termina quando sono stati determinati v-1 spigoli. In questo modo si minimizza il costo aggiuntivo rispetto al limite inferiore corrispondente ai primi v-1 spigoli della lista ordinata e si determina un insieme di spigoli che costituisce l’albero minimo.

Applicazione dell’algoritmo di Kruskal

Applicazione dell'algoritmo di Kruskal

Lista degli spigoli della rete ordinati per costo h_ij crescente

Algoritmo di Sollin

L’algoritmo di Sollin effettua preliminarmente un ordinamento dei vertici della rete ed individua per ciascun vertice lo spigolo incidente in esso con costo h_ij minimo. Se gli spigoli così individuati formano un albero, essi costituiscono la soluzione ottima del problema. Se ciò non avviene il valore di costo totale ad essi associato costituisce sicuramente un limite inferiore al valore di costo dell’albero minimo.

L’algoritmo scandisce quindi la lista dei vertici, iniziando dal primo e inserendo nella soluzione ottima lo spigolo di costo minimo ad esso associato. Il vertice che costituisce l’altro estremo di tale spigolo viene escluso dalla lista per la scansione corrente dei vertici. L’algoritmo esamina quindi in successione il vertice successivo della lista ed inserisce nella soluzione ottima lo spigolo di costo minimo ad esso associato. Il meccanismo di scansione utilizzato garantisce che il nuovo spigolo inserito nella lista non formi ciclo con gli spigoli precedentemente inseriti. Il vertice che costituisce l’altro estremo del nuovo spigolo viene escluso dalla lista dei vertici. Si procede quindi identicamente esaminando in successione i vertici della lista. Quando si esaurisce la lista dei vertici da esaminare si possono verificare due situazioni:

• gli spigoli selezionati sono v-1; essi formano sicuramente un albero e costituiscono la soluzione ottima del problema
• gli spigoli selezionati sono in numero inferiore a v-1. In questo caso essi costituiscono due o più alberi parziali. Questi alberi parziali vengono considerati come macrovertici connessi dagli spigoli del grafo originario. A questo nuovo grafo si applica la stessa procedura fino ad ottenere un albero unico, costituito da v-1 spigoli, che costituisce l’albero minimo del grafo assegnato

Applicazione dell’algoritmo di Sollin

Applicazione dell'algoritmo di Sollin

Spigoli di costo minimo incidenti in ciascun vertice

Macrovertici

Connessione dei macrovertici

Circuito

Con l’espressione “problemi di circuito” si indica solitamente quella classe di problemi nei quali è necessario determinare su una rete un circuito ottimo che passi attraverso un preassegnato insieme di vertici o di archi. I problemi di circuito intervengono in numerosi campi di applicazione (raccolta e distribuzione di merci, rifiuti, posta, informazioni, etc).

Un circuito di una rete è una successione ordinata di archi costituente un percorso chiuso, cioè tale che il vertice destinazione coincida con il vertice origine del percorso stesso. Sono stati definiti due particolari tipi di circuito: il circuito hamiltoniano ed il circuito euleriano.

Il circuito hamiltoniano tocca tutti i vertici della rete attraversando ciascuno una sola volta.

Il circuito euleriano passa per tutti gli archi della rete, attraversando ciascuno una sola volta.

Questi due tipi di circuito costituiscono il punto di riferimento per la soluzione di due classici problemi di ottimizzazione su rete: il problema del Commesso Viaggiatore ed il problema del Postino, descritti nelle slide successive.

Il problema del Commesso Viaggiatore

Il problema del commesso viaggiatore (Traveling Salesman Problem) è un famoso problema di ottimizzazione combinatoria al quale è stata dedicata molta attenzione in letteratura. Il problema è quello di un commesso viaggiatore che voglia visitare un certo numero di città e ritornare in quella di partenza utilizzando il circuito più breve. In altri termini, data una rete orientata R (V, A, C) connessa e senza cappi, con costi costanti c_ij∈ C, si vuole trovare il circuito di costo minimo che tocchi tutti i vertici della rete, attraversando ciascuno di essi almeno una volta.

Se la rete è piena e i costi sugli archi rispettano la “disuguaglianza triangolare” [c_ij ≤ c_ik + c_kj, per ogni arco ij e per ogni vertice k esterno ad esso], si può dimostrare che il circuito minimo sulla rete è un circuito hamiltoniano. Si dimostra infatti che una rete piena contiene almeno un circuito hamiltoniano ed inoltre, nell’ipotesi che valga la disuguaglianza triangolare, per ogni circuito che passa per ogni vertice della rete almeno una volta esiste almeno un circuito hamiltoniano di costo non maggiore. Sotto le ipotesi enunciate il problema del Commesso Viaggiatore diventa quello della individuazione del circuito hamiltoniano minimo su una rete orientata, piena, senza cappi, con costi sugli archi non negativi e non necessariamente simmetrici, che rispettino la disuguaglianza triangolare.

In una slide successiva si riporta una rete piena per la quale i costi rispettano la disuguaglianza triangolare. Il circuito hamiltoniano minimo, di costo 17, è costituito dagli archi 1-4, 4-2, 2-3, 3-1.
Il problema del Commesso Viaggiatore si risolve mediante algoritmi esatti (Branch and Bound, Branch and Cut), e mediante algoritmi approssimati di tipo euristico. Per la descrizione di questi algoritmi si rinvia a testi specialistici di ottimizzazione combinatoria su rete utilizzati nei corsi avanzati di Ricerca Operativa.

Il modello del circuito hamiltoniano minimo

Se si adotta una variabile x_ij che vale 1 se l’arco ij appartiene al circuito, 0 altrimenti, il problema del circuito hamiltoniano minimo può essere formulato nel modo seguente:

Min z = ∑_ij c_ijx_ij
s.a
∑_i=1,v x_ij = 1, …………………………….∀j = 1, v  (1)
∑_j=1,v x_ij = 1, ……………………………∀i = 1, v  (2)
∑_i∈N ∑_j∈N x_ij ≤|N|-1, ∀N: 2 ≤|N|≤ v -1 (3)

Il gruppo di vincoli (1) impone che in una soluzione ogni vertice sia destinazione di un solo arco. Il gruppo di vincoli (2) impone che ogni vertice sia origine di un solo arco. Il gruppo di vincoli (3) impone l’assenza di sottogiri.

Rete non piena e/o senza disuguaglianza triangolare => circuito minimo non hamiltoniano

Se la rete è connessa ma non è piena, ovvero esistono archi per i quali non è rispettata la disuguaglianza triangolare, non c’è garanzia che il circuito minimo sia hamiltoniano e quindi il modello di circuito hamiltoniano minimo non può essere utilizzato per determinare il circuito minimo di una rete. Ci si può in ogni caso ricondurre alle condizioni di circuito hamiltoniano minimo. Infatti per ogni coppia di nodi ( i, j ) non collegati da un arco diretto o collegati da un arco diretto che non rispetti la disuguaglianza triangolare, si può introdurre un arco fittizio di costo pari a quello del percorso minimo tra i due nodi. Ciò equivale in realtà a costruire una rete fittizia corrispondente alla matrice delle distanze minime, che è sicuramente piena e rispetta la disuguaglianza triangolare. Ci si riconduce in questo modo alle condizioni per le quali è possibile adottare il modello descritto e si determina il circuito hamiltoniano minimo su questa rete fittizia. Esso corrisponde sulla rete originaria ad un circuito che potrebbe essere non hamiltoniano, passando più di una volta per uno stesso vertice, come è logico che possa avvenire nei casi applicativi reali.

Nella slide successiva si riporta una rete non piena (a), per la quale i costi su alcuni archi non rispettano la disuguaglianza triangolare. La rete (b) è la rete delle distanze minime, piena e con disuguaglianza triangolare. A ciascuno degli archi di questa rete corrisponde un arco o un percorso della rete (a). Su questa rete il circuito minimo è hamiltoniano (c). A questo circuito hamiltoniano, in base alle corrispondenze tra le reti (a) e (b), corrisponde un circuito minimo non hamiltoniano sulla rete (a), di costo 16, costituito dagli archi 1-4, 4-3, 3-4, 4-2, 2-1.

Rete non piena e/o senza disuguaglianza triangolare

Il problema del postino

Il problema del Postino (Postman Problem) è quello di percorrere tutti gli archi di una rete per consegnare le lettere, utilizzando se necessario il circuito più breve. Data una rete orientata o non orientata R (V, A, C), connessa e senza cappi, ad ogni arco della quale sia associato un costo costante, si vuole trovare il circuito di costo minimo che passi per tutti gli archi della rete, attraversando ciascuno di essi almeno una volta. È necessario infatti verificare che il grafo sia euleriano. Un grafo è detto euleriano se esiste un circuito che contiene ciascun arco esattamente una volta e ciascun nodo almeno una volta. Le condizioni (necessarie e sufficienti) affinché un grafo sia euleriano sono le seguenti: se G è non orientato, ogni vertice deve essere di grado pari, ovvero deve essere pari il numero degli spigoli (archi non orientati) incidenti in ciascun vertice. Questa condizione fu provata da Eulero nel 1736; se G è orientato, il numero degli archi entranti in ciascun vertice deve essere uguale al numero degli archi uscenti.

Se queste condizioni sono soddisfatte è possibile determinare il circuito euleriano sulla rete mediante semplici algoritmi su rete. Nella slide successiva si riporta una rete orientata che rispetta le condizioni di esistenza del circuito euleriano ed uno dei possibili circuiti euleriani. Se le condizioni non sono soddisfatte gli algoritmi per la soluzione del problema del postino si articolano in due fasi distinte. La prima consiste nel determinare la trasformazione di minimo costo del grafo, ovvero il minimo costo di aggiunta di archi che lo rendano euleriano. La seconda consiste nel definire il circuito di percorrenza del grafo divenuto euleriano. Anche per l’esposizione di questi metodi si rinvia a testi specialistici utilizzati nei corsi avanzati di Ricerca Operativa.

Il problema del postino

Rete orientata euleriana

Circuito euleriano

Localizzazione su rete

Con l’espressione “localizzazione su rete” si indicano quei problemi che intervengono quando è necessario determinare la localizzare ottima nei vertici di una rete di uno o più impianti per la produzione di un bene o l’erogazione di un servizio.

Problemi di localizzazione si presentano in numerosi campi di applicazione: nella logistica industriale, quando è necessario localizzare stabilimenti e/o depositi per la produzione e/o la distribuzione di un prodotto ai clienti presenti nei nodi della rete; nella gestione dei servizi sociali e della pubblica amministrazione, quando è necessario localizzare scuole, ospedali o uffici; nella progettazione delle reti di trasporto collettivo su ferro o su gomma, delle reti di comunicazione e delle reti di computer.

È possibile definire numerosi problemi di localizzazione su rete. Essi si differenziano per l’obiettivo da raggiungere (min-max, min-sum; monobiettivo-multiobiettivo), per le restrizioni alla possibilità di localizzazione (nei vertici o in punti qualunque degli archi), per la presenza di vincoli (distanza massima tra gli impianti e i nodi serviti; capacità degli impianti), per l’arco temporale cui si riferisce la localizzazione (monoperiodo, multiperiodo), per la presenza di competizione tra gli impianti (localizzazione competitiva o non competitiva), in base alla struttura degli impianti (strutture puntuali o di percorso), in base alla natura degli impianti da localizzare (generatori e/o attrattori di flusso oppure intercettori di flusso).

Nel seguito si espongono le misure di centralità ed i problemi di localizzazione su rete ad esse associati. Questi problemi sono in generale problemi monobiettivo di tipo min-max o min-sum e possono essere definiti su una rete generale o su un albero. Per ognuno dei problemi definiti sono stati proposti in letteratura numerosi algoritmi risolutivi, di tipo esatto o approssimato, per i quali si rimanda a testi specialistici.

Misure di centralità su rete

Per descrivere i problemi e i modelli di localizzazione su rete è opportuno definire alcuni parametri che misurano la collocazione di un vertice o di un insieme di vertici nella rete. Si consideri un grafo G(V, S), connesso e non orientato in cui V è l’insieme dei vertici ed S l’insieme degli spigoli. Sia inoltre W l’insieme dei pesi associati ai vertici e C l’insieme dei pesi associati agli spigoli.
Si definisce distanza tra due vertici i e k, la distanza minima C(i, k) tra u e k. Se i vertici sono pesati si definisce la distanza minima pesata C_w(i, k) tra due vertici i e k. Viene espressa in funzione della distanza minima non pesata e del peso di uno dei due vertici: C_w(i, k) = C(i, k) w_u. Si definisce distanza tra un insieme S_p di p vertici ed un vertice k, la quantità C(S_p, k): C(S_p, k) = min_i∈Sp C(i, k) ∀ k∈V

Eccentricità e distanza di un vertice
Si definisce eccentricità di un vertice u e si indica con e(i) la massima distanza fra i ed un altro vertice della rete: e(i) = ma_xk∈V C(i, k). Si definisce distanza di un vertice i, e si indica con C(i), la somma delle distanze tra i e gli altri vertici del grafo: C(i) = ∑_k∈V C(i, k). Le definizioni di eccentricità e distanza possono essere estese al caso di vertici pesati, utilizzando le distanze pesate.
Eccentricità e distanza di un insieme di vertici
Si definisce eccentricità e(S_p) di un sottoinsieme S_p di vertici la massima delle distanze tra il sottoinsieme S_p e gli altri vertici del grafo: e(S_p) = max_k∈V C(S_p, k). Si definisce distanza C(S_p) di un sottoinsieme S_p di vertici la somma delle distanze tra S_p e gli altri vertici del grafo: C(S_p) = ∑_k∈V C(S_p, k). Anche queste definizioni di eccentricità e distanza possono essere estese al caso di vertici pesati. Si riporta nella tabella della slide successiva un quadro riassuntivo delle definizioni delle misure di centralità.

Misure di centralità su rete

Misure di centralità di un vertice u

Distanza tra due vertici u e k: distanza minima C(u, k)

Eccentricità di u: e(u)=max_k∈V[C(u, k)]

Distanza di u: d(u)=Σ_k∈VC(u, k)

Misure di centralità di un insieme S di vertici u

Distanza tra S e un vertice k: C(S_p, k)=min_u∈Sp C(u,k), ∀ k∈V

Eccentricità di S: e(Sp)=max_k∈V[C(S_p, k)]

Distanza di S: C(S_p)=Σ_k∈VC(S_p, k)

Centro e p-centro di una rete

Il centro di una rete è il vertice i*∈V di eccentricità minima, cioè tale che:

e( i* ) = min _u∈V [e( i )] = min _i∈V max _k∈V C( i, k)

Per trovare il centro di una rete, con vertici pesati o non pesati, è necessario: calcolare la matrice delle distanze minime, con un costo computazionale O(v²), determinare per ogni riga il valore massimo, cioè l’eccentricità del vertice corrispondente, e determinare infine la minima eccentricità. Il vertice ad essa corrispondente è il centro della rete.

Se viene rimossa la restrizione che il centro debba essere un vertice della rete, si può definire il centro assoluto di una rete come il punto della rete che presenta eccentricità minima.

Il concetto di centro può essere generalizzato in modo che un insieme di p vertici formi un multicentro (p-centro). Pertanto, con riferimento alla definizione di eccentricità di un sottoinsieme S_p di vertici, si può definire il p-centro di una rete come l’insieme di vertici S_p* di eccentricità minima, cioè tale che:

e(S_p*) = minS_p∈V e[S_p] = min_Sp∈V max_k∈V C(S_p, k)

Si può definire infine il p-centro assoluto di una rete come l’insieme di p punti della rete che presenta eccentricità minima.

Mediana e p-mediana di una rete

La mediana di una rete è il vertice iˆ∈V di distanza minima, cioè tale che:

C( iˆ) = min _i∈V [C( i )] = min _u∈V ∑_k∈V C( i, k)

Per trovare la mediana di una rete, con vertici pesati o non pesati, è necessario calcolare la matrice delle distanze minime, effettuando la somma di ciascuna riga i (distanza del vertice i) e determinare il minimo delle somme così calcolate. Il vertice ad esso corrispondente è la mediana della rete.

Se viene rimossa la restrizione che la mediana debba essere un vertice della rete, si può definire la mediana assoluta come il punto della rete che presenta distanza minima. Si dimostra che la mediana assoluta coincide con la mediana.

Il concetto di mediana può essere generalizzato in modo che un insieme di p vertici formi una multimediana (p-mediana). Pertanto, con riferimento alla definizione di distanza di un sottoinsieme S_p di vertici, si può definire la p-mediana di una rete come l’insieme di p-vertici S_p* tali che sia minima la somma delle distanze minime da essi a tutti gli altri vertici del grafo.

C(S_p*) = min_Sp∈V [C(S_p)] = min_Sp∈V ∑_k∈V C(S_p, k).

Il modello di p-mediana

Il problema di p-mediana può essere formulato attraverso un modello che presenta due tipi di variabili, y_i (i ∈V ) ed xi_j ( ij∈A ), y_iè pari a 1 se il vertice i è mediana, è pari a zero altrimenti. Ciascuna variabile x_ij è invece associata ad una coppia di vertici ij della rete collegati da un arco o da un percorso ed assume valore 1 se il vertice j afferisce al nodo i, 0 altrimenti. Si osservi che, assumendo c_ii = 0 (i =1,…, n), se il vertice i è mediana ( y_i=1), i afferirà a se stesso e dunque x_ii =1. Se il vertice i non è mediana (y_i= 0), nessun vertice afferirà ad esso, in particolare il vertice i stesso, e pertanto si avrà x_ii = 0. Esiste dunque una corrispondenza biunivoca tra le variabili y_i e x_ii.

Il modello di p-mediana

Il vincolo (1) impone la condizione che il vertice i o è mediana, oppure deve afferire a qualche altro vertice. Il vincolo (2) impone la condizione che il vertice j può afferire al vertice i solo se i è mediana. Il vincolo (3) impone la condizione che il numero di vertici mediana sia uguale a p.

s.a.