Description
The objective of this model is to allocate aircrafts to routes to maximize
the expected profit when traffic demand is uncertain. Three different
formulations are presented:
the original lambda formulation
a stochastic equivalent with sampling
a stochastic equivalent with all scenarios
Large Model of Type : LP
Category : GAMS Model library
Main file : airsp.gms
$title Aircraft allocation - stochastic Optimization (AIRSP,SEQ=189)
$onText
The objective of this model is to allocate aircrafts to routes to maximize
the expected profit when traffic demand is uncertain. Three different
formulations are presented:
* the original lambda formulation
* a stochastic equivalent with sampling
* a stochastic equivalent with all scenarios
Dantzig, G B, Chapter 28. In Linear Programming and Extensions.
Princeton University Press, Princeton, New Jersey, 1963.
Keywords: linear programming, stochastic programming, aircraft allocation, routing
$offText
Set
i 'aircraft types and unassigned passengers' / a, b, c, d /
j 'assigned and unassigned routes' / route-1*route-5 /
h 'demand states' / 1*5 /
ss 'nodes' / s1*s1000 /
s(ss) 'actual ord temp nodes'
ij(i,j) 'possible assignments'
jh(j,h) 'possible demand states';
Alias (h,hp,h1,h2,h3,h4,h5);
Table dd(j,h) 'demand distribution on route j'
1 2 3 4 5
route-1 200 220 250 270 300
route-2 50 150
route-3 140 160 180 200 220
route-4 10 50 80 100 340
route-5 580 600 620 ;
Table lambda(j,h) 'probability of demand state h on route j'
1 2 3 4 5
route-1 .2 .05 .35 .2 .2
route-2 .3 .7
route-3 .1 .2 .4 .2 .1
route-4 .2 .2 .3 .2 .1
route-5 .1 .8 .1 ;
Table c(i,j) 'costs per aircraft (1000s)'
route-1 route-2 route-3 route-4 route-5
a 18 21 18 16 10
b 15 16 14 9
c 10 9 6
d 17 16 17 15 10;
Table p(i,j) 'passenger capacity of aircraft i on route j'
route-1 route-2 route-3 route-4 route-5
a 16 15 28 23 81
b 10 14 15 57
c 5 7 29
d 9 11 22 17 55;
Parameter
aa(i) 'aircraft availability' / a 10, b 19, c 25, d 15 /
k(j) 'revenue lost (1000 per 100 bumped)' / (route-1,route-2) 13, (route-3,route-4) 7, route-5 1 /
ed(j) 'expected demand'
deltb(j,h) 'incremental demand'
gamma(j,h) 'probability of demand segment'
drand(j,ss) 'sampled demand'
sample(j) 'sampled mean'
num 'temp value'
prob(ss) 'scenario probability'
probxx 'temp probability value';
ij(i,j) = p(i,j);
jh(j,h) = lambda(j,h);
ed(j) = sum(h, lambda(j,h)*dd(j,h));
deltb(jh(j,h)) = dd(j,h) - dd(j,h-1);
gamma(j,h) = sum(hp$(ord(hp) >= ord(h)), lambda(j,hp));
display deltb, gamma, ed;
Positive Variable
x(i,j) 'number of aircraft type i assigned to route j'
z(j) 'allocated capacity'
bh(j,h) 'passengers bumped'
bs(j,ss) 'passengers bumped';
Variable
phi 'total expected costs'
oc 'operating cost';
Equation
ab(i) 'aircraft balance'
cb(j) 'capacity balance'
dbh(j,h) 'demand balance'
dbs(j,ss) 'demand balance'
ocd 'operating cost definition'
objh 'objective function'
objs 'objective function';
ab(i).. sum(ij(i,j), x(ij)) =l= aa(i);
cb(j).. z(j) =e= sum(ij(i,j), p(ij)*x(ij));
dbh(j,h).. dd(j,h) - bh(j,h) =l= z(j);
dbs(j,s).. drand(j,s) - bs(j,s) =l= z(j);
ocd.. oc =e= sum((i,j), c(i,j)*x(i,j));
objh .. phi =e= oc + sum(j, k(j)*sum(jh(j,h), lambda(j,h)*bh(j,h)));
objs.. phi =e= oc + sum(j, k(j)*sum(s, prob(s)*bs(j,s)));
Model
alloch 'aircraft allocation' / ab, cb, dbh, ocd, objh /
allocs 'aircraft allocation' / ab, cb, dbs, ocd, objs /;
option limCol = 0, limRow = 0, solPrint = off;
Parameter rep 'quick report';
solve alloch minimizing phi using lp;
rep(i,j,'alloch') = x.l(i,j);
rep('ev',' ','alloch') = phi.l;
* set up a sample of some size
s(ss) = (ord(ss) <= 100);
loop((j,s),
num = uniform(0,1);
drand(j,s) = sum(jh(j,h)$(num < gamma(jh)), deltb(j,h));
);
prob(s) = 1/card(s);
sample(j) = sum(s, drand(j,s))/card(s);
display sample;
solve allocs minimizing phi using lp;
rep(i,j,'allocs') = x.l(i,j);
rep('ev',' ','allocs') = phi.l;
* enumerate all scenarios
prob(s) = 0;
s(ss) = no;
s('s1') = yes;
loop((h1,h2,h3,h4,h5),
probxx = lambda('route-1',h1)
* lambda('route-2',h2)
* lambda('route-3',h3)
* lambda('route-4',h4)
* lambda('route-5',h5);
if(probxx,
drand('route-1',s) = dd('route-1',h1);
drand('route-2',s) = dd('route-2',h2);
drand('route-3',s) = dd('route-3',h3);
drand('route-4',s) = dd('route-4',h4);
drand('route-5',s) = dd('route-5',h5);
prob(s) = probxx;
* s(ss) = s(ss-1) this looks nice but is very slow
s(ss+1)$s(ss) = yes;
s(ss-1)$s(ss) = no;
);
);
s(ss) = prob(ss);
solve allocs minimizing phi using lp;
rep(i,j,'allocss') = x.l(i,j);
rep('ev',' ','allocss') = phi.l;
display rep;