# Managing the Gate Assignment Problem in the Hub Airport with Satellite Halls: A Transfer Demand-Oriented Approach

Authors: Runfa Wu; Wenliang Zhou; Linhuan Zhong; Yihan Liu
Journal: Computational Intelligence and Neuroscience
 (2022)

---

## Abstract

This study focuses on managing the gate assignment in the hub airport with both main terminal and satellite halls. We first formulate the gate assignment problem (GAP) as a binary linear programming model with multi-objective functions, where the practical constraints, e.g., gate time conflict and gate compatibility, are considered. Then, we incorporate the impact of gate assignment on transfer passengers and formulate the transfer demand-oriented gate assignment problem (TGAP) as a nonlinear model. A linearization approach and a heuristic approach are designed to solve the TGAP model. A case study is conducted based on the practical data of the Shanghai Pudong International Airport, where a comparison between the results of GAP and TGAP by the two proposed approaches is demonstrated. It shows that the proposed TGAP model and solution approaches can not only enhance the service for transfer passengers but also improve the gate utilization efficiency in the hub airport.


---

## Body

## 1. Introduction

Global air passenger demand and airport construction have experienced rapid growth over the past few decades, and passenger demand still grew steady in 2019 before the COVID-19 pandemic [1]. Driven by the recovery in domestic markets in China, many hub airports have returned to pre-pandemic levels in passenger demand and flight numbers; e.g., Shanghai Pudong International Airport was handling 110,000 domestic travelers and 900 domestic flights every day in March 2021, which are both more than that of 2019 [2]. As the import part of the hub-and-spoke system in air transportation, hub airports are experiencing rapid growth in passenger demand and flight numbers. To release operating pressure and provide better airplane/flight service and passenger service, many hub airports have built satellite halls connected with terminals by underground walkways or mass rapid transit (MRT) systems. This raises new challenges for efficient operations and passenger services in the hub airport.Gates are a scarce resource at hub airports, facing intense air traffic and passenger demand pressure [3]. The gate operation connects air traffic (timetable and airplane service), passenger service, and ground operations (including crew assignment), which makes it critical for efficient airport operations. The gate assignment problem (GAP) is to assign airplanes/flights to suitable boarding gates or the apron at the airport on an operating period (usually one day), according to the given flight timetable and airplane fleet assignment, also taking into account the airport layout, gate compatibility, airplane types, and so on. The typical objectives of GAP usually include two aspects, minimizing the operating costs and maximizing the efficiency of gate resources for airport operators; and maximizing satisfaction for passengers. The GAP has been extensively studied as one of the most important problems in the daily operations of the airport, and see [4, 5] for a detailed literature review, and we give an overview from airport and passenger perspectives.From the airport operator perspective, the main objectives for GAP are efficient utilization of gate resources and reducing operating costs. Since the parking positions in the apron are usually far from the terminals and passengers need to take the shuttle bus. If airplanes are assigned to the apron, it will increase the waiting time of passengers and operation costs due to potential effects on ground operations and crew assignment. The most common objective in GAP literature is to minimize the airplanes/flights assigned to the apron (Ding et al. [6], Dorndorf et al. [7, 8], Drexl and Nikulin [9], Deng et al. [10]). Some studies aim to minimize the total delay of airplanes when the airport is busy (Lim et al. [11], Kaliszewski et al. [12]). Moreover, as Karsu et al. [13] point out, hub airports may need to handle different types of flights (domestic/international) and airplanes, so minimizing the moves/costs of towing when airplanes need to move from a gate to another is also considered in the literature (Benlic et al. [14], Kumar and Bierlaire [15], Yu et al. [16]). We consider the gate compatibility instead of the towing operation in this study to capture the matching between airplane/flight types and gate facilities. It was also modeled in the objective function of Benlic et al. [14] and Neuman and Atkin [17]. Following the conclusion that the airport controls gate use will ensure they are used most efficiently in the survey of Gillen and Lall [18], we also consider the integrated operating of gates in terminal and satellite halls in the hub airport and include minimizing the number of used gates in the objective function.Gate assignment also affects the passenger service quality in the airport [11], and it may influence the walking distance, waiting time, and transfer service of passengers. The consideration of passengers in the literature is mainly reflected in the objective function. Hub airports in metropolitan usually have multiterminals, and it may take a lot of time/distance to get the specific gate or transfer between gates, and many studies contribute to GAP to minimize walking time/distance of passengers. Bohr [19] proposed binary linear programming to minimize the passenger walking distance and solved it by the primal-dual simplex algorithm. Karsu et al. [13] formulated a mixed-integer nonlinear programming model for GAP to minimize the total walking distance of all passengers and the number of airplanes assigned to the apron and then proposed exact and heuristic approaches to solve it. Interested readers can also refer to Drexl and Nikulin [9], Haghani and Chen [20], Dell’Orco et al. [21], and Mokhtarimousavi et al. [22]. Besides, Yan and Huo [23] and Yan and Tang [24] are focused on minimizing the total passenger waiting time in GAP. However, from the survey of Entwistle [25], over 60% of passengers plan to shop in the airport, which means minimizing the waiting time is not always the objective of passengers, at least for some of them. Daş [26] proposed a multi-objective model to increase the shopping revenues in the airport through gate assignment, by minimizing the total passenger walking distance and assigning passengers to gates near the shop. We consider the transfer time budget of passengers in this study and propose a more comprehensive way to measure service for transfer passengers. A comparison with some abovementioned major-related studies is shown in Table 1.Table 1
Comparisons of major-related studies.
PaperAirport-orainted objectivePassenger-orainted objectiveTransfer passengerGate compatibilitySolution methodBihr [19]—Walking distanceNo—Simplex algorithmDing et al. [6]Unassigned airplaneWalking distanceYes—Tabu searchYan and Tang [24]—Waiting timeNo—Heuristic approachDrexl and Nikulin [9]Unassigned airplane and flight-gate preferencesWalking distanceYes—Pareto SADell’orco et al. [21]Unassigned airplaneWalking distanceYes—Bee Colony AlgorithmsDas [26]Passengers assigned to specific gatesWalking distanceNo—Two phase local searchDeng et al. [30]Gate utilizationWalking distanceYesAirplane typeQuantum evolutionary algorithmThis paperUnassigned airplane and gate utilizationTransfer pressureYesAirplane and flight typeLinearization approach and SA-based algorithmIn this study, we focus on the impacts of gate assignment on the service of transfer passengers in the hub airport with satellite halls. We proposed a novel transfer demand-oriented objective function considering the transfer time budget, together with objective functions of the airport operator, to explore the trade-off between airport operations and passenger service. Besides, we propose two optimization models, namely a binary linear programming model for gate assignment problem (GAP) and a nonlinear model for transfer demand-oriented gate assignment problem (TGAP). A linearization approach and a heuristic approach are designed to solve the TGAP model, and then, case studies are performed using the data of Shanghai Pudong International Airport.The remainder of this study is organized as follows. In Section2, we give a detailed description of GAP and TGAP. The corresponding mathematic models are formulated in Section 3. Then, Section 4 develops the linearization approach and heuristic approach to solve the model. Case studies are illustrated in Section 5, and Section 6 concludes the study.


## 2. Problem Statement and Assumptions

### 2.1. Problem Statement

We consider a hub airport with the main terminal and several satellite halls, illustrated in Figure1. Gates are available in both the terminal and satellite halls and integrated assigned by the airport operator, denoted by g∈G. Passengers can travel between the terminal and satellite halls via the MRT system. As shown in Figure 1, the airport also has parking positions for airplanes at the apron, denoted by G′, in case an airplane could not be assigned to a gate in the terminal or satellite halls.Figure 1
Example layout of the hub airport with satellite halls.The research period in this study is denoted byT1,T2 (i.e., one day or one week) and discretized into equal-length time intervals t, and let t∈T. Some airplanes land and take off at the airport in this period, they occupy the gates for passenger arrivals and departures, and the set of airplanes is denoted by I. The services that provided by airplanes to transport passengers between airports are called a flight. For a specific airport, one airplane serves two flights, and we assume that the related flights of each airplane and the timetable are given. In Figure 2, we show the relationship between airplanes and related flights it serves. An airplane i∈I is considered, and it serves two flights: one arriving flight with arrival time ai and one departing flight with departure time di, and it needs to occupy a gate g∈G or a parking position g∈G′ during the time period ai,di. Besides, the type of airplanes (wide/narrow-body) and related flights (domestic/international) are also given. Since the correspondence between aircrafts and flights is given, it is possible to model by either airplane or flight, and we use the airplane for modeling in this study.Figure 2
Airplane and served flights.As for the utilization of gates, the first thing to consider is time conflicts. As shown in Figure3, airplanes i∈I and i′∈I use the same gate consecutively, and the usage time periods of the two airplanes ai,di and ai′,di′ should not overlap. Besides, buffer time τb should also be satisfied between serving two airplanes for ground operations. Secondly, because gates in terminal and satellite halls may have different functions (such as check-in facilities and passport control), we consider the gate compatibility in this study. In particular, for airplanes, we consider gate compatibility for wide/narrow-body types; for related flights, the gate compatibility is associated with serving domestic/international flights.Figure 3
Gate utilization and buffer time.The gate assignment problem (GAP) is to assign airplanesi∈I to gates or apron g∈G∪​G′ with considering constraints such as gate time conflict constraints and gate compatibility, and the objective function mainly concerns making efficient use of gates or reducing the number of occupied gates. The decision variables are binary gate assignment variables xig,i∈I,g∈G, and binary gate utilization variables xg,g∈G. In particular, xig equals 1 if airplane i is assigned to gate g and otherwise equals 0; xg equals 1 if gate g is used by any airplane and otherwise equals 0.We also attempt to consider the impact of gate assignment on passengers in this study. The set of passenger groups is denoted byP. As shown in Figure 4, each group of passengers p∈P transfers from the same arrival flight served by airplane ip1∈I to the same departure flight served by airplane ip2∈I (which can be abbreviated as i1 and i2). The transfer time budget for passenger group p is defined as Bp=di2−ai1. The number of passengers in group p is given and denoted by np.Figure 4
Illustration for transfer time budget of passengers.Gate assignment determines passengers’ shortest transfer time, including processing time, walking time, and MRT time. It will affect passengers’ transfer in the airport, especially hub airports with satellite halls. The layout in Figure1 is taken as an example, and a passenger whose transfer time budget is 60 min is considered. Different transfer scenarios are illustrated in Table 2 when arriving and departing airplanes are assigned to different gates. In Scenario 1, both gates of arriving and departing airplanes are assigned in terminal T, and the shortest transfer time is much less than the transfer time budget Bp and transfer success. Passenger transfer is more stressful in Scenario 2 because the assigned gates of two airplanes are located at T and S1, respectively. Passengers in Scenario 3 and Scenario 4 fail to transfer due to the gate assignment.Table 2
Transfer scenarios for passenger groupp under different gate assignment schemes.
ScenariosGate of arriving airplaneGate of departing airplaneShortest transfer timeTransfer time budgetBpResult1Gate 1 (T)Gate 2 (T)30 min60 minSuccess2Gate 1 (T)Gate 3 (S1)55 minSuccess3Gate 1 (T)Gate 5 (S2)70 minFail4Gate 1 (T)Gate 7 (apron)>70 minFailThus, passengersp may fail to transfer if the shortest transfer time is too long between two gates assigned to airplanes i1 and i2, i.e., exceeding the transfer time budget Bp. The demand-oriented gate assignment problem (TGAP) in this study focuses on the trade-off between transfer passenger service and gate utilization efficiency in GAP when satellite halls are constructed in the hub airport.


### 2.2. Assumptions

To facilitate the presentation of our studied problem in this study, the following assumptions are made:A1: (airport layout). Considering a hub airport with one terminal, several satellite halls, and an apron, the shortest transfer time between any two gates is given. There is no limit on the number and type of airplanes that use the apron simultaneously.A2: (flight and airplane). Given the flight timetable in the research period, including arrival/departure time, flight types (domestic/international), and airplane types (wide/narrow-body).A3: (gate service). Only one airplane can use a gate at a time. All of the gates have the same buffer time τb between serving two airplanes. The gate compatibility for flights and airplanes is considered.A4: (passenger demand). Since the satellite halls mainly affect transfer passengers, it is assumed that we only consider the transfer passenger demand. The quantity, associated flights, and transfer time budget of passengers are given.


## 2.1. Problem Statement

We consider a hub airport with the main terminal and several satellite halls, illustrated in Figure1. Gates are available in both the terminal and satellite halls and integrated assigned by the airport operator, denoted by g∈G. Passengers can travel between the terminal and satellite halls via the MRT system. As shown in Figure 1, the airport also has parking positions for airplanes at the apron, denoted by G′, in case an airplane could not be assigned to a gate in the terminal or satellite halls.Figure 1
Example layout of the hub airport with satellite halls.The research period in this study is denoted byT1,T2 (i.e., one day or one week) and discretized into equal-length time intervals t, and let t∈T. Some airplanes land and take off at the airport in this period, they occupy the gates for passenger arrivals and departures, and the set of airplanes is denoted by I. The services that provided by airplanes to transport passengers between airports are called a flight. For a specific airport, one airplane serves two flights, and we assume that the related flights of each airplane and the timetable are given. In Figure 2, we show the relationship between airplanes and related flights it serves. An airplane i∈I is considered, and it serves two flights: one arriving flight with arrival time ai and one departing flight with departure time di, and it needs to occupy a gate g∈G or a parking position g∈G′ during the time period ai,di. Besides, the type of airplanes (wide/narrow-body) and related flights (domestic/international) are also given. Since the correspondence between aircrafts and flights is given, it is possible to model by either airplane or flight, and we use the airplane for modeling in this study.Figure 2
Airplane and served flights.As for the utilization of gates, the first thing to consider is time conflicts. As shown in Figure3, airplanes i∈I and i′∈I use the same gate consecutively, and the usage time periods of the two airplanes ai,di and ai′,di′ should not overlap. Besides, buffer time τb should also be satisfied between serving two airplanes for ground operations. Secondly, because gates in terminal and satellite halls may have different functions (such as check-in facilities and passport control), we consider the gate compatibility in this study. In particular, for airplanes, we consider gate compatibility for wide/narrow-body types; for related flights, the gate compatibility is associated with serving domestic/international flights.Figure 3
Gate utilization and buffer time.The gate assignment problem (GAP) is to assign airplanesi∈I to gates or apron g∈G∪​G′ with considering constraints such as gate time conflict constraints and gate compatibility, and the objective function mainly concerns making efficient use of gates or reducing the number of occupied gates. The decision variables are binary gate assignment variables xig,i∈I,g∈G, and binary gate utilization variables xg,g∈G. In particular, xig equals 1 if airplane i is assigned to gate g and otherwise equals 0; xg equals 1 if gate g is used by any airplane and otherwise equals 0.We also attempt to consider the impact of gate assignment on passengers in this study. The set of passenger groups is denoted byP. As shown in Figure 4, each group of passengers p∈P transfers from the same arrival flight served by airplane ip1∈I to the same departure flight served by airplane ip2∈I (which can be abbreviated as i1 and i2). The transfer time budget for passenger group p is defined as Bp=di2−ai1. The number of passengers in group p is given and denoted by np.Figure 4
Illustration for transfer time budget of passengers.Gate assignment determines passengers’ shortest transfer time, including processing time, walking time, and MRT time. It will affect passengers’ transfer in the airport, especially hub airports with satellite halls. The layout in Figure1 is taken as an example, and a passenger whose transfer time budget is 60 min is considered. Different transfer scenarios are illustrated in Table 2 when arriving and departing airplanes are assigned to different gates. In Scenario 1, both gates of arriving and departing airplanes are assigned in terminal T, and the shortest transfer time is much less than the transfer time budget Bp and transfer success. Passenger transfer is more stressful in Scenario 2 because the assigned gates of two airplanes are located at T and S1, respectively. Passengers in Scenario 3 and Scenario 4 fail to transfer due to the gate assignment.Table 2
Transfer scenarios for passenger groupp under different gate assignment schemes.
ScenariosGate of arriving airplaneGate of departing airplaneShortest transfer timeTransfer time budgetBpResult1Gate 1 (T)Gate 2 (T)30 min60 minSuccess2Gate 1 (T)Gate 3 (S1)55 minSuccess3Gate 1 (T)Gate 5 (S2)70 minFail4Gate 1 (T)Gate 7 (apron)>70 minFailThus, passengersp may fail to transfer if the shortest transfer time is too long between two gates assigned to airplanes i1 and i2, i.e., exceeding the transfer time budget Bp. The demand-oriented gate assignment problem (TGAP) in this study focuses on the trade-off between transfer passenger service and gate utilization efficiency in GAP when satellite halls are constructed in the hub airport.


## 2.2. Assumptions

To facilitate the presentation of our studied problem in this study, the following assumptions are made:A1: (airport layout). Considering a hub airport with one terminal, several satellite halls, and an apron, the shortest transfer time between any two gates is given. There is no limit on the number and type of airplanes that use the apron simultaneously.A2: (flight and airplane). Given the flight timetable in the research period, including arrival/departure time, flight types (domestic/international), and airplane types (wide/narrow-body).A3: (gate service). Only one airplane can use a gate at a time. All of the gates have the same buffer time τb between serving two airplanes. The gate compatibility for flights and airplanes is considered.A4: (passenger demand). Since the satellite halls mainly affect transfer passengers, it is assumed that we only consider the transfer passenger demand. The quantity, associated flights, and transfer time budget of passengers are given.


## 3. Mathematical Formulation

In this section, we first formulate the model for GAP to clarify the resource utilization and constraints in the hub airport, and then, we propose the model for TGAP considering the service of transfer passengers in Section3.2.


### 3.1. Notations and Decision Variables

Table3 lists general indices, sets, parameters, and variables in optimization models that appeared in this study.Table 3
Main sets, indices, parameters, and variables.
SymbolDefinitionSets and indicesGSet of gates in the terminal and satellite hallsG′Set of parking positions in the apronISet of airplanesPSet of passenger groupsTSet of discretized time intervalsgIndex of all gates and parking positions,g∈G∪​G′iIndex of airplanes,i∈IpIndex of passenger groups,p∈PtIndex of discretized time intervals,t∈TParametersT1,T2Daily operation periodτbBuffer time of gatesaiArrival time of airplaneidiDeparture time of airplaneiδitAirplane time incidence parameterσigAirplane gate compatibility incidence parameterip1Arriving airplane of passenger groupp, abbreviated as i1ip2Departing airplane of passenger groupp, abbreviated as i2BpTransfer time budget of passenger grouppnpNumber of passengers in grouppτg1,g2Shortest transfer time between gateg1∈G∪​G′ and g2∈G∪​G′τcWaiting time for passengers when fail to transferMA sufficiently large constantεA sufficiently small positive constantcWeights in the objective functionVariablesxigBinary assignment variable:xig=1 if airplane i∈I is assigned to gate g∈G∪​G′, and xig=0, otherwisexgBinary utilization variable:xg=1 if gate g∈G is used, and xg=0, otherwiseφpTransfer pressure of passenger grouppyi1,2g1,2Binary variable:yi1,2g1,2=1 for passenger p, if arriving airplane i1 is assigned to g1 and departing airplane i2 is assigned to g2, and yi1,2g1,2=0, otherwise


### 3.2. Model for GAP

In this subsection, the mathematic model of GAP is formulated to integrate using the gates in terminal and satellite halls, including constraints and multi-objective functions.


#### 3.2.1. Constraints

The constraints of GAP usually include gate utilization and airplane service, which are next described in detail.(1) Gate Time Conflict Constraint. A feasible gate assignment scheme should guarantee that airplanes assigned to the same gate do not overlap in time and observe the buffer time. The airplane time incidence parameter δit is introduced, which equals 1 when ai≤t≤di+τb and otherwise 0. So, we have the following:(1)∑i∈Iδit⋅xig≤1,∀t∈T,∀g∈G.The incidence parameterδit and assignment variable xig associate airplanes, gates, and time.(2) Gate Utilization Constraints. For gate g∈G, if it is used by any airplane, the variable xg equals 1, otherwise 0. So, we have gate utilization constraints that indicate the relationship between xig and xg as follows:(2)∑i∈Ixig≤M⋅xg,∀g∈G,where M is a sufficiently large positive constant.(3) Airplane Service Constraints. Each airplane must and can only be assigned to one gate or the apron, and then:(3)∑g∈G∪​G′xig=1,∀i∈I.(4) Gate Compatibility Constraints. We consider the gate compatibility in this model, because gates in the different areas of terminal and satellite halls may have different functions, which are mainly influenced by facilities and equipment. The airplane gate compatibility incidence parameter σig is introduced, which equals 1 if airplane i∈I can be served by gate g∈G and otherwise 0. We can derive the values of σig based on the given airplane and gate types.(4)xig≤σig,∀i∈I,∀g∈G∪​G′.In particular, the apron can serve all types of airplanes andσig=1,g∈G′.(5) Constraints for Decision Variables.(5)xig=1if airplane i is assigned to gateg,0otherwise,∀i∈I,∀g∈G∪​G′,xg=1if gategis used,0otherwise,∀g∈G.Constraints (5) and (6) are binary requirements on the decision variables.


#### 3.2.2. Objective Function

Gates are the scarce resource in an airport, and operational efficiency depends on the utilization of this bottleneck resource. Since the hub airport has terminal and satellite halls simultaneously, the GAP aims to make efficient use of the gates in the terminal and satellite halls and minimizes the operating costs.An airplane can use parking positions in the apron if it cannot be assigned to a gate, but the apron is usually far away from the terminal and satellite halls, and passengers need to take a shuttle bus between the terminal and the apron. This will increase the transfer time of passengers on the one hand and increase the operating costs of the airport on the other hand. To make efficient use of the gates and avoid assigning airplanes to the apron, the first objective is to minimize the number of airplanes assigned to the apron:(6)minZ1=∑i∈I∑g∈G′xig.This is a common objective in the literature of GAP (Ding et al. [6], Dorndorf et al. [7, 8], Drexl and Nikulin [9], Deng et al. [10]). It is equivalent to maximizing the number of airplanes assigned to gates. Furthermore, this objective can be easily extended to maximize the total usage time of gates since the dwell time of each airplane is given, but it has no significant impact on passenger service so we use the objective (6) in this study.Besides, the GAP is multi-objective in nature and operation costs for gates are expensive (including ground operation costs), which motivates us to consider objectives more comprehensively. Apart from minimizing the apron operation, the GAP also needs to consider the objective that minimizes the number of used gates, i.e.,(7)minZ2=∑g∈Gxg.In this study, we consider the objective function that consists of the number of airplanes assigned to the apron and the number of used gates and then formulate the GAP as a multi-objective optimization problem. For GAP in a hub airport with the apron, if we only consider the objective (6), gate operating hours may not be fully utilized in some situations; only consider the objective (7) is obviously not feasible either, which would assign all of the airplanes to the apron. Thus, the combination and trade-off between objectives (6) and (7) is comprehensive for GAP. We use linear weight to handle these two objectives and formulate the objective function as follows:(8)minZGAP=α1⋅Z1+α2⋅Z2,where α1 and α2 are positive weights to denote the trade-off between objectives. In particular, we can obtain a Pareto-optimal solution if α1 and α2 are set 1, or their values are set according to the preference of airport operators.


#### 3.2.3. Mathematical Model for GAP

The GAP can be formulated as follows:(9)minZGAP=α1⋅∑i∈I∑g∈G′xig+α2⋅∑g∈Gxg,s.t.constraints1−6.The mathematical model for GAP given in (9) is binary integer linear programming. The model for GAP focuses on the gate resource optimization when a hub airport has both main terminal and satellite halls, and next, we will consider the impact of GAP on passengers and further improve the model involving different stakeholders.


### 3.3. Model for TGAP

Gate assignment affects the service quality of passengers, especially the transfer passengers in the hub airport where both main terminal and satellite halls are providing passenger service. Passengers may take a longer time to get from the arriving flight to the departing flight gate due to the gate assignment and may even exceed the transfer time budget resulting in a failed transfer. Thus, we will incorporate the service of transfer passengers in the GAP in this section.With the given flight timetable and transfer scheme (arriving airplanei1 and departing airplane i2) of passenger group p∈P, we can get the transfer time budget Bp=di2−ai1. The gates serving airplanes i1 and i2 are denoted as g1 and g2, respectively. Given the layout of terminal and satellite halls in the airport, the shortest transfer time τg1,g2 (including processing time, walking time, and MRT time) between any two gates is also fixed.The gate assignment will influence the shortest transfer time of passenger groupp. Here, we introduce the transfer pressure to describe the airport’s service level for transfer passengers. The transfer pressure is the ratio of shortest transfer time to transfer time budget, and the transfer pressure for passenger p is denoted by φp and defined as follows:(10)φp=τg1,g2Bp,ifi1,i2are both assigned to gates,τcBp,otherwise,where τc is the total transfer time (including process time and shuttle bus time) for passengers associated with the apron. If both associate airplanes of a passenger group are assigned to gates in the terminal and satellite halls, passengers need to do a gate-gate transfer with transfer time τg1,g2; otherwise, passengers need to do a gate-apron, apron-gate, or even apron-apron transfer with transfer time τc. Note that τc is longer than the shortest transfer time between any two gates because the parking positions in the apron are usually far away from the terminal and satellite halls.Then, we introduce the objective that minimizes the transfer pressure for passengers to capture the passenger service in the GAP of the hub airport; i.e.,(11)minZ3=∑p∈P∑g1∈G∪​G′∑g2∈G∪​G′xi1g1xi2g2φpnp.The GAP considering passenger transfer time budget can be formulated as follows:(12)minZTGAP=α1⋅∑i∈I∑g∈G′xig+α2⋅∑g∈Gxg+α3⋅∑p∈P∑g1∈G∪​G′∑g2∈G∪​G′xi1g1xi2g2φpnp,s.t.constraints1−6..The mathematical model given in (12) explicitly considers the transfer passenger service and shows the trade-off between passenger service and operating costs of GAP in the hub airport. The mathematical model (12) is nonlinear programming, and the nonlinearities come from the objective function associated with passenger, where the calculation of transfer pressure φp is a segmentation function.Table4 presents the complexity of the model for GAP and TGAP. It can be seen that the model size depends on the number of gates, airplanes, passenger groups, and demand discretization (number of discretized time intervals). Suppose that there is a hub airport with 10 gates and 100 airplanes with 100 transfer passenger groups, the research period is 0:00−24:00. If the discretization time interval is 5 min, there will be 120 variables and 2500 constraints in the GAP model (9). The number of variables in the TGAP model (11) is 1120, with the addition of variables related to transfer passengers.Table 4
Numbers of variables and constraints in the models.
Variables and constraintsQuantityVariablesxigI×G+IxgGφpPyi1,2g1,2P×G+12ConstraintsGate time conflict constraint (1)T×GGate utilization constraints (2)GAirplane service constraints (3)IGate compatibility constraints (4)I×G+IBinary constraints (5)I×G+IBinary constraints (6)GNote:⋅ represents the cardinality of a set.


## 3.1. Notations and Decision Variables

Table3 lists general indices, sets, parameters, and variables in optimization models that appeared in this study.Table 3
Main sets, indices, parameters, and variables.
SymbolDefinitionSets and indicesGSet of gates in the terminal and satellite hallsG′Set of parking positions in the apronISet of airplanesPSet of passenger groupsTSet of discretized time intervalsgIndex of all gates and parking positions,g∈G∪​G′iIndex of airplanes,i∈IpIndex of passenger groups,p∈PtIndex of discretized time intervals,t∈TParametersT1,T2Daily operation periodτbBuffer time of gatesaiArrival time of airplaneidiDeparture time of airplaneiδitAirplane time incidence parameterσigAirplane gate compatibility incidence parameterip1Arriving airplane of passenger groupp, abbreviated as i1ip2Departing airplane of passenger groupp, abbreviated as i2BpTransfer time budget of passenger grouppnpNumber of passengers in grouppτg1,g2Shortest transfer time between gateg1∈G∪​G′ and g2∈G∪​G′τcWaiting time for passengers when fail to transferMA sufficiently large constantεA sufficiently small positive constantcWeights in the objective functionVariablesxigBinary assignment variable:xig=1 if airplane i∈I is assigned to gate g∈G∪​G′, and xig=0, otherwisexgBinary utilization variable:xg=1 if gate g∈G is used, and xg=0, otherwiseφpTransfer pressure of passenger grouppyi1,2g1,2Binary variable:yi1,2g1,2=1 for passenger p, if arriving airplane i1 is assigned to g1 and departing airplane i2 is assigned to g2, and yi1,2g1,2=0, otherwise


## 3.2. Model for GAP

In this subsection, the mathematic model of GAP is formulated to integrate using the gates in terminal and satellite halls, including constraints and multi-objective functions.


### 3.2.1. Constraints

The constraints of GAP usually include gate utilization and airplane service, which are next described in detail.(1) Gate Time Conflict Constraint. A feasible gate assignment scheme should guarantee that airplanes assigned to the same gate do not overlap in time and observe the buffer time. The airplane time incidence parameter δit is introduced, which equals 1 when ai≤t≤di+τb and otherwise 0. So, we have the following:(1)∑i∈Iδit⋅xig≤1,∀t∈T,∀g∈G.The incidence parameterδit and assignment variable xig associate airplanes, gates, and time.(2) Gate Utilization Constraints. For gate g∈G, if it is used by any airplane, the variable xg equals 1, otherwise 0. So, we have gate utilization constraints that indicate the relationship between xig and xg as follows:(2)∑i∈Ixig≤M⋅xg,∀g∈G,where M is a sufficiently large positive constant.(3) Airplane Service Constraints. Each airplane must and can only be assigned to one gate or the apron, and then:(3)∑g∈G∪​G′xig=1,∀i∈I.(4) Gate Compatibility Constraints. We consider the gate compatibility in this model, because gates in the different areas of terminal and satellite halls may have different functions, which are mainly influenced by facilities and equipment. The airplane gate compatibility incidence parameter σig is introduced, which equals 1 if airplane i∈I can be served by gate g∈G and otherwise 0. We can derive the values of σig based on the given airplane and gate types.(4)xig≤σig,∀i∈I,∀g∈G∪​G′.In particular, the apron can serve all types of airplanes andσig=1,g∈G′.(5) Constraints for Decision Variables.(5)xig=1if airplane i is assigned to gateg,0otherwise,∀i∈I,∀g∈G∪​G′,xg=1if gategis used,0otherwise,∀g∈G.Constraints (5) and (6) are binary requirements on the decision variables.


### 3.2.2. Objective Function

Gates are the scarce resource in an airport, and operational efficiency depends on the utilization of this bottleneck resource. Since the hub airport has terminal and satellite halls simultaneously, the GAP aims to make efficient use of the gates in the terminal and satellite halls and minimizes the operating costs.An airplane can use parking positions in the apron if it cannot be assigned to a gate, but the apron is usually far away from the terminal and satellite halls, and passengers need to take a shuttle bus between the terminal and the apron. This will increase the transfer time of passengers on the one hand and increase the operating costs of the airport on the other hand. To make efficient use of the gates and avoid assigning airplanes to the apron, the first objective is to minimize the number of airplanes assigned to the apron:(6)minZ1=∑i∈I∑g∈G′xig.This is a common objective in the literature of GAP (Ding et al. [6], Dorndorf et al. [7, 8], Drexl and Nikulin [9], Deng et al. [10]). It is equivalent to maximizing the number of airplanes assigned to gates. Furthermore, this objective can be easily extended to maximize the total usage time of gates since the dwell time of each airplane is given, but it has no significant impact on passenger service so we use the objective (6) in this study.Besides, the GAP is multi-objective in nature and operation costs for gates are expensive (including ground operation costs), which motivates us to consider objectives more comprehensively. Apart from minimizing the apron operation, the GAP also needs to consider the objective that minimizes the number of used gates, i.e.,(7)minZ2=∑g∈Gxg.In this study, we consider the objective function that consists of the number of airplanes assigned to the apron and the number of used gates and then formulate the GAP as a multi-objective optimization problem. For GAP in a hub airport with the apron, if we only consider the objective (6), gate operating hours may not be fully utilized in some situations; only consider the objective (7) is obviously not feasible either, which would assign all of the airplanes to the apron. Thus, the combination and trade-off between objectives (6) and (7) is comprehensive for GAP. We use linear weight to handle these two objectives and formulate the objective function as follows:(8)minZGAP=α1⋅Z1+α2⋅Z2,where α1 and α2 are positive weights to denote the trade-off between objectives. In particular, we can obtain a Pareto-optimal solution if α1 and α2 are set 1, or their values are set according to the preference of airport operators.


### 3.2.3. Mathematical Model for GAP

The GAP can be formulated as follows:(9)minZGAP=α1⋅∑i∈I∑g∈G′xig+α2⋅∑g∈Gxg,s.t.constraints1−6.The mathematical model for GAP given in (9) is binary integer linear programming. The model for GAP focuses on the gate resource optimization when a hub airport has both main terminal and satellite halls, and next, we will consider the impact of GAP on passengers and further improve the model involving different stakeholders.


## 3.2.1. Constraints

The constraints of GAP usually include gate utilization and airplane service, which are next described in detail.(1) Gate Time Conflict Constraint. A feasible gate assignment scheme should guarantee that airplanes assigned to the same gate do not overlap in time and observe the buffer time. The airplane time incidence parameter δit is introduced, which equals 1 when ai≤t≤di+τb and otherwise 0. So, we have the following:(1)∑i∈Iδit⋅xig≤1,∀t∈T,∀g∈G.The incidence parameterδit and assignment variable xig associate airplanes, gates, and time.(2) Gate Utilization Constraints. For gate g∈G, if it is used by any airplane, the variable xg equals 1, otherwise 0. So, we have gate utilization constraints that indicate the relationship between xig and xg as follows:(2)∑i∈Ixig≤M⋅xg,∀g∈G,where M is a sufficiently large positive constant.(3) Airplane Service Constraints. Each airplane must and can only be assigned to one gate or the apron, and then:(3)∑g∈G∪​G′xig=1,∀i∈I.(4) Gate Compatibility Constraints. We consider the gate compatibility in this model, because gates in the different areas of terminal and satellite halls may have different functions, which are mainly influenced by facilities and equipment. The airplane gate compatibility incidence parameter σig is introduced, which equals 1 if airplane i∈I can be served by gate g∈G and otherwise 0. We can derive the values of σig based on the given airplane and gate types.(4)xig≤σig,∀i∈I,∀g∈G∪​G′.In particular, the apron can serve all types of airplanes andσig=1,g∈G′.(5) Constraints for Decision Variables.(5)xig=1if airplane i is assigned to gateg,0otherwise,∀i∈I,∀g∈G∪​G′,xg=1if gategis used,0otherwise,∀g∈G.Constraints (5) and (6) are binary requirements on the decision variables.


## 3.2.2. Objective Function

Gates are the scarce resource in an airport, and operational efficiency depends on the utilization of this bottleneck resource. Since the hub airport has terminal and satellite halls simultaneously, the GAP aims to make efficient use of the gates in the terminal and satellite halls and minimizes the operating costs.An airplane can use parking positions in the apron if it cannot be assigned to a gate, but the apron is usually far away from the terminal and satellite halls, and passengers need to take a shuttle bus between the terminal and the apron. This will increase the transfer time of passengers on the one hand and increase the operating costs of the airport on the other hand. To make efficient use of the gates and avoid assigning airplanes to the apron, the first objective is to minimize the number of airplanes assigned to the apron:(6)minZ1=∑i∈I∑g∈G′xig.This is a common objective in the literature of GAP (Ding et al. [6], Dorndorf et al. [7, 8], Drexl and Nikulin [9], Deng et al. [10]). It is equivalent to maximizing the number of airplanes assigned to gates. Furthermore, this objective can be easily extended to maximize the total usage time of gates since the dwell time of each airplane is given, but it has no significant impact on passenger service so we use the objective (6) in this study.Besides, the GAP is multi-objective in nature and operation costs for gates are expensive (including ground operation costs), which motivates us to consider objectives more comprehensively. Apart from minimizing the apron operation, the GAP also needs to consider the objective that minimizes the number of used gates, i.e.,(7)minZ2=∑g∈Gxg.In this study, we consider the objective function that consists of the number of airplanes assigned to the apron and the number of used gates and then formulate the GAP as a multi-objective optimization problem. For GAP in a hub airport with the apron, if we only consider the objective (6), gate operating hours may not be fully utilized in some situations; only consider the objective (7) is obviously not feasible either, which would assign all of the airplanes to the apron. Thus, the combination and trade-off between objectives (6) and (7) is comprehensive for GAP. We use linear weight to handle these two objectives and formulate the objective function as follows:(8)minZGAP=α1⋅Z1+α2⋅Z2,where α1 and α2 are positive weights to denote the trade-off between objectives. In particular, we can obtain a Pareto-optimal solution if α1 and α2 are set 1, or their values are set according to the preference of airport operators.


## 3.2.3. Mathematical Model for GAP

The GAP can be formulated as follows:(9)minZGAP=α1⋅∑i∈I∑g∈G′xig+α2⋅∑g∈Gxg,s.t.constraints1−6.The mathematical model for GAP given in (9) is binary integer linear programming. The model for GAP focuses on the gate resource optimization when a hub airport has both main terminal and satellite halls, and next, we will consider the impact of GAP on passengers and further improve the model involving different stakeholders.


## 3.3. Model for TGAP

Gate assignment affects the service quality of passengers, especially the transfer passengers in the hub airport where both main terminal and satellite halls are providing passenger service. Passengers may take a longer time to get from the arriving flight to the departing flight gate due to the gate assignment and may even exceed the transfer time budget resulting in a failed transfer. Thus, we will incorporate the service of transfer passengers in the GAP in this section.With the given flight timetable and transfer scheme (arriving airplanei1 and departing airplane i2) of passenger group p∈P, we can get the transfer time budget Bp=di2−ai1. The gates serving airplanes i1 and i2 are denoted as g1 and g2, respectively. Given the layout of terminal and satellite halls in the airport, the shortest transfer time τg1,g2 (including processing time, walking time, and MRT time) between any two gates is also fixed.The gate assignment will influence the shortest transfer time of passenger groupp. Here, we introduce the transfer pressure to describe the airport’s service level for transfer passengers. The transfer pressure is the ratio of shortest transfer time to transfer time budget, and the transfer pressure for passenger p is denoted by φp and defined as follows:(10)φp=τg1,g2Bp,ifi1,i2are both assigned to gates,τcBp,otherwise,where τc is the total transfer time (including process time and shuttle bus time) for passengers associated with the apron. If both associate airplanes of a passenger group are assigned to gates in the terminal and satellite halls, passengers need to do a gate-gate transfer with transfer time τg1,g2; otherwise, passengers need to do a gate-apron, apron-gate, or even apron-apron transfer with transfer time τc. Note that τc is longer than the shortest transfer time between any two gates because the parking positions in the apron are usually far away from the terminal and satellite halls.Then, we introduce the objective that minimizes the transfer pressure for passengers to capture the passenger service in the GAP of the hub airport; i.e.,(11)minZ3=∑p∈P∑g1∈G∪​G′∑g2∈G∪​G′xi1g1xi2g2φpnp.The GAP considering passenger transfer time budget can be formulated as follows:(12)minZTGAP=α1⋅∑i∈I∑g∈G′xig+α2⋅∑g∈Gxg+α3⋅∑p∈P∑g1∈G∪​G′∑g2∈G∪​G′xi1g1xi2g2φpnp,s.t.constraints1−6..The mathematical model given in (12) explicitly considers the transfer passenger service and shows the trade-off between passenger service and operating costs of GAP in the hub airport. The mathematical model (12) is nonlinear programming, and the nonlinearities come from the objective function associated with passenger, where the calculation of transfer pressure φp is a segmentation function.Table4 presents the complexity of the model for GAP and TGAP. It can be seen that the model size depends on the number of gates, airplanes, passenger groups, and demand discretization (number of discretized time intervals). Suppose that there is a hub airport with 10 gates and 100 airplanes with 100 transfer passenger groups, the research period is 0:00−24:00. If the discretization time interval is 5 min, there will be 120 variables and 2500 constraints in the GAP model (9). The number of variables in the TGAP model (11) is 1120, with the addition of variables related to transfer passengers.Table 4
Numbers of variables and constraints in the models.
Variables and constraintsQuantityVariablesxigI×G+IxgGφpPyi1,2g1,2P×G+12ConstraintsGate time conflict constraint (1)T×GGate utilization constraints (2)GAirplane service constraints (3)IGate compatibility constraints (4)I×G+IBinary constraints (5)I×G+IBinary constraints (6)GNote:⋅ represents the cardinality of a set.


## 4. Solution Approach

The mathematic model (9) for GAP is a binary integer linear programming and can be solved by several existing commercial solvers, such as CPLEX and Gurobi (see, e.g., Linderoth and Ralphs [27]; Atamturk and Savelsbergh [28]).As for the mathematic model (12) for TGAP, it is nonlinear programming with linear constraints, and we next propose two approaches to solve it.


### 4.1. Linearization Approach

In this section, the origin nonlinear programming model (12) will be transformed into binary integer linear programming by introducing new binary variables and linear constraints.Focusing on the nonlinear objective function of the model (12), the calculation of transfer pressure φp is a segmentation function as shown in Eq. (11). According to the analysis of transfer time under different scenarios in Section 3.3, only need to set the shortest transfer time associated with g∈G′ as τc, i.e., τg1,g2=τc,g1∈G′ or g2∈G′ the objective that minimizes the transfer pressure in (12) could be updated as follows:(13)minZ3=∑p∈P∑g1∈G∪​G′∑g2∈G∪​G′xi1g1xi2g2τg1,g2npBp.It can be observed that (13) is nonlinear because of productions of binary variables xi1g1 and xi2g2, and they can be replaced by auxiliary binary variables yi1,2g1,2. Following Williams [29], the productions can be replaced by adding linear constraints:(14)−xi1g1+yi1,2g1,2≤0−xi2g2+yi1,2g1,2≤0xi1g1+xi2g2−yi1,2g1,2≤1yi1,2g1,2∈0,1,∀p∈P,∀g1,g2∈G.Thus, the linearized model for TGAP considering the transfer passenger service can be formulated as follows:(15)minZTGAP=α1⋅∑i∈I∑g∈G′xig+α2⋅∑g∈Gxg+α3⋅∑p∈P∑g1∈G∪​G′∑g2∈G∪​G′yi1,2g1,2τg1,g2npBp,s.t.constraints1−6,14..Note that model (15) is linear programming and can easily be solved by commercial solvers such as CPLEX and Gurobi to find a globally optimal solution.As shown in Table4, the number of auxiliary binary variables yi1,2g1,2 is P×G+12. Based on the example in Section 3, there will be 121120 variables and 489000 constraints in the linearized model (15) for TGAP. Besides, when the number of passenger groups and airport gates increases, the number of variables and constraints increases rapidly, which takes a long computation time to solve the TGAP with commercial solvers. To address this issue, we further design a heuristic approach to solve the TGAP.


### 4.2. Heuristic Approach

The gate assignment problem is a complex nondeterministic polynomial hard (NP-hard) problem due to the complex layout of airports, multi-flights, passenger trips, and gate compatibility [30, 31], and many studies adopted heuristic approaches to solve it [16, 21, 24]. To solve TGAP in large hub airports requires an efficient algorithm to obtain a satisfactory solution and solve the problem in reasonable CPU time. The simulated annealing (SA) algorithm is a metaheuristic to approximate the global optimization and has good robustness. Thus, we propose an approach for TGAP at large hub airports based on the framework of the SA algorithm.Algorithm 1: Solving framework based on SA algorithm for TGAP.
(1)
Input Solution S0 of GAP as the initial solution of TGAP, passenger information (flights and volume), algorithm parameters (initial and end temperature T0,Tf, the maximum number of inner iterations mmax and temperature drop ratio θ).(2)
Calculate the objective valueZ0 in the model (12). Set current solution S←S0,Z←Z0 and the best solution S∗←S0,Z∗←Z0; the current temperature T←T0.(3)
Repeat(4)
m←0;(5)
Repeat(6)
m←m+1;(7)
Neighborhood searching using strategies for different objectives in Section 4.2(8)
① search for the neighborhood by passenger service strategy;(9)
② search for the neighborhood by gate utilization strategy;(10)
③ search for the neighborhood by apron airplane strategy.(11)
Get the neighborhood solutionS′ and Z′.(12)
Update the current solution and best solution(13)
ΔZ←Z′−Z;(14)
ifΔZ≤0then(15)
S←S′, Z←Z′ and S∗←S′, Z∗←Z′;(16)
else if (exp−ΔZ/T〉Random0,1) then(17)
S←S′, Z←Z′;(18)
end(19)
Untilm=mmax(20)
T←θ⋅T;(21)
UntilT〈Tf(22)
Output optimal TGAP solution S∗ and Z∗In Algorithm 1, we adopt the following strategies to adjust the assignment scheme and get neighborhood solutions.


#### 4.2.1. Initial Solution

The model (11) for TGAP has the same constraints as the model (9) for GAP, and we can use the optimal solution of model (9) as the initial solution. It is already efficient in terms of gate resource utilization. As for the model scales, note that the model (9) can be decomposed into two subproblems by gate compatibility on airplane types: one assignment for wide-body airplanes and associate gates and another for narrow-body airplanes and associate gates. In this way, the initial solution of TGAP is designed.


#### 4.2.2. Passenger Service Adjustment Strategy

The passenger service adjustment strategy aims to reduce the transfer pressure of passengers, which includes three options: insert option, swap operation, and remove operation. These operations are performed sequentially, with only one of them executed in each loop, and detailed options are shown as follows.In the current solution, we already know the gate assignment scheme, i.e., the specific gate of each airplane. As we know the transfer information of passenger groupp∈P, Pi1 and Pi2 are denoted as the subset of passenger groups whose arriving and departing airplane is i∈I, respectively. Then, we denote φi as the total transfer pressure of passengers associated with airplane i, which is given as follows:(16)φi=∑p∈Pi1φpnp+∑p∈Pi2φpnp.The total transfer pressure of each airplane is calculated by equation (16) and does the following operations: ① the airplane that has the maximum transfer pressure and is already assigned to a gate is selected. ② Insert operation: the subset of gates that has available time and already been used is found, the selected airplane is inserted into one of them randomly. If the subset is empty, the next operation is proceeded. ③ Swap operation: the subset of airplanes that has the same time interval and type (no violation of constraints (1) and (4)) is found, the selected airplane and one of them are randomly swapped. If the subset is empty, the next operation is proceeded. ④ Remove operation: if the above two operations are not executed, the subset of gates suitable for the selected airplane is found, one of them is chosen at random, and the selected airplane is assigned to this gate, and then, the airplanes with conflicts are assigned to the apron.


#### 4.2.3. Gate Utilization Strategy

The gate utilization strategy concentrates on reducing the number of used gates, which includes two options: insert option and remove operation. Based on the current solution, we could know the set of airplanes assigned to gateg∈G and denoted by Ig. ug is denoted as the time utilization ratio of gate g, which equals the ratio of occupied time to research period:(17)ug=∑i∈Igτb+di−aiT2−T1.To reduce the number of used gates, the following operations are executed: ①the gate with the lowest time utilization ratio using (17)is found, and if the ratio is lower than a threshold value (such as 40%), then next options are done. ② insert operation: for airplanes assigned to the selected gate, the subset of gates that has available time and already used is found, and these airplanes are inserted in one of them randomly. ③ Remove operation: the rest of the airplanes are assigned to the apron after the previous option.


#### 4.2.4. Apron Airplane Adjustment Strategy

The apron airplane adjustment strategy is designed to reduce the number of airplanes assigned to the apron and transfer pressure of passengers. Thus, included operations in this part of the strategy consider both of the two objectives. ① The total transfer pressure of each airplane in the apron by (16)is calculated and the maximum one of them is found. ② The insert and swap operations are executed. This airplane is randomly inserted into a gate that has available time periods; otherwise, it is swapped with another airplane assigned to a gate without violation of constraints (1) and (4). ③ If the above two operations are not satisfied, one of the airplanes in the apron is attempted insert into an available gate. ④ If there is any available empty gate, the airplane with the shortest overlap time period with other airplanes in the apron is found and assigned to the new gate.The proposed heuristic approach shown in Algorithm 1 is based on the framework of the SA algorithm, together with three strategies for improving different parts of objective functions, and it would find a satisfactory solution of TGAP in the model (13).


## 4.1. Linearization Approach

In this section, the origin nonlinear programming model (12) will be transformed into binary integer linear programming by introducing new binary variables and linear constraints.Focusing on the nonlinear objective function of the model (12), the calculation of transfer pressure φp is a segmentation function as shown in Eq. (11). According to the analysis of transfer time under different scenarios in Section 3.3, only need to set the shortest transfer time associated with g∈G′ as τc, i.e., τg1,g2=τc,g1∈G′ or g2∈G′ the objective that minimizes the transfer pressure in (12) could be updated as follows:(13)minZ3=∑p∈P∑g1∈G∪​G′∑g2∈G∪​G′xi1g1xi2g2τg1,g2npBp.It can be observed that (13) is nonlinear because of productions of binary variables xi1g1 and xi2g2, and they can be replaced by auxiliary binary variables yi1,2g1,2. Following Williams [29], the productions can be replaced by adding linear constraints:(14)−xi1g1+yi1,2g1,2≤0−xi2g2+yi1,2g1,2≤0xi1g1+xi2g2−yi1,2g1,2≤1yi1,2g1,2∈0,1,∀p∈P,∀g1,g2∈G.Thus, the linearized model for TGAP considering the transfer passenger service can be formulated as follows:(15)minZTGAP=α1⋅∑i∈I∑g∈G′xig+α2⋅∑g∈Gxg+α3⋅∑p∈P∑g1∈G∪​G′∑g2∈G∪​G′yi1,2g1,2τg1,g2npBp,s.t.constraints1−6,14..Note that model (15) is linear programming and can easily be solved by commercial solvers such as CPLEX and Gurobi to find a globally optimal solution.As shown in Table4, the number of auxiliary binary variables yi1,2g1,2 is P×G+12. Based on the example in Section 3, there will be 121120 variables and 489000 constraints in the linearized model (15) for TGAP. Besides, when the number of passenger groups and airport gates increases, the number of variables and constraints increases rapidly, which takes a long computation time to solve the TGAP with commercial solvers. To address this issue, we further design a heuristic approach to solve the TGAP.


## 4.2. Heuristic Approach

The gate assignment problem is a complex nondeterministic polynomial hard (NP-hard) problem due to the complex layout of airports, multi-flights, passenger trips, and gate compatibility [30, 31], and many studies adopted heuristic approaches to solve it [16, 21, 24]. To solve TGAP in large hub airports requires an efficient algorithm to obtain a satisfactory solution and solve the problem in reasonable CPU time. The simulated annealing (SA) algorithm is a metaheuristic to approximate the global optimization and has good robustness. Thus, we propose an approach for TGAP at large hub airports based on the framework of the SA algorithm.Algorithm 1: Solving framework based on SA algorithm for TGAP.
(1)
Input Solution S0 of GAP as the initial solution of TGAP, passenger information (flights and volume), algorithm parameters (initial and end temperature T0,Tf, the maximum number of inner iterations mmax and temperature drop ratio θ).(2)
Calculate the objective valueZ0 in the model (12). Set current solution S←S0,Z←Z0 and the best solution S∗←S0,Z∗←Z0; the current temperature T←T0.(3)
Repeat(4)
m←0;(5)
Repeat(6)
m←m+1;(7)
Neighborhood searching using strategies for different objectives in Section 4.2(8)
① search for the neighborhood by passenger service strategy;(9)
② search for the neighborhood by gate utilization strategy;(10)
③ search for the neighborhood by apron airplane strategy.(11)
Get the neighborhood solutionS′ and Z′.(12)
Update the current solution and best solution(13)
ΔZ←Z′−Z;(14)
ifΔZ≤0then(15)
S←S′, Z←Z′ and S∗←S′, Z∗←Z′;(16)
else if (exp−ΔZ/T〉Random0,1) then(17)
S←S′, Z←Z′;(18)
end(19)
Untilm=mmax(20)
T←θ⋅T;(21)
UntilT〈Tf(22)
Output optimal TGAP solution S∗ and Z∗In Algorithm 1, we adopt the following strategies to adjust the assignment scheme and get neighborhood solutions.


### 4.2.1. Initial Solution

The model (11) for TGAP has the same constraints as the model (9) for GAP, and we can use the optimal solution of model (9) as the initial solution. It is already efficient in terms of gate resource utilization. As for the model scales, note that the model (9) can be decomposed into two subproblems by gate compatibility on airplane types: one assignment for wide-body airplanes and associate gates and another for narrow-body airplanes and associate gates. In this way, the initial solution of TGAP is designed.


### 4.2.2. Passenger Service Adjustment Strategy

The passenger service adjustment strategy aims to reduce the transfer pressure of passengers, which includes three options: insert option, swap operation, and remove operation. These operations are performed sequentially, with only one of them executed in each loop, and detailed options are shown as follows.In the current solution, we already know the gate assignment scheme, i.e., the specific gate of each airplane. As we know the transfer information of passenger groupp∈P, Pi1 and Pi2 are denoted as the subset of passenger groups whose arriving and departing airplane is i∈I, respectively. Then, we denote φi as the total transfer pressure of passengers associated with airplane i, which is given as follows:(16)φi=∑p∈Pi1φpnp+∑p∈Pi2φpnp.The total transfer pressure of each airplane is calculated by equation (16) and does the following operations: ① the airplane that has the maximum transfer pressure and is already assigned to a gate is selected. ② Insert operation: the subset of gates that has available time and already been used is found, the selected airplane is inserted into one of them randomly. If the subset is empty, the next operation is proceeded. ③ Swap operation: the subset of airplanes that has the same time interval and type (no violation of constraints (1) and (4)) is found, the selected airplane and one of them are randomly swapped. If the subset is empty, the next operation is proceeded. ④ Remove operation: if the above two operations are not executed, the subset of gates suitable for the selected airplane is found, one of them is chosen at random, and the selected airplane is assigned to this gate, and then, the airplanes with conflicts are assigned to the apron.


### 4.2.3. Gate Utilization Strategy

The gate utilization strategy concentrates on reducing the number of used gates, which includes two options: insert option and remove operation. Based on the current solution, we could know the set of airplanes assigned to gateg∈G and denoted by Ig. ug is denoted as the time utilization ratio of gate g, which equals the ratio of occupied time to research period:(17)ug=∑i∈Igτb+di−aiT2−T1.To reduce the number of used gates, the following operations are executed: ①the gate with the lowest time utilization ratio using (17)is found, and if the ratio is lower than a threshold value (such as 40%), then next options are done. ② insert operation: for airplanes assigned to the selected gate, the subset of gates that has available time and already used is found, and these airplanes are inserted in one of them randomly. ③ Remove operation: the rest of the airplanes are assigned to the apron after the previous option.


### 4.2.4. Apron Airplane Adjustment Strategy

The apron airplane adjustment strategy is designed to reduce the number of airplanes assigned to the apron and transfer pressure of passengers. Thus, included operations in this part of the strategy consider both of the two objectives. ① The total transfer pressure of each airplane in the apron by (16)is calculated and the maximum one of them is found. ② The insert and swap operations are executed. This airplane is randomly inserted into a gate that has available time periods; otherwise, it is swapped with another airplane assigned to a gate without violation of constraints (1) and (4). ③ If the above two operations are not satisfied, one of the airplanes in the apron is attempted insert into an available gate. ④ If there is any available empty gate, the airplane with the shortest overlap time period with other airplanes in the apron is found and assigned to the new gate.The proposed heuristic approach shown in Algorithm 1 is based on the framework of the SA algorithm, together with three strategies for improving different parts of objective functions, and it would find a satisfactory solution of TGAP in the model (13).


## 4.2.1. Initial Solution

The model (11) for TGAP has the same constraints as the model (9) for GAP, and we can use the optimal solution of model (9) as the initial solution. It is already efficient in terms of gate resource utilization. As for the model scales, note that the model (9) can be decomposed into two subproblems by gate compatibility on airplane types: one assignment for wide-body airplanes and associate gates and another for narrow-body airplanes and associate gates. In this way, the initial solution of TGAP is designed.


## 4.2.2. Passenger Service Adjustment Strategy

The passenger service adjustment strategy aims to reduce the transfer pressure of passengers, which includes three options: insert option, swap operation, and remove operation. These operations are performed sequentially, with only one of them executed in each loop, and detailed options are shown as follows.In the current solution, we already know the gate assignment scheme, i.e., the specific gate of each airplane. As we know the transfer information of passenger groupp∈P, Pi1 and Pi2 are denoted as the subset of passenger groups whose arriving and departing airplane is i∈I, respectively. Then, we denote φi as the total transfer pressure of passengers associated with airplane i, which is given as follows:(16)φi=∑p∈Pi1φpnp+∑p∈Pi2φpnp.The total transfer pressure of each airplane is calculated by equation (16) and does the following operations: ① the airplane that has the maximum transfer pressure and is already assigned to a gate is selected. ② Insert operation: the subset of gates that has available time and already been used is found, the selected airplane is inserted into one of them randomly. If the subset is empty, the next operation is proceeded. ③ Swap operation: the subset of airplanes that has the same time interval and type (no violation of constraints (1) and (4)) is found, the selected airplane and one of them are randomly swapped. If the subset is empty, the next operation is proceeded. ④ Remove operation: if the above two operations are not executed, the subset of gates suitable for the selected airplane is found, one of them is chosen at random, and the selected airplane is assigned to this gate, and then, the airplanes with conflicts are assigned to the apron.


## 4.2.3. Gate Utilization Strategy

The gate utilization strategy concentrates on reducing the number of used gates, which includes two options: insert option and remove operation. Based on the current solution, we could know the set of airplanes assigned to gateg∈G and denoted by Ig. ug is denoted as the time utilization ratio of gate g, which equals the ratio of occupied time to research period:(17)ug=∑i∈Igτb+di−aiT2−T1.To reduce the number of used gates, the following operations are executed: ①the gate with the lowest time utilization ratio using (17)is found, and if the ratio is lower than a threshold value (such as 40%), then next options are done. ② insert operation: for airplanes assigned to the selected gate, the subset of gates that has available time and already used is found, and these airplanes are inserted in one of them randomly. ③ Remove operation: the rest of the airplanes are assigned to the apron after the previous option.


## 4.2.4. Apron Airplane Adjustment Strategy

The apron airplane adjustment strategy is designed to reduce the number of airplanes assigned to the apron and transfer pressure of passengers. Thus, included operations in this part of the strategy consider both of the two objectives. ① The total transfer pressure of each airplane in the apron by (16)is calculated and the maximum one of them is found. ② The insert and swap operations are executed. This airplane is randomly inserted into a gate that has available time periods; otherwise, it is swapped with another airplane assigned to a gate without violation of constraints (1) and (4). ③ If the above two operations are not satisfied, one of the airplanes in the apron is attempted insert into an available gate. ④ If there is any available empty gate, the airplane with the shortest overlap time period with other airplanes in the apron is found and assigned to the new gate.The proposed heuristic approach shown in Algorithm 1 is based on the framework of the SA algorithm, together with three strategies for improving different parts of objective functions, and it would find a satisfactory solution of TGAP in the model (13).


## 5. Case Studies

To demonstrate the performance of the proposed models and solve approaches, we use the data of the Shanghai Pudong International Airport in China as a case study. We will describe the experiment data in Section5.1. The numerical results are presented in Section 5.2.All numerical tests are conducted on a personal computer with Intel® Core (™) 3.00 GHz processor and 16.00 GB RAM and Windows 10 Home Edition Operating System (64 bit). The YALMIP-R20190425 together with MATLAB R2019b is used to conduct the numerical tests. The commercial solver Gurobi optimization studio 8.1.1 (with academic license) is adopted to solve GAP and linearized TGAP models, and the solver used the branch-and-cut algorithm to find optimal solutions for the above two mixed-integer programming models.


### 5.1. Data and Parameter Setting

We consider a real-world case study on the Shanghai Pudong International Airport, which is an important hub airport in eastern China. The gates are integrated used in a terminalT and connected satellite hall S, and both terminal T and satellite hall S could handle transfer processes for passengers. There is an MRT line that connects T and S to quickly transport passengers, assuming that passengers’ MRT time for a one-way trip is 5 minutes (for layout, see Figure 5). We consider the GAP and TGAP for 28 gates in terminal T and 41 gates in satellite hall S and an apron, and the detailed information of gates can be found in Table 5. The compatibility of gates such as service for domestic/international flights and wide/narrow-body airplanes is also given. τc is set as 180 minutes.Figure 5
Layout of terminal T1 and satellite hall S1 in Shanghai Pudong International Airport.Table 5
Gate information and compatibility in the case study.
Gate no.TerminalArrival serviceDeparture serviceAirplane typeGate no.TerminalArrival serviceDeparture serviceAirplane typeT1TIINS1SDDNT2TIIWS2SDDNT3TIIWS3SDDNT4TIIWS4SDDNT5TID, IWS5SDDNT6TD, ID, IWS6SDDNT7TD, ID, INS7SDDNT8TD, IDNS8SDDNT9TD, IDNS9SDDNT10TDDNS10SDDNT11TDDNS11SIINT12TDDNS12SIINT13TDDNS13SIINT14TDDNS14SDDNT15TDDNS15SDDNT16TDDNS16SDDNT17TDDNS17SDDNT18TDDNS18SDDNT19TDDNS19SDDNT20TDD, INS20SDDNT21TDD, INS21SDDNT22TD, ID, INS22SDDNT23TD, ID, IWS23SDDNT24TD, ID, IWS24SDDNT25TD, IIWS25SDDNT26TIIWS26SDDNT27TIIWS27SDDNT28TIIWS28SDDNS29SDDWS36SIIWS30SDDWS37SIIWS31SIIWS38SIIWS32SIIWS39SIIWS33SIIWS40SIIWS34SIIWS41SIIWS35SIIWNote. T: terminal, S: satellite hall, D: domestic flight service, I: international flight service, W: wide-body airplane service, N: narrow-body airplane service.In this case study, the considered research period is set as0:00−24:00, which covers a full day of operations. We select 296 airplanes related to the above gates of China Eastern Airlines and Xiamen Airlines on January 20, 2018. Table 6 shows several records as an example, and every record corresponds to one airplane, which services two flights. The information of airplanes includes the arrival and departure date, arrival and departure time, arrival and departure flights, airplane types (wide/narrow-body), and flight types (domestic/international).Table 6
Partial airplane and flight records.
Airplane no.Arrival flight numberArrival date and timeArrival typeDeparture flight numberDeparture date and timeDeparture typeAirplane type1MU6753Jan 19, 19:50DMU6358Jan 20, 08:15DN2MU6785Jan 20, 11:00DMU398Jan 20, 13:10IN3MU6155Jan 20, 13:20IMU6494Jan 20, 14:25DN4MU663Jan 20, 16:30IMU6588Jan 20, 20:05IW5FM9188Jan 20, 17:20DFM865Jan 20, 18:20IN6MU5588Jan 20, 21:20DMU5515Jan 21, 08:55DNNote. D: domestic flight, I: international flight, W: wide-body airplane, N: narrow-body airplane.Meanwhile, transfer information of more than 3000 passengers is selected and divided into groups based on arrival and departure flights. The example of information is shown in Table7, which includes arrival and departure flight, arrival and departure date, and passenger number in groups. Combining with the information of airplanes and flights in Table 6, we can easily get the transfer time budget of each passenger group. Since the layout of the airport is set, the shortest transfer time τg1,g2 between any two gates is also determined, including processing time, walking time, and MRT time. The buffer time of gates τb is set to 45 minutes.Table 7
Partial transfer passengers’ information.
Passenger group no.Number of passengersArrival flight numberArrival date and timeDeparture flight numberDeparture date and time110MU5668Jan 19, 18:35MU739Jan 20, 00:20244MU212Jan 20, 10:20MU207Jan 20, 12:0539MU5698Jan 20, 14:30MU545Jan 20, 16:10420MU504Jan 20, 18:25MU6720Jan 20, 20:5557MU5130Jan 20, 21:40MU5023Jan 21, 00:15Table 8
Performance comparison of GAP and linearized TGAP solutions.
ProblemZ1Z2Z3Gate time utilization rateGAP47651361.15∗66.40%TGAP48651039.3170.21%∗Note: the total passenger transfer pressure Z3 of GAP is calculated after solving the optimal solution.The linear weights in the model (10), (13), and (16) are, respectively,α1=296,α2=1,α3=10; the algorithm parameters are set as follows: T0=106,Tf=5,mmax=50,θ=0.5.


### 5.2. Computational Results

Given the above data and settings, the proposed solution approaches will be implemented for GAP and TGAP. The results of GAP, TGAP with linearization approach, and performance comparison are shown in Subsection5.2.1; Subsection 5.2.2 shows the result of TGAP solved by the heuristic approach.


#### 5.2.1. Solutions of GAP and Linearized TGAP

In this subsection, we solve the GAP and linearized TGAP by commercial solver Gurobi optimization, and the CPU time to solve GAP is 5.75s. The result of GAP is shown in Figure6, and the horizontal axis represents the research period (0:00−24:00 on January 20, 2018), and the vertical axis represents the total of 69 gates in terminal T and satellite hall S. The colored bars in Figure 6 represent the time period when the airplanes occupy the corresponding gates, and the buff time is not included. It can be clearly seen that airplanes satisfy the time conflict constraints of gates and buffer time is also held between two adjacent airplanes. One can find that airplanes arriving and departing during 0:00−6:00 usually occupy the gates for a long time as passengers tend not to travel at this period. The result of TGAP is shown in Figure 7, which also satisfies all of the constraints.Figure 6
Optimal gate assignment scheme of GAP.Figure 7
Optimal gate assignment scheme of linearized TGAP.From Figure6, we can find that several gates (S29, S30, S39, and S41) are not occupied by any airplane, and they are all serving wide-body airplanes. Meanwhile, Figure 8 shows that all wide-body airplanes are already assigned to gates in GAP and that ratio for narrow-body airplanes is 81%, and the total number of airplanes successfully assigned to the gates is 249. Here is why we consider the objective that minimizes the number of used gates in (7), which can improve the efficiency of gate utilization when one kind of resource is sufficient, i.e., gates for wide-body airplanes. Thus, the combination of objectives (6) and (7) is more comprehensive for gate utilization in both GAP and TGAP.Figure 8
Assigned numbers and rates for different types of airplanes in GAP.Next, we compare the solution of GAP and TGAP, and values of different parts in objective functions are shown in Table8, of which the value of Z3 (transfer pressure) in GAP is calculated based on the optimal solution of the model (10) and services for passengers are not taken into account. It is obvious from Table 8 that when the first and second objectives (minimizing the number of apron airplanes Z1 and used gates Z2) are close in the GAP and TGAP, considering the objective Z3 can significantly reduce the transfer pressure of passengers (23.64% reduction). That is, model (12) of the TGAP can improve the service level of transfer passengers without increasing the resource requirement in the hub airport. Moreover, although the number of assigned airplanes has decreased in the TGAP solution, the time utilization rate of gates in terminal T and satellite hall S has increased, and the scheme in TGAP assigns airplanes serving more transfer passengers and with less occupation time to the gates. This also demonstrates that considering the gate resource utilization and passenger service simultaneously is a more comprehensive way to address gate assignment in the hub airport.


#### 5.2.2. Solution of TGAP Adopting Heuristic Approach

Although the proposed linearization approach in Section4.1 can obtain the global optimal solution for TGAP, it takes a long time to converge. We adopted the commercial solver Gurobi optimization studio 8.1.1 to solve the linearized TGAP, and the CPU time to get the optimal solution is 6.09 h. The proposed heuristic approach takes 726s to solve the TGAP with the same input and parameters and only has a 2.59% solution GAP with linearization approach, and the gate assignment scheme is shown in Figure 9 as follows.Figure 9
Gate assignment scheme of TGAP solved by the heuristic approach.Passenger group no. 3 in Table7 is taken as an example, passenger transfers from flight MU5698 arriving on January 20, 14:30, to flight MU545 departing at January 20, 16:10, and the transfer time budget is 100 min. In the GAP solution, airplanes separately serving the arrival and departure flight are assigned to gates S5 and T3. As the two gates are not in the same terminal, the shortest transfer time for passengers is 60 min. When we take the transfer pressure into account in TGAP, the above two airplanes are assigned to gates T18 and T5, which are both in the terminal T, passengers’ shortest transfer time reduced to 35 min, and transfer pressure decreased from 0.60 to 0.35. Furthermore, the total transfer pressure of passengers in the solution of TGAP by the heuristic approach is still lower than that in the solution of GAP. This indicates that the TGAP well considered the service for passengers and realized the integrated assignment of gates in terminal and satellite halls.As shown in Figure10, gates in the terminal T are all used due to the shorter transfer time related to the gates in T than that in S, and there are 3 gates in the satellite hall S serving wide-body airplanes that are not used. The total utilization rate of gates is 96%, and the time utilization rate is 69.98%. For TGAP, although the gate time utilization rate in the solution of the linearized approach (70.21%) is higher than that of the heuristic approach, the difference is not significant.Figure 10
Gate utilization in terminal T and satellite hall S in TGAP.Next, we compare the passenger transfer pressure in three cases: the GAP solution, linearized approach of TGAP solution, and heuristic approach of TGAP solution. The proportion of passengers within different transfer pressure intervals of the above three solutions are reported in Figure11, where we observe that most of the passengers’ transfer pressure remains at a relatively low level and lies in the range of 0.1,0.5 in all three cases. Two solutions of TGAP are compared with the GAP solution, and we can see that the quantity of passengers who experience low transfer pressure 0.1,0.3 in TGAP solutions is significantly more than that in the GAP solution, while in the high transfer pressure range 0.5,1.0, the proportion of passengers in TGAP solutions is less than that in the GAP solution. This result indicates that proposed TGAP models could improve the service for transfer passengers.Figure 11
Comparison of passenger transfer pressure.Turning now to solutions of TGAP by linearization approach and heuristic approach, the distributions of passenger transfer pressure in these two solutions are comparable, which means the proposed heuristic approach could obtain a satisfactory solution in a reasonable time. What is striking in Figure11 is that some passengers in all three solutions have transfer pressure greater than 1 because related airplanes are assigned to the apron, and this situation is enhanced in TGAP solutions.


## 5.1. Data and Parameter Setting

We consider a real-world case study on the Shanghai Pudong International Airport, which is an important hub airport in eastern China. The gates are integrated used in a terminalT and connected satellite hall S, and both terminal T and satellite hall S could handle transfer processes for passengers. There is an MRT line that connects T and S to quickly transport passengers, assuming that passengers’ MRT time for a one-way trip is 5 minutes (for layout, see Figure 5). We consider the GAP and TGAP for 28 gates in terminal T and 41 gates in satellite hall S and an apron, and the detailed information of gates can be found in Table 5. The compatibility of gates such as service for domestic/international flights and wide/narrow-body airplanes is also given. τc is set as 180 minutes.Figure 5
Layout of terminal T1 and satellite hall S1 in Shanghai Pudong International Airport.Table 5
Gate information and compatibility in the case study.
Gate no.TerminalArrival serviceDeparture serviceAirplane typeGate no.TerminalArrival serviceDeparture serviceAirplane typeT1TIINS1SDDNT2TIIWS2SDDNT3TIIWS3SDDNT4TIIWS4SDDNT5TID, IWS5SDDNT6TD, ID, IWS6SDDNT7TD, ID, INS7SDDNT8TD, IDNS8SDDNT9TD, IDNS9SDDNT10TDDNS10SDDNT11TDDNS11SIINT12TDDNS12SIINT13TDDNS13SIINT14TDDNS14SDDNT15TDDNS15SDDNT16TDDNS16SDDNT17TDDNS17SDDNT18TDDNS18SDDNT19TDDNS19SDDNT20TDD, INS20SDDNT21TDD, INS21SDDNT22TD, ID, INS22SDDNT23TD, ID, IWS23SDDNT24TD, ID, IWS24SDDNT25TD, IIWS25SDDNT26TIIWS26SDDNT27TIIWS27SDDNT28TIIWS28SDDNS29SDDWS36SIIWS30SDDWS37SIIWS31SIIWS38SIIWS32SIIWS39SIIWS33SIIWS40SIIWS34SIIWS41SIIWS35SIIWNote. T: terminal, S: satellite hall, D: domestic flight service, I: international flight service, W: wide-body airplane service, N: narrow-body airplane service.In this case study, the considered research period is set as0:00−24:00, which covers a full day of operations. We select 296 airplanes related to the above gates of China Eastern Airlines and Xiamen Airlines on January 20, 2018. Table 6 shows several records as an example, and every record corresponds to one airplane, which services two flights. The information of airplanes includes the arrival and departure date, arrival and departure time, arrival and departure flights, airplane types (wide/narrow-body), and flight types (domestic/international).Table 6
Partial airplane and flight records.
Airplane no.Arrival flight numberArrival date and timeArrival typeDeparture flight numberDeparture date and timeDeparture typeAirplane type1MU6753Jan 19, 19:50DMU6358Jan 20, 08:15DN2MU6785Jan 20, 11:00DMU398Jan 20, 13:10IN3MU6155Jan 20, 13:20IMU6494Jan 20, 14:25DN4MU663Jan 20, 16:30IMU6588Jan 20, 20:05IW5FM9188Jan 20, 17:20DFM865Jan 20, 18:20IN6MU5588Jan 20, 21:20DMU5515Jan 21, 08:55DNNote. D: domestic flight, I: international flight, W: wide-body airplane, N: narrow-body airplane.Meanwhile, transfer information of more than 3000 passengers is selected and divided into groups based on arrival and departure flights. The example of information is shown in Table7, which includes arrival and departure flight, arrival and departure date, and passenger number in groups. Combining with the information of airplanes and flights in Table 6, we can easily get the transfer time budget of each passenger group. Since the layout of the airport is set, the shortest transfer time τg1,g2 between any two gates is also determined, including processing time, walking time, and MRT time. The buffer time of gates τb is set to 45 minutes.Table 7
Partial transfer passengers’ information.
Passenger group no.Number of passengersArrival flight numberArrival date and timeDeparture flight numberDeparture date and time110MU5668Jan 19, 18:35MU739Jan 20, 00:20244MU212Jan 20, 10:20MU207Jan 20, 12:0539MU5698Jan 20, 14:30MU545Jan 20, 16:10420MU504Jan 20, 18:25MU6720Jan 20, 20:5557MU5130Jan 20, 21:40MU5023Jan 21, 00:15Table 8
Performance comparison of GAP and linearized TGAP solutions.
ProblemZ1Z2Z3Gate time utilization rateGAP47651361.15∗66.40%TGAP48651039.3170.21%∗Note: the total passenger transfer pressure Z3 of GAP is calculated after solving the optimal solution.The linear weights in the model (10), (13), and (16) are, respectively,α1=296,α2=1,α3=10; the algorithm parameters are set as follows: T0=106,Tf=5,mmax=50,θ=0.5.


## 5.2. Computational Results

Given the above data and settings, the proposed solution approaches will be implemented for GAP and TGAP. The results of GAP, TGAP with linearization approach, and performance comparison are shown in Subsection5.2.1; Subsection 5.2.2 shows the result of TGAP solved by the heuristic approach.


### 5.2.1. Solutions of GAP and Linearized TGAP

In this subsection, we solve the GAP and linearized TGAP by commercial solver Gurobi optimization, and the CPU time to solve GAP is 5.75s. The result of GAP is shown in Figure6, and the horizontal axis represents the research period (0:00−24:00 on January 20, 2018), and the vertical axis represents the total of 69 gates in terminal T and satellite hall S. The colored bars in Figure 6 represent the time period when the airplanes occupy the corresponding gates, and the buff time is not included. It can be clearly seen that airplanes satisfy the time conflict constraints of gates and buffer time is also held between two adjacent airplanes. One can find that airplanes arriving and departing during 0:00−6:00 usually occupy the gates for a long time as passengers tend not to travel at this period. The result of TGAP is shown in Figure 7, which also satisfies all of the constraints.Figure 6
Optimal gate assignment scheme of GAP.Figure 7
Optimal gate assignment scheme of linearized TGAP.From Figure6, we can find that several gates (S29, S30, S39, and S41) are not occupied by any airplane, and they are all serving wide-body airplanes. Meanwhile, Figure 8 shows that all wide-body airplanes are already assigned to gates in GAP and that ratio for narrow-body airplanes is 81%, and the total number of airplanes successfully assigned to the gates is 249. Here is why we consider the objective that minimizes the number of used gates in (7), which can improve the efficiency of gate utilization when one kind of resource is sufficient, i.e., gates for wide-body airplanes. Thus, the combination of objectives (6) and (7) is more comprehensive for gate utilization in both GAP and TGAP.Figure 8
Assigned numbers and rates for different types of airplanes in GAP.Next, we compare the solution of GAP and TGAP, and values of different parts in objective functions are shown in Table8, of which the value of Z3 (transfer pressure) in GAP is calculated based on the optimal solution of the model (10) and services for passengers are not taken into account. It is obvious from Table 8 that when the first and second objectives (minimizing the number of apron airplanes Z1 and used gates Z2) are close in the GAP and TGAP, considering the objective Z3 can significantly reduce the transfer pressure of passengers (23.64% reduction). That is, model (12) of the TGAP can improve the service level of transfer passengers without increasing the resource requirement in the hub airport. Moreover, although the number of assigned airplanes has decreased in the TGAP solution, the time utilization rate of gates in terminal T and satellite hall S has increased, and the scheme in TGAP assigns airplanes serving more transfer passengers and with less occupation time to the gates. This also demonstrates that considering the gate resource utilization and passenger service simultaneously is a more comprehensive way to address gate assignment in the hub airport.


### 5.2.2. Solution of TGAP Adopting Heuristic Approach

Although the proposed linearization approach in Section4.1 can obtain the global optimal solution for TGAP, it takes a long time to converge. We adopted the commercial solver Gurobi optimization studio 8.1.1 to solve the linearized TGAP, and the CPU time to get the optimal solution is 6.09 h. The proposed heuristic approach takes 726s to solve the TGAP with the same input and parameters and only has a 2.59% solution GAP with linearization approach, and the gate assignment scheme is shown in Figure 9 as follows.Figure 9
Gate assignment scheme of TGAP solved by the heuristic approach.Passenger group no. 3 in Table7 is taken as an example, passenger transfers from flight MU5698 arriving on January 20, 14:30, to flight MU545 departing at January 20, 16:10, and the transfer time budget is 100 min. In the GAP solution, airplanes separately serving the arrival and departure flight are assigned to gates S5 and T3. As the two gates are not in the same terminal, the shortest transfer time for passengers is 60 min. When we take the transfer pressure into account in TGAP, the above two airplanes are assigned to gates T18 and T5, which are both in the terminal T, passengers’ shortest transfer time reduced to 35 min, and transfer pressure decreased from 0.60 to 0.35. Furthermore, the total transfer pressure of passengers in the solution of TGAP by the heuristic approach is still lower than that in the solution of GAP. This indicates that the TGAP well considered the service for passengers and realized the integrated assignment of gates in terminal and satellite halls.As shown in Figure10, gates in the terminal T are all used due to the shorter transfer time related to the gates in T than that in S, and there are 3 gates in the satellite hall S serving wide-body airplanes that are not used. The total utilization rate of gates is 96%, and the time utilization rate is 69.98%. For TGAP, although the gate time utilization rate in the solution of the linearized approach (70.21%) is higher than that of the heuristic approach, the difference is not significant.Figure 10
Gate utilization in terminal T and satellite hall S in TGAP.Next, we compare the passenger transfer pressure in three cases: the GAP solution, linearized approach of TGAP solution, and heuristic approach of TGAP solution. The proportion of passengers within different transfer pressure intervals of the above three solutions are reported in Figure11, where we observe that most of the passengers’ transfer pressure remains at a relatively low level and lies in the range of 0.1,0.5 in all three cases. Two solutions of TGAP are compared with the GAP solution, and we can see that the quantity of passengers who experience low transfer pressure 0.1,0.3 in TGAP solutions is significantly more than that in the GAP solution, while in the high transfer pressure range 0.5,1.0, the proportion of passengers in TGAP solutions is less than that in the GAP solution. This result indicates that proposed TGAP models could improve the service for transfer passengers.Figure 11
Comparison of passenger transfer pressure.Turning now to solutions of TGAP by linearization approach and heuristic approach, the distributions of passenger transfer pressure in these two solutions are comparable, which means the proposed heuristic approach could obtain a satisfactory solution in a reasonable time. What is striking in Figure11 is that some passengers in all three solutions have transfer pressure greater than 1 because related airplanes are assigned to the apron, and this situation is enhanced in TGAP solutions.


## 5.2.1. Solutions of GAP and Linearized TGAP

In this subsection, we solve the GAP and linearized TGAP by commercial solver Gurobi optimization, and the CPU time to solve GAP is 5.75s. The result of GAP is shown in Figure6, and the horizontal axis represents the research period (0:00−24:00 on January 20, 2018), and the vertical axis represents the total of 69 gates in terminal T and satellite hall S. The colored bars in Figure 6 represent the time period when the airplanes occupy the corresponding gates, and the buff time is not included. It can be clearly seen that airplanes satisfy the time conflict constraints of gates and buffer time is also held between two adjacent airplanes. One can find that airplanes arriving and departing during 0:00−6:00 usually occupy the gates for a long time as passengers tend not to travel at this period. The result of TGAP is shown in Figure 7, which also satisfies all of the constraints.Figure 6
Optimal gate assignment scheme of GAP.Figure 7
Optimal gate assignment scheme of linearized TGAP.From Figure6, we can find that several gates (S29, S30, S39, and S41) are not occupied by any airplane, and they are all serving wide-body airplanes. Meanwhile, Figure 8 shows that all wide-body airplanes are already assigned to gates in GAP and that ratio for narrow-body airplanes is 81%, and the total number of airplanes successfully assigned to the gates is 249. Here is why we consider the objective that minimizes the number of used gates in (7), which can improve the efficiency of gate utilization when one kind of resource is sufficient, i.e., gates for wide-body airplanes. Thus, the combination of objectives (6) and (7) is more comprehensive for gate utilization in both GAP and TGAP.Figure 8
Assigned numbers and rates for different types of airplanes in GAP.Next, we compare the solution of GAP and TGAP, and values of different parts in objective functions are shown in Table8, of which the value of Z3 (transfer pressure) in GAP is calculated based on the optimal solution of the model (10) and services for passengers are not taken into account. It is obvious from Table 8 that when the first and second objectives (minimizing the number of apron airplanes Z1 and used gates Z2) are close in the GAP and TGAP, considering the objective Z3 can significantly reduce the transfer pressure of passengers (23.64% reduction). That is, model (12) of the TGAP can improve the service level of transfer passengers without increasing the resource requirement in the hub airport. Moreover, although the number of assigned airplanes has decreased in the TGAP solution, the time utilization rate of gates in terminal T and satellite hall S has increased, and the scheme in TGAP assigns airplanes serving more transfer passengers and with less occupation time to the gates. This also demonstrates that considering the gate resource utilization and passenger service simultaneously is a more comprehensive way to address gate assignment in the hub airport.


## 5.2.2. Solution of TGAP Adopting Heuristic Approach

Although the proposed linearization approach in Section4.1 can obtain the global optimal solution for TGAP, it takes a long time to converge. We adopted the commercial solver Gurobi optimization studio 8.1.1 to solve the linearized TGAP, and the CPU time to get the optimal solution is 6.09 h. The proposed heuristic approach takes 726s to solve the TGAP with the same input and parameters and only has a 2.59% solution GAP with linearization approach, and the gate assignment scheme is shown in Figure 9 as follows.Figure 9
Gate assignment scheme of TGAP solved by the heuristic approach.Passenger group no. 3 in Table7 is taken as an example, passenger transfers from flight MU5698 arriving on January 20, 14:30, to flight MU545 departing at January 20, 16:10, and the transfer time budget is 100 min. In the GAP solution, airplanes separately serving the arrival and departure flight are assigned to gates S5 and T3. As the two gates are not in the same terminal, the shortest transfer time for passengers is 60 min. When we take the transfer pressure into account in TGAP, the above two airplanes are assigned to gates T18 and T5, which are both in the terminal T, passengers’ shortest transfer time reduced to 35 min, and transfer pressure decreased from 0.60 to 0.35. Furthermore, the total transfer pressure of passengers in the solution of TGAP by the heuristic approach is still lower than that in the solution of GAP. This indicates that the TGAP well considered the service for passengers and realized the integrated assignment of gates in terminal and satellite halls.As shown in Figure10, gates in the terminal T are all used due to the shorter transfer time related to the gates in T than that in S, and there are 3 gates in the satellite hall S serving wide-body airplanes that are not used. The total utilization rate of gates is 96%, and the time utilization rate is 69.98%. For TGAP, although the gate time utilization rate in the solution of the linearized approach (70.21%) is higher than that of the heuristic approach, the difference is not significant.Figure 10
Gate utilization in terminal T and satellite hall S in TGAP.Next, we compare the passenger transfer pressure in three cases: the GAP solution, linearized approach of TGAP solution, and heuristic approach of TGAP solution. The proportion of passengers within different transfer pressure intervals of the above three solutions are reported in Figure11, where we observe that most of the passengers’ transfer pressure remains at a relatively low level and lies in the range of 0.1,0.5 in all three cases. Two solutions of TGAP are compared with the GAP solution, and we can see that the quantity of passengers who experience low transfer pressure 0.1,0.3 in TGAP solutions is significantly more than that in the GAP solution, while in the high transfer pressure range 0.5,1.0, the proportion of passengers in TGAP solutions is less than that in the GAP solution. This result indicates that proposed TGAP models could improve the service for transfer passengers.Figure 11
Comparison of passenger transfer pressure.Turning now to solutions of TGAP by linearization approach and heuristic approach, the distributions of passenger transfer pressure in these two solutions are comparable, which means the proposed heuristic approach could obtain a satisfactory solution in a reasonable time. What is striking in Figure11 is that some passengers in all three solutions have transfer pressure greater than 1 because related airplanes are assigned to the apron, and this situation is enhanced in TGAP solutions.


## 6. Conclusions and Future Research

In this study, we focus on the impacts of gate assignment on the service of transfer passengers in the hub airport with satellite halls. First, a binary linear programming model for GAP is proposed that considers the gate time conflict, gate compatibility constraints, and the airport operator-oriented objective functions. Then, we introduce the transfer time budget and transfer pressure to measure the passenger service and formulate the TGAP as a nonlinear programming with linear constraints. In particular, multi-objective functions were considered in the TGAP model, including transfer demand-oriented and operator-oriented objectives. We proposed a linearization approach and a SA algorithm-based heuristic approach to solve the nonlinear model of TGAP. Finally, the case study based on practical data demonstrated the benefits of the proposed models and solution approaches. In the experimental results, it was verified that the proposed TGAP model and solution approaches can improve the service for transfer passengers and lead to more efficient utilization of gate resources in the hub airport.Further research could consider the randomness of transfer passenger demand and the effects of random flight delay on gate assignment and transfer passenger service. We can also manage the fairness of passengers through transfer pressure in the gate assignment problem.



---

*Source: 5087941-2022-04-25.xml*