Meta-Heurísticas para o Problema de Programação de Tripulações

Aborda-se aqui o problema de programação de tripulações de transporte em massa (PPT) também conhecido como Crew Scheduling. O problema consiste em gerar um conjunto de escalas de trabalho, atribuindo tarefas a tripulações, com menor custo possível, e ao mesmo tempo satisfazendo restrições tais como leis trabalhistas, legislações federais, sindicais e normas internas da empresa. O presente trabalho aborda o problema utilizando em sua solução as meta-heurísticas Busca Tabu e Iterated Local Search. Realiza-se um estudo comparativo entre os métodos aqui aplicados e uma metodologia exata de programação matemática, onde o PPT é modelado como um problema de particionamento de conjuntos. Através deste é apresentado de forma categórica baseando-se em resultados concretos a grande eficiência das meta-heurísticas em fornecer rapidamente soluções de alta qualidade para problemas reais tais como o PPT. Dentre os métodos aqui aplicados, aquele que baseia-se na meta-heurística Iterated Local Search é o que mais se destaca, fornecendo os melhores resultados. A solução final deste problema é dada por um conjunto de jornadas diárias de trabalho. As instâncias de testes foram geradas baseando-se estritamente em dados reais de uma empresa do setor de transporte público coletivo que opera no município de Belo Horizonte/MG.