A set of benchmarks to compare a new prototype MiniZinc implementation
dekker.one
1%------------------------------------------------------------------------------
2% Airport Check-in Counter Allocation Problem (ACCAP) with fixed opening/closing times
3%------------------------------------------------------------------------------
4%
5% Airports have certain number of check-in counters that can be used by any airlines(common-use
6% check-in counters) throughout the day. Airlines need to start and end the check-in operations
7% for their flights at given times before the departure time of the flights. Each flight has a
8% given time interval/duration (opDur) that they need to keep the check-in open, and this is
9% fixed for the whole duration of the check-in. Given the number of airlines, their flights
10% (FLIGHTS), starting time of each check-in (xCoor) ,required number of counters (cNum), and
11% duration of the check-in (opDur), the objective is to find such an allocation of flights
12% (check-ins) to counters (yCoor: starting counter ID ) to minimise the maximum used number of
13% counters throughout the day (D), as well as making sure that the flights of the same airlines
14% are clustered in the same check-in area by minimising the sum of the total distances (S)
15% between the counters of each pair of flights of the same airline (S).
16%
17%
18%------------------------------------------------------------------------------
19% Includes
20
21include "diffn.mzn";
22
23%------------------------------------------------------------------------------
24% Sets and indices
25
26% set of flights
27int: flights;
28set of int: FLIGHT = 1..flights;
29
30% time intervals
31int: times;
32set of int: TIME = 1..times;
33
34% set of counter IDs
35set of int: COUNTER = 1..sum(cNum);
36
37% set of airlines
38int: airlines;
39set of int: AIRLINE = 1..airlines;
40
41% set of flights of airlines
42array[AIRLINE] of set of FLIGHT: FA;
43
44% set of steart-end check-in times of flights
45array[FLIGHT] of set of TIME: ISet =
46 [ {k| k in xCoor[f]..(opDur[f] + xCoor[f] - 1)} | f in FLIGHT];
47
48%------------------------------------------------------------------------------
49% Variables and parameters
50
51array[FLIGHT] of int: xCoor; %starting time
52array[FLIGHT] of var COUNTER: yCoor; %lower-bottom corner of the rectangle (counter) : variable
53array[FLIGHT] of int: opDur; %Length - opening Duration
54array[FLIGHT] of int: cNum; %Height - required numebr of counters
55var max(cNum)..((airlines + 1) * sum(cNum)): objective; %objective: variable
56
57% Distance between two flights :variable
58array[AIRLINE] of var 0..sum(cNum): S;
59
60% Domain of D(maximum counter use) :variable
61var max(cNum)..sum(cNum): D;
62
63%------------------------------------------------------------------------------
64% Constraints
65
66% C1: Non-overlapping constraint
67constraint diffn(xCoor, yCoor, opDur, cNum);
68
69% C2: Capacity constraint
70constraint forall(f in FLIGHT)( (yCoor[f] + cNum[f] - 1) <= D );
71
72% C3: Distance constraint
73constraint forall(a in AIRLINE, f, g in FA[a] where f != g)(
74 ((yCoor[f] + cNum[f] - 1) - (yCoor[g]) <= S[a])
75);
76
77% C4: Objective function
78constraint objective = sum(a in AIRLINE)(S[a]) + D;
79
80%------------------------------------------------------------------------------
81% Solve item
82
83solve
84 :: seq_search([
85 int_search(yCoor, first_fail, indomain_min, complete),
86 int_search(S, first_fail, indomain_min, complete),
87 int_search([D], input_order, indomain_min, complete)
88 ])
89 minimize objective;
90
91%------------------------------------------------------------------------------
92% Output
93
94output [
95 "yCoor = \(yCoor);\n",
96 "S = \(S);\n",
97 "D = \(D);\n",
98 "objective = \(objective);\n"
99];
100
101