Asignación de controladores aéreos a sectores: estudio de los entornos en el recocido simulado

Abstract

En esta tesis se aborda el problema de la asignación de controladores aéreos a sectores. Este problema pertenece a la clase de problemas de timetabling. El problema de asignación de controladores aéreos a sectores se caracteriza por la gran cantidad de restricciones que hay que satisfacer. Para solucionar este problema usaremos el recocido simulado, una metaheurística trayectorial que simula el proceso de reordenación de los átomos cuando se enfría un material. La metodología usada será la propuesta por Tello et al. [40] que consiste en optimizar la solución en 3 fases: primero se construirán unas soluciones iniciales utilizando unas plantillas, segundo se intenta conseguir una solución factible por cada solución inicial y por último se optimizan las soluciones factibles encontradas. Nos centraremos en analizar la generación de nuevas soluciones a partir de una dada (también conocidos como los entornos o vecindarios). En concreto se definirán una serie de movimientos que tratan de solucionar los problemas que se encontraron en los análisis. Estos movimientos están basados en crear una rejilla que restrinja los movimientos que se pueden realizar. Los resultados obtenidos por los nuevos movimientos son superiores a los de los movimientos existentes en los principales criterios del análisis: mejor valor objetivo encontrado, más instancias solucionadas y más soluciones factibles encontradas. En cuanto al criterio de velocidad, casi todos los nuevos movimientos son comparables a los ya existentes.--ABSTRACT--In this thesis we address the problem of assignment of air trafficc controllers to sectors. This problem belongs to the class of timetabling problems. The problem of assignment of air trafficc controllers to sectors is characterized by having a lot of restrictions that need to be satisfied. To solve this problem we will use simulated annealing, a trayectory-based metaheuristic that simulates the process of rearrangemente of the atoms when a material cools. The methodology used is the one proposed by Tello et al. [40] consisting of optimizing a solution in 3 phases: first we construct a set of initial solutions by means of a certain template, second we try to find a feasible solution out of each of the initial solutions and, lastly, the feasible solutions found in the Phase 2 are then optimized. We will focus on analyzing the construction of new solutions from a previous one (also known as environments or neighbourhoods). Specifically, we will define a set of movements trying to overcome certain problems encountered in the analyses. These movements will be based on the idea of a grid that restricts the movements allowed. The results show that the new movements are better that the state of the art movements with respect to the main criteria: better fitness value achieved, more problem instances solved and more feasible solutions found. With respect the speed criteria, almost all the new movements are comparable to the existing ones.