Capitolo 6
Lo sviluppo dell’algoritmo in
AMPL
Si `e scelto di tradurre il modello in un’algoritmo scritto in AMPL[9], un linguaggio per l’ottimizzazione e la programmazione matematica, con il risolutore non lineare MINOS. L’algoritmo segue fase per fase il modello: l’unica differenza, solo nominale, `e la presenza della FaseV che in realt`a coincide con i passi 4, 5 e 6 della FaseIV del modello: in tali passi infatti si ripetono le stesse ottimizzazioni eseguite nei tre passi precedenti, ma ora senza prendere in considerazione la linea il cui coordinamento risulta essere il p`u gravoso in termini di costo totale. Il programma `e composto da tre file:
1. il file cord.mod,
2. il file cord.dat,
3. il file cord.run.
6.1
Il file della descrizione del modello
Il file cord.mod contiene la descrizione del modello, ovvero la definizione degli insie-mi, delle variabili e dei parametri, ma anche la funzione obiettivo, in questo caso il costo totale da minimizzare, e i vincoli cui ´e soggetto il problema.
set NODI ordered; set TRATTE ordered;
set PRINCIPALI within TRATTE ordered;
set SECONDARIE := TRATTE diff PRINCIPALI ordered; set SEC { NODI } within TRATTE ordered;
set DI := { 1, 2 } ; set DELTA := { 1, 2 } ; param uw >0;
param uv >0;
param costo { TRATTE } >= 0, default 0; param rtt { NODI, TRATTE } >= 0, default 0; param rtp >= 0, default 0;
param attr sec pri { NODI, SECONDARIE, DI } >0, default 0.1; param attr pri sec { NODI, DI, SECONDARIE } >= 0, default 0;
param attr sec sec { NODI, SECONDARIE, SECONDARIE } >0, default 0.1; param saliti { NODI, DI } >= 0, default 0;
param trasb1 { i in NODI, j in SEC[i] } := sum { d in DI } attr sec pri [i, j, d] + sum { k in SEC[i] } attr sec sec [i, j, k];
param trasb2 { i in NODI, j in SEC[i] } := sum { d in DI } attr pri sec [i, d, j] + sum { k in SEC[i] } attr sec sec [i, k, j];
param Iij { i in NODI, j in SEC[i], z in DELTA } := if z = = 1 then trasb1[i,j]
else if z = = 2 then trasb2[i,j];
param saliti pri { i in NODI, d in DI } := saliti [i, d] + sum { j in SEC[i] } attr sec pri [i, j, d];
param discesi pri { i in NODI, d in DI } := discesi [i, d] + sum { j in SEC[i] } attr pri sec [i, d, j];
param n := card { NODI } ;
param Aid { i in NODI, d in DI } := sum { m in 1..i } (saliti pri [m,d] - discesi pri [m,d]);
param vHij { i in NODI, j in SEC[i] } >= 0; param vHp { d in DI } >= 0;
var Hp { d in DI } >= 0;
var Hij { i in NODI, j in SEC[i] } >= 0; var Hpi { i in NODI, d in DI } >= 0; param OB2 >= 0;
param OB3 >= 0; param OB4 >= 0; param OB5 >= 0;
param OBOPT >= 0; param la := 0.49792;
param cord { i in NODI, j in SEC[i] } >= 0, default 0, binary; param optcord { i in NODI, j in SEC[i] } >= 0, default 0, binary; param yid { i in NODI, d in DI } >= 0, default 0, binary;
param optyid { i in NODI, d in DI } >= 0, default 0, binary; param pid { i in NODI, d in DI } >= 0, default 0, binary; param optpid { i in NODI, d in DI } >= 0, default 0, binary; param p5id { i in NODI, d in DI } >= 0, default 0, binary; param optp5id { i in NODI, d in DI } >= 0, default 0, binary; param cont { i in NODI, d in DI } >= 0, default 0, binary; param optHpi { i in NODI, d in DI } >= 0;
param optHp { d in DI } >= 0;
param optHij { i in NODI, j in SEC[i] } >= 0; param optKij { i in NODI, j in SEC[i] } >= 0; param optKid { i in NODI, d in DI } >= 0;
var Kij { i in NODI, j in SEC[i] } >= 0.08, default 0.08; var Kid { i in NODI, d in DI } >= 0.08, default 0.08; var KS { i in NODI, j in SEC[i] } = 1/la + Kij[i,j]; var KP { i in NODI, d in DI } = 1/la + Kid[i,d];
var Co = sum { d in DI } ( rtp * costo [1000] / Hp[d]) + sum { i in NODI, j in SEC[i] } ((rtt[i,j] + Kij[i,j]) * costo[j] / Hij[i,j]);
var Cw = 0.5 * uw * (sum { i in NODI, j in SEC[i] } (Hij[i,j] * trasb2[i,j]) + sum
{ i in NODI, d in DI } (Hp[d] * saliti pri[i,d]));
var Tnikj { i in NODI, k in SEC[i], j in SEC[i] } = 0.5 * Hij[i,j] + 0.5 * vHij[i,j] / Hij[i,j];
var Tnijd { i in NODI, j in SEC[i], d in DI } = 0.5 * Hp[d] + 0.5 * vHp[d] / Hp[d]; var Tnidj { i in NODI, d in DI, j in SEC[i] } = 0.5 * Hij[i,j] + 0.5 * vHij[i,j] / Hij[i,j];
var Dikj1 { i in NODI, k in SEC[i], j in SEC[i] } = exp( - 1 - la * Hij[i,j]) * ( - (Hij[i,j])ˆ2 - 3 * Hij[i,j] * Hij[i,k] + (Hij[i,k])ˆ2 + Hij[i,j] * KS[i,j] + 2 * Hij[i,k] * KS[i,j] + 3 * Hij[i,j] * KS[i,k] - 2 * Hij[i,k] * KS[i,k] - 2 * KS[i,j] * KS[i,k] + (KS[i,k])ˆ2 - 4/(la)ˆ( - 2) - 7 * Hij[i,j]/(2 * la) - 3 * Hij[i,k]/la + 2 * KS[i,j]/la + 3 * KS[i,k]/la - la * Hij[i,k] * (Hij[i,j])ˆ2 + 0.5 * la * Hij[i,j] * (Hij[i,k])ˆ2 + la * Hij[i,j] * Hij[i,k] * KS[i,j] + la * KS[i,k] * (Hij[i,j])ˆ2 - la * Hij[i,j] * Hij[i,k] * KS[i,k] - la * Hij[i,j] * KS[i,j] * KS[i,k] + 0.5 * la * Hij[i,j] * (KS[i,k])ˆ2) + exp( - 1) * ( - 2 * Hij[i,j] * Hij[i,k] + (Hij[i,k])ˆ2 + 2 * Hij[i,k] * KS[i,j] + 2 * Hij[i,j] * KS[i,k] - 2 * Hij[i,k] * KS[i,k] - 2 * KS[i,j] * KS[i,k] + (KS[i,k])ˆ2 - 4/(la)ˆ2 - 2 * Hij[i,j]/la - 3 * Hij[i,k]/la + 2 * KS[i,j]/la + 3 * KS[i,k]/la) + Hij[i,j] * Hij[i,k] 0.5 * (Hij[i,k])ˆ2 Hij[i,k] * KS[i,j] -Hij[i,j] * KS[i,k] + Hij[i,k] * KS[i,k] + KS[i,j] * KS[i,k] - 0.5 * (KS[i,k])ˆ2 + laˆ( - 2) * (3/2 + 3 * exp( - la * KS[i,j]) - 4 * exp( - 1 - la * (Hij[i,k] + KS[i,j] - KS[i,k]))) + laˆ( - 1) * (Hij[i,j] + Hij[i,k] - Hij[i,k] * exp( - 1 - la * (Hij[i,k] + KS[i,j] - KS[i,k])) KS[i,j] + KS[i,j] * exp( la * KS[i,j]) KS[i,j] * exp( 1 la * (Hij[i,k] + KS[i,j] KS[i,k])) KS[i,k] + KS[i,k] * exp( 1 la * (Hij[i,k] + KS[i,j] KS[i,k]))) + laˆ( -1) * (exp( - 2 - la * (Hij[i,j] + Hij[i,k] + KS[i,j] + KS[i,k])) * (2 * exp(la * (Hij[i,k]
+ KS[i,k])) + exp(1 + la * (Hij[i,k] + KS[i,k])) - (1 + la * Hij[i,k]) * exp(1 + la * KS[i,k]) - (1 + la * KS[i,k]) * exp(1 + la * Hij[i,k])) * ((2 + la * (Hij[i,j] - KS[i,j])) * exp(1 + la * (Hij[i,j] + KS[i,j])) + (2 + la * KS[i,j]) * exp(1 + la * Hij[i,j]) + ( - 5 - 2 * la * (Hij[i,j] - KS[i,j])) * exp(la * (Hij[i,j] + KS[i,j])) + exp(1 + la * KS[i,j]) * ( - 2 + la * Kij[i,j] - (la * Hij[i,j])ˆ2 + la * Hij[i,j] * ( - 2 + la * KS[i,j])))) + 0.5 * laˆ( - 2) * exp( - 1 - la * (Hij[i,k] + KS[i,j])) * (2 * exp(la * (Hij[i,j] + KS[i,k])) * ( - 4 + la * (Hij[i,j] - Hij[i,k] - KS[i,j] + KS[i,k])) + exp(1 + la * (Hij[i,k] + KS[i,j])) * (3 - 2 * la * KS[i,j] + 2 * la * KS[i,k] + (la * Hij[i,j])ˆ2 + (la * Hij[i,k])ˆ2 + (la * KS[i,j])ˆ2 - 2 * KS[i,j] * KS[i,k] * (la)ˆ2 + (la * KS[i,k])ˆ2 + 2 * la * Hij[i,k] * ( - 1 + la * (KS[i,j] - KS[i,k])) - 2 * la * Hij[i,j] * ( - 1 + la * (Hij[i,k] + KS[i,j] - KS[i,k]))));
var Dikj0 { i in NODI, k in SEC[i], j in SEC[i] } = exp( - 1 - la * Hij[i,j]) * ( - (Hij[i,j])ˆ2 - 3 * Hij[i,j] * Hij[i,k] + (Hij[i,k])ˆ2 + Hij[i,j] * KS[i,j] + 2 * Hij[i,k] * KS[i,j] + 3 * Hij[i,j] * KS[i,k] - 2 * Hij[i,k] * KS[i,k] - 2 * KS[i,j] * KS[i,k] + (KS[i,k])ˆ2 - 4/(la)ˆ( - 2) - 7 * Hij[i,j]/(2 * la) - 3 * Hij[i,k]/la + 2 * KS[i,j]/la + 3 * KS[i,k]/la - la * Hij[i,k] * (Hij[i,j])ˆ2 + 0.5 * la * Hij[i,j] * (Hij[i,k])ˆ2 + la * Hij[i,j] * Hij[i,k] * KS[i,j] + la * KS[i,k] * (Hij[i,j])ˆ2 - la * Hij[i,j] * Hij[i,k] * KS[i,k] - la * Hij[i,j] * KS[i,j] * KS[i,k] + 0.5 * la * Hij[i,j] * (KS[i,k])ˆ2) + exp( - 1) * ( - 2 * Hij[i,j] * Hij[i,k] + (Hij[i,k])ˆ2 + 2 * Hij[i,k] * KS[i,j] + 2 * Hij[i,j] * KS[i,k] - 2 * Hij[i,k] * KS[i,k] - 2 * KS[i,j] * KS[i,k] + (KS[i,k])ˆ2 - 4/(la)ˆ2 - 2 * Hij[i,j]/la - 3 * Hij[i,k]/la + 2 * KS[i,j]/la + 3 * KS[i,k]/la) + Hij[i,j] * Hij[i,k] 0.5 * (Hij[i,k])ˆ2 Hij[i,k] * KS[i,j] -Hij[i,j] * KS[i,k] + Hij[i,k] * KS[i,k] + KS[i,j] * KS[i,k] - 0.5 * (KS[i,k])ˆ2 + laˆ( - 2) * (3/2 + 3 * exp( - la * KS[i,j]) - 4 * exp( - 1 - la * (Hij[i,k] + KS[i,j] - KS[i,k]))) + laˆ( - 1) * (Hij[i,j] + Hij[i,k] - Hij[i,k] * exp( - 1 - la * (Hij[i,k] + KS[i,j] - KS[i,k]))
KS[i,j] + KS[i,j] * exp( la * KS[i,j]) KS[i,j] * exp( 1 la * (Hij[i,k] + KS[i,j] KS[i,k])) KS[i,k] + KS[i,k] * exp( 1 la * (Hij[i,k] + KS[i,j] KS[i,k]))) + laˆ( -1) * (exp( - 2 - la * (Hij[i,j] + Hij[i,k] + KS[i,j] + KS[i,k])) * (2 * exp(la * (Hij[i,k] + KS[i,k])) + exp(1 + la * (Hij[i,k] + KS[i,k])) - (1 + la * Hij[i,k]) * exp(1 + la * KS[i,k]) - (1 + la * KS[i,k]) * exp(1 + la * Hij[i,k])) * ((2 + la * (Hij[i,j] - KS[i,j])) * exp(1 + la * (Hij[i,j] + KS[i,j])) + (2 + la * KS[i,j]) * exp(1 + la * Hij[i,j]) + ( 5 2 * la * (Hij[i,j] KS[i,j])) * exp(la * (Hij[i,j] + KS[i,j])) + exp(1 + la * KS[i,j]) * ( -2 + la * Kij[i,j] - (la * Hij[i,j])ˆ-2 + la * Hij[i,j] * ( - -2 + la * KS[i,j]))));
var Dikj { i in NODI, k in SEC[i], j in SEC[i] } =
if ( - Hij[i,j] + Hij[i,k] + KS[i,j] - KS[i,k] + 1/la) >= 0 then Dikj1[i,k,j] else Dikj0[i,k,j];
var Dijd1 { i in NODI, j in SEC[i], d in DI } = exp( 1 la * Hpi[i,d]) * ( -(Hpi[i,d])ˆ2 - 3 * Hpi[i,d] * Hij[i,j] + (Hij[i,j])ˆ2 + Hpi[i,d] * KP[i,d] + 2 * Hij[i,j] * KP[i,d] + 3 * Hpi[i,d] * KS[i,j] - 2 * Hij[i,j] * KS[i,j] - 2 * KP[i,d] * KS[i,j] + (KS[i,j])ˆ2 - 4/(la)ˆ( - 2) - 7 * Hpi[i,d]/(2 * la) - 3 * Hij[i,j]/la + 2 * KP[i,d]/la + 3 * KS[i,j]/la - la * Hij[i,j] * (Hpi[i,d])ˆ2 + 0.5 * la * Hpi[i,d] * (Hij[i,j])ˆ2 + la * Hpi[i,d] * Hij[i,j] * KP[i,d] + la * KS[i,j] * (Hpi[i,d])ˆ2 - la * Hpi[i,d] * Hij[i,j] * KS[i,j] - la * Hpi[i,d] * KP[i,d] * KS[i,j] + 0.5 * la * Hpi[i,d] * (KS[i,j])ˆ2) + exp( - 1) * ( - 2 * Hpi[i,d] * Hij[i,j] + (Hij[i,j])ˆ2 + 2 * Hij[i,j] * KP[i,d] + 2 * Hpi[i,d] * KS[i,j] - 2 * Hij[i,j] * KS[i,j] - 2 * KP[i,d] * KS[i,j] + (KS[i,j])ˆ2 - 4/(la)ˆ2 - 2 * Hpi[i,d]/la - 3 * Hij[i,j]/la + 2 * KP[i,d]/la + 3 * KS[i,j]/la) + Hpi[i,d] * Hij[i,j] - 0.5 * (Hij[i,j])ˆ2 - Hij[i,j] * KP[i,d] - Hpi[i,d] * KS[i,j] + Hij[i,j] * KS[i,j] + KP[i,d] * KS[i,j] - 0.5 * (KS[i,j])ˆ2 + laˆ( 2) * (3/2 + 3 * exp( la * KP[i,d]) 4 * exp( 1 la * (Hij[i,j] + KP[i,d]
-KS[i,j]))) + laˆ( - 1) * (Hpi[i,d] + Hij[i,j] - Hij[i,j] * exp( - 1 - la * (Hij[i,j] + KP[i,d] - KS[i,j])) - KP[i,d] + KP[i,d] * exp( - la * KP[i,d]) - KP[i,d] * exp( - 1 - la * (Hij[i,j] + KP[i,d] - KS[i,j])) - KS[i,j] + KS[i,j] * exp( - 1 - la * (Hij[i,j] + KP[i,d] - KS[i,j]))) + laˆ( - 1) * (exp( - 2 - la * (Hpi[i,d] + Hij[i,j] + KP[i,d] + KS[i,j])) * (2 * exp(la * (Hij[i,j] + KS[i,j])) + exp(1 + la * (Hij[i,j] + KS[i,j])) - (1 + la * Hij[i,j]) * exp(1 + la * KS[i,j]) - (1 + la * KS[i,j]) * exp(1 + la * Hij[i,j])) * ((2 + la * (Hpi[i,d] - KP[i,d])) * exp(1 + la * (Hpi[i,d] + KP[i,d])) + (2 + la * KP[i,d]) * exp(1 + la * Hpi[i,d]) + ( - 5 - 2 * la * (Hpi[i,d] - KP[i,d])) * exp(la * (Hpi[i,d] + KP[i,d])) + exp(1 + la * KP[i,d]) * ( - 2 + la * Kij[i,j] - (la * Hpi[i,d])ˆ2 + la * Hpi[i,d] * ( - 2 + la * KP[i,d])))) + 0.5 * laˆ( - 2) * exp( - 1 - la * (Hij[i,j] + KP[i,d])) * (2 * exp(la * (Hpi[i,d] + KS[i,j])) * ( - 4 + la * (Hpi[i,d] - Hij[i,j] - KP[i,d] + KS[i,j])) + exp(1 + la * (Hij[i,j] + KP[i,d])) * (3 - 2 * la * KP[i,d] + 2 * la * KS[i,j] + (la * Hpi[i,d])ˆ2 + (la * Hij[i,j])ˆ2 + (la * KP[i,d])ˆ2 - 2 * KP[i,d] * KS[i,j] * (la)ˆ2 + (la * KS[i,j])ˆ2 + 2 * la * Hij[i,j] * ( - 1 + la * (KP[i,d] - KS[i,j])) - 2 * la * Hpi[i,d] * ( - 1 + la * (Hij[i,j] + KP[i,d] - KS[i,j])))); var Dijd0 { i in NODI, j in SEC[i], d in DI } = exp( 1 la * Hpi[i,d]) * ( -(Hpi[i,d])ˆ2 - 3 * Hpi[i,d] * Hij[i,j] + (Hij[i,j])ˆ2 + Hpi[i,d] * KP[i,d] + 2 * Hij[i,j] * KP[i,d] + 3 * Hpi[i,d] * KS[i,j] - 2 * Hij[i,j] * KS[i,j] - 2 * KP[i,d] * KS[i,j] + (KS[i,j])ˆ2 - 4/(la)ˆ( - 2) - 7 * Hpi[i,d]/(2 * la) - 3 * Hij[i,j]/la + 2 * KP[i,d]/la + 3 * KS[i,j]/la - la * Hij[i,j] * (Hpi[i,d])ˆ2 + 0.5 * la * Hpi[i,d] * (Hij[i,j])ˆ2 + la * Hpi[i,d] * Hij[i,j] * KP[i,d] + la * KS[i,j] * (Hpi[i,d])ˆ2 - la * Hpi[i,d] * Hij[i,j] * KS[i,j] - la * Hpi[i,d] * KP[i,d] * KS[i,j] + 0.5 * la * Hpi[i,d] * (KS[i,j])ˆ2) + exp( - 1) * ( - 2 * Hpi[i,d] * Hij[i,j] + (Hij[i,j])ˆ2 + 2 * Hij[i,j] * KP[i,d] + 2 * Hpi[i,d] * KS[i,j] - 2 * Hij[i,j] * KS[i,j] - 2 * KP[i,d] * KS[i,j] + (KS[i,j])ˆ2 - 4/(la)ˆ2 - 2 * Hpi[i,d]/la - 3 * Hij[i,j]/la
+ 2 * KP[i,d]/la + 3 * KS[i,j]/la) + Hpi[i,d] * Hij[i,j] - 0.5 * (Hij[i,j])ˆ2 - Hij[i,j] * KP[i,d] - Hpi[i,d] * KS[i,j] + Hij[i,j] * KS[i,j] + KP[i,d] * KS[i,j] - 0.5 * (KS[i,j])ˆ2 + laˆ( 2) * (3/2 + 3 * exp( la * KP[i,d]) 4 * exp( 1 la * (Hij[i,j] + KP[i,d] -KS[i,j]))) + laˆ( - 1) * (Hpi[i,d] + Hij[i,j] - Hij[i,j] * exp( - 1 - la * (Hij[i,j] + KP[i,d] - KS[i,j])) - KP[i,d] + KP[i,d] * exp( - la * KP[i,d]) - KP[i,d] * exp( - 1 - la * (Hij[i,j] + KP[i,d] - KS[i,j])) - KS[i,j] + KS[i,j] * exp( - 1 - la * (Hij[i,j] + KP[i,d] - KS[i,j]))) + laˆ( - 1) * (exp( - 2 - la * (Hpi[i,d] + Hij[i,j] + KP[i,d] + KS[i,j])) * (2 * exp(la * (Hij[i,j] + KS[i,j])) + exp(1 + la * (Hij[i,j] + KS[i,j])) - (1 + la * Hij[i,j]) * exp(1 + la * KS[i,j]) - (1 + la * KS[i,j]) * exp(1 + la * Hij[i,j])) * ((2 + la * (Hpi[i,d] - KP[i,d])) * exp(1 + la * (Hpi[i,d] + KP[i,d])) + (2 + la * KP[i,d]) * exp(1 + la * Hpi[i,d]) + ( - 5 - 2 * la * (Hpi[i,d] - KP[i,d])) * exp(la * (Hpi[i,d] + KP[i,d])) + exp(1 + la * KP[i,d]) * ( - 2 + la * Kij[i,j] - (la * Hpi[i,d])ˆ2 + la * Hpi[i,d] * ( - 2 + la * KP[i,d]))));
var Dijd { i in NODI, j in SEC[i], d in DI } =
if ( - Hpi[i,d] + Hij[i,j] + KP[i,d] - KS[i,j] + 1/la) >= 0 then Dijd1[i,j,d] else Dijd0[i,j,d];
var Didj1 { i in NODI, d in DI, j in SEC[i] } = exp( 1 la * Hij[i,j]) * ( -(Hij[i,j])ˆ2 - 3 * Hij[i,j] * Hpi[i,d] + (Hpi[i,d])ˆ2 + Hij[i,j] * KS[i,j] + 2 * Hpi[i,d] * KS[i,j] + 3 * Hij[i,j] * KP[i,d] - 2 * Hpi[i,d] * KP[i,d] - 2 * KS[i,j] * KP[i,d] + (KP[i,d])ˆ2 - 4/(la)ˆ( - 2) - 7 * Hij[i,j]/(2 * la) - 3 * Hpi[i,d]/la + 2 * KS[i,j]/la + 3 * KP[i,d]/la - la * Hpi[i,d] * (Hij[i,j])ˆ2 + 0.5 * la * Hij[i,j] * (Hpi[i,d])ˆ2 + la * Hij[i,j] * Hpi[i,d] * KS[i,j] + la * KP[i,d] * (Hij[i,j])ˆ2 - la * Hij[i,j] * Hpi[i,d] * KP[i,d] - la * Hij[i,j] * KS[i,j] * KP[i,d] + 0.5 * la * Hij[i,j] * (KP[i,d])ˆ2) + exp( - 1) * ( - 2 * Hij[i,j] * Hpi[i,d] + (Hpi[i,d])ˆ2 + 2 * Hpi[i,d] * KS[i,j] + 2 * Hij[i,j] * KP[i,d] - 2 *
Hpi[i,d] * KP[i,d] - 2 * KS[i,j] * KP[i,d] + (KP[i,d])ˆ2 - 4/(la)ˆ2 - 2 * Hij[i,j]/la - 3 * Hpi[i,d]/la + 2 * KS[i,j]/la + 3 * KP[i,d]/la) + Hij[i,j] * Hpi[i,d] - 0.5 * (Hpi[i,d])ˆ2 - Hpi[i,d] * KS[i,j] - Hij[i,j] * KP[i,d] + Hpi[i,d] * KP[i,d] + KS[i,j] * KP[i,d] - 0.5 * (KP[i,d])ˆ2 + laˆ( - 2) * (3/2 + 3 * exp( - la * KS[i,j]) - 4 * exp( - 1 - la * (Hpi[i,d] + KS[i,j] - KP[i,d]))) + laˆ( - 1) * (Hij[i,j] + Hpi[i,d] - Hpi[i,d] * exp( - 1 - la * (Hpi[i,d] + KS[i,j] - KP[i,d])) - KS[i,j] + KS[i,j] * exp( - la * KS[i,j]) - KS[i,j] * exp( - 1 - la * (Hpi[i,d] + KS[i,j] - KP[i,d])) - KP[i,d] + KP[i,d] * exp( - 1 - la * (Hpi[i,d] + KS[i,j] - KP[i,d]))) + laˆ( - 1) * (exp( - 2 - la * (Hij[i,j] + Hpi[i,d] + KS[i,j] + KP[i,d])) * (2 * exp(la * (Hpi[i,d] + KP[i,d])) + exp(1 + la * (Hpi[i,d] + KP[i,d])) - (1 + la * Hpi[i,d]) * exp(1 + la * KP[i,d]) - (1 + la * KP[i,d]) * exp(1 + la * Hpi[i,d])) * ((2 + la * (Hij[i,j] - KS[i,j])) * exp(1 + la * (Hij[i,j] + KS[i,j])) + (2 + la * KS[i,j]) * exp(1 + la * Hij[i,j]) + ( - 5 - 2 * la * (Hij[i,j] - KS[i,j])) * exp(la * (Hij[i,j] + KS[i,j])) + exp(1 + la * KS[i,j]) * ( - 2 + la * Kij[i,j] - (la * Hij[i,j])ˆ2 + la * Hij[i,j] * ( - 2 + la * KS[i,j])))) + 0.5 * laˆ( - 2) * exp( - 1 - la * (Hpi[i,d] + KS[i,j])) * (2 * exp(la * (Hij[i,j] + KP[i,d])) * ( - 4 + la * (Hij[i,j] - Hpi[i,d] - KS[i,j] + KP[i,d])) + exp(1 + la * (Hpi[i,d] + KS[i,j])) * (3 - 2 * la * KS[i,j] + 2 * la * KP[i,d] + (la * Hij[i,j])ˆ2 + (la * Hpi[i,d])ˆ2 + (la * KS[i,j])ˆ2 - 2 * KS[i,j] * KP[i,d] * (la)ˆ2 + (la * KP[i,d])ˆ2 + 2 * la * Hpi[i,d] * ( - 1 + la * (KS[i,j] - KP[i,d])) - 2 * la * Hij[i,j] * ( - 1 + la * (Hpi[i,d] + KS[i,j] - KP[i,d]))));
var Didj0 { i in NODI, d in DI, j in SEC[i] } = exp( 1 la * Hij[i,j]) * ( -(Hij[i,j])ˆ2 - 3 * Hij[i,j] * Hpi[i,d] + (Hpi[i,d])ˆ2 + Hij[i,j] * KS[i,j] + 2 * Hpi[i,d] * KS[i,j] + 3 * Hij[i,j] * KP[i,d] - 2 * Hpi[i,d] * KP[i,d] - 2 * KS[i,j] * KP[i,d] + (KP[i,d])ˆ2 - 4/(la)ˆ( - 2) - 7 * Hij[i,j]/(2 * la) - 3 * Hpi[i,d]/la + 2 * KS[i,j]/la + 3 *
KP[i,d]/la - la * Hpi[i,d] * (Hij[i,j])ˆ2 + 0.5 * la * Hij[i,j] * (Hpi[i,d])ˆ2 + la * Hij[i,j] * Hpi[i,d] * KS[i,j] + la * KP[i,d] * (Hij[i,j])ˆ2 - la * Hij[i,j] * Hpi[i,d] * KP[i,d] - la * Hij[i,j] * KS[i,j] * KP[i,d] + 0.5 * la * Hij[i,j] * (KP[i,d])ˆ2) + exp( - 1) * ( - 2 * Hij[i,j] * Hpi[i,d] + (Hpi[i,d])ˆ2 + 2 * Hpi[i,d] * KS[i,j] + 2 * Hij[i,j] * KP[i,d] - 2 * Hpi[i,d] * KP[i,d] - 2 * KS[i,j] * KP[i,d] + (KP[i,d])ˆ2 - 4/(la)ˆ2 - 2 * Hij[i,j]/la - 3 * Hpi[i,d]/la + 2 * KS[i,j]/la + 3 * KP[i,d]/la) + Hij[i,j] * Hpi[i,d] - 0.5 * (Hpi[i,d])ˆ2 - Hpi[i,d] * KS[i,j] - Hij[i,j] * KP[i,d] + Hpi[i,d] * KP[i,d] + KS[i,j] * KP[i,d] - 0.5 * (KP[i,d])ˆ2 + laˆ( - 2) * (3/2 + 3 * exp( - la * KS[i,j]) - 4 * exp( - 1 - la * (Hpi[i,d] + KS[i,j] - KP[i,d]))) + laˆ( - 1) * (Hij[i,j] + Hpi[i,d] - Hpi[i,d] * exp( - 1 - la * (Hpi[i,d] + KS[i,j] - KP[i,d])) - KS[i,j] + KS[i,j] * exp( - la * KS[i,j]) - KS[i,j] * exp( - 1 - la * (Hpi[i,d] + KS[i,j] - KP[i,d])) - KP[i,d] + KP[i,d] * exp( - 1 - la * (Hpi[i,d] + KS[i,j] - KP[i,d]))) + laˆ( - 1) * (exp( - 2 - la * (Hij[i,j] + Hpi[i,d] + KS[i,j] + KP[i,d])) * (2 * exp(la * (Hpi[i,d] + KP[i,d])) + exp(1 + la * (Hpi[i,d] + KP[i,d])) - (1 + la * Hpi[i,d]) * exp(1 + la * KP[i,d]) - (1 + la * KP[i,d]) * exp(1 + la * Hpi[i,d])) * ((2 + la * (Hij[i,j] - KS[i,j])) * exp(1 + la * (Hij[i,j] + KS[i,j])) + (2 + la * KS[i,j]) * exp(1 + la * Hij[i,j]) + ( - 5 - 2 * la * (Hij[i,j] - KS[i,j])) * exp(la * (Hij[i,j] + KS[i,j])) + exp(1 + la * KS[i,j]) * ( - 2 + la * Kij[i,j] - (la * Hij[i,j])ˆ2 + la * Hij[i,j] * ( - 2 + la * KS[i,j]))));
var Didj { i in NODI, d in DI, j in SEC[i] } =
if ( - Hij[i,j] + Hpi[i,d] + KS[i,j] - KP[i,d] + 1/la) >= 0 then Didj1[i,d,j] else Didj0[i,d,j];
var Mikj1 { i in NODI, k in SEC[i], j in SEC[i] } = (3/la Hij[i,k] + KS[i,j] -KS[i,k]) * exp( - la * (1/la + Hij[i,k] + KS[i,j] - -KS[i,k])) + ( - 1/la + Hij[i,k] + la
* Hij[i,k] * KS[i,j] - KS[i,k] - la * KS[i,j] * KS[i,k]) * exp( - la * KS[i,j]) + (1 + 2 * exp( - 1) + ( - 1 - la * Hij[i,j]) * exp( - la * Hij[i,j]) + ( - 1 - la * KS[i,j]) * exp( - la * KS[i,j])) * (1 - 2 * exp( - 1) + ( - 1 - la * Hij[i,k]) * exp( - la * Hij[i,k]) + (1 + la * KS[i,k]) * exp( - la * KS[i,k])) + ( - 1/la + 3 * exp( - 1 - la * Hij[i,k] - la * KS[i,j] + la * (Hij[i,j] + KS[i,k]))/la + (1 + exp( - 1 - la * Hij[i,k] - la * KS[i,j] + la * (Hij[i,j] + KS[i,k]))) * (Hij[i,k] - Hij[i,j]) + (1 + exp( - 1 - la * Hij[i,k] - la * KS[i,j] + la * (Hij[i,j] + KS[i,k]))) * (KS[i,j] - KS[i,k]));
var Mikj0 { i in NODI, k in SEC[i], j in SEC[i] } = (3/la Hij[i,k] + KS[i,j] -KS[i,k]) * exp( - la * (1/la + Hij[i,k] + KS[i,j] - -KS[i,k])) + ( - 1/la + Hij[i,k] + la * Hij[i,k] * KS[i,j] - KS[i,k] - la * KS[i,j] * KS[i,k]) * exp( - la * KS[i,j]) + (1 + 2 * exp( - 1) + ( - 1 - la * Hij[i,j]) * exp( - la * Hij[i,j]) + ( - 1 - la * KS[i,j]) * exp( - la * KS[i,j])) * (1 - 2 * exp( - 1) + ( - 1 - la * Hij[i,k]) * exp( - la * Hij[i,k]) + (1 + la * KS[i,k]) * exp( - la * KS[i,k]));
var Mikj { i in NODI, k in SEC[i], j in SEC[i] } =
if (1/la - Hij[i,j] + Hij[i,k] + KS[i,j] - KS[i,k]) >= 0 then Mikj1[i,k,j] else Mikj0[i,k,j];
var Mijd1 { i in NODI, j in SEC[i], d in DI } = (3/la - Hij[i,j] + KP[i,d] - KS[i,j]) * exp( - la * (1/la + Hij[i,j] + KP[i,d] - KS[i,j])) + ( - 1/la + Hij[i,j] + la * Hij[i,j] * KP[i,d] KS[i,j] la * KP[i,d] * KS[i,j]) * exp( la * KP[i,d]) + (1 + 2 * exp( -1) + ( - 1 - la * Hpi[i,d]) * exp( - la * Hpi[i,d]) + ( - 1 - la * KP[i,d]) * exp( - la * KP[i,d])) * (1 - 2 * exp( - 1) + ( - 1 - la * Hij[i,j]) * exp( - la * Hij[i,j]) + (1 + la * KS[i,j]) * exp( - la * KS[i,j])) + ( - 1/la + 3 * exp( - 1 - la * Hij[i,j] - la * KP[i,d] + la * (Hpi[i,d] + KS[i,j]))/la + (1 + exp( - 1 - la * Hij[i,j] - la * KP[i,d] + la * (Hpi[i,d]
+ KS[i,j]))) * (Hij[i,j] - Hpi[i,d]) + (1 + exp( - 1 - la * Hij[i,j] - la * KP[i,d] + la * (Hpi[i,d] + KS[i,j]))) * (KP[i,d] - KS[i,j]));
var Mijd0 { i in NODI, j in SEC[i], d in DI } = (3/la - Hij[i,j] + KP[i,d] - KS[i,j]) * exp( - la * (1/la + Hij[i,j] + KP[i,d] - KS[i,j])) + ( - 1/la + Hij[i,j] + la * Hij[i,j] * KP[i,d] - KS[i,j] - la * KP[i,d] * KS[i,j]) * exp( - la * KP[i,d]) + (1 + 2 * exp( - 1) + ( - 1 - la * Hpi[i,d]) * exp( - la * Hpi[i,d]) + ( - 1 - la * KP[i,d]) * exp( - la * KP[i,d])) * (1 - 2 * exp( - 1) + ( - 1 - la * Hij[i,j]) * exp( - la * Hij[i,j]) + (1 + la * KS[i,j]) * exp( - la * KS[i,j]));
var Mijd { i in NODI, j in SEC[i], d in DI } =
if (1/la - Hpi[i,d] + Hij[i,j] + KP[i,d] - KS[i,j]) >= 0 then Mijd1[i,j,d] else Mijd0[i,j,d];
var Midj1 { i in NODI, d in DI, j in SEC[i] } = (3/la - Hpi[i,d] + KS[i,j] - KP[i,d]) * exp( - la * (1/la + Hpi[i,d] + KS[i,j] - KP[i,d])) + ( - 1/la + Hpi[i,d] + la * Hpi[i,d] * KS[i,j] - KP[i,d] - la * KS[i,j] * KP[i,d]) * exp( - la * KS[i,j]) + (1 + 2 * exp( - 1) + ( - 1 - la * Hij[i,j]) * exp( - la * Hij[i,j]) + ( - 1 - la * KS[i,j]) * exp( - la * KS[i,j])) * (1 - 2 * exp( - 1) + ( - 1 - la * Hpi[i,d]) * exp( - la * Hpi[i,d]) + (1 + la * KP[i,d]) * exp( - la * KP[i,d])) + ( - 1/la + 3 * exp( - 1 - la * Hpi[i,d] - la * KS[i,j] + la * (Hij[i,j] + KP[i,d]))/la + (1 + exp( - 1 - la * Hpi[i,d] - la * KS[i,j] + la * (Hij[i,j] + KP[i,d]))) * (Hpi[i,d] - Hij[i,j]) + (1 + exp( - 1 - la * Hpi[i,d] - la * KS[i,j] + la * (Hij[i,j] + KP[i,d]))) * (KS[i,j] - KP[i,d]));
var Midj0 { i in NODI, d in DI, j in SEC[i] } = (3/la - Hpi[i,d] + KS[i,j] - KP[i,d]) * exp( - la * (1/la + Hpi[i,d] + KS[i,j] - KP[i,d])) + ( - 1/la + Hpi[i,d] + la * Hpi[i,d] * KS[i,j] - KP[i,d] - la * KS[i,j] * KP[i,d]) * exp( - la * KS[i,j]) + (1 + 2 * exp( - 1)
+ ( - 1 - la * Hij[i,j]) * exp( - la * Hij[i,j]) + ( - 1 - la * KS[i,j]) * exp( - la * KS[i,j])) * (1 - 2 * exp( - 1) + ( - 1 - la * Hpi[i,d]) * exp( - la * Hpi[i,d]) + (1 + la * KP[i,d]) * exp( - la * KP[i,d]));
var Midj { i in NODI, d in DI, j in SEC[i] } =
if (1/la - Hij[i,j] + Hpi[i,d] + KS[i,j] - KP[i,d]) >= 0 then Midj1[i,d,j] else Midj0[i,d,j];
var Tcikj { i in NODI, k in SEC[i], j in SEC[i] } = Kij[i,k] + Dikj[i,k,j] + Mikj[i,k,j]; var Tcijd { i in NODI, j in SEC[i], d in DI } = Kij[i,j] + Dijd[i,j,d] + Mijd[i,j,d]; var Tcidj { i in NODI, d in DI, j in SEC[i] } = Kid[i,d] + Didj[i,d,j] + Midj[i,d,j]; var Ct = sum { i in NODI, k in SEC[i], j in SEC[i] } (attr sec sec[i,k,j] * uw * (cord[i,j] * cord[i,k] * Tcikj[i,k,j] + (1 - cord[i,j] * cord[i,k]) * Tnikj[i,k,j])) + sum { i in NODI, d in DI, j in SEC[i] } (attr pri sec[i,d,j] * uw * (yid[i,d] * Tcidj[i,d,j] + (1 -yid[i,d]) * Tnidj[i,d,j])) + sum { i in NODI, j in SEC[i], d in DI } (attr sec pri[i,j,d] * uw * (yid[i,d] * Tcijd[i,j,d] + (1 - yid[i,d]) * Tnijd[i,j,d]));
param cap { i in NODI, j in SEC[i] } , >= 0; param Twip >= 0;
param Twfj >= 0;
param Tp := 0.5 * rtp - Twip * n;
param Cv := sum { i in NODI, j in SEC[i], z in DELTA } (Iij[i,j,z] * uv * 0.5 * rtt[i,j]) + sum { s in 2..(n 1), d in DI } (Tp * uv * (Aid[s,d] (saliti pri[s,d] * (2 -d) + discesi pri[s,d] * (d - 1)))) + sum { s in 1..(n - 1), d in DI } (uv * Aid[s,d] * n * Twip);
subject to posit1 : Co >= 0; subject to posit2 : Cw >= 0; subject to posit3 : Ct >= 0;
subject to posec { i in NODI, j in SEC[i] } : Hij[i,j] >= cap[i,j]; subject to popri { d in DI } : Hp[d] >= 0.40;
subject to cappaj { i in NODI, j in SEC[i] } : Kij[i,j] <= 0.5; subject to cappad { i in NODI, d in DI } : Kid[i,d] <= 0.5;
6.2
Il file dei dati
Il file cord.dat contiene invece i dati di input, nel nostro caso il movimento passeggeri, i tempi di viaggio e i vari costi che entrano in gioco nel modello. Per ogni fascia oraria si utilizza un diverso file di dati. Si riporta come esempio quello relativo alla fascia 6 : 00 − 8 : 00. set NODI := 1, 2, 3, 4, 5; set TRATTE := 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 18, 1000; set PRINCIPALI := 3, 5, 8, 10, 1000; set SEC[1] := 1, 2; set SEC[2] := 4, 6; set SEC[3] := 7; set SEC[4] := 9; set SEC[5] := 11, 12, 18; param: vHij:=
1 1 16.13396 1 2 16.13396 2 4 16.13396 2 6 16.13396 3 7 16.13396 4 9 16.13396 5 11 16.13396 5 12 16.13396 5 18 16.13396; param: vHp:= 1 16.13396 2 16.13396; param: costo := 1 809.87 2 762.74 3 865.13 4 579.51 5 728.52 6 648.08 7 593.76 8 859.19 9 1091.56 10 447.20
11 876.04 12 795.88 18 639.37 1000 698.75; param rtt:= 1 1 1.15 1 2 0.68 1 3 0.33 2 3 0.33 2 4 3.82 2 5 0.74 3 5 0.74 2 6 0.92 3 7 1.65 3 8 0.26 4 8 0.26 4 9 0.90 4 10 0.44 5 10 0.44 5 11 4.23 5 12 1.05 5 18 1.35; param rtp = 1.78;
param Twip = 0.03; param Twfj = 0.02; param attr sec pri := 1 1 1 12.5 1 2 1 5.5 2 4 2 16 2 4 1 16 2 6 2 1 2 6 1 36.5 3 7 2 6 3 7 1 8.5 4 9 2 5.5 4 9 1 314 5 11 2 57 5 12 2 203.5 5 18 2 24.5;
param attr pri sec := 1 2 1 20 1 2 2 4 2 1 4 40.5 2 1 6 1 2 2 4 3.5 2 2 6 142.5
3 1 7 0.5 3 2 7 0 4 1 9 0.5 4 2 9 3 5 1 11 0 5 1 12 0 5 1 18 0;
param attr sec sec := 1 1 2 711 1 2 1 195 2 4 6 96 2 6 4 6.5 5 11 12 196 5 11 18 11.5 5 12 11 100.5 5 12 18 9 5 18 11 7.5 5 18 12 6.5; param saliti := 1 1 14 2 1 63.5 2 2 30.5 3 1 208.5
3 2 3 4 1 822 4 2 38 5 2 154.5; param discesi := 1 2 25.5 2 1 65.5 2 2 64 3 1 15.5 3 2 0 4 1 25 4 2 18 5 1 0; param uw = 8.4; param uv = 6; param cap := 1 1 0.40 1 2 0.40 2 4 0.22 2 6 0.22 3 7 0.22 4 9 0.40 5 11 0.40
5 12 0.40 5 18 0.22;
6.3
Il file dei comandi
model cord.mod;
param epsilon := 1.e - 7; data cord6 8.dat;
option solver minos;
option minos options Major iterations= 500; option display precision 0;
# FASE 1
let { d in DI } Hp[d] := sqrt( (costo[1000] * rtp + 0.5 * uw * vHp[d] * sum { i in NODI, j in SEC[i] } attr sec pri[i,j,d]) / (0.5 * uw * (sum { i in NODI } saliti[i,d] + sum { i in NODI, j in SEC[i] } attr sec pri[i,j,d])));
let { i in NODI, j in SEC[i] } Hij[i,j] :=
if (0.5 * uw * (trasb1[i,j] + sum { k in SEC[i] } attr sec sec[i,k,j])) != 0 then sqrt( (costo[j] * rtt[i,j] + 0.5 * uw * vHij[i,j] + sum { k in SEC[i] } attr sec sec[i,k,j]) / (0.5 * uw * (trasb1[i,j] + sum { k in SEC[i] } attr sec sec[i,k,j])));
let { i in NODI, d in DI } Hpi[i,d]:= Hp[d]; display Hij, Hp, costo tot > ./Out/Fase1.out; # FASE 2
let { i in NODI, j in SEC[i] } optcord[i,j] := 0; let OB2 := costo tot;
fix { d in DI } Hp[d];
fix { i in NODI, d in DI } Kid[i,d]; for { i in NODI }
{ for { kfit in SEC[i] } { for { k in SEC[i] }
{ if (cord[i,k] == 0 && Hij[i,k] == max { j in SEC[i]: cord[i,j] == 0 } Hij[i,j])
then
{ let cord[i,k]:= 1;
fix Hij; fix Kij;
unfix { j in SEC[i]: cord[i,j] == 1 } Hij[i,j]; unfix { j in SEC[i]: cord[i,j] == 1 } Kij[i,j]; solve;
if costo tot <= (OB2 + epsilon) then
{ let OB2 := costo tot;
let { s in NODI, j in SEC[s] } optcord[s,j] := cord[s,j]; let { s in NODI, j in SEC[s] } optHij[s,j] := Hij[s,j]; let { s in NODI, j in SEC[s] } optKij[s,j] := Kij[s,j];
} ;
display i, k , costo tot, cord, OB2, optcord > ./Out/Intermedio2.out;
} ; } ; } ;
let { i in NODI, d in DI } optHpi[i,d] := Hp[d]; let { i in NODI, d in DI } optKid[i,d] := Kid[i,d]; display optHij, optKij > ./Out/Hij2.out;
display optHpi, optKid > ./Out/Hp2.out; display OB2, optcord > ./Out/Costo2.out; # FASE 3
let { i in NODI, d in DI } yid[i,d] := 0; let { i in NODI, d in DI } optyid[i,d] := 0; let OB3 := OB2;
for { i in NODI }
{ for { d in DI }
{ if yid [i,d] == 0 then { fix Hij;
fix Kij; fix Hp; fix Kid;
unfix { j in SEC[i] } Hij[i,j]; unfix { j in SEC[i] } Kij[i,j]; unfix Hp[d];
solve;
let yid [i,d] := 1; let Hpi[i,d] := Hp[d];
if costo tot <= (OB3 + epsilon) then
{ let OB3 := costo tot;
let { s in NODI, y in DI } optyid[s,y] := yid[s,y]; let { s in NODI, y in DI } optHpi[s,y] := Hpi[s,y]; let { s in NODI, j in SEC[s] } optHij[s,j] := Hij[s,j]; let { s in NODI, j in SEC[s] } optKij[s,j] := Kij[s,j]; let { s in NODI, y in DI } optKid[s,y] := Kid[s,y];
} ;
display i, d, costo tot, yid, OB3, optyid > ./Out/Intermedio3.out;
} ; } ; } ;
display optHij, optKij > ./Out/Hij3.out; display optHpi, optKid > ./Out/Hpi3.out; display OB3, optyid > ./Out/Costo3.out; # FASE 4:
let { i in NODI, d in DI } pid[i,d] := 0; let { i in NODI, d in DI } optpid[i,d] := 0; let OB4 := OB3;
{ for { sfit in NODI } { for { s in NODI }
{ if (pid[s,y] == 0 && Hpi[s,y] == max { i in NODI: pid[i,y] == 0 } Hpi[i,y])
then { let pid[s,y] := 1; fix Hij; fix Kij; fix Hp; fix Kid;
unfix { i in NODI, j in SEC[i]: pid[i,y] == 1 } Hij[i,j]; unfix { i in NODI, j in SEC[i]: pid[i,y] == 1 } Kij[i,j]; unfix { i in NODI: pid[i,y] == 1 } Kid[i,y];
unfix Hp[y]; solve;
let { i in NODI } Hpi[i,y] := Hp[y]; if costo tot <= (OB4 + epsilon) then
{ let OB4 := costo tot;
let { i in NODI, d in DI } optpid[i,d] := pid[i,d]; let { i in NODI, d in DI } optHpi[i,d] := Hpi[i,d]; let { i in NODI, j in SEC[i] } optHij[i,j] := Hij[i,j]; let { i in NODI, j in SEC[i] } optKij[i,j] := Kij[i,j]; let { i in NODI, d in DI } optKid[i,d] := Kid[i,d];
display y, s, costo tot, pid, OB4, optpid > ./Out/Inter4.out; } ; } ; } ; } ; # FASE 5:
let { i in NODI, d in DI } p5id[i,d] := 0;
let { i in NODI, d in DI } optp5id[i,d] := optpid[i,d]; let { i in NODI, d in DI } cont[i,d] := 0;
let OB5 := OB4; for { y in DI }
{ for { s in NODI }
{ if (Hpi[s,y] == max { i in NODI } Hpi[i,y]) then let cont[s,y] := 1; } ;
for { sfit in NODI }
{ for { s in NODI: cont[s,y] == 0 }
{ if (p5id[s,y] == 0 && Hpi[s,y] == max { i in NODI: p5id[i,y] == 0 && cont[i,y]
== 0 } Hpi[i,y]) then { let p5id[s,y] := 1; fix Hij; fix Kij; fix Hp; fix Kid;
unfix { i in NODI, j in SEC[i]: pid[i,y] == 1 } Hij[i,j]; unfix { i in NODI, j in SEC[i]: pid[i,y] == 1 } Kij[i,j]; unfix { i in NODI: pid[i,y] == 1 } Kid[i,y];
unfix Hp[y]; solve;
if costo tot <= (OB5 + epsilon) then
{ let OB5 := costo tot;
let { i in NODI, d in DI } optp5id[i,d] := p5id[i,d]; let { i in NODI, d in DI } optHpi[i,d] := Hpi[i,d]; let { i in NODI, j in SEC[i] } optHij[i,j] := Hij[i,j]; let { i in NODI, j in SEC[i] } optKij[i,j] := Kij[i,j]; let { i in NODI, d in DI } optKid[i,d] := Kid[i,d];
} ;
display y, s, costo tot, p5id, OB5, optp5id > ./Out/Inter5.out;
} ; } ; } ; } ;
display optHij, optKij > ./Out/Hij5.out; display optHpi, optKid > ./Out/Hpi5.out; display OB5, optp5id > ./Out/Costo5.out;
display OB2, optcord, OB3, optyid, OB5, optp5id > ./Out/Finale.out; quit
6.4
La FaseI
Nella FaseI non `e richiesta nessuna ottimizzazione perch`e, come abbiamo visto, in assenza di coordinamento il costo totale `e funzione solo degli headways delle linee; per calcolare questi ultimi `e quindi sufficiente porre uguale a zero la derivata prima del costo totale. Il file di output relativo a questa fase e alla fascia oraria che va dalle 6 : 00 alle 8 : 00 si presenta cos´ı:
Hij := 1 1 0.5562958022408316 1 2 0.5820811927220929 2 4 2.0110746303244826 2 6 1.1361499084013682 3 7 4.119149131697102 4 9 0.8844103585055153 5 11 1.5744825805593323 5 12 0.7145283116155883 5 18 1.9545877524276303 Hp [*] := 1 2.1033104515579852 2 3.1506431214105444 costo tot = 232957.67003289328
Dai valori ottenuti per gli headways Hij delle linee secondarie risulta quindi che, delle due linee passanti per il nodo 1, ovvero la linea 1 e la linea 2, la prima ha
un headway di 0.56 ore, mentre la seconda ha un headway di 0.58 ore. L’headway maggiore `e quello della linea 7, passante per il nodo 3, pari a 4.12 ore. Per quanto riguarda la linea principale invece, in direzione 1 (cio`e da Viareggio verso Firenze) l’headway Hp[1] `e pari a 2.10h, mentre nella direzione opposta Hp[2] `e 3.15h. Il tutto a fronte di un costo complessivo di 232958Euro
h .
6.5
La FaseII
Nella FaseII invece si devono coordinare tra loro le linee secondarie passanti per lo stesso nodo i. Si fa uso del vettore cord[i, j] che indica lo stato di coordinamento corrente e di optcord[i, j] che tiene memoria di quello migliore, in termini di costo, trovato fino a questo momento. Se in questi vettori l’indice relativo ad una certa linea ´e pari a 1 significa che la linea ´e coordinata, se invece ´e 0 significa che non ´e coordinata. Il parametro OB2 indica il valore pi`u basso del costo totale trovato durante la FaseII: viene inizializzato con il valore trovato in FaseI e aggiornato insieme ad optcord ogni volta che si trova un coordinamento tra linee che determina un valore pi´u basso del costo totale. Vediamo l’esempio del file di output della FaseII ottenuto con i dati dell’intervallo 6 : 00 − 8 : 00. Per ogni nodo i ad ogni ciclo si deve cercare la linea secondaria j passante per i che ha headway massimo e che non `e ancora coordinata (cord[i, j] = 0) quindi le si assegna il valore cord[i, j] = 1: nel caso in esame risulta che per il nodo i = 1 la linea secondaria con headway maggiore `e la numero 2, infatti il file di output indica:
k = 2 costo tot = 179541.5830248794 cord := 1 1 0 1 2 1 2 4 0 2 6 0 3 7 0 4 9 0 5 11 0 5 12 0 5 18 0 OB2 = 179541.5830248794 optcord := 1 1 0 1 2 1 2 4 0 2 6 0 3 7 0 4 9 0 5 11 0 5 12 0 5 18 0
Si vede come, essendo il valore trovato di costo tot inferiore a quello precedente,
OB2 sia stato aggiornato con il nuovo valore: il costo ´e passato quindi da 232958Euro h
a 179542Euro
h . Al passo successivo del ciclo l’algoritmo aggiunge un’altra linea al
coordinamento, in particolare la numero 1, sempre appartenente al nodo 1, quindi si passa da un costo di 179542Euro
h a 143573Euroh , che comporta l’aggiornamento sia di
optcord che di OB2:
i = 1 k = 1 costo tot = 143573.20913725474 cord := 1 1 1 1 2 1 2 4 0 2 6 0 3 7 0 4 9 0 5 11 0 5 12 0 5 18 0 OB2 = 143573.20913725474 optcord := 1 1 1 1 2 1
2 4 0 2 6 0 3 7 0 4 9 0 5 11 0 5 12 0 5 18 0
Il ciclo continua in questo modo prendendo via via in considerazioni tutti i nodi
i, finch´e si raggiunge il risultato finale in cui si ha che:
i = 5 k = 12 costo tot = 115684.38068960627 cord := 1 1 1 1 2 1 2 4 1 2 6 1 3 7 1 4 9 1 5 11 1 5 12 1 5 18 1 OB2 = 115684.38068960627
optcord := 1 1 1 1 2 1 2 4 1 2 6 1 3 7 1 4 9 1 5 11 1 5 12 1 5 18 1
Quindi dalla FaseI alla FaseII si ´e passati da un costo di 232958Euro
h ad uno di
115684Euro
h , con un risparmio di 117274Euroh , quindi il costo totale si ´e dimezzato.
Tale diminuzione di costo orario si ha adottando i seguenti headways e slack times: optHij:= 1 1 1.4219959980738242 1 2 2.186438860724489 2 4 2.339992246989296 2 6 2.636313304670288 3 7 11.419196730767005 4 9 6.321998393267259 5 11 2.0015724159973414 5 12 1.9110935430867062 5 18 2.407184436869917
optKij:= 1 1 0.08 1 2 0.5 2 4 0.08 2 6 0.46402889581796114 3 7 0.08 4 9 0.08 5 11 0.08 5 12 0.08 5 18 0.08 optHpi:= 1 1 2.1033104515579852 1 2 3.1506431214105444 2 1 2.1033104515579852 2 2 3.1506431214105444 3 1 2.1033104515579852 3 2 3.1506431214105444 4 1 2.1033104515579852 4 2 3.1506431214105444 5 1 2.1033104515579852 5 2 3.1506431214105444 optKid := 1 1 0.08
1 2 0.08 2 1 0.08 2 2 0.08 3 1 0.08 3 2 0.08 4 1 0.08 4 2 0.08 5 1 0.08 5 2 0.08
6.6
La FaseIII
In questa fase, nodo per nodo, direzione per direzione, si coordina il gruppo delle linee
SEC[i], con il grado di coordinamento trovato nella FASEII, alla linea principale. yid[i, j] e costotot indicano rispettivamente lo stato attuale del coordinamento e il
costo tot, mentre i valori ottimi sono memorizzati rispettivamente da optyid[i, j] e
OB3. Se yid[i, d] = 0 significa che il gruppo di linee secondarie passanti per i e
coordinate tra loro nella FaseII non `e ancora coordinato alla linea principale i in direzione d. Al primo passo del ciclo si ha il coordinamento del gruppo di linee secondarie passanti per i = 1, ovvero per Viareggio, con la linea principale in direzione
d = 1, ovvero Firenze:
i = 1 d = 1
costo tot = 115052.72349695596 yid := 1 1 1 1 2 0 2 1 0 2 2 0 3 1 0 3 2 0 4 1 0 4 2 0 5 1 0 5 2 0 OB3 = 115052.72349695596 optyid := 1 1 1 1 2 0 2 1 0 2 2 0 3 1 0 3 2 0 4 1 0 4 2 0 5 1 0
5 2 0
Il guadagno, in termini di costo orario complessivo, derivante dal solo coordina-mento del nodo i = 1 ammonta a 631Euro
h , infatti si `e passati da un costo di 115684 Euro
h
ad uno di 115053Euro
h . Proseguendo con gli altri nodi della rete si arriva al termine
della FaseIII con i seguenti risultati: i = 5 d = 2 costo tot = 87423.1876641534 yid := 1 1 1 1 2 1 2 1 1 2 2 1 3 1 1 3 2 1 4 1 1 4 2 1 5 1 1 5 2 1 OB3 = 87423.1876641534 optyid := 1 1 1 1 2 1
2 1 1 2 2 1 3 1 1 3 2 1 4 1 1 4 2 1 5 1 1 5 2 1 optHij := 1 1 1.4143197991887528 1 2 2.1824606115934047 2 4 2.0566145503671907 2 6 2.445439993064003 3 7 3.4205020201358614 4 9 0.5761930463403537 5 11 2.001393291932813 5 12 1.9109163758904184 5 18 2.405520261448135 optKij := 1 1 0.08 1 2 0.5 2 4 0.08 2 6 0.21869338749692754
3 7 0.08 4 9 0.08 5 11 0.08 5 12 0.08 5 18 0.08 optHpi := 1 1 2.6284462546604477 1 2 0.8590923666415663 2 1 2.06202156527363 2 2 0.8656779227041248 3 1 2.58649131702246 3 2 2.6254825255602015 4 1 4.450708368108015 4 2 2.2566220554097156 5 1 2.5116546285457737 5 2 2.4361161099151802 optKid := 1 1 0.08 1 2 0.08 2 1 0.08 2 2 0.08 3 1 0.08 3 2 0.08
4 1 0.08 4 2 0.08 5 1 0.08 5 2 0.08
Il costo finale `e di 87423Euro
h , con un risparmio, rispetto alla FaseII, di 28261 Euro
h ,
mentre rispetto alla FaseI il risparmio `e di 145535Euro h .
6.7
La FaseIV
In questa fase si coordinano tra loro i gruppi di linee, principale compresa, passanti per i vari nodi i. Per ogni direzione d si considerano uno per uno le linee relative ai nodi non ancora coordinati, prendendo i nodi in ordine decrescente di headway. Si nota, alla prima iterazione dell’esempio considerato, che questo tipo di coordinamento non diminuisce il costo totale, quindi il valore ottimo del costo totale OB4, inizializzato con l’ultimo valore trovato nella FaseIII, non viene aggiornato con il nuovo valore ottenuto, cos´ı come non viene aggiornato il vettore optpid che indica il grado del coordinamento ottimo. y = 1 s = 4 costo tot = 98122.6312197572 pid := 1 1 0 1 2 0
2 1 0 2 2 0 3 1 0 3 2 0 4 1 1 4 2 0 5 1 0 5 2 0 OB4 = 87423.1876641534 optpid := 1 1 0 1 2 0 2 1 0 2 2 0 3 1 0 3 2 0 4 1 0 4 2 0 5 1 0 5 2 0
In questo caso neanche al termine della FaseIV si ottengono miglioramenti della funzione obiettivo, infatti l’output dell’ultima iterazione ´e:
s = 4 costo tot = 89636.87223420979 pid := 1 1 1 1 2 1 2 1 1 2 2 1 3 1 1 3 2 1 4 1 1 4 2 1 5 1 1 5 2 1 OB4 = 87423.1876641534 optpid := 1 1 0 1 2 0 2 1 0 2 2 0 3 1 0 3 2 0 4 1 0 4 2 0
5 1 0 5 2 0
6.8
La FaseV
Con la FaseV, che altro non `e che una ripetizione della FaseIV sotto diverse con-dizioni, verifico se eliminando dal coordinamento, per ogni direzione, il nodo in cui la principale ha l’headway piu’ gravoso, la funzione di costo diminuisce. Gi´a alla prima iterazione si notano i miglioramenti, in termini di costo complessivo:
y = 1 s = 1 costo tot = 83530.08850672081 p5id := 1 1 1 1 2 0 2 1 0 2 2 0 3 1 0 3 2 0 4 1 0 4 2 0 5 1 0 5 2 0
OB5 = 83530.08850672081 optp5id := 1 1 1 1 2 0 2 1 0 2 2 0 3 1 0 3 2 0 4 1 0 4 2 0 5 1 0 5 2 0
In questo caso si nota che il risultato ottenuto alla prima iterazione della FaseV non subisce miglioramenti nelle iterazioni successive, infatti il costo resta costante. Il risultato finale ´e:
y = 2 s = 1 costo tot = 83530.08850672084 p5id := 1 1 1 1 2 1 2 1 1 2 2 1
3 1 1 3 2 0 4 1 0 4 2 1 5 1 1 5 2 1 OB5 = 83530.08850672084 optp5id := 1 1 1 1 2 1 2 1 1 2 2 1 3 1 1 3 2 0 4 1 0 4 2 1 5 1 1 5 2 1
Si nota che non risultano giustamente coordinati due nodi, il numero 4 in direzione 1 e il numero 3 in direzione 2.
