Modelli di localizzazione e GIS - Tesi

METODI EURISTICI APPLICATI AI LOCATION MODEL

Come analizzato nel capitolo precedente, uno dei

problemi legati all’integrazione dei modelli di

localizzazione con GIS è quello di implementare e

analizzare nuove euristiche.

La necessità di studiare procedure di soluzioni euristiche

nasce principalmente dal fatto che algoritmi che

producono soluzione ottime richiedono molto sforzo a

livello computazionale, quindi è fondamentale ottenere

delle buone soluzioni in tempi rapidi ( algoritmi

sufficientemente efficienti nel determinare una soluzione

ammissibile di buona qualità senza alcuna pretesa di

ottimalità).

Formalmente indicheremo con il termine metodo

euristico un meccanismo logico algoritmico che ci sia di

ausilio e guida nella individuazione di soluzioni

ammissibili per un problema di ottimizzazione.

Definiremo metodo euristico o, più semplicemente

euristica, un metodo in grado di individuare una “buona

∈

soluzione” x S. 57

3.1 Risolvere il problema della p-mediana con

procedure euristiche

Come è stato osservato nel capitolo 2, nel problema della

p-mediana l’obiettivo è quello di attivare esattamente p

centri di servizio e, come si è detto, di assegnare ogni

∈

cliente v V ad un solo centro di servizio attivato in

modo tale da minimizzare la somma dei costi di

afferenza. Quindi l’obiettivo del problema della

p-mediana può essere espresso in funzione dell’insieme T

⊆ U dei centri di servizio attivati nella forma :

∑

Zm(T)= c vl(v,T)

∈

v V

Con riferimento alla funzione d’insieme Zm(T), possiamo

definire due metodi euristici: Algoritmo Greedy e

Algoritmo Teitz&Bart.

3.2 Algoritmo greedy

L’algoritmo greedy costruisce l’insieme degli impianti

attivati in passi successivi a partire dall’insieme vuoto. Ad

58

ogni passo, l’algoritmo sceglie tra gli impianti non attivati

quell’impianto che, con la sua aggiunta, causa la

massima diminuzione della funzione obiettivo Z(t). Se ad

un certo passo, l’aggiunta di un qualsiasi impianto non

attivato non causa una diminuzione della funzione Z(T)

allora l’algoritmo si ferma e l’insieme corrente di impianti

attivati definisce la soluzione ammissibile prodotta

dall’algoritmo (soluzione greedy). Più formalmente

abbiamo:

Algoritmo “greedy”

Fissato p centri di servizi da attivare

∅; ∞.

Inizializzazione: i= 1; T = Z(T )=

0 0

Fin quando |T |=p

i

Iterazione i-esima ∪{u});

U = argmin Z(T

i u∈U-Ti-1 i-1

∪{u

poni T =T }

i i-1 i

Se |T |=p

i

Allora  STOP:T è la soluzione greedy.

i

Altrimenti poni i:=i+1 e vai all’iterazione i.

Fine dell’iterazione i-esima.

Si osservi che l’algoritmo greedy ha due caratteristiche

cruciali: 59

(i)Una volta che un impianto viene inserito nell’insieme

degli impianti attivati non viene più rimosso.

(ii)L’impianto da aggiungere viene scelto ad ogni passo

guardando esclusivamente al vantaggio immediato

consistente in una diminuzione del valore della funzione

obiettivo.

3.2.1 Esempi Algoritmo greedy

Esempio 1

Si consideri il problema di Localizzazione degli impianti

caratterizzato dalla seguente matrice [c ](le righe sono

vu

associate ai clienti e le colonne agli impianti)[22]:

60

Applichiamo l’algoritmo greedy per p=3:

Inizializzazione

∅; ∞.

i = 1; T = Z(T ) =

0 0

Fisso p:3

Fin quando |T |=p

i

Iterazione 1 . Calcoliamo i valori della funzione obiettivo

∪ ∈

corrispondente agli insiemi T {u} con u U = {1….5}.

0

Z({1}) Z({2}) Z({3}) Z({4}) Z({5})

35 28 31 25 21

Ad esempio Z({5}) = (1 + 2 + 1 + 8 + 8 + 1 ) = 21.

Il valore minimo della funzione obiettivo si ottiene in

∪{5}

corrispondenza all’insieme T = {5}.

0

Minimo è Z({5}) = 21;

∞ ⇒

21 < i = 2, T = {5}.

1

Iterazione 2. Calcoliamo i valori della funzione obiettivo

∪ ∈

corrispondenti agli insiemi T {u} con u U – {5}.

1

Z({1,5}) Z({2,5}) Z({3,5}) Z({4,5})

16 9 12 18

Ad esempio Z({1,5}) = (1 + 2 + 1 + 3 + 8 + 1 ) = 16.

Il valore minimo della funzione obiettivo si ottiene in

∪{2}

corrispondenza all’insieme T = {2,5}.

1

61

Minimo è Z({2,5}) = 16;

⇒

16 <21 i = 3, T = {2,5}.

2

Iterazione 3. Calcoliamo i valori della funzione obiettivo

∪ ∈

corrispondenti agli insiemi T {u} con u U – {2,5}.

2

Z({1,2,5}) Z({2,3,5}) Z({2,4,5})

7 6 6

Ad esempio Z({1,2,5}) = (1 + 2 + 1 + 3 + 0 + 0 ) = 7.

Il valore minimo della funzione obiettivo si ottiene in

∪{3}

corrispondenza all’insieme T = {2,3,5}.

2

Minimo è Z({2,3,5}) = 7;

⇒

7<9 i = 4, T = {2,3,5}.

3

Siccome abbiamo fissato p=3 e dopo la terza iterazione

|T|=p abbiamo che T = {2,3,5}è la soluzione greedy.

3

Esempio 2

Si consideri, un problema di localizzazione di alcuni

impianti in città italiane. I dati relativi al costo di

spedizione sono i seguenti: 62

Fig 3.1 Applicazione euristica greedy

Nella figura sono identificati con il cerchietto rosso i siti candidati

all’attivazione, mentre con i quadratini blu vengono identificati i clienti(o

nodi domanda). 63

Determiniamo la soluzione greedy per p=3.

Inizializzazione

∅; ∞.

i = 1; T = Z(T ) =

0 0

Iterazione 1 . Calcoliamo i valori della funzione obiettivo

∪ ∈

corrispondente agli insiemi T {u} con u U = {1….5}.

0

Z({AN}) Z({BS}) Z({GE}) Z({LE}) Z({SA}) Z({VA

})

552 533 597 1014 777 608

Il valore minimo della funzione obiettivo si ottiene in

∪{BS}

corrispondenza all’insieme T = {BS}.

0

Minimo è Z({BS}) = 533;

∞ ⇒

533 < i = 2, T = {BS}.

1

Iterazione 2. Calcoliamo i valori della funzione obiettivo

∪ ∈

corrispondenti agli insiemi T {u} con u U – {BS}.

1

Z({AN,BS Z({BS,GE Z({BS,LE} Z({BS,SA Z({BS,VA

}) }) ) }) })

404 503 359 300 516

Il valore minimo della funzione obiettivo si ottiene in

∪{SA}

corrispondenza all’insieme T = {BS,SA}.

1

Minimo è Z({BS,SA}) = 300;

64

⇒

300 < 533 i = 3, T = {BS,SA}.

2

Iterazione 3. Calcoliamo i valori della funzione obiettivo

∪ ∈

corrispondenti agli insiemi T {u} con u U – {BS,SA}.

2

Z({AN,BS,SA} Z({BS,GE,SA} Z({BS,LE,S Z({BS,SA,V

) ) A}) A})

298 270 290 283

Il valore minimo della funzione obiettivo si ottiene in

∪{GE}

corrispondenza all’insieme T = {BS,GE,SA}.

2

Minimo è Z({BS,GE,SA}) = 270;

270 < 300

Siccome il valore di T coincide con p l’algoritmo termina.

La soluzione greedy pertanto corrisponde all’attivazione

di BG,GE,SA con un costo totale parti a 270.

65

Fig. 3.2Risultato algoritmo greedy

Come si è visto dall’esempio, la strategia greedy è

effettivamente miope e soffre dell’impossibilità di

rivedere le scelte fatte inizialmente.

66

Se avessimo preso in esame anche i costi di attivazione

degli impianti ad esempio la seguente matrice:

Applicando l’algoritmo greedy ecco il risultato:

67

Fig. 3.3Risultato localizzazione degli impianti

3.3 L’algoritmo di Teitz e Bart

Un algoritmo migliorativo per la p-mediana, basato sulla

sostituzione di vertici, è l’algoritmo di Teitz e Bart.

68

Teitz e Bart come esposto nel capitolo 2 è un euristica

presente nel sistema ARC/INFO.

Esso parte da una soluzione S di p vertici scelti a caso. Al

generico passo si verifica la possibilità di introdurre, al

∈ ∈

posto di un vertice i S, un vertice j S, calcolando

l’eventuale riduzione (o saving) s della funzione

ij

obiettivo. Si effettua quindi la sostituzione tra i e j

caratterizzati dal maggior saving positivo.

Si indica con S la soluzione corrente, con Z(S) il valore

della funzione obiettivo ad essa associato, e con S’

l’insieme dei nodi candidati a sostituire nodi di S.

L’algoritmo si sviluppa nei seguenti passi:

Inizializzazione

Si individuano p nodi che rappresentano la soluzione

corrente S, è da notare che la scelta può essere anche

del tutto casuale; si calcola z(S) e si pone

∀ ∈ ∀

S’= J-S, l(j)=1 j S e l(j)=0 j

∈ S’.

“J rappresenta l’insieme di tutte le facilities.”

69

Calcolo del saving ∈

Si sveglie un vertice j S’ tale che l(j)=0 e si considera la

∈

possibilità di sostituirlo a ciascun vertice i S, calcolando

il saving ∪

s = z(S)-z(S-{i} {j}).

ij

Criterio di arresto

≤ ∀ ∈ ∀

Se s 0 i S si pone l(j)=-1; nel caso in cui l(j)=-1 i

ij

∈ S’ allora l’algoritmo si arresta, altrimenti si ritorna al

passo 2. ≥

In caso contrario, ossia se esiste qualche i tale che s 0

ij

si individua l’indice i* corrispondente al massimo dei

saving positivi calcolati, e si pone: S = S∪ {j} – {i*},

∪ ∀ ∈ ∀ ∈

S’=S’ {i*}-{j }, l(i*)=-1, l(j)=1 j S ed l(j)=0 j

S’ – {i*}.

Il valore l(j)=-1 è associato al nodo di S sostituito

all’iterazione corrente e ai nodi di S’ per i quali è già

verificato che l’inserimento in S non ha prodotto

70

miglioramenti della soluzione. Si deduce quindi che

scegliendo al passo 2 i nodi con l(j)=0 si evita di

effettuare sostituzioni inutili.

Al termine della procedura, S è la soluzione del problema;

∈

mentre la domanda in i afferisce al nodo j* S tale che c ij

= min c

j∈S ij

3.3.1 Esempio Teitz e Bart

Data la seguente matrice dei costi di afferenza

applichiamo l’algoritmo di Teitz e Bart con p=3.

1 2 3 4 5 6

1 0 5 7 3 4 9

2 5 0 10 6 8 5

3 7 10 0 4 7 8

4 3 6 4 0 2 9

5 4 8 7 2 0 6

6 9 5 8 9 6 0

Occorre innanzitutto valutare i saving sij ossia il valore

∪

z(S-{i} {j}) che si ottiene sommando sulla matrice dei

costi di afferenza, il minimo di riga sulle colonne

∪

associate ai nodi (S-{i} {j}).

71

Inizializzazione

Consideriamo ad esempio la soluzione S={1,2,3} per

p=3 e S’={4,5,6},il valore di Z(S) è facilmente

calcolabile facendo la somma dei minimi di riga

relativamente alle colonne (1,2,3) ossia:

(0+0+0+3+4+5)=12.

∀ ∈ ∀ ∈

Poi poniamo l(j)=1 j