ANÁLISE COMPARATIVA DE MÉTODOS PARA RESOLVER O PROBLEMA DE PROGRAMAÇÃO DE TRIPULAÇÕES

Resumo

Este trabalho trata do Problema da Programação de Tripulações (PPT), o qual visa determinar
um conjunto de jornadas de trabalho para as tripulações de menor custo e tal que a
programação dos veículos seja realizada com sucesso. Como restrição, cada jornada deve
atender à legislação trabalhista do setor. Neste trabalho são comparados quatro diferentes
métodos de geração e seleção de colunas, sendo que cada coluna corresponde a uma jornada
para o PPT. No primeiro método são geradas colunas considerando intervalos de tempo, ao
longo do dia, nos quais pode ocorrer a troca de tripulações. No segundo, as jornadas geradas
apresentam um dado tempo mínimo de duração. No terceiro método é implementada a
heurística de Chvátal, a qual seleciona colunas para o PPT. O quarto método combina o
segundo e o terceiro métodos. São apresentados resultados comparativos com dados reais,
mostrando a possibilidade da utilização prática desses métodos em casos brasileiros.

Palavras-chave: Escala de motoristas e cobradores, Programação de tripulações, Geração de
colunas.