Atualmente o conceito de Otimização
Combinatória está bem formulado como um princípio que fundamenta a análise de
muitos problemas de alocação ou de tomada de decisão. A abordagem de um
problema de tomada de decisão complexo, envolvendo a seleção de valores para um
número de variáveis relacionadas, usualmente tem como enfoque um único
objetivo projetado para quantificar performance e medir a qualidade da decisão.
Este único objetivo é maximizado (ou minimizado, dependendo da formulação)
sujeito às restrições que limitam a seleção dos valores possíveis das variáveis
de decisão.
Se um único aspecto de um problema pode
ser isolado e caracterizado adequadamente por um objetivo, podendo ser, por
exemplo: lucro ou custo em um cenário de negócios, velocidade ou distância em
um problema físico, retorno esperado em um ambiente de investimento de risco,
ou bem-estar social no contexto do planejamento governamental, então uma
aplicação de otimização configura-se naturalmente adequada.
Existe uma variedade muito grande de
problemas no mundo real que podem ser resolvidos utilizando-se métodos de
Otimização Combinatória. Todavia, encontrar soluções ótimas, ou mesmo
aproximadas, para esses tipos de problemas é um desafio nem sempre fácil de ser
vencido. Para alguns desses problemas são conhecidos métodos exatos para a sua
solução; já para outros, técnicas que permitem alcançar resultados aproximados
são utilizados como única alternativa. Nem mesmo com o poder computacional
atual pode resolver-se a maioria desses problemas em tempo considerado
razoável, podendo levar-se muitos anos para a execução de tal tarefa.
A Otimização Combinatória na
Aviação
Além de diversos, os problemas de
otimização na aviação comercial são encadeados, compondo, na verdade, um único
e grande problema, que por ser tão complexo, necessita ser subdividido em
porções menores para que possa vir a ser resolvido. Todavia, mesmo quando
decomposto em subproblemas, dificuldades para a sua resolução persistem. Em
particular, cada um desses subproblemas constitui-se em uma tarefa extremamente
árdua para processamento manual, mesmo quando são realizadas por profissionais
qualificados e extremamente experientes.
Restringindo-se apenas ao planejamento de
vôos das empresas aéreas, é necessário definir-se inicialmente que rotas
deverão ser operadas. Para tanto, é necessário
analisar-se todas as demandas existentes entre as diversas regiões envolvidas
e, assim, decidir quais devam ser os pares de aeroportos a interligar em
trechos de vôos da empresa. Uma vez escolhidas as rotas, é necessário
dividi-las em subconjuntos adequados à operação pelas diversas frotas de
aeronaves disponíveis.
A seguir, deve ser definida, para cada voo de um dado subconjunto, a aeronave específica (de sua frota associada) que irá
operá-lo. Alocadas as aeronaves aos vôos, os subconjuntos devem ser divididos
em jornadas de trabalho com início e fim numa mesma base de tripulantes; isso
deve ser feito com o cuidado de minimizar os gastos com diárias de alimentação,
pernoites em hotéis, inatividades em cidades fora das bases, vôos extras para
reposicionamento de tripulantes, realização de deslocamentos, etc.
Definidas as jornadas de trabalho, essas
devem ser distribuídas aos tripulantes observando-se a Regulamentação dos
Aeronautas, pedidos daqueles funcionários e as regras específicas da empresa
para efetuar a alocação. Concluída a distribuição das tarefas de voo e de solo
(reservas e sobreavisos), deve-se cuidar da execução da escala de tripulantes,
de forma a garantir eventuais substituições diante dos mais diversos
imprevistos (de ordem material, aeroportuário, clima ou pessoal), sempre a um
custo mínimo. A coordenação de vôos deve também estar pronta para sugerir
cancelamentos de vôos e posicionamento de aeronaves em decorrência dos mesmos
motivos.
Todos esses problemas de planejamento
levam a uma explosão combinatória considerável, por mais simples que alguns
possam parecer. Uma escala de tripulantes envolvendo 400 comissários de bordo e
800 jornadas mensais de trabalho pode produzir mais de um milhão e meio de
restrições, acarretadas somente pela Legislação dos Aeronautas.
Além dessas restrições, efetuar a
atribuição de forma a provocar um mínimo de desvio na quantidade de horas
trabalhadas pelos tripulantes (visando ao equilíbrio da remuneração entre
eles), pode tornar a decisão de alocação extremamente delicada. Tarefas como a
de composição de jornadas de trabalho de uma pequena base de tripulantes,
envolvendo pouco mais de 1.300 trechos de vôos semanais, podem gerar um
problema de recobrimento envolvendo algumas centenas de milhões de
possibilidades distintas.
Resolver esses problemas sem apoio de
ferramentas apropriadas de decisão (baseadas em modelos matemáticos e
algoritmos de otimização) requer muito tempo e demanda o trabalho de muitas
pessoas. Mais grave ainda, o resultado obtido é, comumente, muito aquém da melhor
solução possível e normalmente acarreta enormes prejuízos financeiros para as
empresas que assim operam.
