1 # TRAIN, a model of railroad passenger car allocation
4 # Robert Fourer, David M. Gay and Brian W. Kernighan, "A Modeling Language
5 # for Mathematical Programming." Management Science 36 (1990) 519-554.
7 ### SCHEDULE SETS AND PARAMETERS ###
11 set links within {c1 in cities, c2 in cities: c1 <> c2};
13 # Set of cities, and set of intercity links
15 param last > 0 integer; # Number of time intervals in a day
17 set times := 1..last; # Set of time intervals in a day
20 {c1 in cities, t1 in times,
21 c2 in cities, t2 in times: (c1,c2) in links};
23 # Member (c1,t1,c2,t2) of this set represents
24 # a train that leaves city c1 at time t1
25 # and arrives in city c2 at time t2
27 ### DEMAND PARAMETERS ###
29 param section > 0 integer;
31 # Maximum number of cars in one section of a train
33 param demand {schedule} > 0;
35 # For each scheduled train:
36 # the smallest number of cars that
37 # can meet demand for the train
39 param low {(c1,t1,c2,t2) in schedule} := ceil(demand[c1,t1,c2,t2]);
41 # Minimum number of cars needed to meet demand
43 param high {(c1,t1,c2,t2) in schedule}
45 := max (2, min (ceil(2*demand[c1,t1,c2,t2]),
46 section*ceil(demand[c1,t1,c2,t2]/section) ));
48 # Maximum number of cars allowed on a train:
49 # 2 if demand is for less than one car;
50 # otherwise, lesser of
51 # number of cars needed to hold twice the demand, and
52 # number of cars in minimum number of sections needed
54 ### DISTANCE PARAMETERS ###
56 param dist_table {links} >= 0 default 0.0;
58 param distance {(c1,c2) in links} > 0
59 := if dist_table[c1,c2] > 0 then dist_table[c1,c2] else dist_table[c2,c1];
61 # Inter-city distances: distance[c1,c2] is miles
62 # between city c1 and city c2
66 var U 'cars stored' {cities,times} >= 0;
68 # u[c,t] is the number of unused cars stored
69 # at city c in the interval beginning at time t
71 var X 'cars in train' {schedule} >= 0;
73 # x[c1,t1,c2,t2] is the number of cars assigned to
74 # the scheduled train that leaves c1 at t1 and
80 sum {c in cities} U[c,last] +
81 sum {(c1,t1,c2,t2) in schedule: t2 < t1} X[c1,t1,c2,t2];
83 # Number of cars in the system:
84 # sum of unused cars and cars in trains during
85 # the last time interval of the day
88 sum {(c1,t1,c2,t2) in schedule} distance[c1,c2] * X[c1,t1,c2,t2];
90 # Total car-miles run by all scheduled trains in a day
94 account {c in cities, t in times}:
96 U[c,t] = U[c, if t > 1 then t-1 else last] +
98 sum {(c1,t1,c,t) in schedule} X[c1,t1,c,t] -
99 sum {(c,t,c2,t2) in schedule} X[c,t,c2,t2];
101 # For every city and time:
102 # unused cars in the present interval must equal
103 # unused cars in the previous interval,
104 # plus cars just arriving in trains,
105 # minus cars just leaving in trains
107 satisfy {(c1,t1,c2,t2) in schedule}:
109 low[c1,t1,c2,t2] <= X[c1,t1,c2,t2] <= high[c1,t1,c2,t2];
111 # For each scheduled train:
112 # number of cars must meet demand,
113 # but must not be so great that unnecessary
120 set cities := BO NY PH WA ;
122 set links := (BO,NY) (NY,PH) (PH,WA)
123 (NY,BO) (PH,NY) (WA,PH) ;
125 param dist_table := [*,*] BO NY 232
131 param section := 14 ;
135 (WA,*,PH,*) 2 5 6 9 8 11 10 13
136 12 15 13 16 14 17 15 18
137 16 19 17 20 18 21 19 22
138 20 23 21 24 22 25 23 26
139 24 27 25 28 26 29 27 30
140 28 31 29 32 30 33 31 34
141 32 35 33 36 34 37 35 38
142 36 39 37 40 38 41 39 42
143 40 43 41 44 42 45 44 47
146 (PH,*,NY,*) 1 3 5 7 9 11 11 13
147 13 15 14 16 15 17 16 18
148 17 19 18 20 19 21 20 22
149 21 23 22 24 23 25 24 26
150 25 27 26 28 27 29 28 30
151 29 31 30 32 31 33 32 34
152 33 35 34 36 35 37 36 38
153 37 39 38 40 39 41 40 42
154 41 43 42 44 43 45 44 46
157 (NY,*,BO,*) 10 16 12 18 14 20 15 21
158 16 22 17 23 18 24 19 25
159 20 26 21 27 22 28 23 29
160 24 30 25 31 26 32 27 33
161 28 34 29 35 30 36 31 37
162 32 38 33 39 34 40 35 41
163 36 42 37 43 38 44 39 45
164 40 46 41 47 42 48 43 1
167 (BO,*,NY,*) 7 13 9 15 11 17 12 18
168 13 19 14 20 15 21 16 22
169 17 23 18 24 19 25 20 26
170 21 27 22 28 23 29 24 30
171 25 31 26 32 27 33 28 34
172 29 35 30 36 31 37 32 38
173 33 39 34 40 35 41 36 42
174 37 43 38 44 39 45 40 46
177 (NY,*,PH,*) 1 3 12 14 13 15 14 16
178 15 17 16 18 17 19 18 20
179 19 21 20 22 21 23 22 24
180 23 25 24 26 25 27 26 28
181 27 29 28 30 29 31 30 32
182 31 33 32 34 33 35 34 36
183 35 37 36 38 37 39 38 40
184 39 41 40 42 41 43 42 44
185 43 45 44 46 45 47 46 48
188 (PH,*,WA,*) 1 4 14 17 15 18 16 19
189 17 20 18 21 19 22 20 23
190 21 24 22 25 23 26 24 27
191 25 28 26 29 27 30 28 31
192 29 32 30 33 31 34 32 35
193 33 36 34 37 35 38 36 39
194 37 40 38 41 39 42 40 43
195 41 44 42 45 43 46 44 47
200 [WA,*,PH,*] 2 5 .55 6 9 .01 8 11 .01
201 10 13 .13 12 15 1.59 13 16 1.69
202 14 17 5.19 15 18 3.55 16 19 6.29
203 17 20 4.00 18 21 5.80 19 22 3.40
204 20 23 4.88 21 24 2.92 22 25 4.37
205 23 26 2.80 24 27 4.23 25 28 2.88
206 26 29 4.33 27 30 3.11 28 31 4.64
207 29 32 3.44 30 33 4.95 31 34 3.73
208 32 35 5.27 33 36 3.77 34 37 4.80
209 35 38 3.31 36 39 3.89 37 40 2.65
210 38 41 3.01 39 42 2.04 40 43 2.31
211 41 44 1.52 42 45 1.75 44 47 1.88
214 [PH,*,NY,*] 1 3 1.05 5 7 .43 9 11 .20
215 11 13 .21 13 15 .40 14 16 6.49
216 15 17 16.40 16 18 9.48 17 19 17.15
217 18 20 9.31 19 21 15.20 20 22 8.21
218 21 23 13.32 22 24 7.35 23 25 11.83
219 24 26 6.61 25 27 10.61 26 28 6.05
220 27 29 9.65 28 30 5.61 29 31 9.25
221 30 32 5.40 31 33 8.24 32 34 4.84
222 33 35 7.44 34 36 4.44 35 37 6.80
223 36 38 4.11 37 39 6.25 38 40 3.69
224 39 41 5.55 40 42 3.29 41 43 4.77
225 42 44 2.91 43 45 4.19 44 46 2.53
228 [NY,*,BO,*] 10 16 1.23 12 18 3.84 14 20 4.08
229 15 21 1.47 16 22 2.96 17 23 1.60
230 18 24 2.95 19 25 1.71 20 26 2.81
231 21 27 1.77 22 28 2.87 23 29 1.84
232 24 30 2.95 25 31 1.91 26 32 3.12
233 27 33 1.93 28 34 3.31 29 35 2.00
234 30 36 3.40 31 37 2.08 32 38 3.41
235 33 39 2.69 34 40 4.45 35 41 2.32
236 36 42 3.40 37 43 1.80 38 44 2.63
237 39 45 1.52 40 46 2.23 41 47 1.25
238 42 48 1.79 43 1 .97 44 2 1.28
239 45 3 .48 46 4 .68 48 6 .08
241 [BO,*,NY,*] 7 13 .03 9 15 1.29 11 17 4.59
242 12 18 2.56 13 19 3.92 14 20 2.37
243 15 21 3.81 16 22 2.24 17 23 3.51
244 18 24 2.13 19 25 3.28 20 26 2.05
245 21 27 3.15 22 28 1.99 23 29 3.09
246 24 30 1.93 25 31 3.19 26 32 1.91
247 27 33 3.21 28 34 1.85 29 35 3.21
248 30 36 1.71 31 37 3.04 32 38 2.08
249 33 39 3.13 34 40 1.96 35 41 2.53
250 36 42 1.43 37 43 2.04 38 44 1.12
251 39 45 1.71 40 46 .91 41 47 1.32
252 43 1 1.80 45 3 1.13 47 5 .23
254 [NY,*,PH,*] 1 3 .04 12 14 4.68 13 15 5.61
255 14 16 3.56 15 17 5.81 16 18 3.81
256 17 19 6.31 18 20 4.07 19 21 7.33
257 20 22 4.55 21 23 7.37 22 24 4.73
258 23 25 7.61 24 26 4.92 25 27 7.91
259 26 28 5.19 27 29 8.40 28 30 5.53
260 29 31 9.32 30 32 5.51 31 33 10.33
261 32 34 9.21 33 35 18.95 34 36 11.23
262 35 37 16.85 36 38 7.29 37 39 10.89
263 38 40 5.41 39 41 8.21 40 42 4.52
264 41 43 6.99 42 44 3.92 43 45 6.21
265 44 46 3.44 45 47 5.17 46 48 2.55
268 [PH,*,WA,*] 1 4 .20 14 17 4.49 15 18 3.53
269 16 19 2.67 17 20 3.83 18 21 3.01
270 19 22 4.12 20 23 3.15 21 24 4.67
271 22 25 3.20 23 26 4.23 24 27 2.87
272 25 28 3.84 26 29 2.60 27 30 3.80
273 28 31 2.77 29 32 4.31 30 33 3.16
274 31 34 4.88 32 35 3.45 33 36 5.55
275 34 37 3.52 35 38 6.11 36 39 3.32
276 37 40 5.53 38 41 3.03 39 42 4.51
277 40 43 2.53 41 44 3.39 42 45 1.93
278 43 46 2.52 44 47 1.20 45 48 1.75