Collaboration Optimization of Flight Schedule in Beijing-Tianjin-Hebei Airport Group

，

1.College of Civil Aviation，Nanjing University of Aeronautics and Astronautics，Nanjing 211106，P.R.China；2.Office of Air Traffic Management，Civil Aviation Administration of China，Beijing 100710，P.R.China

（Received 27 May 2020；revised 15 September 2020；accepted 10 October 2020）

Abstract:The coordinated and integrated development of regional airport group system has been identified as an important research topic in the field of air traffic management in China.However，due to the clear limitation on airspace resources and severe traffic congestion，it is necessary to further study the problem of flight schedule coordination optimization for airport clusters.We take the Beijing-Tianjin-Hebei airport Group as an example and construct an optimization model of flight schedule with the minimum adjustment and delay.The design of the implementation algorithm is proposed.As demonstrated by the simulation results，the flight delay in the Beijing-Tianjin-Hebei multi-airport system is noticeably reduced by applying both the optimization model and the algorithm proposed in this paper.

Key words：air transport；flight schedule；airport group system；optimization algorithm

0 Introduction

Airspace congestion and flight delay are known as the problems that impose restriction on the highquality development of multi-airport clusters.In order to resolve these problems，many scholars have started to perform flight schedule optimization and carry out flight demand management from different perspectives， including time and space， strategy and tactics，as well as fairness and effectiveness.In respect of flight schedule optimization，Xu［1］studied the frequency of flight schedule and approaches of aircraft deployment，and constructed a flight time optimization model based on the minimum cost of passenger travel.Wang et al.［2］constructed a mathematical model of flight timing optimization for the multi-airport system，which reduced airport congestion and flight delay by optimizing the departure time of each flight.By introducing the concept of airport group，Liu et al.［3］investigated the problem of air traffic congestion arising from the excessive demand in the hub，based on which the mathematical model was constructed for flight landing airport selection and the corresponding optimization algorithm was developed.By combining the SIMMOD modeling and restricted simultaneous perturbation stochastic approximation（SPSA）optimization algorithm，Zhu et al.［4］optimized the flight time of airport group in the Pearl River Delta（PRD）region in China and determined the optimal scheduling time for each flight departure.Wang et al.［5］constructed a flight time optimization model based on airline fairness and devised a cuckoo search algorithm which was premised on particle swarm optimization algorithm for the optimization of flight scheduling.With regard to the management of demand for flight schedule，Czerny［6］performed time slot resource allocation to manage flight schedule requirements through a combination of congestion charging，time slot auction and other measures.Liu et al.［7］applied game theory to conduct analysis，model airline decision-making，and make adjustment to demand by means of pricing.As demonstrated by simulation experiments，time slot auction was effective in reducing the total delay cost incurred by congested airspace.However，no consideration was given to the complicated and constant-changing characteristics of airport operation.In order to reduce flight delays at airport groups，Wu et al.［8］introduced the theory of transport demand management into flight optimization based on passenger travel demand.Zhu et al.［4］performed simulation and optimization for the multiairportsystem from the perspective ofairport group，which led to a new flight schedule to reduce the total delay time.In practice，there are many studies focusing on the runway scheduling to optimize the runway landings and take-offs［9-11］.By conducting the above-mentioned studies，the flight delay problem caused to the airport group was reduced to a certain extent.Despite this，no consideration was given to the integrated optimization of flight schedule adjustment amplitude，i.e.，the position shifting of slot，or the difference between the initial slot number and the optimized slot number，and flight connection in turnaround processes.Simaiakis et al.［12］optimized flight schedules for the minimum gap between airline demand and manager time allocation，but failed to take into consideration the role played by regional airport groups and congestion at the waypoints.As reaching the airport delay level，Yang et al.［13］reduced the impact of flight schedule adjustment on airlines and airport operations to the minimum，thus reducing flight delays，improving the normal rate of release and mitigating the loss of airlines and airports.To date，most of the algorithms used in flight management in individual airports and multi-airport systems are heuristics and metaheuristics［14-17］.Branch and bound，branch and price，and queuing theory have also been adopted to solve specific problem formulations［18-19］.

Most studies on optimization of flight time and demand management fucused on the capacity constraints of the airport itself.This led to the airspace and route congestion in the terminal area being discounted.Plus，the joint operation of multiple airports in a cluster resulted in frequent conflicts of flight movement and airspace utilization in the terminal area，and thus influented the integrated operation efficiency within the whole cluster.

This paper focuses on the flight scheduling problems for multiple airports in an airport group system，different from most of the existing studies that focus on a single airport.We formulat a novel model to optimize the integrated flight scheduling in Beijing-Tianjin-Hebei airport cluster from the spatial and temporal perspectives.A simulated annealing algorithm premised on flight sequence update and time rolling layer is proposed.By esxemplifying the multi-airport system of Beijing-Tianjin-Hebei airport group，a simulation is performed to validate the feasibility of the model and the algorithm in practice.

1 Flight Schedule Optimization Model for a Multi-airport System

1.1 Notation

The set offlights is indicated asF={1，2，…，f}，i∈F.The set of airports is denoted asJ={1，2，…，e}，j∈J.The set of waypoints is expressed asU={1，2，…，m}，u∈U.The set of time intervals is indicated asV={1，2，…，n}，v∈V.Valso represents operation time in an airport，which can be split into multiple periods of a continuous time.In this paper，the optimization time interval is set to 15 min.The set of flights in airportjis denoted asFj={1，2，…，fj}.The set of flightsthatgoesthrough waypointuisFu={1，2，…，fu}.

1.2 Flight schedule optimization model

In order to formulate the flight scheduling problem in multi-airport system，we make some assumption based on the characteristics of the actual conditions in the Beijing-Tianjin-Hebei airport group.The assumptions are listed as follows.

（1）The capacities of the airports and airspace are already obtained from the airspace capacity evaluated system（ACES）platform in Civil Aviation Administration of China（CAAC），and only the key input parameters are used in the flight scheduling problem.

（2）There are no obvious unconventional disturbances in the internal and external environments of flight operations in the investigated multi-airport system.Once the flight schedule is formulated，it will not be changed under normal operations.

1.2.1 Objective function

For the optimal objective function of airport group flight schedule，the maximum adjustment of flight schedule，the total amount of flight time adjustment，the average flight delay，and the minimum weighted sum of flight delays are involved and described as

whereμiindicates the adjustment amount of flighti；μijthe slot adjustment for flightiin airportj；εjthe weight of airportj；di，jthe distance of flightito waypointj；the estimated time of departure of flightf；denote the schedule time from airportsA/B/Cto way pointj，respectively；andw1，w2，w3，w4the weights with values greater than or equal to 0，less than or equal to 1，and they satisfy

1.2.2 Constraints

（1）?i∈Fsatisfies the uniqueness limit.It is ensured that a flight involves a single schedule.

（2）?i，k∈Fare required to meet the aircraft connectivity constraints.Continuous flights need to satisfy the requirements of the minimum and maximum transit time for the corresponding airport，while the flights with passenger continuity（joint trip）need to satisfy the requirements of transit time.

whereanddenote the minimum and the maximum turn-around times for connecting flightsiin airportj，respectively；andequal to 1 if the assigned slot number istfor flightkandibetween airportjand waypointr，respectively，otherwise 0.

（3）There is a necessity for the conditions of capacity limit to be met，including the capacity limit of each airport at a unit time window，the capacity limit of the waypoint （corridor port）， and the uniqueness of the corridor entrance.

wherecuvindicates the capacities of airportjand waypointuin the time intervalv.

（4） The departure capacity constraintCdshould be holdHd，that is to say，the adjusted flight ΔCzcannot exceed the departure capacity of the associated airport

The arrival capacity constraintCashould be holdHa，that is to say，the adjusted flightΔCzcannot exceed the arrival capacity of the associated airport

The constraint of departure time of flightsis described as

wheredenotes the latest departure time of flightsat airportφ.

The number of time slots should be controlled below the route capacity in the sector.All the flights can be allocated to the corresponding time slots.

whereβftjequals to 1 if the assigned slot number istfor flightfat waypointj，otherwise 0；Rx(t)the capacity of enroute in slott；andmfthe number of slot for flight operations.

2 The Simulated Annealing Algorithm

In this paper，the simulated annealing algorithm is developed for the collaboration optimization of flight schedule in Beijing-Tianjin-Hebei airport cluster.The simulated annealing algorithm is a random optimization algorithm based on the Monte Carlo iterative solution strategy and an extension of the local search algorithm［20-22］.For the temperature in an annealing system，uphill moves are more likely to occur at a higher temperature.As the temperature approaches 0，the trend becomes more and more unlikely，until the simulated annealing algorithm behaves more or less like the hill-climbing.In a typical simulated annealing optimization，the temperature starts high and is gradually decreased according to an“annealing schedule”.

Specifically，it is a metaheuristic algorithm to approximate global optimization in a large search space for an optimization problem.The implementation procedure of our algorithm is as follows.

Algorithm

Initialization： temperaturel=300+round（0.98P×100）//Pis the Metropolis acceptance criteria，a certain probability at which the degraded solution is accepted so as to escape local extremes and avoid premature convergence［23］.

Optimization times at the identical temperature：iter=10+round（（1-0.95P）×P/4）×10

Initial value of repeat number：h=1

While temperaturel＞0.000 1

Fori=1：iter

Determine the new flight sequenceAtempby Monte Carlo simulation

Change the value ofδijto obtain a new flight sequenceAtemp

CalculateXby the rule of first-come-firstserved（FCFS）

CalculateX′under the sequenceAtemp

A flight scheduling decision will be firstly made on the feasibility of the new solution in the simulated annealing algorithm.If the new solution is infeasible，other new solutions will be generated iteratively.The maximum number of iterations is set to 30，based on which the next cycle is initiated to remove the possibility of a dead cycle.dis called a“cost function”，and corresponds to the free energy in the case of annealing a metal；Δdis the change of distance implied by the trade（negative for a“good”trade；positive for a“bad”trade）.

Calculation increment ΔF=Foptimal，L-F(X)//Findicates a multi-objective evaluation function.

Else if exp（-ΔF/l）＞rand（）.Otherwise，X′′′is accepted as the new current solution according to the Metropolis acceptance criterion［24-26］

3 Case Study and Discussions

Across the Beijing-Tianjin-Hebei multi-airport system，Beijing Capital International Airport（PEK），Tianjin Binhai International Airport（TSN），and Shijiazhuang Zhengding International Airport（SJW）represent the major ones.The conflict between the available airspace capacity and the largescale demands makes severe air congestion inevitable.In this paper，one-day flight plan data from 1 June 2018 with 1 032 flights at the Beijing-Tianjin-Hebei airport group is taken to perform case study.In this section，the improved optimization algorithm and its application in the case study of the Beijing-Tianjin-Hebei multi-airport system are introduced and discussed.First，the results of the FCFS algorithm are described，and compared with the results of the simulated annealing algorithm with equal weights subsequently （i.e.w1=w2=w3）.Second，the outcomes obtained from different weights are elaborated.

3.1 FCFS algorithm and the simulated annealing algorithm with same weights

As demonstrated by the comparison performed between the results of FCFS and the simulated annealing method with equal weights，the maximum displacement，average delay and maximum delay values of the simulated annealing algorithm are less significant（Tables 1，2）.

Table 1 Performance of FCFS algorithm

Table 2 Performance of simulated annealing algorithm

3.2 Results of the simulated annealing algorithm with different weights

Based on the experimental results and the comparison between them（Table 3），it can be known that，when the simulated annealing is applied to resolve the problem with multi-objective optimization flight scheduling，the weight of each target shows a significant influence on the optimization results.This is due to the fact that the simulated annealing algorithm exhibits the instability of the heuristic algorithm.Under this circumstance，even though the reasonable parameter setting is performed，the possibility remains low to obtain the optimal solution by applying the simulated annealing algorithm only once.Therefore，it is more advisable to calculate the results of different weights in parallel using multiple computers，and to select the results that are in the best interest of all parties using the expert evaluation method as described in this paper.

Table 3 Optimization results under different weight combinations

The airport flight time optimization method can help to meet the key bottleneck of space resources limits.

As can be seen from Fig.1，the scene capacity of PEK is 1 720 sorties for flights running northward，and the service sorties during peak hours are 95 sorties.According to the delay distribution in PEK，the departure delay is generally larger than the arrival delay，and there is a departure delay peak in morning rush hours，mainly because a large number of flights need to wait at the end of the runway in morning rush hours.

Fig.1 Delay distribution of PEK after optimization

As can be seen from Fig.2，the scene capacity of TSN is 636 sorties in northbound operation，and 43 sorties in peak hour service.According to the distribution of delays in TSN，during the isolated operation of dual runways in the daytime，the overall arrival and departure delays are small；however，when a single runway is used after 8：30 in the evening，there are obvious interactions between the arrival and departure flights，and the departure flight delays are large.

Fig.2 Delay distribution of TSN after optimization

After optimization，a total of 346 flights（287 flights of PEK and 59 flights of TSN）were adjusted，with an overall average adjustment deviation of 16.9 min and a maximum adjustment deviation of 60 min.Nine flights were adjusted and pushed to the next day.The structure of ideal flight time on typical days after optimization is shown in Figs.3，4.

Fig.3 Optimal flight time structure of PEK after optimization

Fig.4 Optimal flight time structure of TSN after optimization

Aiming at the system bottleneck，we took the airspace of Beijing terminal area as the object to verify the flight time optimization effect of multiple airports in 2019.In general，the operation efficiency of PEK and TSN in the terminal area of Beijing was significantly improved，with the overall average de-lay reduced by 4 min and the peak total delay reduced by 13 min.

4 Conclusions

Due to the limit on airspace resources，the configuration and operation of the airport flight schedule in the multi-airport system have impact on each other.Therefore，the optimization of single airport flight schedule is less than optimal without considering other airports.In order to address this problem，the operation optimization model for the airport group system is constructed in this paper.An improvement is made to the optimization model and the optimization algorithm is proposed，so as to enhance the efficiency of flight schedule and reduce its adjustment.The optimization algorithm is applied to the Beijing-Tianjin-Hebei airport group.The allocation of flight schedule is optimized and the number of flights in each period is well controlled after adjustment.The flight time optimization model and the algorithm of the multi-airport system are effective in achieving optimization of the flight schedule and in reducing problems of congestion and delay.