tas.mod

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

/* TAS, Tail Assignment Problem */

/* Written in GNU MathProg by Andrew Makhorin <[e-mail]> */

/* The Tail Assignment Problem (TAS) is to construct rosters for a set
   of aircrafts (tails), which cover all flights for a given scheduling
   period.

   This model includes only flight connection constraints while other
   constraints (for example, maintenance constraints) are ignored. Such
   simplification allows using a single commodity network to model the
   problem, where commodity corresponds to the set of aircrafts.

   Nodes of the network are activities. They include all flights plus
   two dummy nodes (activities): source node, s, corresponding to
   initial activity of each aircraft, and sink node t, corresponding to
   final activity of each aircraft. Arc v->v' exists in the network if
   and only if the same aircraft is able to operate activity v and then
   immediately activity v'. In partucular, arcs s->f and f->t exist for
   all flights f. Arcs f->f', where f and f' are some flights, exist
   only if the connection time (which is the difference between the
   departure time of f' and the arrival time of f) is not less than a
   given minimal connection time.

   Reference:
   M. Groenkvist, "The Tail Assignment Problem," Dept. of Comp. Sci.
   and Eng., Chalmers University of Technology and Goeteborg University,
   Goeteborg, Sweden, August 2005. */

########################################################################

param nf, integer, > 0;
/* number of flights */

set F := 1..nf;
/* set of flights (for a given period from timetable) */

param hub{f in F}, in {1, 2};
/* hub[f] = 1: Sheremetyevo-1
   hub[f] = 2: Sheremetyevo-2 */

param dest{f in F}, symbolic;
/* destination airport (IATA code) */

param fno1{f in F}, integer;
/* first leg flight number */

param dep1{f in F}, integer, >= 0;
/* departure time from Sheremetyevo airport, in minutes */

check{f in F: f < nf}: dep1[f] <= dep1[f+1];
/* all flights must be ordered by ascending of the departure time */

param arr1{f in F}, integer, >= 0;
/* arrival time to destination airport, in minutes */

param fno2{f in F}, integer;
/* second leg flight number */

param dep2{f in F}, integer, >= 0;
/* departure time from destination airport, in minutes */

param arr2{f in F}, integer, >= 0;
/* arrival time to Sheremetyevo airport, in minutes */

param mct1, integer, >= 0, default 80;
/* minimal connection time (within SVO1 or SVO2), in minutes */

param mct2, integer, >= 0, default 150;
/* minimal connection time (between SVO1 and SVO2), in minutes */

set E := setof{f in F, ff in F: arr2[f] + (if hub[f] = hub[ff] then
   mct1 else mct2) <= dep1[ff]} (f, ff);
/* connection network; arc f->ff is in E, iff the same aircraft can be
   assigned to flight f and then immediately to flight ff */

var s{f in F}, >= 0;
/* s[f] is a flow from source node to node f */

var x{(f,ff) in E}, >= 0;
/* x[f,ff] is a flow from node f to node ff */

var t{f in F}, >= 0;
/* t[f] is a flow from node f to sink node */

s.t. into{f in F}: s[f] + sum{(ff,f) in E} x[ff,f] = 1;
/* exactly one aircraft must come into each node f */

s.t. from{f in F}: t[f] + sum{(f,ff) in E} x[f,ff] = 1;
/* exactly one aircraft must come from each node f */

minimize obj: sum{f in F} s[f];
/* minimize the number aircrafts sufficient to cover all flights */

solve;

########################################################################

param na := floor(sum{f in F} s[f] + .5);
/* minimal number of aircrafts found */

printf "At least %d aircrafts needed\n", na;

set A := 1..na;
/* set of aircrafts */

printf "Building rosters...\n";

param tail{f in F}, in A, :=
/* tail[f] is the number of an aircraft assigned to flight f */

   if f = 1 then 1
   /* assign aircraft 1 to the earliest flight */

   else if s[f] >= 0.9 then (max{ff in 1..f-1} tail[ff]) + 1
   /* if f is the first flight in a roster, assign to it a next
      aircraft */

   else sum{(ff,f) in E} tail[ff] * (if x[ff,f] >= 0.9 then 1);
   /* otherwise, assign to flight f the same aircraft, which is
      assigned to a preceding flight in the roster */

########################################################################

param file, symbolic, default "tas.ps";
/* file to output the assignment chart in postscript format */

param title, symbolic, default "(no title)";
/* chart title */

param left, default 25;
/* left margin, in mm */

param top, default 25;
/* top margin, in mm */

param right, default 20;
/* right margin, in mm */

param bottom, default 15;
/* bottom margin, in mm */

param sx := 297 - left - right;
/* chart area horizontal size, in mm */

param sy := 210 - top - bottom;
/* chart area vertical size, in mm */

param gap, default sy / (na - 1);
/* gap between rosters, in mm */

printf "Writing assignment chart to %s...\n", file;

printf "%%!PS-Adobe-3.0\n" > file;
printf "%%%%Title: Tail Assignment Chart\n" >> file;
printf "%%%%Creator: GLPK MathProg\n" >> file;
printf "%%%%BoundingBox: 0 0 595 842\n" >> file;
printf "%%%%EndComments\n" >> file;
printf "<</PageSize [595 842]>> setpagedevice\n" >> file;
printf "72 25.4 div dup scale\n" >> file;
printf "210 %.3f sub %.3f translate\n", bottom, left >> file;
printf "90 rotate\n" >> file;

printf "/HelveticaBold findfont 5 scalefont setfont\n" >> file;
printf "%.3f %.3f moveto (%s) dup show\n", 0, sy + 5, title >> file;

param period := floor((max{f in F} arr2[f]) / 60. + .5);
/* period duration, in hours */

/* vertical bars */
printf ".8 .8 .8 setrgbcolor\n" >> file;
for {tt in 0..period}
{  printf "%s setlinewidth\n",
      if tt mod 24 = 0 then ".5" else "0" >> file;
   printf "newpath %.3f %.3f moveto %.3f %.3f lineto stroke\n",
      tt * (sx / period), 0, tt * (sx / period),
      sy + (if tt mod 24 = 0 then 2) >> file;
}

/* rosters */
for {a in A}
{  printf "0 0 0 setrgbcolor\n" >> file;
   printf "0 setlinewidth\n" >> file;
   printf "newpath %.3f %.3f moveto %.3f %.3f lineto stroke\n",
      0, sy - gap * (a - 1), sx, sy - gap * (a - 1) >> file;
   printf "/Dingbats findfont 4 scalefont setfont\n" >> file;
   printf "%.3f %.3f moveto <28> dup show\n",
      -4, sy - gap * (a - 1) - 1.4, a >> file;
   printf "/Helvetica findfont 3 scalefont setfont\n" >> file;
   printf "%.3f %.3f moveto (%2d) dup show\n",
      -9, sy - gap * (a - 1) - 1.2, a >> file;
   for {f in F: tail[f] == a}
   {  printf "0 0 %s setrgbcolor\n",
         if hub[f] = 1 then "0" else ".8" >> file;
      printf "1 setlinewidth\n" >> file;
      printf "newpath %.3f %.3f moveto %.3f %.3f lineto stroke\n",
         dep1[f] / 60 * (sx / period), sy - gap * (a - 1),
         arr2[f] / 60 * (sx / period), sy - gap * (a - 1) >> file;
      printf "/Helvetica findfont 1.8 scalefont setfont\n" >> file;
      printf "%.3f %.3f moveto (%02d:%02d %s) dup show\n",
         dep1[f] / 60 * (sx / period), sy - gap * (a - 1) + .8,
         (dep1[f] mod 1440) div 60, (dep1[f] mod 1440) mod 60,
         dest[f] >> file;
      printf "%.3f %.3f moveto (%d %02d:%02d) dup show\n",
         dep1[f] / 60 * (sx / period), sy - gap * (a - 1) - 2.1,
         fno1[f],
         (arr2[f] mod 1440) div 60, (arr2[f] mod 1440) mod 60 >> file;
   }
}

printf "showpage\n" >> file;
printf "%%%%EOF\n" >> file;

########################################################################

data;

param title := "Tu-154 [from 2008-08-18 to 2008-08-24]";

param nf := 261;

param : hub dest fno1 dep1  arr1  fno2 dep2  arr2 :=
      1  1  IKT  743   195   520  744   610   970
      2  1  OMS  815   205   405  816   485   700
      3  1  CEK  897   205   360  898   430   595
      4  1  KRR  763   260   400  764   480   610
      5  2  SIP  133   280   420  134   500   620
      6  2  BUD  131   290   450  132   520   675
      7  1  AAQ  701   305   440  702   510   640
      8  1  MRV  785   310   440  786   520   650
      9  2  WAW  101   355   475  102   540   660
     10  2  GYD  147   370   550  148   675   860
     11  1  AER  869   385   530  870   655   795
     12  1  KRR  765   430   560  766   630   760
     13  1  AAQ  703   520   660  704   740   850
     14  1  LED  845   530   620  846   690   775
     15  1  KRR  767   540   675  768   765   895
     16  2  KBP  183   665   760  184   850   940
     17  1  MRV  787   755   905  788   985  1135
     18  1  KRR  771   810   940  772  1030  1165
     19  1  LED  849   825   900  850   960  1095
     20  2  IST  209   880  1050  210  1120  1280
     21  1  AER  873   885  1030  874  1760  1900
     22  1  ASF  711   995  1145  712  1640  1795