# Flight Time and Frequency-Optimization Model for Multiairport System Operation

Authors: Danwen Bao; Songyi Hua
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

This study’s goal is to reduce the number of flights and alleviate congestion in hub airports. It proposes a flight time and frequency-optimization method for multiairport systems. A flight time and frequency-optimization model for multiairport system operation is created to minimize loss of passenger trip time. Ak-means clustering algorithm is designed to solve the model and calculate indexes such as flight time and frequency, passenger trip-time loss, and distribution of airplane models and quantity. The calculation results of an example in China are as follows. Under multiairport system operation mode, passenger demands are divided into 7 categories; 11 flights satisfy all passenger demands; passenger trip-time loss is 129,573 min; and the average passenger load factor is 90.1%. Under an independent operation mode, passenger demands are divided into 8 categories; 13 flights satisfy all passenger demands; passenger trip-time loss is 173,705 min; and the average passenger load factor is 87.4%. The multiairport system operation mode not only improves passenger trip efficiency but also benefits airlines by improving the passenger load factor and reducing flights. Moreover, comparative analysis of a genetic algorithm versus a clustering algorithm further proves the accuracy of the clustering algorithm.


---

## Body

## 1. Introduction

The State Council of China’s 2011 12th Five-Year Development Plan for China Civil Aviation explicitly specified the development goal of constructing “five major multiairport systems” [1] by coordinating regulations and consolidating route allocation, airspace resources, and scheduling to promote the coordinated development of multiple airports in urban agglomerations. In the metropolitan circle of the Yangtze River Delta, there are 18 airports (Shanghai Pudong, Shanghai Hongqiao, Nanjing Lukou, Hangzhou Xiaoshan, Wuxi Sunan, etc.). Regional airport density is 0.87/104 km2, which is well above the 0.17 average in China’s other metropolitan circles and exceeds the 0.6 average in the United States. Indeed, the Yangtze River Delta region has one of the world’s highest multiairport system densities [2]. Data show the existence of homogenous routes for the airports in a multiairport system. However, passenger volumes are significantly different. For instance, during peak hours, flights from Shanghai Hongqiao to Beijing Capital arrive at 5 min intervals, whereas flights from airports such as Wuxi arrive at 40 min intervals. Varying flight times for each airport in a multiairport system results in enormous flight arrival and departure pressure at Beijing Capital, exacerbates flight delays at hubs, and reduces the overall transport efficiency of multiairport systems. One notable feature of the multiairport system is that airports are connected via advanced ground transportation systems, facilitating passenger demand for transfers between airports [3]. Therefore, to alleviate congestion at hub airports and improve the overall operation efficiency of multiairport systems, it is of great importance to systematically design flight times and frequencies for multiairport system operation modes.Numerous researchers worldwide have investigated the correlation between flight schedules and flight delays. Yang et al. (2013) suggest that flight volume growth and fluctuations are major causes of domestic flight delays [4]. Liu et al. (2014) have investigated the effect of flight volume on delays, proposing that growth in flight volume results in an increased number of airports being delayed and increased total delay time until the disappearance of an effect on subsequent flight delays [5]. Abeyratne (2000) has investigated the relation between airport flights and flight delays, proposing a method to control the primary market and secondary market for time slots through both market and administrative means [6]. Pels and Verhoef (2004) have investigated pricing for congestion costs, proposing that because the congestion price was equal to the marginal value of the trip delay, that value should be the basis for the charge; in addition, they have suggested that the suboptimal charge was normally lower than the congestion cost [7]. These studies are primarily based on demand management and leverage various pricing and charge methods to alleviate flight delays. Although their findings have been widely adopted by airports worldwide, it is difficult to apply these methods to China’s air transport system [8]. Therefore, numerous researchers have studied how to manage congestion in hub airports using methods that are not based on charging. Brueckner (2009) has compared the difference between managing airport congestion via extra charges and managing airport congestion via flight control. Research shows that flight control—such as assigning each airline a fixed number of time slots either without charge or via auction—results in fixed flights for airlines. Thus, congestion is completely determined by the optimal control of time slots by the airport authority [9]. Vaze and Barnhart (2012) have studied alleviating airport congestion by enabling competition among airlines for flight frequency, proposing a Nash game model under time slot constraints and obtaining an equilibrium solution via a sequential optimization decision method based on dynamic planning. Their result shows that reducing a very small number of time slots—that is, reducing a very small number of flights—reduces passenger delays and creates higher profits for airlines [10]. Flores-Fillol (2010) have investigated the relation between flight frequency and airplane model at a hub airport, creating a model composed of flight frequency, airplane models, and pricing for congestion costs and suggesting that one major cause of hub airport congestion was that too many flights were based on an undersized model [11]. Although these studies suggest that limiting flights, employing a large airplane model, and reducing airline time slots could effectively alleviate airport congestion, most of them focus on flight arrangements at a single airport and do not consider coordination among multiple airports. Studies on multiairport system flight congestion primarily focus on regulating air transport traffic. Shi (2012) have created a flight-adjustment efficiency matrix to optimize coordinated decisions for flight departure plans; under specific conditions, a coordinated flight schedule plan for a multiairport system was obtained via this method [12]. To effectively alleviate growing airspace congestion in multiairport systems, Ma et al. (2015) have systematically investigated the coordinated arrangement of flights in multiairport terminal areas, combining that approach with multiobjective optimization and a basic genetic algorithm theory to find a Pareto-optimal solution for the coordinated arrangement of flights in a multiairport terminal area [13]. The primary focus of the aforementioned studies is that flight operations should satisfy flight safety requirements, potentially resulting in delays caused by flights’ avoidance of one another. Such research tends to emphasize microscopic delays, ignoring that the essence of flight times is the efficient satisfaction of passenger trip-time requirements.There are also researches focusing on methods from the perspective of airport demand management to ease the flight delay. The International Civil Aviation Transport Association (IATA) established three types of airport flight coordination mechanism which are widely used in the global transport system due to a high degree of stability and consistency. But this mechanism is only applicable to the situation when part of the time can not meet the needs of the airport, or a small number of flights can not meet the needs. Congestion charges are commonly means used in demand management. Pels and Verhoef (2004) researched on the case of congestion pricing and proposed equaling the congestion price to the marginal value of passenger’s delay as a basis for the charges, in order to achieve flight routes adjustment in the period of congestion [7, 14]. Vaze et al. (2012) focused on the allocation of airport time slot resources. They put forward the strategy to control the primary and secondary market of time slot by administrative and market means, optimizing the allocation time slot resources by auction to reduce the impact of airlines on monopolies [10, 15, 16]. In recent years, more and more airports have applied demand management tools to alleviate the airport congestion, but most of them are administrative means or economic means. There is little research applying demand management tools to technology from the perspective of flight frequency and time.This paper is the first to apply transport-demand management theory to flight optimization for multiairport systems from the perspective of passenger trip requirements with the goal of reducing flight delays. The fundamental method of reducing flight delays involves optimizing flight times and frequencies, reducing flight demand from multiairport systems to hub airports, and decreasing the opportunity to deplete hub airport time slots. Because the Yangtze River Delta is one of China’s most economically developed areas, there are more tourism airline passengers than business airline passengers. Moreover, there is passenger demand to depart from different cities. This paper is based on the assumption that passenger demand can be transferred among the airports in the Yangtze River Delta multiairport system. Based on the precondition of the satisfaction of passenger demand, the configuration of airports’ flight volume, schedule, and airplane models in the multiairport system is optimized to reduce congestion at the hub airport. Multiairport systems are extremely different from single airports in terms of flight time optimization. There is only a one-dimensional difference between single-airport passenger demand and flights. It is more difficult to obtain a solution to the problem of passenger demand and flights in a multiairport system because the difference between multiairport passenger demand and flights involves two-dimensional differences in time and space. Based on actual flight operations, this study abandons the mathematical requirement of strict convergence for the clustering algorithm, and the algorithm convergence condition is based on the requirement of minimizing the time slot interval. A flight time and frequency-optimization model for multiairport system operation mode is created, and the result is compared with that of the model for single-airport independent operation mode.


## 2. Model Creation

### 2.1. Basic Assumption

In a single airport, when price is not considered, the criterion used by passengers to select among multiple flights is minimization of the gap between the expected departure time and the scheduled departure time. Although an increased flight frequency reduces this gap, it also results in airport congestion and consequent flight delays. In multiairport system operation mode, passengers can choose to depart from various cities, and airlines assemble demands scattered among various airports by guiding passenger demand. Because concentrated passenger demand increases the passenger load factor, airlines use large passenger airplanes to meet passenger demand. The passengers will consider ground transport time and flight delay time when departing from a different city. Therefore, passenger’s travel time can be divided into two parts: passenger departure time loss and passenger arrival-time loss. Passenger departure time loss is defined as the difference value between passenger expected departure time and scheduled flight departure time. In addition, the ground transport time needs to be considered when passengers depart from a different city. Passenger arrival-time loss is defined as the difference value between scheduled flight departure time and actual flight departure time, namely, flight delay time.The passenger’s choice to depart from either a local city or another city presents significantly different departure time losses depending on which origination point is chosen. For each airport in the multiairport system, the flight delay to the destination airport is essentially the same because that delay is primarily caused by flow control at the destination airport. There is no significant difference in the effect of flow control on flights to the same destination; therefore, passenger arrival-time loss is identical.To simplify the model, the following assumptions are proposed: (1) There is no difference in prices for flights in the multiairport system. (2) Each airport has identical departure and arrival conditions and only a single runway in the multiairport system. (3) Passengers choose the flight with the minimum departure time loss [17]. As an example in Figure 1, assuming that expected departure time of a passenger at airport B is 10:00, the scheduled departure time of the flights at airports A, B, and C is, respectively, 9:00, 12:30, and 11:30. The ground transport times from airport B to airport A and airport C are both 60 minutes. Referring to formula (7), if the passenger chooses to depart from airport A, the departure time loss is the sum of difference between passenger expected departure time and scheduled flight departure time and ground transport time. The value is 120 min. If the passenger chooses to depart from airport B, the departure time loss is only the difference between passenger expected departure time and scheduled flight departure time. The value is 150 min. If the passenger chooses to depart from airport C, the departure time loss is only 90 min because the ground transport time is less than the difference between passenger expected departure time and scheduled flight departure time. After comparing the three conditions, the passenger will eventually choose to depart from airport C. (4) If there are multiple airports with the same departure time loss, passengers choose the flight whose scheduled departure time is ahead. Assuming that the ground transport time from airport B to airport C is 120 minutes, then the departure time loss of departing from airport A or C is 120 minutes. The passengers will choose to depart from airport A because the scheduled flight departure time in airport A is ahead of airport C. (5) All passengers demands are assured. And (6) each flight has a minimal passenger load factor.Figure 1
The distance between the demand point and the category center.


### 2.2. Problem Description

Passenger demand at each airport is discrete, which is normal when confined to a limited time range. Therefore, it is abstracted as a demand point. When planning a flight, the goal is to minimize the gap between the actual and expected passenger departure times at each demand point. Based on the reverse thinking method, passenger demand points are categorized. Next, a flight is planned at the center of each category. In this way, flight planning accurately reflects passenger demand, and clustering makes the solution both more efficient and more easily implemented. Based on both the above assumption and the clustering method requirement, the following mathematical model is created:(1)minZ=∑i∑j∑puijpxijp+∑iDif∑i∑j∑pxijp(2)∑pxijp≤1(3)δcp≤dijp≤cp;when xijp=1, there are(4)∑i∑j∑pdijp=∑iDi(5)dijp=∑m∑nSimjn(6)uijp=∑m∑nSimjntimjn.In this expression,Z is the value of the objective function, the sum of passenger departure time loss and arrival-time loss. xijp is the 0-1 decision variable; when airplane model p is scheduled at moment j in airport i, xijp is 1; otherwise, it is 0. uijp is the passenger departure time loss on flight xijp; f∑i∑j∑pxijp is the passenger arrival-time loss function, which is related to total flight volume ∑i∑j∑pxijp. More total arriving flights mean a longer delay for each flight. It is difficult to describe the passenger arrival-time loss function accurately via a functional expression. Based on statistics from the historical data, this function is approximated via a piecewise function (Table 3); dijp is the passengers on flight xijp; Simjn is passenger demand transferred from moment n at airport m to moment j at airport I; timjn is passenger departure time loss transferred from moment n at airport m to moment j at airport i; cp is seat in a particular airplane model p; δ is the minimal passenger load factor; and Di is passenger demand at airport i.Formula (1) guarantees the minimum passenger total time loss; formula (2) guarantees that there is a maximum of one flight at any moment at any airport; formula (3) guarantees that the number of passengers on a flight exceeds the minimal passenger load factor and does not exceed the number of seats on the flight; formula (4) guarantees that all passenger demands are met; and formula (5) guarantees that passenger demand for flight xijp is composed of passenger demands from different airports at different moments.


## 2.1. Basic Assumption

In a single airport, when price is not considered, the criterion used by passengers to select among multiple flights is minimization of the gap between the expected departure time and the scheduled departure time. Although an increased flight frequency reduces this gap, it also results in airport congestion and consequent flight delays. In multiairport system operation mode, passengers can choose to depart from various cities, and airlines assemble demands scattered among various airports by guiding passenger demand. Because concentrated passenger demand increases the passenger load factor, airlines use large passenger airplanes to meet passenger demand. The passengers will consider ground transport time and flight delay time when departing from a different city. Therefore, passenger’s travel time can be divided into two parts: passenger departure time loss and passenger arrival-time loss. Passenger departure time loss is defined as the difference value between passenger expected departure time and scheduled flight departure time. In addition, the ground transport time needs to be considered when passengers depart from a different city. Passenger arrival-time loss is defined as the difference value between scheduled flight departure time and actual flight departure time, namely, flight delay time.The passenger’s choice to depart from either a local city or another city presents significantly different departure time losses depending on which origination point is chosen. For each airport in the multiairport system, the flight delay to the destination airport is essentially the same because that delay is primarily caused by flow control at the destination airport. There is no significant difference in the effect of flow control on flights to the same destination; therefore, passenger arrival-time loss is identical.To simplify the model, the following assumptions are proposed: (1) There is no difference in prices for flights in the multiairport system. (2) Each airport has identical departure and arrival conditions and only a single runway in the multiairport system. (3) Passengers choose the flight with the minimum departure time loss [17]. As an example in Figure 1, assuming that expected departure time of a passenger at airport B is 10:00, the scheduled departure time of the flights at airports A, B, and C is, respectively, 9:00, 12:30, and 11:30. The ground transport times from airport B to airport A and airport C are both 60 minutes. Referring to formula (7), if the passenger chooses to depart from airport A, the departure time loss is the sum of difference between passenger expected departure time and scheduled flight departure time and ground transport time. The value is 120 min. If the passenger chooses to depart from airport B, the departure time loss is only the difference between passenger expected departure time and scheduled flight departure time. The value is 150 min. If the passenger chooses to depart from airport C, the departure time loss is only 90 min because the ground transport time is less than the difference between passenger expected departure time and scheduled flight departure time. After comparing the three conditions, the passenger will eventually choose to depart from airport C. (4) If there are multiple airports with the same departure time loss, passengers choose the flight whose scheduled departure time is ahead. Assuming that the ground transport time from airport B to airport C is 120 minutes, then the departure time loss of departing from airport A or C is 120 minutes. The passengers will choose to depart from airport A because the scheduled flight departure time in airport A is ahead of airport C. (5) All passengers demands are assured. And (6) each flight has a minimal passenger load factor.Figure 1
The distance between the demand point and the category center.


## 2.2. Problem Description

Passenger demand at each airport is discrete, which is normal when confined to a limited time range. Therefore, it is abstracted as a demand point. When planning a flight, the goal is to minimize the gap between the actual and expected passenger departure times at each demand point. Based on the reverse thinking method, passenger demand points are categorized. Next, a flight is planned at the center of each category. In this way, flight planning accurately reflects passenger demand, and clustering makes the solution both more efficient and more easily implemented. Based on both the above assumption and the clustering method requirement, the following mathematical model is created:(1)minZ=∑i∑j∑puijpxijp+∑iDif∑i∑j∑pxijp(2)∑pxijp≤1(3)δcp≤dijp≤cp;when xijp=1, there are(4)∑i∑j∑pdijp=∑iDi(5)dijp=∑m∑nSimjn(6)uijp=∑m∑nSimjntimjn.In this expression,Z is the value of the objective function, the sum of passenger departure time loss and arrival-time loss. xijp is the 0-1 decision variable; when airplane model p is scheduled at moment j in airport i, xijp is 1; otherwise, it is 0. uijp is the passenger departure time loss on flight xijp; f∑i∑j∑pxijp is the passenger arrival-time loss function, which is related to total flight volume ∑i∑j∑pxijp. More total arriving flights mean a longer delay for each flight. It is difficult to describe the passenger arrival-time loss function accurately via a functional expression. Based on statistics from the historical data, this function is approximated via a piecewise function (Table 3); dijp is the passengers on flight xijp; Simjn is passenger demand transferred from moment n at airport m to moment j at airport I; timjn is passenger departure time loss transferred from moment n at airport m to moment j at airport i; cp is seat in a particular airplane model p; δ is the minimal passenger load factor; and Di is passenger demand at airport i.Formula (1) guarantees the minimum passenger total time loss; formula (2) guarantees that there is a maximum of one flight at any moment at any airport; formula (3) guarantees that the number of passengers on a flight exceeds the minimal passenger load factor and does not exceed the number of seats on the flight; formula (4) guarantees that all passenger demands are met; and formula (5) guarantees that passenger demand for flight xijp is composed of passenger demands from different airports at different moments.


## 3. Model Algorithm

k-means clustering algorithm was put forward by B. MacQueen in the 1960s, a classic algorithm widely used in data analysis and processing which is especially suitable for large sample data processing. The basic idea of the algorithm is like that: the basic idea of the algorithm is to assume that there are n data objects. Then k sample points as the initial category center are selected and the various sample points are classified into the nearest clustering center. It is recalculated to get a new category center based on the average value of each cluster; if the category center of the adjacent two calculations is the same, it indicates that the clustering criterion function is convergent and the classification of sample points can be ended at this time.Known from the analysis of the above, (1) the procedure ofk-means clustering algorithm and the problem solving in this paper are relatively consistent. Seen from problem description, demands of the passengers can be abstracted into multiple discrete demand points. Taking the minimum passenger departure time loss as the goal, the demand points are categorized and the flights are set at central points. Thus it can be seen that the passenger demand points are equivalent to the sample points of clustering algorithms, the clustering criterion is to minimum passenger departure time loss, and central points are equivalent to the category centers. Therefore, the optimization of flight schedules can be realized as continuous by clustering algorithm iteratively updating. (2) There are so many demand points in this problem, and the passenger departure time loss of each demand point should be recalculated after each adjustment. If adopting the traditional algorithm, the calculation quantity will be too large.k-means clustering algorithm will classify the demand points continuously, which not only can realize the goal of reducing passenger departure time loss when the flights are set at category centers, but also can greatly improve calculation speed. (3) The minimum and maximum number of flights can be determined according to airplane model in this problem; namely, the value of k which represents the number of initial categories has an explicit limit. It can avoid the defect that the value of k ink-means clustering algorithm is difficult to be determined in advance. So based on the above reasons,k-means clustering algorithm is applied to solve flight time optimization model in multiairport system innovatively in this paper. The accuracy and feasibility of the algorithm will be verified by comparing to the results of traditional genetic algorithm in a case study.


### 3.1.k-Means Clustering Algorithm-Based Optimization Method

The 3 key elements of the clustering algorithm are as follows: the sample point, the distance calculation formula, and the category center [18].Sample point: this is also known as the demand point. For any airport in a multiairport system, demand at a particular moment is denoted as variables; the 3 elements of s are SX, Sy, and Sz. SX is the airport for the sample point; Sy is the moment for the sample point; and Sz is passenger demand contained in the sample point.Category center: this is denoted as variablec; the elements of c are cx, cy, and cz. cx is the airport for the category center, denoted as the airport identifier; cy is the moment for the category center; and cz is passenger demand for the category center.The distance between the demand point and the category center is shown in Figure1. The distance calculation formula is as follows: (7)dsc=sy-cy,sx=cxsy-cy+tsx,cx,sx≠cx,sy≥cymax⁡sy-cy,tsx,cx,sx≠cx,sy≺cy,where dx is the distance between the demand point and the category center, which is actually the time difference between the demand point and the category center, and t(sx,cx) is the ground transportation time between 2 airports.The distance between demand points and each category center reflects the gap between passenger expected trip time and flight departure time. The category for any demand point is determined by the distance between demand point s and the category center.The distance between demand points and the center of category 1 is 150 min; the distance between demand point s and the center of category 2 is 120 min (i.e., a passenger at demand point s should depart at 8:00 from airport B to catch a 9:00 flight at airport A after 60 min of ground transportation). The distance between demand point s and the center of category 3 is 90 min (i.e., demand point s passenger should depart at 10:30 from airport B to catch an 11:30 flight at airport C after 60 min of ground transportation). If the ground distance between airport B and airport C is 120 min, then the distance from demand point s to the center of category 3 is 120 min. Then, the distance between demand point s and the center of category 2 is equal to that of category 3. Point s should belong to category 2 because flight time of category 2 is ahead.The center of categoryk is represented as(8)ckx=∑ssxszckzcky=∑sdscszckzckz=∑ssz,where ckx is the airport identifier for the center of category k; cky is the moment for the center of category k; and ckz is passenger demand for the center of category k. If a nonintegral result is obtained from this calculation, it should be converted to an integer during the clustering process by approximating to the closest integer.


### 3.2.k-Means Clustering Algorithm Procedure

Step 1.
The minimum number of flights that satisfy all demands is calculated (demands in all airports divided by seats in the largest model) as the initial clustering lower boundk0; the maximum number of flights (demands in all airport divided by the number of seats in the smallest model) is calculated as clustering category upper bound k1. The sum of initial passenger departure time loss and arrival-time loss is defined as g; the initial value of g is sufficiently large. There are k initial categories, k=k0.Step 2.
The centers ofk categories are determined randomly.Step 3.
All of the adjacent demand points are included in a category. Based on all of the sample points in each category, the center of this category is recalculated. Each step is repeated until either of the airports from consecutive calculations for all category centers is identical and the time gap is less than 3 min (the smallest interval of flight take-off time slots is 3 min) or the clustering reaches its limit (in this paper, 100). If category demand is too low (i.e., if category demand is below the minimal passenger load factor requirement for the smallest model), the demand points in this category are included in the adjacent category.Step 4.
For each demand category, based on corresponding passenger demand, the optimal airplane model is allocated. If passenger demand for that category exceeds the number of seats in the largest model, multiple flights are arranged. Each flight should choose a model to ensure total seating that meets demand without waste. If each category only requires 1 flight, the flight is arranged at the category center. If each category requiresn flights, then the flights are arranged at the category center and the n-1 moment adjacent to the category center.Step 5.
Calculateg′, the sum of actual passenger departure time loss and arrival-time loss. If g′≤g, save the category center and the flight schedule plan. If k<k1, then let k=k+1 and go to Step 2; otherwise, exit.The procedure for thek-means clustering algorithm is shown in Figure 2.Figure 2
The algorithm procedure.


## 3.1.k-Means Clustering Algorithm-Based Optimization Method

The 3 key elements of the clustering algorithm are as follows: the sample point, the distance calculation formula, and the category center [18].Sample point: this is also known as the demand point. For any airport in a multiairport system, demand at a particular moment is denoted as variables; the 3 elements of s are SX, Sy, and Sz. SX is the airport for the sample point; Sy is the moment for the sample point; and Sz is passenger demand contained in the sample point.Category center: this is denoted as variablec; the elements of c are cx, cy, and cz. cx is the airport for the category center, denoted as the airport identifier; cy is the moment for the category center; and cz is passenger demand for the category center.The distance between the demand point and the category center is shown in Figure1. The distance calculation formula is as follows: (7)dsc=sy-cy,sx=cxsy-cy+tsx,cx,sx≠cx,sy≥cymax⁡sy-cy,tsx,cx,sx≠cx,sy≺cy,where dx is the distance between the demand point and the category center, which is actually the time difference between the demand point and the category center, and t(sx,cx) is the ground transportation time between 2 airports.The distance between demand points and each category center reflects the gap between passenger expected trip time and flight departure time. The category for any demand point is determined by the distance between demand point s and the category center.The distance between demand points and the center of category 1 is 150 min; the distance between demand point s and the center of category 2 is 120 min (i.e., a passenger at demand point s should depart at 8:00 from airport B to catch a 9:00 flight at airport A after 60 min of ground transportation). The distance between demand point s and the center of category 3 is 90 min (i.e., demand point s passenger should depart at 10:30 from airport B to catch an 11:30 flight at airport C after 60 min of ground transportation). If the ground distance between airport B and airport C is 120 min, then the distance from demand point s to the center of category 3 is 120 min. Then, the distance between demand point s and the center of category 2 is equal to that of category 3. Point s should belong to category 2 because flight time of category 2 is ahead.The center of categoryk is represented as(8)ckx=∑ssxszckzcky=∑sdscszckzckz=∑ssz,where ckx is the airport identifier for the center of category k; cky is the moment for the center of category k; and ckz is passenger demand for the center of category k. If a nonintegral result is obtained from this calculation, it should be converted to an integer during the clustering process by approximating to the closest integer.


## 3.2.k-Means Clustering Algorithm Procedure

Step 1.
The minimum number of flights that satisfy all demands is calculated (demands in all airports divided by seats in the largest model) as the initial clustering lower boundk0; the maximum number of flights (demands in all airport divided by the number of seats in the smallest model) is calculated as clustering category upper bound k1. The sum of initial passenger departure time loss and arrival-time loss is defined as g; the initial value of g is sufficiently large. There are k initial categories, k=k0.Step 2.
The centers ofk categories are determined randomly.Step 3.
All of the adjacent demand points are included in a category. Based on all of the sample points in each category, the center of this category is recalculated. Each step is repeated until either of the airports from consecutive calculations for all category centers is identical and the time gap is less than 3 min (the smallest interval of flight take-off time slots is 3 min) or the clustering reaches its limit (in this paper, 100). If category demand is too low (i.e., if category demand is below the minimal passenger load factor requirement for the smallest model), the demand points in this category are included in the adjacent category.Step 4.
For each demand category, based on corresponding passenger demand, the optimal airplane model is allocated. If passenger demand for that category exceeds the number of seats in the largest model, multiple flights are arranged. Each flight should choose a model to ensure total seating that meets demand without waste. If each category only requires 1 flight, the flight is arranged at the category center. If each category requiresn flights, then the flights are arranged at the category center and the n-1 moment adjacent to the category center.Step 5.
Calculateg′, the sum of actual passenger departure time loss and arrival-time loss. If g′≤g, save the category center and the flight schedule plan. If k<k1, then let k=k+1 and go to Step 2; otherwise, exit.The procedure for thek-means clustering algorithm is shown in Figure 2.Figure 2
The algorithm procedure.


## 4. Example and Analysis

In China’s Yangtze River Delta, a multiairport system has formed which is composed of 5 large airports: Shanghai Pudong International, Shanghai Hongqiao International, Nanjing Lukou International, Hangzhou Xiaoshan International, and Wuxi Sunan Shuofang International, identified as A, B, C, D, and E, respectively. These 5 airports are connected via a highly developed ground transport system, and each airport has a route to Beijing Capital International (H). Beijing Capital International is under enormous pressure to serve a high volume of flights, and its capacity has been saturated. Currently, Beijing Capital International’s abnormal flight rate reaches 95%; its capacity should be upgraded. However, Beijing Capital International’s capacity upgrade is constrained by airport landings and the construction period; it is very difficult to rapidly expand capacity. Therefore, the only solution is to manage demand and effectively reduce flights while assuring demand. The emergence of a multiairport system creates a favorable condition for reducing flights at the hub airport.In the Yangtze River Delta’s multiairport system, each airport’s passenger demand distribution at peak hours is listed in Table1. Because insufficient airport capacity primarily manifests in insufficient peak hour capacity, data collection primarily focuses on collecting passenger demand at each airport in a multiairport system during peak hours (2 hours). In a multiairport system, passenger time spent at each airport to depart from a different city via ground transport is listed in Table 2. Arriving flights and average flight delays at H airport are listed in Table 3. There are 3 airplane models: model 1 has 150 seats; model 2 has 220 seats; and model 3 has 350 seats. The minimal passenger load factor for airlines is 60%.Table 1
Passenger demand distribution of the 5 major airports to H airport.
Time/min
Airport A
Airport B
Airport C
Airport D
Airport E
0–5
32
6
21
11
32
5–10
26
8
26
13
53
10–15
42
9
16
11
63
15–20
63
16
19
16
63
20–25
47
23
21
15
47
25–30
21
21
23
19
11
30–35
11
11
29
21
11
35–40
37
16
32
23
53
40–45
42
7
25
19
84
45–50
53
6
17
16
74
50–55
21
13
19
11
63
55–60
16
15
18
8
74
60–65
13
13
19
11
68
65–70
26
11
23
21
53
70–75
17
8
17
16
47
75–80
34
6
21
18
42
80–85
47
8
11
16
11
85–90
34
4
21
15
21
90–95
21
2
11
17
27
95–100
17
6
37
19
26
100–105
23
5
20
21
19
105–110
19
7
22
16
11
110–115
26
6
27
19
8
115–120
29
3
25
21
11Table 2
Ground transportation time between 5 airports (min).
Airport
A
B
C
D
E
A
0
30
45
80
110
B
—
0
25
40
60
C
—
—
0
22
55
D
—
—
—
0
20
E
—
—
—
—
0Table 3
Flight number and average delay of H airport.
The number of fights
15–18
12–14
7–11
1–6
Delay/min
45
35
15
5First, assume that all flights employ the smallest model to carry passengers; the upper bound of flights is 18.81, that is, 18 flights. Next, assume that all flights employ the largest model to carry passengers; the lower bound of flights is 5.20, that is, 6 flights. The number of feasible solutions in this study is4.8467∗1026, which is a large-scale combinatorial optimization problem. Based on this study’s proposed algorithm, it is possible to circumvent the conventional method of finding the optimal solution in a feasible solution. In multiairport system operation mode, each airport’s flight schedule is listed in Table 4. Passenger demand is classified into 7 categories; the classification results are listed in Table 5. Passenger total time loss is 129,573 min, which includes departure time loss of 87,237 min and arrival-time loss of 42,336 min; the average flight’s passenger load factor is 90.1%. If an independent operation method is applied—that is, if the passenger demand at each airport is independent—each airport’s optimal flight schedule is listed in Table 6. Passenger demand at each airport is classified into 8 categories; the classification results are listed in Table 7. Passenger total time loss is 173,705 min, among which departure time loss is 83,388 min and arrival-time loss is 90,317 min; an average flight’s passenger load factor is 87.4%. Compared with the independent operation method, multiairport system operation mode employs more large airplanes. Large airplanes decrease the airline’s operation cost when the passenger load factor is high [19]. Full leveraging of the characteristics of multiairport system operation mode to optimize the multiairport system flight schedule benefits both airlines and passengers. However, the multiairport system method has not eliminated the centralized characteristics of each airport’s flight schedule. If the flight time from each airport to the destination airport is identical, congestion at the destination airport still results. Although this congestion is determined by the distribution of passenger demand, that demand can be redistributed via price guides to further discretize flight schedules and reduce congestion [20]. From the airport’s perspective, reduced flights seem to reduce revenue from airport departures and arrival charges; however, each airport can open new routes and assemble potential demand at other airports to achieve differentiated operation, improving the market positioning, differentiating and collaboration of each airport in the multiairport system [16], and achieving the maximum utilization of overall resources. Of course, this requires not only collaboration among the various airports in the multiairport system but also strong support from the civil aviation administration.Table 4
Flight time and frequency for multiairport system operation.
Airport
A
B
C
D
E
Model 1
8
6
Model 2
97,100
Model 3
32,35
28
106
66,69,72Table 5
Category result for multiairport system operation.
Category
Category 1
Category 2
Category 3
Category 4
Category 5
Category 6
Category 7
Airport
A
A
B
C
C
D
E
Time/min
32
8
28
97
6
106
69
Passenger volume
572
143
226
440
85
345
1021Table 6
Flight time and frequency for the independent operation.
Airport
A
B
C
D
E
Model 1
8
6
106
5,87
Model 2
11
86,89
Model 3
38
28
109
90,93Table 7
Category results for the independent operation.
Category
Category 1
Category 2
Category 3
Category 4
Category 5
Category 6
Category 7
Category 8
Airport
A
A
B
C
C
D
E
E
Time/min
8
38
28
6
86
109
5
90
Passenger volume
370
345
232
82
437
389
147
830


## 5. Algorithm Comparison and Analysis

In this study, based on a clustering analysis algorithm, optimization results can be obtained in 2,156 ns, which means this algorithm is highly effective. However, this algorithm’s superiority is not fully proved. Therefore, a genetic algorithm is designed to compare with the clustering algorithm. The genetic algorithm procedure is as follows:(1) Seed size is 100.(2) Gene configuration: every 1 min at each airport is defined as 1 gene. There are 2 h at 5 airports; therefore, each seed comprises 600 genes. In order, genes 1~120 are for the 1st airport, genes 121~240 are for the 2nd airport, and so on. Each gene is in the range of 0, 1, 2, and 3. Among them, 0 means no flight at this point; 1 means that the flight at this point is based on airplane model 1; 2 means that the flight at this point is based on airplane model 2; 3 means that the flight at this point is based on airplane model 3.Based on the maximum and minimum number of flights required to satisfy passenger demand, an integer between the 2 is generated randomly as flights for each gene. Next, flights are distributed randomly at 600 genes with random values of 1, 2, or 3. Other genes are set to 0.(3) Fitness function: the objective function value is defined as the fitness function. For any seed, if seats on all flights cannot satisfy passenger demand, then 1,000,000 min is added as punishment; if seat utilization on a certain flight is below the minimal seats constraint, then 1,000,000 min is added as punishment. The distance between the demand point and flight determines the adjacent flight to which each demand point is assigned, with the precondition that this flight has unbooked seats. When 1 demand point is assigned to a flight, the remaining seats on this flight decrease correspondingly.(4) Gene selection: the maximum value of the species fitness function is selected as the basis, and the difference between the fitness of the other seed and the maximum value of the fitness function is defined as the selection parameter for this seed. The proportion of each seed’s selection parameter is the sum of the selection parameters and is defined as each seed’s selection probability. Based on the roulette method, a seed is selected from the species to form the next-generation evolved species.(5) Gene exchange: the proportion of genes being exchanged is defined as 0.2. Two seeds are randomly selected from the species, and 1 gene locus is selected randomly. Next, the 2 seeds exchange genes after this gene locus to generate 2 new seeds.(6) Gene mutation: the proportion of genes being mutated is defined as 0.01. One seed is randomly selected from the species, and 1 nonzero gene locus and 1 zero gene locus are selected randomly to exchange 2 gene loci and generate 1 new seed.(7) Convergence condition: the generation of species evolutions is defined as the convergence condition, which is limited to 300.An optimization result can be obtained in 35,118 ns via the genetic algorithm; passenger total time loss is 132,424 min, among which the departure-loss time is 90,088 min and the arrival-time loss is 42,336 min. 11 flights are required to satisfy passenger demand; an average flight’s passenger load factor is 84.2%. Flight frequency and schedule are listed in Table8. This shows that the clustering algorithm has a superior optimization result. This calculation shows that the genetic algorithm convergence is unstable because each calculation has a different result most of the time; in comparison, the clustering algorithm is stable and returns identical results from each calculation.Table 8
Calculation results of genetic algorithm.
Airport
A
B
C
D
E
Model 1
119
Model 2
26
38
38,88
Model 3
25,55
17
6,31,42The manner in which the clustering algorithm calculates flight frequency and schedule is significantly different from the genetic algorithm. The primary reason for this result is that, in the clustering algorithm, when category demand exceeds flight seats, this category is not divided further. If this category is divided further until there is no alternative method of scheduling a flight for every category, then the flight is discretized, and the result is similar to that obtained using the genetic algorithm.


## 6. Conclusions

This paper is the first to investigate the multiairport system flight time and frequency-optimization problem. Minimizing passenger trip-time loss is defined as the objective function; passenger turnover rate and the airline passenger load factor are defined as constraints. A flight time and frequency-optimization model for multiairport system operation mode is created. Ak-means clustering algorithm is designed to find a solution; indexes such as flight time and frequency, passenger trip-time loss, airplane model, and quantity distribution method are obtained. In addition, this paper has applied theory to 5 large airports in the Yangtze River Delta. The calculation result shows that, compared to independent airport operation, although passenger departure time loss increases in multiairport system operation mode, arrival-time loss decreases by 53% from 90,317 min to 42,336 min; total time loss decreases by 25% from 173,705 min to 129,573 min; and passenger trip efficiency improves. Moreover, this method employs more large airplanes, and the average flight passenger load factor improves by 3.1%, effectively decreasing airlines’ costs. This shows that flight time optimization in multiairport system operation mode benefits both airlines and passengers.Next, this study has designed a genetic algorithm to compare to a clustering algorithm. The result shows that in terms of either the convergence rate or the optimization result, the clustering algorithm is always superior. Genetic algorithm convergence is unstable because most of the time the calculation result is different. In comparison, the clustering algorithm result is relatively stable. This shows that when category demand matches flights, the two calculations have similar results, thus proving the accuracy of the clustering algorithm.In summary, this paper has proposed a flight time and frequency-optimization method for multiairport system operation mode, providing important guidance for solving airport congestion by reducing flights at hub airports. It is noteworthy that this paper has not considered the effect of competition among airlines on passenger demand and flight schedules. These issues require further analysis in future research.



---

*Source: 7371461-2017-07-05.xml*