Modeling and Optimization of Air Traffic

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.

Auteur

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.

Résumé

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.

Contenu

Introduction xi

PART 1. OPTIMIZATION AND ARTIFICIAL EVOLUTION 1

Chapter 1. Optimization: State of the Art 3

1.1. Methodological principles in optimization 3

1.1.1. Introduction 3

1.1.2. Modeling 4

1.1.3. Complexity 12

1.1.4. Computation time 13

1.1.5. Conclusion 13

1.2. Optimization algorithms 14

1.2.1. Introduction 14

1.2.2. Linear programming 15

1.2.3. Nonlinear programming (NLP) 16

1.2.4. Local methods subject to constraints 19

1.2.5. Deterministic global methods 21

1.2.6. Stochastic global methods 25

1.2.7. Genetic algorithms 33

1.2.8. Conclusion 34

Chapter 2. Genetic Algorithms and Improvements 37

2.1. General points 37

2.1.1. Introduction 37

2.1.2. Principle of genetic algorithms 39

2.1.3. Coding principles 42

2.1.4. Random generation of the initial population 42

2.1.5. Crossover operators 43

2.1.6. Mutation operators 45

2.1.7. Selection principles 47

2.2. Classic improvements 48

2.2.1. Scaling 49

2.2.2. Sharing 50

2.2.3. Crowding 52

2.2.4. Memetic algorithms 53

2.2.5. Multi-objective genetic algorithms 53

2.3. Our contributions 57

2.3.1. Adaptive clustered sharing 58

2.3.2. Association of genetic algorithms with simulated annealing 60

2.3.3. Parallel genetic algorithms 64

2.4. Conclusion 66

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

3.1. Introduction 67

3.2. Order statistics 68

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

3.4. Genetic algorithms and order statistics 71

3.4.1. Introduction 71

3.4.2. Coding 72

3.4.3. Recombination operators 73

3.4.4. Evaluation of fitness 75

3.5. Application to test functions 75

3.5.1. Results for the Griewank function 77

3.5.2. Results for the Rosenbrook function 78

3.5.3. Results for the Lennard-Jones function 79

3.6. Conclusion 81

PART 2. APPLICATIONS TO AIR TRAFFIC CONTROL 83

Chapter 4. Air Traffic Control 85

Chapter 5. Contributions to Airspace Sectorization 91

5.1. Introduction 91

5.2. Modeling in 2D 93

5.2.1. Model based on a transportation network 93

5.2.2. Associated complexity 98

5.3. Continuous modeling 99

5.3.1. Principle 99

5.3.2. Chromosome coding 101

5.3.3. Initial population generation principle 101

5.3.4. Crossover operator 101

5.3.5. Mutation operator 103

5.3.6. Calculation and normalization of the fitness function 104

5.3.7. Results 106

5.3.8. Conclusion 110

5.4. Discrete modeling 111

5.4.1. Principle 111

5.4.2. Coding 113

5.4.3. Recombination operators 115

5.4.4. Results 117

5.4.5. Conclusion 119

5.5. Extension 3D 119

5.5.1. Introduction 119

5.5.2. Mathematical modeling 122

5.5.3. Application of artificial evolution to the problem 127

5.5.4. Results 132

5.5.5. Conclusion 135

5.6. Accounting for the dynamic aspect 136

5.6.1. Formalization of objectives and associated mathematical model 136

5.6.2. Optimization using a genetic algorithm: continuous approach 140

5.6.3. Optimization using a genetic algorithm: discrete approach 144

Chapter 6. Contribution to Traffic Assignment 151

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

6.1.1. Transportation networks 153 6.1.2. Static ass...