Airport capacity management: towards a slot allocation modelling approach compliant with IATA rules

Abstract

Air traffic demand has grown to exceed available capacity during extended parts of each day at many of the busiest airports in the world. Absent opportunities for capacity expansion, this may require the use of demand management measures to restore the balance between scheduled traffic and available capacity. The main demand management mechanism in use today is the administrative slot allocation process operated by the International Air Transport Association (IATA), which is in place at the great majority of the busiest airports outside the United States. At these airports, airlines need to be assigned slots by a slot coordinator to schedule their flights. Slot allocation is driven by a set of rules and priorities specified in the IATA Worldwide Slot Guidelines (WSG). These rules introduce coupling constraints across the allocation of slots at multiple times of the day and multiple days of the year, resulting in a highly complex combinatorial problem that carries enormous weight for airlines, airports and passengers. In recent years, integer programming models have been proposed to support slot allocation by minimizing deviations from the airlines’ requests. However, due to the problem’s complexity, these models have been only successfully implemented at small size airports (up to 50,000 flights per year). In this thesis, we develop an original modelling approach aimed to advance existing slot allocation tools and procedures at the largest airports in the world. For that purpose, we formulate a novel integer programing model of slot allocation fully compliant with the WSG rules. The model – named Priority-based Slot Allocation Model (PSAM) – develops an original and efficient mathematical formulation that enables its implementation using exact optimization methods at airports at least with twice the size as previously considered. In order to solve the slot allocation problem at the busiest airports in the world, we also develop an algorithmic approach based on large-scale neighborhood search heuristics. The proposed algorithm combines a constructive heuristic to provide an initial feasible solution in short computational times, and an improvement heuristic that iteratively re-optimizes slot allocation by subdividing the slot requests into smaller subsets. Experimental results show that the algorithm proposed can provide optimal, or near-optimal solutions, in a few hours of computation in instances where direct implementation of PSAM with commercial solvers does not terminate after several days of computation. The modelling approach proposed in this dissertation was implemented at three Portuguese airports, a small one (Madeira), a mid-size one (Porto) and a large one (Lisbon), using highly detailed data on airline slot requests and airport capacity constraints. Results suggest that its implementation in support of slot allocation at major slot-coordinated airports worldwide can result in flight schedules that match better airlines’ requests and passenger demand. Equally important, the modelling approach developed in this dissertation can also be used to quantify the sensitivity of slot allocation decisions to the various priorities and requirements specified in the WSG. This allowed us to evaluate the impact of potential changes in the current slot allocation rules and procedures. Results obtained from many sensitivity analyses performed using PSAM show that adding even limited flexibility to the WSG can, on its own, bring considerable benefits in the short term to the slot allocation process.

A procura pelo tráfego aéreo tem aumentado nos aeroportos mais movimentados do mundo, ao ponto de superar a capacidade neles disponível durante longos períodos do dia. Na ausência de possibilidades de expansão, é essencial recorrer a medidas de gestão de procura para restabelecer o equilíbrio entre o número de voos calendarizados e a capacidade disponível no aeroporto. A principal medida de gestão de procura utilizada consiste no processo de atribuição de slots da Associação Internacional de Transportes Aéreos (IATA). De acordo com este processo, qualquer companhia aérea que pretenda operar um voo num aeroporto coordenado terá de obter antecipadamente uma permissão para a hora em que deseja que a aterragem ou descolagem do voo tenha lugar. O processo de atribuição de slots é regido por um conjunto de regras e prioridades que estão definidas nas IATA Worldwide Slot Guidelines (WSG). Estas regras introduzem um conjunto de restrições que tornam o problema de atribuição de slots bastante complexo. Nos últimos anos, vários modelos de programação inteira foram desenvolvidos com o intuito de auxiliar os coordenadores de slots a otimizar as suas decisões. No entanto, devido à complexidade do problema, estes modelos apenas podem ser eficazmente implementados em aeroportos de pequenas dimensões (até 50,000 voos por ano). Nesta tese é desenvolvida uma abordagem de modelação destinada a melhorar os procedimentos utilizados na atribuição de slots em aeroportos de grandes dimensões. Com esse propósito, é formulado um modelo de programação inteira de atribuição de slots totalmente compatível com as regras especificadas nas WSG. O modelo, denominado Priority-based Slot Allocation Model (PSAM), utiliza uma formulação matemática eficiente que permite a respetiva implementação através de métodos exatos de otimização em aeroportos com o dobro (ou mesmo mais) das dimensões previamente consideradas na literatura. No sentido de resolver o problema da atribuição de slots em aeroportos de ainda maiores dimensões é também desenvolvido um algoritmo aproximado que se baseia em heurísticas de large-scale neighborhood search. O algoritmo proposto combina uma heurística construtiva, utilizada para gerar solução iniciais admissíveis, e uma heurística de melhoramento, utilizada para melhorar essas soluções iterativamente. Os resultados experimentais da aplicação destas heurísticas mostram que o algoritmo proposto fornece, em poucas horas de computação, soluções ótimas ou muito próximas das ótimas quando a implementação direta de PSAM utilizando software comercial de otimização não fornece a solução ótima após vários dias de computação. A abordagem de modelação proposta nesta dissertação foi implementada em três aeroportos portugueses, nomeadamente um aeroporto de pequena dimensão (Madeira), um de média dimensão (Porto) e um de grande dimensão (Lisboa). Os estudos de caso analisados foram sustentados por dados detalhados referentes aos pedidos de slots feitos pelas companhias aéreas para esses aeroportos. Os resultados obtidos sugerem que a abordagem de modelação desenvolvida nesta tese pode auxiliar o coordenador de slots a tomar melhores decisões, nomeadamente encontrando soluções que se aproximam mais dos interesses das companhias aéreas e dos passageiros. Igualmente importante, a abordagem de modelação proposta nesta dissertação pode ser utilizada com o intuito de avaliar o impacto de pequenas alterações às regras existentes de atribuição de slots especificadas nas WSG. Resultados obtidos através de várias análises de sensibilidade realizadas usando o PSAM mostram que mesmo pequenas alterações podem, por si só, trazer no curto prazo consideráveis benefícios ao processo de atribuição de slots.