cargonet.gms : Cargo network scheduling with stochastic transportation demand

Description

Mulvey and Ruszczynski provide a two stage network problem for
scheduling cargo transportation. The flight schedule is completely determined
in stage one, and the amounts of cargo to be shipped are uncertain.
The recourse actions are to determine which cargo to place on which flights.
Transshipment, getting cargo from node m to node n by more than one
flight on more than one route, is allowed.

In the following example we use a four node network, with node airports
A, B, C and E. All flights have two legs. That is, including the airport of
origin, there are three airports in each flight. No direct legs are allowed
between A and E, but all other possibilities are allowed.

J. M. Mulvey and A. Ruszczynski. A new scenario decomposition
method for large-scale stochastic optimization. Operations Research,
43(3),477-490, May-June 1995.

Ariyawansa, K A, and Felt, A J, On a New Collection of Stochastic
Linear Programming Test Problems, INFORMS Journal on Computing 16(3),
291-299, 2004.


Large Model of Type : SP


Category : GAMS EMP library


Main file : cargonet.gms

$title Cargo network scheduling with stochastic transportation demand (CARGONET,SEQ=90)

$onText
Mulvey and Ruszczynski provide a two stage network problem for
scheduling cargo transportation. The flight schedule is completely determined
in stage one, and the amounts of cargo to be shipped are uncertain.
The recourse actions are to determine which cargo to place on which flights.
Transshipment, getting cargo from node m to node n by more than one
flight on more than one route, is allowed.

In the following example we use a four node network, with node airports
A, B, C and E. All flights have two legs. That is, including the airport of
origin, there are three airports in each flight. No direct legs are allowed
between A and E, but all other possibilities are allowed.

J. M. Mulvey and A. Ruszczynski. A new scenario decomposition
method for large-scale stochastic optimization. Operations Research,
43(3),477-490, May-June 1995.

Ariyawansa, K A, and Felt, A J, On a New Collection of Stochastic
Linear Programming Test Problems, INFORMS Journal on Computing 16(3),
291-299, 2004.
$offText


Sets
   n  nodes      / A, B, C, E /
   r  routes     / r1*r26 /
   i  position   / i1*i3 /
   a  aircrafts  / type0*type1 /;

Alias (n,n0,n1,n2,n3,k), (i,j);

Set DataRoutes(n,n,n) /
   A.B.A, A.B.E, A.B.C, A.C.A, A.C.E, A.C.B
   B.A.B, B.A.C, B.C.A, B.C.B, B.C.E, B.E.B, B.E.C
   C.A.C, C.A.B, C.B.C, C.B.A, C.B.E, C.E.C, C.E.B
   E.C.E, E.C.B, E.C.A, E.B.E, E.B.C, E.B.A /

Sets
   route(r,i,n)  yes if node n is on position i on route r
   vFirst(n,r)   routes with initial node n
   vLast(n,r)    routes with last node n
   vLand(n,r)    routes with landing airport n
   W(n,r)        routes containing node n
   U(n1,n2,r)    routes containing n1 followed by n2
   Udom(n1,n2)   yes if n1 is followed by n2 on any arbitrary route
   OD(n1,n2)     origin-destination pairs of nodes with transportation demand;

scalar nr /1/;
loop(DataRoutes(n1,n2,n3),
   loop(r$(ord(r)=nr), route(r,'i1',n1) = yes; route(r,'i2',n2) = yes; route(r,'i3',n3) = yes);
   nr = nr+1;
);

vFirst(n,r) = route(r,'i1',n);
vLast(n,r) = route(r,'i3',n);
vLand(n,r) = (route(r,'i2',n) or route(r,'i3',n));

option W<route;

loop(r,
   loop(i,
      loop(j$(ord(j)>ord(i)), U(n1,n2,r)$(route(r,i,n1) and route(r,j,n2)) = yes)
   )
);
option Udom<U;

OD(n1,n2) = not sameas(n1,n2);

display route, vFirst, vLast, vLand, W, U, Udom, OD;

Parameters
   b(n1,n2)  demand of shipment between nodes
   c(a)      cost of a flight hour with type a
   q         unit cargo cost for loading and unloading an aircraft / 1 /
   p         unit penalty for undelivered cargo / 1300 /
   sigma(n)  maximum number of landings allowed in n / #n 25 /
   d(a)      maximum payload of an aircraft type a
   hmax(a)   maximum flying hours for type a
   hmin(a)   minimum flying hours for type a
   f(n1,n2)  minimum number of direct flights between nodes / #n1.#n2 0 /
   h(r,a)    flight time on route r with type a;

table b(n1,n2) origin-destination demand
       A     B     C     E
   A         5     8     4
   B   4.5         6.7   4.2
   C   10.1  8.3         12.2
   E   3.2   5.3   7.2       ;

Table aData(a,*)
           payload   cost   maxhours   minhours
   type0   8         5      480        0
   type1   6         4      240        0       ;

c(a) = aData(a,'cost');
d(a) = aData(a,'payload');
hmax(a) = aData(a,'maxhours');
hmin(a) = aData(a,'minhours');

Table flightTime(a,n,n)
           A   B   C   E
   type0.A     5   7
   type0.B         4   8
   type0.C             5
   type1.A     6   8.4
   type1.B         4.8 9.6
   type1.C             6   ;

h(r,a)=sum((route(r,i,n1),n2)$(route(r,i+1,n2)), flightTime(a,n1,n2)+flightTime(a,n2,n1));

display b,c,d,hmax,hmin,h;

Variables
   X(r,a)           number of aircrafts of type a on route r
   DIRECT(r,n1,n2)  amount of cargo delivered directly between nodes on route r
   T(r,n1,k,n2)     amount of cargo moving from n1 to n2 via transshipment node k on route r (n1 and k are part of route r)
   S(r,k,n2)        amount of transshipment cargo moved from transshipment node k to n2 on route r
   Y(n1,n2)         undelivered cargo between n1 and n2
   Z(r,i)           unused capacity on route r on flight from i to i+1
   OBJ              objective function value;

Positive Variables DIRECT,T,S,Y,Z;
Integer Variables X;

Equations
   objFct                    objective function
   minFlightReq(n1,n2)       minimum flight requirements
   landLim(n)                maximum landing limits
   cyclic(a,n)               end round in same state as it started
   timeLimLow(a)             lower time limit
   timeLimUp(a)              upper time limit
   demand(n1,n2)             transportation demand
   transBal(k,n2)            balance of transshipments wind up at n2 via transshipment node k
   matBal(n0,r)              material balance at initial node of route r
   payloadBal(r,i,n1)        payload balance for remaining nodes;

objFct..                     OBJ =e=   sum((r,a), c(a)*h(r,a)*X(r,a))
                                     + sum((r,U(n1,n2,r)), DIRECT(r,n1,n2) + S(r,n1,n2))*q
                                     + sum((r,U(n1,k,r),n2)$(not W(n2,r)), T(r,n1,k,n2))*q
                                     + sum(OD(n1,n2), Y(n1,n2)*p);

minFlightReq(Udom(n1,n2))..  sum((a,U(Udom,r)), X(r,a)) =g= f(Udom);

landLim(n)..                 sum((a,vLand(n,r)), X(r,a)) =l= sigma(n);

cyclic(a,n)..                sum(vFirst(n,r), X(r,a)) =e= sum(vLast(n,r), X(r,a));

timeLimLow(a)..              sum(r, x(r,a)*h(r,a)) =g= hmin(a);

timeLimUp(a)..               sum(r, x(r,a)*h(r,a)) =l= hmax(a);

demand(OD(n1,n2))..          sum(U(n1,n2,r), DIRECT(r,n1,n2))
                           + sum(U(n1,k,r)$(not W(n2,r)), T(r,n1,k,n2)) + Y(n1,n2) =g= b(n1,n2);

transBal(n1,k)..             sum((r,U(n0,n1,r))$(not W(k,r)), T(r,n0,n1,k)) =e= sum(U(n1,k,r), S(r,n1,k));

matBal(vFirst(n0,r))..       sum(U(n0,n1,r), DIRECT(r,n0,n1) + S(r,n0,n1))
                           + sum((U(n0,n1,r),k)$(not W(k,r)), T(r,n0,n1,k)) =e= sum(a, d(a)*X(r,a)) - Z(r,'i1');

payloadBal(route(r,i,n1))$(1<ord(i) and ord(i)<card(i))..
                             sum(U(n1,n2,r), DIRECT(r,n1,n2) + S(r,n1,n2))
                           + sum((U(n1,n2,r),k)$(not W(k,r)), T(r,n1,n2,k))
                           - sum(U(n0,n1,r), DIRECT(r,n0,n1) + S(r,n0,n1))
                           - sum((U(n0,n1,r),k)$(not W(k,r)), T(r,n0,n1,k)) =e= Z(r,i-1) - Z(r,i);

model cargo /all/;

Solve cargo using mip minimizing OBJ ;

file emp / '%emp.info%' /; put emp '* problem %gams.i%'/;
$if not set instance $set instance 16
$goTo i%instance%

$label i16
$onPut
randvar b('A','B') discrete   0.5   4.5     0.5   5.5
randvar b('A','C') discrete   0.25  6.8     0.25  7.6     0.25  8.4     0.25  9.2
randvar b('A','E') discrete   0.5   3.6     0.5   4.4
$offPut
$goTo continue

$label i512
$onPut
randvar b('A','B') discrete   0.5   4.5     0.5   5.5
randvar b('A','C') discrete   0.25  6.8     0.25  7.6     0.25  8.4     0.25  9.2
randvar b('A','E') discrete   0.5   3.6     0.5   4.4
randvar b('B','A') discrete   0.5   4.05    0.5   4.95
randvar b('B','C') discrete   0.25  5.695   0.25  6.365   0.25  7.035   0.25  7.705
randvar b('B','E') discrete   0.5   3.78    0.5   4.62
randvar b('C','A') discrete   0.5   9.09    0.5  11.11
$offPut
$goTo continue

$label i32768
$onPut
randvar b('B','A') discrete   0.5   4.05    0.5   4.95
randvar b('B','C') discrete   0.25  5.695   0.25  6.365   0.25  7.035   0.25  7.705
randvar b('B','E') discrete   0.5   3.78    0.5   4.62
randvar b('C','A') discrete   0.5   9.09    0.5  11.11
randvar b('C','B') discrete   0.5   7.47    0.5   9.13
randvar b('C','E') discrete   0.5  10.98    0.5  13.42
randvar b('E','A') discrete   0.5   2.88    0.5   3.52
randvar b('E','B') discrete   0.5   4.77    0.5   5.83
randvar b('E','C') discrete   0.25  6.12    0.25  6.84    0.25  7.56    0.25  8.28
$offPut

$label continue
putclose emp 'stage 2 b Y T S Z DIRECT demand payloadbal matbal transBal';

Set scen Scenarios / sc1*sc%instance% /;
Parameter
   sc_b(scen,n1,n2)  demand by scenario
   sc_OBJ(scen)      number of aircrafts of type a on route r by scenario
   SC_Y(scen,n1,n2)   undelivered cargo between n1 and n2 by scenario;

Set dict / scen     .scenario. ''
           b        .randvar . sc_b
           OBJ      .level   . sc_OBJ
           Y        .level   . sc_Y   /;

option optcr=0.1;
solve cargo min OBJ use emp scenario dict;

display sc_b, sc_OBJ, sc_Y;