COIN-OR::LEMON - Graph Library

source: glpk-cmake/examples/train.mod @ 1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 11.2 KB
Line 
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
9set cities;
10
11set links within {c1 in cities, c2 in cities: c1 <> c2};
12
13                        # Set of cities, and set of intercity links
14
15param last > 0 integer; # Number of time intervals in a day
16
17set times := 1..last;   # Set of time intervals in a day
18
19set 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
29param section > 0 integer;
30
31                        # Maximum number of cars in one section of a train
32
33param demand {schedule} > 0;
34
35                        # For each scheduled train:
36                        # the smallest number of cars that
37                        # can meet demand for the train
38
39param low {(c1,t1,c2,t2) in schedule} := ceil(demand[c1,t1,c2,t2]);
40
41                        # Minimum number of cars needed to meet demand
42
43param 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
56param dist_table {links} >= 0 default 0.0;
57
58param 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
66var 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
71var 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
79minimize 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
87minimize 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
94account {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
107satisfy {(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
118data;
119
120set cities := BO NY PH WA ;
121
122set links := (BO,NY) (NY,PH) (PH,WA)
123             (NY,BO) (PH,NY) (WA,PH) ;
124
125param dist_table := [*,*]  BO NY  232
126                           NY PH   90
127                           PH WA  135 ;
128
129param last := 48 ;
130
131param section := 14 ;
132
133set 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
198param 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
281end;
Note: See TracBrowser for help on using the repository browser.