Este trabalho foi publicado pelo Galoá e tem um DOI depositado. Para citar este trabalho, use um dos padrões abaixo:
Caso você seja um dos co-autores e queira cadastrar esse trabalho no seu Currículo Lattes, use o seguinte código: doi > 10.59254/sbpo-2019-106762
Se você NUNCA registrou um DOI no seu Lattes, veja nosso tutorial!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.
Com ~200 mil publicações revisadas por pesquisadores do mundo todo, o Galoá impulsiona cientistas na descoberta de pesquisas de ponta por meio de nossa plataforma indexada.
Confira nossos produtos e como podemos ajudá-lo a dar mais alcance para sua pesquisa:
Esse proceedings é identificado por um DOI , para usar em citações ou referências bibliográficas. Atenção: este não é um DOI para o jornal e, como tal, não pode ser usado em Lattes para identificar um trabalho específico.
Verifique o link "Como citar" na página do trabalho, para ver como citar corretamente o artigo