Pré-processamento do problema de cobertura de conjunto aplicado ao escalonamento de condutores

O problema de escalonamento de condutores (PEC) consiste em distribuir de maneira eficiente o quadro de viagens de uma empresa de transporte coletivo entre os condutores disponíveis. Esse problema é comumente modelado como um problema de cobertura de conjunto — PCC (set covering problem). Nesse caso, um bom resultado para o PEC depende de uma boa construção e resolução do PCC. Porém, a maior parte da bibliografia relacionada trata apenas da resolução das instâncias do PCC, sem avaliar a influência dos procedimentos com sua construção, aqui denominado de pré-processamento. Este trabalho propõe-se e investigar metodologias heurísticas baseadas em Simulated Annealing para o pré-processamento de instâncias do PCC, cujas características possibilitem os algoritmos de resolução obterem melhores resultados para o PEC. Nos testes efetuados, conseguiu-se uma redução de até 8% no custo das soluções apresentadas, em comparação com a resolução de instâncias geradas por um método clássico de geração do PCC.