Two approaches to airspacedesign using Genetic Algorithms
EN-002 Designing 3D ATC
Sectors by using a “Genetic
Algorithm”-based
methodology

EN-011 Airspace Designusing a Workload Nodebased GA

José Manuel Rísquez

Xavier Ruiz-Hernández

EIWAC - Tokyo, 11th November 2010

ingeniería y consultoría de transportetransport engineering and consultancy

Two approaches to airspace design using Genetic Algorithms

Index
Two approaches to airspace design using Genetic
Algorithms: common introduction

EN-002 Designing 3D ATC Sectors by using a“Genetic Algorithm”-based methodology

EN-011 Airspace Design using a Workload Nodebased GA

Conclusions on airspace design using GA

2

ingeniería y consultoría de transportetransport engineering and consultancy

Two approaches to airspace design using Genetic Algorithms
What is the relation between an aircraft and a pea?

3

ingeniería y consultoría de transportetransport engineering and consultancy

Two approaches to airspace design using Genetic Algorithms

Introduction: What is Genetics?
Word genetics from ancient Greek: γενετικός
γένεσις
Science studying genes, the inheritance and thevariation of the organisms in the nature.
Term was proposed William Bateson to Adam
Sedgewick in 1905. Previously, Gregor Mendel in1865 had categorized the external characteristicsof the pea plants and called them characters.

4ingeniería y consultoría de transportetransport engineering and consultancy

Two approaches to airspace design using Genetic Algorithms
Introduction: What is Genetics?

In organisms, the genetic information resides in chromosomes,
where it is stored in the sequence of molecules of
Deoxyribonucleic acid (DNA).
Genetics determine most of the (but not the whole) appearanceof the organisms, having the difference in environment andother random factors also impact on it.

5ingeniería y consultoría de transportetransport engineering and consultancy

Two approaches to airspace design using Genetic Algorithms

Introduction: What is Genetic Algorithmia?
Evolutionary computation uses concepts inspired on
biology, as population, mutation, inheritance andsurvival of the fittest to generate iterative improved
solutions for a problem.
A genetic algorithm is a specific method in
evolutionary computation and is based on probability.
The algorithm must maintain the elitism, by keeping
the best elements in the population. The algorithm
tends to converge in probability to an optimum result,which will accomplish with the restrictions that theuser requires for its solution.

6

ingeniería y consultoría de transportetransport engineering and consultancy

Two approaches to airspace design using Genetic Algorithms
Our Work: Two methodologies
Two methodologies have been developed in INECO, using the same baseline of genetic algorithms.

GENES:Volume Approach

OP-DIS: Node Approach
2000

2005

present

10

ingeniería y consultoría de transportetransport engineering and consultancy

Two approaches to airspace design using Genetic Algorithms
Our Work: Two methodologies
Initially, in 2000, a new methodology (GENES) was created as a response to an EU proposal thatleaded the project “Single European Sky [1], that pretended to create one common upper-airspace. Thisapproach is based on 3D cells.

The global airspace volume to be optimized has to be defined and then, this airspace is virtually divided
into small cells. The size and shape of cells must be carefully assessed because this decision impacts
severely on the invested time to obtain the solution.
This algorithm has been widely tested and has succeeded in several Spanish airspace designs.

11ingeniería y consultoría de transportetransport engineering and consultancy

Two approaches to airspace design using Genetic Algorithms
Our Work: Two methodologies
In 2005, OP-DIS was created to solve the same problem of airspace design but using workload nodes.
With this methodology, the events that each aircraft generates in its trajectory are taken into account.
These events generate workload (calculated by an external algorithm) and are assimilated to workloadnodes. The precision of the workload-node (including more or less real workload points on each) will
speed up the calculation process.
This algorithm has been tested as an R&D development, obtaining only preliminary results.

12

EN002 - Designing 3D ATC Sectors by using a “Genetic Algorithm”based methodology – José Manuel Rísquez

ingeniería y consultoría de transportetransport engineering and consultancy

EN002 - Designing 3D ATC Sectors by using a “Genetic Algorithm”-based methodology

ATC basics
An executive ATC Controller is the responsible formanaging, in a safe way, the traffic using a sector.

In order to assure that this task is really safe, it is necessary
to protect the controller against overloads by limiting the
responsibility airspace volume and establishing a workload
limit.
As the controller workload depends strongly on the numberof flights and their related complexity, the way of protecting
him is by defining a maximum number of flights allowed
entering into a sector along one hour, it is called “capacity”.
It is assumed that if traffic demand is lower than capacity
there is no problem.

Controller “hour” is not cheap, so it is required to achieve abalance between minimum number of sectors and enoughsafety.

14

ingeniería y consultoría de transportetransport engineering and consultancy

EN002 - Designing 3D ATC Sectors by using a “Genetic Algorithm”-based methodology

Methodology (I)The main objective is to create optimum sectors configurations according to the following basics:
1. The number of sectors should be minimum.
2. The ATC workload per sector should be as close as possible to a defined “nominal” level but neveroverriding it.
To achieve
considered

this,

two

basic

elements

are1. Traffic load: Defined by flight plans (Current or
Forecast)
2. Elementary volume unit grid: Airspace isdivided into elementary volume units, which will
be unified, under certain criteria, to create control
sector (possible solutions from a combinatorial
point of view).

15ingeniería y consultoría de transportetransport engineering and consultancy

EN002 - Designing 3D ATC Sectors by using a “Genetic Algorithm”-based methodology

Methodology (II)The method is conducted in 3 steps:
1. To obtain the ATC workload, for eachelementary volume unit, according to trafficand conflict distribution.
Fast Time Simulation based
2. To search for the best elementary volume
unit combination to create sectors according
to the objectives previously mentioned:
1. Minimum number of sectors.
2. ATC workload per sector as close as
possible to a defined “nominal” level but
never overriding it.
Optimisation based on
Genetic Algorithms
3. Operational fine tune and validation of thepreviously obtained sectors configuration.
Fast Time Simulation
and Real data based
16

ingeniería y consultoría de transportetransport engineering and consultancy

EN002 - Designing 3D ATC Sectors by using a “Genetic Algorithm”-based methodology

Sector Configuration design using GA: Encoding
Genetic Algorithms establish a likeness between possible solutions for adefined problem and the individuals of biological species, encoding theinformation for each solution in a string like a chromosome.

GENE

1
5
9
13

2
6
10
14

3
7
11
15

4
8
12
16

A
A
A
A

A
A
A
A
A
B
B
B
A
C
C
C
A
C
C
C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

A
B
C
C

A
B
C
C

A
B
C
C

Elementary Airspace Unit

Possible solution (units
combination)

A
A
A
A

A
B
C
C

A
B
A
C

A
B
A
C

Feasible solution (depending
on defined constraints)

A
A
A
A

A
B
C
C

A
B
C
C

A
B
C
C

CHROMOSOMEINDIVIDUAL

Simplified Airspace
Model

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

A
A
A
A
A
B
B
B
A
C
C
C
A
C
C
C

18

ingeniería y consultoría de transportetransport engineering and consultancy

EN002 - Designing 3D ATC Sectors by using a “Genetic Algorithm”-based methodology

Sector Configuration design using GA: Fitness Function (I)A mathematical function F is designed with the following property: the more the sectorisation achieves
the objective, the higher the value of the function is.

OBJECTIVE:
Workload of each sector = 500 seconds

CONT.

Yellow Sector
Green Sector
Orange Sector

ATC WORKLOAD

1200
1000
800
600

Fitness Function
Maximum ( )

400
200
0
1

2

3

4

OBJECTIVE

SECTORISATION

(1)

(2)

(3)

(4)

100 100 100 100
100 25 15 100
100 100 100 100
100 100 100 100

100 100 100 100
100 25 15 100
100 100 100 100
100 100 100 100

100 100 100 100
100 25 15 100
100 100 100 100
100 100 100 100

100 100 100 100
100 25 15 100
100 100 100 100
100 100 100 100

8.7

7.1

8.7

5.7

Fitness
FunctionValue

19ingeniería y consultoría de transportetransport engineering and consultancy

EN002 - Designing 3D ATC Sectors by using a “Genetic Algorithm”-based methodology

Sector Configuration design using GA: Running (I)Sectorisation 1

Sectorisation 2

Sectorisation 3

Sectorisation 4

100 100 100 100
100 25 15 100
100 100 100 100
100 100 100 100

100 100 100 100
100 25 15 100
100 100 100 100
100 100 100 100

100 100 100 100
100 25 15 100
100 100 100 100
100 100 100 100

100 100 100 100
100 25 15 100
100 100 100 100
100 100 100 100

8.7

8.7

5.7

7.1

Sect. 2

Sect. 1

Sect. 4100 100 100 100
100 25 15 100
100 100 100 100
100 100 100 100

100 100 100 100
100 25 15 100
100 100 100 100
100 100 100 100

100 100 100 100
100 25 15 100
100 100 100 100
100 100 100 100

100 100 100 100
100 25 15 100
100 100 100 100
100 100 100 100

100 100 100 100
100 25 15 100
100 100 100 100
100 100 100 100

100 100 100 100
100 25 15 100
100 100 100 100
100 100 100 100

100 100 100 100
100 25 15 100
100 100 100 100
100 100 100 100

100 100 100 100
100 25 15 100
100 100 100 100
100 100 100 100

ITERATIVE PROCESS

100 100 100 100
100 25 15 100
100 100 100 100
100 100 100 100

MUTATION

100 100 100 100
100 25 15 100
100 100 100 100
100 100 100 100

CROSSOVER

100 100 100 100
100 25 15 100
100 100 100 100
100 100 100 100

100 100 100 100
100 25 15 100
100 100 100 100
100 100 100 100

SELECTION

Sect. 121

ingeniería y consultoría de transportetransport engineering and consultancy

EN002 - Designing 3D ATC Sectors by using a “Genetic Algorithm”-based methodology

Sector Configuration design using GA: Running (II)

SELECCIÓN

CRUCE

MUTACIÓN

-----------

N sectors
N-1 sectors
N-2 sectors

SELECCIÓN

CRUCE

N-n sectors

MUTACIÓN

22

ingeniería y consultoría de transportetransport engineering and consultancy

EN002 - Designing 3D ATC Sectors by using a “Genetic Algorithm”-based methodology

Sector Configuration design using GA: Operational conditions

2

1

Example of a doble-entry

Example of a non-cylindrical ATC sector

Example of a short-stay

A

A

A

A

A

B

B

B

A

C

A

A

A

C

C

C

Example of an ATC sector with disruptions
23

ingeniería y consultoría de transportetransport engineering and consultancy

EN002 - Designing 3D ATC Sectors by using a “Genetic Algorithm”-based methodology

Results and Benefits

Main benefits of this method could be classified according to the scope:Long term: to support new airspace organisation by indicating sector configurationthat best fit the requirements of the demand.

As an example of this capability, this algorithm was exploited in the Spanish Single
Sky project a R+D initiative which aims to optimise the available resources of the Air
Navigation System, by a new organisation of the Airspace Structure (routes andsectors), to best fit the forecast demand (2005 and 2007 time horizons) according tosafety, environment, capacity and efficiency criteria.

Short term: to produce homogeneous alternatives to current proposals for sector
configurations modification beyond the local ATC experience.
In this sense, this algorithm is being used to support several projects for TMA
airspace re-organisation in Spain.

24

ingeniería y consultoría de transportetransport engineering and consultancy

EN002 - Designing 3D ATC Sectors by using a “Genetic Algorithm”-based methodology

Results and Benefits

Horizontal limits: SPANISH AIRSPACE(delegated airspace included)
Vertical Limits: GND / FL460(Airports ATZ not included)25

ingeniería y consultoría de transportetransport engineering and consultancy

EN002 - Designing 3D ATC Sectors by using a “Genetic Algorithm”-based methodology

Results and Benefits
Horizon
2007
2005

PENINSULA
Sectors
65
57

Movements
5892
5122

Horizon
2007
2005

CANARY
Sectors
7
7

Movements
837
762

26

EN011 – Airspace Design using a Workload Node-based GA
Xavier Ruiz-Hernández

ingeniería y consultoría de transportetransport engineering and consultancy

EN011 – Airspace Design using a Workload Node-based GA

OP-DIS: main characteristics

The algorithm presented in OP-DIS uses
workload nodes instead of small airspace
regions or traffic flows like other initiatives inthis field, and it takes into account parameterslike the workload produced by aircraft, thelocationoftheconflictsorthepossible/impossible frontier points to consider
specific safety issues.
Thanks to the difference of using workload
nodes the algorithm directly knows where andwhen the workload is produced.

Outstanding points

28ingeniería y consultoría de transportetransport engineering and consultancy

EN011 – Airspace Design using a Workload Node-based GA

OP-DIS: workload nodes
The objective of this GA is to produce a trafficdependent sectorization, and hence a traffic
forecast is needed. By FTSs a log of all thetheoretical events that would occur during theflights is obtained.
Event
For each event produced it is also needed thetype of event, its coordinates (x, y), flight level,
time and indicative.

Sector Pierce
Sector Exit

The importance of their location lies in theworkload at these coordinates. where they occur
and where the Air Traffic Controller must pay
special attention or even communicate with theaircraft.

Start of cruiseThis workload will be one of the main parametersof the fitness function. The user may introduce a
fixed workload value for each category of event.

Crossing point

End of cruise
Conflict29

ingeniería y consultoría de transportetransport engineering and consultancy

EN011 – Airspace Design using a Workload Node-based GA

OP-DIS: initialization
At this step, the genetic algorithm must be
initialized. The population is prepared to encode
the outstanding points detected in the previous
phase.

To achieve this, each chromosome will be
initialized with an individual, i.e. a candidate
solution representing a complete sectorization.
For the purpose of this representation, consider afixed number n of sectors and the number m ofdetected outstanding points in the previous
phase. An individual will then be an array ofexactly n · m genes.
The number of chromosomes is 38, where each
one is related to each mutation.

Example with 4 outstanding points and 3 sectors

30ingeniería y consultoría de transportetransport engineering and consultancy

EN011 – Airspace Design using a Workload Node-based GA

OP-DIS: encoding a chromosome

100Practical example for the encodingof 4 points to be distributed
amongst 3 sectors

31ingeniería y consultoría de transportetransport engineering and consultancy

EN011 – Airspace Design using a Workload Node-based GA

OP-DIS: mutations
The mutations applied to the chromosomes
will be different for each individual and arefocused to reduce the weaknesses that they
may have.

Mutations consist of basic variations on theassignment of outstanding points from a
sector to another sector, modifying the bit in
the related genes.

Mutations focused on…

Removing re-entries
Removing airspace
discontinuities
Balancing the numberof points in a sector

Most of the mutations are only a few times(or even never) producing the best result in
the fitness function for most of the
scenarios. However, in particular situations
they are useful to obtain an optimized result,and hence their utility is very scenario
dependant.

Balancing the numberof flights between sectors

This algorithm use 38 different mutations
focused on several aspects.

Randomly changes

Avoiding breaking
restrictions

32

ingeniería y consultoría de transportetransport engineering and consultancy

EN011 – Airspace Design using a Workload Node-based GA

OP-DIS: selection phase – fitness function

FF  Fx1  Fa  Fx2  Fd  Fx3  Fr 
 Fx4  Fwl  Fx5  Fconst
Factor
Fa
Fd

Fr
Fwl
FconstDescription
Number of airplanes in the
sector with more traffic
Number of discontinuities inaltitude
Numbers of re-entries in
sectors
Estimated workload in sectors
Number of couples of points
breaking constraints

The applied mutations force the change of theindividuals, generating new combinations that inmost of the cases will be worst than their parents.
However, a small amount will obtain a better
fitness result that will improve the population. The
fitness function includes several factors likenumber of airplanes, workload, etc. The user canweight these parameters according to theirneeds.
In two consecutive iterations, the best individual
may be completely different from the previous
one, because as the fitness function evaluates
the individual as an overall, one of the parametersof the new individual may have substantiallydecreased (or increased) in favor of anotherparameter. This equilibrium eases the explorationof the great majority of the search space.

33

ingeniería y consultoría de transportetransport engineering and consultancy

EN011 – Airspace Design using a Workload Node-based GA

OP-DIS: fitness function – reproduction phase
Once all the individuals are evaluated by thefitness function in each iteration, the one having
the minor fitness function result is selected (themore penalties, the higher result in the fitness
function).
When the best individual is selected, it is cloned
to the other 37 chromosomes, having at the endof the iteration the same individual replicated in all
chromosomes in the population.

The phases of selection and reproduction are
iteratively repeated until a termination conditions
is reached.

FF  Fx1  Fa  Fx2  Fd  Fx3  Fr 
 Fx4  Fwl  Fx5  Fconst
34

ingeniería y consultoría de transportetransport engineering and consultancy

EN011 – Airspace Design using a Workload Node-based GA

OP-DIS: fitness function – reproduction phase
Once all the individuals are evaluated by thefitness function in each iteration, the one having
the minor fitness function result is selected (themore penalties, the higher result in the fitness
function).
When the best individual is selected, it is cloned
to the other 37 chromosomes, having at the endof the iteration the same individual replicated in all
chromosomes in the population.

The phases of selection and reproduction are
iteratively repeated until a termination conditions
is reached.

FF  Fx1  Fa  Fx2  Fd  Fx3  Fr 
 Fx4  Fwl  Fx5  Fconst
35

ingeniería y consultoría de transportetransport engineering and consultancy

EN011 – Airspace Design using a Workload Node-based GA

OP-DIS: termination
The algorithm may terminate following the criteriaof the generic genetic algorithms, for instance agiven number of iterations, a fixed execution time,etc.
In this particular case, the algorithm stops when athreshold in the fitness function is reached.
The solution obtained with the algorithm is theassignment of each outstanding point to a sector.
A cloud of points linked to this sector is finallyproducing each of the sectors.

36ingeniería y consultoría de transportetransport engineering and consultancy

EN011 – Airspace Design using a Workload Node-based GA

OP-DIS: evolution and future steps• Clouds of points vs closed polygons: loose of precision• Improvement of mutations• Analysis of random mutations and initialization• Usability of an obtained proposal: training ATCo period37ingeniería y consultoría de transportetransport engineering and consultancy

Two approaches to airspace design using Genetic Algorithms

Conclusions
Both approaches, based on GAs, have proven successful in medium-term planning phaseand great airspace volumes, being able to take into account:“Demand and Capacity Balance” issues by means of balancing Workload and Human
Resources parameters
Solutions must fix to flight trajectories (nowadays concept (fixed route structure) or
SESAR concept (e.g. user-preferred trajectories))
Military reservations (e.g. VGA – Variable Geometry Area)
Traffic demand variability by offering new and quick Dynamic Sectorisations (OP-DIS
capability).

38

ingeniería y consultoría de transportetransport engineering and consultancy

Two approaches to airspace design using Genetic Algorithms

Thank you very much for your attention!

貴重なお時間を大変ありがとうございました。

39

ingeniería y consultoría de transportetransport engineering and consultancy

Two approaches to airspace design using Genetic Algorithms
Who we are

INECO
Ingeniería y Economía del Transporte, S.A.
Avenida del Partenón 4, 4th floor
28042 – Madrid
Spain
http://www.ineco.es

Our work
EN-002 Designing 3D ATC
Sectors by using a “Genetic
Algorithm”-based methodology
José Manuel Rísquez
jrisquez@ineco.es
Contributors
Víctor Bustos
vbustos@ineco.es

EN-011 Airspace Design usinga Workload Node-based GA
Xavier Ruiz Hernández
xavier.ruiz@ineco.es

Fernando Gómez Comendador
fgomez@ineco.es
40