Metaheuristics for Air Traffic Management

Air Traffic Management involves many different services such as Airspace Management, Air Traffic Flow Management and Air Traffic Control. Many optimization problems arise from these topics and they generally involve different kinds of variables, constraints, uncertainties. Metaheuristics are often good candidates to solve these problems.   

The book models various complex Air Traffic Management problems such as airport taxiing, departure slot allocation, en route conflict resolution, airspace and route design. The authors detail the operational context and state of art for each problem. They introduce different approaches using metaheuristics to solve these problems and when possible, compare their performances to existing approaches

Nicolas Durand, Professor at ENAC (Ecole Nationale de l'Aviation Civile).

David Gianazza, Assistant Professor at ENAC (Ecole Nationale de l'Aviation Civile).

Jean-Baptiste Gotteland, Assistant Professor at ENAC (Ecole Nationale de l'Aviation Civile).

Jean-Marc Alliot, Research Director IRIT (Institut de Recherche en Informatique de Toulouse).

Introduction  ix

Chapter 1. The Context of Air Traffic Management  1

1.1. Introduction  1

1.2. Vocabulary and units 2

1.3. Missions and actors of the air traffic management system 3

1.4. Visual flight rules and instrumental flight rules 4

1.5. Airspace classes  4

1.6. Airspace organization and management 5

1.6.1. Flight information regions and functional airspace blocks  5

1.6.2. Lower and upper airspace 6

1.6.3. Controlled airspace: en route, approach or airport control 7

1.6.4. Air route network and airspace sectoring  7

1.7. Traffic separation 9

1.7.1. Separation standard, loss of separation 9

1.7.2. Conflict detection and resolution 11

1.7.3. The distribution of tasks among controllers 12

1.7.4. The controller tools  12

1.8. Traffic regulation  13

1.8.1. Capacity and demand 13

1.8.2. Workload and air traffic control complexity  15

1.9. Airspace management in en route air traffic control centers  16

1.9.1. Operating air traffic control sectors in real time  16

1.9.2. Anticipating sector openings (France and Europe) 17

1.10. Air traffic flow management  19

1.11. Research in air traffic management 20

1.11.1. The international context  20

1.11.2. Research topics  21

Chapter 2. Air Route Optimization 23

2.1. Introduction  23

2.2. 2D-route network 24

2.2.1. Optimal positioning of nodes and edges using geometric algorithms  24

2.2.2. Node positioning, with fixed topology, using a simulated annealing or a particle swarm optimization algorithm 28

2.2.3. Defining 2D-corridors with a clustering method and a genetic algorithm 29

2.3. A network of separate 3D-tubes for the main traffic flows 31

2.3.1. A simplified 3D-trajectory model  31

2.3.2. Problem formulations and possible strategies  34

2.3.3. An A∗ algorithm for the “1 versus n” problem 35

2.3.4. A hybrid evolutionary algorithm for the global problem 41

2.3.5. Results on a toy problem, with the simplified 3D-trajectory model  50

2.3.6. Application to real data, using a more realistic 3D-tube model  57

2.4. Conclusion on air route optimization  66

Chapter 3. Airspace Management 69

3.1. Airspace sector design 70

3.2. Functional airspace block definition 71

3.2.1. Simulated annealing algorithm  73

3.2.2. Ant colony algorithm 73

3.2.3. A fusion–fission method 73

3.2.4. Comparison of fusion–fission and classical graph partitioning methods 74

3.3. Prediction of air traffic control sector openings 74

3.3.1. Problem difficulty and possible approaches 78

3.3.2. Using a genetic algorithm 78

3.3.3. Tree-search methods, constraint programming 79

3.3.4. A neural network for workload prediction 80

3.3.5. Conclusion on the prediction of sector openings  83

Chapter 4. Departure Slot Allocation 85

4.1. Introduction  85

4.2. Context and related works  86

4.2.1. Ground holding  86

4.3. Conflict-free slot allocation  87

4.3.1. Conflict detection 88

4.3.2. Sliding forecast time window  90

4.3.3. Evolutionary algorithm  91

4.4. Results 95

4.4.1. Evolution of the problem size  95

4.4.2. Numerical results 96

4.5. Concluding remarks  98

Chapter 5. Airport Traffic Management  101

5.1. Introduction  101

5.1.1. Airports’ main challenges 101

5.1.2. Known difficulties  102

5.1.3. Optimization problems in airport traffic management 103

5.2. Gate assignment  103

5.2.1. Problem description  103

5.2.2. Resolution methods  104

5.3. Runway scheduling  106

5.3.1. Problem description  106

5.3.2. An example of problem formulation  108

5.3.3. Resolution methods  109

5.4. Surface routing  111

5.4.1. Problem description  111

5.4.2. Related work  112

5.5. Global airport traffic optimization  115

5.5.1. Problem description  115

5.5.2. Coordination scheme between the different predictive systems  116

5.5.3. Simulation results 117

5.6. Conclusion 121

Chapter 6. Conflict Detection and Resolution  123

6.1. Introduction  123

6.2. Conflict resolution complexity  125

6.3. Free-flight approaches 128

6.3.1. Reactive techniques  129

6.3.2. Iterative approach 129

6.3.3. An example of reactive approach: neural network trained by evolutionary algorithms  130

6.3.4. A limit to autonomous approaches: the speed constraint 137

6.4. Iterative approaches  138

6.5. Global approaches 138

6.6. A global approach using evolutionary computation  140

6.6.1. Maneuver modeling  140

6.6.2. Uncertainty modeling 141

6.6.3. Real-time management  142

6.6.4. Evolutionary algorithm implementation 144

6.6.5. Alternative modeling 151

6.6.6. One-day traffic statistics 152

6.6.7. Introducing automation in the existing system 153

6.7. A global approach using ant colony optimization 155

6.7.1. Problem modeling 155

6.7.2. Algorithm description 156

6.7.3. Algorithm improvement: constraint relaxation 159

6.7.4. Results 160

6.7.5. Conclusion and further work 160

6.8. A new framework for comparing approaches  163

6.8.1. Introduction  163

6.8.2. Trajectory prediction model 163

6.8.3. Conflict detection 168

6.8.4. Benchmark generation  169

6.8.5. Conflict resolution 170

6.9. Conclusion 177

Conclusion  179

Bibliography 181

Index  193

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.