An integrated solution for the aircraft taxi and gate assignment problems

Abstract

Airlines incur a number of costs associated with moving freight or passengers for one point to another. To manage and control these costs, airlines are constantly looking for areas or opportunities to manage costs and increase efficiency. Various areas or segments of operations have been investigated with little review of the impact of the researched area on other segments of the operation. This research presents a framework for assigning flights to a departure gate that minimizes delays caused by moving passengers or freight to the departing flight and delays incurred during the taxing from the gate to the runway. As part of this research, variations due to travel speed are investigated. In addition to problem formulation, this research presents a solution algorithm incorporating a genetic algorithm that determines the gate assignment scheme resulting in the minimum delay minutes for a given schedule.

Keywords:

• gate assignment
• job shop
• genetic algorithm
• aircraft taxi problem

Public Interest Statement

Airlines are constantly trying to balance customer convenience with the costs of operation. These balancing efforts can result in deciding to favor operations or customer satisfaction, comfort, and convenience. Whether transporting freight or passengers, the pressures and decision points are similar if not identical. This study investigates balancing delays preparing the aircraft for departure with delays moving the aircraft from the gate to the takeoff runway, balancing the customer with operations. Within this paradigm, this study tests the modeling framework under differing degrees of variation to test the robustness of the approach. Based on this study, the proposed framework provides a robust problem definition and solution set that optimize the solution.

1. Introduction

Inside the transportation sector, airlines move freight and passengers between different geographical areas. While the airline provides a time efficient method to move great distances, this mode of transportation incurs high costs relative to other modes. The high costs of operation are mainly associated with the acquisition and use of the main piece of equipment, the airplane. Whether the flight is sitting on the ground or in flight, the flight will be accruing costs for such items as the flight crew and fuel. To produce a profit, airlines must manage these operational constraints to gain any efficiency possible to control and manage costs.

The air traffic system can be divided into several segments that reflect various functions or segments of the flight. The research community has identified these various segments by focusing research projects on one segment or another. However, these research efforts generally do not consider the impact of a preceding segment on the segment being studied, nor its impact the next segment. Traditionally, the movement of a flight around the airport has been a separate research area from the gate or ramp assignment. The trends in research do not consider where the flight originates prior to movement as well as the impact of location and load times on the departure sequence. In this paper, we present a general framework for integrating two of the operational segments, the gate assignment and aircraft taxi problems. As part of this framework, we translate the combined problem into a job shop scheduling problem. This paper presents the results of applying a genetic algorithm to solve the integrated problem along with a stochastic approach to investigate variations in the travel times.

In Section 2, we present an overview of the key parts of the air traffic system and research to date for the taxi problem and gate assignment problems. Section 3 presents the framework and problem definition for the combined approach. Section 4 presents the results of the solution process, and Section 5 summarizes the research and identifies potential research opportunities.

2. Background

2.1. Service models

The airline business provides a simple service, moving passengers and freight between two points using three operation models: passenger only, mixed (passenger and freight), and freight only. Each model may operate as a point-to-point or hub and spoke system. In a point-to-point operation, the passengers and/or freight move from a specific origin to a specific destination, while in a hub and spoke system, the airline collects passengers and/or freight from a number of origins (spokes), moves them to a central location (hub), sorts the passengers and/or freight, and then moves each item/person to its destination.

The passenger model focuses on the movement of passengers through the airline system, with the main interaction point being the customer and the main measures being their convenience and satisfaction. In the literature, the focus has been on moving passengers through the terminal facility and minimizing the distance the passenger travels within the facility while allowing the flight to depart on time (Bihr, 1990; Dongxuan & Changyou, 2007; Kumar & Bierlaire, 2012; Li & Xu, 2012; Yan & Huo, 2001; Zhang, Cesarone, & Miller, 1994). In this context, customer satisfaction is measured by movement around the terminal, while in reality customer satisfaction is most achieved by arriving at the desired destination by the promised time.

In the mixed model, excess cargo space in the flight (the space remaining after the passenger luggage has been loaded) is used to move freight. The limiting factors for this operation model are the amount of space available and the destinations available, since the cargo must travel where passenger flights are already planned. The passenger portion of this model operates in the same manner as the pure passenger model. In both research and reality, cargo customer satisfaction is measured by the cargo arriving at the desired location at the stated time.

Freight only operations follow one of three modes: charter operations, scheduled operations, and scheduled operations handling express and parcel movements. In charter operations, an aircraft is contracted to move specific freight between two defined points with the charter freight carrier providing the aircraft and staff, and operating on an as needed basis. Satisfaction is measured by the service provider meeting the terms of the contract or charter. Scheduled operations encompass not only large freight units, but also parcels. Larger freight units are tendered to the freight line, moved through a sorting and transportation network, and then delivered to the destination. Parcel transportation follows the same essential process as the larger freight units, with the sort processes utilizing more automation to complete the sort process. The scheduled operation functions within defined operating and movement parameters and timeframes (much like a scheduled passenger airline). The customer interaction points are at the tendering site at the start of the process and at delivery, and satisfaction is measured in terms of on-time delivery of the parcel or freight.

2.2. Air traffic system

All airline operations are impacted by two basic, interrelated factors: fuel costs and air traffic movement. Efficient movement of an aircraft through the air traffic system will naturally lead to more efficient fuel usage through the use of more direct routings, shorter holding time waiting for a landing spot and fewer mid-route changes due to conflicts. The complexity of the procedures involved in moving the flight from the origin to the destination combined with the sheer volume of flights moving through the system introduces a level of uncertainty in maintaining schedules.

For all flights, there are a series of steps or phases that the plane passes through as it moves through the air traffic control system. While there are a number of steps, the following are the steps typically addressed in research:

(1)	Pushback or gate departure – The flight departs the gate and prepares for taxiing around the airport. The time associated with this phase is used by the regulatory bodies to measure on-time departure performance.
(2)	Taxi out – Once the flight leaves the gate, it moves to the runway for take-off. Depending on the status of the operation (hub or non-hub airport), the flight may taxi in areas referred to as the ramp that are controlled by an airline. Prior to entering an airport controlled area, the flight will pass a point where control of the flight is passed from the ramp controller to the ground controller who coordinates the movement of each flight around the airport.
(3)	Take-off or airport departure – At this point, the flight is handed off to the local controller who sequences it with other departing and arriving flights for use of the runway and air space. After the flight clears the runway, it is passed to the approach controller. This phase not only includes the use of the runway, but also the departure air space around the airport.

The air traffic system is complex with a number of independent and dependent features making modeling it difficult. Within the air traffic system, there are assignment problems, network flow problems, inventory problems and scheduling problems. Each one of these problems has unique formulation and solution techniques.

The goal of any analysis of passenger movement is to minimize the distance traveled. Numerous efforts have been made to study assigning gates to minimize the time spent transferring between aircraft (Bihr, 1990; Dongxuan & Changyou, 2007; Kumar & Bierlaire, 2012; Li & Xu, 2012; Yan & Huo, 2001; Zhang et al., 1994). Ding, Lim, Rodrigues, and Zhu (2005) expanded on the travel distance by including embarking and disembarking passengers. Several studies refer to generic walking distance, but do not distinguish between transferring passengers and those who either start or end their travel at a specified airport (Hu & Di Paolo, 2009; Mangoubi & Mathaisel, 1985; Xiao-Bing & Di Paolo, 2009).

The gate represents a costly asset for the entity responsible for its operation and the assignment of the flight to the gate. In order to achieve a return on the investment, fees are charged for the usage of the gate. The goal of the assigning entity is to maximize the number of aircraft using the gate and therefore the funding derived from the usage. Gate usage models can be divided into two categories: time spent occupying a gate and time and effort spent moving aircraft between gates and between gates and temporary parking spots. There have been a number of studies that have investigated maximizing the time a gate is occupied (Genç, Erol, Eksin, Berber, & Güleryüz, 2012) or minimizing the amount of time a gate is empty (Bolat, 2000, 2001). A number of studies combine passenger movement models and assumptions with gate usage to develop assignment models. Ding et al. (2005) combined passenger movement (transfer, embark and disembark) with minimizing the number of flights that were not assigned gates at arrival. Hu and Di Paolo (2009) added baggage travel time to passenger movement and “ungated” flights.

As a problem set, aircraft movement is defined as the movement of aircraft from an origin to the runway for take-off. Within this definition, the problem statements look at both arriving (landing) and departing (take-off) aircraft and the efficient movement through the airport complex to and from gates. Embedded in the assumptions are the supply and demand points for the problem. The supply is generally considered to be from some entry point. There is little consideration in the research for the origin and destination of the flights and the impact these points have on the movement. Although the starting point will impact the time spent moving about the airport, the routing of the aircraft from its starting point (whether a gate or a hand off point) to the departure point (runway) is a greater portion of the time spent in movement and waiting. To mitigate delays, efficient sequencing of the aircraft coupled with the use of the most efficient routings provides a way to minimize time spent on the ground. The major challenge impacting the entry of aircraft into the system is that the controllers do not determine the queue of aircraft presenting themselves for movement authority. To overcome this challenge, scheduling the movement of aircraft around the airport (taxiing between the runway and the terminal gates or apron) can be used (Smeltink, Soomer, de Waal, & van der Mei, 2004). Once the aircraft is provided taxi authority, it is critical to avoid conflicts (two aircraft meeting on a single taxi way or two aircraft trying to traverse the same intersection). It is critical to plan movements ahead of time to identify these conflicts and resolve them with proper routings (Cheng, 1998; Marín, 2006).

Most of the gate assignment problems investigate the gate assignment as a function of customer satisfaction and service resources. An extension of this formulation coupled with the aircraft movement problem investigates gate usage. In settings where there is not a defined inbound and outbound movement, there is the possibility of an assigned gate being occupied when the inbound flight arrives. Narciso and Piera (2015) investigate two approaches to mitigating the negative impact of gate blockages by determining the number of gates needed to support a schedule with minimum blockages and developing various policies to mitigate the negative impact on customers given a fixed number of gates. Castaing et al. (2016) approach the problems associated with gate blockages by developing an approach that provides a gate assignment which minimizes the incidents of gate blockages. Departure metering is used to control the number of taxiing aircraft while maintaining availability to the departing runways. Sang Hyun and Feron (2014), develop a gate assignment approach to minimize the impact of metering on gate blockages.

Both research areas focus on the specific task at hand, but do not consider how one area impacts the other. With gate assignments, the focus is on the gate and not the effects of the assignment on the operation of the flight. With the movement, there is little or no consideration for the origin of the flight and the impact the origin has on the overall problem. Atkin, Burke, and Ravizza (2010) did note there is benefit to “connecting” the aircraft movement problem with the assignment problem. Maharjan and Matis (2012) present a combined approach integrating the efficiency of the airline with the convenience for the customers. In this approach, the metrics are reduced to cost variables. Multiple objective function problems using cost as a metric run the risk of one set of costs overshadowing the other costs and therefore driving the model solution.

Given the lack of connectedness between the flight moving around the airport and the origin of the flight within the airport, research is needed to connect these areas. Our effort proposes a framework for developing a solution approach and quantifying the goodness of the solution. We propose a genetic algorithm to optimize the resulting gate assignments based on the delays that cause a late departure from the gate and the delays during taxiing, connecting gate assignment with the movement of the aircraft through the ramp.

Operating to a schedule brings a certain level of inherent risk and an overall goal to operate as closely to the schedule as possible. The variance of the actual operating times to the schedule can cause conflicts or present challenges in scheduling aircraft to a specific gate. A common gate availability strategy is to pad or buffer the gate availability time with extra time (Narciso & Piera, 2015). While padding the schedule may provide an easier method for managing the gate assignment, this does not take into account the natural variation of the movement speeds of various aircraft. To try and address this natural variation, Roling and Visser (2008) use average travel times based on aircraft size and does not consider the variation. In both approaches, fixed values are used to address unforeseen circumstances as well as normal process variation. To introduce a level of variation into our approach and process, we are proposing using stochastic modeling to introduce variation into the movement times used in the proposed approach.

Several other solution techniques were reviewed to investigate alternatives to the use of a genetic algorithm. Mogale, Dolgui, Kandhway, Kumar, and Tiwari (2017) present a mixed integer problem that uses a max min ant colony algorithm to solve the distribution problem. Kuo (2010) presents a simulated annealing solution to a time dependant vehicle routing problem. Maiyar and Thakkar (2017) provides a particle swarm approach to solve a mixed integer non-linear problem for food distribution. When looking at other heuristics, simple swapping of one or more pairs of gates and flights imitates the mutation function of the GA and does not leverage the effect of the cross on the solution. In most cases, simply swapping a few flights will not yield an adequate search of the solution space when compared to the cross function.

3. Method and materials

For purposes of researching gate assignments and their impact on the movement of the aircraft from the departure gate to the runway and thus the operating costs of the airline, the research area is defined as the ramp. The ramp, also referred to as the terminal area, includes the sorting facility, the aircraft gates, and the associated taxi areas up to the exit point where control transfers to the airport FAA tower. Figure 1 details the parts of a ramp used for freight operations. These include:

(1)	Sort building – The facility where packages and freight are sorted by destination and prepared for flight. All packages are placed in containers for transport and loading into a departing aircraft.
(2)	Gate lead-in lines – The lines that provide the pilot with guidance in placing the aircraft correctly in the gate. Where these lines intersect the centerline of the taxi lane represents a nodal point for measuring the distance and time for aircraft movement.
(3)	Gates – The parking spaces for the flights. Each departing aircraft originates from a gate and travels through the taxi lane to the exit point. The gate is also the end point for freight when moved from the sort building.
(4)	Vehicle drive lanes – Defined areas within the terminal where vehicular traffic is allowed to operate. The main users of the areas are the tugs and dollies used to move the containers from the sort building to the gates.
(5)	Aircraft taxi lanes – These lanes function as the roadway for the aircraft moving through the terminal area. The taxi lanes are fixed routes that every arriving or departing flight must traverse to enter or exit the gate area.
(6)	Traffic control spot (exit point) – The point where control of aircraft movement transitions from the local tower to the FAA tower.

In previous formulations for the assignment model, the objective function covered moving the passenger or freight to and between aircraft (Bihr, 1990; Li & Xu, 2012; Yan & Huo, 2001). While this provides for efficient movement between flights, it does not consider the impact of the gate assignment on the overall operation of the airport. Similarly, the aircraft movement problem objective functions set a goal of minimizing the travel time and establishing an ideal or optimized movement (Bolat, 2001; Genç et al., 2012). While this approach presents an optimized movement, it does not adequately measure the interaction of the source of the flight with the movement. The challenge faced in formulating the gate assignment problem and the taxi movement problem as a single problem is integrating two similar yet different problems. Joining these two problems into a single problem requires three steps: problem definition, delay definition and solution techniques.

Figure 1. Freight terminal area.

3.1. Problem definition

For ease in presenting a solution to the unified problem, a freight ramp (Figure 1) is used. (Although focused on freight, the concepts discussed can be extended to passenger operation.) In addition to using time as a metric, we will consider the delays that arise in departing the gate and delays incurred while taxiing. The proposed approach tracks and coordinates these delays to develop a unified solution that optimizes the ability of the flights to maintain their schedule. Although these delays are combined into a single approach, they can be analysed and tracked separately.

A gate delay is the lateness of a flight departing from the gate when compared to the scheduled departure time. This departure time is defined as the time when the flight is loaded and has asked for clearance to depart the gate. With the control point for the departure defined as the point where clearance is requested, delays can be caused by a number of items, some of which are controllable and some that are not. This study focuses on controllable delays that arise due to congestion at intersections and around the gates due to the impact of the load/unload operations interfering with traffic.

Taxi delays are measured from the point when the flight is ready to depart the gate to the point where the flight exits the modeled environment. By selecting the transition from gate delays to taxi delays as the point in the process where the flight is ready for departure, the taxi delay captures time spent in the gate waiting for the taxi path to clear to allow the flight to occupy the first segment of their taxi path. This wait time, as well as the time spent moving through the remaining segments on the route to the exit point, constitutes the taxi delay and provides an overall measure of the congestion in the taxi system.

In order to monitor aircraft as they move through the modelling environment, the taxi route is divided into fixed-sized segments with the constraint that there can only be one aircraft per segment. Using too large of a segment will result in lower capacity and greater congestion and delays. By setting the segment length based on the largest aircraft, the number of usable segments at any given time is maximized since empty or buffering segments are not needed to maintain separation while enforcing the occupancy requirements and avoiding the computational overhead that would be needed if a dynamic spacing approach were used.

3.2. Assumptions

The following assumptions are used in this approach:

(1)	When operating a freight hub, the arrivals and departures occur in a short period. This characteristic of a hub causes the traffic movements around the ramp and airport to be generally one way in flow. This approach considers just the outbound or departure process and therefore will assume that the taxi movements will move in one direction, outbound.
(2)	With the concentration of movement for hub operations, it is assumed that all gates are available for assignment to an outbound flight.
(3)	All equipment and staffing needed to conduct the tasks will be available when needed. The departure will not be delayed due to a lack of staffing or equipment.
(4)	If a taxi conflict exists, priority is given to the taxiing aircraft. Departing aircraft shall remain in the gate until there is a clear path to exit.
(5)	All planned tasks will be performed in accordance with proper procedures and methods. The load will start according to the stated launch countdown procedures.

3.3. Notation and terms

Within the problem definition, the airline schedule will be used as a data source. This schedule establishes the baseline departure time. The model formulation will use a number of terms to define specific times relating to the schedule.

•	Schedule departure time—the time in the published schedule that the flight should leave the gate. This time will be used for establishing delays.
•	Pushback time—the point in time where the delays transition from gate delays to taxi delays. This is the actual or modeled departure time based on when the flight is ready to leave the gate.

3.3.1. Sets and indices

G(j)	=	The set of gates that meet the restrictions for flight j
M	=	The set of all gates
R(i)	=	The set of taxi segments representing the taxi route from gate i to the exit point
R	=	The set of all taxi segments such that $R(i)\in R$
i	=	Member of the set of all gates
j	=	Member of the set of all flights to be assigned
k	=	The arrival gate/location of origin
l	=	A member of the set of taxi segments R(i)
f	=	The entrance point of a gate into the taxi path as represented by the first segment in the path

3.3.2. Variables

$d_{\mathit{ij}}^g$	=	The delay of flight j departing from gate i due to late freight to the gate.
$d_{\mathit{ij}}^t$	=	The delay of flight j departing from gate i due to traffic movement across the airport complex.
xij	=	Flight j is assigned to gate i.

3.3.3. Parameters

f(x)	=	The pdf for the travel time from the arrival gate or sort location to the departure gate
g(x)	=	The pdf for the taxi time from the gate to the exit point
$a_{\mathit{ikjp}}^e$	=	The expected arrival time of freight or passenger p from gate k to gate i for flight j
lpij	=	The time required to prepare the flight for departure after load is complete for flight j in gate i.
$l{t}_{\mathit{ij}}^e$	=	The expected time to load the last freight or passenger and prep for flight j assigned to gate i
m	=	The number of gates
n	=	The number of flights
$p_{\mathit{ij}}^e$	=	The expected pushback/departure time of flight j from gate i
sj	=	The scheduled departure time of flight j
scp	=	The time of freight or passenger p enters the system and is ready to move to the gate
stjl	=	The time flight j enters segment l
$t_{\mathit{jie}}^m$	=	The time required to move flight j from gate i to the exit point e
$t_{\mathit{jl}}^m$	=	The time required to move flight j through taxi segment l
$t_{\mathit{ie}}^p$	=	The time required to move from gate i to exit point e with no interference or congestion
$t_l^p$	=	The time required to move through taxi segment l with no interference or congestion
$tmi{n}_l^p$	=	The minimum allowable time required to move through taxi segment l with no interference or congestion
$tma{x}_l^p$	=	The maximum allowable time required to move through taxi segment l with no interference or congestion
t	=	Model clock time
teje	=	Exit time of flight j for segment l
ttikjp	=	The travel time of freight or passenger p from gate k to gate i for flight j
tel	=	The exit time for a flight exiting segment l

3.4. Objective function

With this problem, there are two sub problems: transport time (moving freight to the aircraft) and taxi time (moving the aircraft from the gate). Each of these items can be identified by separate objective functions. To combine the goals into a single objective function, a multi-objective objective function is required. The first objective (Z1) addresses delays leaving the gate due to freight movement through the terminal complex, while the second objective (Z2) is to minimize the delay caused by movement through the airport.(1) $$min{Z}_1=\sum _{\begin{array}{c}0<i\le m\hfill \\ 0<j\le n\hfill \end{array}}{d}_{\mathit{ij}}^g$$(1) (2) $$min{Z}_2=\sum _{\begin{array}{c}0\le i\le m\hfill \\ 0<j<n\hfill \end{array}}{d}_{i,j}^t$$(2)

Using the model defined by Kuhpfahl (Kuhpfahl, 2016) as a basis for developing the joint model, the two objectives are combined to achieve a new objective function:(3) $$minZ=\sum _{\begin{array}{c}0<i\le m\hfill \\ 0<j\le n\hfill \end{array}}{d}_{\mathit{ij}}^g+d_{\mathit{ij}}^t$$(3)

The objective function is subject to meeting the constraints:(4) $$d_{\mathit{ij}}^t=t{e}_{\mathit{je}}-\left(p_{\mathit{ij}}^e+\sum _{l\in R(ie)}{t}_l^p\right)\forall i,\forall j$$(4) (5) $$d_{\mathit{ij}}^g=\left(p_{\mathit{ij}}^e-s_j\right)\forall j,\forall i$$(5) (6) $$t{e}_{jl+1}\ge t{e}_{\mathit{jl}}\forall j,\forall l$$(6) (7) $$p_{\mathit{ij}}^e\ge t{e}_{\mathit{if}}\forall f\in R(i),\forall j,\forall i$$(7) (8) $$\sum _{\forall j}{x}_{\mathit{ij}}=1\forall i$$(8) (9) $$\sum _{\forall i}{x}_{\mathit{ij}}=1\forall j$$(9) (10) $$d_{\mathit{ij}}^t,d_{\mathit{ij}}^g\ge 0\forall i,\forall j$$(10) (11) $$x_{\mathit{ij}}\in \left\{0,1\right\}\forall i,\forall j$$(11)

The goal of this problem is to determine an assignment scheme that minimizes the delays incurred by the departing flights. The objective function minimizes the delays moving freight or passengers to the gate and the delays associated with taxiing the flight through the ramp area. The taxi delays must be non-negative Equation (10) and not arbitrarily set to 0 Equation (4). Equation (4) further defines the taxi delay as the difference of the time the flight exits the system and the time it should exit the system if there is no interference. The delays caused by freight or passengers arriving at the gate are defined in Equations (5) and (10). Equation (5) provides that the delay must be the difference between the scheduled departure time and the actual departure. Equation (10) provides that the delay must be non-negative. Equation (12) provides that the departure or pushback time must meet or exceed the scheduled departure time, further enforcing the non-negative delays.

Within the problem, each flight must be assigned to a gate that can accommodate the flight from a set of gates that can accommodate the flight. For an assignment scheme to be valid and feasible only one flight can be assigned to one gate and the assigned gate must be able to accommodate the flight. Equation (8) requires that for each flight only one gate may be assigned to the flight. Similarly, Equation (9) states that for each gate, only one flight may be assigned. Within Equations (8) and (9), a value of 1 denotes an assignment and 0 denotes no assignment Equation (11). With this assignment, there can only be one push back time ($p_{\mathit{ij}}^e$), one scheduled departure time (s_j), and one set of taxi segments (R(i)) associated with a given gate and flight combination.

In order for a flight to leave the gate and enter the taxi system, three conditions must be met: all the freight or passengers must be on the flight, the flight cannot leave before the scheduled departure time, and the taxi path must be clear. Equation (13) requires that the push back time be no earlier than when the loading of the last passenger or freight is complete when flight j is assigned to gate i. Equation (12) states the flight cannot leave the gate before the scheduled departure time when flight j is assigned to gate i. Equation (7) enforces that the segment used to enter the taxi system is clear. While the flight is taxiing, two conditions must be met. First the flight cannot move to the next segment until completing the current segment Equation (14). Prior to moving to the next segment, any flight must have exited the next segment. Equation (6) enforces this constraint.(12) $$p_{\mathit{ij}}^e\ge s_j\forall j,\forall i$$(12) (13) $$p_{\mathit{ij}}^e\ge \left(l{p}_{\mathit{ij}}+l{t}_{\mathit{ij}}^e\right)\forall j,\forall i$$(13) (14) $$s{t}_{jl+1}\ge s{t}_{\mathit{jl}}+t_l^p\forall j,\forall i$$(14)

For a scheme to be feasible, one flight can only be assigned to one gate that can accommodate the flight Equations (8) and (9). The flight cannot depart the gate until all the freight or passengers are on the flight and it cannot depart early Equations (12) and (13). Once the flight is ready to depart, there must be a segment ready to accept the flight Equation (7). Once the flight is taxiing, it must complete one segment before moving to the next Equation (8) and the segment must be available to receive the flight Equation (6). In order for the problem to be feasible, all departure times, both scheduled and actual, must be non-negative and all travel times must be positive Equations (15) and (16).(15) $$p_{\mathit{ij}}^e,t{e}_{\mathit{je}},s{t}_{\mathit{il}}\ge 0\forall i,\forall j,\forall l$$(15) (16) $$t_l^p>0\forall i,\forall j,\forall l$$(16)

The gate delay is the difference between the pushback time and the schedule time Equation (4) with the pushback time being greater than the schedules time Equation (12). The gate delay must be a non-negative number as defined by Equations (10) and (12). The taxi delay is defined as the difference between the time the flight exits the system and the time it should have exited the system with no interference Equation (4). The gate delay must be non-negative Equation (10).

3.5. Stochastic model

The problem definition in Section 3.1 represents the deterministic approach and provides a static view of the problem and the process times. When trying to accommodate variances in travel times, a stochastic model will need to be implemented. Integrating the stochastic model requires modifying two groupings of times, the travel time to the aircraft and the taxi time. When comparing the results, the random variable is applied to the modelled times, not the standard times. This allows variation in the “actual” times when compared to the plan or standard times.

To achieve this integration, the travel time from the sort location (or the arriving gate in the case of passengers) to the departure gate, is modified or adjusted in accordance with the applicable pdf.

$a_{\mathit{ikjp}}^e$ is defined as the arrival time of a piece of freight (or passenger) at the departure gate i and includes the arrival time or release of the passenger or freight into the system along with the travel time from the entrance location k. Let sc_p be defined as the clock time when the sort operations are complete and freight piece p is ready to move to the gate (that passenger p enters the system) and tt_ikjp be defined as the travel time of freight piece or passenger p from sort location (or passenger gate) k to departure gate i for flight j. For freight operations, sc_p is constant for all pieces of freight. $a_{\mathit{ikjp}}^e$ is now defined as:(17) $$a_{\mathit{ikjp}}^e=s{c}_p+t{t}_{\mathit{ikjp}}$$(17)

In applying the stochastic model, the travel will be modified by the appropriate pdf, f(x).(18) $$a_{\mathit{ikjp}}^e=s{c}_p+f(x)\times t{t}_{\mathit{ikjp}}$$(18)

Applying a pdf to the travel time, the deterministic case in Equation (10) for freight p from sort location k to departure gate i for flight j becomes:(19) $$\text{Max}(s{c}_p+f(x)\times t{t}_{\mathit{ikjp}})\text{for all passengers/freight}p\text{arriving at departure gate}i\text{for flight}j$$(19)

For the deterministic case, the modeled taxi time is defined as:(20) $$t_{\mathit{jie}}^m=\sum _{l\in R(ie)}{t}_{\mathit{jl}}^m$$(20)

In the stochastic case the segment travel time $t_l^m$ is computed as: (21) $$t_l^m=t{e}_l^m-t{e}_{l-1}^m$$(21)

where the exit time for the flight is computed using the triangular distribution with the planned transit time, $t_l^p$, and the minimum and maximum transit times as defined by local conditions.(22) $$t{e}_l^m=max\left\{\begin{array}{c}t{e}_{l-1}^m+triangle\left(tmi{n}_l^p,t_l^p,tma{x}_l^p\right)\hfill \\ t{e}_{l+1}^m\hfill \end{array}\right\}$$(22)

The exit time for a segment is the maximum of either the exit time from the preceding segment plus the travel time or when the next segment is available due to blocking.

3.6. Job shop approach

The basic solution algorithm for the aircraft taxi portion of the gate assignment problem can be translated to the job shop scheduling format where an aircraft moving through the system is considered a job that starts at an assigned gate. As the aircraft moves through the system, each segment of the taxi path provides a point where time is accumulated in the same fashion as a job being processed by a machine. The time required to move through each taxi segment is effectively the processing time for the flight at that segment. Each gate and therefore each flight will have a defined taxi path with the gate determining the entry point into the taxi path with Equation (7) defining the time an aircraft enters the system and Equation (20) providing the time required to move through the system. The results from the job shop problem determines the makespan for the sequence of jobs.

3.7. Data requirements

Any optimization effort relies on a certain amount of data. As discussed by Castaing et al. (2016), finding usable historical data may not be possible. As with any operation that runs on a network and schedule, like airlines, truck lines, and trains, using historical data can be problematic. The challenges include changes in the schedule, operational issues such as weather and equipment failure. With this in mind, data from a number of data sources are required to support the solution process. These sources include an inventory of gates, an inventory of flights, a travel time matrix, and a taxi time matrix.

Gate inventory information includes a gate identifier (typically the gate number), definition of where each gate enters the taxi process (which segment), and a list of the constraints for each gate which influences flight assignment (e.g. aircraft size restrictions and service availability). While it would be ideal to have each gate capable of accommodating every flight, that approach does not efficiently use the available land. Therefore, size restrictions exist for each gate. As well, some flights may not be serviceable from tankers (due to the amount of fuel to be transferred) and thus cannot be assigned to certain gates.

The flight inventory is similar to the gate inventory, identifying the flight and the required services that will impact the assigned gate. While it would be preferable for every aircraft to be the same, operations will dictate different sized aircraft to serve various routes. This size variation will impact the number of available gates.

A travel matrix defines the distance the freight or passengers will travel from point of entry into the system to the departing flight. In the case of passengers, this is either the ticketing area or the connecting flight gate (arriving), while for freight processes, this is the point where the freight is placed in shipping containers or pallets for loading on the flight. The taxi matrix provides details on the taxi path a flight will follow from the gate (e.g. G5) to the point where the flight exits the system (e.g. S1 in Figure 2). This matrix will be based on the individual travel segments and the time required for traversing the segment. The matrix will also identify the previous and next segments to establish a travel order or path.

Figure 2. Taxi flow.

3.8. Algorithm

For this problem, a genetic algorithm was applied with a chromosome representing the gate assignments for a single test scenario. The data is coded with each element of the chromosome representing a gate and the ID of its assigned flight. Given the initial gate and flight information, all flights are ordered by size from largest to smallest (or most restrictive to least) and then assigned to gates to create the initial population. When generating possible solutions, the system will only assign flights to gates with sufficient capacity to accommodate the flight. Enforcing feasibility at the point where a flight is assigned to a gate enhances the efficiency of the algorithm. If a suitable gate is not available for the flight, the solution is infeasible and the processing of the solution scheme is terminated, avoiding scoring or further actions on an infeasible scheme.

After producing the initial population, each scheme in the population is scored based on total delay that arises at two points in the system: (1) the time required to prepare the flight for departure (moving the last passengers or freight to the flight and those actions required to close out the flight and turn it over to the flight crew for departure or pushback) and (2) taxi time to move from the gate to the point of exit from the system. The time to traverse a travel segment is measured and compared to the planned or standard time required to move through the segment. The travel time through a segment is defined as a triangle distribution using the planned time as the mean and the minimum and maximum values set as plus/minus user specified value of that mean. For the deterministic runs, the travel times were set equal to their mean.

With the initial population scored, the population is sorted in ascending order based on delay. The scheme with the minimum is the initial model solution. With the optimal scheme defined as one with zero delay, the model ends if the initial population contains a scheme that has zero delay minutes. Otherwise, the models begin the search to find the minimum solution using a variation of the genetic algorithm (GA). Given the ordered population, two parents are randomly selected from the population with equal probability. A cross operation is performed to generate a new scheme using a randomly selected point for the recombination. The new scheme’s fitness is scored and added to the population. It is possible that the cross operation result in a scheme that is infeasible. Consider a simple example that starts with the two parents found in Figure 3.

Figure 3. Sample 2 parent chromosome.

If the cut occurs between gates A3 and A4, then the resulting child in Figure 4.

Figure 4. Initial cross result.

Note that flights 101 and 108 appear twice. Since a flight cannot be assigned to two gates, the gates from Parent 1 take precedent, so the flights for gates A4 and A6 will be filled with the missing flights moving from left to right resulting in the assignment of flights 123 and 132 to arrive at a complete feasible solution (Figure 5). At each point, feasibility is reviewed and enforced.

Figure 5. Final cross result.

In each generation, one scheme is selected for mutation and two randomly selected flights are swapped to create a new scheme for the population. Given it is possible that a flight not fit a gate, prior to the swap, the system will check feasibility and continue to randomly select flights until a viable swap is determined. At the end of the mutation, the schemes in the population are sorted in ascending order based on the total delay time and the top N schemes considered in the next generation (where N is the population size).

4. Results and discussion

4.1. Problem definition

A sample ramp (or apron) and schedule representing a freight operation of 61 gates and 55 flights used for this study based on an actual ramp configuration and airline schedule. With this type of problem, the number of steps for achieving the optimum solution as well as the operating time will increase with problem size. With the increasing time, being able to decompose the problem into sub-problems can improve the solution time and will be the focus of this research (Maharjan & Matis, 2012).

The general layout of the ramp complex and traffic management schemes provide for a series of taxiway segments for a flight to move from the gate to the exit point. In cases where there may be multiple paths, a preferred path is generally used for most movement and the alternate paths are used when traffic or congestion require the alternate moves. These calls are generally made on a case-by-case basis during operations. For this approach, each gate along a specific taxi lane has a defined path, one way out. It is possible to define sub-problems composed of a set of gates with associated taxiways that are independent from another set of gates in that they have no common taxiway segments. With each sub-problem being independent, it can be optimized and, when added to the optimized times for the other sub-problems, produce an optimized result for the total problem.

The experimentation will investigate two cases. Case 1 is composed of sub-cases where the size of each sub-case is based on the size of the gates, the type of aircraft that can use the gates, and the taxi path (geographical location). Each of these sub-cases, by their composition and size, presents an easier problem to solve with a smaller search space. Case 2 considers the entire facility and is composed of all the gates and flights within the sub-cases of Case 1. The definition of the cases can be found in Table 1.

Table 1. Case definitions

Case	Sub-case	Number of gates	Number of flights
1	1a	7	7
	1b	12	11
	1c	42	37
2	2	61	55

4.2. Results

For this problem, the two parameters that drive the solution quality and ultimately the solution time are the position of the aircraft (gate assigned) and the relationship of an individual flight to the other flights in the data-set. The experiment consisted of 30 runs of the model for each of the four subcases while varying the number of schemes in the initial population between sizes of five, seven, nine, and eleven schemes. Each experiment was initially populated from the same set of assignment schemes (group 1 scheme 1 is the same in all experiments). It was of interest to determine how the initial population size affected the run time of the system. A larger initial population size would increase the odds that an acceptable solution would be found earlier, but at the expense of an increase in run time required to process the extra population members.

The model was run on a Dell PC with an Intel Core I5-2400 CPU @ 3.1 Ghz with 4 GB of RAM. In each replication, the model achieved the optimized value (zero delay). Two operational times were measured as part of the model, the time to generate the initial population and the time to reach the optimal value using the GA.

Table 2 lists the results for the four different population sizes using a ±5% spread of the upper and lower bounds on the travel time distribution. The optimized column shows the number of runs or problems where the optimal value (zero delay) was found either in the initial population or as a result of the local search. The run time values represent the average performance of a given set of parameters and schemes over the 30 runs.

Table 2. Results based on population size (±5% spread)

		Stochastic						Deterministic
		Optimized		Run time				Optimized		Run time
Case	Number initial schemes	Initial	Local search	Initial (s)		Local search (s)		Initial	Local search	Initial (s)	Local search (s)
				Mean	S.D	Mean	S.D.
1a	5	30	0	0.54	0.02			30	0	0.43
1b	5	30	0	0.65	0.02			30	0	0.53
1c	5	0	30	1.86	0.02	6.08	6.22	0	30	1.82	5.93
2	5	0	30	2.60	0.02	11.72	13.85	0	30	2.42	10.84
1a	7	30	0	0.76	0.01			30	0	0.58
1b	7	30	0	0.93	0.02			30	0	0.70
1c	7	0	30	2.74	0.03	10.58	10.71	0	30	2.48	9.41
2	7	0	30	3.65	0.04	11.77	14.29	0	30	3.20	10.22
1a	9	30	0	0.98	0.01			30	0	0.76
1b	9	30	0	1.19	0.02			30	0	0.93
1c	9	0	30	3.44	0.03	14.47	15.97	0	30	3.26	13.61
2	9	0	30	4.70	0.04	17.26	17.96	0	30	4.08	15.01
1a	11	30	0	1.19	0.02			30	0	0.91
1b	11	30	0	1.46	0.03			30	0	1.11
1c	11	0	30	4.36	0.04	19.87	22.86	0	30	3.85	17.39
2	11	0	30	5.53	0.07	19.49	18.15	0	30	4.97	17.51

The results in Table 2 show that for both the deterministic and stochastic modes, increases in the initial population size drives longer run times, with the deterministic process requiring less time than the stochastic approach. In addition to the time increases due to initial population size, as expected increases in the number of flights/gates used by the model increases model run times. (With the model run times measured in seconds, the background processes running on the computer, as well as size of the data files, can impact the results and conclusions.) However, looking at the overall run times (Figure 6), the sub-case approach yields a solution in shorter run time. When considering just the local search, the sub-case approach will optimize with shorter run times than the complete case 1c vs. case 2, except when the a population size of 11 is used, wherein the time for the case 1c is 0.38 s longer.

Figure 6. Total run time by population size.

Across all population sizes, the difference in the local search times between the deterministic and stochastic approaches never exceeds 2.4 s. This means that there are subtle factors impacting the solution time. These factors have been discussed earlier and include the environment interaction, the quality of the initial schemes, and where the cuts are made for reach data-set.

To investigate the effects of the spread of the upper and lower bounds on the triangular distribution, in addition to ±5%, runs were also made at ±10, and ±15%. Figure 7 shows the results for cases 1c and 2 for an initial population size of 5 schemes. These results show that for Case 1c there is not much impact, but for Case 2 the run time decreases with the increase in the spread. This decrease in run time can be tied to the variable nature of the taxi times and the impact on the scheduled departure times. Independent of the spread, the solution procedure always produced an optimal result with a run time of less than 15 s and was able to accommodate large sized problems.

Figure 7. Total run time, 5 scheme initial population.

4.3. Cross and mutation

One of the challenges or dangers facing the use of heuristic solution techniques is to ensure the solution is a system or global optimum and not a local optimum. The cross and mutation operations of the GA combat this occurrence. As seen in Figure 8, each operation settles on the local value and eventually achieves the defined system optimal.

Figure 8. Model convergence, case 2, 7 scheme initial population.

Unlike GAs where a mutation operation is traditionally used a small percentage of the time, this model applies the mutation process in each generation. As shown in Table 3, it was found that as the percentage of iterations where the mutation is used increases, the operation time and number of iterations required to achieve the optimum decreases. In each scenario, the model achieves the optimal solution.

Table 3. Mutation percentage impact on solution

Percent mutation (%)	Operation time (s)			Number of generations
	Min	Average	Max	Min	Average	Max
20	0.67	29.43	83.18	8	92.33	250
50	0.34	15.80	67.97	7	50.37	195
100	0.34	6.08	20.33	7	23.60	65

As with any problem, the viability of the solution technique and the benefit of the solution technique should be investigated. With this research, the proposed genetic algorithm was compared to generating schemes randomly. With the stochastic approach using just a 5% variation in the travel speeds, the randomly generated technique failed to arrive at a zero delay solution within 2000 generations while the GA found it within 30 generations (Table 4). Increasing the travel speed variation to 10 and 15% still resulted in the framework yielding optimal solutions within 20 s, as documented in Tables 5 and 6, respectively).

Table 4. Compare random search to genetic algorithm search

Case	Search	Run time (mm:ss)	Number of children
1c	Random	14:06.2	2000
2	Random	18:05.4	2000
1c	Genetic	00:04.8	20.20
2	Genetic	00:10.8	31.20

Table 5. Results by population size, ±10% upper and lower bounds

		Optimized		Run time
Case	Number initial schemes	Initial	Local search	Initial		Local search
				Mean	S.D.	Mean	S.D.
1a	5	30	0	0.56	.01
1b	5	30	0	0.68	.01
1c	5	0	30	1.98	.03	6.52	6.66
2	5	0	30	2.49	.04	11.22	13.27
1a	7	30	0	0.76	.02
1b	7	30	0	0.93	.02
1c	7	0	30	2.68	.04	10.31	10.41
2	7	0	30	3.44	.03	11.13	13.57
1a	9	30	0	0.98	.02
1b	9	30	0	1.18	.02
1c	9	0	30	3.44	.04	14.40	15.26
2	9	0	30	4.50	.04	16.66	17.31
1a	11	30	0	1.18	.02
1b	11	30	0	1.44	.02
1c	11	0	30	4.22	.05	19.22	22.08
2	11	0	30	5.40	.09	19.12	17.77

Table 6. Results by population size, ±15% upper and lower bounds

		Optimized		Run time
Case	Number initial schemes	Initial	Local search	Initial		Local search
				Mean	S.D.	Mean	S.D.
1a	5	30	0	0.55	.02
1b	5	30	0	0.66	.01
1c	5	0	30	1.93	.04	6.30	6.45
2	5	0	30	2.38	.04	10.68	12.68
1a	7	30	0	0.79	.02
1b	7	30	0	0.95	.02
1c	7	0	30	2.72	.03	10.38	10.54
2	7	0	30	3.38	.12	10.94	13.48
1a	9	30	0	1.01	.02
1b	9	30	0	1.22	.02
1c	9	0	30	3.50	.04	14.54	15.39
2	9	0	30	4.37	.10	16.14	16.86
1a	11	30	0	1.18	.02
1b	11	30	0	1.42	.02
1c	11	0	30	4.19	.19	18.82	21.68
2	11	0	30	5.34	.06	18.83	17.59

In addition to comparing the genetic algorithm to a purely random approach, this research compares the performance of the proposed genetic algorithm with a simulated annealing approach. As shown in Table 7, when compared at the 5% level of variation in travel speeds, simulating annealing does not optimize the problem. As seen in Figure 8, there is a tendency of the model to plateau or reach a local optimum. The cross function of the GA allows the solution process to jump from the local optimum a reach a global optimum.

Table 7. Simulated annealing results, ±5% upper and lower bounds

		Optimized		Operation time
Case	Number of replications	Initial	Local search	Initial
				Mean	S.D.
1a	30	30	0	0.13	0.35
1b	30	26	4	0.47	1.22
1c	30	0	0	120.87	4.37

4.4. Discussion

While the problem addressed here reflects a freight airline, the proposed problem formulation and solution technique can be used for both passenger and freight operations with an airline operating in a hub and spoke environment. One of the major costs to an airline is the purchase and operation of the aircraft. With the associated costs of perturbations to the schedule and overall operations that deviate from the schedule, efficiently managing the flow of freight or passengers as well as the flow of aircraft is critical to the overall management of costs.

When modeling an existing process, there will always be a discussion on whether to use schedule data or actual historical data. When operating an airline, the actual operating items vary based on events such as weather, the actual gate used, and aircraft size used for a specific flight. In addition to these sources of variation in the actual data, it is important to run the airline on schedule. With these considerations, schedule data is used throughout the modeling environment.

Applying this same logic, use of existing planning data relies on an available data source that is accepted, adding validity to the solution process and results. Since this data is deterministic in nature, it tends to preclude the use of a stochastic model. When the plan is executed, natural variances will occur that may not have been anticipated or included in the modeling environment. Attempting to cover all sources of variation may make modeling the stochastic case difficult with little or no overall benefit when compared to the deterministic process.

Most schedules are developed to meet certain market, business, and operational goals. With this in mind, meeting the schedule is imperative. This process can provide a number of optimal solutions within the search space, keeping in mind that the goal is zero delay, not the absolute minimum. Part of schedule development is controlled by an airport’s ability to allow flights to take off. The degree of time separation of the departing flights will also impact the number of potential optimal solutions. The degree that these conditions exist drives the model’s ability to locate one of the optimal solutions.

With any large problem, one technique to be used is to subdivide the primary problem into smaller, solvable problems. With this problem, the subdivision is based on independence. In this case, the sub-problems are defined by a grouping of flights and gates that do not share members with other groupings. In this way, each sub-problem can be solved separately. For example, if there are a number of Airbus A-380 aircraft in the schedule and there are a fixed number of gates that can accommodate this aircraft, these can be considered independent if and only if the gates and taxi paths are only used by the A-380. The net impact of the subdividing of the problem is that the search space is reduced and there are less combinations to be evaluated. Because the individual sub-problems are independent, the optimized results can be added together to generate an optimized solution for the bigger problem. With most airlines operating aircraft fleets ranging in size from the smaller regional jets to the larger trunk aircraft such as the Airbus A-350 and Boeing 777 in a hub and spoke operation, it is highly likely that independence will exist in most situations.

Most optimization problems focus of finding either the maximum or minimum value. When using heuristics, the routines run until a determination is made that the answer is not improving (the stopping criteria). When operating an airline it is imperative that the airline operate on schedule. Arriving too early may mean that the gate at the destination may not be available. Additionally, departing early and moving across the ramp can cause the same type of issues as departing late, resulting in delays where an on time flight becomes late. With this in mind, optimality is defined as zero delays and the model terminates when this condition is achieved, resulting in faster run times.

Based on the data presented, both the deterministic and stochastic approaches produce optimal results. With the stochastic approach, the size of the initial population determines which case produces the faster result (case 1 vs. case 2). With the manual assignment process taking in excess of 1 h, solution times on the order of 10–20 s represents a significant improvement.

5. Conclusion

The increase in demand for efficient use of the air traffic system and operational equipment requires that airlines operate in more economical ways, meaning control of operational costs becomes a high priority. While numerous parts of the air traffic system are not controllable by the airlines, the movement around the ramp area, as well as gate usage can be leveraged to gain operational efficiency. Decision support models aid in the decision process to gain and leverage these efficiencies. Past research has been restricted to treating aircraft movement around the airport and gate assignments as separate research areas with no interaction. This research provides a framework for integrating the gate assignment and airport movement problems into a unified problem definition and solution using total delay minutes. The framework considers the impact on moving freight to the aircraft and moving the aircraft from the gate to a hand-off point as it taxis out. Within the operating environment, departing early has an adverse impact on operations, so the best or optimized solution is measured as an on time departure with no delays. With the problem defined, a genetic algorithm was developed to solve the sample problem and provide optimal results. Based on multiple runs of the model, the proposed framework and algorithm achieve the defined optimal value within 26 s.

In this study, we investigated and compared the use of random selection, simulated annealing and a genetic algorithm for finding a solution. Of these methods, the GA was the fastest at producing an optimized solution. When varying the number of schemes used to initialize the system and used as the active population of the GA, the size was found to not impact optimization, but it did impact solution time. We investigated the robustness of the framework and solution approach by introducing variation into the system. The GA was able to optimize the problem under different degrees of travel time variation. Use of simulated annealing showed that the optimizing process reaches a plateau or local optimum. Due to this characteristic, the GA proved to be effective in moving from the local optimum. Based on the results, the proposed framework was shown to generate a robust model that produces an optimal result using a GA with an initial population size of 5 and a 100% mutation rate. The practical application of this approach to the gate assignment problem provides a shortened time to solution when compared to existing manual processes, which can take in excess of 1 h to make the same level of assignments as the complete problem. Using the longest run time, this represents an improvement in excess of 13,000%. In a business decision-making environment, the results of this modelling framework provides data used to evaluate various operation options.

Future research will expand the impact on departure to include consideration of grouping aircraft in gate clusters to support other operational or scheduling concerns as well as measuring the impact of support equipment availability on the delays.

Funding

The authors received no direct funding for this research.

Additional information

Notes on contributors

John Behrends

John Behrends is an Engineer in the shipping and logistics industry. He has a Bachelor of Science degree in Industrial Engineering from Mississippi State University, a Master of Science in Engineering Management from Missouri University of Science and Technology, and a PhD from Mississippi State University, with his studies emphasizing modelling and simulation. Dr Behrends’ research focuses on modelling within the aircraft and airline industry. Dr Behrends is a licensed aircraft dispatcher.

John M. Usher

John M. Usher currently serves as Professor and Head of the Industrial & Systems Engineering department at Mississippi State University. He received his PhD in Engineering Sciences at Louisiana State University, where he also earned master’s degrees in both Chemical and Industrial Engineering. As well, he has a bachelor’s degree in Chemical Engineering from the University of Florida. John’s research interests focus on production systems and systems simulation, modelling, and analysis, with applications in both manufacturing and transportation.