airsp.gms : Aircraft Allocation

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


Reference

  • Dantzig, G B, Chapter 28. In Linear Programming and Extensions. Princeton University Press, Princeton, New Jersey, 1963.

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;