A comparative analysis of simulated annealing and Variable Neighborhood Search in the ATCo work-shift scheduling problem

Tello Caballo, Faustino ORCID: https://orcid.org/0000-0002-0369-5798, Jiménez Martín, Antonio ORCID: https://orcid.org/0000-0002-4947-8430, Mateos Caballero, Alfonso ORCID: https://orcid.org/0000-0003-4764-6047 and Lozano Santiuste, Pablo (2019). A comparative analysis of simulated annealing and Variable Neighborhood Search in the ATCo work-shift scheduling problem. "Mathematics", v. 7 (n. 7); pp. 636-654. ISSN 2227-7390. https://doi.org/10.3390/math7070636.

Description

Title: A comparative analysis of simulated annealing and Variable Neighborhood Search in the ATCo work-shift scheduling problem
Author/s:
Item Type: Article
Título de Revista/Publicación: Mathematics
Date: July 2019
ISSN: 2227-7390
Volume: 7
Subjects:
Freetext Keywords: Air traffic management; Work-shift scheduling problem; Variable Neighborhood Search; Performance analysis
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[thumbnail of INVE_MEM_2019_310260.pdf]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB) | Preview

Abstract

This paper deals with the air traffic controller (ATCo) work shift scheduling problem. This is a multi-objective optimization problem, as it involves identifying the best possible distribution of ATCo work and rest periods and positions, ATCo workload and control center changes in order to cover an airspace sector configuration, while, at the same time, complying with ATCo working conditions. We propose a three-phase problem-solving methodology based on the variable neighborhood search (VNS) to tackle this problem. The solution structure should resemble the previous template-based solution. Initial infeasible solutions are built using a template-based heuristic in Phase 1. Then, VNS is conducted in Phase 2 in order to arrive at a feasible solution. This constitutes the starting point of a new search process carried out in Phase 3 to derive an optimal solution based on a weighted sum fitness function. We analyzed the performance in the proposed methodology of VNS against simulated annealing, as well as the use of regular expressions compared with the implementation in the code to verify the feasibility of the analyzed solutions, taking into account four representative and complex instances of the problem corresponding to different airspace sectorings.

Funding Projects

Type
Code
Acronym
Leader
Title
Government of Spain
MTM2017-86875-C3-3-R
Unspecified
Universidad Politécnica de Madrid
Toma de decisiones multicriterio y modelos de interdependencia para la gestión de riesgos. Seguridad en ATM
Government of Spain
MTM2014-56949-C3-2-R
Unspecified
Universidad Politécnica de Madrid
Apoyo a decisiones en análisis de riesgos. Seguridad operacional aérea

More information

Item ID: 63553
DC Identifier: https://oa.upm.es/63553/
OAI Identifier: oai:oa.upm.es:63553
DOI: 10.3390/math7070636
Official URL: https://www.mdpi.com/2227-7390/7/7/636
Deposited by: Memoria Investigacion
Deposited on: 28 Oct 2020 08:19
Last Modified: 28 Oct 2020 08:19
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM