Multi-Objective Airport Slot Allocation with Demand-Side Fairness Considerations

Abstract

Airport slot allocation is a key short-term solution to address airport capacity constraints, and it has long been a focus of research in the field of air traffic management. The existing studies primarily consider constraints such as airport capacity and flight operations, optimizing the slot allocation of arrival and departure flights to maximize the utilization of airport resources. This study proposes an airline fairness index based on a demand-side value system and addresses the problem of flight slot allocation by developing a tri-objective model. The model simultaneously considers the maximum slot deviation, total slot deviation, and airline fairness. Additionally, dynamic capacity constraints using rolling time windows and constraints on slot migration during peak periods are incorporated. The $\epsilon$-constraint method is employed in conjunction with a large-neighborhood search heuristic to solve a two-stage optimization process, yielding an efficient allocation scheme. The experimental results show that the introduction of rolling capacity constraints effectively resolves the issue of continuous overcapacity that arises when only a fixed capacity is considered. Additionally, the proposed airline fairness index, based on a demand-side value system, can significantly improve fairness during the slot allocation process. By sacrificing at most 16% of the total displacement, it is possible to reduce the unfairness index by nearly 80%.

1. Introduction

In recent years, the rapid growth in air transport demand, coupled with insufficient airport capacity, has led to a pronounced imbalance between airport services and resources. According to statistics, as of 2022, there were 198 slot-coordinated airports globally, accounting for approximately 6% of the total number of airports but handling 50% of the world’s air transport services. However, the flight demand at most major airports has consistently exceeded the airport capacity according to the International Air Transportation Association (IATA) Worldwide Slot Guidelines (WSGs), leading to issues such as congestion and flight delays that place significant cost pressures on airports, airlines, and passengers [1]. In the short term, it is not feasible to resolve this imbalance through airport infrastructure expansion. Therefore, slot coordination and allocation are essential for optimally distributing flight slots to airlines. Most airports have adopted the slot allocation methods proposed by the IATA for coordinated airports to help alleviate this imbalance. At coordinated airports, the airport announces the available airport capacity, typically in terms of hourly and 15 min capacities. These capacities represent the number of aircraft that can land or take off within a given time period and are referred to as “slots”. Prior to the start of the scheduling season, airlines submit slot requests based on their operational needs, specifying the desired routes and time slots. These requests are submitted over a defined period and often follow a weekly pattern. The slot coordinator evaluates these requests in accordance with the declared capacity and priority rules, adjusts the allocations as needed, and then publishes the finalized slot schedule.

Currently, the methods for flight slot allocation can be divided into two forms: administrative allocation and market-based allocation. The administrative approach is the predominant method used by most countries and regions worldwide, where slot management authorities coordinate and allocate airport flight slots based on specific rules. Airport slot allocation (ASA) aims to manage scarce slot resources by matching airline requests with the available slots assigned by airports. Flight slot allocation is a resource-constrained allocation problem and serves as an important tool for demand management at airports, making it a key research focus in both domestic and international air transport studies. The allocation process generally begins with airlines submitting semi-annual requests, followed by coordinators assigning slots according to airport capacity. The complex web of stakeholders involved—including airlines, airports, air traffic control, and passengers—makes slot allocation a highly complex combinatorial problem. Achieving efficient solutions while balancing the interests of all parties remains a significant challenge.

Traditional studies on single-airport slot allocation tend to focus on a limited aspect of fairness. Our research aims to explore whether a more efficient and fair slot allocation scheme can be achieved by considering multi-dimensional fairness objectives within algorithmic and model design. Therefore, our research proposes a novel tri-objective model that simultaneously considers maximum slot displacement, total slot displacement, and airline fairness. By integrating dynamic capacity constraints and introducing a demand-side fairness metric, we offer a more efficient and equitable slot allocation approach. The model is solved using a large-neighborhood search heuristic algorithm, which effectively handles the computational challenges posed by rolling capacity constraints.

The remaining chapters of this paper are divided into five sections. Section 2 discusses the research related to airport slot allocation. Section 3 and Section 4 present the three-objective model and its solution methods, respectively. Section 5 outlines the experimental environment, results, and analysis. Section 6 concludes the paper, discussing the validity of the experimental results and future research directions.

2. Literature Review

Airport slot allocation is a critical issue in the aviation industry, especially at congested airports where demand exceeds capacity [2]. The efficient utilization of slots is essential to maximize system benefits and ensure fair competition in the downstream air transport market [3,4,5]. As airport capacity demand continues to grow, the need for efficient slot allocation mechanisms has become increasingly urgent [5]. The current research on airport slot allocation focuses on various aspects, including market liberalization, dynamic optimization frameworks, incentive-based slot allocation, and multi-objective and multi-level considerations in slot scheduling [6,7,8,9]. Moreover, studies advocate for the incorporation of fairness, resource utilization, and environmental factors into slot scheduling models to improve airport capacity usage [10]. Recent research has proposed decision frameworks that prioritize fairness in slot allocation at capacity-constrained airports, aiming to balance minimal delays with maximum efficiency [11,12]. Additionally, multi-objective flight scheduling models based on absolute fairness have shown promising results in enhancing slot allocation equity across multi-airport systems [13]. Overall, the literature on fair airport slot allocation emphasizes the importance of efficient mechanisms that address multiple objectives, such as demand revelation, competition, fairness, and environmental sustainability, to tackle the challenges posed by growing airport capacity demands [14,15,16].

Airport slot allocation optimization approaches have been a topic of interest in the field of air traffic management. Le et al. [17] introduced an auction-based slot allocation framework that considers factors such as monetary bidding, flight origin–destination pairs, enplanement capability, and airlines’ previous investments. This approach enables various design alternatives and ongoing research on a hybrid demand management approach for congested airports. Vaze and Barnhart [18] proposed a game-theoretic model for airline frequency competition under slot constraints, showing that a small reduction in allocated slots can lead to significant reductions in flight and passenger delays, as well as improvements in airlines’ profits. The goal of [19] was to comprehensively consider efficiency and fairness in slot scheduling and propose a collaborative optimization model that takes into account both airline fairness and airport fairness. Moreover, [20] expanded the environmental benefit analysis from the traditional temporal dimension to the temporal–spatial dimension, focusing on airport slot scheduling and noise pollution issues. Corolli et al. [21] addressed the time slot allocation problem under uncertain capacity, highlighting the challenges of uncertainty in capacity planning. Zografos et al. [9] emphasized the importance of optimum slot scheduling for increasing airport capacity utilization, suggesting that future slot scheduling models should consider fairness, equity, resource utilization, and environmental factors. Ribeiro et al. [22] presented an optimization approach for airport slot allocation under IATA guidelines, focusing on efficient slot allocation strategies. Overall, a review of the literature indicates a growing interest in optimizing airport slot allocation through various approaches, such as auction-based frameworks, game-theoretic models, and optimization algorithms. Future research in this area may explore new objectives for slot scheduling models, consider uncertainties in capacity planning, and incorporate fairness and environmental considerations into slot allocation strategies.

Fairness has been defined in various ways in slot allocation research. For instance, Zografos and Jiang [23] defined fairness as ensuring that the total schedule displacement proportion allocated to an airline aligns with its proportion of requested slots. However, this approach treats all requests as equally important without considering the timing of the requests. Building on this, Fairbrother et al. [24] distinguished between peak and non-peak requests, acknowledging differences in slot value. Expanding on these concepts, this study employs demand as a flexible metric to quantify slot value. Furthermore, this study introduces a novel airline fairness metric based on demand-side values and develops a tri-objective model that incorporates maximum slot displacement, total slot displacement, and airline fairness. By considering dynamic capacity constraints and utilizing a large-neighborhood search algorithm, the proposed method not only improves allocation efficiency but also enhances fairness in the slot allocation process.

3. Slot Allocation Models with Three Objectives

This section introduces a three-objective slot allocation model that considers total displacement, maximum displacement, and airline fairness. To enhance the practicality of the model, several constraints are incorporated, including slot allocation priority constraints, rolling time window constraints, and slot removal time period restrictions. Additionally, the model accounts for commonly used capacity constraints over 1 h and 15 min intervals.

Table 1. Sets, parameters, and decision variables in the airport allocation model.

Sets
$T_1$	Minimum scale time series, $t\in T_1$
$T_{21}\left(T_{22}\right)$	Series for capacity, $T\in T_{21}$($T_{22}$)
$T_3$	Restricted time periods, $t\in T_3$
I	Request series, $i\in I$
$I_{arr\left(dep\right)}$	Requests for arrival (departure)
$I_{his(hc,new,os)}$	Requests by priority
R	Date series, $r\in R$
A	Airline consortium, $a\in A$
$P\subset I\times I$	$(a,b)\in P$
$Q=P\cap (I_{hc}\times I_{hc})$	$(a,b)\in Q$
$C(C_{arr},C_{dep})$	Airport capacity (takeoff and landing capacity) series
Parameters
$F_{it}$	0 if request $i\in I$ departs earlier than period $t\in T_1$; 1 otherwise.
$H_{it}$	0 if historic time of request $i\in I_{his}\cap I_{hc}$ is earlier than period t;
	1 otherwise.
$D_{ir}$	1 if request i departs on day r; 0 otherwise.
$C_T$	Airport capacity corresponding to time period T
$L_1$	Length of time interval $T_1$
$C_{tum}$	Rolling time window capacity
$L_{ct}$	Length of rolling time window
$\lambda$	Penalty coefficient
$n_{Air}$	Number of airlines
$N_a$	Number of requests applied by airline a
Decision Variables
$W_i$	1 if request i is allocated into the restricted time periods;
	0 otherwise.
$D{M}_i^{+}\left(D{M}_i^{-}\right)$	Forward (backward) displacement of request i
$Y_{it}$	0 if request i is allocated to depart earlier than period t;
	1 otherwise.
$G_i$	Loss value of request i
$x_a$	The average Loss value of airport a
$\overline{x}$	The average Loss value across all airports

presents the sets, parameters, and decision variables used in the model. $F_{it}$ and $D_{ir}$ represent the airlines’ requested times and dates, respectively, while $Y_{it}$ denotes the actual allocated time as the decision variable to be determined.

The proposed model is defined as follows:

$$minZ=\left\{\stackrel{Z_1}{\overbrace{\sum _{i\in I}\sum _{r\in R}(D{M}_i^{+}+D{M}_i^{-})D_{ir}}},\stackrel{Z_2}{\overbrace{max\left(D{M}_i^{-},D{M}_i^{+}\right)}},\stackrel{Z_3}{\overbrace{\sum _{a\in Air}{(x_a-\overline{x})}^2}}\right\}+\lambda \times W_i$$

(1)

$$\begin{array}{cccc}\hfill & Y_{i1}=1\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}& \hfill \forall i\in I\end{array}$$

(2)

$$\begin{array}{cccc}\hfill & Y_{it}⩾Y_{i,t+1}\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em} & \hfill \hspace{1em}\hspace{1em}\forall i\in I,t\in T_1\end{array}$$

(3)

$$\begin{array}{cccc}\hfill & \sum _{t\in T_1}(1-F_{it})Y_{it}=D{M}_i^{+}\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}& \hfill \forall i\in I\end{array}$$

(4)

$$\begin{array}{cccc}\hfill & \sum _{t\in T_1}(1-Y_{it})F_{it}=D{M}_i^{-}\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}& \hfill \forall i\in I\end{array}$$

(5)

$$\begin{array}{cccc}\hfill & D{M}_i^{+}=D{M}_i^{-}=0\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em} & \hfill \forall i\in I_{his}\end{array}$$

(6)

$$\begin{array}{cccc}\hfill & \sum _{i\in I_{arr}}\sum _{t\in (T,T+L_1)}(Y_{i,t}-Y_{i,t+1})\times D_{ir}⩽C_{arr,T}\hfill & \hspace{1em}\hspace{1em}\hspace{1em} & \hfill \forall T\in T_{21}(T\in T_{22}),r\in R,t\in T_1\end{array}$$

(7)

$$\begin{array}{cccc}\hfill & \sum _{i\in I_{dep}}\sum _{t\in (T,T+L_1)}(Y_{it}-Y_{i,t+1})\times D_{ir}⩽C_{dep,T}\hfill & \hspace{1em}\hspace{1em}\hspace{1em} & \hfill \forall T\in T_{21}(T\in T_{22}),r\in R,t\in T_1\end{array}$$

(8)

$$\begin{array}{cccc}\hfill & \sum _{i\in I}\sum _{t\in (T,T+L_1)}(Y_{it}-Y_{i,t+1})\times D_{ir}⩽C_T\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em} & \hfill \forall T\in T_{21}(T\in T_{22}),r\in R,t\in T_1\end{array}$$

(9)

$$\begin{array}{cccc}\hfill & \sum _{i\in I}\sum _{t\in (T,T+L_{ct})}(Y_{it}-Y_{i,t+1})\times D_{ir}⩽C_{tum}\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}& \hfill T\in T_1,r\in R\end{array}$$

(10)

$$\begin{array}{cc}\hfill & V_t={\alpha }_1{N}_t+{\alpha }_2(N_{t+L_1}+N_{t-L_1})\hfill \\ \hfill & +{\alpha }_3(N_{t+2L_1}+N_{t-2L_1})+{\alpha }_4(N_{t+3L_1}+N_{t-3L_1})\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}& \hfill \forall t\in T_1\end{array}$$

(11)

$$\begin{array}{cc}\hfill & G_i=\sum _{i\in I_a}\sum _{r\in R}(D{M}_i^{+}+D{M}_i^{-})D_{ir}+\hfill \\ \hfill & \min (V_t(Y_{it}-Y_{i,t+1}-F_{it}+F_{i,t+1}),0)D_{ir}\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}& \hfill \forall i\in I,t\in T_1\end{array}$$

(12)

$$\begin{array}{cccc}\hfill & x_a=\sum _{i\in I_a}{G}_i/N_a\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}& \hfill \forall a\in Air\end{array}$$

(13)

$$\begin{array}{cccc}\hfill & \overline{x}={\displaystyle \frac{{\sum }_{a\in Air}{x}_a}{n_{Air}}}\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}& \hfill \end{array}$$

(14)

$$\begin{array}{cccc}\hfill & \Delta F_{ab}=\sum _{t\in T_1}{F}_{bt}-F_{at}\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em} & \hfill \forall (a,b)\in P\end{array}$$

(15)

$$\begin{array}{cccc}\hfill & T_{min}⩽\sum _{t\in T_1}(Y_{bt}-Y_{at}-\Delta F_{ab})⩽T_{max}\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}& \hfill \forall (a,b)\in P\end{array}$$

(16)

$$\begin{array}{cccc}\hfill & \Delta H_{ab}=\sum t\in T_1(H_{bt}-H_{at})\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}& \hfill (a,b)\in Q\end{array}$$

(17)

$$\begin{array}{cccc}\hfill & \min (\Delta F_{ab},\Delta H_{ab})⩽\sum _{t\in T_1}(Y_{bt}-Y_{at})\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}& \hfill (a,b)\in Q\end{array}$$

(18)

$$\begin{array}{cccc}\hfill & \sum _{t\in T_1}(Y_{bt}-Y_{at})⩽\max (\Delta F_{ab},\Delta H_{ab})\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em} & \hfill (a,b)\in Q\end{array}$$

(19)

$$\begin{array}{cccc}\hfill & \sum _{t\in T_3}[(F_{it}-F_{i,t+1})-(Y_{it}-Y_{i,t+1})]=W_i\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em} & \hfill \forall i\in I\end{array}$$

(20)

$$\begin{array}{cccc}\hfill & W_i⩾0\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}& \hfill \forall i\in I\end{array}$$

(21)

$$\begin{array}{cc}\hfill & D{M}_i^{+},D{M}_i^{-},W_i\in \mathbb{N}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hfill \end{array}$$

(22)

As shown in Equation (1), the objective function Z consists of three components: $Z_1$, which represents the total slot displacement and reflects the overall efficiency of the slot allocation; $Z_2$, which represents the maximum slot displacement and reflects the worst-case scenario in the slot allocation; and $Z_3$, which denotes the fairness deviation, expressed in the form of variance, representing the fairness of the slot allocation among the considered airlines. The term $\lambda \times W_i$ at the end represents the penalty for slot allocation outside the restricted time periods, which will be explained in detail later. Constraints (2) and (3) present the detailed structure of $Y_{it}$, which represents the slot allocated to the request. Specifically, $Y_{it}$ equals 0 if the request is allocated to a time slot before t, and it equals 1 if the request is allocated to slot t or later. Constraints (4) and (5) define the forward and backward displacement ($D{M}_i$) generated by request i. Requests with historical priority can retain their historical slots during the allocation process, assigning them the highest priority. This process is controlled by Constraint (6), which manages $Y_{it}$. Constraints (7), (8), and (9) represent the airport capacity constraints, while Constraint (10) defines the rolling capacity constraint, ensuring that the capacity within each rolling time window does not exceed the predefined capacity limits.

Constraints (11), (12), (13), and (14) provide a comprehensive framework for evaluating fairness in slot allocation based on the demand-driven slot value metric proposed in this paper. The time slot value $V_t$ is calculated using a demand-based approach (Constraint (11)), which incorporates both the number of requests at the target time slot and those from adjacent time intervals. To reflect temporal variations in demand, the calculation assigns weights (${\alpha }_1,{\alpha }_2,{\alpha }_3,\dots$) to the requests, with ${\alpha }_1>{\alpha }_2>{\alpha }_3$, ensuring that closer intervals have a greater influence on the slot value. Building on the slot value $V_t$, the loss metric $G_i$ quantifies the fairness of the allocation process (Constraint (12)). Specifically, $G_i$ measures two aspects of loss for each request:

• Time Slot Value Loss: The disparity between the value of the requested slot and the value of the allocated slot.
• Displacement Loss: The deviation in time between the requested slot and the allocated slot, particularly when the assigned slot is further away from the preferred time.

The total loss value for a request, $G_i$, integrates these dimensions and provides a comprehensive measure of allocation fairness. To further safeguard fairness, particularly for smaller airlines, the average loss in slot request value for each airline is calculated using Constraint (13). This metric evaluates the average impact of slot allocations on individual airlines. Additionally, the overall fairness of the allocation process across all airlines is assessed through the mean average loss value (Constraint (14)), providing a holistic view of system-wide fairness in slot allocation.

In practical operations, airlines seek to request suitable flight connections to ensure that an aircraft can quickly transition to its next flight after completing its turnaround, minimizing waiting time. Constraints (15) and (16) limit the range of time variations for turnaround flights. Considering this factor can facilitate flight connections for airlines and enhance their operational efficiency. Constraints (17) to (19) restrict flights of the “change to historic” type. This limitation follows the requirements outlined in the WASG regarding “change to historic” flights. During actual operations, airports typically designate peak hours, and external slots are generally not allocated to peak hours during the scheduling process. Constraint (21) defines the variable $W_i$, which, in conjunction with the penalty values in the objective function, collectively forms the constraints on slot allocations outside of restricted time periods.

4. Solution Approach

In the process of airport slot allocation, this study considers the capacity constraints of 1 h and 15 min, as well as a rolling capacity constraint with a width of 1 h and a step size of 5 min. Actual data from Urumqi Diwopu Airport and Shanghai Hongqiao Airport are used, involving over 2000 slot requests over a duration of six months. The large number of constraints and the substantial volume of data make the problem complex to solve. Therefore, a heuristic algorithm is employed as the solution method, and the $\epsilon$-constraint method is introduced to address the multi-objective nature of the problem. The following sections introduce the heuristic algorithm and the solution process after incorporating the $\epsilon$-constraint method.

4.1. Heuristic Algorithm

To reduce the computational complexity of the algorithm, this study employs the large-neighborhood search (LNS) algorithm proposed by Ribeiro et al. [25] for efficient and rapid problem-solving. This utilizes a time window neighborhood structure, decomposing the problem into consecutive time windows for final resolution. Figure 1 illustrates the neighborhood structure of the time windows. In this diagram, the white nodes represent slot requests, and the interactions between adjacent time slot nodes are more significant during the slot allocation process. The algorithm groups nodes by selecting a specific time window for optimization. Additionally, to ensure the efficiency of slot allocation, the algorithm introduces an adaptive adjustment mechanism. The window size is denoted by s, and the window step size is represented by r.

The specific steps of the large-neighborhood algorithm are shown in the diagram in Figure 2. Initially, the slot requests are grouped with respect to time; after this grouping, a time window is randomly selected. The solutions for other windows are fixed while the selected window is optimized. The displacement value corresponding to the selected time window is used as the weight. Based on the selected requests, the local solution is optimized. If there is an improvement, the weight of the corresponding window is increased; otherwise, the weight remains unchanged. Additionally, if an optimal solution is not obtained within a set time, the current neighborhood structure is reduced, and requests are selected according to a certain proportion. If the optimal value does not improve within n consecutive iterations, the solution is considered optimal, the iterations end, and the current solution is returned.

4.2. Solution Process

To solve the multi-objective problem, this study introduces the $\epsilon$-constraint method. The entire algorithm process is illustrated in Figure 2, and it is divided into two phases. The input data for the first phase include airport capacity data, airline slot requests, and the parameters involved in the algorithm. In the first phase, the objective function is set to minimize $Z_1$:

$$Z_1=\min (\sum _{i\in I}\sum _{r\in R}(D{M}_i^{+}+D{M}_i^{-})D_{ir})$$

(23)

The remaining constraints are established according to the airport slot allocation model described above. The problem is then solved using the large-neighborhood search algorithm, and, after several iterations, a slot allocation scheme is obtained. The objective function value of the new solution is denoted by ${\widehat{Z}}_1$. In the second phase, the result from the first phase is used as the initial solution, and the objective function is reconstructed (Equation (24)) with the corresponding $\epsilon$-constraint added (Constraint (25), where $\theta >1$):

$$\begin{array}{cc}\hfill & Z_2=\min \left(\max \left(D{M}_i^{-},D{M}_i^{+}\right)\right)\hfill \end{array}$$

(24)

$$\begin{array}{cc}\hfill & Z_1⩽{\widehat{Z}}_1\times \theta \hfill \end{array}$$

(25)

After the model is modified, the initial solution is fed into the large-neighborhood algorithm, and, after several iterations, an updated solution is obtained. The objective function value of this solution is denoted by ${\widehat{Z}}_2$. The above steps are repeated, with the objective function set to $Z_3$ (Equation (26)) and corresponding constraints (27) and (28). In this way, the multi-objective problem can be effectively solved, resulting in a relatively good solution.

$$\begin{array}{cc}\hfill & Z_3=\min (\sum _{a\in Air}{(x_a-\overline{x})}^2)\hfill \end{array}$$

(26)

$$\begin{array}{cc}\hfill & Z_1⩽{\widehat{Z}}_1\times \theta \hfill \end{array}$$

(27)

$$\begin{array}{cc}\hfill & Z_2⩽{\widehat{Z}}_2\times \theta \hfill \end{array}$$

(28)

5. Experimental Results and Analyses

All the experiments described in this paper were conducted on an AMD Ryzen 7 4800H CPU with 16 GB of RAM using Gurobi. The following sections provide a detailed description of the data used and the experimental results.

5.1. Input Data and Problem Parameters

The input data were divided into three parts: airline slot requests, airport capacity information, and experimental parameters. The airline slot request information included details such as the airline, requested time, flight frequency, start time, end time, and flight connection information. The airport capacity information included 1 h and 15 min slot capacities, as well as rolling capacities, each covering takeoffs, landings, and total capacities.

Table 2. Flight schedule example data.

Type1	Start Date	End Date	Freq	Time	Type2	Orig Time	Airline	Pre ID
dep	2024-03-31	2024-05-11	1,2,4,5,7	19:55	cr	21:15	CZ6801	-1
arr	2024-04-06	2024-05-11	1,3,5,7	23:05	new	-1	CZ6828	-1
arr	2024-03-31	2024-04-25	2,4,6	19:10	cr	22:45	CZ6678	-1
dep	2024-03-31	2024-04-05	1,3,5,7	13:55	his	13:55	CZ6831	-1
dep	2024-04-11	2024-04-11	4	19:10	cr	18:35	CZ6807	-1
arr	2024-04-11	2024-04-11	4	23:45	cr	23:15	CZ6808	-1

presents an example of the airline slot request information. In the table, Type1 indicates the flight operation type (arrival or departure), Start Date and End Date specify the duration of the operation, and Freq represents the weekly frequency. For instance, “2,4,6” indicates that the flight operates on Tuesdays, Thursdays, and Saturdays. Type2 denotes the priority type during the slot allocation process.

To fully verify the efficiency of the algorithm and observe fairness during the allocation process, this study selected slot allocation data from the Shanghai Hongqiao and Urumqi Diwopu airports for experimentation. Four datasets were extracted, with the longest duration spanning six months and containing up to 2564 slot requests. The datasets included one small-scale example, two medium-scale examples, and one large-scale example.

Table 3. Request features of some instances in the experimentation.

Instance	Movements	Requests	Duration	Airport	Airlines	Rotation
1	5223	368	1 month	ZSSS	26	28
2	27,831	601	4 months	ZWWW	29	35
3	35,391	429	6 months	ZSSS	39	37
4	119,472	2564	3 months	ZSSS	42	75

lists some characteristics of the input data. The table details the number of requests and movements for four instances. The distinction is that a request by an airline for a flight on every Tuesday and Thursday in February was considered to be one request, but, since the flight is scheduled to operate eight times in February, this request was regarded as including eight movements. The Airlines column lists the number of airlines involved in the slot requests. Rotation refers to flight turnarounds. It is important to note that this paper only included certain potential turnarounds in the constraints, and the Rotation column does not represent the actual number of turnarounds occurring during operations.

Table 4. Parameter settings in multi-objective airport slot allocation.

Parameter	Explanation	Value
$\theta$	Allowed deviation in objective function	1.2
s	Time window size	2 h
r	Time window step	30 min
${\alpha }_1$	Weight parameter 1	5
${\alpha }_2$	Weight parameter 2	3
${\alpha }_3$	Weight parameter 3	1
$\lambda$	Penalty coefficient	576

presents the baseline parameter settings used during the experiments.

5.2. Experimental Results

Figure 3 illustrates the distribution of time slot values based on demand across different time periods for four distinct instances. Although instances 1, 3, and 4 all pertain to Shanghai Hongqiao Airport, the calculated slot values differ due to variations in the input requests. However, a clear pattern emerges as the peak and trough trends in slot values are generally consistent across these three instances. In contrast, the time slot values for Urumqi Diwopu Airport exhibit a certain delay. For example, while the first peak at Hongqiao occurs between 6:00 and 8:00, the corresponding peak at Urumqi appears after 8:00. Additionally, Urumqi demonstrates stronger operational performance during nighttime hours compared to Hongqiao, with higher slot values between midnight and 2:00 AM, during which Hongqiao’s slot values remain relatively low. This phenomenon is likely attributable to time zone differences, which shift the operational hours at Diwopu to a later timeframe.

Table 5. Multi-objective airport slot allocation objective values at different stages.

Instance	Phase 1				Phase 2				Phase 3				Exactly Solve
	${\mathbf{Z}}_{\mathbf{1}}$	${\mathbf{Z}}_{\mathbf{2}}$	${\mathbf{Z}}_{\mathbf{3}}$		${\mathbf{Z}}_{\mathbf{1}}$	${\mathbf{Z}}_{\mathbf{2}}$	${\mathbf{Z}}_{\mathbf{3}}$		${\mathbf{Z}}_{\mathbf{1}}$	${\mathbf{Z}}_{\mathbf{2}}$	${\mathbf{Z}}_{\mathbf{3}}$		${\mathbf{Z}}_{\mathbf{1}}$	${\mathbf{Z}}_{\mathbf{2}}$	${\mathbf{Z}}_{\mathbf{3}}$
1	472	26	1689.49		472	26	1689.49		548	28	492.31		565	29	458.41
2	2560	28	17,597.62		2640	23	18,497.74		2943	23	3673.68		3271	25	2943.65
3	2865	42	41,436.22		2932	33	38,062.17		3281	34	11,642.34		3052	34	10,068.25
4	6206	31	34,962.35		6452	24	34,037.44		6894	26	16,231.26		7059	30	15,744.65

and

Table 6. Percentage variations in objective function values across different phases.

Instance	Phase 1–Phase 2			Phase 2–Phase 3				Phase 1–Phase 3
	${\mathbf{Z}}_{\mathbf{1}}$	${\mathbf{Z}}_{\mathbf{2}}$		${\mathbf{Z}}_{\mathbf{1}}$	${\mathbf{Z}}_{\mathbf{2}}$	${\mathbf{Z}}_{\mathbf{3}}$		${\mathbf{Z}}_{\mathbf{1}}$	${\mathbf{Z}}_{\mathbf{2}}$	${\mathbf{Z}}_{\mathbf{3}}$
1	0.00%	0.00%		16.10%	7.69%	−70.86%		16.10%	7.69%	−70.86%
2	3.13%	−17.86%		11.48%	0.00%	−80.14%		14.96%	−17.86%	−79.12%
3	2.34%	−21.43%		11.90%	3.03%	−69.41%		14.52%	−19.05%	−71.90%
4	3.96%	−22.58%		6.85%	8.33%	−52.31%		11.09%	−16.13%	−53.58%

presents the objective values and their variations for four instances across different phases. In Phase 1, the focus is on optimizing the total displacement $Z_1$; in Phase 2, the emphasis shifts to optimizing the maximum displacement $Z_2$; and, in Phase 3, the objective is to enhance $Z_3$, the fairness indicator for airlines. It is evident that the model significantly improves fairness in slot allocation, albeit with a slight trade-off in the total and maximum displacements. The Table 5 also presents a comparison between the heuristic solution and the exact solution. The “Exactly solve” column shows the results obtained by applying exact methods in all three phases.

In Phase 2, as compared to Phase 1, the total displacement shows a slight increase, with a maximum rise of 3.96%, while the maximum displacement decreases by approximately 20%. In Phase 3, as compared to Phase 2, the unfairness indicator decreases by as much as 80.14%, while the total displacement increases by a maximum of 16.1%, and the maximum displacement increases by up to 8.33%. These results indicate that the proposed solution process effectively solves the multi-objective model presented in this paper, consistently yielding favorable outcomes across multiple experiments.

It is worth noting that, during the Phase 2 process, although the optimization focuses solely on maximum displacement, this indicator also reflects fairness in allocation to some extent. Consequently, the unfairness indicators for certain results (instances 3 and 4) have decreased, while, in some cases, other indicators have increased.

To verify the impact of rolling capacity on the scheduling configuration process, this study solved models with and without the addition of rolling capacity, considering rolling capacity violations (RCVs). A comparative analysis was conducted from multiple dimensions, including the total displacement, maximum displacement, and fairness indicators, as summarized in

Table 7. Comparison of results with and without rolling capacity consideration.

Instance	RCVs 1			${\mathit{Z}}_1$			${\mathit{Z}}_2$			${\mathit{Z}}_3$
	WRC 2	NRC 3		WRC	NRC		WRC	NRC		WRC	NRC
1	0.00%	2.92%		548	503		28	24		492.31	263.21
2	0.00%	2.28%		2943	2778		23	17		3673.68	3972.56
3	0.00%	1.49%		3281	2931		34	20		11,642.34	10,872.30
4	0.00%	1.51%		6894	6502		26	17		16,231.26	16,846.95

¹ RCVs: rolling capacity violations. ² WRC: with rolling capacity. ³ NRC: no rolling capacity.

. The results indicate that considering rolling capacity leads to a significant reduction in RCVs, with some cases even reaching zero, demonstrating its effectiveness in decreasing the number of violations. In terms of total displacement, the differences between the results with rolling capacity (WRC) and results without rolling capacity (NRC) are relatively small. However, in certain instances, WRC exhibits slightly higher displacement due to the unavoidable alteration of the optimal solution after the introduction of additional constraints. Similarly, both the maximum displacement and fairness indicators for WRC may slightly increase; however, the addition of rolling capacity does not substantially impact the fairness of the allocation.

6. Conclusions

Globally, there are 198 slot-coordinated airports, accounting for approximately 6% of the total number of airports, yet they handle 50% of the world’s air transport services. Fairness has not been sufficiently considered in the slot allocation process, which is typically based solely on fixed capacity constraints. To address this issue, this study incorporated rolling capacity constraints to optimize both the fairness and efficiency of slot allocation. The contributions of this study are as follows:

• This study proposed an airline fairness metric based on a demand-side value system and developed a tri-objective model for flight slot allocation. The model simultaneously considers the maximum slot displacement, total slot displacement, and airline fairness.
• Dynamic capacity constraints were introduced in the form of rolling time windows and peak limit slot migration constraints. A large-neighborhood search heuristic algorithm was applied to solve the model and achieve an efficient allocation scheme.
• The experimental results demonstrated that incorporating rolling capacity constraints effectively resolved the overcapacity issues caused by static capacity limits over continuous time periods.
• The proposed airline fairness metric, grounded in the demand-side value system, significantly enhanced fairness in the slot allocation process. Specifically, it achieved an almost 80% reduction in the unfairness metric with a sacrifice of at most 16% in terms of total displacement.
• This paper considered rolling capacity during the scheduling process and used a large-neighborhood search algorithm to address the large computational scale caused by rolling capacity. The goal was to obtain a solution that avoids overload during consecutive time periods while ensuring that the total displacement change remains minimal within a limited timeframe.

This study focused solely on single-airport slot allocation and did not extend to multi-airport or airport network scenarios, which could be explored in future research. Moreover, the introduction of a heuristic algorithm may have resulted in suboptimal solutions due to limitations in terms of the algorithm’s scale and computation time. Future work could consider incorporating more test cases and different scenarios to enhance the robustness of the algorithm. Additionally, adaptive rolling capacity window lengths could be considered to reduce the algorithm’s computational burden.