# Research on Aircraft Surface Taxi Path Planning and Conflict Detection and Resolution

Authors: Ningning Zhao; Nan Li; Yu Sun; Lei Zhang
Journal: Journal of Advanced Transportation
 (2021)

---

## Abstract

Aircraft surface taxiing conflict avoidance is mostly adopted by waiting and rerouting methods, but this method does not consider the difference in total taxiing time that may be caused by different strategies. In this study, the airport taxiing path optimization model and taxiing area division model are constructed first. Then, the taxiway use is controlled by subregion based on the analysis of the surface activity area connection relationship. Based on the results of aircraft surface taxiway preselection, the time window of the taxiing area is solved and conflict detection is performed. For aircraft with taxiing conflicts, waiting or changing paths is selected to deconflict taxiing by comparing priorities. An improvedA∗ algorithm solution is applied to generate conflict-free glide paths and new glide trajectory occupancy time windows, while the glide paths of aircraft without glide conflicts are not affected. The results of the study show that the use of time windows for conflict detection and deconfliction can further reduce the total taxiing time of aircraft operating on the surface, resulting in a significant reduction in the number of aircraft conflicts, and thus, airport operational safety is ensured. This study has a high practical value and is expected to be applied in the real-time control decision of aircraft taxiing in the future.


---

## Body

## 1. Introduction

With the continuous development of the goal of “building a powerful air transport country,” my country’s civil aviation industry has developed rapidly in recent years. According to statistics, the compound annual growth rates of my country’s total civil aviation transportation turnover, civil aviation passenger transportation and turnover, and civil aviation cargo and mail transportation and turnover from 2011 to 2018 were 11.10%, 11.08%, 13.06%, 4.10%, 4.10%, and 6.06%, respectively [1]. With the increase in flight business, major airports have been constantly renovating and expanding to cope with the increasingly congested traffic volume. At the same time, various airports across the country have also adopted measures such as increasing runways and parking spaces, building more terminal buildings, and constantly introducing field monitoring equipment. Other measures are to further increase the surface operating capacity. However, as the number of multirunway airports continues to increase, the airport surface structure is becoming increasingly complex. As the multirunway system is in operation, the flight activities between the various runways and the airport airspace affect each other, which further causes the problem of surface conflict and congestion to become more serious. According to statistics, the average delay time for departures from domestic airports in 2019 is about 28.16 minutes, of which the average delay time for departure in July reached 39.51 minutes [2]. According to statistics, the direct economic loss caused by every 10% of flight delays is as high as 1.5 billion euros [3]. The increasingly complicated airport scene layout has led to frequent taxiing congestion incidents on the scene, threatening the safety of aircraft taxiing and greatly reducing the efficiency of airport operations. Literature 4 statistics on the average taxi time of flights at major airports across the country in 2018 show that Urumqi Diwopu Airport has the longest taxi time at 27.8 minutes and Beijing Capital Airport has an average taxi time of about 25.3 minutes, ranking second. The shortest taxi time is Sanya Phoenix Airport, which is 13.4 minutes. In 2018, the average extra taxi time data of my country’s airports was about 1.5 minutes per sortie, which is similar to Europe. However, some busy airports in my country have the problem of more extra taxi time, with an average of about 4.94 minutes per sortie, while the throughput of Europe is relatively high. The extra taxi time of a large airport is 2.8 min/sort. The problem of airport capacity restriction caused by the aircraft’s long taxi time cannot be ignored [4]. Therefore, the conflict between the limited airport resources and the increasing passenger traffic volume in China is becoming increasingly serious, and the consequent problems, including airport surface conflict and declining of flight punctuality, are also becoming severer; thus, effective trajectory prediction and conflict resolution is an effective way to improve the flight punctuality and guarantee the safe operation of flights. There are many research studies on 4D trajectory prediction and surface conflict at home and abroad. Jun Chen et al. used aircraft surface taxiing velocity profiles to compute low-cost and environmental 4D trajectories by combining 4D trajectories and path scheduling together into a multiobjective optimization subject [5]. Wickramasinghe et al. quantified the optimization of 4D trajectories in relation to aircraft flight plans and showed that 4D trajectories can optimize the flight plans of aircraft [6]. Zhang et al. used linear programming to allocate the arrival time of the control points. The particle swarm optimization methods are used to optimize the speed of the distribution control points. They generate an improved and more accurate taxiing speed curve [7]. Yang obtained optimized 4D trajectory predictions using an isometric trajectory modeling method [8]. Wang et al. used a multiobjective immune optimization method to solve the Pareto optimum speed curve of the aircraft by establishing an aircraft motion model as well as a discrete taxiing speed model, and the results showed that the method can provide a variety of accurate taxiing velocity profiles for the surface aircraft [9]. Podgrski and Skorupski constructed a dynamic taxiing path choice model to describe airport surface congestion by using conflict points and calculated the conflict resolution of taxiing paths through a simulation model [10]. Li et al. constructed a model with the least taxiing time as the objective function and the typical conflict of aircraft taxiing as the constraint to solve the optimized aircraft taxiing path by using a genetic algorithm. The results showed that the method effectively avoids taxiing conflicts [11]. Wang constructed an airport structure model to optimize the aircraft surface taxiing paths conditional on the temporal and spatial distribution characteristics of airport conflicts. The results showed that the model can lead to a reduction in aircraft taxiing time and a decrease in the number of surface taxiing conflicts [12]. To further reduce the number of aircraft surface conflicts, Li et al. constructed a model and solved it with the A∗ algorithm to obtain the optimized aircraft taxiing time by taking the airport taxiing rules, aircraft wake interval, and conflict avoidance restrictions as constraints and the surface conflict as minimization objective function [13]. However, there are few research studies on the combination of conflict detection and relief of aircraft taxiing paths.Studies have shown that when taxiing conflicts on the airport surface, aircraft waiting or replanning the route are often used to avoid conflicts, but the selection of different strategies may cause the total taxi time to be different. Here, the use of taxiway is controlled in a subregion based on the analysis of the airport movement area connection relationship, and the time window occupied by the taxiing area is solved for conflict detection based on preliminary results of the taxiing path on the aircraft scene. For the aircraft with taxiing conflicts, by comparing the priority, the waiting, or changing, the path is selected to deconflict the taxiing conflicts, and then, the time window occupied by the conflict-free taxiing path and the new navigational trajectory is generated for the aircraft.


## 2. Planning and Solving of Aircraft Taxiing Path on the Surface

P surface taxiing paths are generated for any aircraft k in the aircraft set F = {f1, f2, …, fn}. Among them, the preselected article z taxiing path Lkz (1 ≤ k ≤ n, 1 ≤ z ≤ p) is composed of a group of ordered nodes {N1, N2, …, Nq}. There are M nodes in the airport network model V; therefore, ≤M, Ni, Nj, Nr ∈ V, (Ni, Nj) ∈ E, i = 1, 2, …, q, j = 1, 2,…, q, among which the meanings of variables are as follows.xij = 1, which means that the aircraft k taxis from node Ni to node Nj; otherwise, xij = 0;dij is the length of straight-line taxiway section (Ni, Nj) in the taxiway systemtij is the taxiing time of the aircraft on the straight-line taxiing section (Ni, Nj)Rr = 1 indicates that the aircraft k turns at the node Nr; otherwise, Rr = 0;dr is the turning length at the node Nr during aircraft surface taxiingtr is the turning and taxiing time of the aircraft at the node Nr. Then, the total taxiing distance of the aircraft can be obtained from the following formula:(1)D=∑i=1m∑j=1mxijdij+∑i=1mRrdr.There are two objective functions: the first∑i=1m∑j=1mxijdij is the taxiing distance of the aircraft on each straight taxiing section. Among them, xij is determined by the node Ni taxiing straight to the node Nj whether the aircraft k is routed to the node Nj, the value is 1 or 0, and dij is the length of the taxiing road segment (Ni, Nj); the second ∑i=1mRrdr is the turning distance of the aircraft turning node, which depends on whether the aircraft is at the node Nr. Decide when you turn, Ri takes the value 1 or 0, and dr can be expressed as(2)dr=θrπr180.The taxiing process of the aircraft turning section is shown in Figure1.Figure 1
The taxiing process of the aircraft turning section.As shown in Figure1, the calculation assumes that the scene aircraft k starts taxiing at the node Nu and passes through the Ng and Nw nodes in turn. In reality, the aircraft has a turn length at the Ng point, and the aircraft starts taxiing at the Nu point, turning from the Nr point. Nf end the turn at a point and continue to slide to Nw. The actual length of the taxiing distance of the aircraft on this section is the sum of the straight length dfw, the straight length dur, and the turning length dr.Because there are many variables in the model, the Bellman–Ford algorithm andA∗ algorithm are used to solve the problem. The cost evaluation function of the A∗ algorithm is(3)fn=gn+hn,where n is the current node; f(n) is the cost evaluation function from the starting point through the node n to the target point; gn is the actual cost from the starting node to the node n, and h(n) is the estimated cost from the node n to the target point. When n is the starting node, (n) = 0; if h(n) = 0, the A∗ algorithm is the Dijkstra algorithm without heuristic information. The search goal of the A∗ algorithm is to find the k path with the shortest taxi distance for the request aircraft; then, f(n) is the total taxi distance from the starting node to the target node, and gn is the glide distance from the initial node to the current node n. h(n) is preprocessed before the algorithm is executed. Reverse all sections of the airport, execute the Bellman–Ford algorithm starting from the target point, and calculate the shortest sliding distance from the target point to all nodes in advance, and the calculated distance value is h(n).


## 3. Aircraft Taxiing Conflict Types and Time Windows

### 3.1. Types of Aircraft Taxiing Conflicts

Aircraft taxiing conflicts at the surface are mainly of the following three types [14].


#### 3.1.1. Head-to-Head Conflict

Assuming that aircraft 1 and aircraft 2 are expected to arrive at the same or similar times on the same taxiway, a head-on conflict will be caused when the two aircraft taxi in opposite directions, as shown in Figure2.Figure 2
Head-to-head conflict.To avoid head-to-head conflicts in the surface, taxiing, ATC can direct aircraft 2 to stop at intersection B for waiting according to the priority. If aircraft 2 has already passed intersection B, dynamic path planning will change the taxiing path of aircraft 1 and direct aircraft 1 to pass through intersection A without interrupting the taxiing of both aircraft 1 and aircraft 2.


#### 3.1.2. Cross-Conflict

Assuming that aircraft 1 and aircraft 2 pass through the same intersection and are expected to arrive at the intersection at the same or a similar time, a crossover conflict may arise, as shown in Figure3.Figure 3
Cross-conflict.To avoid surface taxi crossover conflicts, the ATC can instruct aircraft 2 to wait before reaching the intersection to avoid aircraft 1, and after it passes, aircraft 2 continues taxiing on a preplanned trajectory while maintaining wake separation.


#### 3.1.3. Rear-End Conflict

Assume that aircraft 1 and aircraft 2 are taxiing in the same direction with different taxiing speeds on the same taxi line. The distance between the rear aircraft and the front aircraft is less than the minimum safety interval, which may cause a rear-end conflict, as shown in Figure4.Figure 4
Rear-end conflict.To avoid rear-end conflicts at the surface, the ATC may command aircraft 2 not to enter the section until aircraft 1 passes this section and meet the safe wake interval.


### 3.2. Aircraft Taxiing Area and Taxi Time Window

#### 3.2.1. Taxiing Area Division Model

According to the airport network model, the taxiway area connection relationship is known, and then, the taxiway is divided into several nonoverlapping areas according to the area connection relationship to obtain the taxiway area division model. Finally, the two are superimposed according to the spatial location to obtain the hierarchical taxiway structure model, as shown in Figure5.Figure 5
Schematic diagram of the taxiway node network, area division, and taxi path.The safety of aircraft taxiing is ensured by the method of controlled operation of the surface in zones, limiting each zone to one aircraft. To improve taxiway utilization efficiency, longer paths are segmented based on node locations. The algorithm generates forecast data for the aircraft after receiving its request, including the aircraft taxiing path, the velocity profile in each road segment, the desired arrival time at each point, and the taxiing time window corresponding to each region. When the aircraft taxiing area occupancy time window conflict is detected, the conflict is deconflicted based on the current aircraft surface taxiway occupancy time window situation to meet the area usage restriction requirements. After the conflict resolution is completed, timely update the prediction path of the surface sliding and the time window of the area occupation time window to ensure that the predicted velocity profile corresponds to the regional occupation time window.


#### 3.2.2. Aircraft Taxi Time Window

Based on the aircraft request information and taxi path prediction results, calculate the moments when the aircraft enters each taxiway area on the taxiing trajectory and leaves each taxiway area and then solve the occupation time window of each area on the taxiing trajectory [15, 16].Assume that the moment when aircraftk enters taxiing region Qi is denoted as tiink and the moment when it leaves taxiing region Qi is denoted as tioutk. If Qi is the starting taxiing area, the time when aircraft k enters the area Qi is equal to the path planning start time t0. If Qi is not the starting taxiing area, then aircraft k entering the taxiing area Qi at the time tiink is the moment ti−1outk of leaving the taxiing area Qi−1. If Qi is the ending taxiing area, the time when the aircraft k leaves the area Qi, tioutk is equal to the end taxi time te, satisfying the following equation:(4)tiink=t0,i=1tiink=ti−1outk=titioutk=te,i=e−1,2≤j≤e−1.Taxi time window vector: the set of occupied time windows for each region of aircraftk on the planned taxi path Lkz. The time window twi (k) of aircraft k occupying taxiing region Qi can be defined as the two tuples tiink and tioutk:(5)twik=tiink,tioutk.Therefore, the taxiing time window vectorLkz of the path (k) can be defined by(6)TWk=tw1k,tw2k,…,twe−1k.


## 3.1. Types of Aircraft Taxiing Conflicts

Aircraft taxiing conflicts at the surface are mainly of the following three types [14].


### 3.1.1. Head-to-Head Conflict

Assuming that aircraft 1 and aircraft 2 are expected to arrive at the same or similar times on the same taxiway, a head-on conflict will be caused when the two aircraft taxi in opposite directions, as shown in Figure2.Figure 2
Head-to-head conflict.To avoid head-to-head conflicts in the surface, taxiing, ATC can direct aircraft 2 to stop at intersection B for waiting according to the priority. If aircraft 2 has already passed intersection B, dynamic path planning will change the taxiing path of aircraft 1 and direct aircraft 1 to pass through intersection A without interrupting the taxiing of both aircraft 1 and aircraft 2.


### 3.1.2. Cross-Conflict

Assuming that aircraft 1 and aircraft 2 pass through the same intersection and are expected to arrive at the intersection at the same or a similar time, a crossover conflict may arise, as shown in Figure3.Figure 3
Cross-conflict.To avoid surface taxi crossover conflicts, the ATC can instruct aircraft 2 to wait before reaching the intersection to avoid aircraft 1, and after it passes, aircraft 2 continues taxiing on a preplanned trajectory while maintaining wake separation.


### 3.1.3. Rear-End Conflict

Assume that aircraft 1 and aircraft 2 are taxiing in the same direction with different taxiing speeds on the same taxi line. The distance between the rear aircraft and the front aircraft is less than the minimum safety interval, which may cause a rear-end conflict, as shown in Figure4.Figure 4
Rear-end conflict.To avoid rear-end conflicts at the surface, the ATC may command aircraft 2 not to enter the section until aircraft 1 passes this section and meet the safe wake interval.


## 3.1.1. Head-to-Head Conflict

Assuming that aircraft 1 and aircraft 2 are expected to arrive at the same or similar times on the same taxiway, a head-on conflict will be caused when the two aircraft taxi in opposite directions, as shown in Figure2.Figure 2
Head-to-head conflict.To avoid head-to-head conflicts in the surface, taxiing, ATC can direct aircraft 2 to stop at intersection B for waiting according to the priority. If aircraft 2 has already passed intersection B, dynamic path planning will change the taxiing path of aircraft 1 and direct aircraft 1 to pass through intersection A without interrupting the taxiing of both aircraft 1 and aircraft 2.


## 3.1.2. Cross-Conflict

Assuming that aircraft 1 and aircraft 2 pass through the same intersection and are expected to arrive at the intersection at the same or a similar time, a crossover conflict may arise, as shown in Figure3.Figure 3
Cross-conflict.To avoid surface taxi crossover conflicts, the ATC can instruct aircraft 2 to wait before reaching the intersection to avoid aircraft 1, and after it passes, aircraft 2 continues taxiing on a preplanned trajectory while maintaining wake separation.


## 3.1.3. Rear-End Conflict

Assume that aircraft 1 and aircraft 2 are taxiing in the same direction with different taxiing speeds on the same taxi line. The distance between the rear aircraft and the front aircraft is less than the minimum safety interval, which may cause a rear-end conflict, as shown in Figure4.Figure 4
Rear-end conflict.To avoid rear-end conflicts at the surface, the ATC may command aircraft 2 not to enter the section until aircraft 1 passes this section and meet the safe wake interval.


## 3.2. Aircraft Taxiing Area and Taxi Time Window

### 3.2.1. Taxiing Area Division Model

According to the airport network model, the taxiway area connection relationship is known, and then, the taxiway is divided into several nonoverlapping areas according to the area connection relationship to obtain the taxiway area division model. Finally, the two are superimposed according to the spatial location to obtain the hierarchical taxiway structure model, as shown in Figure5.Figure 5
Schematic diagram of the taxiway node network, area division, and taxi path.The safety of aircraft taxiing is ensured by the method of controlled operation of the surface in zones, limiting each zone to one aircraft. To improve taxiway utilization efficiency, longer paths are segmented based on node locations. The algorithm generates forecast data for the aircraft after receiving its request, including the aircraft taxiing path, the velocity profile in each road segment, the desired arrival time at each point, and the taxiing time window corresponding to each region. When the aircraft taxiing area occupancy time window conflict is detected, the conflict is deconflicted based on the current aircraft surface taxiway occupancy time window situation to meet the area usage restriction requirements. After the conflict resolution is completed, timely update the prediction path of the surface sliding and the time window of the area occupation time window to ensure that the predicted velocity profile corresponds to the regional occupation time window.


### 3.2.2. Aircraft Taxi Time Window

Based on the aircraft request information and taxi path prediction results, calculate the moments when the aircraft enters each taxiway area on the taxiing trajectory and leaves each taxiway area and then solve the occupation time window of each area on the taxiing trajectory [15, 16].Assume that the moment when aircraftk enters taxiing region Qi is denoted as tiink and the moment when it leaves taxiing region Qi is denoted as tioutk. If Qi is the starting taxiing area, the time when aircraft k enters the area Qi is equal to the path planning start time t0. If Qi is not the starting taxiing area, then aircraft k entering the taxiing area Qi at the time tiink is the moment ti−1outk of leaving the taxiing area Qi−1. If Qi is the ending taxiing area, the time when the aircraft k leaves the area Qi, tioutk is equal to the end taxi time te, satisfying the following equation:(4)tiink=t0,i=1tiink=ti−1outk=titioutk=te,i=e−1,2≤j≤e−1.Taxi time window vector: the set of occupied time windows for each region of aircraftk on the planned taxi path Lkz. The time window twi (k) of aircraft k occupying taxiing region Qi can be defined as the two tuples tiink and tioutk:(5)twik=tiink,tioutk.Therefore, the taxiing time window vectorLkz of the path (k) can be defined by(6)TWk=tw1k,tw2k,…,twe−1k.


## 3.2.1. Taxiing Area Division Model

According to the airport network model, the taxiway area connection relationship is known, and then, the taxiway is divided into several nonoverlapping areas according to the area connection relationship to obtain the taxiway area division model. Finally, the two are superimposed according to the spatial location to obtain the hierarchical taxiway structure model, as shown in Figure5.Figure 5
Schematic diagram of the taxiway node network, area division, and taxi path.The safety of aircraft taxiing is ensured by the method of controlled operation of the surface in zones, limiting each zone to one aircraft. To improve taxiway utilization efficiency, longer paths are segmented based on node locations. The algorithm generates forecast data for the aircraft after receiving its request, including the aircraft taxiing path, the velocity profile in each road segment, the desired arrival time at each point, and the taxiing time window corresponding to each region. When the aircraft taxiing area occupancy time window conflict is detected, the conflict is deconflicted based on the current aircraft surface taxiway occupancy time window situation to meet the area usage restriction requirements. After the conflict resolution is completed, timely update the prediction path of the surface sliding and the time window of the area occupation time window to ensure that the predicted velocity profile corresponds to the regional occupation time window.


## 3.2.2. Aircraft Taxi Time Window

Based on the aircraft request information and taxi path prediction results, calculate the moments when the aircraft enters each taxiway area on the taxiing trajectory and leaves each taxiway area and then solve the occupation time window of each area on the taxiing trajectory [15, 16].Assume that the moment when aircraftk enters taxiing region Qi is denoted as tiink and the moment when it leaves taxiing region Qi is denoted as tioutk. If Qi is the starting taxiing area, the time when aircraft k enters the area Qi is equal to the path planning start time t0. If Qi is not the starting taxiing area, then aircraft k entering the taxiing area Qi at the time tiink is the moment ti−1outk of leaving the taxiing area Qi−1. If Qi is the ending taxiing area, the time when the aircraft k leaves the area Qi, tioutk is equal to the end taxi time te, satisfying the following equation:(4)tiink=t0,i=1tiink=ti−1outk=titioutk=te,i=e−1,2≤j≤e−1.Taxi time window vector: the set of occupied time windows for each region of aircraftk on the planned taxi path Lkz. The time window twi (k) of aircraft k occupying taxiing region Qi can be defined as the two tuples tiink and tioutk:(5)twik=tiink,tioutk.Therefore, the taxiing time window vectorLkz of the path (k) can be defined by(6)TWk=tw1k,tw2k,…,twe−1k.


## 4. Aircraft Taxiing Conflict Detection and Resolution

When there is a conflict in the planned trajectory time window, the aircraft chooses to wait or change its path to resolve the taxiing conflict based on comparing its priorities. High-priority aircraft can pass the conflict area directly according to the original planned path; low-priority aircraft can slow down in advance to wait or use the second best preselected path (a shortest path that avoid the conflict area and reach the end point). At the same time, the wake interval timeλ needs to be added in the calculation of the waiting time to meet the wake interval criteria for aircraft taxiing at the surface.


### 4.1. Aircraft Taxiing Regulations and Priority Determination

To ensure safer and more efficient airport operations, surface aircraft should follow certain rules when taxiing [17].(1)
The aircraft taxiing or towing on the surface must follow the prescribed or designated route by the surface controller; the taxi speed on the taxiway shall not exceed 50 km/h. After entering the passenger apron and apron, to ensure that it can be stopped at any time, the aircraft can only taxi at a slow speed.(2)
Two or more aircrafts will follow up taxiing. The rear aircraft shall not overtake the front aircraft. The distance between the rear aircraft and the front aircraft shall comply with the minimum separation standard specified by the wake interval: 100 meters from the tail of the taxiing light aircraft (light aircraft: aircraft with a maximum take-off weight of less than 7 tons); 200 meters from the tail of a medium-sized aircraft during taxiing (medium-sized aircraft: aircraft with a maximum take-off weight of 7–136 tons); and 300 meters from the tail of a heavy aircraft during taxi (heavy aircraft: maximum aircraft with a take-off weight greater than 136 tons).The dynamic path optimization of the aircraft that taxi at the surface is based on their conflict relief priority. At present, the research of aircraft surface taxiing mainly adopts the first-come-first-served strategy, which is simple and practicable and reflects the principle of fairness. In view of this, the priority of flights during conflict detection and resolution is set as the priority of aircraft dispatch time (when the dispatch time is the same, the priority is determined by the peak of inbound and outbound flights).


### 4.2. Aircraft Taxiing Head-to-Head Conflict Detection and Resolution

Assuming that the moment when aircraftk1 enters Qi is tiink1 and the moment when it leaves Qi is ti(k1), the moment of aircraft k2 entering Q is tiink2 and the moment when it leaves Qi is tioutk2. If there is a head-to-head conflict between aircraft k1 and k2, the taxiing area Qi is the head-to-head conflict section between aircraft k1 and aircraft k2, and then, the head-to-head conflict time window distribution is shown in Figure 6:Figure 6
Time window for head-to-head conflict.Therefore,(7)tiink2<tioutk1,tioutk2>tiink1.Assuming that the aircraft chooses to wait in place to complete the head-to-head conflict resolution, its waiting time ℎ can be found by(8)h=tioutk1−tiink2+λ.Then, the time of aircraftk2 entering the taxiway area Qi can be updated as(9)tiink2=ti−1outk2+h.The updated aircraft taxiing occupancy time window is shown in Figure7.Figure 7
Update the time window for head-to-head conflict.Assuming that the aircraft chooses to change the path to complete the conflict resolution, the aircraft is rescheduled for the suboptimal preselected path and the time window of the aircraft’s taxiing area over the entire taxiway is updated.


### 4.3. Aircraft Taxiing Cross-Conflict Detection and Resolution

Assume that the moment of aircraftk1 entering Qi is tiink1 and the moment of aircraft k2 entering Qi is tiink2. If there is a cross-conflict between aircraft k1 and k2, the taxiing area Qi is the cross-conflict section of aircraft k1 and aircraft k2; then, the cross-conflict time window distribution is shown in Figure 8.Figure 8
Time window for cross-conflict.Then,(10)tiink2−tiink1<λ.Assuming that the aircraft chooses to wait in place to complete the cross-conflict resolution, its waiting timeh can be found by(11)h=tiink2−tiink1+λ.Then, the time of aircraftk2 entering the taxiway area Qi can be updated as(12)tiink2=ti−1outk2+h.The updated taxiway occupancy time window is shown in Figure9.Figure 9
Update time window for cross-conflict.Assuming that the aircraft chooses to change the path to complete the conflict resolution, the aircraft is rescheduled for the suboptimal preselected path and the time window of the aircraft’s taxiing area over the entire taxiway is updated.


### 4.4. Aircraft Taxiing Rear-End Conflict Detection and Resolution

Assuming that the moment when aircraftk1 enters Qi is tiink1 and the moment when it leaves Qi is tioutk1, the moment of aircraft k2 entering Qi is tiink2 and the moment when it leaves Qi is ti(k2). If there is a rear-end conflict between aircraft k1 and k2, the taxiing area Qi is the rear-end conflict section between aircraft k1 and aircraft k2, then the rear-end conflict time window. Distribution is shown in Figure 10.Figure 10
Time window for rear-end conflict.Then,(13)tiink2≥tiink1,tioutk2≤tioutk1.Assuming that the aircraft chooses to wait in place to complete the rear-end conflict resolution, its waiting timeh can be found by(14)h=tioutk1−tioutk2+λ.Then, the time of aircraftk2 entering the taxiway area Qi can be updated as(15)tiink2=ti−1outk2+h.The updated taxiway occupancy time window is shown in Figure11.Figure 11
Update time window for rear-end conflict.Assuming that the aircraft chooses to change the path to complete the conflict resolution, the aircraft is rescheduled for the suboptimal preselected path, and the time window of the aircraft’s taxiing area over the entire taxiway is updated.


### 4.5. Plane Taxiing Path with Aircraft Taxiing after the Conflict Is Resolved

If there aren aircrafts operating at the airport surface, the time delay of taxiing aircraft k conflict with other aircrafts is defined as σk:(16)σk=∑h.The objective of the dynamic path planning method is to minimize the total taxiing time of the surface operating aircraft by making the low-priority aircraft wait or change their paths to deconflict. Thus, its objective function is as follows:(17)Z=te−t0+σk,(18)t0≥ETOP,(19)te≤ETOD,where t0 is the time when the aircraft enters the starting taxiing section and te is the time when the aircraft leaves the ending taxiing section. Equation (18) is the moment when the aircraft starts taxiing not earlier than the expected launch time, and equation (19) is the moment when the aircraft ends taxiing not later than the expected departure time ETOD.


## 4.1. Aircraft Taxiing Regulations and Priority Determination

To ensure safer and more efficient airport operations, surface aircraft should follow certain rules when taxiing [17].(1)
The aircraft taxiing or towing on the surface must follow the prescribed or designated route by the surface controller; the taxi speed on the taxiway shall not exceed 50 km/h. After entering the passenger apron and apron, to ensure that it can be stopped at any time, the aircraft can only taxi at a slow speed.(2)
Two or more aircrafts will follow up taxiing. The rear aircraft shall not overtake the front aircraft. The distance between the rear aircraft and the front aircraft shall comply with the minimum separation standard specified by the wake interval: 100 meters from the tail of the taxiing light aircraft (light aircraft: aircraft with a maximum take-off weight of less than 7 tons); 200 meters from the tail of a medium-sized aircraft during taxiing (medium-sized aircraft: aircraft with a maximum take-off weight of 7–136 tons); and 300 meters from the tail of a heavy aircraft during taxi (heavy aircraft: maximum aircraft with a take-off weight greater than 136 tons).The dynamic path optimization of the aircraft that taxi at the surface is based on their conflict relief priority. At present, the research of aircraft surface taxiing mainly adopts the first-come-first-served strategy, which is simple and practicable and reflects the principle of fairness. In view of this, the priority of flights during conflict detection and resolution is set as the priority of aircraft dispatch time (when the dispatch time is the same, the priority is determined by the peak of inbound and outbound flights).


## 4.2. Aircraft Taxiing Head-to-Head Conflict Detection and Resolution

Assuming that the moment when aircraftk1 enters Qi is tiink1 and the moment when it leaves Qi is ti(k1), the moment of aircraft k2 entering Q is tiink2 and the moment when it leaves Qi is tioutk2. If there is a head-to-head conflict between aircraft k1 and k2, the taxiing area Qi is the head-to-head conflict section between aircraft k1 and aircraft k2, and then, the head-to-head conflict time window distribution is shown in Figure 6:Figure 6
Time window for head-to-head conflict.Therefore,(7)tiink2<tioutk1,tioutk2>tiink1.Assuming that the aircraft chooses to wait in place to complete the head-to-head conflict resolution, its waiting time ℎ can be found by(8)h=tioutk1−tiink2+λ.Then, the time of aircraftk2 entering the taxiway area Qi can be updated as(9)tiink2=ti−1outk2+h.The updated aircraft taxiing occupancy time window is shown in Figure7.Figure 7
Update the time window for head-to-head conflict.Assuming that the aircraft chooses to change the path to complete the conflict resolution, the aircraft is rescheduled for the suboptimal preselected path and the time window of the aircraft’s taxiing area over the entire taxiway is updated.


## 4.3. Aircraft Taxiing Cross-Conflict Detection and Resolution

Assume that the moment of aircraftk1 entering Qi is tiink1 and the moment of aircraft k2 entering Qi is tiink2. If there is a cross-conflict between aircraft k1 and k2, the taxiing area Qi is the cross-conflict section of aircraft k1 and aircraft k2; then, the cross-conflict time window distribution is shown in Figure 8.Figure 8
Time window for cross-conflict.Then,(10)tiink2−tiink1<λ.Assuming that the aircraft chooses to wait in place to complete the cross-conflict resolution, its waiting timeh can be found by(11)h=tiink2−tiink1+λ.Then, the time of aircraftk2 entering the taxiway area Qi can be updated as(12)tiink2=ti−1outk2+h.The updated taxiway occupancy time window is shown in Figure9.Figure 9
Update time window for cross-conflict.Assuming that the aircraft chooses to change the path to complete the conflict resolution, the aircraft is rescheduled for the suboptimal preselected path and the time window of the aircraft’s taxiing area over the entire taxiway is updated.


## 4.4. Aircraft Taxiing Rear-End Conflict Detection and Resolution

Assuming that the moment when aircraftk1 enters Qi is tiink1 and the moment when it leaves Qi is tioutk1, the moment of aircraft k2 entering Qi is tiink2 and the moment when it leaves Qi is ti(k2). If there is a rear-end conflict between aircraft k1 and k2, the taxiing area Qi is the rear-end conflict section between aircraft k1 and aircraft k2, then the rear-end conflict time window. Distribution is shown in Figure 10.Figure 10
Time window for rear-end conflict.Then,(13)tiink2≥tiink1,tioutk2≤tioutk1.Assuming that the aircraft chooses to wait in place to complete the rear-end conflict resolution, its waiting timeh can be found by(14)h=tioutk1−tioutk2+λ.Then, the time of aircraftk2 entering the taxiway area Qi can be updated as(15)tiink2=ti−1outk2+h.The updated taxiway occupancy time window is shown in Figure11.Figure 11
Update time window for rear-end conflict.Assuming that the aircraft chooses to change the path to complete the conflict resolution, the aircraft is rescheduled for the suboptimal preselected path, and the time window of the aircraft’s taxiing area over the entire taxiway is updated.


## 4.5. Plane Taxiing Path with Aircraft Taxiing after the Conflict Is Resolved

If there aren aircrafts operating at the airport surface, the time delay of taxiing aircraft k conflict with other aircrafts is defined as σk:(16)σk=∑h.The objective of the dynamic path planning method is to minimize the total taxiing time of the surface operating aircraft by making the low-priority aircraft wait or change their paths to deconflict. Thus, its objective function is as follows:(17)Z=te−t0+σk,(18)t0≥ETOP,(19)te≤ETOD,where t0 is the time when the aircraft enters the starting taxiing section and te is the time when the aircraft leaves the ending taxiing section. Equation (18) is the moment when the aircraft starts taxiing not earlier than the expected launch time, and equation (19) is the moment when the aircraft ends taxiing not later than the expected departure time ETOD.


## 5. Example Application

Take Xi’an Xianyang International Airport as an example. Here, the model and improvedA∗ algorithm are used to calculate the aircraft planning taxiing path. The airport has two parallel runways and three terminals. The airport structure simplified diagram is shown in Figure 12.Figure 12
Xi’an Xianyang airport structure simplified diagram.Taking into account the particularity of the epidemic, the flight data of Xi’an Xianyang Airport from 15:16:00 to 15:28:20 on May 2nd, 2019, is used for simulation calculation. The taxi schedule of flights is given in Table 1. Assume the surface taxi speed of the aircraft: 5 m/s for the straight section and 4 m/s for the turning section. The number of preselected paths P of the aircraft is set to 3, and the algorithm will plan out 3 preselected taxi paths with the shortest distance for each aircraft.Table 1
Flight taxi schedule.
Flight number
Arrival/departure
Starting point
Terminal point
NS8264
Arrival
6
165
HU7577
Departure
166
137
MU4405
Arrival
154
167
MU5569
Departure
168
1
HU7817
Departure
169
1
MU2158
Arrival
7
170The calculation results of the three preselected taxi paths and their corresponding taxi distances for the six aircraft are given in Table2.Table 2
Aircraft preselected taxi path and corresponding taxi distance.
Flight number
Preselected taxi path
Taxi distance
NS8264
6 ⟶ 12 ⟶ 16 ⟶ 33 ⟶ 32 ⟶ 31 ⟶ 47 ⟶ 60 ⟶ 165
2853.12
NS8264
6 ⟶ 12 ⟶ 16 ⟶ 33 ⟶ 32 ⟶ 48 ⟶ 61 ⟶ 60 ⟶ 165
2853.14
NS8264
6 ⟶ 12 ⟶ 16 ⟶ 33 ⟶ 32 ⟶ 31 ⟶ 30 ⟶ 46 ⟶ 59 ⟶ 165
3130.13
HU7577
166 ⟶ 100 ⟶ 99 ⟶ 98 ⟶ 97 ⟶ 96 ⟶ 95 ⟶ 105 ⟶ 118 ⟶ 137
2341.62
HU7577
166 ⟶ 100 ⟶ 109 ⟶ 108 ⟶ 107 ⟶ 106 ⟶ 105 ⟶ 118 ⟶ 137
2341.63
HU7577
166 ⟶ 100 ⟶ 109 ⟶ 124 ⟶ 123 ⟶ 122 ⟶ 121 ⟶ 120 ⟶ 119 ⟶ 118 ⟶ 137
2424.64
MU4405
154 ⟶ 155 ⟶ 156 ⟶ 134 ⟶ 133 ⟶ 132 ⟶ 131 ⟶ 130 ⟶ 129 ⟶ 128 ⟶ 127 ⟶ 126 ⟶ 125 ⟶ 124 ⟶ 109 ⟶ 100 ⟶ 166 ⟶ 91 ⟶ 167
3254.05
MU4405
154 ⟶ 155 ⟶ 156 ⟶ 134 ⟶ 113 ⟶ 112 ⟶ 111 ⟶ 110 ⟶ 109 ⟶ 100 ⟶ 166 ⟶ 91 ⟶ 167
3260.062
MU4405
154 ⟶ 155 ⟶ 156 ⟶ 134 ⟶ 133 ⟶ 132 ⟶ 131 ⟶ 130 ⟶ 129 ⟶ 111 ⟶ 102 ⟶ 101 ⟶ 100 ⟶ 166 ⟶ 91 ⟶ 167
4033.02
MU5569
168 ⟶ 101 ⟶ 100 ⟶ 99 ⟶ 98 ⟶ 97 ⟶ 78 ⟶ 75 ⟶ 73 ⟶ 42 ⟶ 23 ⟶ 22 ⟶ 1
4201.19
MU5569
168 ⟶ 101 ⟶ 100 ⟶ 99 ⟶ 98 ⟶ 97 ⟶ 78 ⟶ 75 ⟶ 73 ⟶ 42 ⟶ 41 ⟶ 22 ⟶ 1
4290.13
MU5569
168 ⟶ 101 ⟶ 110 ⟶ 109 ⟶ 108 ⟶ 97 ⟶ 78 ⟶ 75 ⟶ 73 ⟶ 42 ⟶ 23 ⟶ 22 ⟶ 1
4399.34
HU7817
169 ⟶ 61 ⟶ 48 ⟶ 32 ⟶ 31 ⟶ 30 ⟶ 29 ⟶ 28 ⟶ 27 ⟶ 26 ⟶ 25 ⟶ 24 ⟶ 23 ⟶ 22 ⟶ 1
3083.71
HU7817
169 ⟶ 61 ⟶ 48 ⟶ 47 ⟶ 46 ⟶ 45 ⟶ 44 ⟶ 43 ⟶ 42 ⟶ 41 ⟶ 22 ⟶ 1
3172.65
HU7817
169 ⟶ 61 ⟶ 48 ⟶ 47 ⟶ 46 ⟶ 45 ⟶ 44 ⟶ 43 ⟶ 42 ⟶ 23 ⟶ 22 ⟶ 1
3676.64
MU2158
7 ⟶ 13 ⟶ 17 ⟶ 36 ⟶ 35 ⟶ 34 ⟶ 33 ⟶ 32 ⟶ 48 ⟶ 61 ⟶ 60 ⟶ 165 ⟶ 59 ⟶ 170
3628.42
MU2158
7 ⟶ 13 ⟶ 17 ⟶ 36 ⟶ 35 ⟶ 34 ⟶ 33 ⟶ 32 ⟶ 31 ⟶ 47 ⟶ 60 ⟶ 165 ⟶ 59 ⟶ 170
3628.42
MU2158
7 ⟶ 13 ⟶ 17 ⟶ 36 ⟶ 35 ⟶ 34 ⟶ 33 ⟶ 32 ⟶ 31 ⟶ 30 ⟶ 46 ⟶ 59 ⟶ 170
3628.42To further analyze the aircraft taxi path planning method after conflict resolution, select the preselected path with the shortest taxi distance in the preselected trajectory, calculate the time window occupied by the taxiway, perform conflict detection and relief, and finally generate the conflict-free and shortest taxi path. The taxiway structure model here covers the runway, parking stands, and main taxiway areas of Xi’an Xianyang Airport, including 218 areas. The time window occupied by the taxiway area of the aircraft during the study period is shown in Figure13. The abscissa in the figure represents the taxi time, the ordinate represents the area number of the taxiing road segment, and the rectangle is the time window distribution of the preselected taxiing path of the aircraft in the area of each road segment.Figure 13
The area occupied the time window of the preselected route of the aircraft.From the figure, if taxiing along the preselected path, aircraft HU7577 and HU7817 will have a rear-end collision in area 48, and aircraft MU4405 and MU5569 will have a cross-collision in area 66. According to the priority regulations, adjust the taxi paths of the low-priority aircrafts HU7817 and MU5569. After adjustment, the taxi paths of the two aircrafts are shown in Figures14(a) and 14(b).Figure 14
(a) Aircraft MU5569 area occupation time window before and after conflict resolution. (b) Aircraft HU7817 area occupation time window before and after conflict resolution.
(a)
(b)From the figure, the initial planned trajectories of aircrafts MU5569 and HU7817 are both changed. Since the total taxiing time after waiting is less than that after changing the path, aircraft MU5569 enters area 67 after waiting in area 66 and continues to taxi on the initial planned path. Aircraft GS7657 enters area 46 after waiting in area 48 and continues to taxi on the initial planned path.In addition, the planned paths of the other four aircrafts should not be disturbed by the deconfliction measures. The time change before and after the aircraft dynamic planning reaches the target point is given in Table3, Due to conflict resolution, the time of aircrafts MU5569 and HU7817 reaching the target point increases, while the rest of the aircraft not affected remain unchanged, so that the conflict resolved does not affect the operation of other taxiing.Table 3
Changes in taxi time before and after the aircraft taxi path planning (unit: second).
Aircraft
Initial taxi time
Taxi time after conflict resolution
Amount of change
NS8264
427.83
427.83
0
HU7577
294.21
294.21
0
MU4405
467.51
467.51
0
MU5569
511.98
541.57
29.59
HU7817
367.28
396.43
29.15
MU2158
506.64
506.64
0The waiting time, total taxiing time, total taxiing distance, and the number of conflicts are compared based on static taxiing path and dynamic path planning, respectively. As given in Table3, in the results of the static taxiing path, the aircraft is requested to taxiing according to the shortest taxiing path without considering the conflicts caused to other aircrafts at the surface in the actual operation. In this example, there are two conflict points, and the dynamic path planning model finally plans a conflict-free taxiing path with the shortest taxiing time for the six aircraft in the study period.Compare the waiting time, total taxi time, total taxi distance, and number of conflicts before and after conflict resolution. As given in Table4, in the preselected taxi path results, the aircraft is requested to taxi along the shortest taxi path, without considering the actual operation. Conflict is caused by other aircrafts on the scene. In this example, there are two conflict points. After the conflict is resolved, the time window model is used to finally plan a conflict-free and shortest taxi path for the six aircraft in the study period.Table 4
Comparison of the results of taxi path planning before and after conflict resolution.
Waiting time (s)
Total taxi time (s)
Total taxi distance (m)
Number of conflicts
Preselected taxi path
0
2634.18
19225.52
2
Taxi path after conflict resolved
58.74
2575.44
19225.52
0


## 6. Conclusion

Through the study of the aircraft surface taxiing path, the airport surface structure model was established, the aircraft surface taxiing path planning model was constructed, and the improvedA∗ algorithm was used to solve the P preselected paths with the shortest total taxi distance of the aircraft. According to the calculation results of the preselected path, the shortest taxi path is selected to calculate the time window occupied by the aircraft on the taxiing section, and the conflict of the time window occupied by the taxiing area is detected. According to the taxiing rules of the aircraft, the selection is based on the priority of comparison, wait or change the route to resolve the taxi conflict, generate a conflict-free taxi route for the aircraft, and update the preselected route time window. The calculation results of the calculation examples show that the use of the conflict resolution method in this study can further reduce the total taxi time of the aircraft operating on the surface, significantly reduce the number of aircraft conflicts, and ensure the safety of airport operations. In the research process, the A∗ algorithm was used to calculate the shortest taxi path of the 6 flights. Although the A∗ algorithm is more accurate, the calculation efficiency is low. Therefore, it is not easy to use the A∗ algorithm when the number of flights is large, and a more appropriate algorithm should be selected for the solution. At the same time, it is assumed here that the taxi speed of the 6 flights is 5 meters per second in the straight section and the taxi speed in the turning section is 4 meters per second. When the number of flights is large, the taxi speed of the flight in the straight section and the turning section will be different. The deficiencies of these considerations also need to be improved in the follow-up research.



---

*Source: 9951206-2021-10-05.xml*