Universidade de Brasília
Departamento de
Ciência da Computação
A EVOLUÇÃO DA TOMADA DE DECISÃO
COLABORATIVA NO GERENCIAMENTO
DE FLUXO DE TRÁFEGO AÉREO
Antonio Carlos de Arruda Junior
Li Weigang
Leonardo Cruciol
2014
Sumário
• Introdução
• Fundamentação Teórica
– O Programa de Espera em Solo
– O CDM Clássico
– A Teoria de Matching
• CDM e Teoria dos Jogos
• Abordagem em Teoria dos Jogos
• Considerações Finais
2014
Introdução
• As centenas de voos realizados diariamente são reguladas
pelos órgãos de controle de tráfego aéreo (Air Traffic Control
– ATC)
• Centro Nacional da Navegação Aérea (CGNA)
– é o principal órgão executivo na realização das atividades de
Gerenciamento de Fluxo de Tráfego Aéreo (Air Traffic Flow
Management – ATFM) em âmbito nacional
• ATFM – busca garantir o movimento seguro, ordenado e
eficiente da aeronave durante todas as fases do voo, de forma
que estas possam cumprir com os horários previstos de saída
e chegada, mantendo perfis “ótimos” de voo sem, contudo,
afetar os padrões de segurança
2014
Introdução
• Apesar do processo de alocação ser realizado
com certa antecedência, situações adversas como
o aumento de demanda e/ou a possibilidade de
mau
tempo
podem
resultar
em
congestionamentos de aeroportos ou setores do
cenário aéreo
• Para se garantir a segurança os órgãos de
controle de tráfego aéreo (ATC) buscam reduzir a
quantidade de voos nos locais afetados através
da imposição de medidas restritivas
2014
Introdução
• Por motivos de economia e segurança, dentre as
medidas mais utilizadas estão as que resultam no
atraso das aeronaves em solo
• Essas medidas preveem a redução da capacidade
operacional
dos
aeroportos
afetados,
possibilitando o atraso das aeronaves antes de
sua decolagem
• Tal situação gera a necessidade de alteração do
cronograma original dos voos que irão utilizar os
SLOTS das pistas desses aeroportos
2014
Fundamentação Teórica
• O programa de espera em solo (Ground Delay Program –
GDP) é um processo que gerencia os recursos disponíveis
(SLOTS) através de premissas definidas na filosofia da
tomada de decisão colaborativa (Collaborative Decision
Making – CDM)
• Essas premissas estão relacionadas a conceitos de
propriedade, priorização, justiça e eficiência na alocação de
recursos
• O paradigma central do modelo CDM, criado na década de
1990, é o de permitir o relacionamento dos diversos
intervenientes afetados de forma que a troca de
informações entre eles resulte em melhores decisões no
gerenciamento do tráfego aéreo
2014
Fundamentação Teórica
• Programa de espera em solo (GDP)
– realiza procedimentos caracterizados pela redução
da capacidade de operação de um ou mais
aeroportos (Airport Arrival Rate – AAR)
– faz com que multiplos voos afetados sejam
atrasados com segurança, enquanto estão no solo,
nos aeroportos de origem
2014
Fundamentação Teórica
• Programa de espera em solo (GDP)
– trata da análise e solução de duas questões
principais:
• quais aeronaves deverão ser atrasadas, e
• por quanto tempo elas deverão ser seguradas no solo
2014
Fundamentação Teórica
Programa de espera em solo
(Ground Holding Program – GDP)
2014
Fundamentação Teórica
• Algoritmo Ration-By-Schedule
– trata da redistribuição dos SLOTS para a nova
quantidade de aeronaves que podem operar por hora
no aeroporto
– cria uma nova lista de SLOTS com horários revisados,
alocando os voos do antigo cronograma na nova lista,
preservando a ordem original de chegada definida
para cada aeronave
• O efeito dos atrasos pode gerar atrasos de horas
para alguns voos
2014
Fundamentação Teórica
• Etapa de substituições e cancelamentos
• Oportunidade das companhias aéreas analisarem o
resultado informado pelo algoritmo e tomarem decisões
visando mitigar os efeitos adversos de um GDP em suas
operações, devendo:
– comunicar tempestivamente possíveis atrasos, devidos a falhas
mecânicas e outros problemas operacionais;
– comunicar tempestivamente cancelamentos, devido a ajustes
internos e decisões estratégicas das companhias aéreas em seus
voos, e;
– comunicar tempestivamente substituições de voos entre SLOTS
de “propriedade” da mesma companhia aérea, onde um voo
pode ser priorizado em detrimento de outro.
2014
Fundamentação Teórica
• Algoritmo Compression
– quando um SLOT é deixado vazio, ele tenta alocar a
ele outro voo da companhia aérea proprietária
daquele SLOT
• se ele encontrar um voo elegível, respeitando-se as
restrições de horário, ele reserva o SLOT vazio ao voo
• se não existirem voos disponíveis, então o algoritmo buscará
um voo possível pertencente à outra companhia aérea
– caso um voo elegível seja encontrado, ele realiza a troca do voo
entre os SLOTS das companhias aéreas, trocando também sua
propriedade
– mas se não encontrar, irá declarar o SLOT como inutilizado
2014
Fundamentação Teórica
• Algoritmo Compression
– alguns autores mostraram que:
• ele não consegue garantir o conceito de direitos de
propriedade de SLOTS para as companhias aéreas
• os mecanismos existentes podem ser manipulados
quanto à omissão ou atraso no envio de informações
sobre cancelamentos, e
• o algoritmo nem sempre obtém resultados estáveis de
alocação (Balikrishnan, 2007; Schummer e Vohra, 2013)
2014
Fundamentação Teórica
• A Teoria de Matching – criada para tratar de mercados
caracterizados por recursos disponíveis que são negociados
entre jogadores específicos
• As preferências de cada jogador em relação aos recursos
são estratégias que serão avaliadas por um mecanismo de
alocação
• Mecanismo deve encontrar um resultado satisfatório
alocando jogadores entre si, levando em conta as
preferências de cada um
• Matching – representa o resultado final contendo a
alocação ou troca de recursos entre todos os jogadores
presentes nestes mercados
2014
Fundamentação Teórica
• Caso nenhum agente encontre uma forma de
conseguir um resultado melhor do que o
resultado proposto pelo mecanismo de matching,
dizemos que o resultado é estável.
• A noção de estabilidade é um conceito central na
teoria dos jogos cooperativos
• Na teoria de matching ela determina uma
característica
fundamental
de
qualquer
mecanismo de alocação:
– fornecer resultados ótimos aos jogadores
2014
CDM e Teoria dos Jogos
• Apesar de existirem diversas abordagens propondo
variadas soluções, as pesquisas de Ball et al. (2001a)
e Wolfe et al. (2009) indicam que existe já há algum
tempo, a tendência em se utilizar modelos de teoria
dos jogos para análise de procedimentos CDM na
área de gerenciamento de tráfego aéreo (ATM).
2014
Abordagem em Teoria dos
Jogos
• Algoritmos de alocação de slots, utilizando pagamentos
laterais associados com trocas complexas de slots, foi
verificado que:
– Rassenti et al. (1982) criaram um mecanismo de leilão combinatorial
para slots de aeroportos;
– Ball et al. (2005) retomaram o estudo, análise de objetivos e questões
referentes a leilões em problemas da aviação;
– Vossen e Ball (2006a) modelaram um novo framework de intercâmbio
utilizando o Compression com trocas singleton;
– Vossen e Ball (2006b) criaram a formalização de trocas mais complexas
envolvendo conjuntos de slots, onde modelos relacionados levam à
solução via mercados de matching.
2014
Abordagem em Teoria dos
Jogos
• Em 2007, Balakrishnan apresentou um trabalho
contendo duas abordagens diferentes com base em
modelos de mercados para resolver a questão de
realocação de slots de pouso de um aeroporto.
– Na primeira abordagem, foi analisado o problema da troca de slots
sem pagamentos monetários, onde foi mostrada a existência de
alocações estáveis no resultado do modelo. O mecanismo utilizado foi
o Top Trading Cycle (TTC) para alocação de casas.
– Na segunda abordagem, um método baseado em leilão para trocas
com pagamentos laterais entre as companhias aéreas. O modelo de
pagamentos proposto utiliza mecanismos de precificação VickreyClarke-Groves (VCG) aproximados em combinação com uma
abordagem baseada em otimização para o mercado.
2014
Abordagem em Teoria dos
Jogos
• Em 2013, Schummer e Vohra apresentaram o
trabalho Assignment of Arrival Slots, contendo novas
propostas sobre teoria de matching de um lado, para
o problema da espera em solo.
– As principais contribuições deste trabalho foram a formalização
e análise de atributos das companhias aéreas, e a proposta de
um mecanismo que satisfaz alguns desses atributos
formalizados, chamado TradeCycle.
– Esse mecanismo é uma generalização do Top Trading Cycle (TTC)
de Shapley e Scarf (1974), que já apareceu em outros modelos
relacionados.
2014
Abordagem em Teoria dos
Jogos
• Em 2013, Ribeiro e Weigang publicaram um modelo baseado
em sequenciamento de partidas em aeroportos com teoria
dos jogos. Este trabalho propôs um sequenciamento de
aeronaves por meio de negociação de slots utilizando
algoritmos Ration by Schedule e Compression.
• Em 2014, proposto por Arruda Jr. et al., procurou expandir os
limites da Collaborative Decision Making clássica (CDM)
através da inclusão de um novo jogador no processo de
tomada de decisão: os gestores dos aeroportos. Este trabalho
utilizou a teoria de matching para resolver o problema de
alocações de recursos envolvendo cenários multiagentes.
2014
Considerações Finais
• O aumento da utilização do meio de transporte
aéreo nos últimos anos tem causado um impacto
significativo na forma como o gerenciamento de
recursos aeronáuticos e aeroportuários é
realizado.
• No Brasil, além da construção de novos
aeroportos, expansão de pistas e concessões da
administração aeroportuária, uma evolução e
adaptação dos processos existentes fazem-se
claramente necessária.
2014
Fim
Perguntas ?
2014