A Otimizacao CombinatoriaAtualmente o conceito de OtimizacaoCombinatoria esta bem formulado como um principio que fundamenta a analise demuitos problemas de alocacao ou de tomada de decisao. A abordagem de umproblema de tomada de decisao complexo, envolvendo a selecao de valores para umnumero de variaveis relacionadas, usualmente tem como enfoque um unicoobjetivo projetado para quantificar performance e medir a qualidade da decisao.Este unico objetivo e maximizado (ou minimizado, dependendo da formulacao)sujeito as restricoes que limitam a selecao dos valores possiveis das variaveisde decisao. Se um unico aspecto de um problema podeser isolado e caracterizado adequadamente por um objetivo, podendo ser, porexemplo: lucro ou custo em um cenario de negocios, velocidade ou distancia emum problema fisico, retorno esperado em um ambiente de investimento de risco,ou bem-estar social no contexto do planejamento governamental, entao umaaplicacao de otimizacao configura-se naturalmente adequada.Existe uma variedade muito grande deproblemas no mundo real que podem ser resolvidos utilizando-se metodos deOtimizacao Combinatoria. Todavia, encontrar solucoes otimas, ou mesmoaproximadas, para esses tipos de problemas e um desafio nem sempre facil de servencido. Para alguns desses problemas sao conhecidos metodos exatos para a suasolucao; ja para outros, tecnicas que permitem alcancar resultados aproximadossao utilizados como unica alternativa. Nem mesmo com o poder computacionalatual pode resolver-se a maioria desses problemas em tempo consideradorazoavel, podendo levar-se muitos anos para a execucao de tal tarefa.A Otimizacao Combinatoria naAviacaoAlem de diversos, os problemas deotimizacao na aviacao comercial sao encadeados, compondo, na verdade, um unicoe grande problema, que por ser tao complexo, necessita ser subdividido emporcoes menores para que possa vir a ser resolvido. Todavia, mesmo quandodecomposto em subproblemas, dificuldades para a sua resolucao persistem. Emparticular, cada um desses subproblemas constitui-se em uma tarefa extremamenteardua para processamento manual, mesmo quando sao realizadas por profissionaisqualificados e extremamente experientes. Restringindo-se apenas ao planejamento devoos das empresas aereas, e necessario definir-se inicialmente que rotasdeverao ser operadas. Para tanto, e necessarioanalisar-se todas as demandas existentes entre as diversas regioes envolvidase, assim, decidir quais devam ser os pares de aeroportos a interligar emtrechos de voos da empresa. Uma vez escolhidas as rotas, e necessariodividi-las em subconjuntos adequados a operacao pelas diversas frotas deaeronaves disponiveis. A seguir, deve ser definida, para cada voo de um dado subconjunto, a aeronave especifica (de sua frota associada) que iraopera-lo. Alocadas as aeronaves aos voos, os subconjuntos devem ser divididosem jornadas de trabalho com inicio e fim numa mesma base de tripulantes; issodeve ser feito com o cuidado de minimizar os gastos com diarias de alimentacao,pernoites em hoteis, inatividades em cidades fora das bases, voos extras parareposicionamento de tripulantes, realizacao de deslocamentos, etc.Definidas as jornadas de trabalho, essasdevem ser distribuidas aos tripulantes observando-se a Regulamentacao dosAeronautas, pedidos daqueles funcionarios e as regras especificas da empresapara efetuar a alocacao. Concluida a distribuicao das tarefas de voo e de solo(reservas e sobreavisos), deve-se cuidar da execucao da escala de tripulantes,de forma a garantir eventuais substituicoes diante dos mais diversosimprevistos (de ordem material, aeroportuario, clima ou pessoal), sempre a umcusto minimo. A coordenacao de voos deve tambem estar pronta para sugerircancelamentos de voos e posicionamento de aeronaves em decorrencia dos mesmosmotivos.Todos