# Multiobjective Optimization Model for Collaborative En-Route and Slot Allocation

Authors: Shangwen Yang; Jingting Zhang; Ping Chen; Yongjie Yan
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

To allocate the en-routes and slots resource to the flights with collaborative decision-making, a multiobjective 0-1 integer programming model was proposed. According to different demands from air traffic control departments, airlines, and passengers, efficiency, equity, and effectiveness principles of collaborative decision-making were considered. With the aim to minimize the total flight delay costs, the total number of turning points, and average delay time of passengers, the effectiveness constraints were achieved. The algorithm was designed to solve the model on the basis of the objective method, and Lingo11 and MatlabR2007b were applied in numerical tests. To test how well the model works in real world, a numerical test was performed based on the simulated data of a civil en-route. Test results show that, compared with the traditional strategy of first come first served, the model gains better effect. The superiority of the model was verified.


---

## Body

## 1. Introduction

En-route and slot resource allocation which assigns available en-routes and time slots in coming time period to flights is one of the key technologies of collaborative en-route management. There have been some achievements; typical ones are formulated below. In 2000, Goodhart [1] studied the preferences of airlines during en-route resource allocation when the airspace was confined. In 2005, AFP (Airspace Flow Program) was proposed by FAA (Federal Aviation Administration) [2] and was applied in alleviating air traffic pressure and reducing the influence of adverse weather. In AFP, flights are allowed to flexibly choose suitable en-route. According to real capacity of confined airspace, AFP allocates en-route and slot resource using traditional RBS (Ration-by-Schedule) algorithm in accordance with FCFS (first come first served). RBS well embodies the equity of resource allocation. Ball et al. [3] proposed RBD (ration-by-distance) algorithm of which the efficiency was better than RBS and the equity was worse. In 2005, Hoffman et al. [4] proposed an en-route resource allocation method considering airspace users’ preferences and air traffic management decisions. In 2009, in the context of AFP, Pourtaklo and Ball [5] proposed an algorithm equitably allocating the en-routes and slots according to flight operators’ preferences and their randomicity. Since 2006, AFP has been applied in reducing flight delay and the effect has been verified by practice [6]. However, CTOP (Collaborative Trajectory Options Program) optimally allocating en-route resource with CDM (collaborative decision making) was proposed by FAA and carried out in 2014 [7]. CTOP concentrates on resource attributes of airspace and satisfies flight operators’ preferences. In CTOP, different en-routes have different operation costs, and air traffic flow management strategies are introduced in. CTOP uses RBS algorithm and assigns flights holding on the ground or rerouting before entering confined airspace [8]. Market mechanism is also an important way for collaborative en-route and slot allocation. At this time, en-route and slot resource is a type of competitive resource. Market mechanisms such as bid and auction were introduced in en-route, and slot resource allocation was performed according to the need of airlines [9–12]. In 2013, Kim and Hansen [13] proposed an evaluation model for en-route resource allocation effect. The model holds that there is some uncertainty on operation costs due to flight operators’ preferences and analyzes the deviations of delay costs resulting from four typical methods, respectively, that is, FISO (Full Information System-optimal), PASO (Parametric System-optimal), FSFA (First Submitted First Assigned), and RBS. The effect of each method was evaluated in [13]. In 2015, Kim and Hansen [14] proposed an en-route sequential resource allocation model based on game theory. Flight operators could compare the benefits resulting from different time of submitting en-route application, and there was competition about submitting time. It is good for determining the time of submitting en-route application.In existing achievements, various delay costs are the main index for en-route resource allocation. Although the evaluation ways of delay costs are different, single objective is one-sided. The references on multiobjective programming for en-route and slot resource allocation are less seen. Collaborative en-route management refers to the stakeholders such as air traffic control department, airlines, and passengers with the aspects of efficiency, equity, and effectiveness. Delay costs primarily express the efficiency. It is worth establishing multiobjective models expressing the needs of the stakeholders and providing various strategies. In the paper, we proposed a multiobjective 0-1 integer programming model for en-route and slot resource allocation with the aim to minimize the total flight delay costs, the total number of turning points, and average delay time of passengers. The three objectives represent the preferences or interests of these stakeholders. Necessary constraints on en-route capacity, arrival time, and the allocation completeness are also included. To gain noninferior solutions with less complexity, we designed the solving algorithm on the basis of the objective method. The remainder is organized as follows. In Section2, the operative environment is briefly introduced. In Section 3, the multiobjective model is formulated, and necessary notations are given. In Section 4, the solving algorithm is formulated. In Section 5, a numerical test based on the simulated data of a civil en-route is made to illustrate the efficiency of the model, and necessary analyses are performed. Finally, we conclude in Section 6.


## 2. Operative Environment

As shown in Figure1, the planned en-route is from en-route point 1 to en-route point 2. The en-route point 1 is the entry, and the en-route point 2 is the exit as well as the entry to the airspace sector downstream (en-route or controlled sector). When the capacity of the planned en-route decreases due to adverse weather, air traffic flow would be confined. Flight delay would occur. It is a better way to open several temporary en-routes near the planned en-route and divert some flights to temporary en-routes. Then, the flights from the planned en-route and the temporary en-routes would enter the airspace sector downstream at en-route point 2. When a temporary en-route is established, the features such as cost and range are known. Generally speaking, each en-route is featured by its capacity, delay cost, flight time, and the number of turning points. It is necessary to determine the en-route and the time entering the airspace sector downstream for each flight. Due to the relationship between planned en-route and airspace sector downstream, collaborative en-route and slot allocation model should assign the en-route and slot to a flight efficiently, equitably, and effectively according to the slots of airspace sector downstream and the capacities of the en-routes. The preferences or interests of these stakeholders should be combined, and multiple objectives should be achieved. It aims to alleviate airspace congestion and ensure the clearance of air traffic.Figure 1
The diagram of collaborative en-route operation.


## 3. Mathematical Model

Delay cost is the essential characteristic of the allocation efficiency and is related to the benefits of the airlines. Furthermore, delay costs in the en-routes are different with each other. Generally speaking, delay costs in temporary en-route are more than planned en-route, and the flights with different aircraft types have different delay costs. Then, the objective on allocation efficiency aiming to minimize total delay costs can be formulated as follows.(1)min∑i=1I∑j=1Jcsxij+∑k=1Kctkyijktj-etai.In formulation (1), cs represents the delay costs per unit time in planned en-route, and ctk represents the delay costs per unit time in temporary en-route k (1≤k≤K, where K is the number of temporary en-routes). tj (1≤j≤J, where J is the number of the slots) is the initial time of a slot and represents the slot. etai represents the estimated time of arrival (ETA) at airspace sector downstream for flight i (1≤i≤I, where I is the number of the flights). xij and yijk are decision variables, which can be formulated as follows.(2)xij=1,slotjandplanneden-routeforflighti,0,otherwise,yijk=1,slotjandtemporaryen-routekforflighti,0,otherwise.Turning points directly express the complexity of en-routes and the workload of air traffic control. Then, the objective on air traffic control efficiency aiming to minimize the total number of turning points can be formulated as follows.(3)min∑i=1I∑j=1Jrsxij+∑k=1Krtkyijk.In formulation (3), rs represents the number of turning points in planned en-route, and rtk represents the number of turning points in temporary en-route k.Delay time is most concerned by passengers and expresses the quality of airlines service. When flight delay occurs, delay time should be balanced to avoid large delay for part of passengers. Then, the objective on allocation equity aiming to minimize average delay time of passengers can be formulated as follows.(4)min∑i=1I∑j=1Jnitj-etaixij+∑k=1Kyijk∑i=1Ini.In formulation (4), ni represents the number of passengers in flight i.Then, the constraints meeting allocation effectiveness can be formulated as follows.(5)∑j=1Jxij+∑k=1Kyijk=1,1≤i≤I,(6)∑i=1Ixij+∑k=1Kyijk≤1,1≤j≤J,(7)tj≥etai,1≤i≤I,1≤j≤J,(8)tj≥etai+Δkyijk,1≤i≤I,1≤j≤J,1≤k≤K,(9)∑i=1I∑j=1Jxij≤Cas,(10)∑i=1I∑j=1Jyijk≤Catk,1≤k≤K.Constraint (5) ensures that there would be only an en-route and a slot for a flight. Constraint (6) ensures that a slot could be assigned to no more than one flight. Constraint (7) ensures that real time of arrival (RTA) at airspace sector downstream would not be earlier than ETA. Constraint (8) ensures that RTA would not be earlier than ETA with the addition of flight time resulting from temporary en-routes, where Δk is the additional flight time resulting from temporary en-route k. Constraint (9) ensures that air traffic flow would not exceed the capacity of planned en-route, where Cas represents the capacity of planned en-route. Constraint (10) ensures that air traffic flow would not exceed the capacity of temporary en-routes, where Catk represents the capacity of temporary en-routek.


## 4. Algorithm Designing

Generally speaking, the methods for solving multiobjective optimization include weighted sum method and noninferior method (Pareto-optimal method). The weighted sum method combines all the multiobjective functions into single composite objective function using the weighted sum, and the solutions are affected by the weights. Noninferior method has been widely used. Based on the objective method [15], we successively retained one of the objectives and translated other objectives into the constraints. Then, the multiobjective programming model could be formulated as a single-objective programming model. Mathematical software Lingo11 was applied in solving a group of single-objective models. The detailed process of the algorithm is shown in Figure 2.Figure 2
The process of the algorithm.In the algorithm, largerε may result in omitting noninferior solutions, while less ε may result in the decrease of the algorithm efficiency. It is not clear how to exactly determine the value of ε. Generally speaking, the initial value of ε is less. Then, the initial value of ε should be gradually increased to gain all of noninferior solutions according to the need of real simulation.


## 5. Numerical Test

Set the simulated data of a civil en-route as an example. The capacity of the en-route decreased due to adverse weather, and flight delay would be caused. According to available airspace and air traffic control experiences, two temporary en-routes were set. The information of the three en-routes is shown in Table1 where delay costs per hour are for light (L) flights in each en-route. Medium (M) and heavy (H) flights are, respectively, two times and four times the values of light flights according to experiences. Generally speaking, flight time and delay costs in temporary en-routes are larger than those in planned en-route. In the test, flight time in planned en-route is twenty minutes, and the flight time in temporary en-route 1 and temporary en-route 2 is, respectively, 5% and 15% larger than that in planned en-route. The information of the flights is shown in Table 2. The capacity of airspace sector downstream is ten flights per hour, and the length of a slot is six minutes.Table 1
The information of the en-routes.
Number
En-route
Capacity (flights/hour)
Flight delay costs (yuan/hour)
The number of turning points
(
1
)
Planned en-route
4
2400
1
(
2
)
Temporary en-route 1
9
3300
2
(
3
)
Temporary en-route 2
5
2900
3Table 2
The information of the flights.
Number
Aircraft type
ETA
The number of the passengers
(
1
)
H
10:00
260
(
2
)
H
10:02
280
(
3
)
M
10:04
120
(
4
)
H
10:06
300
(
5
)
M
10:08
110
(
6
)
M
10:10
100
(
7
)
H
10:12
280
(
8
)
M
10:14
120
(
9
)
L
10:16
70
(
10
)
M
10:18
140
(
11
)
H
10:20
300
(
12
)
M
10:22
100
(
13
)
H
10:24
270
(
14
)
M
10:26
130
(
15
)
M
10:28
140
(
16
)
H
10:30
290
(
17
)
H
10:32
250
(
18
)
L
10:34
70
(
19
)
H
10:36
300
(
20
)
H
10:38
260
(
21
)
H
10:40
280
(
22
)
H
10:42
240
(
23
)
M
10:44
130
(
24
)
M
10:46
150
(
25
)
H
10:48
280
(
26
)
L
10:50
70
(
27
)
H
10:52
250
(
28
)
M
10:54
130
(
29
)
H
10:56
270
(
30
)
H
10:58
300Mathematical software Lingo11 and MatlabR2007b were applied in solving the model, where MatlabR2007b was used for processing data and creating decision matrices. Noninferior solutions are shown in Figure3.Figure 3
Test results.FCFS is the typical method for en-route and slot resource allocation and well represents the equity. We perform FCFS using MatlabR2007b, and the allocation strategy is shown in Table3. The total delay costs, average delay time of passengers, and the total number of turning points are 249840 yuan, 59.61 minutes, and 60, respectively.Table 3
FCFS strategy.
No.
(
1
)
(
2
)
(
3
)
(
4
)
(
5
)
(
6
)
(
7
)
(
8
)
(
9
)
(
10
)
(
11
)
(
12
)
(
13
)
(
14
)
(
15
)
(
16
)
(
17
)
(
18
)
(
19
)
(
20
)
(
21
)
(
22
)
(
23
)
(
24
)
(
25
)
(
26
)
(
27
)
(
28
)
(
29
)
(
30
)
RTA
1000
1006
1012
1018
1024
1030
1036
1042
1048
1054
1100
1106
1112
1118
1124
1130
1136
1142
1148
1154
1200
1206
1212
1218
1224
1230
1236
1242
1248
1254
Selected en-route
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3For the noninferior solutions in Figure3, the average values of the total delay costs, average delay time of passengers, and the total number of turning points are 158748.75 yuan, 37.39 minutes, and 56.46, respectively.It can be seen from test results that the model proposed is remarkably better than FCFS and takes account of the efficiency and equity. The model formulates the objectives representing the interests of the stakeholders such as air traffic control department, airlines, and passengers and provides various strategies. The algorithm is easy to perform. In the numerical test, Lingo11 completely solved each single-objective programming using branch and bound.


## 6. Conclusion

According to the efficiency, equity, and effectiveness principles of collaborative decision-making as well as the stakeholders such as air traffic control departments, airlines, and passengers, we proposed a multiobjective 0-1 integer programming model for en-route and slot resource allocation with the aim to minimize the total flight delay costs, the total number of turning points, and average delay time of passengers. We performed the numerical test based on the simulated data of a civil en-route with Lingo11 and MatlabR2007b. Test results show superiority of the model. Collaborative en-route management refers to various stakeholders, decision-making demands, and airspace environment. Next research would consider more decision objectives and propose mathematical models or algorithms being fit for different en-route operation conditions.



---

*Source: 5686281-2018-01-31.xml*