，，，

1.Civil Aviation Flight Wide Area Surveillance and Safety Control Technology Key Laboratory，Civil Aviation University of China，T ianjin 300300，P.R.China；

2.North China Air Traffic Management Bureau，Civil Aviation Administration of China，Beijing 100000，P.R.China；

3.Tianjin Air Traffic Management Bureau，Civil Aviation Administration of China，Tianjin 300300，P.R.China

Abstract:Most of the traditional taxi path planning studies assume that the aircraft is in uniform speed，and the optimization goal is the shortest taxi time.Although it is easy to solve，it does not consider the changes in the speed profile of the aircraft when turning，and the shortest taxitime does not necessarily bring the best taxifuel consumption.In this paper，the number of turns is considered，and the improved A*algorithm is used to obtain the P static paths with the shortest sum of the straight-line distance and the turning distance of the aircraft as the feasible taxi paths.By balancing taxitime and fuel consumption，a set of Pareto optimal speed profiles are generated for each preselected path to predict the 4-D trajectory of the aircraft.Based on the 4-D trajectory prediction results，the conflict by the occupied time window in the taxiing area is detected.For the conflict aircraft，based on the priority comparison，the waiting or changing path is selected to solve the taxiing conflict.Finally，the conflict free aircraft taxiing path is generated and the area occupation time window on the path is updated.The experimental results show that the total taxidistance and turn time of the aircraft are reduced，and the fuel consumption is reduced.The proposed method has high practical application value and is expected to be applied in real-time air traffic control decision-making in the future.

Key words：air transportation；trajectory planning；heuristic algorithm；taxitime；taxifuel consumption

0 Introduction

With the rapid development of air transportation，the number of flights at China’s major airports has continued to increase.The traffic in the flight area of the airport is complicated，the taxiing time of the aircraft is too long，and the workload of the controller increases，which seriously threatens the safety of operation.Due to congestion caused by aircraft taxiing conflict or ground waiting，each additional minute of taxi time will increase fuel consumption by 10—20 kg［1-2］，resulting in an increase in aircraft emissions and affecting air quality around the airport.In order to realize the sustainable development of air transportation，the use of scientific and effective taxi path planning methods can not only reduce taxi time and fuel consumption，but also ensure the reliability and safety of actual airport operations.

Many scholars have studied the taxi path planning and 4-D trajectory prediction of aircraft at the airport，and obtained a series of research results.A taxi 4-D trajectory is a time-based taxi route that includes an expected location（x，ycoordinates or latitude，longitude）at all time（t），with an allowable deviation from the expected position.The allowable deviation defines the degree of freedom with which an aircraft can deviate from the expectedx，ylocation at any time and still be considered in conformance with the 4-D trajectory［3］.In 2014，Ravizzaet al.［4］studied the path planning of aircraft at the airport surface con-sidering time and fuel consumption，and introduced a sequence diagram-based algorithm to solve the problem.In 2015，Weiszer et al.［5］proposed the airport surface motion database for the high calculation time requirements of existing speed configuration optimization methods，and effectively separated path planning（routing and scheduling）and speed profile generation modules through pre-calculation to avoid the same repeated optimization of taxiway.Moreover，Weiszer et al.［6］used a multi-objective optimization method to solve the comprehensive optimization problem combining runway scheduling and ground motion problems.The proposed evolutionary algorithm is based on an improved congestion distance，taking into account delay costs and fuel prices.In 2016，Liet al.［7］used support vector machines to perform position classification and trajectory determination of taxiing aircraft，and applied data mining technology to predict aircraft taxiing time，determine taxiing hotspots and conflict areas.In 2016，Chen et al.［8］proposed the concept of active routing，which combined 4-D trajectory routing scheduling into a multi-objective optimization problem，and finally generated a more environmentally friendly and costeffective 4-D trajectory.In 2017，Chen et al.［9］considered that the route and timetable generated by taxi time prediction were not flexible.Based on multi-objective fuzzy rules and historical aircraft taxi data，they quantified the uncertainty of the route and timetable generated by taxi time prediction.In 2017，Wang et al.［10］discretized the taxi speed based on the taxiing motion model of the aircraft，and used amultiobjective immune optimization method to study the specific relationship between the taxi speed and fuel consumption.In 2018，Zhang et al.［11］proposed an online speed profile generation method，which simplified the non-linear optimization model into three easyto-handle composition problems and further optimized to produce an improved fuel efficiency speed profile.In 2018，Li et al.［12］considered the aircraft taxi time and the number of turns to establish an aircraft taxi path optimization model at the airport with the shortest taxi time as the goal.The genetic algorithm was used to solve the model.

It can be seen from the research review that the taxi path planning has achieved fruitful results in both theoretical research and practical application.Traditional studies mostly assume that the fuel consumption of aircraft taxiing will decrease with the reduction of taxi time，and path planning is based on the shortest taxi time.However，due to the existence of the turning section，the aircraft needs more power to accelerate and decelerate greatly，and the pure pursuit of a shorter time will increase fuel consumption.Although precise algorithms such as multi-objective optimization take full consideration of various scene constraints，such algorithm models are complex and computationally intensive，and it is generally difficult to obtain the optimal solution in an acceptable time.Therefore，this article comprehensively considers the aircraft’s taxiing distance and the number of turns，and plans the shortest path for the aircraft taxiing.Based on this，a multi-target speed profile model is established to weigh the time and fuel consumption during taxiing.Each path generates a more accurate speed profile that takes into account time and fuel efficiency，obtaining aircraft taxiing 4-D trajectory.The concept of maximum theoretical speed is added to the heuristic search process，which further simplifies the calculation amount.Compared with other complicated algorithms that consider multiple factors，the calculation speed is faster and has higher practical value.

1 Aircraft Taxi Shortest Path Planning

1.1 Airpor t sur face str ucture modeling

The airport movement area includes the runway，taxiway and apron system.There are various types of intersections，which are composed of straight and curved roads interwoven to varying degrees.Therefore，the network structure of the airport movement area is redefined to simplify the connection relationship.Taking Xi’an Xianyang International Airport as an example，the simplified diagram of the airport movement area structure is shown in Fig.1.The letters and the combination of letter and number in Fig.1 represent the names of the taxiway.

Fig.1 Simplified diagram of movement area structure of Xi’an Xianyang International Airport

After simplifying the structure of the airport surface，the network connection relationship of the airport surface system can be clearly and intuitively understood.But it is not applicable to the design and solution processing of path planning algorithms.To this end，the scene structure is represented abstractly asG=（V，E）in the form of an undirected graph.Vrepresents the set of nodes in the taxiway system，which is composed of the intersections between taxiways，the intersections between taxiways and runways，parking spots，two ends of the runway，etc；Erepresents the set of edges connecting various nodes in the taxiway system，and is composed of taxiway sections between adjacent nodes in the taxiway system.

In this paper，the adjacency matrix is used to represent the connection relationship between nodes and the directed graph model is transformed into a matrix representation.Suppose there aremnodes in the airport surface structure diagram，which are represented by a matrixCofm×m，and define the elementCijof the matrix.

In the path planning，the nodes of the scene road network and the taxiway sections must consider their attributes，and the attributes of the scene road network are defined according to the following requirementsE-Rrelationship model：

（1）Road network（node number，path number）.

（2）Path node（node number，x-coordinate，ycoordinate）.Directional segment of the path（path number，start point，end point，distance，taxiway to which it belongs，wingspan restriction，running direction，disable or fault）.

When planning a route，the aircraft must consider its attributes.The attributes of the aircraft identification are：（1）Aircraft call sign；（2）aircraft type；（3）aircraft wingspan；（4）current taxi speed of the aircraft.

1.2 Aircraft taxi static path planning model

For any aircraftkin the aircraft setF={f1，f2，…，f n}，the system generatesPpreselected paths for it，and itszth preselected taxi pathL kz(1≤k≤n，1≤z≤p)is composed of a set of ordered nodes{N1，N2，…，N q}.There areMnodes in the airport network model， whereq≤M；N i，N j，N r∈V；（N i，N j）∈E；i=1，2，…，q；j=1，2，…，q.The used variables are：x ij=1，indicating that aircraftkpasses through nodeN iof the taxiway and then taxis straight to nodeN j，otherwisex ij=0；d ijis the length of the straight taxiway road section（N i，N j）in the taxiway system；tijis the taxi time of the aircraft on the straight taxiway（N i，N j）；Rr=1 indicates that the aircraftkturns when passing through the taxiway nodeN r，otherwiseRr=0；d ris the turning length of the aircraftkat the nodeN rduring taxiing of the scene；tris the turning and taxiing time of the aircraft at the nodeN r.Then the total taxidistanceDof the aircraft can be obtained by

According to Ref.［11］，the cosine theorem is used to solve the aircraft steering angle.The taxiing process of the aircraft during the turn is shown in Fig.2.

Fig.2 Aircraft turning section taxiing process

As shown in Fig.2，because the scene topology diagram is simplified，the scene aircraftkinitially taxis at nodeN u，and then continuously taxis through the two nodesN gandN w.In reality，the aircraft has a turn length at pointN g，and the aircraft started to taxi at pointN u，and started to turn from pointN r.After the turn at pointN f，it continued to taxi toN w.Then the taxi distance of this road section is actually the sum of the straight line lengthd ur，the turning lengthd r，and the straight line lengthd fw.

1.3 Path planning model solution

The aircraft path taxiing path planning model established in this paper has many variables，and some equations are non-linear，so traditional algorithms are difficult to solve.In order to solve this problem，the Bellman Ford algorithm and the A*algorithm are combined to solve the model.The model solving the algorithm designed in the paper is as follows：The goal is to find the path with the shortest taxiing distance ofPaircrafts.Letg（n）be the slip distance from the start of the path to the current noden，h（n）the shortest slip distance from the current node to the target node，andf（n）the total slip distance of the aircraft from the start node of the path to the target node.Among them，h（n）is executed before the algorithm is executed and pre-processed.All road sections of the airport are reversed，and the Bellman Ford algorithm is executed from the punctuation point as the starting point to find the shortest taxi distance from the target point to all points.The value isH（n）at this point.

2 Modeling Taxi Time Profile Considering Time and Fuel

Based on thePtaxi paths obtained from the shortest path planning，the purpose of multi-objective speed profile modeling is to generate a set of unobstructed speed curves satisfying the time and fuel optimal for each path，which is called the Pareto solution setY i.Therefore，the 4-D trajectory of the aircraft at the airport surface taxiing is obtained，as shown in Fig.3.The straight segment taxi time istur，the turn segment taxi time istr，the straight segment taxi time istfw.They are the time corresponding to the distancesd ur，d randd fw.

Fig.3 Partial multi-target taxiing profile

2.1 Air cr aft taxi time modeling

2.1.1 Discretization of aircraft taxi trajectory

During the taxiing of an aircraft，its taxiing speed is continuously changing.In order to reduce the computational complexity and calculation time of the algorithm，it is necessary to discretize the taxi speed and taxi trajectory.

During the aircraft’s taxiing process，the speed curve on each link(N i，N j)can be subdivided into four parts，as shown in Fig.4.The length of each part represents the taxiing distance of the aircraft in different operating phases，and the taxiing speed of the aircraft also changes according to the operating status.

Fig.4 A speed profile with four phases

In the first stage，the aircraft performs uniform acceleration motion，the accelerationa1is a constant value，and the taxi speed is accelerated fromv0tov1.The value ofv1depends on the lengthd1of the first stage.

The aircraft maintains a speedv1，the duration of which depends on the lengthd2of the second phase.

In the third and fourth stages，the aircraft performs deceleration.The difference between these two stages is that the fourth stage needs to be decelerated fromv3（The final speed of the third stage of the aircraft）tov4in the shortest time at the maximum deceleration ratea4=amax.The length of the third stage isd3=d-d1-d2-d4，andv3can be determined bya4，v4，andd4.

Therefore， there are four variablesa1，d1，d2，d4for each link(N i，N j).By calculating the values of four variables，the speed curve and objective function value of the link can be obtained.

2.1.2 Taxi time model

For each link(N i，N j)，the speed curve of the link can be determined through four decision variablesa1，d1，d2，d4and the time for taxiing with the speed curve can be determined as

whereTT ijis the taxi time used by the aircraft on the link；andtsthe time consumption of each stage of the speed curve，s=1，2，3，4.

For the complete taxi pathL kzof aircraftk，which is composed of multiple links，the objective functiong1of taxitime can be further expressed as

2.2 Aircraft taxiing fuel consumption modeling

The discrete aircraft speed profile includes four phases：acceleration，constant speed，braking，and emergency braking.The thrust level of the aircraft in the acceleration and constant speed segments is obtained according to Ref.［8］，assuming that the thrust level in the braking and emergency braking phasesε=5%，and the turning phaseε= “7%” .According to the fuel flow rate in the ICAO emission database and linear interpolation，the fuel flow ratefscorresponding to the thrust level at each stage in the speed profile is obtained by linear interpolation.Then for each link(N i，N j)，the fuel consumption of taxiing at this speed curve can be determined as

wherefsis the fuel flow rate at each stage of the speed curve；tsthe time consumption of each stage of the speed curve；s=1，2，3，4.

For the complete taxiing pathL kzof aircraftk，which is composed of multiple links，the objective function of taxiing fuel consumptiong2can be further expressed as

2.3 Restr ictions

For each link(N i，N j)，the taxi speed profile of aircraftkis mainly determined by four decision variablesa1，d1，d2，d4.Decision variables are calculated sequentially，and once determined，it will be used to further calculate the next decision variable.Due to the need to integrate the best speed curve generation method into the routing and scheduling module to provide online decision making，many decision variables may result in failure to meet time requirements.In view of this，the following assumptions are made on the problem of multi-target velocity profile generation：

（1）The aircraft accelerates with the maximum accelerationamaxto minimize the acceleration time.

（2）Based on the ICAO emission database method，the fuel consumption during braking is equivalent to the fuel combustion during constant speed.Because braking does not save fuel，the aircraft’s constant speed travel distanced2is maximized.Using the maximum deceleration，the driving distanced4during the rapid braking phase when decelerating fromv1tov4can be expressed by

Based on this assumption，the only undecided decision variable is the acceleration distanced1，and heuristic search method is used to search for the best value ofv1within the allowable range to determined1.

Before searching forv1，the maximum theoretical speedvtheoryis added，and it is determined by the lengthd ijof the link(N i，N j)，i.e.

whered ijis the length of the link(N i，N j)；d1the acceleration distance of the aircraft in the first stage；vtheorythe maximum theoretical speed；v0the initial speed on the link(N i，N j)；andv tthe final speed on the link(N i，N j).

There are two situations：

（1）vtheory≥vmax

At this time，it is shown that the link is long enough，the aircraft satisfies the acceleration ofa1tovmax，and then decelerates to the final speedv tof the link(N i，N j).Search for thebest valueofv1withinvmax.

（2）vtheory＜vmax

At this point，it is shown that the link length is not enough to accelerate tovmax.The aircraft will accelerate tovtheorybya1，and then decelerate byvmaxto meet the situation where the link end reachesv t.Search for the best value ofv1withinvtheory.

2.4 Multi-objective velocity profile model solution

This paper uses a heuristic search method to search the decision variablev1，weighs the taxi time and fuel consumption，and finally generates a multitarget speed profile for the selected path.The specific search steps are as follows：

（1）Input the segmented pathL kz.

（2）Traverse weightsu1，u2：

u1is from 0 to 1 in step of 1/12，i.e.

（3）Corresponding to the determined weight，take the link(N i，N j)on the pathL kz：

①Straight link

Speed valuev1=[vmin，vmax，1]，a total of 12 schemes.

Introducevtheoryto traverse the speed value during the acceleration phase.

Corresponding to the determined speedv1，find the taxi timeTT ijand fuel consumptionFF ijof the link(N i，N j)，and solve

Select the correspondingv1when the benefit is the smallest，and use this value to determine the speed profile of the link(N i，N j).

②Turn link

The corresponding speed is 5.14 m/s，and find the cornering benefit value.

（4）Summing the fuel consumptionFF ijand timeTT ijof all links(N i，N j)to obtain the objective function valuesg1，g2.

（5）Speed profile generation of taxipath.

Outputg1，g2.

3 Dynamic Path Planning for Aircraft Taxiing

Due to the complexity of the airport surface taxiway network，and the uncertainty of taxiway operation and taxiway operating rules，the dynamic path planning part divides the airport surface area.According to the 4-D trajectory prediction model，the area occupied by each taxiing trajectory is solved for the time window，and the head-to-head collision，cross-collision and rear-end collision detection are performed for each static preselected path.In order to resolve the conflict，the aircraft must stop waiting or change the path.After release，recalculate its taxiing 4-D trajectory and update the time window of the preselected path.The path with the least total taxi time and total waiting time is taken as the optimal solution for dynamic path planning，and a conflict-free taxi path is planned for the aircraft currently requesting the path［13］.

3.1 Taxiway area division model

Assuming that the taxiway area connection relationship is obtained from the airport network model.And then the taxiway is divided into several non-overlapping areas.Therefore the taxiway area division model is obtained.Finally，the two are superimposed according to the spatial position to obtain a hierarchical taxiway structure model，asshown in Fig.5.

Fig.5 T axiway area division

The conflicts in the taxiway system can be divided into three categories as shown in Fig.6：（1）Head conflict；（2）cross conflict；（3）rear-end conflict.

Fig.6 Taxiconflict

3.2 Aircraft taxi time window

According to the results of path planning，calculate the time when the aircraft enters and leaves each taxiway area，and solves the time window occupied by each area on the taxi path［14-15］.

The time when the aircraftkenters the taxiing areaQiis recorded as(k)，and the time when the aircraftkleaves the taxiing areaQiis recorded as(k).IfQiis the initial taxiing area，the time for the aircraftkto enter the areaQ iis equal to the path planning start timet0.IfQiis not the initial taxiing area，then the time(k)when the aircraftkenters the taxiing areaQiis the time(k)to leave the taxiing area(k).IfQ iis the end taxiing area，the time(k)for the aircraftkto leave the areaQ iis equal to the taxiend timete，which satisfies

Taxi time window vector is a collection of the occupied time window of each area on the planned taxi pathL KZfor the aircraftk.The time windowtw i（k）of the taxiing areaQioccupied by aircraftkcan be defined as a two-tuple of(k)and(k)，i.e.

Therefore，the taxi time window vectorTW(k)of pathLcan be defined as

3.3 Sur face conflict detection and r esolution based on taxi time window

When there is a conflict in the planned trajectory time window of the aircraft，based on the comparison of their priorities，wait or change the route to resolve the taxi conflict.The high-priority aircraft can directly pass through the conflict area on the original planned path.Low-priority aircraft can slow down in advance or take a suboptimal preselected path（the shortest path that does not pass through the conflict zone and reaches the destination）.At the same time，it is necessary to add the safety interval timeλwhen calculating the waiting time to meet the aircraft surface taxi standard.Currently，aircraft surface taxiing studies mainly adopt a first-come，first-served strategy，which is simple and easy to implement and reflect the principle of fairness.The flight priority is based on the aircraft’s take-off time，and the earlier take-off time has the higher priority.

If the aircraft chooses to change the path to complete the conflict resolution，re-arrange the suboptimal pre-selected path for the aircraft and update the time window of the aircraft’s taxiarea on the entire taxi path.If the aircraft chooses to wait in place to complete the conflict resolution，the three conflict resolution methods are as follows：

（1）Head-to-head conflict detection and resolution

If there is a head-on conflict between aircraftk1andk2，and the taxiing areaQ iis the conflict section，there is

Assuming that the aircraft chooses to wait in place to complete the conflict resolution，its waiting timehcan be obtained as

Then the time when the aircraftk2enters the taxiway areaQican be updated to

（2）Cross-conflict detection and resolution

If there is a cross conflict between aircraftsk1andk2，and the taxiing areaQiis the cross conflict section，there is

Assuming that the aircraft chooses to wait in place to complete the cross conflict resolution，the waiting timehcan be obtained as

Then the time of aircraftk2entering the taxiway areaQ ican be updated to

（3）Rear-end conflict detection and resolution

If collision occurs between aircraftsk1andk2，and the taxiing areaQ iis the rear end section，there is

Assuming that the aircraft chooses to wait in place to complete the rear-end collision resolution，its waiting timehcan be obtained as

Then the time of aircraftk2entering the taxiway areaQ ican be updated to

3.4 Dynamic path planning and solution

If there are a total ofnaircraft operating on the scene，the waiting time of the aircraftk，due to conflict with other aircraft when taxiing，is defined as

By making low-priority aircraft wait or change paths to resolve conflicts，the goal of the dynamic path planning method proposed in this paper is to minimize the total taxi timeZof surface-operating aircraft.Its objective function is

where ETOP is the time when the aircraft starts taxiing is not earlier than the expected push-back time.ETOD is the time when the aircraft ends taxi is no later than the estimated take-off time.

4 Example Analysis

4.1 Aircr aft taxi shortest path generation

（1）Experimental settings

This paper takes the ground taxi system of Xi’an Xianyang International Airport as an example，and uses the A*algorithm to optimize the model.The airport has three terminals and two parallel runways.The flight data of the airport on April 2nd，2019 from 14：00：00 to 14：10：55 are used for simulation calculation.The taxi schedule of the flight is shown in Table 1.Plan three pre-selected taxi paths for each aircraft according to their respective flight plans，that is，the number of pre-selected pathsP=3.

Table 1 Flight taxi schedule

（2）Simulation results

The system gives the feasible taxi path of each aircraft，and the taxi path length and number of turns of taxiing from the starting node to the target node according to this path.The pre-selected path and time for aircraft HU 7869 are shown in Table 2.

Table 2 Pre-selected path and time for aircraft HU7869

As can be seen from Table 2，the taxi path planning system considers the number of turns，and provides three different pre-selected paths for each aircraft，which are sorted in increasing order according to the total taxi distance.For a nonsteering node on the aircraft’s taxi path，the aircraft is considered to taxi directly into the node and only take up the node at a certain moment.For a turning node on the aircraft’s taxi path，it is considered that the aircraft takes a certain amount of time to perform a turning operation after taxiing into the node，and then the aircraft taxis out of the node.

Fig.7 shows the aircraft paths with and without considering the turning distance.The red section indicates the section that cannot be driven due to direction restrictions.It can be seen from Fig.7 that the route considering the turning distance reduces the aircraft’s taxinodes and the number of turns.

The taxi data of the six aircraft paths listed in Table 1 with and without considering the turning distance are calculated.The comparison results of taxi path data with and without considering the taxi turning distance for aircraft MU 9025 are shown in Table 3.

Table 3 Taxi data comparison with and without considering turning distance

Comparing the statistical data in Table 3，it can be seen that the total taxi distance and the turning distance of the aircraft are reduced after the path optimization，and the taxi turn distance is the main factor for the reduction of the total taxi distance.

4.2 Multi-target velocity profile generation

（1）Experimental settings

According to ICAO standards，the aircraft’s linear speed does not exceed 30 knot，and the turn taxi speed does not exceed 10 knot.It is assumed that the minimum taxi speedvminof the aircraft is 5.14 m/s and the maximum speedvmaxis 15.43 m/s.Constant speed when turning.The turning speed is set to 5.14 m/s.In order to ensure passenger comfort，the maximum acceleration and deceleration rateamaxis set to 0.98 m/s2.

Based on the obtained shortest taxi path for taxiing，the taxi path is divided into straight sections and turning sections，and the initial speed，final speed and section length information of each section are obtained，as shown in Table 4.

Table 4 HU7869 taxi path segmentation information

Take flight number HU 7869 as an example.The flight is an approaching aircraft.The initial speed is 5.14 m/s and the taxiing speed is 5.14 m/s on the path segment “6-12” to the turning node “12” .At a speed of 5.14 m/s，the taxi is at a constant speed at the turning point “12” ，and then taxis on the path segment “12-16” at a speed of 5.14 m/s to reach the next turning point “16” at a speed of 5.14 m/s. Take the arriving flight HU7869 as an example.It starts to taxi on the path “6-12” to the turning point “12” with an initial speed of 5.14 m/s，and turn at the turning point “12” at a constant speed；taxi on “12-16” at a speed of 5.14 m/s to reach the next turning point “16” ，and turn at the turning point “16” at a constant speed，and so on.Until all paths are skidded，and finally reach the apron and reduce the speed to 0.

（2）Simulation results

The system generated the speed profile of each aircraft on the shortest preselected path，as shown in Fig.8.

Fig.8 Speed profile and trust corresponding to different fuel consumption and time weight settings

It can be seen from Fig.8 that when searching with different weights，the aircraft generates completely different speed profiles，which depends on the decision of the controller in practical applications.Taking the shortest path of flight HU 7869 as an example，the taxi data of the speed profile at different weights are counted.The comparison results are shown in Table 5.It can be seen that when the time weight is the largest，the total taxi time of the generated speed profile is the least，but the fuel consumption is the largest.Otherwise，when the fuel weight is the largest，the total taxi time in the speed profile is the longest，but the fuel consumption is the smallest.When the aircraft is taxiing at different speeds and accelerations on a specified path，the effect on taxi time cost and taxi fuel consumption cost is different.The pursuit of the optimal time cost will inevitably cause excessive fuel consumption，and the taxi time when the fuel consumption is optimal is not really optimal from the perspective of the total taxi cost.Taking the shortest path of flight HU 7869 as an example，the Pareto front of the best speed profile is shown in Fig.9.

Fig.9 Pareto fronti of the best speed profile of flight HU 7869

Table 5 Comparison of taxi data of speed profile of HU7869 at different weights

It can be clearly seen from the experimental results that the optimal taxiing time for the aircraft to complete the designated path does not correspond to the optimal taxiing fuel consumption，and the two are not in direct relationship.Decreasing the taxi time of the aircraft does not mean that the fuel consumption is reduced.On the contrary，reducing the taxi time of the aircraft will change the taxi speed，and frequent acceleration and deceleration will bring more fuel consumption.

4.3 Dynamic path planning and solution of surface taxiing aircr aft

（1）Dynamic path planning example

In order to further verify the dynamic path planning method，the six aircraft select the preselected paths with the shortest taxiing distance（Table 6），and the conflict detection and resolution are carried out based on calculating the taxiway occupation time window.Therefore，the dynamic path planning method generates a collision free taxiing path with the shortest taxiing time for the requesting aircraft.

Table 6 The shor test pr e-selected paths of six air cr afts

（2）Result analysis

The taxiway structure model covers the runways，stands and main taxiway areas of Xi’an Xianyang International Airport.The time window occupied by the taxiway area of the aircraft during the study period is shown in Fig.10.

It can be seen from Fig.10 that if taxiing according to the initial planned track，the aircraft MU 2159 and GS7657 will have a rear-end collision，and the aircraft MU 2769 nd MU 9025 will have a cross-collision.The dynamic path planning method is used to adjust the planned tracks of low priority aircraft MU 9025 and GS7657.The adjustment structure is shown in Fig.11.

It can be seen from Fig.11 that the initial planned tracks of aircraft MU 9025 and GS7657 have changed.Since the total taxiing time after waiting is less than the taxiing time after changing the route，the aircraft MU 9025 will continue taxiing according to the initial planned path after waiting.After waiting，the aircraft GS7657 continues to glide along the original planned path.

Fig.11 Occupied time window before and after conflict resolution of MU9025 and GS7657

In addition，the planned path of the other four aircraft should not be interfered by conflict resolution measures.The time variation of arriving at the target point before and after aircraft dynamic planning is shown in Table 7.Due to the conflict resolution，the time for MU 9025 and GS7657 to reach the target point has been increased，and the remaining aircraft not affected by the dynamic planning have not changed，so as to achieve the purpose that dynamic planning does not affect other surface operations.

Table 7 Change of taxiing time before and after aircraft dynamic planning

5 Conclusions

By using the dynamic path planning method proposed in this paper，the total taxiing time of the aircraft on the surface can be further reduced，the number of aircraft conflicts can be significantly reduced，and the airport operation safety can be guaranteed.Some conclusions are obtained as follows：

（1）A multi-target velocity profile model is established on the basis of generating static preselected paths.

（2）By balancing the taxiing time and fuel consumption of the aircraft，a more accurate multi-target speed profile considering time and fuel efficiency is generated for each path，and the 4-D trajectory of the aircraft taxiing is predicted.

（3）In the optimization search process，the concept of maximum theoretical speed is added to the heuristic search process，which further simplifies the calculation.It is faster than other complicated algorithms that consider multiple factors，which is helpful for real-time air traffic control decisions and has higher practical application value.