A set of benchmarks to compare a new prototype MiniZinc implementation
dekker.one
1%----------------------------------------------------------------------------%
2%----------------------------------------------------------------------------%
3%
4% We have n trains moving along a single track with m stations. There is a
5% non-zero constant flow of passengers arriving at all but the first and last
6% station who wish to travel to the final station. Trains are originally
7% scheduled so that they collect the passengers and drop them at the final
8% station. To this original schedule a disruption is introduced whereby a train
9% is delayed. Each of the trains (at the time of the delay) has knowledge of the
10% duration of the delay. The objective is to reschedule the trains to minimize
11% the average travel time of the passengers. Trains are not able to overtake
12% preceding trains, however they do have the option to
13% skip a station and wait longer at a station to collect more passengers.
14
15%----------------------------------------------------------------------------%
16%----------------------------------------------------------------------------%
17
18%include "globals.mzn";
19
20int : n;
21int : m;
22
23int : maxTime;
24
250..maxTime : delayTime;
261..n : delayTrain;
270..maxTime : delayDuration;
28
29array [1..m-1] of 0..maxTime : distance;
30
31array [1..n, 1..m] of 0..maxTime : scheduledArrival;
32array [1..n, 1..m] of 0..maxTime : scheduledDeparture;
33
34array [1..m] of 0..maxTime : passengerStart;
35array [1..m] of 0..maxTime : passengerStop = [scheduledDeparture[n,j] | j in 1..m];
36array [1..m] of int : passengerFlow;
37
38array [1..n, 1..m] of var 0..maxTime : departure;
39array [1..n, 1..m] of var 0..maxTime : arrival;
40
41array [1..n] of var 0..maxTime : finalArrival = [ arrival[i,m] | i in 1..n ];
42
43array [1..n, 1..m] of var 0..maxTime : sigmaLower;
44array [1..n, 1..m] of var 0..maxTime : sigmaUpper;
45
46int : capacity;
47
48array [1..n, 1..m] of var 0..capacity : collect;
49array [1..n, 1..m] of var 0..capacity : load;
50
51% All trains "arrive" at the first station at time 0.
52constraint forall (i in 1..n)
53 (arrival[i,1] = 0);
54% ... and "depart" from the last station as soon as they arrive there.
55constraint forall (i in 1..n)
56 (departure[i,m] = arrival[i,m]);
57
58% Before the delay, everything runs to schedule.
59constraint forall (i in 1..n, j in 1..m-1)
60 (if scheduledDeparture[i,j] <= delayTime
61 then departure[i,j] = scheduledDeparture[i,j]
62 else true
63 endif);
64
65% If the train is in motion, then the arrival of the
66% delayed train is at least the departure time at the previous station
67% plus the ordinary travel time plus the duration of the delay.
68int : destinationWhenDelayed = min([j | j in 1..m where scheduledDeparture[delayTrain,j] > delayTime]);
69constraint if destinationWhenDelayed > 1
70 then if delayTime < scheduledDeparture[delayTrain,destinationWhenDelayed-1] + distance[destinationWhenDelayed-1]
71 then arrival[delayTrain,destinationWhenDelayed] >=
72 departure[delayTrain,destinationWhenDelayed-1] + delayDuration + distance[destinationWhenDelayed-1]
73 else true
74 endif
75 else true
76 endif;
77% The train's next departure is at least the delay time plus the delay
78% duration.
79constraint departure[delayTrain, destinationWhenDelayed] >= delayTime + delayDuration;
80
81% Trains depart after they arrive.
82constraint forall (i in 1..n, j in 1..m)
83 (departure[i,j] >= arrival[i,j]);
84
85% Trains never leave earlier than scheduled.
86constraint forall (i in 1..n, j in 1..m-1)
87 (departure[i,j] >= scheduledDeparture[i,j]);
88
89% There is a minimum travel time between stations.
90constraint forall (i in 1..n, j in 1..m-1)
91 (arrival[i,j+1] >= departure[i,j] + distance[j]);
92
93% At station 1, trains leave in order.
94constraint forall (i in 1..n-1)
95 (departure[i,1] < departure[i+1,1]);
96% At most one train dwelling at a station at a given time.
97constraint forall (i in 1..n-1, j in 2..m-1)
98 (departure[i,j] <= arrival[i+1,j]-2);
99
100% The sigma values partition time at each station.
101constraint forall (i in 1..n, j in 1..m)
102 (sigmaLower[i,j] <= sigmaUpper[i,j]);
103
104% For the first and last trains, the sigma values are equal to the
105% extreme times of passenger arrivals.
106constraint forall (j in 2..m-1)
107 ((sigmaLower[1,j] = passengerStart[j])
108 /\ (sigmaUpper[n,j] = scheduledDeparture[n,j]));
109% The sigma values join together.
110constraint forall (i in 1..n-1, j in 1..m)
111 (sigmaUpper[i,j] = sigmaLower[i+1,j]);
112
113% You can't pick up people after you leave.
114constraint forall (i in 1..n-1, j in 1..m-1)
115 (sigmaUpper[i,j] <= departure[i,j]);
116constraint forall (j in 1..m-1)
117 (sigmaUpper[n,j] <= departure[n,j]);
118
119% Defines collect and load variables.
120constraint forall (i in 1..n, j in 1..m)
121 (collect[i,j] = (sigmaUpper[i,j]-sigmaLower[i,j])*passengerFlow[j]);
122
123constraint forall (i in 1..n) (load[i,1] = collect[i,1]);
124constraint forall (i in 1..n, j in 2..m)
125 (load[i,j] = load[i,j-1] + collect[i,j]);
126
127% If a train picks anyone up, then it must pick
128% everyone up (until it gets full).
129constraint forall (i in 1..n, j in 1..m-1)
130 (sigmaUpper[i,j] > sigmaLower[i,j] ->
131 ((sigmaUpper[i,j] = departure[i,j]) \/
132 (sigmaUpper[i,j] = scheduledDeparture[n,j]) \/
133 (load[i,j] + bool2int(sigmaUpper[i,j] < scheduledDeparture[n,j])*passengerFlow[j] > capacity)));
134
135% Boarding time.
136constraint forall (i in 1..n, j in 2..m)
137 (((capacity-load[i,j-1] < 100) -> (collect[i,j] <= dwell[i,j]*20)) /\
138 ((capacity-load[i,j-1] >= 100) -> (collect[i,j] <= dwell[i,j]*50)));
139% (Redundant for j>=2 (but necessary for j=1))
140constraint forall (i in 1..n, j in 1..m)
141 (collect[i,j] <= (departure[i,j]-arrival[i,j])*50);
142
143array [1..n, 1..m] of var 0..maxTime : dwell;
144constraint forall (i in 1..n, j in 1..m) (dwell[i,j] = departure[i,j] - arrival[i,j]);
145
146int: objective_min = lb(sum(i in 1..n)(load[i,m]*arrival[i,m]));
147int: objective_max = ub(sum(i in 1..n)(load[i,m]*arrival[i,m]));
148var objective_min..objective_max: objective = sum(i in 1..n)(load[i,m]*arrival[i,m]);
149
150solve
151 :: seq_search([
152 int_search(
153 [arrival[i,m-j+1] | j in 1..m, i in 1..n] ++
154 [departure[i,m-j+1] | j in 1..m, i in 1..n] ++
155 [sigmaUpper[i,m-j+1] | j in 1..m, i in 1..n] ++
156 [sigmaLower[i,m-j+1] | j in 1..m, i in 1..n],
157 input_order, indomain_min, complete
158 ),
159 int_search(
160 array1d(1..n*m, collect) ++ array1d(1..n*m, load) ++ array1d(1..n*m, dwell),
161 first_fail, indomain_min, complete
162 )
163 ])
164 minimize objective;
165
166output [
167 "arrival = array2d(1..", show(n), ", 1..", show(m), ", ", show(arrival), ");\n",
168 "departure = array2d(1..", show(n), ", 1..", show(m), ", ", show(departure), ");\n",
169 "sigmaLower = array2d(1..", show(n), ", 1..", show(m), ", ", show(sigmaLower), ");\n",
170 "sigmaUpper = array2d(1..", show(n), ", 1..", show(m), ", ", show(sigmaUpper), ");\n",
171 "collect = array2d(1..", show(n), ", 1..", show(m), ", ", show(collect), ");\n",
172 "load = array2d(1..", show(n), ", 1..", show(m), ", ", show(load), ");\n",
173 "dwell = array2d(1..", show(n), ", 1..", show(m), ", ", show(dwell), ");\n",
174 "constraint objective = ", show(objective), ";\n"
175];
176