/* TAS, Tail Assignment Problem */
/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
/* 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
23 2 ULN 563 995 1335 564 1415 1815
24 2 OTP 151 1020 1175 152 1800 1940
25 2 BEY 509 1025 1265 510 1350 1580
26 2 OSL 211 1060 1220 212 1860 2015
27 1 IKT 739 1085 1420 740 1510 1870
28 1 KRR 773 1095 1240 774 1620 1765
29 1 SGC 877 1120 1315 878 1395 1625
30 1 LED 857 1150 1230 858 1610 1690
31 1 CEK 899 1230 1385 900 1455 1620
32 1 PEE 821 1235 1390 822 1450 1600
33 2 TBS 197 1240 1405 198 1560 1715
34 1 UFA 891 1275 1405 892 1475 1610
35 1 KJA 781 1300 1570 782 1680 1990
36 1 IKT 743 1635 1960 744 2050 2410
37 1 OMS 815 1645 1845 816 1925 2140
38 1 CEK 897 1645 1800 898 1870 2035
39 1 KRR 763 1700 1840 764 1920 2050
40 2 SIP 133 1720 1860 134 1940 2060
41 2 BUD 131 1730 1890 132 1960 2115
42 1 AAQ 701 1745 1880 702 1950 2080
43 1 MRV 785 1750 1880 786 1960 2090
44 2 WAW 101 1795 1915 102 1980 2100
45 2 GYD 147 1810 1990 148 2115 2300
46 1 AER 869 1825 1970 870 2095 2235
47 2 EVN 193 1850 2030 194 2105 2275
48 1 KRR 765 1870 2000 766 2070 2200
49 1 AAQ 703 1960 2100 704 2180 2290
50 1 LED 845 1970 2060 846 2130 2215
51 1 KRR 767 1980 2115 768 2205 2335
52 2 KBP 183 2105 2200 184 2290 2380
53 1 MRV 787 2195 2345 788 2425 2575
54 1 KRR 771 2250 2380 772 2470 2605
55 1 LED 849 2265 2340 850 2400 2535
56 2 IST 209 2320 2490 210 2560 2720
57 1 AER 873 2325 2470 874 3200 3340
58 2 ULN 563 2435 2775 564 2855 3255
59 1 ASF 711 2435 2585 712 3080 3235
60 2 DAM 517 2465 2705 518 2790 3020
61 2 OSL 211 2500 2660 212 3300 3455
62 2 KBP 185 2510 2610 186 3160 3250
63 1 IKT 739 2525 2860 740 2950 3310
64 1 KRR 773 2535 2680 774 3060 3205
65 1 SGC 877 2560 2755 878 2835 3065
66 1 LED 857 2590 2670 858 3050 3130
67 1 CEK 899 2670 2825 900 2895 3060
68 1 PEE 821 2675 2830 822 2890 3040
69 2 TBS 197 2680 2845 198 3000 3155
70 1 UFA 891 2715 2845 892 2915 3050
71 1 KJA 781 2740 3010 782 3120 3430
72 1 IKT 743 3075 3400 744 3490 3850
73 1 CEK 897 3085 3240 898 3310 3475
74 1 OMS 815 3085 3285 816 3365 3580
75 1 KRR 763 3140 3280 764 3360 3490
76 2 SIP 133 3160 3300 134 3380 3500
77 2 BUD 131 3170 3330 132 3400 3555
78 1 AAQ 701 3185 3320 702 3390 3520
79 1 MRV 785 3190 3320 786 3400 3530
80 2 WAW 101 3235 3355 102 3420 3540
81 2 FRU 181 3245 3495 182 3590 3860
82 2 GYD 147 3250 3430 148 3555 3740
83 1 AER 869 3265 3410 870 3535 3675
84 1 KRR 765 3310 3440 766 3510 3640
85 1 AAQ 703 3400 3540 704 3620 3730
86 1 LED 845 3410 3500 846 3570 3655
87 1 KRR 767 3420 3555 768 3645 3775
88 2 KBP 183 3545 3640 184 3730 3820
89 1 MRV 787 3635 3785 788 3865 4015
90 1 KRR 771 3690 3820 772 3910 4045
91 1 LED 849 3705 3780 850 3840 3975
92 2 IST 209 3760 3930 210 4000 4160
93 1 AER 873 3765 3910 874 4640 4780
94 2 ULN 563 3875 4215 564 4295 4695
95 1 ASF 711 3875 4025 712 4520 4675
96 2 OTP 151 3900 4055 152 4680 4820
97 2 BEY 509 3905 4145 510 4230 4460
98 2 OSL 211 3940 4100 212 4740 4895
99 2 KBP 185 3950 4050 186 4600 4690
100 1 IKT 739 3965 4300 740 4390 4750
101 1 KRR 773 3975 4120 774 4500 4645
102 1 SGC 877 4000 4195 878 4275 4505
103 1 LED 857 4030 4110 858 4490 4570
104 1 CEK 899 4110 4265 900 4335 4500
105 1 PEE 821 4115 4270 822 4330 4480
106 2 TBS 197 4120 4285 198 4440 4595
107 1 UFA 891 4155 4285 892 4355 4490
108 1 KJA 781 4180 4450 782 4560 4870
109 1 IKT 743 4515 4840 744 4930 5290
110 1 OMS 815 4525 4725 816 4805 5020
111 1 CEK 897 4525 4680 898 4750 4915
112 1 KRR 763 4580 4720 764 4800 4930
113 2 SIP 133 4600 4740 134 4820 4940
114 2 BUD 131 4610 4770 132 4840 4995
115 1 AAQ 701 4625 4760 702 4830 4960
116 1 MRV 785 4630 4760 786 4840 4970
117 2 WAW 101 4675 4795 102 4860 4980
118 2 GYD 147 4690 4870 148 4995 5180
119 1 AER 869 4705 4850 870 4975 5115
120 2 EVN 193 4730 4910 194 4985 5155
121 1 KRR 765 4750 4880 766 4950 5080
122 1 AAQ 703 4840 4980 704 5060 5170
123 1 LED 845 4850 4940 846 5010 5095
124 1 KRR 767 4860 4995 768 5085 5215
125 2 KBP 183 4985 5080 184 5170 5260
126 1 MRV 787 5075 5225 788 5305 5455
127 1 KRR 771 5130 5260 772 5350 5485
128 1 LED 849 5145 5220 850 5280 5415
129 2 IST 209 5200 5370 210 5440 5600
130 1 AER 873 5205 5350 874 6080 6220
131 1 ASF 711 5315 5465 712 5960 6115
132 2 ULN 563 5315 5655 564 5735 6135
133 2 DAM 517 5345 5585 518 5670 5900
134 2 OSL 211 5380 5540 212 6180 6335
135 2 KBP 185 5390 5490 186 6040 6130
136 1 IKT 739 5405 5740 740 5830 6190
137 1 KRR 773 5415 5560 774 5940 6085
138 1 SGC 877 5440 5635 878 5715 5945
139 1 LED 857 5470 5550 858 5930 6010
140 1 CEK 899 5550 5705 900 5775 5940
141 1 PEE 821 5555 5710 822 5770 5920
142 2 TBS 197 5560 5725 198 5880 6035
143 1 UFA 891 5595 5725 892 5795 5930
144 1 KJA 781 5620 5890 782 6000 6310
145 1 IKT 743 5955 6280 744 6370 6730
146 1 OMS 815 5965 6165 816 6245 6460
147 1 CEK 897 5965 6120 898 6190 6355
148 1 KRR 763 6020 6160 764 6240 6370
149 2 SIP 133 6040 6180 134 6260 6380
150 2 BUD 131 6050 6210 132 6280 6435
151 1 AAQ 701 6065 6200 702 6270 6400
152 1 MRV 785 6070 6200 786 6280 6410
153 2 WAW 101 6115 6235 102 6300 6420
154 2 FRU 181 6125 6375 182 6470 6740
155 2 GYD 147 6130 6310 148 6435 6620
156 1 AER 869 6145 6290 870 6415 6555
157 2 EVN 193 6170 6350 194 6425 6595
158 1 KRR 765 6190 6320 766 6390 6520
159 1 AAQ 703 6280 6420 704 6500 6610
160 1 LED 845 6290 6380 846 6450 6535
161 1 KRR 767 6300 6435 768 6525 6655
162 2 KBP 183 6425 6520 184 6610 6700
163 2 AYT 223 6500 6690 224 6750 6940
164 1 AER 867 6510 6660 868 6730 6880
165 1 MRV 787 6515 6665 788 6745 6895
166 1 KRR 771 6570 6700 772 6790 6925
167 1 LED 849 6585 6660 850 6720 6855
168 2 IST 209 6640 6810 210 6880 7040
169 1 AER 873 6645 6790 874 7520 7660
170 1 ASF 711 6755 6905 712 7400 7555
171 2 ULN 563 6755 7095 564 7175 7575
172 2 OTP 151 6780 6935 152 7560 7700
173 2 BEY 509 6785 7025 510 7110 7340
174 2 OSL 211 6820 6980 212 7620 7775
175 2 KBP 185 6830 6930 186 7480 7570
176 1 IKT 739 6845 7180 740 7270 7630
177 1 KRR 773 6855 7000 774 7380 7525
178 1 SGC 877 6880 7075 878 7155 7385
179 1 LED 857 6910 6990 858 7370 7450
180 1 CEK 899 6990 7145 900 7215 7380
181 1 PEE 821 6995 7150 822 7210 7360
182 2 TBS 197 7000 7165 198 7320 7475
183 1 UFA 891 7035 7165 892 7235 7370
184 1 KJA 781 7060 7330 782 7440 7750
185 1 IKT 743 7395 7720 744 7810 8170
186 1 CEK 897 7405 7560 898 7630 7795
187 1 KRR 763 7460 7600 764 7680 7810
188 2 SIP 133 7480 7620 134 7700 7820
189 2 BUD 131 7490 7650 132 7720 7875
190 1 AAQ 701 7505 7640 702 7710 7840
191 1 MRV 785 7510 7640 786 7720 7850
192 2 IST 207 7545 7720 208 7795 7985
193 2 WAW 101 7555 7675 102 7740 7860
194 2 GYD 147 7570 7750 148 7875 8060
195 1 AER 869 7585 7730 870 7855 7995
196 2 AYT 221 7610 7800 222 7895 8085
197 2 EVN 193 7610 7790 194 7865 8035
198 1 KRR 765 7630 7760 766 7830 7960
199 1 AAQ 703 7720 7860 704 7940 8050
200 1 LED 845 7730 7820 846 7890 7975
201 1 KRR 767 7740 7875 768 7965 8095
202 2 KBP 183 7865 7960 184 8050 8140
203 2 AYT 223 7940 8130 224 8190 8380
204 1 MRV 787 7955 8105 788 8185 8335
205 1 KRR 771 8010 8140 772 8230 8365
206 1 LED 849 8025 8100 850 8160 8295
207 2 IST 209 8080 8250 210 8320 8480
208 1 AER 873 8085 8230 874 8960 9100
209 1 ASF 711 8195 8345 712 8840 8995
210 2 ULN 563 8195 8535 564 8615 9015
211 1 KJA 779 8230 8500 780 8575 8870
212 2 OSL 211 8260 8420 212 9060 9215
213 2 KBP 185 8270 8370 186 8920 9010
214 1 IKT 739 8285 8620 740 8710 9070
215 1 KRR 773 8295 8440 774 8820 8965
216 1 SGC 877 8320 8515 878 8595 8825
217 1 LED 857 8350 8430 858 8810 8890
218 1 CEK 899 8430 8585 900 8655 8820
219 1 PEE 821 8435 8590 822 8650 8800
220 2 TBS 197 8440 8605 198 8760 8915
221 1 UFA 891 8475 8605 892 8675 8810
222 1 KJA 781 8500 8770 782 8880 9190
223 1 IKT 743 8835 9160 744 9250 9610
224 1 OMS 815 8845 9045 816 9125 9340
225 1 CEK 897 8845 9000 898 9070 9235
226 1 KRR 763 8900 9040 764 9120 9250
227 2 SIP 133 8920 9060 134 9140 9260
228 2 BUD 131 8930 9090 132 9160 9315
229 1 AAQ 701 8945 9080 702 9150 9280
230 1 MRV 785 8950 9080 786 9160 9290
231 2 IST 207 8985 9160 208 9235 9425
232 2 WAW 101 8995 9115 102 9180 9300
233 2 FRU 181 9005 9255 182 9350 9620
234 2 GYD 147 9010 9190 148 9315 9500
235 1 AER 869 9025 9170 870 9295 9435
236 2 EVN 193 9050 9230 194 9305 9475
237 1 KRR 765 9070 9200 766 9270 9400
238 1 AAQ 703 9160 9300 704 9380 9490
239 1 LED 845 9170 9260 846 9330 9415
240 1 KRR 767 9180 9315 768 9405 9535
241 2 KBP 183 9305 9400 184 9490 9580
242 2 AYT 223 9380 9570 224 9630 9820
243 1 MRV 787 9395 9545 788 9625 9775
244 1 KRR 771 9450 9580 772 9670 9805
245 1 LED 849 9465 9540 850 9600 9735
246 2 IST 209 9520 9690 210 9760 9920
247 1 AER 873 9525 9670 874 10400 10540
248 1 ASF 711 9635 9785 712 10280 10435
249 2 ULN 563 9635 9975 564 10055 10455
250 2 OTP 151 9660 9815 152 10440 10580
251 2 DAM 517 9665 9905 518 9990 10220
252 2 OSL 211 9700 9860 212 10500 10655
253 2 KBP 185 9710 9810 186 10360 10450
254 1 IKT 739 9725 10060 740 10150 10510
255 1 KRR 773 9735 9880 774 10260 10405
256 1 SGC 877 9760 9955 878 10035 10265
257 1 LED 857 9790 9870 858 10250 10330
258 1 CEK 899 9870 10025 900 10095 10260
259 1 PEE 821 9875 10030 822 10090 10240
260 1 UFA 891 9915 10045 892 10115 10250
261 1 KJA 781 9940 10210 782 10320 10630
;
end;
distrib
>
Fedora
>
13
>
i386
>
media
>
os
>
by-pkgid
>
f1e2bc5e1a8a784323c2a7a37d36f441
>
files
>
131
