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

Suárez Cuesta, Adán (2017). Asignación de controladores a sectores aéreos mediante metaheurísticas trayectoriales: búsqueda tabú. Tesis (Master), E.T.S. de Ingenieros Informáticos (UPM).

Descripción

Título: Asignación de controladores a sectores aéreos mediante metaheurísticas trayectoriales: búsqueda tabú
Autor/es:
  • Suárez Cuesta, Adán
Director/es:
  • Mateos Caballero, Alfonso
Tipo de Documento: Tesis (Master)
Título del máster: Inteligencia Artificial
Fecha: Junio 2017
Materias:
Escuela: E.T.S. de Ingenieros Informáticos (UPM)
Departamento: Inteligencia Artificial
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (1MB) | Vista Previa

Resumen

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.

Más información

ID de Registro: 47930
Identificador DC: http://oa.upm.es/47930/
Identificador OAI: oai:oa.upm.es:47930
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 02 Oct 2017 06:43
Ultima Modificación: 02 Oct 2017 06:43
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM