1 /* TAS, Tail Assignment Problem */
3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
5 /* The Tail Assignment Problem (TAS) is to construct rosters for a set
6 of aircrafts (tails), which cover all flights for a given scheduling
9 This model includes only flight connection constraints while other
10 constraints (for example, maintenance constraints) are ignored. Such
11 simplification allows using a single commodity network to model the
12 problem, where commodity corresponds to the set of aircrafts.
14 Nodes of the network are activities. They include all flights plus
15 two dummy nodes (activities): source node, s, corresponding to
16 initial activity of each aircraft, and sink node t, corresponding to
17 final activity of each aircraft. Arc v->v' exists in the network if
18 and only if the same aircraft is able to operate activity v and then
19 immediately activity v'. In partucular, arcs s->f and f->t exist for
20 all flights f. Arcs f->f', where f and f' are some flights, exist
21 only if the connection time (which is the difference between the
22 departure time of f' and the arrival time of f) is not less than a
23 given minimal connection time.
26 M. Groenkvist, "The Tail Assignment Problem," Dept. of Comp. Sci.
27 and Eng., Chalmers University of Technology and Goeteborg University,
28 Goeteborg, Sweden, August 2005. */
30 ########################################################################
32 param nf, integer, > 0;
33 /* number of flights */
36 /* set of flights (for a given period from timetable) */
38 param hub{f in F}, in {1, 2};
39 /* hub[f] = 1: Sheremetyevo-1
40 hub[f] = 2: Sheremetyevo-2 */
42 param dest{f in F}, symbolic;
43 /* destination airport (IATA code) */
45 param fno1{f in F}, integer;
46 /* first leg flight number */
48 param dep1{f in F}, integer, >= 0;
49 /* departure time from Sheremetyevo airport, in minutes */
51 check{f in F: f < nf}: dep1[f] <= dep1[f+1];
52 /* all flights must be ordered by ascending of the departure time */
54 param arr1{f in F}, integer, >= 0;
55 /* arrival time to destination airport, in minutes */
57 param fno2{f in F}, integer;
58 /* second leg flight number */
60 param dep2{f in F}, integer, >= 0;
61 /* departure time from destination airport, in minutes */
63 param arr2{f in F}, integer, >= 0;
64 /* arrival time to Sheremetyevo airport, in minutes */
66 param mct1, integer, >= 0, default 80;
67 /* minimal connection time (within SVO1 or SVO2), in minutes */
69 param mct2, integer, >= 0, default 150;
70 /* minimal connection time (between SVO1 and SVO2), in minutes */
72 set E := setof{f in F, ff in F: arr2[f] + (if hub[f] = hub[ff] then
73 mct1 else mct2) <= dep1[ff]} (f, ff);
74 /* connection network; arc f->ff is in E, iff the same aircraft can be
75 assigned to flight f and then immediately to flight ff */
78 /* s[f] is a flow from source node to node f */
80 var x{(f,ff) in E}, >= 0;
81 /* x[f,ff] is a flow from node f to node ff */
84 /* t[f] is a flow from node f to sink node */
86 s.t. into{f in F}: s[f] + sum{(ff,f) in E} x[ff,f] = 1;
87 /* exactly one aircraft must come into each node f */
89 s.t. from{f in F}: t[f] + sum{(f,ff) in E} x[f,ff] = 1;
90 /* exactly one aircraft must come from each node f */
92 minimize obj: sum{f in F} s[f];
93 /* minimize the number aircrafts sufficient to cover all flights */
97 ########################################################################
99 param na := floor(sum{f in F} s[f] + .5);
100 /* minimal number of aircrafts found */
102 printf "At least %d aircrafts needed\n", na;
105 /* set of aircrafts */
107 printf "Building rosters...\n";
109 param tail{f in F}, in A, :=
110 /* tail[f] is the number of an aircraft assigned to flight f */
113 /* assign aircraft 1 to the earliest flight */
115 else if s[f] >= 0.9 then (max{ff in 1..f-1} tail[ff]) + 1
116 /* if f is the first flight in a roster, assign to it a next
119 else sum{(ff,f) in E} tail[ff] * (if x[ff,f] >= 0.9 then 1);
120 /* otherwise, assign to flight f the same aircraft, which is
121 assigned to a preceding flight in the roster */
123 ########################################################################
125 param file, symbolic, default "tas.ps";
126 /* file to output the assignment chart in postscript format */
128 param title, symbolic, default "(no title)";
131 param left, default 25;
132 /* left margin, in mm */
134 param top, default 25;
135 /* top margin, in mm */
137 param right, default 20;
138 /* right margin, in mm */
140 param bottom, default 15;
141 /* bottom margin, in mm */
143 param sx := 297 - left - right;
144 /* chart area horizontal size, in mm */
146 param sy := 210 - top - bottom;
147 /* chart area vertical size, in mm */
149 param gap, default sy / (na - 1);
150 /* gap between rosters, in mm */
152 printf "Writing assignment chart to %s...\n", file;
154 printf "%%!PS-Adobe-3.0\n" > file;
155 printf "%%%%Title: Tail Assignment Chart\n" >> file;
156 printf "%%%%Creator: GLPK MathProg\n" >> file;
157 printf "%%%%BoundingBox: 0 0 595 842\n" >> file;
158 printf "%%%%EndComments\n" >> file;
159 printf "<</PageSize [595 842]>> setpagedevice\n" >> file;
160 printf "72 25.4 div dup scale\n" >> file;
161 printf "210 %.3f sub %.3f translate\n", bottom, left >> file;
162 printf "90 rotate\n" >> file;
164 printf "/HelveticaBold findfont 5 scalefont setfont\n" >> file;
165 printf "%.3f %.3f moveto (%s) dup show\n", 0, sy + 5, title >> file;
167 param period := floor((max{f in F} arr2[f]) / 60. + .5);
168 /* period duration, in hours */
171 printf ".8 .8 .8 setrgbcolor\n" >> file;
172 for {tt in 0..period}
173 { printf "%s setlinewidth\n",
174 if tt mod 24 = 0 then ".5" else "0" >> file;
175 printf "newpath %.3f %.3f moveto %.3f %.3f lineto stroke\n",
176 tt * (sx / period), 0, tt * (sx / period),
177 sy + (if tt mod 24 = 0 then 2) >> file;
182 { printf "0 0 0 setrgbcolor\n" >> file;
183 printf "0 setlinewidth\n" >> file;
184 printf "newpath %.3f %.3f moveto %.3f %.3f lineto stroke\n",
185 0, sy - gap * (a - 1), sx, sy - gap * (a - 1) >> file;
186 printf "/Dingbats findfont 4 scalefont setfont\n" >> file;
187 printf "%.3f %.3f moveto <28> dup show\n",
188 -4, sy - gap * (a - 1) - 1.4, a >> file;
189 printf "/Helvetica findfont 3 scalefont setfont\n" >> file;
190 printf "%.3f %.3f moveto (%2d) dup show\n",
191 -9, sy - gap * (a - 1) - 1.2, a >> file;
192 for {f in F: tail[f] == a}
193 { printf "0 0 %s setrgbcolor\n",
194 if hub[f] = 1 then "0" else ".8" >> file;
195 printf "1 setlinewidth\n" >> file;
196 printf "newpath %.3f %.3f moveto %.3f %.3f lineto stroke\n",
197 dep1[f] / 60 * (sx / period), sy - gap * (a - 1),
198 arr2[f] / 60 * (sx / period), sy - gap * (a - 1) >> file;
199 printf "/Helvetica findfont 1.8 scalefont setfont\n" >> file;
200 printf "%.3f %.3f moveto (%02d:%02d %s) dup show\n",
201 dep1[f] / 60 * (sx / period), sy - gap * (a - 1) + .8,
202 (dep1[f] mod 1440) div 60, (dep1[f] mod 1440) mod 60,
204 printf "%.3f %.3f moveto (%d %02d:%02d) dup show\n",
205 dep1[f] / 60 * (sx / period), sy - gap * (a - 1) - 2.1,
207 (arr2[f] mod 1440) div 60, (arr2[f] mod 1440) mod 60 >> file;
211 printf "showpage\n" >> file;
212 printf "%%%%EOF\n" >> file;
214 ########################################################################
218 param title := "Tu-154 [from 2008-08-18 to 2008-08-24]";
222 param : hub dest fno1 dep1 arr1 fno2 dep2 arr2 :=
223 1 1 IKT 743 195 520 744 610 970
224 2 1 OMS 815 205 405 816 485 700
225 3 1 CEK 897 205 360 898 430 595
226 4 1 KRR 763 260 400 764 480 610
227 5 2 SIP 133 280 420 134 500 620
228 6 2 BUD 131 290 450 132 520 675
229 7 1 AAQ 701 305 440 702 510 640
230 8 1 MRV 785 310 440 786 520 650
231 9 2 WAW 101 355 475 102 540 660
232 10 2 GYD 147 370 550 148 675 860
233 11 1 AER 869 385 530 870 655 795
234 12 1 KRR 765 430 560 766 630 760
235 13 1 AAQ 703 520 660 704 740 850
236 14 1 LED 845 530 620 846 690 775
237 15 1 KRR 767 540 675 768 765 895
238 16 2 KBP 183 665 760 184 850 940
239 17 1 MRV 787 755 905 788 985 1135
240 18 1 KRR 771 810 940 772 1030 1165
241 19 1 LED 849 825 900 850 960 1095
242 20 2 IST 209 880 1050 210 1120 1280
243 21 1 AER 873 885 1030 874 1760 1900
244 22 1 ASF 711 995 1145 712 1640 1795
245 23 2 ULN 563 995 1335 564 1415 1815
246 24 2 OTP 151 1020 1175 152 1800 1940
247 25 2 BEY 509 1025 1265 510 1350 1580
248 26 2 OSL 211 1060 1220 212 1860 2015
249 27 1 IKT 739 1085 1420 740 1510 1870
250 28 1 KRR 773 1095 1240 774 1620 1765
251 29 1 SGC 877 1120 1315 878 1395 1625
252 30 1 LED 857 1150 1230 858 1610 1690
253 31 1 CEK 899 1230 1385 900 1455 1620
254 32 1 PEE 821 1235 1390 822 1450 1600
255 33 2 TBS 197 1240 1405 198 1560 1715
256 34 1 UFA 891 1275 1405 892 1475 1610
257 35 1 KJA 781 1300 1570 782 1680 1990
258 36 1 IKT 743 1635 1960 744 2050 2410
259 37 1 OMS 815 1645 1845 816 1925 2140
260 38 1 CEK 897 1645 1800 898 1870 2035
261 39 1 KRR 763 1700 1840 764 1920 2050
262 40 2 SIP 133 1720 1860 134 1940 2060
263 41 2 BUD 131 1730 1890 132 1960 2115
264 42 1 AAQ 701 1745 1880 702 1950 2080
265 43 1 MRV 785 1750 1880 786 1960 2090
266 44 2 WAW 101 1795 1915 102 1980 2100
267 45 2 GYD 147 1810 1990 148 2115 2300
268 46 1 AER 869 1825 1970 870 2095 2235
269 47 2 EVN 193 1850 2030 194 2105 2275
270 48 1 KRR 765 1870 2000 766 2070 2200
271 49 1 AAQ 703 1960 2100 704 2180 2290
272 50 1 LED 845 1970 2060 846 2130 2215
273 51 1 KRR 767 1980 2115 768 2205 2335
274 52 2 KBP 183 2105 2200 184 2290 2380
275 53 1 MRV 787 2195 2345 788 2425 2575
276 54 1 KRR 771 2250 2380 772 2470 2605
277 55 1 LED 849 2265 2340 850 2400 2535
278 56 2 IST 209 2320 2490 210 2560 2720
279 57 1 AER 873 2325 2470 874 3200 3340
280 58 2 ULN 563 2435 2775 564 2855 3255
281 59 1 ASF 711 2435 2585 712 3080 3235
282 60 2 DAM 517 2465 2705 518 2790 3020
283 61 2 OSL 211 2500 2660 212 3300 3455
284 62 2 KBP 185 2510 2610 186 3160 3250
285 63 1 IKT 739 2525 2860 740 2950 3310
286 64 1 KRR 773 2535 2680 774 3060 3205
287 65 1 SGC 877 2560 2755 878 2835 3065
288 66 1 LED 857 2590 2670 858 3050 3130
289 67 1 CEK 899 2670 2825 900 2895 3060
290 68 1 PEE 821 2675 2830 822 2890 3040
291 69 2 TBS 197 2680 2845 198 3000 3155
292 70 1 UFA 891 2715 2845 892 2915 3050
293 71 1 KJA 781 2740 3010 782 3120 3430
294 72 1 IKT 743 3075 3400 744 3490 3850
295 73 1 CEK 897 3085 3240 898 3310 3475
296 74 1 OMS 815 3085 3285 816 3365 3580
297 75 1 KRR 763 3140 3280 764 3360 3490
298 76 2 SIP 133 3160 3300 134 3380 3500
299 77 2 BUD 131 3170 3330 132 3400 3555
300 78 1 AAQ 701 3185 3320 702 3390 3520
301 79 1 MRV 785 3190 3320 786 3400 3530
302 80 2 WAW 101 3235 3355 102 3420 3540
303 81 2 FRU 181 3245 3495 182 3590 3860
304 82 2 GYD 147 3250 3430 148 3555 3740
305 83 1 AER 869 3265 3410 870 3535 3675
306 84 1 KRR 765 3310 3440 766 3510 3640
307 85 1 AAQ 703 3400 3540 704 3620 3730
308 86 1 LED 845 3410 3500 846 3570 3655
309 87 1 KRR 767 3420 3555 768 3645 3775
310 88 2 KBP 183 3545 3640 184 3730 3820
311 89 1 MRV 787 3635 3785 788 3865 4015
312 90 1 KRR 771 3690 3820 772 3910 4045
313 91 1 LED 849 3705 3780 850 3840 3975
314 92 2 IST 209 3760 3930 210 4000 4160
315 93 1 AER 873 3765 3910 874 4640 4780
316 94 2 ULN 563 3875 4215 564 4295 4695
317 95 1 ASF 711 3875 4025 712 4520 4675
318 96 2 OTP 151 3900 4055 152 4680 4820
319 97 2 BEY 509 3905 4145 510 4230 4460
320 98 2 OSL 211 3940 4100 212 4740 4895
321 99 2 KBP 185 3950 4050 186 4600 4690
322 100 1 IKT 739 3965 4300 740 4390 4750
323 101 1 KRR 773 3975 4120 774 4500 4645
324 102 1 SGC 877 4000 4195 878 4275 4505
325 103 1 LED 857 4030 4110 858 4490 4570
326 104 1 CEK 899 4110 4265 900 4335 4500
327 105 1 PEE 821 4115 4270 822 4330 4480
328 106 2 TBS 197 4120 4285 198 4440 4595
329 107 1 UFA 891 4155 4285 892 4355 4490
330 108 1 KJA 781 4180 4450 782 4560 4870
331 109 1 IKT 743 4515 4840 744 4930 5290
332 110 1 OMS 815 4525 4725 816 4805 5020
333 111 1 CEK 897 4525 4680 898 4750 4915
334 112 1 KRR 763 4580 4720 764 4800 4930
335 113 2 SIP 133 4600 4740 134 4820 4940
336 114 2 BUD 131 4610 4770 132 4840 4995
337 115 1 AAQ 701 4625 4760 702 4830 4960
338 116 1 MRV 785 4630 4760 786 4840 4970
339 117 2 WAW 101 4675 4795 102 4860 4980
340 118 2 GYD 147 4690 4870 148 4995 5180
341 119 1 AER 869 4705 4850 870 4975 5115
342 120 2 EVN 193 4730 4910 194 4985 5155
343 121 1 KRR 765 4750 4880 766 4950 5080
344 122 1 AAQ 703 4840 4980 704 5060 5170
345 123 1 LED 845 4850 4940 846 5010 5095
346 124 1 KRR 767 4860 4995 768 5085 5215
347 125 2 KBP 183 4985 5080 184 5170 5260
348 126 1 MRV 787 5075 5225 788 5305 5455
349 127 1 KRR 771 5130 5260 772 5350 5485
350 128 1 LED 849 5145 5220 850 5280 5415
351 129 2 IST 209 5200 5370 210 5440 5600
352 130 1 AER 873 5205 5350 874 6080 6220
353 131 1 ASF 711 5315 5465 712 5960 6115
354 132 2 ULN 563 5315 5655 564 5735 6135
355 133 2 DAM 517 5345 5585 518 5670 5900
356 134 2 OSL 211 5380 5540 212 6180 6335
357 135 2 KBP 185 5390 5490 186 6040 6130
358 136 1 IKT 739 5405 5740 740 5830 6190
359 137 1 KRR 773 5415 5560 774 5940 6085
360 138 1 SGC 877 5440 5635 878 5715 5945
361 139 1 LED 857 5470 5550 858 5930 6010
362 140 1 CEK 899 5550 5705 900 5775 5940
363 141 1 PEE 821 5555 5710 822 5770 5920
364 142 2 TBS 197 5560 5725 198 5880 6035
365 143 1 UFA 891 5595 5725 892 5795 5930
366 144 1 KJA 781 5620 5890 782 6000 6310
367 145 1 IKT 743 5955 6280 744 6370 6730
368 146 1 OMS 815 5965 6165 816 6245 6460
369 147 1 CEK 897 5965 6120 898 6190 6355
370 148 1 KRR 763 6020 6160 764 6240 6370
371 149 2 SIP 133 6040 6180 134 6260 6380
372 150 2 BUD 131 6050 6210 132 6280 6435
373 151 1 AAQ 701 6065 6200 702 6270 6400
374 152 1 MRV 785 6070 6200 786 6280 6410
375 153 2 WAW 101 6115 6235 102 6300 6420
376 154 2 FRU 181 6125 6375 182 6470 6740
377 155 2 GYD 147 6130 6310 148 6435 6620
378 156 1 AER 869 6145 6290 870 6415 6555
379 157 2 EVN 193 6170 6350 194 6425 6595
380 158 1 KRR 765 6190 6320 766 6390 6520
381 159 1 AAQ 703 6280 6420 704 6500 6610
382 160 1 LED 845 6290 6380 846 6450 6535
383 161 1 KRR 767 6300 6435 768 6525 6655
384 162 2 KBP 183 6425 6520 184 6610 6700
385 163 2 AYT 223 6500 6690 224 6750 6940
386 164 1 AER 867 6510 6660 868 6730 6880
387 165 1 MRV 787 6515 6665 788 6745 6895
388 166 1 KRR 771 6570 6700 772 6790 6925
389 167 1 LED 849 6585 6660 850 6720 6855
390 168 2 IST 209 6640 6810 210 6880 7040
391 169 1 AER 873 6645 6790 874 7520 7660
392 170 1 ASF 711 6755 6905 712 7400 7555
393 171 2 ULN 563 6755 7095 564 7175 7575
394 172 2 OTP 151 6780 6935 152 7560 7700
395 173 2 BEY 509 6785 7025 510 7110 7340
396 174 2 OSL 211 6820 6980 212 7620 7775
397 175 2 KBP 185 6830 6930 186 7480 7570
398 176 1 IKT 739 6845 7180 740 7270 7630
399 177 1 KRR 773 6855 7000 774 7380 7525
400 178 1 SGC 877 6880 7075 878 7155 7385
401 179 1 LED 857 6910 6990 858 7370 7450
402 180 1 CEK 899 6990 7145 900 7215 7380
403 181 1 PEE 821 6995 7150 822 7210 7360
404 182 2 TBS 197 7000 7165 198 7320 7475
405 183 1 UFA 891 7035 7165 892 7235 7370
406 184 1 KJA 781 7060 7330 782 7440 7750
407 185 1 IKT 743 7395 7720 744 7810 8170
408 186 1 CEK 897 7405 7560 898 7630 7795
409 187 1 KRR 763 7460 7600 764 7680 7810
410 188 2 SIP 133 7480 7620 134 7700 7820
411 189 2 BUD 131 7490 7650 132 7720 7875
412 190 1 AAQ 701 7505 7640 702 7710 7840
413 191 1 MRV 785 7510 7640 786 7720 7850
414 192 2 IST 207 7545 7720 208 7795 7985
415 193 2 WAW 101 7555 7675 102 7740 7860
416 194 2 GYD 147 7570 7750 148 7875 8060
417 195 1 AER 869 7585 7730 870 7855 7995
418 196 2 AYT 221 7610 7800 222 7895 8085
419 197 2 EVN 193 7610 7790 194 7865 8035
420 198 1 KRR 765 7630 7760 766 7830 7960
421 199 1 AAQ 703 7720 7860 704 7940 8050
422 200 1 LED 845 7730 7820 846 7890 7975
423 201 1 KRR 767 7740 7875 768 7965 8095
424 202 2 KBP 183 7865 7960 184 8050 8140
425 203 2 AYT 223 7940 8130 224 8190 8380
426 204 1 MRV 787 7955 8105 788 8185 8335
427 205 1 KRR 771 8010 8140 772 8230 8365
428 206 1 LED 849 8025 8100 850 8160 8295
429 207 2 IST 209 8080 8250 210 8320 8480
430 208 1 AER 873 8085 8230 874 8960 9100
431 209 1 ASF 711 8195 8345 712 8840 8995
432 210 2 ULN 563 8195 8535 564 8615 9015
433 211 1 KJA 779 8230 8500 780 8575 8870
434 212 2 OSL 211 8260 8420 212 9060 9215
435 213 2 KBP 185 8270 8370 186 8920 9010
436 214 1 IKT 739 8285 8620 740 8710 9070
437 215 1 KRR 773 8295 8440 774 8820 8965
438 216 1 SGC 877 8320 8515 878 8595 8825
439 217 1 LED 857 8350 8430 858 8810 8890
440 218 1 CEK 899 8430 8585 900 8655 8820
441 219 1 PEE 821 8435 8590 822 8650 8800
442 220 2 TBS 197 8440 8605 198 8760 8915
443 221 1 UFA 891 8475 8605 892 8675 8810
444 222 1 KJA 781 8500 8770 782 8880 9190
445 223 1 IKT 743 8835 9160 744 9250 9610
446 224 1 OMS 815 8845 9045 816 9125 9340
447 225 1 CEK 897 8845 9000 898 9070 9235
448 226 1 KRR 763 8900 9040 764 9120 9250
449 227 2 SIP 133 8920 9060 134 9140 9260
450 228 2 BUD 131 8930 9090 132 9160 9315
451 229 1 AAQ 701 8945 9080 702 9150 9280
452 230 1 MRV 785 8950 9080 786 9160 9290
453 231 2 IST 207 8985 9160 208 9235 9425
454 232 2 WAW 101 8995 9115 102 9180 9300
455 233 2 FRU 181 9005 9255 182 9350 9620
456 234 2 GYD 147 9010 9190 148 9315 9500
457 235 1 AER 869 9025 9170 870 9295 9435
458 236 2 EVN 193 9050 9230 194 9305 9475
459 237 1 KRR 765 9070 9200 766 9270 9400
460 238 1 AAQ 703 9160 9300 704 9380 9490
461 239 1 LED 845 9170 9260 846 9330 9415
462 240 1 KRR 767 9180 9315 768 9405 9535
463 241 2 KBP 183 9305 9400 184 9490 9580
464 242 2 AYT 223 9380 9570 224 9630 9820
465 243 1 MRV 787 9395 9545 788 9625 9775
466 244 1 KRR 771 9450 9580 772 9670 9805
467 245 1 LED 849 9465 9540 850 9600 9735
468 246 2 IST 209 9520 9690 210 9760 9920
469 247 1 AER 873 9525 9670 874 10400 10540
470 248 1 ASF 711 9635 9785 712 10280 10435
471 249 2 ULN 563 9635 9975 564 10055 10455
472 250 2 OTP 151 9660 9815 152 10440 10580
473 251 2 DAM 517 9665 9905 518 9990 10220
474 252 2 OSL 211 9700 9860 212 10500 10655
475 253 2 KBP 185 9710 9810 186 10360 10450
476 254 1 IKT 739 9725 10060 740 10150 10510
477 255 1 KRR 773 9735 9880 774 10260 10405
478 256 1 SGC 877 9760 9955 878 10035 10265
479 257 1 LED 857 9790 9870 858 10250 10330
480 258 1 CEK 899 9870 10025 900 10095 10260
481 259 1 PEE 821 9875 10030 822 10090 10240
482 260 1 UFA 891 9915 10045 892 10115 10250
483 261 1 KJA 781 9940 10210 782 10320 10630