Candidati

Alessandro SEPIACCI

Mattia ZENNARO

Anno accademico 2011/2012

FACOLTÀ DÌ INGEGNERIA, INFORMATICA E STATISTICA

Corso di laurea in Ingegneria Gestionale

Tesina di Ottimizzazione Combinatoria I Localizzazione delle colonnine elettriche a Roma

1 / 24

Un Problema di Localizzazione degli Impianti consiste nel trovare l’allocazione ottima di una serie di strutture in modo tale da soddisfare tutti i

clienti, in funzione dei vantaggi o degli svantaggi relativi alla loro utilizzazione.

J = insieme dei potenziali Impianti da attivare

I = insieme dei clienti da

servire

cij = costi di afferenza del cliente i all’impianto j

fj = costi di attivazione

dell’impianto j.

- Insieme J* degli impianti da attivare - Assegnazione di ciascun cliente ad uno degli impianti attivati.

Minimizzando il COSTO COMPLESSIVO

2 / 24

Sistemazione delle Colonnine Elettriche a Roma.

- 4 allacciamenti a tensione variabile CC per Bike o Scooter + 1 presa 230V AC per Auto - Si possono caricare contemporaneamente: 4 scooter o 4 bike e un'auto

3 / 24

Dai dati offerti dal Comune di Roma, abbiamo identificato ogni quartiere come un cliente per il nostro problema, in modo da coprire l’intera popolazione. Adottando tale criterio, abbiamo ottenuto 87 Clienti ( |I| = 87) .

Cliente Municipio Cliente Municipio Cliente Municipio Cliente Municipio

campitelli 1 nomentano 3 parco dè medici 12 primavalle 18\19

campo marzio 1 tiburtino 3 europa 12 trieste 2\4

castro pretorio 1 casal boccone 4 fonte ostiense 12 colli dell'aniene 5\6\7

celio 1 castel giubileo 4 giuliano dalmata 12 tor sapienza 5\7

colonna 1 conca d'oro 4 torrino 12 tuscolano 6\7\9\10

esquilino 1 marcigliana 4 portonaccio 5 pigneto 6\9

ludovisi 1 piazza sempione 4 corviale 13 torre spaccata 7\8

monti 1 val melaina 4 casetta mattei 13 don bosco 7\8\10

parione 1 vigne nuove 4 borgo 17 re di roma 9

pigna 1 pietralata 5 prati 17 torre maura 8\10

ponte 1 ponte mammolo 5 tomba di nerone 20 acqua vergnie 8\5

regola 1 san basilio 5 tor di quinto 20 appio latino 9\11

ripa 1 torraccia 5 appio pignatelli 10\11 ottavia 19

s. angelo 1 alessandrino 7 cecchignola 11\12 monte spaccato 18

s. eustachio 1 la rustica 7 ostiense 11\12 garbatella 11

sallustiano 1 prenestino 7 gianicolense 15\16 marconi 15

trastevere 1 tor tre teste 7 la pisana 15\16 fleming 20

trevi 1 appio claudio 10 portuense 15\16 cortina d'ampezzo 20

flaminio 2 centocelle 10 trionfale 17\18\19 libia 2

parioli 2 ardeatino 11 della vittoria 17\19\20 san lorenzo 3

pinciano 2 torricola 11 aurelio 18\19 piazza bologna 3

salario 2 magliana 12 casalotti 18\19

4 / 24

Anche per gli impianti, abbiamo cercato di ricoprire l’intera città. Definita la zona, laddove fosse presente, abbiamo allocato l’impianto in prossimità della fermata Metro, altrove abbiamo optato per punti strategici (parchi, piazze, Centri Commerciali, parcheggi, zona turistica, università, ). Adottando tale criterio, abbiamo ottenuto 74 Impianti ( |J| = 74) .

Impianto Municipio Impianto Municipio Impianto Municipio Impianto Municipio

giardinetti 8 valle aurelia 18 santa maria dle soccorso 5 garbatella 11

torre maura 8 battistini 19 ponte mammolo 5 roma 70 11

torre spaccata 1 8 vittorio emanuele 19 rebibbia 5 san lorenzo 3

torre spaccata 2 8 manzoni 3 parco de medici 15 cecchignola 12

centocelle 7 re di roma 9 porta di roma 4 piazza cola di rienzo 17

pigneto 6 ponte lungo 9 roma est 8 policlinico gemelli 19

san giovanni 6 colli albani 9 roma eur 12 ospedale san camillo 15

amba aradam 6 tuscolano 10 viale di tor di quinto 20 trastevere 1

colosseo 1 cinecittà 10 stadio olimpico 17 piazza mancini 2

cavour 1 anagnina 10 stadio flaminio 2 piazza vescovio 2

piazza venezia 1 castro pretorio 3 palalottomatica 12 piazza istria 2

san pietro 17 policlinico 3 viale europa 12 piazzal delle provincie 3

piazza clodio 1 piazza bologna 3 san basilio 5 aldo moro 3

termini 2 annibaliano 4 casal boccone 4 via appia nuova 10

repubblica 1 libia 4 fidene 4 villa ada 2

barberini 1 conca d'oro 4 ottavia 19 villa borghese 2

spagna 1 jonio 4 torrevecchia 18 parco degli scipioni 1

flaminia 20 tiburtina 5 monte spaccato 18

Ottaviano 19 monti tiburtini 5 viale egeo 12

5 / 24

𝑐𝑖𝑗 = 𝑑𝑖𝑗 ∗ 𝑘𝑗 ∗ 𝑚

Cij : costo di afferenza del cliente i all’impianto j. m = 250 : fattore di scala.

𝑑𝑖𝑗 = (𝑥𝑖 − 𝑥𝑗 )2 + (𝑦𝑖 − 𝑦𝑗 )2

dij : distanza (in linea d’aria) tra il cliente i e l’impianto j.

( xi ; yi ) = coordinate del cliente i. ( xj ; yj ) = coordinate dell’impianto j.

6 / 24

Per l’assegnazione delle coordinate a Impianti e Clienti, abbiamo definito un sistema di riferimento che ricoprisse interamente Roma.

7 / 24

kj : fattore caratterizzante l’impianto j, con 0 < kj < 1 . È calcolato come la media aritmetica di 6 componenti, che definiscono la presenza o meno di punti strategici:

• Centro Commerciale • Piazza • Fermata Metro • Stazione / Capolinea bus • Zona turistica • Università

I valori assegnati a ciascuna componente sono :

• 0.25 : incidenza elevata • 0.7 : incidenza media • 1 : incidenza nulla

Impianto CC Piazza Metro Stazione ZT Università K

Termini 1 0.7 0.25 0.25 0.25 1 0.575

8 / 24

𝑓𝑗 = 𝑑𝑗′ ∗ 𝑘𝑗 ∗ 𝑐𝑓

fj : costo di attivazione dell’impianto j.

cf : costo fisso unitario.

È calcolato come prodotto di due contributi, dove dj :fattore densità, considerato come caratterizzante dell’impianto in termini di dimensione/capacità del servizio. kj: fattore precedentemente descritto

Impianto Densità municipio dj’

Termini 90.8 1.908

𝑑𝑗′ = 1 +

𝑑𝑒𝑛𝑠𝑖𝑡à(𝑑𝑒𝑙 𝑚𝑢𝑛𝑖𝑐𝑖𝑝𝑖𝑜)

100

9 / 24

z(x,y) = funzione obiettivo xi = variabile di attivazione (vettore a componenti 0-1)

yij = variabili di allaccio (vettore a componenti 0-1) (1) = vincolo di servizio

(2) = vincolo di attivazione

min 𝑧 = 𝑐𝑖𝑗 𝑦𝑖𝑗

𝑗 ∈𝐽

+ 𝑓𝑗𝑥𝑗𝑗 ∈𝐽𝑖∈𝐼

𝑦𝑖𝑗

𝑗 ∈𝐽

= 1 𝑖𝜖𝐼

𝑥𝑗 − 𝑦𝑖𝑗 ≥ 0 𝑖𝜖𝐼 , 𝑗𝜖𝐽

𝑥𝑗 𝜖 0,1 , 𝑦𝑖𝑗 𝜖 0,1 𝑖𝜖𝐼 , 𝑗𝜖𝐽

(1)

(2)

10 / 24

Z

Z*

Z’

Gap

Trovare una soluzione del problema con l’algoritmo Greedy, migliorando il risultato con

l’euristica della Ricerca Locale.

Confrontare la soluzione ottenuta, con il Lower Bound per definire il “GAP”, ovvero il

certificato di qualità della soluzione trovata.

Trovare un buon “Lower Bound” del problema attraverso l’algoritmo Dualoc.

11 / 24

L’algoritmo Dualoc di ascesa duale è un algoritmo che consente di produrre un Lower Bound sul valore ottimo del problema rilassato, in modo molto efficiente e di qualità accettabile. In altre parole, lo scopo è di rinunciare in parte alla qualità che si otterrebbe risolvendo all'ottimo il problema, in cambio di una sostanziale riduzione dei tempi di calcolo. L'idea di fondo è di applicare il teorema della dualità debole: il valore della funzione obiettivo di una qualunque soluzione ammissibile per il problema duale è un Lower Bound per il valore della soluzione ottima del problema primale. Dunque, l'idea è di riuscire, in modo efficiente, a produrre una soluzione ammissibile per il problema duale di qualità "buona".

12 / 24

min 𝑧 = 𝑐𝑖𝑗 𝑦𝑖𝑗

𝑗 ∈𝐽

+ 𝑓𝑗𝑥𝑗𝑗 ∈𝐽𝑖∈𝐼

𝑦𝑖𝑗

𝑗 ∈𝐽

= 1 𝑖𝜖𝐼

𝑥𝑗 − 𝑦𝑖𝑗 ≥ 0 𝑖𝜖𝐼 , 𝑗𝜖𝐽

𝑥𝑗 𝜖 0,1 , 𝑦𝑖𝑗 𝜖 0,1 𝑖𝜖𝐼 , 𝑗𝜖𝐽

min 𝑧 = 𝑐𝑖𝑗 𝑦𝑖𝑗

𝑗 ∈𝐽

+ 𝑓𝑗𝑥𝑗𝑗 ∈𝐽𝑖∈𝐼

𝑦𝑖𝑗

𝑗 ∈𝐽

= 1 𝑖𝜖𝐼

𝑥𝑗 − 𝑦𝑖𝑗 ≥ 0 𝑖𝜖𝐼 , 𝑗𝜖𝐽

𝑥𝑗 ≥ 0 , 𝑦𝑖𝑗 ≥ 0 𝑖𝜖𝐼 , 𝑗𝜖𝐽 max 𝑔(𝑧) = 𝑧𝑖𝑖∈𝐼

𝑤𝑖𝑗

𝑖∈𝐼

≤ 𝑓𝑗 𝑗𝜖𝐽

𝑧𝑖 − 𝑤𝑖𝑗 ≥ 0 𝑖𝜖𝐼 , 𝑗𝜖𝐽

𝑤𝑖𝑗 ≥ 0 𝑖𝜖𝐼 , 𝑗𝜖𝐽

Primale

Duale (del rilassamento)

Rilassamento del Primale

13 / 24

Funzionamento: Partendo dalla soluzione data dalla seguente relazione,

l'algoritmo fissa un ordinamento delle variabili duali zi , dopo di che, seguendo questo ordinamento, si procede ad aumentare ciascuna variabile (senza toccare le altre) della massima quantità che consente di mantenere l'ammissibilità duale della soluzione. Alla fine, avremo una soluzione duale, e dunque un Lower Bound, di qualità senz'altro superiore a quella di partenza. Tale massima quantità può essere facilmente calcolata in forma chiusa come segue:

𝑧𝑖 = 𝑚𝑖𝑛𝑗∈𝐽 𝑐𝑖𝑗 𝑖 ∈ 𝐼

𝑧𝑠𝑚𝑎𝑥 = 𝑚𝑖𝑛𝑗𝜖𝐽 {𝑐𝑠𝑗 + 𝑓𝑗 − 𝑤𝑖𝑗

𝑖≠𝑠

𝑧𝑖 = 𝑚𝑖𝑛𝑗∈𝐽 𝑐𝑖𝑗 𝑖 ∈ 𝐼

𝑤𝑖𝑗 = 𝑚𝑎𝑥 0 , 𝑧𝑖 − 𝑐𝑖𝑗 𝑖 ∈ 𝐼 , 𝑗 ∈ 𝐽

14 / 24

L’algoritmo aggiorna di volta in volta il valore di zs , passando poi a cercare di aumentare (non è detto che zmax sia maggiore del valore già presente) la successiva variabile, in base all’ordinamento prescelto.

Ovviamente, nei passi successivi sarà utilizzato il valore aggiornato delle variabili.

𝑧 =

𝑧1

𝑧2

.

.

.𝑧|𝐼|

𝑧 =

𝑧1𝑚𝑎𝑥

𝑧2𝑚𝑎𝑥

.

.

.𝑧|𝐼|𝑚𝑎𝑥

15 / 24

Il valore del Lower Bound, si ricava sommando tutte le componenti del vettore z precedentemente trovato. Per il nostro problema :

z = (814,637,686,325,442,815,551,502,812,229,205,670,924,333,513,458, 440,318,975,493,856,928,928,594,802,1092,817,1172,1502,621,793,1002, 962,1244,1030,3256,2033,1353,3099,1060,531,1073,2319,2288,758,500, 832,1312,2327,1224,3587,3248,247,951,4197,520,1094,1023,1113,1384, 3361,1211,801,693,1409,1262,1679,751,1083,2858,1386,1084,616,475, 503,475,2868,1211,500,799,559,2121,1274,1346,727,195,542) g(z) = 98 603

16 / 24

Per individuare una soluzione accettabile e piuttosto buona, utilizziamo l’algoritmo euristico Greedy. Il Greedy cerca di ottenere una soluzione ottima da un punto di vista globale attraverso la scelta della soluzione più “golosa” ad ogni passo locale. Questa tecnica consente, dove applicabile (infatti non sempre si arriva ad una soluzione ottima), di trovare soluzioni ottimali per determinati problemi in un tempo polinomiale.

𝑇 è 𝑙𝑎

𝑠𝑜𝑙𝑢𝑧𝑖𝑜𝑛𝑒 𝐺𝑟𝑒𝑒𝑑𝑦

𝑇 = ∅ ; 𝑐 𝑇 = ∞

𝑄∗ = min 𝑐 𝑇 ∪ 𝑘 : 𝑘 ∉ 𝑇 , 𝑇 ∪ 𝑘 𝑠𝑜𝑙. 𝑝𝑎𝑟𝑧𝑖𝑎𝑙𝑒

𝑘∗ = arg min 𝑐 𝑇 ∪ 𝑘 : 𝑘 ∉ 𝑇 , 𝑇 ∪ 𝑘 𝑠𝑜𝑙. 𝑝𝑎𝑟𝑧𝑖𝑎𝑙𝑒

𝑇 ∈ 𝑆

𝑄 > 𝑐(𝑇)

si no 𝑇 = 𝑇 ∪ 𝑘∗

17 / 24

Cerchiamo ora di migliorare la soluzione Greedy attraverso l’algoritmo di Ricerca Locale. Tale algoritmo non fa altro che confrontare la soluzione del Greedy con altre soluzioni ammissibili, scelte secondo un preciso “intorno”. Il metodo che abbiamo adottato prevede un “intorno di scambio”, cioè le soluzioni che la Ricerca Locale andrà ad analizzare, sono ricavate a partire dalla soluzioni Greedy, sostituendo ad ognuno degli impianti trovati, tutti i restanti impianti “scartati”. Definito :

𝐹 ∈ 𝜃 𝐹𝑖 ⟺ 𝐹 = 𝐹𝑖 ∪ 𝑗 − 𝑘 : 𝑘 ∈ 𝐹𝑖 , 𝑗 ∉ 𝐹𝑖 , 𝐹 ∈ 𝑆

L’algoritmo di Ricerca Locale avrà la seguente struttura:

18 / 24

𝐹 è 𝑙𝑎

𝑛𝑢𝑜𝑣𝑎 𝑠𝑜𝑙𝑢𝑧𝑖𝑜𝑛𝑒

𝐹0 ∈ 𝑆 ; 𝑘 = 0

𝑄∗ = min 𝑐 𝐹 : 𝐹 ∈ 𝜃(𝐹𝑘)

𝐹𝑘+1 = arg min 𝑐 𝐹 : 𝐹 ∈ 𝜃(𝐹𝑘)

𝑄∗ > 𝑐(𝐹𝑘) si no

𝑘 = 𝑘 + 1

19 / 24

Per il nostro problema :

c(TGreedy) = 99 639

c(TRL) = 99 417

La Ricerca Locale ha migliorato la soluzione del Greedy, abbassando il costo di ben 222.

20 / 24

Termini Ponte Lungo Piazza Cola di Rienzo

Palalottomatica San Basilio Trastevere

Ponte Mammolo Tuscolano Viale Egeo

Porta di Roma Ospedale San Camillo Barberini

Torre Spaccata 2 Piazza Istria Valle Aurelia

San Pietro Monte Spaccato Colosseo

Parco dè Medici Torre Maura Viale Jonio

Viale di Tor di Quinto Roma Est Roma eur

Battistini Centocelle Tiburtina

Conca d’oro Flaminia Viale Libia

Cecchignola Via Appia Nuova Piazzale Aldo Moro

Garbatella Roma 70 Torre Spaccata 1

San Lorenzo Policlinico Gemelli Casal Boccone

Ottavia Fidene San Giovanni

Piazza Venezia Piazza Bologna Piazza di Spagna

21 / 24

Il “Simplesso Dinamico” è un metodo per la risoluzione di problemi di Programmazione Lineare.

simplessoDinamico.run

simplessoDinamico1.run simplessoDinamico2.run

.

.

. simplessoDinamico29.run

oracolo.run

simplessoDinamico.mod

simplesso1.dat simplesso2.dat

.

.

. simplesso29.dat

22 / 24

Avendo un problema di dimensione maggiore di 300variabili x 300vincoli , abbiamo

suddiviso la matrice dei costi in 29 sotto-matrici (3x74)

costituite da tutti gli impianti e da 3 clienti (il max consentito),

in modo tale da non precludere a nessun cliente la possibilità

di essere servito da un determinato impianto.

Cosi facendo, abbiamo ottenuto 29 soluzioni parziali che generano un risultato totale (

= 110245 ) decisamente maggiore (peggiore) di quello trovato in precedenza.

Tale conclusione era prevista, in quanto non si considera il problema nella sua

interezza.

Si osserva che la soluzione trovata dal “simplesso Dinamico” non è particolarmente

lontana da quella evidenziata dagli algoritmi Dualoc-Greedy-Local Search.

23 / 24

Cliente Impianto Cliente Impianto Cliente Impianto Cliente Impianto

campitelli Colosseo nomentano Policlinico parco dè medici Parco dè Med. primavalle Ottaviano

campo marzio Spagna tiburtino Policlinico europa Viale Egeo trieste Annibaliano

castro pretorio Termini casal boccone Casal boccone fonte ostiense Palalottom. colli dell'aniene Pte Mammolo

celio Colosseo castel giubileo Fidene giuliano dalmata Palalottom. tor sapienza Pte Mammolo

colonna Piazza Venezia conca d'oro Conca d’oro torrino Roma Eur tuscolano Pigneto

esquilino Aldo Moro marcigliana Porta di Roma portonaccio Tiburtina pigneto Pigneto

ludovisi Barberini piazza sempione Jonio Corviale San Camillo torre spaccata Torre spaccata 1

monti Barberini val melaina Jonio casetta mattei Parco dé Med. don bosco Tuscolano

parione San Pietro vigne nuove Porta di Roma borgo San Pietro re di roma San Giovanni

pigna Piazza Venezia pietralata Tiburtina prati Cola di Rienzo torre maura Torre Maura

ponte Termini ponte mammolo Pte Mammolo tomba di nerone Ottavia acqua vergnie Roma Est

regola Piazza Venezia san basilio San Basilio tor di quinto Viale Tor di Q. appio latino Amba Aradam

ripa Trastevere torraccia San Basilio appio pignatelli San Giovanni ottavia Ottavia

s. angelo San Pietro alessandrino Torre Maura cecchignola Cecchignola monte spaccato Monte Spaccato

s. eustachio Piazza Venezia la rustica Roma Est ostiense Garbatella garbatella Garbatella

sallustiano Termini prenestino San Lorenzo gianicolense San Camillo marconi Viale Egeo

trastevere Trastevere tor tre teste Centocelle la pisana San Camillo fleming Viale Tor di Q.

trevi Termini appio claudio Tuscolano portuense San Camillo cortina d'ampezzo Viale Tor di Q.

flaminio Piazzale Clodio centocelle Centocelle trionfale Gemelli libia Libia

parioli Flaminia ardeatino Roma 70 della vittoria Cola di Rienzo san lorenzo San Lorenzo

pinciano Flaminia torricola Via Appia Nuo. aurelio Valle Aurelia piazza bologna Piazza Bologna

salario Piazza Istria magliana Viale Egeo Casalotti Battistini

Impianti attivati dal Simplesso Dinamico e non dal Dualo-Greedy-Local Search.

24 / 24