Categoria Melhor Monografia 2º Lugar: Otimização de negociação dinâmica para múltiplas áreas restritas de fluxo no programa de opções de trajetórias colaborativo

Abstract

A otimização de recursos no gerenciamento de tráfego aéreo é, por si só, um problema computacionalmente complexo. Durante o último ano, foi colocada em operação nos EUA uma evolução de alguns dos atuais programas de gerenciamento de tráfego aéreo, o Collaborative Trajectory Options Program (CTOP), pela Federal Aviation Administration. Esse programa faz parte da iniciativa Next Generation Air Transportation System e possibilita a melhoria dos resultados de negócio pelas companhias aéreas. Existe uma grande dificuldade pelas companhias aéreas, dada pela incerteza inerente ao complexo processo, na definição de quantas rotas devem ser enviadas para cada voo. O desenvolvimento de uma solução que trate de maneira dinâmica, quando o CTOP é iniciado, se mostrou computacionalmente complexa do ponto de vista da modelagem das informações a serem utilizadas. A utilização de uma estratégia errada pode gerar atrasos diversas vezes maiores. Existe uma solução para este problema, na qual foram utilizados algoritmos de busca greedy para apresentar as rotas com menor atraso para uma determinada companhia aérea envolvida no CTOP, porém esta solução não trata a incerteza envolvida ao serem assumidas premissas não reais. Assim, esta tese apresenta um modelo inovador que utiliza sistemas inteligentes para o tratamento de incertezas ao sugerir ao especialista quantas rotas deverão ser enviadas. O processo de disputa apresentado foi dividido em dois níveis. Primeiro, resolvido pelo modelo computacional Single Games for CTOP (SG-CTOP), como realizar a otimização dinâmica e automática do processo de disputa de slots disponíveis para múltiplas áreas restritas de fluxo durante a primeira rodada de negociações, no qual não existe qualquer conhecimento prévio dos seus concorrentes. Segundo, resolvido pelo modelo computacional Repeated Games for CTOP (RG-CTOP), como a estratégia de cada companhia irá afetar a estratégia da outra e possibilitar o aprendizado de reputações adaptando, assim, as estratégias utilizadas nas negociações anteriores. Os resultados alcançados pelos dois modelos se mostraram promissores para as companhias aéreas. Em dois estudos de caso foram gerados 20.000 negociações em CTOP, assim, retratando os mais diversos casos e estratégias utilizadas dentro do CTOP. O modelo SG-CTOP alcançou um desempenho superior, ou igual, em 97% dos casos, quando comparado com as melhores estratégias atuais, reduzindo em 537 horas de atrasos para uma determinada companhia. Quanto ao modelo RG-CTOP, foi alcançada uma taxa de melhoria aproximada de 21%, para uma determinada companhia aérea, ao se considerar o aprendizado e adaptação de estratégias frente aos seus concorrentes na disputa dos melhores slots.