Università degli studi Roma Tre

Facoltà di Scienze Matematiche Fisiche e Naturali Corso di Laurea in Matematica

Sintesi della Tesi di Laurea in Matematica di

Davide Rossi

Metodi di ottimizzazione per problemi di distribuzione

Relatore Prof. Marco Liverani

Il Candidato Il Relatore

Anno Accademico 2002/2003 Luglio 2003

Indice

Introduzione 3

1 Metodo del Simplesso 5

1.1 Programmazione Lineare, Lineare Intera, Lineare {0,1} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.1 Metodo del Simplesso . . . . . . . . . . . . . . . . . . . . . 7 1.1.2 Oracolo di Separazione - Simplesso Dinamico Primale … 7 1.1.3 Oracolo di Generazione di Colonne - Simplesso Dinamico

Duale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Soluzione del Problema di Localizzazione degli Impianti delle Poste Italiane con algoritmi di Ricerca Operativa 11 2.1 Formulazione del Problema . . . . . . . . . . . . . . . . . . . . . . 12

2.1.1 Vincoli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1.2 Mezzi di trasporto . . . . . . . . . . . . . . . . . . . . . . 13 2.1.3 Definizione della funzione costo . . . . . . . . . . . . . . . 13 2.1.4 Costo di Attivazione . . . . . . . . . . . . . . . . . . . . . 13 2.2 Risoluzione del Problema . . . . . . . . . . . . . . . . . . . . . . . 14

2.2.1 Calcolo del costo minimo . . . . . . . . . . . . . . . . . . . 14 2.2.2 Calcolo del lower bound . . . . . . . . . . . . . . . . . . . 16 2.2.3 Individuazione dei possibili centri di servizio . . . . . . . . 17 2.2.4 Assegnazione dei centri di servizio e dei clienti . . . . . . . 19 2.2.5 Aggiornamento della soluzione . . . . . . . . . . . . . . . . 20

A Alcune schermate del programma 23

Introduzione

Lo scorso anno sono stato contattato da Progetti & Tecnologie, azienda del gruppo Quattroemme S.P.A., con la quale ho iniziato a collaborare sviluppando la tesi proposta.

Attualmente Progetti & Tecnologie sta operando anche come consulente per le Poste Italiane ed è proprio da tale rapporto che nasce l’esigenza di risolvere un problema riguardante la localizzazione geografica di centri di distribuzione propostomi per la tesi.

Scopo ed obiettivo della tesi

Il tema da sviluppare assegnatomi per le Poste Italiane riguarda il Problema di Localizzazione degli Impianti. Si richiede di individuare i centri di servizio (impianti addetti alla raccolta e alla distribuzione dei prodotti postali) e i clienti da associare a ciascun impianto. La realizzazione di un algoritmo efficiente per la risoluzione di questo problema permetterebbe di ottenere su tutta le rete nazionale una distribuzione degli impianti e degli uffici postali tale da minimizzare i costi di edificazione dei centri di servizio e i costi di trasporto dei prodotti postali.

La soluzione proposta nella tesi è basata sull’utilizzo di diversi algoritmi e metodologie classiche della Ricerca Operativa, con una rappresentazione del problema che alterna l’uso di grafi orientati con sistemi di equazioni lineare di dimensione anche molto elevata. In figura 2.1 riportiamo uno schema generale del metodo risolutivo.

La soluzione del problema è corredata dalla realizzazione di un programma in linguaggio Java che ci ha permesso di compiere diverse simulazioni. Java attualmente è uno tra gli strumenti più potenti di cui dispone la tecnologia informatica.

Utilizzeremo strategie tipiche degli strumenti GIS (Georaphic Information System) per risolvere il nostro problema sviluppando una significativa proiezione geografica in grado di rappresentare graficamente una precisa e dettagliata mappa tematica dell’Italia sulla quale verrano distinti tutti i centri di servizio, tutti i clienti e i percorsi.

Capitolo 1

Metodo del Simplesso

Proponiamo come tecnica risolutive per il problema di ottimizzazione il metodo del Simplesso Dinamico Duale. Descriveremo tale strategia facendo riferimento alla Programmazione Lineare, Lineare Intera e {0,1}, al metodo del Simplesso e del Simplesso Dinamoco.

1.1 Programmazione Lineare, Lineare Intera, Lineare {0,1}

La Programmazione Lineare (PL) è una tecnica usata per fornire una descrizione matematica, ovvero un modello, di un problema della vita reale in cui una funzione, detta funzione obiettivo, deve essere massimizzata o minimizzata. La soluzione ottima del problema si ottiene con la scelta opportuna di valori delle variabili strutturali del modello. I parametri sono passibili di uno o più vincoli, equazioni o disequazioni, che descrivono le restrizioni alle quali deve essere soggetta la funzione durante il processo. I valori delle variabili che soddisfano tutti i vincoli corrispondono ai punti che giacciono entro una determinata figura geometrica: se le variabili sono due, quella figura sarà un poligono il cui numero di lati corrisponde al numero dei vincoli; se le variabili sono tre, sarà un poliedro; se sono n, sarà un politopo in uno sapzio n-dimensionale.

Sia f la funzione obiettivo, dipendente da n variabili x_{1}, …, x_{n}, definita in un campo S e le m equazioni del sistema in n incognite con m < n detto sistema di vincoli. Il problema di ottimizzare la funzione obiettivo acquista significato se si impone alle variabili x_{j} la condizione di non assumere valori negativi come spesso si richiede, del resto, che sia nei problemi concreti.

Il processo di associazione di un modello matematico ad un problema reale viene comunemente detto formulazione del problema. In generale la formulazione di un problema di P L è descritta nella seguente maniera:

min \{ \begin{matrix}c^{T} x \\ Hx ≥ d \\ x ∈ ℝ^{n} \\ x ≥ 0 \end{matrix}

I valori di x che soddisfano i vincoli Hx ≤ d, dove H è la matrice m × n dei coefficienti dei vincoli, sono detti soluzioni ammissibili del problema di PL. Si osservi che la regione ammissibile è descritta dal poliedro P = {x ∈ ℝ^{n} : Hx ≥ d, x ≥ 0}.

Ogni problema di PL è completamente caratterizzato dall’insieme S delle soluzioni ammissibili e dal vettore c dei costi e qundi potrà essere sempre descritto dalla coppia (S, c). Il problema consiste nell’ottimizzare la funzione lineare al contorno del suo campo di definizione S.

I problemi di Programmazione Lineare nei quali le variabili sono vincolate ad assumere valori interi sono detti problemi di Programmazione Lineare Intera (PLI).

Un generico problema di Programmazione Lineare {0,1} (PL01) è caratterizzato da un insieme di vettori S ⊆ {0, 1}^{n} (regione ammissibile) e da un vettore di costo c ∈ ℝ^{n}. Ciascun vettore x ∈ S è detto soluzione ammissibile.

1.1.1 Metodo del Simplesso

Si intuisce facilmente che per n ed m abbastanza grandi, sarebbe molto difficile determinare tutte le soluzioni possibili del problema e, quindi, scegliere tra queste quelle che ottimizzano la funzione obiettivo. Utilizzeremo, al fine di risolvere tale problema, il Metodo del Simplesso. Con questo metodo di calcolo, partendo da una qualunque soluzione base, si riesce a determinare la soluzione ottima con approssimazioni successive. È ovvio che questo metodo dispone di un criterio per stabilire se la soluzione presa in esame è ottima oppure no. Nella seconda alternativa, lo stesso criterio consente di passare ad un’altra soluzione base che sia migliore della precedente ai fini dell’ottimizzazione della funzione f. Dopo un numero finito di passi viene raggiunta la soluzione ottima.

Ricordando la rappresentazione geometrica dei vincoli, si ha che il problema di PL si riduce a trovare il vertice della regione vincolare (poligono, poliedro o politopo) in cui si verifica l’ottimizzazione. Ci potrebbero essere milioni di vertici, per cui una ricerca sistematica è fuori discussione. Con l’algoritmo del simplesso si parte da un vertice e poi ci si sposta sulla superficie del politopo, lungo i lati, da vertice a vertice. Ogni volta che si arriva a un vertice, ci saranno varie direzioni in cui procedere. Il criterio più ovvio da seguire, consiste nel portarsi a un vertice che aumenta la quantità da massimizzare, o la diminuisce se è da minimizzare. A causa dell’enorme numero di percorsi possibili intorno ai vertici di un politopo, l’algoritmo del simplesso, in teoria, è un algoritmo di complessità esponenziale, quindi inefficiente, ma quando viene usato praticamente, su problemi che implicano centinaia o addirittura migliaia di variabili, funziona molto bene, puntando direttamente verso il vertice ottimale con relativamente pochi passaggi.

1.1.2 Oracolo di Separazione - Simplesso Dinamico Primale

Il Metodo Dinamico del Simplesso nella sua versione primale acquisisce le informazioni sulla struttura del poliedro P non da una esplicita rappresentazione in termini di disequazioni Hx ≥ d, bensì da una sua rappresentazione implicita realizzata per mezzo di un Oracolo di Separazione che, dato un vettore x̄ ∈ ℝ^{n}, fornisce una disequazione h^{T} x ≥ h_{0} appartenente al sistema Hx ≥ d e con la proprietà che h^{T} x < h_{0} (vincolo violato) o conclude che tutte le disequazioni Hx ≥ d sono soddisfatte da x̄.

Da un punto di vista geometrico, l’Oracolo costruisce, se esiste, un iperpiano che definisce una faccia di P e che separa i vettori appartenenti a P dal punto x̄ (iperpiano di separazione o piano di taglio). Se tale iperpiano non esiste allora il punto x̄ appartiene al poliedro P.

Il metodo del Simplesso Dinamico Primale converge in un numero finito di passi in quanto, nel caso peggiore, esso sarà costretto ad aggiungere tutte le disequazioni della rappresentazione Hx ≤ d.

1.1.3 Oracolo di Generazione di Colonne - Simplesso Dinamico Duale

In questo paragrafo descriveremo come il Metodo del Simplesso Dinamico possa essere utilizzato per risolvere problemi con un grandissimo numero di variabili. A questo scopo descriveremo il Metodo Duale, anche questo metodo è basato su un Oracolo che tratta in modo implicito le variabili del problema min{c^{T} x : Hx ≥ d, x ≥ 0_{n}}.

In particolare, risolve (utilizzando il metodo classico del simplesso) una sequenza di problemi parziali della forma min{c_{D}^{T}z : Dz ≥ d, z ≥ 0_{q}} con D sottomatrice di H con m righe e q ≪ n colonne, z vettore in ℝ^{q} e c_{D} sottovettore del vettore c associato alle colonne di D. Il Metodo viene inizializzato scegliendo opportunamente un primo problema parziale min{c_{D_{0}}^{T}z : D_{0}z ≤ d, z ≥ 0_{q}} (problema parziale iniziale). Successivamente, ciascun problema parziale della sequenza viene generato aggiungendo al precedente una colonna prodotta da un opportuno Oracolo di Generazione di Colonne.

Per descrivere il meccanismo di generazione delle colonne, assumiamo che ciascun problema parziale della sequenza sia ammissibile e limitato (duale ammissibile) e denotiamo con z̄ ∈ ℝ^{q} e λ̄ ∈ ℝ^{m} la coppia di soluzioni ottime del primale e del duale.

Lo scopo dell’Oracolo di Generazione di Colonne, è quello di individuare, se esiste, un vincolo duale violato dalla soluzione λ̄ (o, in modo equivalente, una colonna del problema primale con costo ridotto negativo rispetto a λ̄) oppure rispondere che tutte le colonne del problema hanno costi ridotti positivi o nulli.

Valgono per l’Oracolo di Generazione di Colonne tutte le osservazioni fatte riguardo all’Oracolo di Separazione. In particolare, ache in questo caso abbiamo che l’Oracolo può essere realizzato con un algoritmo che, senza calcolare “esplicitamente” tutti i costi ridotti, ne fornisca uno negativo o risponda che tutti i costi ridotti sono positi o nulli.

La struttura del Metodo del Simplesso Dinamico Duale può essere così descritta:

Metodo del Simplesso Dinamico Duale

1. Definire un sottoproblema parziale iniziale min{c_{D}^{T}z ∈ ℝ^{q} : D_{z} ≥ d, z ≥ 0_{q}} (problema corrente) con D = D_{0} sottomatrice di H con q ≪ m righe ed n colonne, con c_{D} sottovettore di c corrispondente a D e con P_{0} = {z ∈ ℝq : D_{z} ≥ d, z ≥ 0_{q}} limitato e non vuoto.

2. Risolvere il problema corrente min{c_{D}^{T}z ∈ ℝ^{q} : D_{z} ≥ d, z ≥ 0_{q}} utilizzando il Metodo del Simplesso. Siano z̄ e λ̄ la coppia di soluzioni ottime per il primale e per il duale del problema corrente.

3. Applicare l’Algoritmo di Generazione di Colonne per generare una colonna con costo ridotto negativo rispetto a λ̄. Se tale colonna viene generata, aggiungerla al problema corrente e tornare al passo 2.

4. Se, invece, nessuna colonna con costo ridotto negativo viene generata, allora tutte le colonne hanno costo ridotto positivo o nullo ed il vettore x̄ = (z̄, 0_{n−q}) è una soluzione ottima del problema originario.

Capitolo 2

Soluzione del Problema di Localizzazione degli Impianti delle Poste Italiane con algoritmi di Ricerca Operativa

Risolveremo il Problema di Localizzazione degli Impianti limitandoci ai modelli con singolo obiettivo e singolo prodotto.

L’obiettivo sar quello di attivare un insieme T di centri di servizio e di assegnare ogni cliente ad un centro attivato in modo da minimizzare i costi. Dal momento che abbiamo deciso di rispettare la struttura attuale della rete di distribuzione postale, il processo di localizzazione dei centri di servizio e dei relativi clienti sarà ripartito in tre sotto problemi corrispondenti ai livelli che definiscono i diversi centri di servizio (hub, nazionale, provinciale).

Il prodotto postale che consideremo, è costituito lettere il cui peso può essere modificato dall’utente. Supporremo che all’istante iniziale gli hub siano stati già riforniti. Quindi escluderemo la parte che riguarda la distribuzione della merce dal fornitore ai depositi postali.

Otterremo come soluzione una rete a stella i cui nodi (centri di servizio) sono distribuiti su due livelli: livello nazionale (primo livello) e livello provinciale (secondo livello). A monte della rete saranno presenti due hub che riforniscono i centri di servizio nazionale. Dai centri provinciali, serviti dai centri di servizio nazionale, partono i collegamenti agli Uffici Postali.

Una rete a stella è formata da un nodo centrale a cui sono collegati tutti gli altri nodi. Quindi, nel nostro caso, abbiamo due nodi centrali hub a cui sono connessi i rispettivi centri di servizio nazionale. Ogni centro nazionale rappresenta a sua volta un nodo centrale a cui sono collegati i centri di servizio provinciale.

Allo scopo di risolvere il problema sopra citato calcoleremo, fissato un valore per il numero di centri di servizio da attivare sui tre livelli della rete a stella, quanti e quali sono gli impianti di raccolta e di distribuzione e i relativi clienti associati.

2.1 Formulazione del Problema

La rete di distribuzione del problema che vogliamo risolvere è caratterizzata da un un grafo G = (V, E) orientato e connesso. V è l’insieme dei vertici che rappresentano i potenziali centri di servizio e clienti. E è l’insieme degli spigoli del grafo, riproduzione della rete stradale che connette i nodi tra loro.

2.1.1 Vincoli

I vincoli, associati al modello proposto, sono rappresentati dalla struttura della domanda ossia la distribuzione spaziale dei potenziali clienti e la quantità di merce da essi richiesta, dalla struttura dei trasporti e della rete di comunicazione, e dalla struttura delgli impianti (centri di servizio). La domanda è definita dal prodotto tra il numero della popolazione, dell’area in questione, e la quantità richiesta per ogni individuo. I mezzi di Trasporto sono distinti dalla capacità di carico e dal consumo per chilometro. Le strade sono classificate in autostrade, super strade e strade statali. Infine gli impianti sono definiti dalla posizione geografica e dal costo di attivazione. Questi parametri definiscono i vincoli per il problema.

2.1.2 Mezzi di trasporto

I mezzi inpiegati per il trasporto della merce lungo la rete stradale, di norma sono autoarticolati e furgoni. Gli autoarticolati verranno utilizzati per il trasporto della merce dagli hub ai centri di servizio nazionale, e dai centri di servizio nazionale a quelli provinciali, mentre tutti gli Uffici Postali serviti dai centri provinciali verranno raggiuniti dai furgoni. Questa scelta stata ponderata in funzione del costo di trasporto e della capacità dei veicoli. Infatti la quantità di merce da trasportare dai centri provinciali agli uffici postali di gran lunga inferiore rispetto a quella che va inviata dagli hub ai centri nazionali e da questi a quelli provinciali dal momento che c’è sta una ripartizione dei prodotti da distribuire tra i centri di sevizio.

Noi impostiamo questo vincolo variaible in modo da tale rendere possibile la scelta del mezzo di trasporto da utilizzare per ogni livello.

2.1.3 Definizione della funzione costo

Dato il grafo G indichiamo con i nodi v ∈ V e u ∈ V rispettivamente i potenziali clienti e i potenziali centri di servizio. La funzione costo è quinidi definita nel modo seguente:

c_{uv} = d_{v}(l_{uv}t)

dove d_{v} è la domanda del cliente v, l_{uv} è la lunghezza del cammino da u a v, t è il costo di trasporto della merce per unità di peso (Kg) e unità di distanza (Km) in funzine del tipo di mezzo impiegato.

2.1.4 Costo di Attivazione

Definiamo il valore dei costi di attivazione f_{u} associati a ciascun impianto u strettamente positivo. Infatti se un impianto u avesse un costo di attivazione negativo o nullo allora sarebbe possibile risolvere un problema semplificato nel quale l’impianto u appartiene sempre all’insieme degli impianti attivati.

2.2 Risoluzione del Problema

Dato il grafo G, precedentemente definito, vogliamo ottenere una rete a stella di profondità n, soluzione del problema di ottimizzazione.

Per il problema di Localizzazione degli Impianti, ricordiamo che l’obbiettivo del problema è quello di decidere quali impianti attivare nell’insieme U allo scopo di assegnare ciascun cliente ad un solo impianto attivato minimizzando, nel contempo, la somma dei costi di attivazione e dello svantaggio complessivo dei clienti.

Possiamo affermare che in questo caso abbiamo due tipi di eventi logici elementari:

1. l’impianto u ∈ U è aperto o chiuso;

2. il cliente v ∈ V è assegnato o no all’impianto u ∈ U.

il problema da risolvere si riduce ad un problema di Programmazione Lineare {0, 1}

2.2.1 Calcolo del costo minimo

Dato un grafo G(V, E) orientato, connesso e tale che ad ogni spigolo (u, v) sia associato un peso non negativo w(u, v). Fissata una sorgente s, l’algoritmo di Dijkstra calcola il cammino minimo partendo da s per raggiungere tutti gli altri vertici del grafo. Variando s possiamo ottenere il cammino minimo tra tutte le coppie di nodi del grafo.

Algoritmo di Dijkstra

Algoritmo di Dijkstra

1. Fissato s poni l(s, s) = 0

2. Q = V

3. fintanto che Q non è vuoto ripeti:

(a) sia u l’elemento di Q con d(s, u) minima (b) estrai u da Q

(c) ∀v adiacente a u ripeti:

se l(s, v) > l(s, u) + w(u, v) allora i. l(s, v) = l(s, u) + w(u, v) ii. p_{v} = u padre del nodo v

(d) fine ciclo

4. fine ciclo

Cosiderate le dimensioni del grafo è necessario limitare al massimo le operazioni da far eseguire al calcolatore per poter ridurre i tempi di calcolo, a tale scopo modifichiamo l’algoritmo di Dijkstra. Le modifiche che apporteremo ci consentiranno di ridurre il costo computazionale dell’algoritmo DUALOC, il più dispendioso del progetto. Non Calcoliamo quindi i cammini minimi tra tutte le coppie di nodi ma, fissato l’insieme delle sorgenti S_{i} = {s_{j}conj = 1 … h_{i}}, dove h_{i} il numero di centri di servizio da attivare per il livello i. Ora eseguendo l’algoritmo di Dijkstra distribuisco tutti i nodi del grafo tra le sorgenti fissate individuando cos gli insiemi dei vertici V_{j} con j = 1 … h_{i}. Elimino tutti i nodi apparteneti ad S_{i} e dall’insieme E delgli archi del grafo G tutti gli spigoli adiacenti a vertici appartenenti a V_{j} diversi e tutti gli archi adiacenti ad i nodi appartenenti all’insieme S_{i}. Ottengo in questo modo G_{j}V_{j}, E_{j}. Supponiamo a questo punto che tutti i nodi di ogni sottografo rappresentino all’interno del sottografo stesso i clienti associati alle sorgenti escluso ovviamente l’insieme di nodi S_{i}, che contiene i centri attivati del livello superiore, e inseriamoli nell’insieme S_{i+1}.

2.2.2 Calcolo del lower bound

Dati h_{i} sottografi G_{j}(V_{j}, E_{j}) e l’insieme U_{i} = S_{i} calcoliamo il lower bound per il livello i. Per ogni nodo v ∈ ⋃_{j=1...h_{i}} G_{j} calcoliamo z_{v}^{0} = min_{u∈U_{i}}{c_{uv}}. Otteniamo quindi un vettore z^{0} tale che per ogni nodo u corrisponde il costo minimo tra tutti i cammini minimi calcolati dai centri di servizio che lo ragguingono. Il lower bound coincide con il valore ottimo della funzione obiettivo ed è della forma

g(z) = ∑ ; v∈⋃_{j=1...h_{i}} V_{j} z_{v} + ∑_{u∈U_{i}} max{0, ∑ ; v∈⋃_{j=1...h_{i}} V_{j} max 0, z_{v} − c_{uv} − f_{u}}

questo significa che risolvere il problema è equivalente ad individuare il vettore z^{⋆} che massimizza la funzione g.

La teoria della dualità ci consente di definire, in modo estremamente semplice, lower bound per ogni problema di Programmazione Lineare {0, 1}. Infatti, ad ogni soluzione ammissibile del problema duale π corrisponde un valore d^{T} π che è certamente minore o uguale al valore ottimo del problema primale e, quindi, minore o uguale al valore della soluzione ottima intera. In particolare, il miglior lower bound associato ad una soluzione duale-ammissibile \overline{π} si ottiene in corrispondenza alla soluzione ottima π^{∗} del problema duale.

I valori di z determinano quindi il valore di g. Dal momento che z^{0} probabilmente potrebbe non determinare il valore ottimo per il lower bound, l’algoritmo modificherà z^{0} in passi successivi z^{1}, …, z^{n} fino a quando non saranno soddisfatte le condizioni che ci garantiscono l’ottimo per il problema.

Algoritmo di Ascesa Duale modificato (dualoc)

1. Inizializzazione: z̄_{v} = min_{u∈U}{c_{vu}} ∀ v ∈ V; i = 1 2. Iterazione i-esima:

V̄ = V Ripeti:

v̄ = arg min_{v∈V̄} {h(v)} V̄ = V̄ − {v̄} τ_{v̄u} = f_{u} − ∑_{v∈V −{v}} max{0, z̄_{v} − c_{vu}} bv̄ = min_{u∈U}{c_{v̄u} + τ_{v̄u} − z̄v̄}

b′ ; v̄ = min{bv̄, min_{u∈U, c_{v̄u}−z̄v̄>0}{c_{v̄u} − z̄v̄}

fino a che b′ ; v̄ > 0 oppure V̄ = ∅ Se b′ ; v̄ = 0 allora fermati altrimenti

z̄v̄ = z̄v̄ + b′ ; v̄

i = i + 1 vai all’iterazione i-esima

3. Fine iterazione i-esima

2.2.3 Individuazione dei possibili centri di servizio

Una volta determinato il vettore z^{n} che massimizza la funzione g, imponiamo al problema le seguenti ipotesi euristiche:

1. La soluzione è ottima per il problema duale.

2. La soluzione ottima del rilassamento lineare definito dalla formulazione forte ha componenti intere ed è quindi ottima per il problema di Localizzazione degli Impianti.

Se l’assunzione 1 è verificata allora ogni soluzione ammissibile (x^{⋆}, y^{⋆}) del rilassamento definito dalla formulazione forte è anche ottima per tale problema se e solo se soddisfa le seguenti condizioni di scarto complementare:

1. w̄_{uv}(x_{u}^{⋆} − y_{uv}^{⋆}) = 0

2. t̄_{u}(1 − x_{u}^{⋆}) = 0

3. y_{uv}^{⋆}(c_{uv} − z̄_{v} + w̄_{uv} = 0)

4. x_{u}^{⋆}(f_{u} − ∑_{v∈V} w̄_{uv} + t̄_{u})

con

w̄_{uv} = max{0, z̄_{v} − c_{uv}} v ∈ V t̄_{u} = max{w̄_{uv} − f_{u}} u ∈ V

poiché t̄_{u} ∀u ∈ U segue

1. w̄_{uv}(x_{u}^{⋆} − y_{uv}^{⋆}) = 0

2. y_{uv}^{⋆}(c_{uv} − z̄_{v} + w̄_{uv} = 0)

3. x_{u}^{⋆}(f_{u} − ∑_{v∈V} w̄_{uv} + t̄_{u})

Ora, se anche la condizione 2 è verificata, allora esiste una soluzione (x^{⋆}, y^{⋆}) del precedente sistema di equazioni che è ammissibile (e quindi ottima) per il problema di Localizzazione degli Impianti.

In particolare grazie all’equazione 3 abbiamo che

(x_{u}^{⋆} = 1) ⇒ f_{u} = ∑_{v∈V_{j}} w̄_{v}u

ovvero che un impianto u ∈ U_{i} è attivato in una soluzione ottima solo se f_{u} = ∑_{v∈V} w̄_{uv} Possiamo quinidi definire l’insieme Ū_{i} degli impianti candidati

Ū_{i} = {u ∈ V_{j} : f_{u} = ∑_{v∈V_{j}} w̄_{uv}}

ed affermare che x_{u}^{⋆} = 0 per ogni u ∈ U_{i} − Ū_{i}. Non possiamo invece concludere che x_{u}^{⋆} = 1 per ogni u ∈ Ū_{i}; infatti un indice u ∈ U con x_{u}^{⋆} = 0 è perfettamente compatibile con la condizione 3. Per costruire una soluzione dobbiamo quindi scegliere quali impianti dell’insieme Ū devono essere effettivamente attivati.

2.2.4 Assegnazione dei centri di servizio e dei clienti

Utilizziamo l’algoritmo greedy e l’algoritmo di scambio per attivare i centri di servizio ed associare ad ogni centro attivato i relativi clienti imponendo delle modifiche per ottimizzare la localizzazione su un problema a pi livelli.

L’Algoritmo Greedy ha due caratteristiche cruciali:

1. Una volta che un impianto viene inserito nell’insime degli impianti attivati non viene più rimosso.

2. L’impianto da aggiungere viene scelto, ad ogni passo, guardando esclusivamente al vantaggio immediato consistente in una diminuzione del valore della funzione obiettivo. A sua volta, tale vantaggio viene valutato esaminando soltanto |U − T_{i−1}| soluzioni ammissibili.

L’euristica greedy può essere facilmente modificata rimuovendo le assunzioni 1 e 2 sopra descritte; ovvero consentendo all’algoritmo di aggiungere, ma anche di rimuovere due diversi impianti ad ogni passo. In tal modo, si consente all’algoritmo di rivedere le decisioni prese ai passi precedenti e si ottiene la cosiddetta “euristica di scambio”.

Calcolati gli insiemi V_{j} e Ū_{i} dei clienti e dei centri di servizio candidati, definiamo T l’insieme dei centri di servizio attivati tale che T ⊆ Ū_{1} ∪ … ∪ Ū_{n}. Definiamo la funzione l(v, T) che associa a ciascun cliente v ∈ V un centro attivato l(v, T) ∈ T. Associo il centro di servizio l(v, T) ∈ T al nodo ṽ tale che d(ṽ, l(ṽ, T)) < r e (l(ṽ, T) = arg min_{l(ṽ,T)} c(l(ṽ, T) + c(l(ṽ, T), l(l(ṽ, T))) tenendo, quindi, conto anche del costo tra il centro di servizio del livello superiore e quello in esame garantendo l’ottimo per la soluzione non per un unico livello, ma per tutta la profondit della rete a stella.

La funzione obiettivo sar quindi della seguente forma

Z(T) = ∑_{v∈V} c_{vl(v,T)} + ∑_{u∈T} f_{u}

Algoritmo Greedy Modificato + Algoritmo di Scambio

1. Inizializzazione: i = 1; T_{0} = ∅; Z(T_{0}) = ∞.

2. Iterazione i-esima

u_{i} = arg min_{u∈Ū−T_{i−1}} Z(T_{i−1} ∪ {u});

Se Z(T_{i−1} ∪ {u_{i}}) ≥ Z(T_{i−1}) allora fermati: T_{i−1} è la soluzione greedy altrimenti poni T_{i} = T_{i−1} ∪ {u_{i}} se T_{i} = U allora fermati: T_{i} è la soluzione greedy altrimenti poni i := i + 1 e vai all’iterazione i

3. Fine dell’iterazione i-esima

2.2.5 Aggiornamento della soluzione

Calcolati i centri di servizio e associati ad ognuno di essi i rispettivi clienti è necessario aggiornare la soluzione del problema. Sia S = {⋃_{i=1...n} S_{i}}. Al passo i-esimo eliminiamo da S tutti i centri attivati che non sono serviti dai centri di servizio del livello i − 1. I clienti che erano associati ai centri eliminati, o non sono più serviti da alcun fornitore oppure sono serviti da un centro di servizio del livello i−1, oppure i clienti sono serviti da un centro di servizio del livello i-esimo e del livello i − 1. Se è verificata la prima condizione allora ridistribuisco i clienti sconnessi tra i centri attivi del livello i-esimo. Se è verificata la seconda condizione non opero alcuna operazione sul cliente. Se è verificata la terza condizione associo il cliente al centro di livello i o al centro di livello i − 1 in funzione del minimo costo.

Algoritmo risolutivo

Dato un grafo G(V, E) orientato e connesso, fissiamo il numero n dei livelli (nel nostro caso hub, nazionale, provinciale). Sia h_{i} con i = {1, …, n}, h_{1} = 2 fissato, il numero dei centri di servizio che si vogliono attivare per ogni livello. L’algorito opera sul grafo G modificandolo in passi successivi ,eliminando nodi ed archi, ottenendo cos un grafo sconnesso rappresentato dall’unione dei sottografi G_{j} connessi con j = 1 … h_{i}. Allora

S = ∅ S_{1} = {Hub1, Hub2} Dijkstra modificato(G,S) per j = 1 … h_{j}

Dijkstra modificato(G,S)

Dualoc

Greedy modificato

elimina dal G i centri di servizio attivati e gli archi ad essi adiacenti Update Solution()

END

Per i = 3 abbiamo la formulazione che ci risolve il problema di Localizzazione delle Poste Italiane.

Figura 2.1: Schema generale del programma Java 23

Appendice A Alcune schermate del programma

Di seguito riportiamo alcune delle schermate del programma Java che implementa gli algoritmi descritti nelle pagine precedenti.