Content area
Full text
Received Jun 23, 2017; Revised Dec 15, 2017; Accepted Jan 8, 2018
This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
1. Introduction
The core of air traffic control operator (ATCo) activity is to facilitate airspace and airport surface traffic flow, while avoiding collisions between aircraft. To satisfy this essential safety constraint, they must detect and solve possible conflicts between trajectories.
As a human ATCo can only handle a limited amount of traffic, the airspace is divided into a number of sectors. These sectors are operated by two ATCo working positions (executive and planner). All the sectors open at any one time are referred to as sectorization. The sectorization changes throughout the day depending on the air traffic.
The sectorization required to handle the estimated traffic for a time period can be designed beforehand. Therefore, a very important problem in air traffic control is to determine the minimum number of ATCos necessary to cover a sectorization structure for a given time period, denoted as airspace sector configuration, while satisfying certain ATCo labor conditions, including, for instance, resting and working time distributions. Alternatively, the number of ATCos could be fixed. The aim then would be to distribute ATCos to cover the corresponding airspace sector configuration.
These optimization problems belong to the class of timetabling and scheduling problems. The size and complexity of these combinatorial problems make them hard or even impossible to solve with exact methods.
Different problem-solving approaches have been proposed in the literature to deal with timetabling problems [1]. The Third International Timetabling Competition (ITC2011) [2] motivated the development of several approaches for the extended markup language for high school timetabling (XHSTT) problem [3]. The four finalists employed metaheuristics as part of or as the main problem solver [4–7].
Recent problem-solving approaches for the XHSTT problem are based on variable neighborhood search (VNS) [8], simulated annealing (SA) [9], or matheuristics (the integration of metaheuristics and mathematical programming) [10, 11].
Different approaches can also be found in the literature concerning other timetabling problems, including operational research, metaheuristics, or novel intelligent methods, such as university course timetabling problems [12], job shop...