# Simulated Annealing Method-Based Flight Schedule Optimization in Multiairport Systems

Authors: Xi Geng; Minghua Hu
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Integrated development and operational collaboration of regional airport groups have the potential to improve capacity and safety and also reduce environmental impacts and operational costs. However, research in multiairport systems (MASs), especially in China, is still in its infancy, with the consequences of unbalanced development, inadequate coordination, unclear function partitioning, difficulty in air traffic management, and poor service quality of regional airports. Considering these characteristics influencing effective interaction and collaboration of regional airports, this paper formulates a model to optimize the flight schedules in the MAS with multiple objectives of minimizing the maximum displacement of all flights, the weighted sum of total flight adjustment of each airport, and flight delays. An improved simulated annealing algorithm (SAA) is designed to solve the proposed multiobjective optimization problem. The model is applied to a case of the Beijing-Tianjin-Hebei Airport Group. The computational results demonstrate that the model generates significant reductions in maximum displacement, average displacement, and average delay, compared to the First-Come-First-Served (FCFS) principle. The model proposed in this paper can be used by civil aviation authorities, air navigation service providers, and airlines to facilitate the integrated management of flight schedules in the MAS.


---

## Body

## 1. Introduction

In order to improve the integrated development and operation of a group of airports in a multiairport system, the allocation of achievable flight resources should be fully optimized to significantly reduce congestion and delays. In a multiairport system, the relevant airports work together in a collaborative way towards their common goals. To date, research has focused on optimizing flight time resources at the tactical level. However, delivering real change in resolving congestion and delay requires the consideration of strategic level of operations, through optimizing the flight schedules.Recently, the problem of flight scheduling and demand management has attracted considerable attention. Several studies focus on slot allocation based on market-based mechanisms such as congestion pricing and slot auctions [1–4]. Other studies seek an integrated approach to improve flight schedule coordination, through a joint optimization of flight schedules at the strategic level and airport operation efficiency at the tactical level [5, 6]. Simaiakis et al. optimize the allocation of airport capacity to airlines at slot-controlled airports in Europe by minimizing the difference between the requested and allocated scheduled times [7]. Based on the evaluation of the impact of flight continuity and passenger demands on airport capacity, Yang et al. [8] formulate a model to reduce flight delays in airport systems. The squeaky-wheel optimization (SWO) algorithm is improved and used to search for the minimal flight adjustment allocation scheme at the Beijing Capital airport.The existing studies above are limited as they only consider adjusting the demands through flight schedules, while ignoring the interaction of several airports in a region that compete for limited airspace resources. The former is addressed by [9] through a simulation-based optimization of flight schedule in the Pearl River Delta (PRD) region. Postorino and Praticò [10] illustrate the application of the multiple-criteria decision-making (MCDM) method to validate the role and position of each airport within an MAS. To solve the multiairport ground-holding problem, some researchers have proposed multiobjective optimization approaches considering the objectives of minimizing the total delay time, total delay cost, total number of adjusted flights, and the total number of delayed flights, subject to the constraints such as airspace capacity and aircraft turn-around process [11]. Sidiropoulos et al. [12] propose a framework for the design and optimization of dynamic arrival and departure routing in airport terminal maneuvering areas (TMAs), which significantly improves the operational efficiency in MAS airspaces compared to the conventional segregated approach. Yin et al. [13] propose a methodological and assessment framework for runway configuration with a focus on the exploitation of multiple active runways in metroplex airports.The optimization of flight allocation has been widely studied through various operation research approaches. Unfortunately, most of the corresponding models are formulated as a single-objective optimization which mainly focuses on minimizing flight delay [10, 11]. Ma et al. [14] consider a multiairport system with its surrounding airspace to attempt to solve the problem of optimal aircraft routing and scheduling. These research efforts have achieved some progress in improving slot management. However, they ignore the imbalance between air traffic demand and airport capacity in the MAS. Therefore, to significantly improve airport operations and alleviate congestion in terminal maneuvering areas, this paper focuses on flight schedule optimization in regional multiairport systems through the dual dimensions of space and time. In this paper, an optimization model of flight schedule in multiairport systems is formulated to minimize the maximum displacement of all flights, considering a weighted flight adjustment for each airport in the multiairport systems. To date, most of the algorithms used in flight management in individual airports and multiairport systems are heuristics and metaheuristics [15–18]. Additionally, branch and bound, branch and price, and queuing theory have also been adopted to solve specific problem formulations [19, 20]. The simulated annealing algorithm (SAA) is a metaheuristic algorithm which can be used to approximate the global solution in a large search space for mathematical optimization problems. Although the SAA has been used in other research fields, e.g., job-shop problem, sequencing problem, and resource allocation [21–23], it is not widely used in civil aviation research and in particular flight scheduling in multiairport systems.When optimizing flight schedule, the first thing is to comply with the safety requirements and relevant operational regulations. All aircraft’s takeoff and landing times must be assigned as soon as possible to achieve optimal allocation of airspace and runway resources and minimal total delay time of TMA departures and arrivals. Besides, a scheduling scheme must be set without extra workload on air traffic controllers. In addition, the system should facilitate a flight to land at the most economic speed, minimizing the total fuel cost resulting from deviation of aircraft start-times from respective ready-times. The scheduling should be generated to facilitate the required arrival within a TMA as a flight can be delayed by waiting at holding points, speed control, and maneuver operation. In a word, the current optimization of a single airport flight schedule without the consideration of the other proximate airports in a multiairport system is suboptimal. To solve this problem, this paper develops a framework for the optimization of the operation of multiairport systems. The contributions of this paper are summarized as follows: we formulate a model to optimize the flight schedules in multiairport systems with the objectives of minimizing the maximum displacement of all flights, the weighted sum of total flight adjustment of each airport, and flight delays. An improved simulated annealing algorithm (SAA) is designed to solve the proposed multiobjective optimization problem. The model is applied to the case of the Beijing-Tianjin-Hebei Airport Group. The results demonstrate that the model generates significant reductions in maximum displacement, average displacement, and average delay, compared to the First-Come-First-Served (FCFS) principle.The paper is structured as follows. In Section2, we describe the problem of flight schedule and formulate an optimized model for flight scheduling in multiairport systems. Then, an improved simulated annealing algorithm is proposed in Section 3 to solve the formulated model. In Section 4, we conduct a case study for the Chinese Beijing-Tianjin-Hebei Airport Group based on real data. Section 5 presents the comparison between the FCFS and SAA and discusses the computational results. Finally, the paper is concluded in Section 6.


## 2. Mathematical Formulation

### 2.1. Notations

Consider a set of flightsF=1,2,…,f in a multiairport system J=1,2,…,e, and i∈f and j∈J. The planning horizon is divided into a set of time intervals V=1,2,…,n, and v∈V. In this paper, the length of a single time interval is set to 15 min. The notations of our mathematical formulation are shown in Table 1.Table 1
Notations
NotationsExplanationUThe set of waypoints,U=1,2,…,m, and u∈U.FjThe set of flights in airportj. Fj=1,2,…,fj.FuThe set of flights which go through the waypointu. Fu=1,2,…,fu.μijThe slot adjustment for flighti in airport j.dijThe delay of flighti in airport j.εjThe weight of airportj when computing the slot adjustment.sThe total number of flights.tijkminThe minimum turn-around times for connecting flightsi,k in airport j.tijkmaxThe maximum turn-around times for connecting flightsi,k in airport j.kThe immediate successor departure flight of arrival flighti.cjvThe capacity of airportj in the time interval v.cuvThe capacity of waypointu in the time interval v.δThe maximum flight adjustment in the MAS.ωThe total flight adjustments in the MAS.∂jThe capacity of airportj.βjThe service rate of arrival and departure of airportj.


### 2.2. Flight Scheduling Model in MAS

The flight scheduling problem in a multiairport system involves different objectives from different perspectives that consider, for example, displacement of flight adjustment and flight delay. In this paper, we seek to balance a number of optimization objectives including the maximum displacement of all flights, weighted sum of total flight adjustment of each airport in the multiairport system, and the average flight delay in the multiairport system. The optimization model of flight scheduling in the MAS is presented as follows:(1)minz=w1maxi∈F,j∈Jμij+w2∑j∈Jεj∑i∈Fjμij+w3s⋅∑i∈F,j∈Jdij,(2)s.t.∑k=13wk=1,(3)∑v∈Vxijuv=1,(4)∑v∈Vyijuv=1,(5)∑u∈Uxijuv=1,(6)∑u∈Uyijuv=1,(7)∑v∈Vtxijuv=∑v∈Vtaijuv+μij,(8)∑v∈Vtyijuv=∑v∈Vtdijuv+μij,(9)xijuvyijuv=1,if flightiis assigned a periodvto land /take off from airportjand go through waypointu,0,otherwise,(10)aijuvbijuv=1,if flightioriginally scheduled to land /take off from airportjand go through waypointuduring periodv,0,otherwise,(11)∑v∈Vvykjuv−∑v∈Vvxkjuv≥Zijktijkmin,(12)∑t∈Ttyjkrt−∑t∈Ttxikrt≥Zijktijkmax,(13)zijk=1,if flightiandkare flown by the same aircraft in airportj,andkis the immediate successor flight ofi,0,otherwise,(14)∂j∑j∈Jyijuv+βj∑j∈Jxijuv≤cjv,∀j∈J,∀v∈V,(15)∑u∈Uxijuv≤cuv,∀u∈U,∀v∈V,(16)∑u∈Uyijuv≤cuv,∀u∈U,∀v∈V,(17)μi≤δ,∀i∈F,(18)∑j∈Jεk∑i∈Fjμij≤ω.The first objective function (i.e., the first part in equation (1)) minimizes the maximum displacement of all flights in the multiairport system. The second objective function (i.e., the first part in equation (2)) minimizes the weighted sum of the total flight adjustment of each airport in a multiairport system. The weighted sum is expressed as the product sum of the total flight adjustment at the airport j and its corresponding weight εj. The third objective function (i.e., the first part in equation (3)) minimizes the average flight delays in the multiairport system.The constraints in equations (2)∼(10) ensure that each flight ∀i∈F is related to a/an departure/arrival period, airport, and waypoint, which make the unique characteristics of variable setting. The scheduled time interval between each pair of connecting flights should meet particular values considering the regulated turn-around time. For ∀i,k∈F, aircraft connectivity constraints (11)–(13) ensure that the ground turn-around time is larger than the minimum turn-around time and smaller than the maximum turn-around time. The following three capacity constraints are related to the slot limits which we want to apply to the airport and route. Constraint (14) reflects the limit of flight schedule capacity curve at the airport j. Constraints (15) and (16) ensure that the number of arrival and departure flights is less than the route and the waypoint capacity in all periods. Moreover, these capacity constraints represent capacity limit of multiairport systems in regional airspace. Constraints (17) ∼ (18) present the restriction of the maximum deviation and total deviation of flights.


## 2.1. Notations

Consider a set of flightsF=1,2,…,f in a multiairport system J=1,2,…,e, and i∈f and j∈J. The planning horizon is divided into a set of time intervals V=1,2,…,n, and v∈V. In this paper, the length of a single time interval is set to 15 min. The notations of our mathematical formulation are shown in Table 1.Table 1
Notations
NotationsExplanationUThe set of waypoints,U=1,2,…,m, and u∈U.FjThe set of flights in airportj. Fj=1,2,…,fj.FuThe set of flights which go through the waypointu. Fu=1,2,…,fu.μijThe slot adjustment for flighti in airport j.dijThe delay of flighti in airport j.εjThe weight of airportj when computing the slot adjustment.sThe total number of flights.tijkminThe minimum turn-around times for connecting flightsi,k in airport j.tijkmaxThe maximum turn-around times for connecting flightsi,k in airport j.kThe immediate successor departure flight of arrival flighti.cjvThe capacity of airportj in the time interval v.cuvThe capacity of waypointu in the time interval v.δThe maximum flight adjustment in the MAS.ωThe total flight adjustments in the MAS.∂jThe capacity of airportj.βjThe service rate of arrival and departure of airportj.


## 2.2. Flight Scheduling Model in MAS

The flight scheduling problem in a multiairport system involves different objectives from different perspectives that consider, for example, displacement of flight adjustment and flight delay. In this paper, we seek to balance a number of optimization objectives including the maximum displacement of all flights, weighted sum of total flight adjustment of each airport in the multiairport system, and the average flight delay in the multiairport system. The optimization model of flight scheduling in the MAS is presented as follows:(1)minz=w1maxi∈F,j∈Jμij+w2∑j∈Jεj∑i∈Fjμij+w3s⋅∑i∈F,j∈Jdij,(2)s.t.∑k=13wk=1,(3)∑v∈Vxijuv=1,(4)∑v∈Vyijuv=1,(5)∑u∈Uxijuv=1,(6)∑u∈Uyijuv=1,(7)∑v∈Vtxijuv=∑v∈Vtaijuv+μij,(8)∑v∈Vtyijuv=∑v∈Vtdijuv+μij,(9)xijuvyijuv=1,if flightiis assigned a periodvto land /take off from airportjand go through waypointu,0,otherwise,(10)aijuvbijuv=1,if flightioriginally scheduled to land /take off from airportjand go through waypointuduring periodv,0,otherwise,(11)∑v∈Vvykjuv−∑v∈Vvxkjuv≥Zijktijkmin,(12)∑t∈Ttyjkrt−∑t∈Ttxikrt≥Zijktijkmax,(13)zijk=1,if flightiandkare flown by the same aircraft in airportj,andkis the immediate successor flight ofi,0,otherwise,(14)∂j∑j∈Jyijuv+βj∑j∈Jxijuv≤cjv,∀j∈J,∀v∈V,(15)∑u∈Uxijuv≤cuv,∀u∈U,∀v∈V,(16)∑u∈Uyijuv≤cuv,∀u∈U,∀v∈V,(17)μi≤δ,∀i∈F,(18)∑j∈Jεk∑i∈Fjμij≤ω.The first objective function (i.e., the first part in equation (1)) minimizes the maximum displacement of all flights in the multiairport system. The second objective function (i.e., the first part in equation (2)) minimizes the weighted sum of the total flight adjustment of each airport in a multiairport system. The weighted sum is expressed as the product sum of the total flight adjustment at the airport j and its corresponding weight εj. The third objective function (i.e., the first part in equation (3)) minimizes the average flight delays in the multiairport system.The constraints in equations (2)∼(10) ensure that each flight ∀i∈F is related to a/an departure/arrival period, airport, and waypoint, which make the unique characteristics of variable setting. The scheduled time interval between each pair of connecting flights should meet particular values considering the regulated turn-around time. For ∀i,k∈F, aircraft connectivity constraints (11)–(13) ensure that the ground turn-around time is larger than the minimum turn-around time and smaller than the maximum turn-around time. The following three capacity constraints are related to the slot limits which we want to apply to the airport and route. Constraint (14) reflects the limit of flight schedule capacity curve at the airport j. Constraints (15) and (16) ensure that the number of arrival and departure flights is less than the route and the waypoint capacity in all periods. Moreover, these capacity constraints represent capacity limit of multiairport systems in regional airspace. Constraints (17) ∼ (18) present the restriction of the maximum deviation and total deviation of flights.


## 3. Algorithm Design

To address the limitations of existing approaches discussed in Section1, an improved simulated annealing algorithm (SAA) framework is developed below for the optimization of the flight operations in multiairport systems. In this section, we proposed an improved SAA to solve the formulated flight schedule optimization model in Section 2. In order to investigate the optimization performance of the SAA, we take the classical First-Come-First-Served (FCFS) as a baseline. In the real practice of Chinese airport operations, the FCFS principle is the most frequently adopted strategy to manage the landings and takeoffs.


### 3.1. Parameter Setting

The SAA is a random optimization algorithm based on the Monte Carlo iterative solution strategy and is an extension of the local search algorithm. Specifically, it is a metaheuristic algorithm to approximate global optimization in a large search space for an optimization problem. The starting point is the similarity between the annealing process of solid substances and general combinatorial optimization problems. By simulating the solid annealing process, starting from a certain initial temperature, as the temperature decreases, the optimal solution is searched in the solution space in combination with the probability jump characteristic tending to a global optimal. It uses the Metropolis-Hastings acceptance criteria and controls the algorithmic process with a set of parameters called a cooling schedule.The parameters of this model are set as follows:(i)
Initial optimization sequenceA is opt_A.(ii)
Optimal objective function value at each temperature: total delay = optimization (1).(iii)
Initial global optimal objective function value total delay = optimization_value.(iv)
Initial optimized scheduling time:X = X_opt.(v)
Initial temperature: temperature (1) = 50 + round (((0.98)^P) ∗ 100). P is the Metropolis acceptance criteria, a certain probability at which the degraded solution is accepted so as to escape local extremes and avoid premature convergence.(vi)
Optimization times at the same temperature: iter = 10 + round ((1 – ((0.95)^P)) ∗ P/4) ∗ 10.(vii)
Initial value of repeat number:l = 1.(viii)
Initialize weightw1, weight w2, and weight w3.(ix)
Execute expression (1).(x)
Start time = now.


### 3.2. SAA Framework

Based on the description above, the SAA implementation framework is presented in Figure1, followed by the corresponding pseudocode in Algorithm 1. The new flight sequence temp_A is obtained by Monte Carlo simulation. A decision is first made on the feasibility of the new solution. If it is infeasible, a new solution will be generated iteratively. The maximum number of iterations is set to 30, after which the next cycle is initiated to prevent going into a dead cycle.Figure 1
SAA iterative procedure.Algorithm 1: Iteration procedure of the SAA.
WHILE temperature (l) > 0.0001FORi = 1 : iterCalculateF(X′) in accordance with expression (1).ΔF = optimization_value−F(X)IF ΔF < 0A = temp_A; (Accept temp_A as the new taking off/landing sequence and enter the next cycle.)X = X‴; (Accept X‴ as a new current solution)Optimization (l) = F(X‴); (Update the optimal value of objective function at lth cycle)Δd = F(X‴)−optimization_value;IF Δd < 0opt_A = temp_A,X_opt = ‴optimization_value =F(X‴),optimization_value (l) = F(X‴),ENDELSEIF exp(−ΔF/temperature (l)) > rand()A = temp_A,X = ‴,optim_F(l) = F(X‴),ENDEND FORendtime1 = now;epstime1 = (endtime1 − starttime)∗ 24 ∗ 3600;IF epstime1 > 160break;ENDl = l + 1,temperature(l) = temperature (l − 1) ∗ 0.99;IF temperature(l)<(temperature(1)∗ 0.618)temperature(l) = temperature(l)∗ 0.6;ENDEND WHILE


### 3.3. Baseline

FCFS is a type of service rules used in the Chinese air traffic management center, and it provides an efficient, simple, and error-free process scheduling algorithm that saves valuable computational resources [13]. Actually, it represents the actual operational data in the multiairport system. Under the rule of FCFS, the flight shall land in accordance with their estimated departure/arrival time. The first flight which abides by its estimated runway time will be given priority for takeoff/landing.


## 3.1. Parameter Setting

The SAA is a random optimization algorithm based on the Monte Carlo iterative solution strategy and is an extension of the local search algorithm. Specifically, it is a metaheuristic algorithm to approximate global optimization in a large search space for an optimization problem. The starting point is the similarity between the annealing process of solid substances and general combinatorial optimization problems. By simulating the solid annealing process, starting from a certain initial temperature, as the temperature decreases, the optimal solution is searched in the solution space in combination with the probability jump characteristic tending to a global optimal. It uses the Metropolis-Hastings acceptance criteria and controls the algorithmic process with a set of parameters called a cooling schedule.The parameters of this model are set as follows:(i)
Initial optimization sequenceA is opt_A.(ii)
Optimal objective function value at each temperature: total delay = optimization (1).(iii)
Initial global optimal objective function value total delay = optimization_value.(iv)
Initial optimized scheduling time:X = X_opt.(v)
Initial temperature: temperature (1) = 50 + round (((0.98)^P) ∗ 100). P is the Metropolis acceptance criteria, a certain probability at which the degraded solution is accepted so as to escape local extremes and avoid premature convergence.(vi)
Optimization times at the same temperature: iter = 10 + round ((1 – ((0.95)^P)) ∗ P/4) ∗ 10.(vii)
Initial value of repeat number:l = 1.(viii)
Initialize weightw1, weight w2, and weight w3.(ix)
Execute expression (1).(x)
Start time = now.


## 3.2. SAA Framework

Based on the description above, the SAA implementation framework is presented in Figure1, followed by the corresponding pseudocode in Algorithm 1. The new flight sequence temp_A is obtained by Monte Carlo simulation. A decision is first made on the feasibility of the new solution. If it is infeasible, a new solution will be generated iteratively. The maximum number of iterations is set to 30, after which the next cycle is initiated to prevent going into a dead cycle.Figure 1
SAA iterative procedure.Algorithm 1: Iteration procedure of the SAA.
WHILE temperature (l) > 0.0001FORi = 1 : iterCalculateF(X′) in accordance with expression (1).ΔF = optimization_value−F(X)IF ΔF < 0A = temp_A; (Accept temp_A as the new taking off/landing sequence and enter the next cycle.)X = X‴; (Accept X‴ as a new current solution)Optimization (l) = F(X‴); (Update the optimal value of objective function at lth cycle)Δd = F(X‴)−optimization_value;IF Δd < 0opt_A = temp_A,X_opt = ‴optimization_value =F(X‴),optimization_value (l) = F(X‴),ENDELSEIF exp(−ΔF/temperature (l)) > rand()A = temp_A,X = ‴,optim_F(l) = F(X‴),ENDEND FORendtime1 = now;epstime1 = (endtime1 − starttime)∗ 24 ∗ 3600;IF epstime1 > 160break;ENDl = l + 1,temperature(l) = temperature (l − 1) ∗ 0.99;IF temperature(l)<(temperature(1)∗ 0.618)temperature(l) = temperature(l)∗ 0.6;ENDEND WHILE


## 3.3. Baseline

FCFS is a type of service rules used in the Chinese air traffic management center, and it provides an efficient, simple, and error-free process scheduling algorithm that saves valuable computational resources [13]. Actually, it represents the actual operational data in the multiairport system. Under the rule of FCFS, the flight shall land in accordance with their estimated departure/arrival time. The first flight which abides by its estimated runway time will be given priority for takeoff/landing.


## 4. Data Source

In this paper, we conduct a case study of flight scheduling in the multiairport system of the Beijing-Tianjin-Hebei Airport Group, which includes three major airports: Beijing Capital International Airport (PEK), Tianjin Binhai International Airport (TSN), and Shijiazhuang Zhengding International Airport (SJW).The airspace resource in the region when used individually by airports does not meet the traffic demand, causing severe congestion. One-day flight plan data in this airport group are selected for analysis in the case study. In the above regional airspace, capacity is limited with a few way points. These waypoints result in severe levels of airspace congestion in this multiairport system. Table2 shows the basic information of the Beijing-Tianjin-Hebei region multiairport group.Table 2
Basic information of the Beijing-Tianjin-Hebei Airport Group.
AirportRunway quantityHour capacityTerminal area (kilo square meters)Number of aircraft movements in 20182018 handing capacityPassenger throughput (kilo person-time)Cargo handling capacity (kilo ton)PEK3881414614022100,9832074TSN23436417941423,591258SJW1205.58971711,33346


## 5. Results and Discussion

This section presents and discusses the computational results from the FCFS and SAA methods. First, we illustrate the result of FCFS, and then the result of the SAA is produced with the same weight settings,w1 = w2 = w3. Finally, we interpret the results for the corresponding results with different weights.


### 5.1. Comparisons between FCFS and SAA with Equal Weights

The computational results of max. displacement, average displacement, and average delay with the FCFS and SAA methods are illustrated in Tables3 and 4.Table 3
Computational results with the FCFS method.
Max. displacement (min)Average displacement (min)Average delay (min)19.4211.0624.06Table 4
Computational results with the SAA method.
Max. displacement (min)Average displacement (min)Average delay (min)17.4010.0620.06From the results of the FCFS and SAA methods with equal weights in Tables3 and 4, the values of the max. displacement, average displacement, and average delay are significantly smaller for the simulated annealing algorithm than the FCFS method.


### 5.2. Results of SAA with Different Weights

When simulated annealing is applied to solve the multiobjective optimization of takeoff and landing problem, the weights of each objective will have a strong influence on the optimization results, which are shown in Table5.Table 5
Computational results with different weight settings.
Instance no.Weight settingMax. displacement (min)Average displacement (min)Average delay (min)1w1 = w2 = w3 = 1/317.4010.0620.062w1 = 1, w2 = w3 = 016.4012.4628.153w2 = 1, w1 = w3 = 019.226.5527.364w3 = 1, w1 = w3 = 021.3019.7810.12We can see from Table5 that, if we only focus on minimizing the maximum displacement of all flights, the weight setting w1 = 1, w2 = w3 = 0 is the best policy, and the minimal max. displacement is 16.4 min. If we only focus on minimizing the weighted sum of total flight adjustment of each airport in the multiairport system, the weight setting w2 = 1, w1 = w3 = 0 is the best policy, and the minimal max. displacement is 6.55 min. If we only focus on minimizing the average flight delays in the multiairport system, the weight setting w3 = 1, w1 = w2 = 0 is the best policy, and the minimal max. displacement is 10.12 min. Obviously, if we focus on the trade-offs among the three parts of objective with weight setting w1 = w2 = w3 = 1/3, the values will be located in the interval from instance nos. 2–4 in Table 5.Due to the characteristics of the heuristic algorithm, the simulated annealing algorithm has a challenging task to get the optimal solution by merely running once, even with appropriate parameter settings. Therefore, it is recommended to conduct multiple experiments and get the results with different weights. The evaluation method proposed in this paper can be employed to select the result which best satisfies the interests of multiple stakeholders in air transportation industry.The limitation of our method is the sensitivity to the weights in making trade-offs among different parts of the objective function, while ignoring the flexible trade-off among different optimization objectives. We will address this limitation in future research.


## 5.1. Comparisons between FCFS and SAA with Equal Weights

The computational results of max. displacement, average displacement, and average delay with the FCFS and SAA methods are illustrated in Tables3 and 4.Table 3
Computational results with the FCFS method.
Max. displacement (min)Average displacement (min)Average delay (min)19.4211.0624.06Table 4
Computational results with the SAA method.
Max. displacement (min)Average displacement (min)Average delay (min)17.4010.0620.06From the results of the FCFS and SAA methods with equal weights in Tables3 and 4, the values of the max. displacement, average displacement, and average delay are significantly smaller for the simulated annealing algorithm than the FCFS method.


## 5.2. Results of SAA with Different Weights

When simulated annealing is applied to solve the multiobjective optimization of takeoff and landing problem, the weights of each objective will have a strong influence on the optimization results, which are shown in Table5.Table 5
Computational results with different weight settings.
Instance no.Weight settingMax. displacement (min)Average displacement (min)Average delay (min)1w1 = w2 = w3 = 1/317.4010.0620.062w1 = 1, w2 = w3 = 016.4012.4628.153w2 = 1, w1 = w3 = 019.226.5527.364w3 = 1, w1 = w3 = 021.3019.7810.12We can see from Table5 that, if we only focus on minimizing the maximum displacement of all flights, the weight setting w1 = 1, w2 = w3 = 0 is the best policy, and the minimal max. displacement is 16.4 min. If we only focus on minimizing the weighted sum of total flight adjustment of each airport in the multiairport system, the weight setting w2 = 1, w1 = w3 = 0 is the best policy, and the minimal max. displacement is 6.55 min. If we only focus on minimizing the average flight delays in the multiairport system, the weight setting w3 = 1, w1 = w2 = 0 is the best policy, and the minimal max. displacement is 10.12 min. Obviously, if we focus on the trade-offs among the three parts of objective with weight setting w1 = w2 = w3 = 1/3, the values will be located in the interval from instance nos. 2–4 in Table 5.Due to the characteristics of the heuristic algorithm, the simulated annealing algorithm has a challenging task to get the optimal solution by merely running once, even with appropriate parameter settings. Therefore, it is recommended to conduct multiple experiments and get the results with different weights. The evaluation method proposed in this paper can be employed to select the result which best satisfies the interests of multiple stakeholders in air transportation industry.The limitation of our method is the sensitivity to the weights in making trade-offs among different parts of the objective function, while ignoring the flexible trade-off among different optimization objectives. We will address this limitation in future research.


## 6. Conclusions

This paper proposes a framework for flight schedule optimization in multiairport systems at the strategic level, while enforcing a set of constraints and an objective function with three different parts. We design an improved SAA to seek for the Pareto-optimal solutions of this computationally challenging problem, which can make trade-offs amongst three parts of the optimization objectives of the model, including the maximum displacement of all flights, weighted sum of total flight adjustment of each airport in the multiairport system, and the average flight delay in the multiairport system.The method is applied to the Beijing-Tianjin-Hebei multiairport system, with the results showing that, compared with the classical FCFS as the baseline strategy, our optimized SAA strategy can improve the operation performance in the MAS. Improvements have been achieved in the efficiency of flight schedule, which leads to the realization of the full functionality of the international airport hub of PEK. In summary, the multiairport system schedule optimization model and algorithm can be applied to optimize flight schedule, which can significantly alleviate the congestion and delay problems in the multiple airport systems.



---

*Source: 4731918-2020-06-02.xml*