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

Autores

  • Ademir Aparecido Constantino Universidade Estadual de Maringá
  • Edilson Costa de Castro Universidade Estadual de Maringá
  • Silvio Alexandre de Araujo Universidade Estadual Paulista, Departamento de Ciências da Computação e Estatística, São José do Rio Preto(SP)
  • Cândido Ferreira Xavier de Mendonça Neto Universidade de São Paulo, Escola de Artes Ciências e Humanidades, São Paulo(SP).

DOI:

https://doi.org/10.5335/rbca.v8i2.5131

Palavras-chave:

Escalonamento de condutores, Heurística, Simulated Annealing, Algoritmos Genéticos

Resumo

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.

Downloads

Os dados de download ainda não estão disponíveis.

Biografia do Autor

  • Ademir Aparecido Constantino, Universidade Estadual de Maringá
    Departamento de Informática Área: Pequisa Operacional, Grafos, Programação Matemática, Heurísticas

Downloads

Publicado

01-09-2016

Edição

v. 8 n. 2 (2016)

Seção

Artigo Original

Licença

Licença Creative Commons
Todos os artigos estão licenciados com a licença Creative Commons Atribuição-NãoComercial-SemDerivações 4.0 Internacional. Autores que publicam nesta revista concordam com os seguintes termos:
a) Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Licença Creative Commons Attribution que permite o compartilhamento do trabalho com reconhecimento da autoria e publicação inicial nesta revista.
b) Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
c) Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado (Veja O Efeito do Acesso Livre).

Como Citar

[1]
2016. Pré-processamento do problema de cobertura de conjunto aplicado ao escalonamento de condutores. Revista Brasileira de Computação Aplicada. 8, 2 (set. 2016), 28–43. DOI:https://doi.org/10.5335/rbca.v8i2.5131.