Algoritmos para a Versão Estocástica de 2-Estágios do Problema do Caixeiro Viajante

Vol 51, 2019 - 111513
Pôster
Favoritar este trabalho
Como citar esse trabalho?
Resumo

O problema do caixeiro-viajante consiste em, dado um conjunto de cidades, encontrar um circuito de custo mínimo que visite cada cidade exatamente uma vez. Por ser um problema NP-difícil, não existem algoritmos exatos que encontram uma solução ótima em tempo polinomial, a menos que P = NP. Entretanto, algoritmos de aproximação para a versão métrica do caixeiro-viajante são conhecidos. Esses, por sua vez, consideram que os custos para viajar entre as cidades estão disponíveis e não variam com o tempo, o que não se verifica em diversas aplicações.
Para incorporar essas características, considera-se a versão estocástica de dois estágios do problema, em que as incertezas são representadas por uma quantidade finita de cenários, cada um associado a uma probabilidade de ocorrência e a diferentes custos para viajar entre as cidades. O algoritmo pode adquirir trechos que conectam cidades (arestas) no primeiro estágio, pelo custo original, ou em cada cenário do segundo estágio, por um custo possivelmente maior. O objetivo é a construção de um circuito para cada cenário, a partir de arestas selecionadas no primeiro e segundo estágios, de modo a minimizar o custo total esperado da solução.
Neste trabalho, utiliza-se um framework evolutivo para a resolução de problemas estocásticos de dois estágios associado a algoritmos para a versão métrica do caixeiro-viajante. Foram realizados testes com instâncias geradas aleatoriamente e outras obtidas na literatura.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Departamento de Computação / Centro de Ciências Exatas e de Tecnologia / Universidade Federal de São Carlos
  • 2 Instituto de Matemática e Computação / Universidade Federal de Itajubá
Eixo Temático
  • OC – Otimização Combinatória
Palavras-chave
Problema do caixeiro viajante
Problemas estocásticos de dois estágios
algoritmos de aproximação