Final report on research carried out for the
Optimization of Aircraft Route Assignment in a Sectorless Environment
project
(Inspired by Telecommunication Network Routing).
Dritan Nace, Jacques Carlier
Heudiasyc Laboratory, UMR CNRS 6599,
University of Technology of Compiègne
July 2003
1
Table of contents
Abstract 3
1. Introduction 4
2. State of the art 5
2.1. Related works in the ATM and operations research areas 5
2.2. Telecommunication Network versus Airspace Network 8
3. Modeling and mathematical formulation 9
3.1. Designing the airspace network 9
3.2. Modeling 10
3.3. Mathematical Model 12
4. Sketch of a Resolution Method for Larger Instances 14
5. Concluding Remarks and Future Work 16
References 17
ANNEXE : 20
Abstract
In this intermediate report we present the work done on this project between October 1 2001 and September 30 2002. Our research concerns the route assignment problem aiming at global flight plan optimization, which has already become a key issue owing to the growth of air traffic. Better co-ordination of all existing flights for all airlines is becoming an increasingly desirable goal. A number of related problems appear in the operations research literature, notably vehicle routing, scheduling and other transportation problems. Several studies have been devoted to the problem of aircraft scheduling and routing. Aircraft routing requires the generation of non-colliding, time-dependent routes through a specified airspace that we call the airspace network. The problem considered in this project can be modeled as a specific flow problem in a given space-time network. This study aims at estimating the effects of routing capabilities at a quantitative level (the congestion level, i.e. the number of potential en-route conflicts and total possible delay), and at a qualitative level (traffic smoothing). This work is divided into two main parts with respect to the first two tasks defined in the paragraph “Schedule and Deliverables” of the contract.
First, we have looked at the state of the art, and in particular we have studied a large range of mathematical models used to represent the airspace network and related (routing) problems. We have also considered the ATM (Air Traffic Management) sectorless environment, which represents the context of this study. Another valuable source are the related ATFM (Air Traffic Flow Management) projects realized in the past or currently in progress at EEC (Eurocontrol Experimental Centre). This preliminary work was very useful in helping us to achieve an appropriate mathematical modeling.
Secondly, we have developed an appropriate mathematical model for this problem. We propose the use of dynamic network flow models, which, for our requirements, can accurately represent the aircraft routing problem. Such methods are already known in the operations research area, but we have introduced some changes in accordance with the objectives and constraints of the problem under consideration. We have also tried to take advantage of our experience in the routing area (more precisely, routing in circuit telecommunication networks), in order to develop a suitable model for ATM.
Keywords: Air Traffic Flow Management, trajectory-based environment, Operations Research, optimization, linear programming, routing.
1. Introduction
The route assignment problem, aiming at global flight plan optimization, has already become a key issue owing to the growth of air traffic. There is expected to be an increase of 5% in air traffic each year, so that traffic in 2015 will be double that of 1998 (see [24])
. Better co-ordination of all existing flights for all airlines is particularly necessary, given this growth. We address the problem of global flight plan optimization from a routing point of view (assigning the appropriate route and level to each flight) in a given airspace network. Our aim is to reduce the number of potential en-route conflicts. In some ways, this problem is very close to those addressed by ATFM. Indeed, the role of ATFM at EEC is to ensure that air traffic does not overtake the capacity of airports and ATC (Air Traffic Control) sectors. In Europe, this function is achieved by the CFMU (Central Flow Management Unit). When demand is higher than capacity in some ATC sectors, traffic must be regulated by delaying some flights through the slot allocation process. Another means is to re-route some flights in agreement with the airlines concerned. As we explain later, we do study the problem of optimization of route assignment, but in a sectorless environment (not the environment defined by ATC sectors).
The work we have done so far is the realization of the first two scheduled tasks, and it can be divided naturally into two main parts.
The first task was to realize a complete state of the art. In particular, we tried to study most if not all of the mathematical models used to represent the airspace network and the related routing problems. In order to become acquainted with the main requirements of flight planning, and more especially with the route assignment problem, we also studied past and present related ATFM projects at EEC. We also had several valuable discussions with ATC experts[1]. Another primary factor considered in this preliminary phase is the specific ATM context of this study, and we therefore discuss the modeling of the airspace in which the routing will take place. This study is intended to be compatible with the ATM sectorless environment. That is, we are mostly interested in designing air routes according to the way the control could be realized in response to the growing demand for air traffic, that is end-to-end and not local/decentralized (by sectors) which is applied actually. All this constitutes a rather good starting point for us to define a cost function from the economic and safety viewpoints. This preliminary work was also intended to facilitate the mathematical modeling.
Secondly, we developed a mathematical model for this problem. We propose the use of dynamic network flow models, which, for our requirements, can accurately represent this problem. Such methods are already known in the operations research area, but we have introduced some changes in accordance with the objectives and constraints of the problem under consideration. In this report we briefly review the dynamic network flow model of Ford and Fulkerson ([24]) and Ahuja et al ([1]), and discuss its application to ATM. At this stage, we have tried to take advantage of our experience in circuit telecommunication networks, in order to develop a suitable model for ATM.
It can easily be seen that the route assignment problem is a multi-period (dynamic) one. Indeed, the time dimension is an essential ingredient to consider when constructing flight plans for a large number of flights, and evaluating the number of potential en-route conflicts. Co-existing flights, especially those involved in the same cluster of en-route conflicts, usually have different origins, destinations, durations, takeoff and landing times. This dynamic problem can be transformed into a static one using the standard technique of time-expanding of the underlying network, (see [1]).
This report is organized as follows. After this introduction, in section 2 we report the state of the art, which comprises a number of related works in the operations research area and more especially in ATM. Furthermore, we analyze and compare telecommunication and airspace network models. The mathematical model is then presented in section 3. In section 4 we briefly describe three methods of integer and combinatorial optimization (cutting-plane approach, column or path generation and Benders decomposition) that will be very useful in the next stages of this work. Next, we report some discussions on their application on our model. Section 5 is devoted to some concluding remarks and future work on this project. Finally, we present as an annexe a paper entitled Using Dynamic Flow Network Modeling for Aircraft Route Assignment, accepted for presentation at the 21st DASC Digital Avionics Systems Conference, ([22]).
2. State of the art
2.1. Related works in the ATM and operations research areas
A number of related problems appear in the operations research literature, notably vehicle routing, scheduling and other transportation problems. Several studies are devoted to the problem of aircraft scheduling and routing. Aircraft routing has been subject of studies presented in [3], [4], [5], [6], [7], [23], [27], [29], [30], etc. Others concerned with ground holding (often presented as a scheduling problem) one are presented in [8], [9], [10], [11], [12] etc. Let us first cite Bertsimas and Stock ([3], [4]) who have considered the Air Traffic Flow Management Rerouting Problem (TFMRP), treating simultaneously the time and route assignment problems through an efficient deterministic approach. Delahaye and Odoni (see [5]) have considered this problem from a stochastic optimization point of view. They propose a genetic algorithm to resolve the whole problem. Barnier and Brisset ([7]), have considered the problem of flight level allocation to aircraft flows in order to ensure their separation. This can be stated as a graph-coloring problem, known to be NP-hard. Note that their study is confined to predefined direct routes, so there is one fixed route for each flight. In our study we intend to define a model to determine both routes and flight levels. Furthermore, in the next stage we shall take time assignment (i.e. time-slot allocation) into account.
Another widely-studied problem is time-slot allocation, known also as ground holding. Several studies are presented in [8], [10], [11], [12], [13]. We must also cite [14], which gives two relevant network-based models for Air Traffic Control.
Throughout these studies modeling variations can be distinguished, such as deterministic versus stochastic, and static versus dynamic models.
As for airspace network design, an interesting methodology has been reported in [15]. This study relies on Voronoy diagrams for modeling the network. The method described allows nodes to be located in the network with respect to ATC requirements and cost considerations.
Other interesting studies using linear programming techniques are presented in [16], [17], and more particularly the Dantzig-Wolfe and Benders decomposition for aircraft routing and crew scheduling, [18]. Even though these works are not directly related to our problem, they provide applications of the sort of fundamental decomposition approach that we intend to use for solving larger instances.
Studies in the operations research area, more precisely flows in networks (see [1]), are particularly interesting and useful for a deeper study of our problem. Indeed, aircraft routing requires the generation of non-colliding, time-dependent routes through a specified airspace that we call the airspace network. So the problem considered in this project can be modeled as a specific flow problem in a given space-time network. The primary difficulty is how to model such a network. Indeed, network and aircraft flow are in motion, and we are used to representing the network in the static case. So the first thing to do is to reduce this “dynamic flow network” to a static one. This problem was first addressed in [25]. Dynamic network flow has since been used by many researchers in modeling various vehicle routing and scheduling problems. In [23], the authors show how the dynamic network flow modeling can be used to compute how to route as many aircraft as possible through the network (max-flow problem). But our problem is quite different: we need to route a given set of flights under a given set of fixed economic and safety requirements. Consequently, the associated LP model is also different. It is clear, however, that all models used for route computation are of great interest with regard to the problem in hand. We can see, for instance, that our problem concerns route computing under time and cost constraints known as constrained shortest path problem, which is already known to be NP-hard.
Our objectives are the same as in other ATFM optimization studies. The ATFM programme includes the elaboration and validation of Standard Routing Schemes, as well as the study of slot allocation mechanisms. The goal is to improve current approaches and to develop new algorithms. An interesting project, directly related to our problem, is CARAT (Computer Aided Route Allocation Tool), which was set up to develop flow management re-routing prototypes to assist in the management of the CFMU route catalogue. Another application of CARAT is assistance in flight planning. The CARAT routing prototype computes the cheapest path, according to the user-selected cost function, from origin to destination. This rerouting may take into account a “via” and/or “avoid” constraints lists (composed of ATC points). CARAT is already used as a stand-alone tool. The method used is based on an improved version of an algorithm primarily concerned with vertical profile and temporal restriction. Another tool is AMOC (ATFM Modeling Capability), an EEC ATFM simulator, one of whose components is CASA slot allocation, based on a heuristic. In fact, this tool appears able to reduce total delay, with a good smoothing, and without any risk of significant overload. Recently, another tool, ISA (Innovative Slot Allocation) has been put forward. ISA is a generic software tool that integrates a number of optimization techniques. Programming techniques include constraint programming and linear programming. We must also cite COSAAC (COmmon Simulator to Assess ATFM Concepts), a simulation tool used in the pre-tactical phase. One of its functions is to manage airport or ATC sector constraints and manual re-routing (CARAT results) of flights or flows. Finally, SRS (Standard Route Scheme) is a strategically planned routing system designed to make the most effective use of ATC capacity. It enables ATC to maximise capacity by defining routes that provide an organized system of major traffic flows through congested areas, and reducing the crossing of major flows at critical points.
Our project is not limited to developing a re-routing tool. Our objective is to participate in the elaboration of a more global planning tool. Here we present a deterministic model intended to optimize route and flight-level assignment in a trajectory-based ATM environment. This model is extensible, with the possibility of future integration of slot-allocation requirements. Furthermore, the model can also be adapted to super-sector airspace. This represents the first contribution of this work. We feel that some other contributions are the following:
- As far as we know, airspace congestion has been only considered in terms en-route capacities, i.e. the number of aircraft in a sector. With our approach, we propose measuring airspace congestion with greater accuracy: we consider the number of aircraft involved in potential en-route conflicts. This is particularly interesting in ATM trajectory-based or sectorless environment, (see [30]).