Métodos exatos para resolver o problema de programação da tripulação

Este trabalho tem como objetivo implementar um metodo de otimizacao para o Problema da Programacao de Tripulacoes (PPT), o qual visa determinar um conjunto de jornadas de trabalho para as tripulacoes, de tal forma que a programacao dos veiculos seja realizada com o menor custo possivel. Como restricoes, cada jornada deve atender a legislacao e a convencao coletiva de trabalho do setor. Neste trabalho sao apresentadas e comparadas quatro diferentes metodologias de geracao de colunas para o PPT, definindo assim problemas de programacao linear inteira com variaveis binarias. A primeira metodologia consiste em definir um intervalo de tempo durante o qual podera ocorrer a troca de tripulacoes. Na segunda metodologia as jornadas possuem pelo menos um dado tempo minimo de duracao. Na terceira metodologia e implementada a heuristica de Chvatal. A quarta metodologia apresenta a implementacao de um metodo hibrido de geracao de colunas para o PPT. Neste trabalho apresentam-se resultados comparativos obtidos com a aplicacao das metodologias a problemas reais.