Context Navigation

train.mod @ 9:33de93886c88

subpack-glpk

Last change on this file since 9:33de93886c88 was 9:33de93886c88, checked in by Alpar Juttner <alpar@…>, 12 years ago
Import GLPK 4.47
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
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;

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: lemon-project-template-glpk/deps/glpk/examples/train.mod @ 9:33de93886c88

Download in other formats: