Asignación de controladores a sectores aéreos mediante metaheurísticas trayectoriales: Variable Neighbourhood Search

Abstract

Este trabajo trata de dar solución a un problema de timetabling, propuesto por
CRIDA, en el que se intenta asignar ciertos controladores aéreos a un determinado
número de sectores abiertos en un tiempo determinado. Una de las principales
complejidades del problema son las numerosas condiciones que deben cumplir las soluciones
para ser factibles. Esta asignación se está realizando hasta ahora mediante
un sistema de plantillas que tiene grandes limitaciones. Por esto, para la resolución
del problema se ha propuesto el uso de la metaheurística Variable Neighbourhood
Search (VNS).
La metodología que se propone para resolver el problema de asignación de controladores
a sectores aéreos consta de tres fases. En la primera fase se formarán
soluciones iniciales a partir de la plantilla optimizada de controlar un sector con tres
controladores, y estas que servirán como punto de partida para generar soluciones
factibles. En la segunda fase se aplicará la metaheurística VNS para la generación
de soluciones factibles a partir de las soluciones iniciales, este será el principal desarrollo
de este trabajo. En la tercera fase, la metaheurística también se aplicará para
optimizar la solución factible de acuerdo a cuatro funciones objetivo.
La metaheurística logra importantes resultados en la segunda fase, donde es capaz
de encontrar soluciones factibles prácticamente en todos los casos propuestos e
incluso en dos de ellos consigue solventar la tarea con menos recursos de los disponibles.
Además, en la tercera fase es capaz de encontrar soluciones mejores que las
que se aplican actualmente en casos reales.---ABSTRACT---This work aim to solve a timetabling problem proposed by CRIDA where they
need to build some air trafic controller schedules among some sector of the space
filling a fixed amount of time. One of the main issues of the problem are the strong
conditions that must be accomplished for a solution to be feasible. A Variable Neighborhood
Search (VNS) approach is proposed to deal with this task.
The first step of the proposed solution is the construction of some templates that
will be used as initial points for generating the feasible solutions. At the second step,
VNS is applyed for building the feasible solution and this will be of main objective
of this work. The metaheuristic will be also applied for the third phase, that it's
aimed to optimize the feasible solution according to 4 objective solutions.
The metaheuristic achieves great results at the second step of the methodogy
proposed finding feasible solutions in almost every studied case, even in one of them
is cappable to find feasible solutions with fewer resources than expected. Also at the
step 3 is finding better solutions that the nowadays implemented in real cases in
CRIDA.