Asignación de controladores a sectores aéreos mediante metaheurísticas trayectoriales: búsqueda tabú

Abstract

En este documento abordamos la asignación de controladores a sectores aéreos en un problema
de timetabling. En nuestro problema existen una serie de condiciones de obligado
cumplimiento y otras condiciones deseables. Estos objetivos tienen que ver con los periodos
de trabajo y descanso de los controladores así como con sus posiciones de trabajo, la estructura
de la solución y el número de cambios de sala. Además se trata de buscar que la carga
de trabajo entre los distintos controladores esté repartida uniformemente.
Se propone una metodología basada en tres fases. En la primera fase, se utiliza una heurística
para obtener soluciones iniciales infactibles basadas en las plantillas proporcionadas.
A continuación, en la segunda fase, se usa un algoritmo MIR (Multiple Independent Run)
basado en recocido simulado para tratar de alcanzar soluciones factibles. Por último, en la
tercera fase, usaremos la búsqueda tabú a partir de las soluciones factibles obtenidas en la
segunda fase con el objetivo de optimizar las funciones objetivo. Para ello tenemos en cuenta
información ordinal sobre estos, de esta manera transformamos el problema multiobjetivo
de optimización en uno de un solo objetivo usando el método del centroide. Adicionalmente
donde se pueda usamos expresiones regulares para comprobar las condiciones de trabajo de
los controladores, permitiéndonos realizar ésto con rapidez.
Nuestro software, el cual implementa este enfoque, nos ha permitido obtener resultados
reales que mejoran los proporcionados por una plantilla de referencia dada.---ABSTRACT---In this document we address a work-shift scheduling problem regarding the assignment
of air traffic controllers (ATC) to air sectors. In this problem there exists a series of constraints
that must be fulfilled, in addition there are other conditions that are desirable. These
objectives deal with the work and rest periods of the ATC and their positions, the structure
of the solution and the number of control center changes. In addition we try to balance the
workload of the different ATCs.
We propose a methodology based on three phases. In the first phase, a heuristic is used to
obtain diferent feasible or unfeasible initial solutions based on some given templates. Next,
in the second phase, we use a MIR (Multiple Independent Run) algorithm based on simulated
annealing with the purpose of reaching feasible solutions. Last, in the third phase, we
use tabu search on the feasible solutions given by the previous phase with the goal of optimizing
them regarding the objetive functions. In order to do this, we have into account ordinal
information about them and we can transform this multiobjetive optimization problem into
a single optimization problem using the rank order centroid method. In addition we will
use regular expressions, if possible, to check if the work conditions of the ATCs are met,
allowing us to do this quite fast.
Our own software implementing this approach allowed us to obtain results in a real-world
problem that improve the ones given by a reference template.