|
1 # TRAIN, a model of railroad passenger car allocation |
|
2 # |
|
3 # References: |
|
4 # Robert Fourer, David M. Gay and Brian W. Kernighan, "A Modeling Language |
|
5 # for Mathematical Programming." Management Science 36 (1990) 519-554. |
|
6 |
|
7 ### SCHEDULE SETS AND PARAMETERS ### |
|
8 |
|
9 set cities; |
|
10 |
|
11 set links within {c1 in cities, c2 in cities: c1 <> c2}; |
|
12 |
|
13 # Set of cities, and set of intercity links |
|
14 |
|
15 param last > 0 integer; # Number of time intervals in a day |
|
16 |
|
17 set times := 1..last; # Set of time intervals in a day |
|
18 |
|
19 set schedule within |
|
20 {c1 in cities, t1 in times, |
|
21 c2 in cities, t2 in times: (c1,c2) in links}; |
|
22 |
|
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 |
|
26 |
|
27 ### DEMAND PARAMETERS ### |
|
28 |
|
29 param section > 0 integer; |
|
30 |
|
31 # Maximum number of cars in one section of a train |
|
32 |
|
33 param demand {schedule} > 0; |
|
34 |
|
35 # For each scheduled train: |
|
36 # the smallest number of cars that |
|
37 # can meet demand for the train |
|
38 |
|
39 param low {(c1,t1,c2,t2) in schedule} := ceil(demand[c1,t1,c2,t2]); |
|
40 |
|
41 # Minimum number of cars needed to meet demand |
|
42 |
|
43 param high {(c1,t1,c2,t2) in schedule} |
|
44 |
|
45 := max (2, min (ceil(2*demand[c1,t1,c2,t2]), |
|
46 section*ceil(demand[c1,t1,c2,t2]/section) )); |
|
47 |
|
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 |
|
53 |
|
54 ### DISTANCE PARAMETERS ### |
|
55 |
|
56 param dist_table {links} >= 0 default 0.0; |
|
57 |
|
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]; |
|
60 |
|
61 # Inter-city distances: distance[c1,c2] is miles |
|
62 # between city c1 and city c2 |
|
63 |
|
64 ### VARIABLES ### |
|
65 |
|
66 var U 'cars stored' {cities,times} >= 0; |
|
67 |
|
68 # u[c,t] is the number of unused cars stored |
|
69 # at city c in the interval beginning at time t |
|
70 |
|
71 var X 'cars in train' {schedule} >= 0; |
|
72 |
|
73 # x[c1,t1,c2,t2] is the number of cars assigned to |
|
74 # the scheduled train that leaves c1 at t1 and |
|
75 # arrives in c2 at t2 |
|
76 |
|
77 ### OBJECTIVES ### |
|
78 |
|
79 minimize cars: |
|
80 sum {c in cities} U[c,last] + |
|
81 sum {(c1,t1,c2,t2) in schedule: t2 < t1} X[c1,t1,c2,t2]; |
|
82 |
|
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 |
|
86 |
|
87 minimize miles: |
|
88 sum {(c1,t1,c2,t2) in schedule} distance[c1,c2] * X[c1,t1,c2,t2]; |
|
89 |
|
90 # Total car-miles run by all scheduled trains in a day |
|
91 |
|
92 ### CONSTRAINTS ### |
|
93 |
|
94 account {c in cities, t in times}: |
|
95 |
|
96 U[c,t] = U[c, if t > 1 then t-1 else last] + |
|
97 |
|
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]; |
|
100 |
|
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 |
|
106 |
|
107 satisfy {(c1,t1,c2,t2) in schedule}: |
|
108 |
|
109 low[c1,t1,c2,t2] <= X[c1,t1,c2,t2] <= high[c1,t1,c2,t2]; |
|
110 |
|
111 # For each scheduled train: |
|
112 # number of cars must meet demand, |
|
113 # but must not be so great that unnecessary |
|
114 # sections are run |
|
115 |
|
116 ### DATA ### |
|
117 |
|
118 data; |
|
119 |
|
120 set cities := BO NY PH WA ; |
|
121 |
|
122 set links := (BO,NY) (NY,PH) (PH,WA) |
|
123 (NY,BO) (PH,NY) (WA,PH) ; |
|
124 |
|
125 param dist_table := [*,*] BO NY 232 |
|
126 NY PH 90 |
|
127 PH WA 135 ; |
|
128 |
|
129 param last := 48 ; |
|
130 |
|
131 param section := 14 ; |
|
132 |
|
133 set schedule := |
|
134 |
|
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 |
|
144 46 1 |
|
145 |
|
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 |
|
155 45 47 47 1 |
|
156 |
|
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 |
|
165 44 2 45 3 46 4 48 6 |
|
166 |
|
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 |
|
175 41 47 43 1 45 3 47 5 |
|
176 |
|
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 |
|
186 47 1 |
|
187 |
|
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 |
|
196 45 48 46 1 47 2 ; |
|
197 |
|
198 param demand := |
|
199 |
|
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 |
|
212 46 1 1.05 |
|
213 |
|
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 |
|
226 45 47 4.00 47 1 1.65 |
|
227 |
|
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 |
|
240 |
|
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 |
|
253 |
|
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 |
|
266 47 1 1.24 |
|
267 |
|
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 |
|
279 46 1 .88 47 2 .87 ; |
|
280 |
|
281 end; |