Integer and constraint programming model formulations for flight-gate assignment problem

Abstract

Flight-gate assignment problems are complex real world problems involving different constraints. Some of these constraints include plane-gate eligibility, assigning planes of the same airline and planes getting service from the same ground handling companies to adjacent gates, buffers for changes in flight schedules, night stand flights, priority of some gates over others, and so on. In literature there are numerous models to solve this highly complicated problem and tackle its complexity. In this study, first, we propose two different integer programming models, namely, timetabling and assignment based models, and then a scheduling based constraint programming model to solve the problem to optimality. These models prove to be highly efficient in that the computational times are quite short. We also present the results for one day operation of an airport using real data. Finally, we present our conclusions based on our study along with the possible further research.

1 Introduction and literature survey

A gate is an important resource at the disposal of an airline in a hub-spoke airport. With an intense air-traffic increase in recent years (doubled since early 1980s), improper assignment of gates may result in flight delays, inefficient use of the resource, customer’s dissatisfaction and hence the need to efficiently use these to reduce operating costs, increase passenger satisfaction, and alleviate congestion has become more prevalent in modern times (de Man 2011; Ballis 2002). The flight gate assignment problem is encountered by gate managers at an airport on a periodic basis, usually daily. This assignment should be made so as to balance carrier efficiency and passenger comfort, while providing buffers for unexpected events that cause assignment disruptions. A typical metropolitan airport has more than fifty gates and handles hundreds of flights a day for thousands of passengers. Gate assignment is a complicated and over-constrained problem as it deals with a wide range of interdependent resources including aircrafts, gates, gate facilities, and crews (Ding et al. 2005).

Airport gate assignment is a critical issue for the operation management of an airport. It means assigning flights to gates according to their real-time arrival time and departure time, such that each flight is assigned to exactly one gate, and there is no conflict between two consecutive flights assigned to the same gate. Determining which aircraft is assigned to which gate is the Gate Assignment Problem (GAP). Since aircraft hardly ever arrives/departs on time, an assignment plan for the upcoming day is to be prepared, based on currently available flight-schedule information in such a way that a reasonable deviation from the scheduled arrival/departure of any of the flights does not result in an infeasible assignment plan. The assignment plan should be robust against such small deviations during the actual day of operations. Typically, gates are first pre-assigned to the scheduled arriving and departing aircrafts ahead of time to ensure a smooth operation. Although gate assignment problem produces only a static schedule, it provides a basis for making last-minute changes to handle operational uncertainty caused by unexpected events such as flight delays, machine failures, and severe weather conditions.

Different methods have been developed to solve this problem with different objectives. For passengers, the objectives include, to name a few, minimizing passenger walking distance and waiting time; for flights and gates, minimizing connection times, cargo handling costs of the gate assignments, slack times, i.e., idle time between two successive assignments of the gate, number of gate conflicts of any two adjacent flights that are assigned to the same gate, aircraft waiting time on the apron, number of ungated flights, off-gate events. Other objectives considered are analyzing the effects of stochastic flight delays on static gate assignments, maximizing the preferences of total gate assignment, the robustness of the resulting schedule and finding gate assignment efficiency which represents rational compromises between waiting time for gate and apron operations (Bouras et al. 2014; Cheng et al. 2012).

From a mathematical view, GAP has been formulated as integer, binary, or mixed integer, general linear or nonlinear models. Some publications proposed specific formulations as binary or mixed binary quadratic models. Quadratic assignment problem (QAP), clique partitioning problem (CPP), and scheduling problem, which are well-known related problems in combinatorial optimization have been used to formulate GAP. From a different point, stochastic or robust optimization was used in few publications. The use of exact solution methods is certainly preferable, however, the use of meta-heuristics is also common (Cheng et al. 2012).

Lim et al. (2005) formulated GAP as an integer programming model and proposed two models with time windows. The first model minimised the passenger walking distance and the second model cargo handling costs of the gate assignments. They used an IP solver to find the optimal solution in the first model; however several heuristic algorithms were used to generate solutions in the second model. According to the results, heuristics gave better results than the IP solver in both CPU time and solutions quality. To minimize the passenger walking distance, the other reference, Bihr (1990), developed a binary integer model. This model was used to solve a sample problem using primal–dual simplex algorithm. Bolat (1999), developed a mixed integer program for GAP with the objective of minimizing the slack times. Li (2009) developed a nonlinear binary mixed integer model with a constraint programming (Dechter 2003) which minimizes the number of gate conflicts of any two adjacent flights that are assigned to the same gate. A study for a stochastic GAP was designed by Yan and Tang (2007). In this analysis, the flight delays are stochastic. It had three parts: the gate assignment model, a rule for the reassignments, and two adjustment methods for penalties. The performance was analyzed and evaluated by a simulation-based method. Drexl and Nikulin (2008), formulated the multi-criteria airport gate assignment as a quadratic assignment problem (QAP) and solved it using Pareto simulated annealing. The objectives are minimizing connection times or total passenger walking distances, maximizing the preferences of total gate assignment, and minimizing the number of ungated flights. Li (2010) modeled GAP as a parallel machine scheduling problem and applied dynamic scheduling and the direct graph model to solve it. For solving the small size problems, branch and bound was used while the large size problems were solved by using dynamic scheduling. Diepen et al. (2012) modeled a completely new IP formulation with a robust objective function expressed as the maximization of an allocation of a maximum possible idle time between each pair of consecutive flights such that the probability of flights overlapping is minimised and the gate schedule becomes more robust.

As an example to multi-objective gate assignment study, Deng et al. (2017) considered the minimum walking distances of passengers, the minimum idle time variance of each gate, the minimum number of flights at parking apron and the most reasonable utilization of large gates as the optimization objectives. They solved the developed model using an improved adaptive particle swarm optimization (DOADAPO) algorithm based on making full use of the advantages of Alpha-stable distribution and dynamic fractional calculus.

For more references on the types of the problem and the relevant solution approaches to assigning flights to gates, see (Sügüt 2016). Finally, not only assigning incoming flights to external gates but also to internal gates (aka common use check-in counters) is quite important in smooth running of airport operations (Lee et al. 2016; Ornek et al. 2019).

This paper considers gate assignment problem for a real medium size airport, which is regarded to be a highly complex problem. There are various considerations that are involved while assigning gates to incoming and outgoing flights at an airport. Gates have different restrictions, such as adjacency, LIFO and push time, which is known in advance based on the structure of the airport. As aforementioned, many different objective functions have been used in literature. In this paper, we propose a novel objective function, different from those found in literature, based on gate utility (importance) concept to reflect practical considerations of the airport authority. The basis of the utility function is that a utility associated with a gate and the utility of a flight being assigned to that specific gate determines together how flights are allocated to the gates. Besides, we propose two novel optimization models, namely, Timetabling and Assignment based integer programming models (IP) and a scheduling based constraint programming model (CP) subject to airport specific business rules formulated as constraints. We solve these models, present, and compare the results for daily operations of an airport using real data sets. The rest of the paper is organised as follows. Section 2 defines the problem and develops the model formulations. Section 3 discusses the performance evaluations of the proposed formulations and provides numerical examples of which data are obtained from a medium-sized airport. Finally, we present our conclusions and elaborate on future research directions.

2 Problem definition and the model formulations

The airport under consideration has a number of open park areas and bridge-equipped gates. Airport management prefers flights to be assigned to bridge-equipped gates as it facilitates embarking and disembarking of passengers. Also, after aircrafts arrive, they need to be refueled, replenished, all the waste has to be taken off-board. If all gates are engaged, then flights are to be assigned to open park areas. Also, night stand flights are assigned to open park areas. Some gates are for emergencies only. These are large enough for allocation of larger planes. For instance, if the bridges 26th and 42nd are full, large planes are assigned to 24th or 25th bridge-equipped parking area. Some airlines have a priority to be assigned to the same gates. Normally, no other flight is assigned to those gates unless that gate is available.

Airline companies that use the same ground handling services firms are assigned adjacent to each other in order to prevent apron traffic. Departure and arrival of a plane is also considered. For instance, if a plane’s departure is international, it has a priority for bridge-equipped parking areas in the international terminal. Similarly, if its departure is domestic, it has a priority in the domestic terminal. Some gates have priority due to their proximity to facilities in the airport. Not every plane fits in every parking area. Hence, some flights cannot be assigned to some parking areas, which we call plane-gate eligibility. We consider improving gate utilization as our primary objective.

In this study, the effectiveness of the gate assignment to a flight is measured by the term “utility”. In other words, a utility value shows how appropriate a gate is for the flight. Maximizing the total utility of the flight-gate assignment under some restrictions is the main objective for the IP formulations. Each gate has a utility value and also each gate takes a different utility value based on the flight assigned to it. These utility values are defined after many observations and the meeting with the operation managers. Therefore, the product of these utility values gives us the total utility of this assignment problem for the IP formulations.

Due to combinatorial nature of the problem, we propose two different integer programming (IP) formulations, namely Timetabling and Assignment based. The basic difference between these two formulations is the number of variables created when a flight is assigned to a gate. Time-tabling model creates number of variables equal to the number of periods a flight remains connected to a gate, whereas the assignment model creates just one when a flight is assigned to (arrives at) the gate. First, we develop a general time-tabling based IP formulation, and then we introduce the tuple concept to dramatically reduce the number of variables unnecessarily created by the model. Next, we provide assignment formulation based on the tuple concept, and then compare their performances. Furthermore, due to its success in solving combinatorial problems, we also propose a constraint programming (CP) based model formulation with customized search heuristic.

Before giving the IP and CP model formulations, we introduce the notation used throughout the paper.

Sets and indices

• $i$: Index of periods, $i \in S = \{ 1,2, \ldots ,|S|\}$

• $j,b$: Index of flights, $j,b \in U = \{ 1,2, \ldots ,|U|\}$

• $k,r$: Index of parking areas, $k,r \in N = \{ 1,2, \ldots ,|M|,|M + 1|, \ldots ,|N|\}$

  Where the first $|M|$ parking areas represent the bridge-equipped parking areas in which night-stand planes cannot be assigned to,

• $d$: Index of parking areas that are occupied from the previous day, $d \in D \subset N$.

• $c$: Index of ground service firms, $c \in C = \{ 1,2, \ldots ,|C|\}$

• $y$: Index of night-stand flights, $y \in Y = \{ 1,2, \ldots ,|Y|\}$

Parameters

• $a_{j}$: Scheduled arrival period of flight $j, \, a_{j} \in S$

• $g_{j}$: Scheduled departure period of flight $j, \, g_{j} \in S$.

  It is assumed that flight j left the airport in period $\left( {g_{j} - 1} \right)$. Hence, the same parking area can be used by another flight starting from the beginning of $g_{j}$. In other words, any flight occupies the assigned parking area in time interval $\left[ {a_{j} ,g_{j} } \right)$. Note that buffer periods for changes in flight schedules are also added to the g_j.

• $f_{j}$: Ground Service Company of flight $j, \, f_{j} \in C$

  $$L_{kr} = \left\{ {\begin{array}{*{20}l} 1 & {If\;parking\;areas\;k\;and\;r\;are\;adjacent} \\ 0 & {o/w} \\ \end{array} } \right.$$
  $$B_{jk} = \left\{ {\begin{array}{*{20}l} 1 & {If\;flight\;j\;can\;be\;assigned\;to\;the\;parking\;area\;k} \\ 0 & {o/w} \\ \end{array} } \right.$$

• $t_{k}$: Earliest available period of parking area $k \in D, \, t_{k} \in S$

• $W_{jk}$: Utility of assigning flight j to parking area k, $W_{jk} \in {\mathbb{R}}^{ + }$

• $w_{k}$: Utility of parking area $k,w_{k} \in {\mathbb{R}}^{ + }$

The decision maker should determine the values of the coefficients $W_{jk}$ and $w_{k}$. In calculating the appropriate values, pairwise comparisons of objectives were used as a good starting point. This comparison scheme is employed in Analytic Hierarchy Process (AHP) (Saaty 1977). AHP is a method of multi-criteria decision making through pairwise comparisons derived from the judgments of experts. The comparisons are made on scales that represent decisions among the criteria. With the use of AHP, the inclusion of intangible factors in the objective function is also possible (Öztürk et al. 2017).

Decision variables

$$x_{ijk} = \left\{ {\begin{array}{*{20}l} 1 & {If \, flight \, j \, is \, assigned \, to \, parking \, area \, k \, in \, period \, i} \\ 0 & {o/w} \\ \end{array} } \right.$$

2.1 Timetabling based integer programming model

In this section, we provide a Timetabling based IP model for the flight-gate assignment problem. Although, we assume parking areas as the limited resources and flights (i.e., aircrafts) as the resource consumers as in Li (2009), different from the literature, in this model we initialize a variable for each flight at each eligible parking area during the service time. In other words, if a flight j can be assigned to parking area k, we define (g_j–a_j) binary variables for flight j at parking area k for periods [a_j, g_j).

$$\text{Maximize}\quad \sum\limits_{j \in U} {\sum\limits_{k \in N} {W_{jk} w_{k} x_{{a_{j} jk}} } }$$

(1)

s.t.

$$\sum\limits_{k \in N} {x_{{a_{j} jk}} } = 1,\quad \forall j \in U$$

(2)

$$x_{ijk} = 0,\quad \forall i \in S,\quad \forall j \in U,\quad \forall k \in N|(i < a_{j} ) \vee (i \ge g_{j} )$$

(3)

$$\sum\limits_{j \in U} {x_{ijk} \, \le 1,} \quad \forall i \in S,\quad \forall k \in N$$

(4)

$$\sum\limits_{{i \in S|a_{j} \le i < g_{j} }} {x_{ijk} = (g_{j} - a_{j} )x_{{a_{j} jk}} ,} \quad \forall j \in U,\quad \forall k \in N$$

(5)

$$\begin{aligned} & x_{ijr} + x_{ibk} \le 1,\quad \forall i \in S,\forall j,b \in U,\forall k,r \in N|(j < b) \\ & \quad \wedge [(a_{j} \le i < g_{j} ) \vee (a_{b} \le i < g_{b} )]^{ \wedge } (f_{j} \ne f_{b} ) \\ & \quad \wedge (L_{kr} = 1) \wedge [(a_{b} \le a_{j} \wedge g_{b} > \, a_{j} ) \vee (a_{j} \le a_{b} \wedge g_{j} > \, a_{b} )] \\ \end{aligned}$$

(6)

$$x_{{a_{j} jk}} = 0,\quad \forall j \in Y,\quad \forall k \in M$$

(7)

$$x_{{a_{j} jk}} = 0,\quad \forall j \in U,\quad \forall k \in D|a_{j} \le {\text{t}}_{k}$$

(8)

$$x_{{a_{j} jk}} \le B_{jk} ,\quad \forall j \in U,\quad \forall k \in N$$

(9)

$$x_{ijk} \in \{ 0,1\} \quad \forall j \in U,\quad \forall i \in S,\quad \forall k \in N$$

(10)

Objective function (1) maximizes total utility of flight-gate assignment plan which is a product of the utility (importance) of a gate the utility of a flight being assigned to that gate. Constraints (2) ensure that each flight is assigned to exactly one gate at its arrival time. Constraints (3) forbid assigning a flight to a gate before its arrival and after its departure. Note that if a flight’s arrival and departure times are a_j and g_j respectively, the plane of that flight will occupy that gate from start of a_j to the start of g_j. For example, assume that a flight’s (e.g., flight 7) arrival and departure times are 64th and 72nd time periods, respectively. Then, the corresponding Gantt chart for the assigned gate (e.g., gate 29) will be as in the following (see Fig. 1).

Fig. 1

Partial schedule of Parking Area 29 between the beginning of 64th and 72nd periods

All binary variables corresponding to periods between 64 (included) and 72 (excluded) equal 1 in the solution and others 0.

$$\sum\limits_{{i = a_{j} \, (i = 64)}}^{{g_{j} - 1 \, (72 - 1 = 71)}} {x_{i,7,29} } = (g_{7} - a_{7} )x_{64,7,29} \quad x_{64,7,29} + x_{65,7,29} + \cdots + x_{71,7,29} = 8 = 72 - 64$$

In other words, if a flight arrives in period i, it indicates that the assigned gate is used (i.e., occupied by that plane) in between i and i + 1. Constraints (4) ensure that a parking area is occupied by at most one flight at any period. Constraints (5) guarantee that the same parking area is used during the service period of the flight [see the above numerical example given for constraints (3)]. Since the variable is equal to 1 for only one gate [due to constraints (2)], right hand side of constraints (5) will be equal to the service period of the flight for only the assigned parking area. And in that case, left hand side of the constraint will enforce that sum of the binary assignment variables in the consecutive periods will be equal to the service time period. Similarly, if flight j is not assigned to parking area k at its arrival period a_j, right hand side of the constraint (5) will be “0” and therefore enforce that the sum of the binary variables for the next consecutive periods during the service period will be equal to zero. In other words, that flight cannot be assigned to those periods. Note that this constraint is formulated for the periods between the arrival and departure times of the flight and is executed once for each flight and parking area when the period is equal to that flights’ arrival period. Constraints (6) ensure that any two flights that are served with different companies and their service periods overlap must be assigned to non-neighbour parking areas. Constraints (7) forbid assigning night-stand flights to bridge-equipped parking areas, while constraints (8) ensure that a parking area can’t be used before it becomes available. Constraints (9) guarantee that each flight is assigned to only eligible parking areas. Finally, constraints (10) give variable domain. Right hand side of Constraints (6) requires further explanation as in the following:

• $(j < b)$: Generate this constraint for flight numbers $j < b$. Do not generate for $j > b$.

• $[(a_{j} \le i < g_{j} ) \vee (a_{b} \le i < g_{b} )]$: Generate this constraint for the largest time interval from the earliest arrival to the latest departure of the flights j and b. In other words, i is within the following interval ${\text{min(}}a_{j} ,a_{b} )\le i < { \hbox{max} }(g_{j} ,g_{b} )$.

• $(f_{j} \ne f_{b} )$: Generate this constraint if and only if flights j and b belong to different ground service companies.

• $(L_{kr} = 1)$: Generate this constraint for only adjacent parking areas.

• $[(a_{b} \le a_{j} \wedge g_{b} > \, a_{j} ) \vee (a_{j} \le a_{b} \wedge g_{j} > \, a_{b} )]$: Generate this constraint if and only if flight j arrives while flight b is already in the airport and departure of b is later than arrival of j $(a_{b} \le a_{j} \wedge g_{b} > \, a_{j} )$ or vice versa $(a_{j} \le a_{b} \wedge g_{j} > \, a_{b} )$. This filtering guarantees that only overlapping periods are considered.

The proposed model is bounded with $|S|{\text{x}}|U|{\text{x}}|N|$ variables and $|S|{\text{x}}|U|^{2} {\text{x}}|N|^{2}$ constraints.

Next, we provide a time-tabling formulation based on the tuple concept. To prevent generating binary variables for non-eligible gates and the periods that the flight j does not stay in the airport, we define the following feasible parking period, flight and parking area triplets.

$z,z^{\prime }$ Index of all feasible period, flight and park assignment triplets,

$$\begin{aligned} & z,z^{\prime } \in Assignments \subset S \times U \times N \, \\ & \quad = \left\{ \begin{aligned} &< period,flight,park > ,\quad \, \forall period \in S,\quad \forall flight \in U,\quad \forall park \in N\left| {} \right. \hfill \\ &(a_{flight} \le period < g_{flight} ) \wedge (B_{flight,park} = 1) \wedge \neg (flight \in Y \wedge park \in M) \wedge \hfill \\ &\neg (park \in D \, \wedge \, a_{flight} \le \, t_{park} ) \hfill \\ \end{aligned} \right\} \\ \end{aligned}$$

where $z \cdot period,z \cdot flight{\text{ and }}z \cdot park$ refer to the allowed period, flight and park indices for the corresponding assignment triplet $z$, respectively. The filters used to create only feasible triplets are explained as follows.

• $(a_{flight} \le period < g_{flight} )$: A feasible assignment variable (triplet) is generated for each flight at each park for each period interval while the corresponding flight is being served on the ground. In other words, (g_j-a_j) assignment triplets are generated for each eligible parking area to represent duration of stay for each flight.

• $B_{flight,park} = 1$: Only eligible flight-parking area tuples are generated.

• $\neg (flight \in Y \wedge park \in M)$: Any flight-parking area assignment is excluded if the flight is a night-stand one and the corresponding parking area is bridge-equipped.

• $\neg (park \in D \, \wedge \, a_{flight} \le \, t_{park} )$: Any flight-period-parking area assignment is excluded if the parking area has been occupied from the previous day until it becomes available.

Feasible triplets generated in Assignments set are demonstrated in the following table for two flights.

Based on these feasible triplets $z \in Assignments$, we introduce binary variables for each of them to be used in the Timetabling based model formulation.

$$x_{z} = \left\{ {\begin{array}{*{20}l} 1 & {If z \cdot flight\;is\;assigned\;to\;z \cdot park\;in\;period\;z \cdot period} \\ 0 & {o/w} \\ \end{array} } \right.$$

Timetabling Based IP model

$$Maximize\; \, \sum\limits_{{z \in Assignments|z.period = a_{z\cdot flight} }} {W_{z\cdot flight,z.park} w_{z.park} x_{z} }$$

(11)

Subject to

$$\sum\limits_{{z \in Assignments|(z\cdot flight = j) \wedge (z.period = a_{j} )}} {x_{z} } = 1\quad \forall j \in U$$

(12)

$$\sum\limits_{z \in Assignments|(z \cdot period = i) \wedge (z \cdot park = k)} {x_{z} \, \le 1} \quad \forall i \in S,\quad \forall k \in N$$

(13)

$$\begin{aligned} & \sum\limits_{{z^{\prime } \in Assignments|(z^{\prime } \cdot flight = z \cdot flight) \wedge (z^{\prime } \cdot park = z \cdot park) \wedge (a_{z\cdot flight} \le z^{\prime } \cdot period < g_{z \cdot flight} )}} {x_{{z^{\prime } }} = (g_{z \cdot flight} - a_{z \cdot flight} )x_{z} } \\ & \quad \forall z \in Assignments|z \cdot period = a_{z \cdot flight} \, \\ \end{aligned}$$

(14)

$$\begin{aligned} & x_{z} + x_{{z^{\prime } }} \le 1\quad \forall z,z^{\prime } \in Assignments\left| {(z \cdot flight < z^{\prime } \cdot flight) \wedge (z \cdot period = z^{\prime } \cdot period) \wedge } \right. \\ & (f_{z \cdot flight} \ne f_{{z^{\prime } \cdot flight}} ) \wedge (L_{{z \cdot park,z^{\prime } \cdot park}} = 1) \wedge \\ & [(a_{{z^{\prime } \cdot flight}} \le a_{z \cdot flight} \wedge g_{{z^{\prime } \cdot flight}} > \, a_{z \cdot flight} ) \vee (a_{z \cdot flight} \le a_{{z^{\prime } \cdot flight}} \wedge g_{z \cdot flight} > \, a_{{z^{\prime } \cdot flight}} )] \\ \end{aligned}$$

(15)

$$x_{z} \in \{ 0,1\} \quad \forall z \in Assignments$$

(16)

Objective function (11) maximizes total utility of flight-gate assignment plan. Constraints (12) assign each flight to exactly one gate at its arrival time. Constraints (13) ensure that a parking area is occupied by at most one flight at any period. Constraints (14) guarantee that the same parking area is used during the service period of the flight. Since $x_{z}$ variable is equal to “1” for only one parking area, [due to constraints (12)], right hand side of constraint will be equal to the service period of the flight for only the assigned parking area. And in this case, left hand side of the constraint will enforce that sum of the binary assignment variables in the consecutive periods will be equal to the total number of service time for the assigned parking area z.park. Similarly, if corresponding flight z·flight is not assigned to the corresponding parking area z.park at its arrival period $a_{z\cdot flight}$ (which is also equal to the $z \cdot period$ due to the constraint filtering), right hand side of the constraint (14) will be “0” and therefore it enforces that the sum of the binary variables for the next consecutive periods during the service period will be equal to zero for the corresponding parking area z.park. In other words, flight z·flight cannot be assigned to periods between $[a_{z \cdot flight} ,g_{z \cdot flight} ]$. The following example demonstrates the use of the constraint where flight 7 is assigned to parking area 29 when it arrived to the airport at the beginning of period 64 and scheduled to take off at period 71. Note that, due to the flight safety, we assume that the parking area is occupied by the same aircraft during the period of take-off and therefore, we assume take-off period of flight 7 as 72nd period. Hence, parking area 29 is available to a new flight at the beginning of period 72. In other words, parking area 29 is occupied by flight 7 during time interval (64, 72). Partial schedule of parking area 29 is demonstrated in Fig. 1.

Flight 7 starts using parking area 29 at the beginning of period 64, i.e. its scheduled arrival period. Hence, corresponding binary variable which shows the assignment of flight 7 to parking area 29 at the beginning of period 64 is equal to 1 ($x_{ < 64,7,29 > } = 1$). Note that, $x_{ < 64,7,29 > } = 1$ assignment also means that parking area 29 is used by flight 7 from the beginning to the end of the 64th period. Since the parking area is occupied by flight 7 during the next 8 periods (g_j–a_j = 72–64 = 8), corresponding binary variables for those periods are also equal to 1 due to constraints (4).

$x_{ < 64,7,29 > } + x_{ < 65,7,29 > } + \cdots + x_{ < 71,7,29 > } = \left( {g_{7} - a_{7} } \right)x_{ < 64,7,29 > }$$\sum\nolimits_{{i = a_{7} }}^{{g_{7} }} {x_{ < i,7,29 > } } = \left( {g_{7} - a_{7} } \right)x_{ < 64,7,29 > }$ which means $\sum\nolimits_{i = 64}^{72} {x_{ < i,7,29 > } } = \left( {72 - 64} \right)x_{ < 64,7,29 > }$ or $\sum\nolimits_{i = 64}^{72} {x_{ < i,7,29 > } } = 8x_{ < 64,7,29 > }$. This equation holds if and only if $x_{ < 64,7,29 > } = x_{ < 65,7,29 > } = \cdots x_{ < 71,7,29 > } = 1$ or 0. If a feasible solution results that the flight 7 is assigned to parking area 29 at its arrival ($x_{ < 64,7,29 > } = 1$), all consecutive binary variables in the equation are also equal to 1 ($x_{ < 64,7,29 > } = x_{ < 65,7,29 > } = \cdots = x_{ < 71,7,29 > } = 1$). Constraints (14) also guarantee that if flight 7 is not assigned to parking area 29 at its arrival period ($x_{ < 64,7,29 > } = 1$), all other consecutive binary variables on this parking area are also equal to 0, $x_{ < 64,7,29 > } = x_{ < 65,7,29 > } = \cdots = x_{ < 71,7,29 > } = 0$.

Constraints (15) ensure that for any two possible assignments, if time periods are overlapping and corresponding ground service companies are different, they are assigned to non-adjacent parking areas. Right hand terms that are used to filter possible assignment tuples to be constrained in inequality (15) are explained in the following:

• $z \cdot flight < z' \cdot flight$: Prevents comparing any two flights twice.

• $z \cdot period = z' \cdot period$: Ensures that constraints are generated for periods such that both flights are in the airport.

• $f_{z \cdot flight} \ne f_{z' \cdot flight}$: Guarantees that constraints are generated if ground service companies of the corresponding flights are different.

• $L_{z \cdot park,z' \cdot park} = 1$: States that constraints are generated if and only if parking areas of the corresponding assignments are adjacent.

• $[(a_{z' \cdot flight} \le a_{z \cdot flight} \wedge g_{z' \cdot flight} > \, a_{z \cdot flight} ) \vee (a_{z \cdot flight} \le a_{z' \cdot flight} \wedge g_{z \cdot flight} > \, a_{z' \cdot flight})]$: These two possible assignments are considered in the constraint if and only if flight z·flight arrives while $z'\cdot flight$ has been already in the airport or vice versa.

Finally, constraints (16) give variable domains. Note that, due to the filtering in the definition of the allowed assignments, we do not need to include original constraints (3), (7), (8) and (9) in the tuple formulation.

2.2 Assignment based integer programming model

In the second alternative IP model formulation, to reduce the number of binary variables, we define binary variables for only those periods where corresponding flights arrive at the airport. Before giving the new IP model, we introduce re-defined sets, indices and variables as in the following.

$z,z^{'}$ Index of all feasible flight, park, period assignment triplets,

$$\begin{aligned} & z,z^{'} \in Assignments \subset S \times U \times N \, = \\ & \quad \left\{ \begin{aligned} &\\ &< period,flight,park > ,\quad \forall period \in S,\quad \forall flight \in U,\quad \forall park \in N\left| {} \right. \hfill \\& (period = a_{flight} ) \wedge (B_{flight,park} = 1) \wedge \neg (flight \in Y \wedge park \in M) \, \wedge \hfill \\& \neg (park \in D \, \wedge \, a_{flight} \le \, t_{park} ) \hfill \\ \end{aligned} \right\} \\ \end{aligned}$$

As stated in $(period = a_{flight} )$ filtering operator, a single <period, flight, park> triplet is created for each flight and parking area. Changes in the revised Assignments set compared to Table 1 is demonstrated in the following table where feasible triplets are generated for each flight and eligible parking area for only the arrival period of the flight (Table 2).

Table 1 Feasible assignment triplets for two flights

Table 2 Revised feasible assignment triplets for two flights

Furthermore, we need the following set to formulate constraints for occupying the same parking area during the duration of stay for each flight.

$h$: Index of feasible flight-park pairs.

$$h \in FlightParkPairs = \{ < z \cdot flight,z \cdot park > \} ,\quad \forall z \in \, Assignments\}$$

Finally, we redefine the binary variables as:

$$x_{z} = \left\{ {\begin{array}{*{20}l} 1 & {If\;flight\;z \cdot flight\;is\;assigned\;to\;park\;z \cdot park\;at\;its\;arrival, z \cdot period} \\ 0 & {\text{o/w}} \\ \end{array} } \right.$$

Based on the redefined sets and variables, the assignment based IP model is formulated as in the following:

$$Maximize\;\sum\limits_{z \in Assignments} {W_{z \cdot flight,z \cdot park} w_{z \cdot park} x_{z} }$$

(17)

subject to

$$\sum\limits_{z \in Assignments|(z \cdot flight = j)} {x_{z} } = 1\quad \forall j \in U$$

(18)

$$\begin{aligned} & \sum\limits_{z \in Assignments|(z\cdot flight \ne j) \wedge (z.period = i) \wedge (z.park = k)} {x_{z} } \le \left| U \right|(1 - x_{{ < a_{j} ,j,k > }} ) \\ & \quad \forall i \in S,\forall j \in U,\forall k \in N\left| { < j,k > \, in \, FlightParkPairs \wedge (a_{j} \le i < g_{j} ) \, } \right. \\ \end{aligned}$$

(19)

$$\begin{aligned} & \sum\limits_{{z^{\prime } \in Assignments|(z^{\prime } \cdot flight \ne z \cdot flight) \wedge (i = z^{\prime } \cdot period) \wedge (f_{{z^{\prime } \cdot flight}} \ne f_{z \cdot flight} ) \wedge (L_{{z^{\prime } \cdot park,z \cdot park}} = 1)}} {x_{{z^{\prime } }} \le \left| U \right|(1 - x_{z} )} \\ & \quad \forall i \in S,\quad \forall z \in Assignments\left| {a_{z \cdot flight} \le i < g_{z \cdot flight} } \right. \\ \end{aligned}$$

(20)

and constraints (13) and (16).

Constraints (17), (18) (19), (20), are reformulation of constraints (11), (12), (14), and (15) respectively. Constraints (13) and (16) given in the Timetabling model are used as given in the timetabling based model just with redefined Assignments set. Note that the cardinality of the set of flights,|U| is used as big-M in linearization of constraints (19) and (20).

2.3 Scheduling based constraint programming model

Although IP models developed in the previous sections capture the problem with all aspects, they suffer from scalability issues. However, constraint programming (CP) is a powerful alternative to model and solve complex problems such as over-constrained flight-gate assignment problem. Reader may refer to Ornek and Öztürk (2016) for detailed comparison and application of CP and IP methods in planning and scheduling.

In this section, due to its time dependent nature, we develop a scheduling based CP model for the problem. Since the formulation of the CP models is basically related to the software system used, we represent our variables and constraints with CP Optimizer (IBM 2017) constructs that are used to implement and solve the problem.

Flights in this problem are defined as intervals $\alpha_{j} , \, j \in U$. Each interval $\alpha_{j}$ is associated with three variables as $endOf(\alpha_{j} ),startOf(\alpha_{j} )$ and $sizeOf(\alpha_{j} )$ which represents the end, start and duration of stay in the airport for each flight respectively. All these variables are ranging in $\left[ {a_{j} ,g_{j} } \right)$. As described in (IBM, 2017), an important property of interval variables is that they can be designed as optional which means that they might not occur in the solution and may not be considered. Since each eligible parking area is an alternative for each flight, $\alpha_{j}$ interval variables may be performed in any of them. Therefore, we also define optional interval variables $\beta_{h}$ for each feasible flight park assignment pair $h \in FlightParkPairs$ defined for the Assignment based IP model formulation in the previous section.

Since each flight interval has to be processed on one of its eligible parking areas, $k \in N$, parking areas are defined as disjunctive resources $\gamma_{k}$ which can be used by at most one flight at a time. Each sequence $\gamma_{k}$ is a collection of all corresponding optional flight intervals. More formally, $\gamma_{k} = \left\{ {B_{h} ,h \in FlightParkPairs\left| {h.park = k} \right.} \right\}$. Note that disjunctive resources such as parking areas in this paper are defined as “sequence” in CP Optimizer (IBM 2017).

In addition to the interval and sequence variables, we define a final integer variable $park_{j} \in N$ which indicates the parking area of flight $\, j$ assigned to. Finally, we define additional sets and indices used in the formulation of CP model and the search strategy as follows:

• $parkOfFlight_{j} = \{ k| < j,k > \in FlightParkPairs\}$: the set of all eligible parking areas for flight j.

• $forbiddenParkOfFlight_{j} = N - parkOfFlight_{j}$: the set of non-eligible parking areas for flight j.

• $averageUtilityOfFlight_{j} = (\sum\nolimits_{k \in N} {W_{jk} } )/\left| {parkOfFlight_{j} } \right|$: the average utility of each flight.

  Before formulating our problem, we introduce global constraints that are provided by CP Optimizer and used in this paper. See (IBM 2017) for further details.

• $alternative(interval\left( \alpha \right) , { }set of optional intervals\left( \beta \right))$: This global constraint models that if interval $\alpha$ present, then exactly one of intervals in the interval $\beta$.

• $allowedAssignments(set of integer values, set of integer variables)$: It is used to define the allowed combinations of values for several integer decision variables.

• $forbiddenAssignments(set of integer values, set of integer variables)$: Similarly, this global constraint is used to define the forbidden combinations of values for several integer decision variables.

• $noOverlap(sequence)$: This global constraint is used to formulate disjunctive nature of sequences and prevents overlapping of the intervals in the sequence.

• $presenceOf({\text{optional interval}})$: This global constraint is used to capture existence of an optional interval.

• $forbidStart(interval variable, forbidden interval)$: This global constraint ensure that a given interval variable cannot be started during the forbidden interval.

The CP model of the problem is formulated as in the following:

$$maximize\quad \sum\limits_{j \, in \, U} {W_{{j,park_{j} }} w_{{park_{j} }} }$$

(21)

subject to

$$allowedAssignments(parkFlight_{j} park_{j} ) \, \quad \forall j \in U$$

(22)

$$forbiddenAssignments(forbiddenParkOfFlight_{j} ,park_{j} )\quad \forall j \in U$$

(23)

$$noOverlap(\gamma_{k} )\quad \forall k \in N$$

(24)

$$alternative(\alpha_{j} ,all(h \, in \, FlightParkPairs:h\cdot flight = j)\beta_{h} )\quad \forall j \in U$$

(25)

$$\begin{aligned} & presenceOf(\beta_{ < j,k > } ) \wedge presenceOf(\beta_{ < b,r > } ) \Rightarrow \\ & (endOf(\alpha_{j} ) \le startOf(\alpha_{b} )) \vee \\ & (endOf(\alpha_{b} ) \le startOf(\alpha_{j} )) \\ & \forall < j,k > , < b,r > \, in \, FlightParkPairs|(j < b) \wedge (f_{j} \ne f_{b} ) \\ & \wedge (L_{kr} = 1) \wedge [(a_{j} \le a_{b} \wedge g_{b} > a_{j} ) \vee (a_{b} \ge a_{j} \wedge g_{j} > a_{b} )] \\ \end{aligned}$$

(26)

$$forbidStart\left( {\beta_{h} ,\left[ {0,t_{k} } \right)} \right)\quad \forall h \in FlighParkPairs\left| {h \cdot park \in D \wedge a_{h\cdot flight} \le t_{k} } \right.$$

(27)

Objective function (21) is a reformulated version of the total utility given in (11) and (17). Note that we use variable indexing feature of CP formulation, which enhances the problem representation where $park_{j}$ returns the index of the parking area used by flight j. Constraints (22) and (23) define and prune domains of parking area variables for each flight respectively. Constraints (24) prevent overlapping of flight interval variables for each parking area k. Recall that $\gamma_{k}$ is the collection of all optional flight interval variables that can be assigned to parking area k. Constraints (25) map each flight interval variable to all optional interval variables and guarantee that for each flight interval $\alpha_{j}$, exactly one of the alternative $\beta_{h}$ intervals is selected. Constraints (26) ensure that any two optional interval flight variables cannot be served in adjacent parking areas at the same time if they belong to the different ground services. If they are assigned to adjacent parking areas, one has to be finished before starting the other. Finally constraints (27) prevent starting of any optional interval variable before the assigned parking area becomes available.

A well-designed and customized search strategy greatly affects the performance of a CP model (Dechter 2003). Hence, we employ a two-phase search strategy for variable (i.e., ordering the variables to branch on in the search tree) and value ordering (the order of value to be instantiated to the selected variable). In the first phase, we start searching with selecting a flight with minimum number of parking areas in its domain (i.e., fail-first). Then we assign the selected flight to an eligible parking area with maximum utility $w_{k}$ in favor of the objective function. Once the parking variable is instantiated, in the second phase, we select a parking area (i.e., sequence) with maximum number of possible flight that can be assigned to and select a flight with maximum average utility $averageUtilityOfFlight_{j}$. See (IBM ILOG CPLEX Optimization Studio 2017) for details on implementation of search phases.

3 Performance evaluation of the models and a numerical example

In this section, we provide results of implementing developed models by a real case and three more synthetically generated instances. Before presenting the numerical results, in the following table, we compare the size of the proposed models in terms of theoretical bounds in the number of variables and constraints.

As shown in Table 3, while the number of variables depends on the duration of a stay of a flight in Timetabling based IP model, it is independent from this parameter in Assignment based IP model and Scheduling based CP model. Note that the number of variables in the developed CP model is bounded with $\left| U \right|\left| N \right| + \left| U \right| + \left| N \right|$ of which $\left| U \right|\left| N \right|$ are optional interval variables ($\beta_{h}$), $\left| N \right|$ are sequence variables ($\gamma_{k}$) and $\left| U \right|$ are parking area assignment variables (park_j). The developed models are tested using a realistic size instance provided by a main airline operator in Turkey with 35 parking areas, 19 of which are bridge-equipped, 105 flights, and four different ground service companies. Models have been run on a Windows 7 64 bit machine with 8 GB RAM and Intel i7 processor. IBM CPLEX 12.6 has been used to implement and solve the proposed formulations, which includes IBM CPLEX and IBM CP optimizer to solve integer and constraint programming models respectively. Performances of the developed models are summarized in Table 4.

As seen in Table 4, both Timetabling and Assignment based IP models are able to find the optimal solution in very short time. Although theoretical bounds for the Timetabling and Assignment models are the same as reported in Table 3, instance based reported number of variables and constraints in Table 4 are different. Because; solver’s pre-solver tries to reduce the size of the problem by making inferences about the nature of the problem and as both Timetabling and Assignment based models are formulated differently, CPLEX presolve aggregator eliminates different number of columns and rows and results different number of variables and constraints (https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/CPLEX/UsrMan/topics/cont_optim/simplex/15_preprocess.html).

Table 3 Theoretical bounds for the size of the models

Table 4 Performance evaluation of the developed models on a real size instance where * indicates optimal solution

Although it has the power of expressing complicated constraints efficiently, Scheduling based CP model has lack of ability to use LP relaxation in the search tree (Öztürk et al. 2013) and therefore, it couldn’t improve the best solution found in 30 min within 4 h. Another reason that CP model is not able to find the optimal solution is the number of symmetric solutions which returns the same objective function value with different value assignment to variables. Table 4 obviously shows this fact with almost one magnitude more number of solutions found in Scheduling based CP model.

Furthermore, to evaluate performance of aforementioned models in different settings we generated three more synthetic instances (n = 1, 2, 3) by changing duration of stay for each flight by an amount of between ± Kⁿ% where Kⁿ $\in Z$ varies between 3, 5 and 10 percent for each of three instances respectively. In short, random duration of stays has been generated for each flight in each instance as in the following formula.

$$g_{j}^{n} = a_{j} + \left( {g_{j} - a_{j} } \right)\left[ {1 + {{uniform\left( { - K^{n} ,K^{n} } \right)} \mathord{\left/ {\vphantom {{uniform\left( { - K^{n} ,K^{n} } \right)} {100}}} \right. \kern-0pt} {100}}} \right]\quad \forall j \in U,\forall n \in \left\{ {1,2,3} \right\},K^{1} = 3,K^{2} = 5,K^{3} = 10$$

The results of the additional experiments are provided in the following tables.

Although both theoretical and instance based results show that there are more variables and constraints in Timetabling based IP formulation, it was expected to have tighter bounds in Timetabling based IP model since it might lead a stronger LP-relaxation due to not relying on big-M based constraints. However, in practice, assignment based model creates a smaller branch and bound tree to be traversed as it requires at least one order of magnitude less number of variables and constraints. This is why Assignment based IP model reaches optimal solution much faster than the Timetabling based IP model. It is also interesting to note that even though we introduce 3% and 5% average deviation from the initial duration of stay in the real data in first two synthetic instances, the models are able to assign flights to the same utility valued gates and hence returns the same objective function value.

Although its lack of finding optimal solution, proposed constraint programming method gives a strong baseline for simply adding new business rules emerging from airports’ operational needs as constraints. Furthermore, for larger size instances, constraint programming model serves as a quick solution finder for a heuristic framework like large neighborhood search. Indeed, results presented in Tables 4, 5, 6 and 7 shows that CP model is able to traverse wider solution space with large number of solutions found which indicates it can be used as a good constructive solution finder in such heuristic frameworks to escape from local optima. It is noteworthy that as in the initial experiments with real data; we limit CP experiments with synthetic data with 30 min.

Table 5 Performance evaluation of the developed models on randomly generated instance (n = 1, K¹ = 3) where * indicates optimal solution

Table 6 Performance evaluation of developed models on randomly generated instance (n = 2, K² = 5) where * indicates optimal solution

Table 7 Performance evaluation of the developed models on randomly generated instance (n = 3, K³ = 10) where * indicates optimal solution

Instance data and detailed results are provided in “Appendix 1”.

4 Conclusions and further research

With the increase in the intensity of air-traffic in recent years, the management of airport gates has become more important and complicated. This is simply because improper assignment of gates to incoming and outgoing flights may result in flight delays, customer dissatisfaction, and increase in operational costs. As a result, many studies have been undertaken to efficiently use these resources.

In this paper, we propose two IP models and a CP model to solve a highly complicated and over-constrained fight-gate assignment problem to optimality. IP models are able to find the optimal solution in about 100 s, whereas CP model terminates after 1800 s with a near optimal solution. However, this does not imply that IP models are superior to CP model, but points out that CP model is to be revised in terms of search methods. Nevertheless, CP model in this study is one of the pioneering attempts to tackle these types of problems in literature.

For further research directions, two studies are in progress. The first one is to hybridize IP and CP utilizing their powerful properties and the second one is to develop a heuristic algorithm for companies that do not own commercial optimization solvers. Hybridizing a constraint programming based multi-dimensional placement model formulation with large neighborhood search meta-heuristic seems to be a promising and challenging area of interest, too. Application of those hybrid methods to different combinatorial problems arising in airports, such as airline boarding problem (Soolaki et al. 2012) is also a challenging research direction. Evaluating different search heuristics on different CP formulations of the problem could be an important research direction too, as well as symmetry breaking constraints for traversing the search tree faster. Furthermore, incorporating multiple stake holders (airlines, airport authority, ground handlers etc.) into the optimization framework within a distributed manner using distributed constraint programming methods (Rolf and Kuchcinski 2011) is a quite promising research direction for holistic improvement of airport operations as well as multi-objective nature of the problem under full or limited information sharing conditions.

Appendix 1: numerical results

See Tables 8 and 9.

Table 8 The arrival, original departure and departure with extra periods of the flights and the ground service data of flights

Table 9 The optimal assignment of flights on each gate for the Timetabling based integer programming model