O Problema do Caixeiro Viajante

O Problema do Caixeiro Viajante (PCV) é um problema que tenta determinar a menor rota para percorrer uma série de cidades (visitando uma única vez cada uma delas), retornando à cidade de origem. Ele é um problema de otimização do tipo NP-difícil inspirado na necessidade dos vendedores em realizar entregas em diversos locais (as cidades) percorrendo o menor caminho possível, reduzindo o tempo necessário para a viagem e os possíveis custos com transporte e combustível. Basicamente, dado um grafo G = (V, E, w) deve-se encontrar um ciclo Hamiltoniano de custo mínimo.

Para solucionar esse problema pode ser utilizado o algoritmo Twice-Around, cujo pseudocódigo é mostrado na figura 1.

Figura 1: Pseudocódigo do algoritmo Twice-Around

Desse modo, foi elaborado um programa em Python baseado no algoritmo Twice-Around acima, no intuito de se gerar 10 soluções diferentes para o problema do caixeiro viajante e listar as 3 soluções que possuem o melhor custo e as 3 soluções que possuem o pior custo.

Inicialmente, o programa lê uma matriz de adjacências de um arquivo .txt, e a partir dela gera dois grafos, G e CopyG, como mostra a figura 2 a seguir.

Figura 2: Matriz de adjacência é transformada em grafos

Como é possível notar no trecho de código acima, o processo de transformação de matriz de adjacência é realizado 10 vezes, e são criados dois grafos iguais em cada uma das vezes para que se possa a partir deles obter o Prim, que no nosso código não mantém o peso das arestas após gerar a mst, então o CopyG é utilizado para preservar o peso das arestas das arestas iniciais.

Após serem gerados os grafos, a função twice_around é chamada e ela segue o algoritmo de mesmo nome. Inicialmente se obtém a mst do grafo G a partir do código Prim, que é praticamente igual aquele já feito pelo grupo. Depois disso, as arestas da mst são dobradas ao transformá-lo em dígrafo, o que permite que seja percorrido um circuito euleriano na árvore. Então, é definido o ciclo euleriano e ele então é percorrido de modo a se obter a soma dos pesos das arestas nele visitado. O algoritmo então retorna o peso total do ciclo euleriano e o caminho que foi percorrido. O trecho de código que representa esse processo é mostrado na figura 3.

Figura 3: Trecho do código do Twice-Around

Por fim, é criado um arquivo circuito.txt que contém os 10 circuitos gerados e o peso de cada um, como é mostrado na figura 4. Cabe lembrar que, devido ao fato do código do Prim não possuir raiz fixa, cada vez que o programa roda vão ser gerados circuitos com pesos diferentes, então será analisado os que foram gerados apenas em nosso teste.

Figura 4: Circuitos e pesos gerados

Como é possível notar pela imagem acima, as três melhores soluções são aquelas dos caminhos (0), (1) e (5) cujo peso é igual a 790. Já as três piores soluções são aquelas dos caminhos (2), (4) e (6), sendo que a do caminho (4) é a que possui o pior custo possível, 873. A diferença entre o pior custo e o melhor custo é de 83. Como já dito anteriormente, a variação do peso decorre do fato de que o Prim feito não possui raiz fixa, iniciando seu caminho de forma variada toda vez que é chamado, gerando essas pequenas variações.

A figura 5 mostra como o grafo se encontrava inicialmente e como ele ficou depois do Prim e de ser transformado em dígrafo.

Figura 5: Representa como o grafo é alterado ao longo do programa