Swappa : Uni / Ricerca Operativa - PLI - Rover

Torna alla pagina di Ricerca Operativa

 :: Ricerca Operativa - PLI - Rover - 12.02.09 ::

Testo del problema

Ad un rover esploratore su Marte sono stati segnalati alcuni siti di interesse scientifico. Il rover conosce la propria posizione, la posizione dei siti ed il valore atteso della loro esplorazione. Esso conosce inoltre quanto tempo e quanta energia richiede l’esplorazione dei siti e lo spostamento da un sito all’altro. Il rover ha risorse limitate a disposizione: tempo ed energia. La scarsità di risorse potrebbe precludere l’osservazione di tutti i siti, nel qual caso sarebbe necessario massimizzare l’utilità complessiva (valore atteso) delle esplorazioni compiute. Se invece fosse possibile visitare tutti i siti, allora l’obiettivo sarebbe quello di minimizzare il consumo complessivo di energia.
Formulare il problema, classificarlo e risolverlo con i dati del file ROVER.TXT. Discutere l’ottimalità della soluzione trovata.

Dati

Sono stati segnalati 6 siti interessanti.
Il rover è inizialmente nella posizione indicata come sito n.7.

Tabella 1: Tempi di spostamento tra i siti (minuti)
     1   2   3   4   5   6  7
 1   0  13  14  16  13  13 13 
 2  13   0  15  14  16  14 11
 3  14  15   0  15  18  13 17
 4  16  14  15   0  17  16 18
 5  13  16  18  17   0  18 15
 6  13  14  13  16  18   0 15
 7  13  11  17  18  15  15  0

Tabella 2: Tempi di esplorazione dei siti (minuti)
Sito    Tempo (min)
  1      35
  2      20
  3      40
  4      60
  5      25
  6      10

Tabella 3: Consumo per l’esplorazione dei siti (Joule)
Sito    Consumo (J)
  1      60
  2      45
  3      70
  4     110
  5      50
  6      25

Tabella 4: Valore atteso di ogni esplorazione
Sito    Valore
  1      90
  2      50
  3      20
  4     100
  5     120
  6      50

Consumo per gli spostamenti: 8 Joule/min, indipendentemente dalla posizione.
Energia disponibile: 1000 Joule
Tempo disponibile: 400 minuti

Formulazione del problema

Dati

siti = 7 (numero siti, di cui uno di partenza e sei da visitare)
temSp_ij (tempo di spostamento dal sito di partenza i al sito di arrivo j) [minuti]
temEsp_i (tempo di esplorazione del sito i) [minuti]
consEsp_i (consumo di energia per l'esplorazione del sito i) [joule]
valAtt_i (valore atteso dell'esplorazione del sito i)
consSp = 8 (consumo per lo spostamento) [joule/minuto]
enDisp = 1000 (energia disponibile) [joule]
temDisp = 400 (tempo disponibile) [minuti]

Variabili

x_i (indica se il rover ha esplorato il sito i) (binaria)
y_ij (indica se il rover si è spostato dal sito di partenza i al sito di arrivo j) (binaria)

Funzione obiettivo

max (somma)_i valAtt_i * x_i

Vincoli

vincolo che impone che il tempo totale impiegato sia inferiore a quello disponibile:
(somma)_i x_i * temEsp_i + y_ij * temSp_ij <= temDisp (per ogni i e per ogni j)
vincolo che impone che la quantità di energia consumata sia inferiore a quella disponibile:
(somma)_i x_i * consEsp_i + y_ij * temSp_ij * consSpo <= enDisp (per ogni i e per ogni j)
vincolo che impone che un sito non venga marcato come visitato se non ha nessun arco entrante (quindi se non ci è ancora andato nessuno):
x_j <= (somma)_i y_ij) (per ogni j)
vincolo che impone che nessun sito sia visitato più di una volta:
x_i <= 1 (per ogni i)
vincolo che impone che solo il sito di partenza possa avere un'uscita e nessuna entrata, mentre tutti gli altri devono avere un numero di uscite minore delle entrate:
(somma)_j y_ij <= (somma)_j y'_ji' (per ogni i <= 6)
Il "<= 6" è fondamentale, perché fa in modo che non venga contato anche il nodo di partenza
vincolo che impone che dal sito di partenza (che non è conteggiato nel vincolo precedente) non si possa andare in più di un sito:
(somma)_i y_7i <= 1
vincolo che impone che non ci siano autoanelli, ovvero archi che entrano ed escono dallo stesso nodo:
(somma)_i y_ii = 0

Linghizzazione del problema

! esercizio - Rover;

model:

sets:
sito /1..7/: consEsp, temEsp, valAtt, x;
tratta (sito,sito): temSp, y;
endsets

data:
temSp = 	0  13  14  16  13  13  13
 		13   0  15  14  16  14  11
 		14  15   0  15  18  13  17
 		16  14  15   0  17  16  18
 		13  16  18  17   0  18  15
 		13  14  13  16  18   0  15
 		13  11  17  18  15  15   0;
consSp = 8;
temEsp = 35 20 40 60 25 10 0;
consEsp = 60 45 70 110 50 25 0;
valAtt = 90 50 20 100 120 50 0;
enDisp = 1000;
temDisp   =  400;
enddata

! funzione obiettivo;
max = @sum(sito(i): valAtt(i) * x(i));

! vincolo sul tempo disponibile;
@sum(sito(i): x(i) * temEsp(i)) + 
              @for(sito(i): @sum(sito(j): y(i,j) * temSp(i,j))) <= temDisp;

! vincolo sull'energia disponibile;
@sum(sito(i): x(i) * consEsp(i)) + 
              @for(sito(i): @sum(sito(j): y(i,j) * consSp * temSp(i,j))) <= enDisp;

! vincoli che impongono che ogni sito sia visitato al massimo una volta;
@for(sito(j): 
       x(j) <= @sum(sito(i): y(i,j))
);
@for(sito(i): x(i) <= 1);

! vincolo per bilanciare le entrate e le uscite dei siti (dal sito 1 al 6);
@for(sito(i) | i #LE# 6:
     @sum(sito(j): y(i,j)) <= @sum(sito(j): y(j,i))
);

! vincolo per imporre che dal sito di partenza non si vada in più di un sito;
@sum(sito(j): y(7,j)) <= 1;

! vincolo per impedire gli autoanelli;
@for(sito(i): y(i,i) = 0);

! definisco le variabili binarie x e y;
@for(sito(i): @for(sito(j): @bin(y(i,j))));
@for(sito(i): @bin(x(i)));

end

Torna alla pagina di Ricerca Operativa