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.

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 assignment 155

6.1.3. Dynamic assignment 163

6.2. Other approaches to traffic assignment  167

6.2.1. Temporal extension of the network  167

6.2.2. Optimal control  168

6.2.3. Dynamic programming approaches (ground holding problem) 169

6.2.4. Conclusion  171

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

6.3.1. Mathematical formalization of objectives 173

6.3.2. Coding and operators of the genetic algorithm  176

6.3.3. Introduction of an inter-chromosome distance for sharing   179

6.3.4. Example of results   182

6.3.5. Conclusion  185

6.4. Allocation of routes and slots using artificial evolution 186

6.4.1. System architecture 187

6.4.2. The fitness function   192

6.4.3. Simple genetic algorithm   194

6.5. Modification of the algorithm – adaptive modifications   198

6.5.1. Establishing congestion levels in the chromosome  198

6.5.2. Establishment of trends 200

6.5.3. New coding and biased initial population 203

6.5.4. New crossover operator  203

6.5.5. New mutation operator   204

6.5.6. New results 205

6.5.7. Dynamic bi-allocation   207

6.5.8. Multi-objective approach   210

6.5.9. Conclusion   211

6.6. Sequencing flights for landing 211

6.6.1. Introduction    212

6.6.2. Single runway formulation 213

6.6.3. Modeling using GA   214

6.6.4. Results 217

6.7. Trajectory planning 220

6.7.1. Introduction    220

6.7.2. The light propagation algorithm  222

6.7.3. Approach using genetic algorithms on B-splines    234

6.8. Conclusion 241

Chapter 7. Airspace Congestion Metrics 243

7.1. Introduction 243

7.2. Flow-based approach 248

7.2.1. Mathematical modeling of the control workload    253

7.3. Geometrical approaches 253

7.3.1. Proximity metric  254

7.3.2. Convergence 258

7.3.3. Clusters 263

7.3.4. Grassmannian indicator 265

7.4. Approach based on dynamic systems  268

7.4.1. Linear dynamic systems 268

7.4.2. Spatial extension using nonlinear dynamic systems 273

7.4.3. Spatiotemporal extension using nonlinear dynamic systems 281

7.4.4. Local linear models   285

7.4.5. Stochastic extension 288

Conclusion and Future Perspectives 291

Bibliography  299

Index 327

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.