Post on 26-Jul-2015
Tesina diRicerca Operativa
E.Benetti,F.Brunelli,E.Nazzaro
Localizzazione dei centri di emergenza Sia data una regione geografica, e un insieme di
potenziali siti in cui installare dei presidi medici di emergenza. Si vuole garantire che ogni punto del territorio sia entro una distanza (in linea d’aria) prefissata D dal centro più vicino. Si risolva il problema di determinare il numero minimo di siti e quali, e si consideri la variante in cui un punto può essere entro distanza D’>D se a distanza D c’e’ una farmacia 24h.
Discretizzazione utenti Il primo passo nello sviluppo del
progetto è quello di discretizzare il numero di utenti della provincia di Ferrara in modo tale da fornire, in maniera più agevole, al programma Mosel i dati necessari per l’ elaborazione.
Questo è stato fatto sovrapponendo alla cartina di Ferrara una griglia che suddivide il territtorio in quadrati di 4,5 Km di lato; i vertici di tali quadrati rappresentano i punti utenza, ed il loro lato diventa l’ unità di misura usata dal programma Xpress.
Gestione della distanza per la copertura totale del territtorio (1/2)
Questa discretizzazione pone un problema nella copertura del territtorio: come infatti si nota nella figura, nel caso in cui uno o più punti utenza dello stesso quadrato si trovino sul bordo dell’area di copertura del sito di emergenza, o in punti limitrofi ad esso, possono non essere incluse tutte le zone della provincia.
D
Gestione della distanza per la copertura totale del territtorio (2/2)
Per risolvere questa problematica, abbiamo deciso di imporre che i punti utenza siano entro una distanza D-√2/2 dal sito di emergenza.
(dove √2/2 è la metà della diagonale di un quadrato della griglia e D è la distanza in km inserita dall’utente,divisa per 4,5 al fine di renderla compatibile con la nostra discretizzazione. Analogamente è trattata la Delta delle farmacie).
D
Piattaforma grafica
Latitudine e longitudine del punto Distanza D Distanza delta
Siti Disponibili
Passaggio dati tra piattaforma grafica ed Xpress (1/3)Nell’ interfaccia in Java si è scelto di gestire i click del mouse con un
ascoltatore di eventi che, oltre ad aggiungere in un vettore le coordinate dei punti cliccati col tasto sinistro e visualizzare longitudine e latitudine con un click del tasto destro, permette di gestire anche diversi pulsanti:
Scrivi: Raccoglie le coordinate dei siti possibili e le salva in un file di nome “outputInterface.txt” in un formato comprensibile al programma Xpress
Disegna: Disegna i punti contenuti nel file “inputInterface.txt”
Reset: Resetta l’ intera interfaccia
Reset Siti: Resetta solo i siti evidenziati
Passaggio dati tra piattaforma grafica ed Xpress (2/3)Esempio: SX: [ 3.580246913580247 4.148148148148148 2.9876543209876543
6.197530864197531 6.074074074074074 6.172839506172839 8.962962962962964 8.17283950617284 8.592592592592593 10.493827160493828 10.296296296296296 13.08641975308642 15.82716049382716 18.54320987654321 21.061728395061728 20.0 19.679012345679013 18.320987654320987 15.358024691358025 13.45679012345679 13.308641975308642 13.580246913580247 17.061728395061728 17.506172839506174 15.45679012345679 11.358024691358025 ] SY: [ 2.617283950617284 4.296296296296297 6.074074074074074 7.08641975308642 2.765432098765432 4.271604938271605 4.197530864197531 6.567901234567901 8.987654320987655 10.246913580246913 5.950617283950617 2.3950617283950617 1.876543209876543 2.246913580246914 3.753086419753086 6.271604938271605 9.728395061728396 11.530864197530864 11.308641975308642 9.753086419753087 12.864197530864198 6.419753086419753 5.407407407407407 8.592592592592593 8.17283950617284 3.925925925925926 ] D: 6N: 26DELTA: 2
Passaggio dati tra piattaforma grafica ed Xpress (3/3)Acquisizione dati in Mosel:
declarations N: integer !numero siti disponibili
end-declarations
initializations from 'outputInterface.txt'N
end-initializations
declarationsSITES = 1..N ! Siti possibiliUSERS = 1..211 ! UtentiSX,SY: array(SITES) of real ! Coordinate siti possibiliUX,UY: array(USERS) of real ! Coordinate utentiD: real ! Distanza da rispettareSA: array(SITES) of mpvarA: mpvar
end-declarations
initializations from 'outputInterface.txt'SX SY D
end-initializations
initializations from 'utenti.txt'UX UY
end-initializations
Dal file “outputInterface.txt” vengono presi in ingresso: - N: Numero dei siti disponibili- SX,SY: Coordinate dei siti- D: Distanza richiesta
Dal file “utenti.txt” invece:- UX,UY: Coordinate dei punti utenza discretizzati
Vincoli e funzione obiettivo del programma Xpress forall (i in SITES) SA(i) is_binary Questo vincolo impone che un sito sia attivato (valore 1) o non
attivato (valore 0).
forall (b in USERS) sum(a in SITES) (SA(a)*OK(a,b)) >= 1
Questo vincolo controlla, per ogni punto utenza, che esso sia coperto da almeno 1 sito. Questo si ottiene moltiplicando il vettore riga dei siti con ogni colonna della matrice di ammissibilità OK(a,b), che ha per colonne i punti utenza e per righe i siti.
OBIETTIVO: Minimizzando la somma dei valori nel vettore dei siti, minimizzeremo il numero dei siti.
A = sum(i in SITES) SA(i)minimize(A)
Creazione matrice ammissibilitàforall(a in SITES,b in USERS) do
DIST(a,b):= sqrt((SX(a)-UX(b))^2 + (SY(a)-UY(b))^2)if(DIST(a,b)<=(D-(sqrt(2)/2))) then
OK(a,b) := 1else OK(a,b) := 0end-if
end-do
Per ogni sito disponibile viene prima calcolata la distanza rispetto a ogni utente e memorizzata nella matrice DIST(a,b).
Se questa distanza è <= a quella richiesta dalle specifiche allora la posizione corrispondente nella matrice di ammissibilità OK(a,b) assumerà valore 1, altrimenti 0
Passaggio inverso tra Xpress e piattaforma grafica
fopen("inputInterface.txt",F_OUTPUT)forall(a in SITES | getsol(SA(a))>0) do
write(SX(a),",",SY(a),",") end-do
write("%") fclose(F_OUTPUT)
Esempio:
4.14815,4.2963,10.4938,10.2469,13.0864,2.39506,20,6.2716,18.321,11.5309,%
Output grafico (Emergenza)
Siti scelti da Xpress
Output grafico (Farmacie)
Aggiunta delle Farmacie! Distanze utenti e farmacie e matrice ammissibilita distanzaforall(a in FARMA,b in USERS) do
DISTF(a,b):= sqrt((FX(a)-UX(b))^2 + (FY(a)-UY(b))^2)if(DISTF(a,b)<=D) then
OKF(a,b) := 1else OKF(a,b) := 0end-if
end-do
! Distanze tra siti e utenti e matrice ammissibilità distanzaforall(a in SITES,b in USERS) do
DIST(a,b):= sqrt((SX(a)-UX(b))^2 + (SY(a)-UY(b))^2)if(sum(c in FARMA) OKF(c,b) >= 1) then
if(DIST(a,b)<=((D-(sqrt(2)/2))+DELTA)) then
OK(a,b) := 1else OK(a,b) := 0end-ifelse if(DIST(a,b)<=(D-(sqrt(2)/2))) then
OK(a,b) := 1else OK(a,b) := 0end-if
end-ifend-do
Nel file “utentifarma.txt” oltre ai punti utenza avremo, in questo caso, 4 farmacie:FX: [4 9 13 14] FY: [3 5 3 12]
Dal file “inputIterface.txt” prenderemo in ingresso anche la Delta definita dall’utente.
Analogamente al caso precedente, si calcoleranno le distanze tra farmacie e punti utenza e verranno memorizzati in DISTF(a,b). A seconda che rispettino o meno la distanza D richiesta verrà scritto 1 o 0 nella matrice OKF(a,b).
Nel controllo delle distanze tra siti e punti utenza nella matrice DIST(a,b) se nella colonna corrispondente a un utente nella matrice OKF vi è almeno un 1 (ovvero, è presente almeno una farmacia a distanza <=D), nella matrice di ammissibilità OK(a,b) metteremo un 1 se la distanza è <= D-(sqrt(2)/2))+DELTA, se non vi è una farmacia la distanza verrà calcolata come prima.
Commenti La scelta di far comunicare interfaccia e
programma Xpress tramite file è stata determinata dal fatto che le classi di integrazione per Java fornite da Mosel sono per i soli utenti aventi licenza completa, questo avrebbe limitato l’ utilizzo dell’ interfaccia Java.
L’ utilizzo del file consente invece di realizzare un’ architettura client/server, dove il client possiede l’interfaccia e il server il processo servitore in Xpress, grazie alla quale si può pensare ad un utilizzo distribuito di questa applicazione.