PROBLEMA DO VENDEDOR: UMA ABORDAGEM VIA ALGORITMOS GENÉTICOS

Dandara de Almeida Machado, Juliana Verga Shirabayash

Resumo


Neste trabalho, estudamos o problema do vendedor, que é uma variante do Problema do Caixeiro Viajante (PCV). O PCV resume-se em um determinado vendedor partindo de uma cidade inicial que deseja visitar todas as cidades listadas, e voltar à cidade de origem, com o objetivo de percorrer essas cidades uma única vez e com o menor caminho possível. Ele é um problema de otimização combinatória que serve de plataforma de teste para diversos métodos de resolução na mesma. Primeiramente foi feita a modelagem para o problema do vendedor, que diferentemente do problema do caixeiro viajante, não necessita retornar à cidade de origem. Para resolver tal problema, primeiramente utilizamos um algoritmo clássico de caminhos mínimos, que mostrou-se eficiente apenas para problemas pequenos; posteriormente utilizamos algoritmos genéticos, que são mais versáteis e encontram soluções boas e factíveis para diversos problemas, inclusive problemas do tipo do PCV, como é o caso do problema do vendedor.

Texto completo: PDF

Apontamentos

  • Não há apontamentos.