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

Revista Brasileira de Computação Aplicada

Silvio Alexandre de Araujo¹  Ademir Aparecido Constantino²  Edilson Costa de Castro²  Cândido Ferreira Xavier de Mendonça Neto³ 

[1] Universidade Estadual Paulista, Departamento de Ciências da Computação e Estatística, São José do Rio Preto(SP);Universidade Estadual de Maringá;Universidade de São Paulo, Escola de Artes Ciências e Humanidades, São Paulo(SP).;

关键词: Escalonamento de condutores;    Heurística;    Simulated Annealing;    Algoritmos Genéticos;   

DOI  :  10.5335/rbca.v8i2.5131

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown