diff -r d59bea55db9b -r c445c931472f examples/tas.mod --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/examples/tas.mod Mon Dec 06 13:09:21 2010 +0100 @@ -0,0 +1,486 @@ +/* TAS, Tail Assignment Problem */ + +/* Written in GNU MathProg by Andrew Makhorin */ + +/* 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 "<> 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;