A set of benchmarks to compare a new prototype MiniZinc implementation
dekker.one
1%----------------------------------------------------------------------------%
2%
3% There are two warehouses, A and B.
4% Each warehouse has a fixed set of customers. No customer
5% is served by both warehouses - so the two sets are disjoint.
6% Each warehouse has a truck.
7% There is a table of distances from customer to warehouse
8% and between the customers.
9%
10% A truck is allowed to deliver not only to customers
11% of its own warehouse, but also to customers of the other warehouse.
12% To make this possible there is a "depot" where one truck can leave
13% some goods for the other truck to pick up and deliver to the customer.
14% The choice of depot is a decision variable ranging over customer and
15% warehouse locations.
16%
17% Naturally before delivering to a customer of another warehouse, the
18% truck must first visit the depot to collect the goods for delivery
19% to the customer. The other truck must also visit the depot, of
20% course, to drop off the goods. There are no time constraints, and
21% therefore no restriction on which truck visits the depot first.
22% (Since there are no time constraints, the first truck to arrive
23% could simply wait till the other truck came.)
24%
25% The objective is to minimise the maximum of the distances
26% travelled by the trucks.
27%
28%----------------------------------------------------------------------------%
29
30include "alldifferent.mzn" ;
31
32%----------------------------------------------------------------------------%
33%
34% Parameters
35%
36
37% Number of clients each warehouse has.
38%
39int: PSize;
40
41% This model allows Depot to be a parameter:
42% int: Depot = 11;
43% To ensure trucks only serve their own clients
44% you can set the depot to a non-existent location
45% int: Depot = 0 ;
46% ...or a variable over all the possible locations
47var 1..TSize: Depot;
48
49% Total number of locations (Warehouses plus customers) in the problem.
50%
51int: TSize = (PSize +1 ) * 2 ;
52
53% We use PSize+1 often, so we next give it the name TourLength.
54%
55int: TourLength = PSize+1 ;
56
57% Warehouse A's clients are from 1..TourLength
58% Warehouse B's clients are from TourLength+1..TSize
59
60% Set the location of warehouse A to 1.
61%
62int: AWHouse = 1 ;
63
64% Set the location of warehouse B to first of its client's locations.
65% For a size 3 problem, therefore, warehouse B is at location 5.
66%
67int: BWHouse = TourLength + 1;
68
69% Each tour may have a different size, but
70% to keep things manageable we have only allowed each truck to
71% visit at most 1 extra client. In this model both tours are
72% represented as arrrays of the same size: one larger than needed
73% to visit all their customers.
74% In case the extra location is not needed (the truck only visits
75% its own customers) the truck simply remains at the warehouse
76% so each of its first AND SECOND location is the warehouse.
77%
78int: ASize = TourLength + 1;
79int: BSize = TourLength + 1;
80
81%----------------------------------------------------------------------------%
82%
83% Variables
84%
85
86% Need two "NextCity" arrays when there's a depot!
87% This is the easy TSP model, with the awkward cost function
88% The tour for truck A, simply listed the locations visited
89% in the order of visits.
90% Each truck can visit any location.
91%
92array[1..ASize] of var 1..TSize: TourALoc ;
93
94% The tour for truck B.
95%
96array[1..BSize] of var 1..TSize: TourBLoc ;
97
98% Set the complete distance table (see the .dzn files for actua numbers).
99%
100array[1..14, 1..14] of int: AllDist;
101
102int: MaxTotDist = sum([max([AllDist[N,M] |M in 1..TSize]) | N in 1..TSize]) ;
103int: MaxLeg = max([max([AllDist[N,M] | M in 1..TSize]) | N in 1..TSize]) ;
104
105% For each tour (A and B) keep an array of distances
106% to use for computing total distance.
107%
108array[1..ASize] of var 0..MaxLeg: ALegDist ;
109array[1..BSize] of var 0..MaxLeg: BLegDist ;
110
111% Represent the optimisation expression as a variable so as to
112% get proper output from lazy MiniZinc.
113%
114var 0..MaxTotDist: ADist;
115var 0..MaxTotDist: BDist;
116
117var 0..MaxTotDist: objective;
118
119%----------------------------------------------------------------------------%
120
121% The optimisation variable.
122%
123constraint ADist = sum(ALegDist) ;
124constraint BDist = sum(BLegDist) ;
125constraint objective = max(ADist,BDist) ;
126
127% The distance between the Nth and (N+1)th locations.
128%
129constraint
130 forall (N in 1..ASize-1) (ALegDist[N] = AllDist[TourALoc[N], TourALoc[N+1]]);
131
132% The distance from the final location back to the warehouse.
133%
134constraint ALegDist[ASize] = AllDist[TourALoc[ASize],TourALoc[1]] ;
135
136constraint
137 forall (C in 1..BSize-1) (BLegDist[C] = AllDist[TourBLoc[C], TourBLoc[C+1]]);
138
139constraint BLegDist[BSize] = AllDist[TourBLoc[BSize],TourBLoc[1]] ;
140
141% Ensure all location are visited by at least one of the tours A or B.
142%
143constraint forall (C in 1..TSize) ( exists (Y in TourALoc++TourBLoc) (Y = C) );
144
145% Constraints
146% Ensure each tour visits different locations.
147% BEWARE that these constraint are NOT redundant with the previous one, because they
148% exclude consecutive visits of non-warehouse locations!
149%
150constraint alldifferent([TourALoc[N]|N in 2..ASize]);
151constraint alldifferent([TourBLoc[N]|N in 2..BSize]);
152
153% The warehouse must be visited first
154%
155constraint TourALoc[1] = AWHouse ;
156constraint TourBLoc[1] = BWHouse ;
157
158% Don't come back to the Warehouse until all the
159% deliveries are done!
160%
161constraint forall (N in 3..ASize-1) (TourALoc[N] != AWHouse);
162constraint forall (N in 3..BSize-1) (TourBLoc[N] != BWHouse);
163
164% Symmetry breaking constraints
165% A second visit of the warehouse must be at the second position
166%
167constraint symmetry_breaking_constraint( TourALoc[ASize] != AWHouse );
168constraint symmetry_breaking_constraint( TourALoc[BSize] != BWHouse );
169
170% Warehouses cannot be visit by different trucks
171%
172constraint forall (N in 1..ASize) (TourALoc[N] != BWHouse);
173constraint forall (N in 1..BSize) (TourBLoc[N] != AWHouse);
174
175%----------------------------------------------------------------------------%
176%
177% Depot constraints
178%
179
180% If tour A visits a location from warehouse B, then its must visit the depot
181% before visiting this location.
182% Thus if the Nth location in tour A is a client of warehouse B,
183% (because its value is greater than TourLength and it is not the Depot)
184% then tour A must visit the Depot beforehand (at its Mth location, where M<N).
185%
186constraint
187 forall (N in 1..ASize)
188 ( (TourALoc[N] > TourLength /\ TourALoc[N] != Depot ) ->
189 ( exists (M in 1..N-1) (TourALoc[M] = Depot) ) );
190
191% If tour B visits one of A's clients, then it must visit the Depot beforehand.
192%
193constraint
194 forall (N in 1..BSize)
195 ( (TourBLoc[N] <= TourLength /\ TourBLoc[N] != Depot ) ->
196 ( exists (M in 1..N-1) (TourBLoc[M] = Depot) ) ) ;
197
198% Note that a truck always visits the depot if the depot is one of
199% its own customers because, if it does not visit any of the other
200% warehouse's customers, it must still visit TourLength different locations
201% which means it visits ALL its own customers!
202
203%----------------------------------------------------------------------------%
204
205solve
206 :: seq_search([
207 int_search(TourALoc ++ TourBLoc, first_fail, indomain_min, complete),
208 int_search([Depot], input_order, indomain_min, complete)
209 ])
210 minimize objective;
211
212%----------------------------------------------------------------------------%
213
214output[ "%% Maximum Tour Distance: ", show(objective),
215 ";\nDepot = ", show(Depot),
216 ";\n%% ADist is: ",show(ADist),
217 ";\n%% BDist is: ", show(BDist),
218 ";\nTourALoc = ", show(TourALoc),
219 ";\nTourBLoc = ", show(TourBLoc),
220 ";\nobjective = ", show(objective),
221 ";\n" ] ;
222
223%----------------------------------------------------------------------------%
224%----------------------------------------------------------------------------%