Solving the airport slot allocation problem trough a constraint programming model

Dissertação de Mestrado Integrado em Engenharia Civil apresentada à Faculdade de Ciências e Tecnologia

A atribuição de slots nos principais aeroportos mundiais é efetuada de acordo com as complexas orientações constantes das World Slot Guidelines (WSG) estabelecidas pela International Air Transport Association (IATA). Nos últimos anos, o aumento da procura por parte dos passageiros tem levado à necessidade de maior quantidade de aeronaves, voos e consequentemente mais espaço nos aeroportos, os quais estão a atingir, se é que já não atingiram, o seu limite de capacidade. A comunidade científica tem investido no desenvolvimento de modelos e algoritmos de otimização para realizar a atribuição de slots de acordo com as orientações referidas. Este desenvolvimento tem sido acompanhado pelo crescimento evidente na área de computação e linguagem de programação que tem assim oferecendo novas ferramentas aplicáveis à resolução deste problema.A presesente dissertação insere-se no esforço de desenvolvimento de novas abordagens de otimização para a atribuição de slots nos aeroportos mais congestionados. Para tal, apoiar-se-á num novo modelo de por restrições. O desenvolvimento e aplicação deste modelo foram efetuados tendo por referência o modelo de otimização (ou programação) inteira-mista PSAM (Priority-based Slot Allocation Model), desenvolvido no Departamento de Engenharia Civil da Universidade de Coimbra. Este trabalho teve como objetivo a comparação, em termos de capacidade e velocidade de processamento, do modelo proposto com o referido acima, modelo esse que foi resolvido por um método de branch-and-cut.O trabalho realizado inseriu-se no projeto ASAP (Airport Slot Allocation Process), atualmente em curso na Universidade de Coimbra. Contou ainda com a colaboração da entidade coordenadora de slots de França, COHOR e com a École Nationale d’Aviation Civile (ENAC) através da realização de um estágio no grupo de investigação em otimização, que se dedica maioritariamente a modelos de otimização aplicados a problemas relacionados com a aviação.

The slot allocation process at major airports worldwide occurs in compliance with the World Slot Guidelines (WSG) established by the International Air Transport Association (IATA). Over the last few years, the general increase of demand from passengers led to the need for more aircraft, more flights and consequently more space at the airports which are reaching or already passing their capacity limit. The scientific community has been working on the development of models and optimization algorithms to perform the slot allocation in compliance with the guidelines referred above. This development has been supplemented by the growth in computing and programming language that has been offering new tools applicable to this problem.This dissertation is part of the effort to develop new approaches to slot allocation in the most congested airports. To do so, it will rely on a new constraint model. The development and application of this model having as a reference the PSAM (Priority-base Slot Allocation Problem) model, developed at the Department of Civil Engineering of the University of Coimbra. The objective was to compare the model now proposed with this other model which was solved by a branch-and-cut method, in terms of processing capacity and speed to obtain optimal slot allocation solutions.The work was carried out as part of the ASAP (Airport Slot Allocation Process) project, currently underway at the University of Coimbra, with the collaboration of the French slot coordinator entity COHOR and the École Nationale d'Aviation Civile (ENAC) which provided an internship with the optimization research group that mainly devote their work to aviation optimization practice.