Swappa : Uni / Ricerca Operativa - PLI - Ambulanze

Torna alla pagina di Ricerca Operativa

 :: Ricerca Operativa - PLI - Ambulanze - 16.04.09 ::

Testo del problema

Un territorio che comprende un certo numero di centri abitati deve essere coperto da un dato numero di ambulanze per il pronto intervento. Le ambulanze possono sostare presso apposite rimesse dislocate nel territorio, in posizioni date. Da ciascuna di queste posizioni ogni ambulanza può coprire alcuni dei centri abitati, ma non tutti. Un centro abitato si intende coperto quando esiste almeno un’ambulanza in grado di raggiungerlo entro un dato tempo limite.
Conoscendo la popolazione residente in ciascuno dei centri abitati, localizzare le ambulanze in modo da massimizzare la copertura della popolazione.

Dati

I centri abitati sono 9, le postazioni disponibili sono 6, 
le ambulanze sono 3.

Tab. 1: Popolazione [n. abitanti]

Paese     Popolazione
  1           250
  2           450
  3          1000
  4           825
  5          1100
  6           940
  7           120
  8           280
  9           480

Tab. 2: Tempo di intervento [minuti]

Paese                Postazione
           1    2    3    4    5    6

1          1    3   12    6   12    4
2          2    2   11    2   13    8
3          5    3   12    0   19    7
4          7    5   14    1   21    9
5          5    0    8    3   11    3
6         14    8    0   12    6   12
7         17   12    3   16    2    9
8         12    8    8   12    2    4
9          7    3   12    7    7    0

Tab. 3: Disponibilità ambulanze

N. Ambulanze    Frazione di tempo
    0                 15%
    1                 20%
    2                 30%
    3                 35%

Tempo max di intervento = 8 minuti.

Formulazione del problema

Dati

centri = 9 (numero di centri abitati)
post = 6 (numero di postazioni disponibili)
ambul = 3 (numero ambulanze disponibili)
popol_i (popolazione del centro abitato i=1..9)
tInt_ij (tempo di intervento dalla postazione j=1..6 al centro abitato i=1..9) [minuti]
dispAmb_k (disponibilità ambulanza k=1..3 espressa come frazione di tempo) [%]
maxInt = 8 (tempo massimo di intervento) [minuti]

Variabili

x_i (variabile binaria che indica se il centro abitato i è coperto o no)
y_j (variabile binaria che indica se nella postazione j c'è un'ambulanza)

Funzione obiettivo

(somma)_i max x_i * popol_i

Vincoli

vincolo sulla disponibilità di ambulanze:
(somma)_j y_j = ambul
vincolo che impone che le città coperte siano solo quelle a cui le ambulanze possono arrivare entro il tempo limite:
x_i <= (somma)_j y_j "per cui tInt_ij <= maxInt"
Non sapendo come altro scriverlo ho messo la condizione tra virgolette. In altre parole verranno conteggiate nella somma solo quelle postazioni che distano meno di maxInt dal centro abitato. In questo modo se non ce n'è nemmeno una, allora x_i dovrà essere <= 0 (come è ovvio che sia), altrimenti potrà valere anche 1.

Linghizzazione del problema

! esercizio: ambulanze;

model:

sets:
centro /1..9/: popol,
               x;
postazione /1..6/: y;
intervento(centro,postazione): tInt;
endsets

data:
popol = 250 450 1000 825 1100 940 120 280 480;
tInt =   1    3   12    6   12    4
       	 2    2   11    2   13    8
       	 5    3   12    0   19    7
       	 7    5   14    1   21    9
       	 5    0    8    3   11    3
      	14    8    0   12    6   12
      	17   12    3   16    2    9
      	12    8    8   12    2    4
         7    3   12    7    7    0;
ambul = 3;
maxInt = 8;
enddata

! funzione obiettivo;
max = @sum(centro(i): x(i) * popol(i));

! vincolo sulla disponibilità di ambulanze;
@sum(postazione(j): y(j)) = ambul;

! vincolo sulla copertura dei centri;
@for(centro(i): 
	x(i) <= @sum(postazione(j) | tInt(i,j) #LE# maxInt: y(j))
);

! definisco le variabili binarie;
@for(centro(i): @bin(x(i)));
@for(postazione(j): @bin(y(j)));

end

Torna alla pagina di Ricerca Operativa