Modeling and Optimization of Air Traffic E-Book

Daniel Delahaye

• Herausgeber: John Wiley & Sons
• Kategorie: Fachliteratur
• Sprache: Englisch

Seitenzahl: 329

Veröffentlichungsjahr: 2013

Beschreibung

This book combines the research activities of the authors, both of whom are researchers at Ecole Nationale de l'Aviation Civile (French National School of Civil Aviation), and presents their findings from the last 15 years. Their work uses air transport as its focal point, within the realm of mathematical optimization, looking at real life problems and theoretical models in tandem, and the challenges that accompany studying both approaches. The authors' research is linked with the attempt to reduce air space congestion in Western Europe, USA and, increasingly, Asia. They do this through studying stochastic optimization (particularly artificial evolution), the sectorization of airspace, route distribution and takeoff slots, and by modeling airspace congestion. Finally, the authors discuss their short, medium and long term research goals. They hope that their work, although related to air transport, will be applied to other fields, such is the transferable nature of mathematical optimization. At the same time, they intend to use other areas of research, such as approximation and statistics to complement their continued inquiry in their own field. Contents 1. Introduction. Part 1. Optimization and Artificial Evolution 2. Optimization: State of the Art. 3. Genetic Algorithms and Improvements. 4. A new concept for Genetic Algorithms based on Order Statistics. Part 2. Applications to Air Traffic Control 5. Air Traffic Control. 6. Contributions to Airspace Sectorization. 7. Contribution to Traffic Assignment. 8. Airspace Congestion Metrics. 9. Conclusion and Future Perspectives. About the Authors Daniel Delahaye works for Ecole Nationale de l'Aviation Civile (French National School of Civil Aviation) in France. Stéphane Puechmorel works for Ecole Nationale de l'Aviation Civile (French National School of Civil Aviation) in France.

Leseprobe

Table of Contents

Introduction

PART 1: Optimization and Artificial Evolution

Chapter 1: Optimization: State of the Art

1.1. Methodological principles in optimization

1.2. Optimization algorithms

Chapter 2: Genetic Algorithms and Improvements

2.1. General points

2.2. Classic improvements

2.3. Our contributions

2.4. Conclusion

Chapter 3: A New Concept for Genetic Algorithms Based on Order Statistics

3.1. Introduction

3.2. Order statistics

3.3. Estimating the probability that the global optimum belongs to a given domain

3.4. Genetic algorithms and order statistics

3.5. Application to test functions

3.6. Conclusion

PART 2: Applications to Air Traffic Control

Chapter 4: Air Traffic Control

Chapter 5: Contributions to Airspace Sectorization

5.1. Introduction

5.2. Modeling in 2D

5.3. Continuous modeling

5.4. Discrete modeling

5.5. Extension 3D

5.6. Accounting for the dynamic aspect

Chapter 6: Contribution to Traffic Assignment

6.1. Summary of traffic assignment methods based on transportation network theory

6.2. Other approaches to traffic assignment

6.3. Using artificial evolution in all-or-nothing traffic assignment

6.4. Allocation of routes and slots using artificial evolution

6.5. Modification of the algorithm – adaptive modifications

6.6. Sequencing flights for landing

6.7. Trajectory planning

6.8. Conclusion

Chapter 7: Airspace Congestion Metrics

7.1. Introduction

7.2. Flow-based approach

7.3. Geometrical approaches

7.4. Approach based on dynamic systems

Conclusion and Future Perspectives

Bibliography

Index

First published 2013 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUKwww.iste.co.uk

John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USAwww.wiley.com

© ISTE Ltd 2013The rights of Daniel Delahaye and Stéphane Puechmorel to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2013936316

British Library Cataloguing-in-Publication DataA CIP record for this book is available from the British LibraryISBN: 978-1-84821-595-5

Introduction

This book presents the main research topics that we have worked on over the last 15 years. Research is a fascinating occupation that allows permanent enrichment of knowledge and sustains rich intellectual activity. Moments of doubt do arise when a problem seems impossible to solve, but this is intrinsically linked to one of the great advantages of research: the feeling of satisfaction when a solution is finally found. As researchers at the Ecole Nationale de l’Aviation Civile (French Civil Aviation University), our research activity focuses on the theme of air transport and, specifically, on the domain of mathematical optimization. It is always fascinating to look at real problems taken from the operational domain as their characteristics are often complex, representing a significant challenge with applicable results. When observing real situations, we note that they are often considerably different from theoretical models, and our mathematical tools are of limited use when attempting to tackle a complex problem as a whole. These practical problems present a certain interest for researchers as they require the development of new tools.

Our research focuses on issues linked to reducing congestion in airspace. These types of problems are generally not only found in Western Europe and the United States, but also in Asia.

Our main research topics in recent years have been the following:

1) Optimization through Artificial Evolution. The complexity of the problems which we have considered generally leads us to study the possibilities of stochastic optimization, in particular artificial evolution. We were fortunate enough to work for a long period with Marc Schoenauer (CMAPX1), who introduced us to this groundbreaking technique that simulated genetic evolution, following the principles laid down by Darwin, to optimize mathematical functions. Since then, we have continued to work on this technique, in particular in the context of application to real world problems. We have also introduced a number of modifications to the genetic algorithms in order to improve their performances.

Finally, we also designed a new principle for genetic algorithms working on state space domains that are evaluated using order statistics within a continuous framework. This new algorithm presents improvements in performance compared to the standard version.

2) Sectorization of airspace. Using a set of airplane trajectories across a country or a continent that requires control of the airspace, sectorization consists of determining an optimal three-dimensional (3D) division of the airspace in order to balance the levels of control acrivity required for each sector and to minimize the number of times trajectories cross the sector borders, at the same time respecting a number of operational constraints.

We began working on this project using a two-dimensional (2D) modeling in the form of a Voronoi diagram2. Subsequently, we proposed a discrete model allowing direct division of the network of airways. This project was then extended to take account of a dynamic framework for which sectorization adapts to variations in air traffic flow (e.g. seasonal variations). Finally, we proposed a 3D extension to both approaches, allowing us to synthesize the cylindrical sectors with polygonal cross-sections corresponding to the characteristics of operational control sectors.

3) Route distribution and take-off slots. When it is not possible to increase the capacity of a transport network, we need to adapt demand to capacity in order to avoid the congestion phenomena in the network. In the case of air transport, this leads us to look for optimal routes and take-off slots for all the flights using a given airspace over a fixed period of time. A project for looking into these issues was launched by the Centre d’Étude de la Navigation Aérienne (Air Navigation Research Center) in 1992, and was then continued by the Aero-Astro department at MIT under the direction of Professor Amedeo Odoni. The project consisted of seeking the optimal bi-allocation (routes plus take-off slots) for all flight plans in the US airspace (around 50,000) while respecting the objectives of airlines. Taking 10 routes and 10 slots, the number of possibilities with this type of problem are of the order 10050,000 with non-separable criteria, which leads us to look immediately to stochastic optimization. This work was extended at the CMAPX within the framework of a research co-supervised by Marc Schoenauer and Daniel Delahaye (PhD thesis of Sofiane Oussedik and financed by Eurocontrol3). The results obtained during the course of this research demonstrated that it is possible, in a robust manner, to reduce the congestion by a factor of 2.5 across the entire French airspace by modifying the take-off times by ±15 min with a maximum increase of 10% in the length of routes. Based on the target plan, which would create substantial reductions in congestion, we needed to find effective means for encouraging users to adopt this solution. This was the subject of another piece of research, carried out at ONERA, Toulouse (the PhD thesis entitled “Optimization of congestion pricing leading to system balancing, with user fairness” was written by Karine Deschinkel and co-supervized by Jean-Loup Farges).

4) Modeling airspace congestion. In the context of airspace sector design problems or traffic assignment problems, the measurements of operational congestion used to construct the objective function are not sufficient enough to correctly reflect the difficulty of managing traffic situations. The operational capacity of a control sector is measured by the maximum number of flights that may cross the sector in a given period of time. This measurement does not take into account the direction of the traffic, treating geometrically structured and disordered traffic in the same way. Thus, in certain situations, a controller may continue to accept traffic even though the operational capacity has been reached (structured traffic); in other cases, a controller may need to prevent the airplanes even though the operational capacity has not been reached (disordered traffic). Thus, the measurement using the number of airplanes per unit of time is insufficient to reflect the levels of difficulty involved in a traffic situation. To refine this congestion measurement, we propose the following three approaches:

– flow-based metrics;

– metrics based on the geometric distribution of speed vectors in the airspace;

– metrics obtained by modeling the air traffic using a dynamic system (linear or nonlinear).

The structure of this book broadly reflects the four main topics of our research:

1) optimization by artificial evolution;

2) sectorization of airspace;

3) route distribution and take-off slots;

4) modeling airspace congestion.

The main focus of our current research activity is on functional optimization using artificial evolution. The aim of this research is to synthesize a set of airplane trajectories (four-dimensional) allowing us to maximize or minimize a criterion. When dealing with a functional optimization problem (in a space of infinite dimensions), it is naive to attempt to discretize the trajectory in order to replace it in a state space of finite dimensions. This approach produces moderate results and it is preferable to search for a decomposition basis adapted to the problem in question. In the case of air traffic, for example, an airplane trajectory is a succession of segments of constant curve and torsion. For this specific case, we have developed a decomposition principle which allows effective and efficient synthesis of this type of trajectory using a limited set of coefficients. We may then simply run these coefficients using artificial evolution in order to synthesize the optimal trajectory. Other more traditional bases, such as wavelets and splines, may also be envisaged.

1 Applied Mathematics Laboratory of Ecole Polytechnique.

2 In mathematics, a Voronoi diagram is a particular decomposition of a metric space determined by the distances of a discrete set of objects in space, generally a discrete set of points.

3 European organization for the management of air traffic control.

PART 1

Optimization and Artificial Evolution

Chapter 1

Optimization: State of the Art

In this chapter, we present the methodological principles involved in optimization, before introducing the main optimization methods used in an industrial context.

1.1. Methodological principles in optimization

This section presents the main characteristics of modeling of industrial optimization problems.

1.1.1. Introduction

When faced with a real optimization problem, we must analyze the problem in a precise manner in order to choose the best method to use. Real optimization problems correspond to needs observed in industrial or operational contexts, and aim to improve the performance of an economic process connected with an operational company or management organization. In practice, these problems are identified by domain experts who wish to develop an optimization principle in order to improve the performance of a system.

1.1.2. Modeling

The first stage in the optimization process consists of modeling the real problem using a mathematical abstraction that is as efficient as possible (see Figure 1.1). Using this abstraction, it is possible to develop solution algorithms that can be executed on a computer. This optimization process produces a set of solution points, which can then be implemented in the real world. In the past, there were few choices of optimization algorithms and it was necessary to use models that were somewhat different from reality but for which solution methods existed. Therefore, the solutions produced could be different from the true solution in the real world. A classic example involves linear programming (LP) for which we have efficient solution algorithms, but which requires linear modeling of the problem.

Figure 1.1.Modeling process

The modeling stage, then, consists of characterizing the state space and the objective space.

1.1.2.1. State space

The state space represents the set of parameters of the system upon which we may act in order to optimize one (or more) objective(s). Examination of the properties of the state space then helps us in choosing a suitable optimization method.

In most industrial optimization problems, the variables of the state space must remain within a subdomain defined by a set of constraints. We obtain the following general model: