Anais do Simpósio Brasileiro de Pesquisa Operacional

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.