102 lines
3.5 KiB
MiniZinc
102 lines
3.5 KiB
MiniZinc
%------------------------------------------------------------------------------
|
|
% Airport Check-in Counter Allocation Problem (ACCAP) with fixed opening/closing times
|
|
%------------------------------------------------------------------------------
|
|
%
|
|
% Airports have certain number of check-in counters that can be used by any airlines(common-use
|
|
% check-in counters) throughout the day. Airlines need to start and end the check-in operations
|
|
% for their flights at given times before the departure time of the flights. Each flight has a
|
|
% given time interval/duration (opDur) that they need to keep the check-in open, and this is
|
|
% fixed for the whole duration of the check-in. Given the number of airlines, their flights
|
|
% (FLIGHTS), starting time of each check-in (xCoor) ,required number of counters (cNum), and
|
|
% duration of the check-in (opDur), the objective is to find such an allocation of flights
|
|
% (check-ins) to counters (yCoor: starting counter ID ) to minimise the maximum used number of
|
|
% counters throughout the day (D), as well as making sure that the flights of the same airlines
|
|
% are clustered in the same check-in area by minimising the sum of the total distances (S)
|
|
% between the counters of each pair of flights of the same airline (S).
|
|
%
|
|
%
|
|
%------------------------------------------------------------------------------
|
|
% Includes
|
|
|
|
include "diffn.mzn";
|
|
|
|
%------------------------------------------------------------------------------
|
|
% Sets and indices
|
|
|
|
% set of flights
|
|
int: flights;
|
|
set of int: FLIGHT = 1..flights;
|
|
|
|
% time intervals
|
|
int: times;
|
|
set of int: TIME = 1..times;
|
|
|
|
% set of counter IDs
|
|
set of int: COUNTER = 1..sum(cNum);
|
|
|
|
% set of airlines
|
|
int: airlines;
|
|
set of int: AIRLINE = 1..airlines;
|
|
|
|
% set of flights of airlines
|
|
array[AIRLINE] of set of FLIGHT: FA;
|
|
|
|
% set of steart-end check-in times of flights
|
|
array[FLIGHT] of set of TIME: ISet =
|
|
[ {k| k in xCoor[f]..(opDur[f] + xCoor[f] - 1)} | f in FLIGHT];
|
|
|
|
%------------------------------------------------------------------------------
|
|
% Variables and parameters
|
|
|
|
array[FLIGHT] of int: xCoor; %starting time
|
|
array[FLIGHT] of var COUNTER: yCoor; %lower-bottom corner of the rectangle (counter) : variable
|
|
array[FLIGHT] of int: opDur; %Length - opening Duration
|
|
array[FLIGHT] of int: cNum; %Height - required numebr of counters
|
|
var max(cNum)..((airlines + 1) * sum(cNum)): objective; %objective: variable
|
|
|
|
% Distance between two flights :variable
|
|
array[AIRLINE] of var 0..sum(cNum): S;
|
|
|
|
% Domain of D(maximum counter use) :variable
|
|
var max(cNum)..sum(cNum): D;
|
|
|
|
%------------------------------------------------------------------------------
|
|
% Constraints
|
|
|
|
% C1: Non-overlapping constraint
|
|
constraint diffn(xCoor, yCoor, opDur, cNum);
|
|
|
|
% C2: Capacity constraint
|
|
constraint forall(f in FLIGHT)( (yCoor[f] + cNum[f] - 1) <= D );
|
|
|
|
% C3: Distance constraint
|
|
constraint forall(a in AIRLINE, f, g in FA[a] where f != g)(
|
|
((yCoor[f] + cNum[f] - 1) - (yCoor[g]) <= S[a])
|
|
);
|
|
|
|
% C4: Objective function
|
|
constraint objective = sum(a in AIRLINE)(S[a]) + D;
|
|
|
|
%------------------------------------------------------------------------------
|
|
% Solve item
|
|
|
|
solve
|
|
:: seq_search([
|
|
int_search(yCoor, first_fail, indomain_min, complete),
|
|
int_search(S, first_fail, indomain_min, complete),
|
|
int_search([D], input_order, indomain_min, complete)
|
|
])
|
|
minimize objective;
|
|
|
|
%------------------------------------------------------------------------------
|
|
% Output
|
|
|
|
output [
|
|
"yCoor = \(yCoor);\n",
|
|
"S = \(S);\n",
|
|
"D = \(D);\n",
|
|
"objective = \(objective);\n"
|
|
];
|
|
|
|
|