A Comparative Analysis of Simulated Annealing and Variable Neighborhood Search in the ATCo Work-Shift Scheduling Problem

Faustino Tello, Antonio Jiménez-Martín, Alfonso Mateos and Pablo Lozano
Additional contact information
Faustino Tello: Departamento de Inteligencia Artificial, E.T.S.I. Informáticos, Universidad Politécnica de Madrid, Campus de Montegancedo S/N, 28660 Boadilla del Monte, Spain
Antonio Jiménez-Martín: Departamento de Inteligencia Artificial, E.T.S.I. Informáticos, Universidad Politécnica de Madrid, Campus de Montegancedo S/N, 28660 Boadilla del Monte, Spain
Alfonso Mateos: Departamento de Inteligencia Artificial, E.T.S.I. Informáticos, Universidad Politécnica de Madrid, Campus de Montegancedo S/N, 28660 Boadilla del Monte, Spain
Pablo Lozano: Departamento de Inteligencia Artificial, E.T.S.I. Informáticos, Universidad Politécnica de Madrid, Campus de Montegancedo S/N, 28660 Boadilla del Monte, Spain

Mathematics, 2019, vol. 7, issue 7, 1-18

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.

Keywords: air traffic management; work-shift scheduling problem; variable neighborhood search; performance analysis (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/7/636/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/7/636/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:7:y:2019:i:7:p:636-:d:249315

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().