Metaheuristics for Air Traffic Management

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  ixChapter 1. The Context of Air Traffic Management  11.1. Introduction  11.2. Vocabulary and units 21.3. Missions and actors of the air traffic management system 31.4. Visual flight rules and instrumental flight rules 41.5. Airspace classes  41.6. Airspace organization and management 51.6.1. Flight information regions and functional airspace blocks  51.6.2. Lower and upper airspace 61.6.3. Controlled airspace: en route, approach or airport control 71.6.4. Air route network and airspace sectoring  71.7. Traffic separation 91.7.1. Separation standard, loss of separation 91.7.2. Conflict detection and resolution 111.7.3. The distribution of tasks among controllers 121.7.4. The controller tools  121.8. Traffic regulation  131.8.1. Capacity and demand 131.8.2. Workload and air traffic control complexity  151.9. Airspace management in en route air traffic control centers  161.9.1. Operating air traffic control sectors in real time  161.9.2. Anticipating sector openings (France and Europe) 171.10. Air traffic flow management  191.11. Research in air traffic management 201.11.1. The international context  201.11.2. Research topics  21Chapter 2. Air Route Optimization 232.1. Introduction  232.2. 2D-route network 242.2.1. Optimal positioning of nodes and edges using geometric algorithms  242.2.2. Node positioning, with fixed topology, using a simulated annealing or a particle swarm optimization algorithm 282.2.3. Defining 2D-corridors with a clustering method and a genetic algorithm 292.3. A network of separate 3D-tubes for the main traffic flows 312.3.1. A simplified 3D-trajectory model  312.3.2. Problem formulations and possible strategies  342.3.3. An A∗ algorithm for the “1 versus n” problem 352.3.4. A hybrid evolutionary algorithm for the global problem 412.3.5. Results on a toy problem, with the simplified 3D-trajectory model  502.3.6. Application to real data, using a more realistic 3D-tube model  572.4. Conclusion on air route optimization  66Chapter 3. Airspace Management 693.1. Airspace sector design 703.2. Functional airspace block definition 713.2.1. Simulated annealing algorithm  733.2.2. Ant colony algorithm 733.2.3. A fusion–fission method 733.2.4. Comparison of fusion–fission and classical graph partitioning methods 743.3. Prediction of air traffic control sector openings 743.3.1. Problem difficulty and possible approaches 783.3.2. Using a genetic algorithm 783.3.3. Tree-search methods, constraint programming 793.3.4. A neural network for workload prediction 803.3.5. Conclusion on the prediction of sector openings  83Chapter 4. Departure Slot Allocation 854.1. Introduction  854.2. Context and related works  864.2.1. Ground holding  864.3. Conflict-free slot allocation  874.3.1. Conflict detection 884.3.2. Sliding forecast time window  904.3.3. Evolutionary algorithm  914.4. Results 954.4.1. Evolution of the problem size  954.4.2. Numerical results 964.5. Concluding remarks  98Chapter 5. Airport Traffic Management  1015.1. Introduction  1015.1.1. Airports’ main challenges 1015.1.2. Known difficulties  1025.1.3. Optimization problems in airport traffic management 1035.2. Gate assignment  1035.2.1. Problem description  1035.2.2. Resolution methods  1045.3. Runway scheduling  1065.3.1. Problem description  1065.3.2. An example of problem formulation  1085.3.3. Resolution methods  1095.4. Surface routing  1115.4.1. Problem description  1115.4.2. Related work  1125.5. Global airport traffic optimization  1155.5.1. Problem description  1155.5.2. Coordination scheme between the different predictive systems  1165.5.3. Simulation results 1175.6. Conclusion 121Chapter 6. Conflict Detection and Resolution  1236.1. Introduction  1236.2. Conflict resolution complexity  1256.3. Free-flight approaches 1286.3.1. Reactive techniques  1296.3.2. Iterative approach 1296.3.3. An example of reactive approach: neural network trained by evolutionary algorithms  1306.3.4. A limit to autonomous approaches: the speed constraint 1376.4. Iterative approaches  1386.5. Global approaches 1386.6. A global approach using evolutionary computation  1406.6.1. Maneuver modeling  1406.6.2. Uncertainty modeling 1416.6.3. Real-time management  1426.6.4. Evolutionary algorithm implementation 1446.6.5. Alternative modeling 1516.6.6. One-day traffic statistics 1526.6.7. Introducing automation in the existing system 1536.7. A global approach using ant colony optimization 1556.7.1. Problem modeling 1556.7.2. Algorithm description 1566.7.3. Algorithm improvement: constraint relaxation 1596.7.4. Results 1606.7.5. Conclusion and further work 1606.8. A new framework for comparing approaches  1636.8.1. Introduction  1636.8.2. Trajectory prediction model 1636.8.3. Conflict detection 1686.8.4. Benchmark generation  1696.8.5. Conflict resolution 1706.9. Conclusion 177Conclusion  179Bibliography 181Index  193