Tema
Estudaremos neste projeto o problema de otimização de escalonamento de viagens e tripulantes em companhias aéreas brasileiras.
Resumo
O problema do planejamento automatizado de escalas de tripulantes vem sido estudado a algumas décadas e representa um desafio do ponto de vista computacional com implicações práticas importantes.
Os gastos com a tripulação de uma empresa aérea representam o segundo maior custo operacional (da ordem de 20%), perdendo apenas para as despesas com combustível. Dessa forma, o planejamento otimizado no escalonamento de tripulantes pode representar economias significativas para as empresas. Por esse motivo, tal problema de otimização tem sido amplamente estudado pela comunidade de pesquisa operacional.
Dado o grande número de variáveis e restrições exigidas para se modelar o planejamento corretamente, diversas técnicas de otimização aproximadas vêm sido sugeridas. Isso porque o problema é de natureza NP-difícil, tornando sua solução computacionalmente inviável em qualquer situação realista.
Tradicionalmente o escalonamento de tripulantes tem sido atacado resolvendo dois subproblemas separados de forma sequencial, cada um de complexidade menor do que o original. Descreveremos brevemente os dois subproblemas abaixo.
O primeiro deles trata da determinação de um conjunto de viagens ótimo, i.e., de menor custo, que cubra cada etapa de um conjunto de voos exatamente uma vez. Uma viagem é formada por uma sequência de jornadas de trabalho (sequência de etapas executados em um dia, onde o local de chegada de um voo coincide com o local de partida do próximo). O local de partida da primeira etapa de uma viagem deve ser o mesmo local de chegada da última etapa, o qual deve ser uma das bases de habitação dos tripulantes. Uma viagem válida deve ainda respeitar uma série de regras e restrições da regulamentação imposta pela agência nacional de aviação. Por exemplo, deve se limitar o número máximo de pousos e horas de voo executadas durante uma jornada de trabalho, bem como o número máximo de dias que a viagem pode durar. Note que a geração de uma viagem nesse primeiro subproblema é um processo que independe dos tripulantes disponíveis. Ela depende apenas do conjunto de voos oferecido pela empresa.
Obtido o conjunto de viagens ótimas, no segundo subproblema deve-se atribuir as viagens aos tripulantes, considerando uma série de restrições trabalhistas. Além das viagens, também deve-se atribuir outras atividades como folgas, reservas, sobreavisos, cursos, etc. Tais atividades podem ser previamente atribuídas, facilitando assim o processo de otimização. As restrições trabalhistas que regem a geração de uma escala legal controlam, por exemplo, o número máximo de horas voadas e de jornada de trabalho no mês, número mínimo de folgas, tempo de descanso mínimo entre viagens, etc. O objetivo, no final, é encontrar uma solução de custo ótimo, de modo que cada viagem seja corretamente tripulada.
Ambos os subproblemas podem ser modelados em termos de um problema de programação matemática conhecido por recobrimento de conjuntos (set covering), com um número enorme de variáveis. Tendo em vista sua natureza NP-difícil, várias heurísticas são utilizadas na busca de uma solução aproximada obtida com tempo de processamento aceitável.
Objetivos
O primeiro objetivo é realizar um estudo mais detalhado sobre o tema com base nos artigos acadêmicos publicados, visando um bom entendimento sobre a formulação do problema e seus métodos de resolução.
O segundo objetivo é fazer experimentos computacionais, realizando estudos para determinar até que ponto o problema pode ser resolvido de forma exata usando os otimizadores disponíveis. A seguir, propõem-se a implementação de heurísticas e meta-heurísticas (a serem definidas) para comparação de resultados e desempenho, bem como o estudo da formulação integrada dos dois subproblemas (viagens + atribuição).
Todas as modelagens e implementações, tanto na geração de viagens quanto de escalas legais, situar-se-ão no contexto brasileiro de regulamentação e estrutura de pagamento, utilizando como modelo uma das maiores empresas do país.
Cronograma
- Março: escolha do supervisor;
- Abril: definição do tema e pesquisa bibliográfica;
- Maio-Junho: definição da proposta e testes com ferramentas de otimização;
- Julho-Setembro: pesquisa e implementação de heurísticas e meta-heurísticas; entrega da versão preliminar;
- Outubro: testes e comparação entre os resultados obtidos;
- Outubro-Novembro: preparação do pôster, apresentação e redação final da monografia.
Atividades Realizadas
- Definição do orientador;
- Criação do blog referente ao progresso do projeto;
- Avaliação de trabalhos de formatura anteriores;
- Estudo sobre o tema através da leitura de livros e publicações acadêmicas;
- Reuniões periódicas com o orientador;
- Criação da página web;
- Redação da parte introdutória da monografia;
- Contato com os diretores da companhia aérea GOL.
Estrutura Esperada
- Introdução: apresentação e contextualização do problema, e breve descrição do trabalho;
- Conceitos e Tecnologias: explicação detalhada do problema, e descrição das tecnologias, heurísticas e meta-heurísticas utilizadas;
- Metodologia: informações sobre o método de trabalho;
- Resultados: apresentar resultados obtidos através de comparações entre as diferentes técnicas de resolução do problema (tabelas e gráficos);
- Conclusões: discussão sobre resultados, comentários finais e perspectivas futuras;
- Parte Subjetiva: relação entre a experiência obtida no trabalho e o BCC;
- Bibliografia.