# Optimal Airport Surface Traffic Planning Using Mixed-Integer Linear Programming

Authors: P. C. Roling; H. G. Visser
Journal: International Journal of Aerospace Engineering
 (2008)

---

## Abstract

We describe an ongoing research effort pertaining to the development of a surface traffic automation system that will help controllers to better coordinate surface traffic movements related to arrival and departure traffic. More specifically, we describe the concept for a taxi-planning support tool that aims to optimize the routing and scheduling of airport surface traffic in such a way as to deconflict the taxi plans while optimizing delay, total taxi-time, or some other airport efficiency metric. Certain input parameters related to resource demand, such as the expected landing times and the expected pushback times, are rather difficult to predict accurately.  Due to uncertainty in the input data driving the
taxi-planning process, the taxi-planning tool is designed such that it produces solutions that are robust to uncertainty. The taxi-planning concept presented herein, which is based on
mixed-integer
linear programming, is designed such that it is able to adapt to perturbations in these input conditions, as well as to account for failure in the actual execution of surface trajectories. The capabilities of the tool are illustrated in a simple hypothetical airport.


---

## Body

## 1. Introduction

The ability of the air
transport system to
accommodate anticipated future growth in traffic demand
depends, to a significant extent, on the available capacity of the airport
infrastructure. In today’s air transport system, many major airports
are already operating close their maximum throughput capacity. The consequence
of this is that a large number of flights are delayed, which in many cases is
due to congestion on the airport surface. To enlarge airport capacity, runway
and taxiway systems are being expanded. However, as the density and complexity
of airport of surface operations increases, safety concerns related to
operations on the surface are mounting, especially under the condition of low visibility.
Indeed, in the current air traffic control system, aircraft cannot be
sufficiently monitored and guided under low-visibility conditions and, as a
consequence, the theoretically available capacity of an airport cannot
effectively be utilized.In response to these problems, significant
research is being conducted to develop systems to enhance airport ground
movement efficiency while maintaining a high level of safety in all weather
conditions. In this paper, we describe a research effort pertaining to the
development of a surface traffic automation system that will help controllers
to better coordinate surface traffic movements related to arrival and departure
traffic. More specifically, we describe the concept for a taxi-planning support tool that aims to optimize
the sequencing and scheduling of traffic, such as to minimize delays and to
reduce the number of stops during taxiing.Using the envisioned
taxi-planning tool, the movement of ground traffic can be planned in a
conflict-free fashion, given the constraints of limited available taxiway
resources. The taxi planning involves the management of arrival traffic on the
taxiway system from landing runway to the apron, as well as the management of
departure traffic from pushback to take-off. The proposed time-based
taxi-planning concept heavily relies on the assumption that, in the near future,
advanced guidance and control systems will become available that will provide
aircraft with high-precision taxi capability. This capability will enable
aircraft to precisely follow the deconflicted movement plans produced by the
taxi-planning tool. Recent research [1] has shown that the development of such
advanced guidance and control concepts is both desirable and feasible.The taxi-planning support tool that we present is
based on a graph-theoretic airport-layout model to facilitate conflict-free
aircraft movement planning. In this approach, the taxiway system is modeled as
a set of nodes and links. For this purpose, taxiway intersections, runway
crossings, runway and apron entries, and exits and divisions for separation
constraints are defined as nodes. The aircraft movements through the taxiway
system connecting the various runways with the apron are captured through a
space/time network representation in which the occupancy of the nodes and links
of the graph changes in time. The taxi-planning problem involves creating a
time-based movement plan for each aircraft that is guaranteed to be
conflict-free and takes account of both upstream and downstream requirements.
Conflict-free planning implies that a specified level of separation between
each aircraft is assured in the movement plans. Downstream constraints may
include maintaining a certain departure sequence or meeting specified departure
slot times.  The capability to deal with
(often hard to predict) changes in scheduled pushback times is a typical
example of an upstream requirement. In addition to satisfying the above
constraints, the taxi plans also aim to optimize a global (collective)
performance metric that is directly related to the efficiency of taxi
operations. A typical example of such a collective objective is the total taxi
time.  In our research, a range of
collective criteria has been explored and in the planning tool a graphical user
interface is provided that allows controllers to select and adjust these
criteria to meet their specific needs.Several of the explored performance criteria
are based on the objective to deviate as little as possible from the “ideal”
taxi plans. An ideal taxi plan is the preferred taxi plan for each individual
surface movement in the absence of any other traffic. In other words, ideal
taxi plans involve uncoordinated trajectories that may well contain multiple
conflicts. Using the initial set of ideal taxi movement plans as its major
input data set, the taxi-planning tool produces optimal conflict resolutions
that result in minimal deviation from the ideal surface operations from a
collective perspective. To resolve such conflicts, the taxi-planning tool
utilizes two management instruments, namely, rerouting of aircraft and holding
the aircraft for a certain amount of time at the apron and at various other
predetermined locations on the surface.Due to uncertainty in the input data driving
the taxi planning process, the taxi-planning tool must be designed such that it
produces solutions that are robust to uncertainty. Certain input parameters related to resource demand, such as the
expected landing time, and particularly the expected pushback time, are rather
difficult to accurately predict prior to these events. A taxi-planning tool
must therefore be able to adapt to perturbations in these input conditions, as
well as to account for failure in the actual execution of surface trajectories
(e.g., a missed runway exit).The online planning tool that we envision bases
its activities primarily on observations of
the current state of the system and on the traffic anticipated to be
using the taxiway system within the planning horizon. At each planning update (a multiple of the time increment step size,
typically a factor of six), the actual position on the surface is used to
revise the initial conditions in the planning process. Also any revision in the
estimated pushback or landing time is taken into account. The envisioned
taxi-planning tool performs time/space deconfliction over a fixed planning
horizon. Obviously, it is not desired that the entire surface operation
is completely reshuffled every time a planning update is made. For this reason,
also a freezing horizon has been introduced into the planning system. If a
departing aircraft has its earliest possible pushback time before the freezing
horizon, the route of that aircraft is fixed and no holding is allowed before
that horizon. In the next section, we will primarily focus on the models and
results for a single planning update, without considering a freezing horizon.
The numerical example, however, will show the results of a calculation with
multiple planning updates.To handle the online
planning problem outlined above, one of the most commonly employed operations
research methods for large-scale problems has been successfully used, namely, mixed-integer
linear programming (MILP) [2].
More specifically, a commercial MILP package called CPLEX has been employed [3].In the literature, various models and
algorithms to deal with the taxi movement planning problem have been explored.
In [4], Smeltink et al. present a study which is in some ways very similar to
the work presented herein, as it also uses an MILP formulation, employs a
network based on nodes, and features a sliding window for replanning. A major
difference between their work and the work presented here is that they use a
sequencing-based separation, where only nodes are taken into account,
separation on links is taken into account indirectly, and dummy aircraft are
used to fill up gaps. While their method allows for a range of speeds, instead of
a few discrete values as in the method prescribed here, it does not permit
holding and rerouting of aircraft. Moreover since in their model, time is not
discretized, their approach is not likely to permit planning updates at fixed
time intervals.The research by Pitfield et al. [5] relies on a
Monte Carlo simulation to study potentially
conflicting ground movements, including towed aircraft, at congested taxiway systems.
In their simulation approach, they do not optimize and only solve conflicts by
holding aircraft at certain holding points, rather than through rerouting.
Gotteland et al. [6] use a genetic algorithm to optimize ground traffic. Also their
model does not allow for rerouting of traffic and only considers a single taxi
speed. In addition, the genetic optimization approach taken by the authors appears
to be better suited for offline applications.
Marín [7] defines the taxi
planning model as a linear multicommodity flow network, with additional side
constraints. In contrast to the model considered herein, routes between origin
and destination nodes are fixed and a priori determined using a shortest path
algorithm in [7]. Also, in [7], only a single performance criterion is
considered, namely, the total routing time for all flights only.This paper is organized
as follows. In Section2, the time-based surface traffic movement planning
concept is introduced. Section 3 outlines the mathematical model for a single-planning
update. In Section 4, the taxi-planning concept is demonstrated in a numerical
example involving a hypothetical airport. Finally, in the conclusions, the
contributions of the present study are summarized, and recommendations for
further research are provided.


## 2. Concept Description

In the envisioned
concept, the taxi-planning tool involves creating a (time-based)
surface movement plan for each aircraft by deconflicting the uncoordinated taxi
movement plans, while simultaneously optimizing a collective performance goal.
The output of the tool is an optimized taxi plan that specifies for each
aircraft the route to be followed and the time of arrival at each node in the
selected route.To enable the optimization of the simultaneous
actions of all aircraft, a deterministic model has been formulated that
involves a discretization in both time (multiperiod formulation) and space
(multielement).It is assumed that at the beginning of each
planning update, a complete set of scheduled taxi movements is available for
the planning interval[t0,t0+T], including the
following:(i)
the estimated
landing times of the arriving aircraft;(ii)
the earliest
possible pushback times for a departing aircraft;(iii)
the scheduled runway
arrival times for a departing aircraft;(iv)
the initial node
(apron exit node for a departing aircraft and expected runway exit node for an
arriving aircraft);(v)
the final node
(runway entrance node for a departing aircraft and apron entrance node for an arriving
aircraft).Note thatT represents the planning horizon. Since the above set pertains to individual
taxi movements that are essentially uncoordinated, numerous conflicts in the
trajectories may occur. Surface conflicts of various types can be
distinguished, including trailing aircraft that infringes the separation
requirements by closing in on the
leading aircraft due to a higher taxi speed, aircraft are on an intersection of two taxiways
at the same time, and two aircraft that taxi on the same taxiway in opposite
directions.The ability to
provide optimal time/space deconfliction for all taxi trajectories
simultaneously represents one of the major design requirements for the
taxi-plannin system. The remaining requirements on which the current design
has been based are as follows:(1)
Minimize a collective performance
criterion that is a weighted combination of the following metrics:
(a)
the total taxi time;(b)
the total holding time.(2)
Each aircraft must have its own time-based
taxi movement plan.(3)
It should be possible to accommodate both
one-way and two-way taxiways.(4)
It should be possible to specify a
constant average taxi speed for each individual flight.(5)
The calculation time for a planning
update has to be sufficiently fast to allow compatibility with the planning
update rate.To implement the above requirements, a discrete
time-space network representation has been developed for the taxi-planning
system. The employed time-space network representation was originally conceived
in [8]. Time is treated as discrete by dividing the considered planning
interval [t0,t0+T] into periods k of equal length, k=1,2,…,K, where K is the total number of such periods. With respect to geographic
partitioning of the prototype model, an airport is divided into several
sectors, which are in turn subdivided into several elements.In the
model, the primary elements are nodes. Nodes can either be intersections,
holding points or just subdivisions of a taxiway. Links connect the nodes to
each other in one or both directions.Figure1 shows the geographic partitioning for
a hypothetical example airport, featuring three runways (27, 18L, 18R). The
aircraft holding points (or nodes) are located at the borders of the three
sectors (I, II, III) shown in Figure 1.Figure 1
Example
airport divided into sectors and elements.A taxi route is split up into several taxi
segments with each segment located in only one airport sector. As an example,
we consider an aircraft that has to taxi from the apron exit G1 (node 25) to
the departure runway 18L (node 6). The shortest possible taxi route, as shown
in Figure2, is
(1)G1(N25)⟶N16⟶N1⟶N2⟶N3⟶N4⟶N5⟶R18L(N6). In this notation, Nx stands for node x,Gx for the node corresponding to apron
exit (Gate) x, and Rx for the node belonging to runway x. This
taxi route is split up in two
taxi segments. The first taxi segment (which falls in sector I) is(2)G1(N25)⟶N16⟶N1⟶N2⟶N3⟶N4.The second segment (which falls in sector II)
is(3)N4⟶N5⟶R18L(N6).The maximum number of segments is dependant on
the taxi route because not every taxi route passes through the same number of
sectors. Since one of the requirements is that an aircraft can be rerouted, a
number of alternative taxi routes are assigned to each aircraft in addition to
the easiest route. The easiest route is the route that passes the least number
of nodes and is usually also the shortest.Figure 2
Taxi route from Gate 1 to Runway 18L.Since the performance index is based on a group
(collective) criterion, there is a danger that certain individual taxi
movements are penalized more than others in terms of the delay that they have
to incur. To limit the calculation time and avoid grossly inequitable departure
delays for individual aircraft, a maximum amount of delay is specified by the
user.


## 3. Taxi Planning Model

In this section, the MILP model for the taxi-planning
problem is defined, based on the time-space network representation described in
the previous section.


### 3.1. Decision Variables

The variables that are used to define the taxi
planning problem are binary in nature as follows.xf,d,r,s. The indices indicate a
segment (s) of route (r) belonging to flight (f) with a
certain seconds of delay (d). Thus, xf,d,r,s is 1 if flight (f) takes route (r) and
has delay (d) in segment (s), and is 0 otherwise.wf,d,r,s.  If
a flight (f) with seconds of delay (d) waits for one period on a node at the
start of segment (s) of route (r), then wf,d,r,s is 1, and 0 otherwise. This variable is only
used for blocking a node during the time the aircraft is waiting on it.


### 3.2. Objective Function

The objective function(Z) considered in this study is a weighted combination of the total
taxi time and the total holding time:(4)Z=∑f=1fmax∑r=1rmax(f)∑d=0dmaxKf[Cr+Cd]xf,d,r,smax(f,r), where Kf is the flight priority cost factor. Specifying
a higher value of Kf for a given flight (f) relative to the other flights makes delay for that particular
flight relatively more expensive, causing the optimization process to avoid
adding delay to that flight.The route costCr is equal to the route time cost times the
total active taxi time (thus without delay):(5)Cr=Kr(Tstart(f,r)−Tend(f,r)), where
Kr is the user-specified route time cost factor;
Tstart(f,r) is the time on which route (r) of flight (f) starts;
Tend(f,r) is the time on which route (r) of flight (f) ends.The delay costCd specified in the objective function is defined
as(6)Cd=Kdd.


### 3.3. Constraints

The discrete model developed is used in
conjunction with a mixed-integer linear programming (MILP) approach. The linear
constraints that are used this model are as follows.(i)Node
occupancy is a holding constraint that is needed to avoid conflicts by
limiting the occupation of a node to a single flight at a time:(7)NOt,n:∑f=1fmax∑r=1rmax(f)∑s=1smax(f,r)∑d=0dmax(f,r,s)nf,r,s,n,t−dxf,d,r,s≤1∀t=tmin,…,tmax,∀n=1,…,ntot,n≠nhold(),   where nf,r,s,n,t−d is a binary constant that indicates if segment
(s) of route (r) belonging to flight (f) occupies node (n)
if it has an amount of delay (d) at time (t).(ii)Link
occupancy is a separation constraint and is similar to the node occupancy
constraint as link occupancy limits the occupation of a link to a single flight
at a time:(8)LOl,n:∑f=1fmax∑r=1rmax(f)∑s=1smax(f,r)∑d=0dmax(f,r,s)lf,r,s,l,t-dxf,d,r,s≤1∀t=tmin,…,tmax,∀l=1,…,ltot,   where lf,r,s,l,t-d is a binary constant that indicates if a
flight segment (s) of route (r) belonging to flight (f)
occupies link (l) if it has an amount of delay (d) at time (t).(iii)Route
and delaychoice is a flow
conservation constraint that forces a route and delay to be chosen for every
flight and segment, even if it is an empty segment in which the flight has
already finished its route:(9)RADCf,s:∑r=1rmax(f)∑d=0dmax(f,r,s)xf,d,r,s=1∀f=1,…,fmax,∀s=1,…,smax(f).(iv)Waiting times is a
sequence and flow conservation constraint and ties all segments and waiting
periods together, where Δt is the time increment step size and is equal
to one period. In the example scenarios, the value of Δt = 10 seconds(10)WTf,r,s:∑d=0dmax(f,r,s)2d/Δtxf,d,r,s−2d/Δtxf,d,r,s−1−2d/Δtwf,d,r,s=0∀f=1,…,ftot,∀r=1,…,rtot(f),∀s=2,…,stot(f,r).   If extra delay is “inserted” between two
segments, this constraint forces the time gap between these segments to be
filled with waiting points. For example, if delay is zero for segment one and
twenty seconds for segment two, the summation—if zero values of x are omitted—reduces to the following
equation:(11)22xf,20,r,2−20xf,0,r,1−20wf,0,r,2−21wf,10,r,2−22wf,20,r,2=0⟶4−1−wf,0,r,2−2wf,10,r,2−4wf,20,r,2=0. The
above equality can only be satisfied if wf,0,r,2=1, wf,10,r,2=1, and wf,20,r,2=0.


## 3.1. Decision Variables

The variables that are used to define the taxi
planning problem are binary in nature as follows.xf,d,r,s. The indices indicate a
segment (s) of route (r) belonging to flight (f) with a
certain seconds of delay (d). Thus, xf,d,r,s is 1 if flight (f) takes route (r) and
has delay (d) in segment (s), and is 0 otherwise.wf,d,r,s.  If
a flight (f) with seconds of delay (d) waits for one period on a node at the
start of segment (s) of route (r), then wf,d,r,s is 1, and 0 otherwise. This variable is only
used for blocking a node during the time the aircraft is waiting on it.


## 3.2. Objective Function

The objective function(Z) considered in this study is a weighted combination of the total
taxi time and the total holding time:(4)Z=∑f=1fmax∑r=1rmax(f)∑d=0dmaxKf[Cr+Cd]xf,d,r,smax(f,r), where Kf is the flight priority cost factor. Specifying
a higher value of Kf for a given flight (f) relative to the other flights makes delay for that particular
flight relatively more expensive, causing the optimization process to avoid
adding delay to that flight.The route costCr is equal to the route time cost times the
total active taxi time (thus without delay):(5)Cr=Kr(Tstart(f,r)−Tend(f,r)), where
Kr is the user-specified route time cost factor;
Tstart(f,r) is the time on which route (r) of flight (f) starts;
Tend(f,r) is the time on which route (r) of flight (f) ends.The delay costCd specified in the objective function is defined
as(6)Cd=Kdd.


## 3.3. Constraints

The discrete model developed is used in
conjunction with a mixed-integer linear programming (MILP) approach. The linear
constraints that are used this model are as follows.(i)Node
occupancy is a holding constraint that is needed to avoid conflicts by
limiting the occupation of a node to a single flight at a time:(7)NOt,n:∑f=1fmax∑r=1rmax(f)∑s=1smax(f,r)∑d=0dmax(f,r,s)nf,r,s,n,t−dxf,d,r,s≤1∀t=tmin,…,tmax,∀n=1,…,ntot,n≠nhold(),   where nf,r,s,n,t−d is a binary constant that indicates if segment
(s) of route (r) belonging to flight (f) occupies node (n)
if it has an amount of delay (d) at time (t).(ii)Link
occupancy is a separation constraint and is similar to the node occupancy
constraint as link occupancy limits the occupation of a link to a single flight
at a time:(8)LOl,n:∑f=1fmax∑r=1rmax(f)∑s=1smax(f,r)∑d=0dmax(f,r,s)lf,r,s,l,t-dxf,d,r,s≤1∀t=tmin,…,tmax,∀l=1,…,ltot,   where lf,r,s,l,t-d is a binary constant that indicates if a
flight segment (s) of route (r) belonging to flight (f)
occupies link (l) if it has an amount of delay (d) at time (t).(iii)Route
and delaychoice is a flow
conservation constraint that forces a route and delay to be chosen for every
flight and segment, even if it is an empty segment in which the flight has
already finished its route:(9)RADCf,s:∑r=1rmax(f)∑d=0dmax(f,r,s)xf,d,r,s=1∀f=1,…,fmax,∀s=1,…,smax(f).(iv)Waiting times is a
sequence and flow conservation constraint and ties all segments and waiting
periods together, where Δt is the time increment step size and is equal
to one period. In the example scenarios, the value of Δt = 10 seconds(10)WTf,r,s:∑d=0dmax(f,r,s)2d/Δtxf,d,r,s−2d/Δtxf,d,r,s−1−2d/Δtwf,d,r,s=0∀f=1,…,ftot,∀r=1,…,rtot(f),∀s=2,…,stot(f,r).   If extra delay is “inserted” between two
segments, this constraint forces the time gap between these segments to be
filled with waiting points. For example, if delay is zero for segment one and
twenty seconds for segment two, the summation—if zero values of x are omitted—reduces to the following
equation:(11)22xf,20,r,2−20xf,0,r,1−20wf,0,r,2−21wf,10,r,2−22wf,20,r,2=0⟶4−1−wf,0,r,2−2wf,10,r,2−4wf,20,r,2=0. The
above equality can only be satisfied if wf,0,r,2=1, wf,10,r,2=1, and wf,20,r,2=0.


## 4. Numerical Example

To illustrate the developed concept, a
numerical example is presented related to the hypothetical airport shown in
Figure1. The major characteristics of this airport are as follows:(a)
it has
an outer and an inner taxiway, which are one-way taxiways;(b)
it has a two-way taxiway on which
aircraft can taxi in both directions;(c)
the apron lies in the center of the taxiway system, so aircraft can taxi
clockwise or counterclockwise from the starting node (either the landing runway
or the apron exit) to the end node (either the apron entrance or takeoff
runway);(d)
there are multiple apron exits
and entrances;(e)
the airport-use configuration involves three runways that are all
operated in a segregated mode.Aircraft
entering the taxiway system are divided into fast and slow aircraft. Fast
aircraft taxi with an average speed of 16 m/s, while slow aircraft taxi with an
average speed of 8 m/s. In the numerical example, the safe separation distance
Separation
is
set at 200 m. Based on this separation distance, the line elements (links) are configured
as shown in Table 1.Table 1
The line element lengths and the number of periods
needed to cover the elements with different taxi speeds.
From nodeTo nodeDistance (meters)Periods at 16 m/sPeriods at 8 m/sN01N0210012N01N1425024N01N1610012N02N0330024N02N1710012N03N0420023N04N0520023N05N0610012N05N2010012N05N0720023N07N0825024N08N0920023N09N2310012N09N2720023N09N1020023N10N1110012N11N1220023N11N2320023N12N1320023N13N1510012N13N1625024N13N1410012N16N1710012N16N2510012N17N2610012N17N1820023N18N1910012N19N2020023N20N2110012N21N2215012N22N2320023N23N2410012N27N2820023With the lengths of the line elements, the taxi-speed
options, and a period length of 10 seconds, the number of periods needed to
cover each line element for a given taxi speed can be approximately
determined.Let us, for example, consider line element
connecting Node 2 and Node 3 with a length of 300 m. It takes 37.5 seconds or 4
time periods to cover the 300 m distance with a taxi speed of 8 m/s. In the
last period, Node 3 is also occupied. The resulting set of the number of time
periods needed is included in Table1. It should be noted that it is possible
for an aircraft to block multiple nodes and links during the same period, so
the rounding of time to periods does not accumulate during the route.To test the taxi-planning concept for the hypothetic airport, a scenario has been created that involves the movement planning of eight aircraft (six departing and two arriving) using a planning horizonT of 42 periods. In view of the assumed
period length of 10 seconds, the planning interval consists of 420 seconds or
(6 minutes).As mentioned earlier, a set of the ideal
uncoordinated movement plans is calculated at the start of the planning update.
Table2 lists the aircraft planning set for the present example scenario. It
should be noted that this planning set is purposely complex to give a good
indication of the conflicts to be solved.Table 2
List with the
departing and arriving aircraft,
the taxi speed, the starting point (departure gate or arrival runway), the
destination point (arrival gate or departure runway), the start time (earliest
pushback time or runway arrival time), and the destination time (latest gate
arrival time or allocated runway departure time).
AircraftStartTimeDestinationTimeSpeed (m/s)1 (departing)G2 (N26)0:01:10R18R (N15)0:06:0082 (departing)G3 (N24)0:01:00R18R (N15)0:07:00163 (departing)G1 (N25)0:01:40R18L (N06)0:07:00164 (departing)G1 (N25)0:01:20R18L (N06)0:07:3085 (departing)G1 (N25)0:02:40R18L (N06)0:08:30166 (departing)G3 (N24)0:02:20R18L (N06)0:08:3087 (arriving)R27 (N28)0:00:00G2 (N26)0:09:3088 (arriving)R27 (N28)0:00:30G2 (N26)0:09:008With the information provided in Tables1 and
2, the ideal taxi plan for each aircraft is determined. These individually
ideal taxi plans are shown in Table 3. The bold printed time in
Table 3 indicates
the applied planning horizon. The use of a planning horizon helps to reduce the
complexity of the optimization problem. Note that the pushback time is
specified in such a way that departures can not only be delayed, but can also
be scheduled earlier due to the use of longer routes.Table 3
Ideal taxi plan (with conflicts).
TimeAircraft123456780:00280:1027-280:2027-280:3027-28280:4027-2827-280:5027-2827-281:0027-2827-281:109-2727-281:209-2727-281:309-2727-281:409-279-271:509-279-272:00259-279-272:1016-259-239-272:2016-259-239-272:3016-259-239-272:40241-1622-239-232:5023-241-1622-239-233:0023-241-1622-239-233:102622-231-222-2322-233:2017-2622-231-222-2322-233:3017-2622-231-222-2322-233:4017-2621-222-321-2222-233:5016-1721-22252-321-2222-234:0016-1720-2116-252-321-2222-234:1016-1720-2116-252-321-2221-224:2013-1619-201-162-320-2121-224:3013-1619-201-162-320-2121-224:4013-1619-201-22-32420-2121-224:5013-1618-191-22-323-2419-2020-215:0013-1618-192-33-423-2419-2020-215:1013-1617-182-33-423-2419-2020-215:2013-1617-182-33-42522-2319-2019-205:3013-1517-182-33-416-2522-2319-2019-205:4013-1516-173-43-416-2522-2319-2019-205:5013-1516-173-43-41-1622-2318-1919-206:0013-163-44-51-1622-2318-1919-206:1013-164-54-51-222-2318-1919-206:2013-164-54-51-221-2217-1818-196:3013-164-54-52-321-2217-1818-196:4013-155-64-52-321-2217-1818-196:5013-155-64-52-321-2217-1817-187:005-62-320-2117-1817-187:105-63-420-2117-1817-187:205-63-420-2117-2617-187:303-45-2017-2617-187:404-55-2017-2617-187:504-55-2017-268:004-55-617-268:105-65-617-268:205-65-6The bold numbers in Table3 indicate the various
conflicts. If aircraft would indeed taxi according to the ideal taxi plan, two
kinds of conflicts can be observed as follows.(1)
Two
aircraft are at an intersection at the same time. According to the
individually ideal plans, aircraft 1 and 3 both cross node 16 at time 4:10.(2)
Two
aircraft close in while taxiing on the same link.  If the ideal plans were to be followed,
aircraft 3 would overtake aircraft 4, and aircraft 7 would violate the
separation with aircraft 8.
To resolve the conflicts and optimize the
traffic flow, a performance index has to be specified. At present, two
different criteria as well as any weighted combination of these criteria could
be selected. In the example presented herein, the primary objective is to
minimize the taxi travel time while penalizing delay twice as heavy.The results for this particular scenario are
shown in Table4. In
Table 4, the optimized and deconflicted taxi plans are
shown for the 8 aircraft moving on the surface. The bold printed cells
indicate changes and arrows indicate delayed pushback.Table 4
First planning update (conflict after horizon).
TimeAircraft123456780:00280:1027-280:2027-280:3027-28⇓0:4027-28⇓0:5027-28⇓1:0027-28281:10249-2727-281:2023-249-2727-281:3023-249-2727-281:4022-239-2727-281:5022-239-2727-282:0022-23259-2727-282:1021-2216-259-239-272:2021-2216-259-239-272:3020-212516-259-239-272:4020-2116-251-1622-239-272:505-2016-251-1622-239-273:005-2013-161-1622-239-273:10265-713-161-222-239-233:2017-265-713-161-222-239-233:3017-265-713-161-222-239-233:4017-267-812-132-321-2222-233:5016-177-812-132-321-2222-234:0016-177-812-132-321-2222-234:1016-177-811-122-321-2222-234:2013-168-911-122-320-2122-234:3013-168-911-122-320-2122-234:4013-168-911-232-3⇓20-2121-224:5013-169-1011-232-3⇓19-2021-225:0013-169-1011-233-42419-2021-225:1013-169-1022-233-423-2419-2021-225:2013-1610-1122-233-42523-2419-2020-215:3013-1510-1122-233-416-2523-2419-2020-215:4013-1511-1221-223-416-2522-2319-2020-215:5013-1511-1221-223-41-1622-2318-1919-206:0011-1220-214-51-1622-2318-1919-206:1012-1320-214-51-222-2318-1919-206:2012-135-204-51-222-2317-1819-206:3012-135-204-52-322-2317-1819-206:4013-155-64-52-321-2217-1819-206:5013-155-64-52-321-2217-1818-197:005-62-321-2217-1818-197:105-63-421-2217-1818-197:205-63-420-2117-2617-187:303-420-2117-2617-187:404-520-2117-2617-187:504-55-2017-188:004-55-2017-188:105-65-2017-188:205-65-617-268:305-617-268:405-617-26In the optimal solution, the following features
can be observed.(1)
Aircraft 1 taxies according to its ideal
taxi plan.(2)
Aircraft 2 follows a longer route
than the shortest one, as is illustrated in Figures3 and
4, and to arrive at
the takeoff runway on the stated time, it departs
the apron earlier. This is still, however, later than the earliest pushback time stated
in Table 2.(3)
Aircraft 3 follows a longer route, as
aircraft 2 does. It therefore alsoleaves the apron earlier
to be at the departure runway on time.(4)
Aircraft
4 taxies according to itsideal taxi plan.(5)
Aircraft
5 taxiesaccording to its ideal taxi plan.(6)
Aircraft
6 follows theshortest route, but is delayed at the gate for two
periods and therefore arrives at the runway 20 seconds later.(7)
Aircraft
7 taxies according to itsideal taxi plan.(8)
Aircraft
8 follows theshortest route, but holds at the runway exit for three
periods and therefore arrives at the gate 30 seconds later.Figure 3
Aircraft 2, shortest route.Figure 4
Aircraft 2, rerouted.Due to that fact that planning is restricted to
within a fixed horizon, a conflict may still exist beyond the planning horizon.
Table4 shows such a conflict for aircraft 5 and 6 at time 8:20. In the planning
update 2 minutes later, shown in Table 5, this conflict is resolved by delaying
flight 6 on node 21 for one period. The rest of the planning remains unchanged.Table 5
Planning update after 2 minutes (conflict-free).
TimeAircraft123456780:00280:1027-280:2027-280:3027-280:4027-280:5027-281:0027-28281:10249-2727-281:2023-249-2727-281:3023-249-2727-281:4022-239-2727-281:5022-239-2727-282:0022-23259-2727-282:1021-2216-259-239-272:2021-2216-259-239-272:3020-212516-259-239-272:4020-2116-251-1622-239-272:505-2016-251-1622-239-273:005-2013-161-1622-239-273:10265-713-161-222-239-233:2017-265-713-161-222-239-233:3017-265-713-161-222-239-233:4017-267-812-132-321-2222-233:5016-177-812-132-321-2222-234:0016-177-812-132-321-2222-234:1016-177-811-122-321-2222-234:2013-168-911-122-320-2122-234:3013-168-911-122-320-2122-234:4013-168-911-232-320-2121-224:5013-169-1011-232-319-2021-225:0013-169-1011-233-42419-2021-225:1013-169-1022-233-423-2419-2021-225:2013-1610-1122-233-42523-2419-2020-215:3013-1510-1122-233-416-2523-2419-2020-215:4013-1511-1221-223-416-2522-2319-2020-215:5013-1511-1221-223-41-1622-2318-1919-206:0011-1220-214-51-1622-2318-1919-206:1012-1320-214-51-222-2318-1919-206:2012-135-204-51-222-2317-1819-206:3012-135-204-52-322-2317-1819-206:4013-155-64-52-321-2217-1819-206:5013-155-64-52-321-2217-1818-197:005-62-321-2217-1818-197:105-63-421-2217-1818-197:205-63-42117-2617-187:303-420-2117-2617-187:404-520-2117-2617-187:504-520-2117-188:004-55-2017-188:105-65-2017-188:205-65-2017-268:305-617-268:405-617-268:505-6The computational burden for a problem of the
complexity as presented herein is modest, even though the situation shown in
the example is purposely overcomplex. On a standard PC, the calculation of a
full run with eight aircraft and many conflicts takes about 5 seconds, with
planning updates running significantly faster due to the reduced number of
conflicts. It should be noted that the computational time does significantly
increase with an increase of the number of flights. For example, doubling the
number of flights in the numerical example from 8 to 16 causes the calculation
time to go up from 5 to about 20 seconds.
It is therefore important that both the airport model and the flight
schedule are well structured and that the planning horizon is kept within
reasonable limits to ensure that the MILP problem remains computationally
tractable. Preliminary runs with a full scale flight schedule, with 20 aircraft
divided regularly over 15 minutes, show that, due to the reduced number of
conflicts and thus complexity, the computational time remains within a couple
of seconds.


## 5. Concluding Remarks

In this paper, a concept for a taxi-movement-planning
tool based on MILP models has been presented. Application of the tool results
in a revision of the taxi plans for each aircraft to match the constraints
while minimizing the “costs.” The initial results are primarily
related to a single planning update.
Such an update involves the planning of all
the current aircraft
and those anticipated to be using the taxiway system within the planning
horizon.On the indication of the preliminary results,
the concept appears to hold out great promise for further development. A real-life
schedule and airport model will be implemented in the near future to demonstrate
that the taxi-movement-planning tool is indeed able to optimally solve taxi
planning scenarios, especially with respect to the complexity and size of the
resulting MILP problems.



---

*Source: 732828-2008-06-23.xml*