ABSTRACT

This paper presents a short contribution in air transportation, specifically in scheduling aircraft (plane) landings at Léopol Sédar Senghor (LSS) airport of Dakar. The safety of air navigation of LSS is managed by ASECNA: Agency for Air Navigation Safety in Africa and Madagascar. Scheduling aircraft landing is the problem of deciding a landing time on an appropriate runway for each aircraft in a given set of aircraft such that each aircraft lands within a predetermined time window. The separation criteria between the landing of an aircraft, and the landing of all successive aircraft, are respected. Our objective is to minimize the cost of deviation from the target times. We present a mixed-integer 0 - 1 formulation for the single runway case. Numerical experiments and comparisons based on real datasets of LSS airport are presented.

1. Introduction

The domain of air navigation is rich in optimization problems. In this paper, we study the problem of efficiently scheduling the landing times of aircraft at the Léopol Sédar Senghor (LSS) airport in Dakar. < > (ASECNA) was founded in 1959. It is a multinational organization, created by 16 African countries, 14 from Western and Central Africa, plus Madagascar, and France (see Figure 1). The group was joined by the Comorian Union in 2004. The agency is presented as the best example of North to South cooperation, as well as the structure for civil aviation excellence. ASECNA has managed to last more than half a century because it adapted itself to the political and economic context. In addition of its mission of ensuring the safety of air navigation, the Agency provides also meteorological services necessary for operations of air navigation. ASECNA manages an area of more than 16 million square kilometers characterized by a weak network of altitude measuring stations.

Air France-KLM is the dominant carrier on the long haul market. It serves all ASECNA’s main airports. Swiss, SN Brussels, Iberia, Lufthansa and Alitalia also regularly flight to the region. In fact, about 80 percent of the commercial traffic is operated by these carriers. More details about ASECNA structures and activities can be found in [1,2].

ASECNA is responsible for guiding aircraft in an equitable, safe and efficient manner. Flights approaching LSS airport are under the guidance of the approach controller, when they enter the so-called radar range of the airport. From this moment, the controller must create a correctly separated flow of aircraft towards the runway. To maintain safety, a minimum separation between landing aircraft is required. This separation depends on the weight categories of the aircraft. The aircraft landing problem is one of determining a landing time for each plane such that each plane in ASECNA horizon lands within a prespecified landing time window, bounded by an earliest time and a latest time. LSS airport of Dakar is one of the main airports of ASECNA. It is served by major regional, continental and intercontinental airlines. During the last ten years, traffic in this airport has continuously grown. The number of aircraft movements has increased by 8 percent per year on average. The service provided is acceptable, but can be improved; because ASECNA must anticipate these mutations, and their foreseeable impact on the air navigation system, and articulate its strategy to match the exigencies.

In such a situation, help can be provided to the air traffic controller by presenting him a set of solutions. The results presented in this paper are part of a study (partnership) that was done together with ASECNA.

The landing time is bounded by an earliest time and a latest time (these times may being different for different

planes). The earliest time represents: the earliest time a plane can land if it flies at its maximum airspeed. The latest time represents: the latest time a plane can land if flies at its most fuel efficient airspeed while also holding for the maximum allowable time. The main objective is the punctuality which is an important issue for airlines and their passengers.

There are many variants of the aircraft landing problem and many approaches for solving it. The problem is presented first in [3]. They give an extensive literature overview on the aircraft landing problem. In the works [3-5], they are considering both single and multiple runway formulations. Their objective is to minimize the (weighted) deviation from the preferred arrival time or the total timespan. Equity among airlines is not (explicitly) considered. They give a mixed integer programming formulation and use several heuristics to solve the problem, such as using a heuristic upperbound for a three search and restarting the branch and bound algorithm [3] and genetic algorithms [4]. Another article [5] presents a dynamic formulation that includes additional cost for perturbing earlier schedules.

In [6], they consider the tactical single runway arrival problem. They focus on collaborative decision making reflected by giving airlines the possibility to provide cost functions related to arrival delays for their flights. Artiouchine et al. [7] consider the landing problem with holding patterns, implying the possibility to delay certain flights using detours of fixed lengths (possibly performed multiple times) before landing. This gives a set of time intervals for each flight in which the landing is possible. The problem is solved by a branch and cut approach.

Carr et al. analyze the effect of using sequence preferences from airlines for their own aircraft [8] and of exchanging delays [9], using simulations. Their results indicate that both can be done while causing little or no decrease in efficiency.

The single airport ground holding problem is considered in various articles. Hoffman and Ball [10] compare different formulations of the problem, minimizing the weighted delay. Richetta [11] consider different cost rates for airborne and ground delays. These papers consider the problem on a flight-basis, and equity between airlines is not explicitly considered. Vossen et al. consider the ground holding problem by assigning arrival slots (time intervals) to flights. Flights are first assigned to slots based on scheduled arrival times. The airlines are now considered as the owner of these slots. In case of delays (or cancellations) the slots can be redistributed, by minimizing the deviation (per airline) between the actual and the first allocation [12] or by mediated slot trading among airlines [13].

Andreatta et al. [14] consider the multi airport ground holding problem. Their aim is to improve the application of these models, by introducing simple, easy to understand heuristics. Each heuristic is based on a specific “priority rule’’.

As in [3] and [15], we are only interested in modeling the decision problem here, that is we are only interested in deriving, for each plane, a landing time. Along with this, ASECNA controllers must also determine solutions to the control problem of how to land the planes. The main objectives are maximizing the throughput of the runways, minimizing inbound delays and minimizing also cost of deviation from the target times. One difficult issue is the choice of an appropriate objective function.

Actually, the existing solution techniques for the ASECNA controller used are based on a radar and system aurocatx formulation. We want to know how good other optimization methods are suited for ASECNA.

In this paper, we consider the problem of scheduling aircraft (plane) landings at LSS airport. This problem is one of deciding a landing time for each plane such that each plane lands within a predetermined time window and separation criteria are respected. We are dealing only with the off-line case where we have complete knowledge of the set of planes that are going to land. We present a mixed-integer 0 - 1 formulation of the problem for the single runway case.

In the next section, we present the model that minimizes the cost of deviation from the target times. In Section 3, we present numerical results using the IBMCPLEX’s MILP solver (with the real data of ASECNA). Finally, summary and conclusions are presented in Section 4.

2. Formulation of the Aircraft Landings

The model can be used to determine an arrival times for a given set of flights on a single runway, complying with the separation rules. The flights are already assigned to a runway. We assume for each flight that there is a closed time interval for each flight in which the landing will take place. More details concerning the Mixed Integer Programming (MIP) formulation of the aircraft landings model can be found in [3].

2.1. Notations

The following notations are used to describe procedures for scheduling aircraft landings.

Indices-Parameters-Sets:

: number of arriving planes to schedule

: earliest possible landing time for plane ()

: latest possible landing time for plane ()

: target (preferred) landing time for plane ()

: required separation time () when plane lands before plane,;

: penalty cost () per unit of time for landing before the target time for plane ()

: penalty cost () per unit of time for landing after the target time for plane ()

Using the separation times and (overlap of) possible landing time intervals we can define three sets of pairs of flights:

: set of pairs of planes for which it is uncertain whether plane i lands before plane j.

: the set of pairs of planes for which definitely lands before, but for which the separation is not automatically satisfied.

: the set of pairs of planes for which aircraft definitely lands before plane, and the separation is automatically satisfied.

More formally:

Decision Variables:

: landing time for plane ()

: how soon plane () lands before.

: how soon plane () lands after

: binary variable which becomes 1 if plane lands before plane (), 0 otherwise.

2.2. Problem Formulation

The complete formulation (model) of the single runway problem is formulated as follows:

(1)

subject to

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

The objective function (1) minimizes the cost of deviation from the target times. It is a linear objective function. Constraint (2) is effective only when either plane must land before plane (equals one) or plane must land before plane (equals one). For elements in the set and the order of the planes is known. So trivially the constraints (3) hold. Constraint (4) ensures that a time must elapse after the landing of plane at before plane can land at. Constraint (5) ensures separation if the order of the flights is not known (pairs of flights in set). Constraints (6) and (7) ensure that is at least as big as zero and the time difference between and, and at most the time difference between and. Constraints (8) and (9) are similar equations for. Constraint (10) relates the landing time to the time lands before, or after, target. Constraint (11) ensures that each plane lands within its time window. Constraints (12), (13) and (14) represent the domains of the variables.

3. Computational Results

In this section, it is shown how optimization tools are suited for ASECNA controllers, compared with their actual existing solution techniques based on a radar and formulation of system aurocatx.

ASECNA ensures the control of air navigation flows, aircraft guidance, transmission of technical and traffic messages, airborne information etc. This includes ground aircraft guidance and movements, and approach control. Theses services are delivered for en route, terminal approach and landing phases of flights.

Consider the planes within the radar horizon of ASECNA at LSS airport. Typically, the controller is in charge of determining approach paths, runway allocation, and landing times of several planes in the radar horizon. Each of these planes has a preferred landing time (earliest and latest possible landing times). Efficiency cannot be considered as the only objective, punctuality is an important issue for airlines and their passengers. For a specific flight by an airline: the transfer times of the passengers, the propagation of the delay and the fuel cost can also play a role in the valuation of an arrival delay. The main objective is to minimize the cost of deviation from the target times with respect to separation and earliest/latest possible landing times.

Recall that the input data needed to use the model are:

• number of arriving planes

• earliest possible landing time vector

• latest possible landing time vector

• preferred landing time vector

• time-separation matrix

• penalty cost vector for landing before the target time

• penalty cost vector for landing after the target time

• aircraft size and type.

All realistic scenarios are given by ASECNA from data related to the flow of arrival traffic. Nevertheless, one difficult issue is the choice of an appropriate objective function to be able to measure the quality of different aircraft sequences.

The cost incurred by an airline for an arriving flight depends on its landing time. Every flight may have different characteristics, such as the number of transfer passengers and their transfer times etc. Therefore, the airline is allowed to provide a separate cost function for every individual flight.

The considered costs can vary a lot between different airlines. However, we allow all airlines as much flexibility as possible to define their own cost functions. At the same time the functions need to be suitable to determine an equitable arrival schedule.

The costs vary according to the operational conditions, in particular: the phase of flight where the delay occurs, aircraft size and type, and the load factor.

Airlines try to manage their costs by reducing delays, and their financial impacts, at all levels of planning from the strategic phase, through to pre-departure slot management, and into the airborne phase of the flight. Delay recovery and fuel burn are related through the cost index. The cost index is a parameter set in the cockpit, which determines how the flight management system will direct the aircraft. It quantifies the choice to fly faster to recover delay, or to fly slower to conserve fuel.

Most comprehensive report on the cost of delays in the air traffic management system can be found in [16,17].

We considered two sets of test problems on separate days. The first set, involved 16 aircraft. The second set we considered were more large, involving 36 aircraft.

For the first set, the day we consider is Friday (day where traffic is very important); and the time-period we consider is between 03:00 PM and 02:50 AM. This implies that we schedule aircraft in batches, between 03:00 PM and 06:35 PM for the first batch, then between 11:20 PM and 02:50 AM for the second.

For the number of arriving planes: the assumed arrival rates for the two aircraft batches are 8 aircraft between 03:00 PM and 06:35 PM, and 8 aircraft between 11:20 PM and 02:50 AM (see Table 1), respectively.

For the second set (seperate day), three scenarios are considered during the second FESMAN (World Festival of Black Arts and Cultures) edition, where traffic has increased considerably. The time-period we consider is between 10:45 AM and 05:50 PM. This implies that we schedule aircraft in batches, between 10:45 AM and 01:43 PM for the first batch, then between 00:20 PM and 01:43 PM for the second, and between 03:20 PM and 05:50 PM for the third.

For the number of arriving planes: the assumed arrival rates for the three aircraft batches are 15 aircraft between 10:45 AM and 01:43 PM, 10 aircraft between 00:20 and 01:43 PM, and 11 aircraft between 03:20 and 05:50 PM (see Table 2), respectively.

The landing time between any two aircraft pairs in the horizon must be greater than some minimum interval. This

minimum separation is the same for all aircraft types and for all pairs of aircraft in the horizon. This minimum separation distance is 8.0 min.

The problem formulation in Section 2 is a mixedinteger 0 - 1 program involving 3i continuous variables, at most  n(n – 1) binary 0 - 1 variables and at most constraints (excluding bounds on variables).

The aircraft landings model outlined in this paper is programmed in C++. In order to solve the mixed-integer 0 - 1 formulation of the problem to optimality, we use the commercial MILP solver, namely IBM-CPLEX V12.3 [18], for a number of test problems involving up to 36 aircraft and one runway. The numerical experiments are run on a personal computer with a 2.0 GHz CPU 2× Intel(R) Core(TM)2 Duo, on a Linux platform and 4.0 GB RAM.

To facilitate understanding, we present the scenario results separately.

For the first set, the number of aircraft is 8 for each scenario; and the optimal values are and, respectively.

Tables 3 and 4 show the preferred landing times, the actual times (optimal solution) and delays (counted positively). All times are given in minutes.

Only aircraft 2 (first scenario) and 2 (second scenario) land before and after their preferred landing times, for +5 and +8 minutes, respectively.

For the second set, the numbers of aircraft are 15, 10 and 11 respectively. The optimal values are 9.175000e+ 02, and, respectively.

Tables 5, 6 and 7 show the preferred landing times, the actual times and delays; and all times are given in minutes.

First scenario: aircraft 3, 9, 10 and 13 land before their preferred landing times, for +3, +7, +5 and +1 minutes, respectively. Then aircraft 12, 14 and 15 land after their preferred landing times, for +1, +2 and +5 minutes, respectively.

Second scenario: aircraft 4, 5 and 8 land before their

preferred landing times, for +7, +5, and +1 minutes, respectively. Then aircraft 7, 9 and 10 land after their preferred landing times, for +1, +2 and +5 minutes, respectively.

For the third scenario: the aircraft 4 and 10 land before their preferred landing times, for +2 and +3 minutes, respectively. Only aircraft 5 lands after its preferred landing times, for +1 minute.

In order to develop safely and orderly, ASECNA needs a reliable air navigation infrastructure and an adapted air navigation service provision for LSS airport.

Using these scenarios, we have demonstrated that the given procedure is flexible, can compute optimal solutions very quickly, and scales slowly and reliably with increase in number of aircraft.

The datasets lead to the improvement of the optimum value of the objective function and

• make possible to assist ASECNA controllers in making decisions

• globally improve the performance of the aircraft landing in LSS

• and support real time decisions.

4. Conclusion and Perspectives

We have studied formulation and simulations of the static aircraft landing problem for single runway case. We solved the related mixed-integer 0 - 1 linear program; and showed how the simulation techniques can be applied successfully to practical decision support of ASECNA, in a real-world setting at LSS international airport. Using some intances, we dicussed that ASECNA controllers can maximize the throughput of the runway system minimizing cost of deviation from the target times. Furthermore, we extend the formulation to the multiple runway case; and the subject of the dynamic or on-line case, where decisions about the landing times for planes must be made as time passes and the situation changes (planes land, new planes appear, etc.) will be study in a separate paper for LSS and the new airport of Dias.

5. Acknowledgements

We thank ASECNA’s specialists for the fruitful discussions. Also we would like to thank M. Gueye for providing the data, results validation, and discussions related to the meaning of the data.

REFERENCES