Otimização de negociação dinâmica para múltiplas áreas restritas de fluxo no programa de opções de trajetórias colaborativo

Tese (doutorado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2015.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.The optimization of resources in air traffic management is a computationally complex problem. During the last year, the Collaborative Trajectory Options Program (CTOP) had started as an operational evolution of current air traffic management programs by Federal Aviation Administration in USA. This program is part of Next Generation Air Transportation System initiative and makes possible to improve airlines' business results. Airlines have a great issue to decide how many routes might be sent for each flight, because of the uncertainty in this complex process. The development of a solution that handle dynamically, as soon as CTOP has started, it was very complex considering the information modeling to be used. A wrong strategy could achieve delays several times greater. There is a solution for this problem, which used greedy algorithms to find out the routes with minimum delay for a specific airline in CTOP. However, this solution does not handle the uncertainty involved once some unreal assumptions are made. So, this thesis presents an innovation model to suggest how many routes should be sent by intelligent systems to handle uncertainties. The negotiation process was divided into two levels. First, using the computational model Single Games for CTOP (SG-CTOP), how to realize a dynamical and automatic optimization in the dispute process of available slots for multiple flow constrained areas during the first negotiation, which there is no previous knowledge about competitors. Second, using the computational model Repeated Games for CTOP (RG-CTOP), how the competitors' strategy could change the strategy of an airline and makes possible to learn by competitors' reputation, adjusting the past strategies. The achieved results by both computational models are promising for airlines. In the case studies, 20.000 CTOP negotiations were generated. Thus, it was studied several cases and strategies used in CTOP. The SG-CTOP achieved a performance better, or equal, in 97% of CTOP negotiations, when it was compared to others strategies, representing a delay reduction of 537 hours for the airline. The RG-CTOP achieved a rate improvement about 21% for an airline, when it was used a learning process by adapting its strategies against competitors to be allocated in better available slots