Problema do Caixeiro Viajante

Prévia do material em texto

Problema do Caixeiro Viajante 
Problemas de caixeiro viajante são muito comuns em diversas aplicações do cotidiano. Podemos 
destacar, por exemplo, a rota de um entregador de pizzas, a rota de um caminhão de uma loja de 
móveis ou até mesmo a programação do roteiro de uma viagem de férias. O princípio básico de um 
problema de caixeiro viajante consiste em, partindo de um ponto inicial, passar uma única vez por 
todas as localidades apresentadas no problema e, no final, retornar ao ponto de partida de modo que o 
custo total seja o menor possível. O custo pode ser a distância total percorrida, o tempo ou o preço 
referente a esse deslocamento. Podemos também considerar outros elementos a serem minimizados 
nesse problema, tais como risco de acidente, risco de assalto, entre outros. 
Para exemplificar um problema de caixeiro viajante, vamos apresentar a seguinte situação: 
Um viajante, partindo de Curitiba, deverá passar por Ponta Grossa, Arapongas, Londrina, 
Maringá e, em seguida, retornar a Curitiba. Utilizando o WinQSB, determine a rota cuja distância total 
a ser percorrida seja a menor possível. 
Para resolvermos um problema de caixeiro viajante, primeiro precisamos conhecer os custos 
entre todas as localidades apresentadas. No nosso exemplo, precisamos das distâncias entre as 
localidades. Uma forma bastante simples é utilizarmos algum aplicativo ou site que forneça a distância 
entre duas localidades. Em particular, utilizaremos o Google Maps para obtermos as distâncias 
necessárias. Como não foi fornecido o endereço exato, basta digitarmos o nome da cidade de origem e 
o nome da cidade de destino nos respectivos espaços. Em situações reais, deveremos digitar o 
endereço exato das localidades do problema. 
A figura a seguir ilustra a utilização do Google Maps. 
 
 Muitas vezes é comum o Google apresentar mais do que uma rota entre duas cidades. O critério 
de escolha de qual rota depende de vários fatores. No nosso caso, escolheremos a rota de menor 
distância. 
 A tabela a seguir apresenta as distâncias obtidas. É importante ressaltar que, mesmo utilizando 
o mesmo recurso para obtermos as rotas, é possível que haja divergência entre as distâncias obtidas 
quando pesquisadas em datas diferentes, pois, no caso de não digitarmos o endereço exato das 
localidades, mas apenas o nome das cidades, pode haver mudança nos pontos de referência utilizados 
pelo Google e, consequentemente, mudança nas distâncias apresentadas entre as cidades. Também é 
importante ressaltar que nem sempre a distância referente à ida é igual à distância referente ao trajeto 
de volta. 
 
 
 
 
 
 Curitiba Ponta Grossa Arapongas Londrina Maringá 
Curitiba 0 114 378 387 426 
Ponta Grossa 114 0 264 273 311 
Arapongas 378 264 0 36,3 66,7 
Londrina 387 273 36,3 0 98,9 
Maringá 426 311 66,7 98,9 0 
 
 Agora que já temos as distâncias entre as localidades, vamos utilizar o WinQSB para 
encontrarmos a solução ótima do problema. 
 O primeiro passo é clicar em Iniciar e depois em Todos os Programas. Em WinQSB, clicaremos 
em Network Modeling. 
 
 
 Fazendo isso, você irá ver uma tela como a apresentada abaixo. 
 
 
 
 O próximo passo é clicar em File, New Problem. 
 
 
 Na tela a seguir, selecionaremos a opção Traveling Salesman Problem, que se refere ao 
problema de caixeiro viajante. É fundamental colocar o número de nós do problema no campo Number 
of Nodes. No caso do nosso problema, o número de nós é igual a 5 pois temos 5 cidades. Como o 
objetivo é minimizar o custo total, a opção Minimization deve ser marcada no campo Objective 
Criterion. 
 
 
 Para alterar o nome dos nós, é só clicar em Edit, Node Names. Em seguida basta digitar os 
nomes das cidades. 
 
 Clicando em OK, teremos os nomes das cidades apresentados na tabela. Agora é só adicionar as 
distâncias entre as cidades. Muito cuidado com o separador das casas decimais. Para o WinQSB o 
padrão de separador é o ponto e não a vírgula, como estamos habituados. O valor 98,9, por exemplo, 
precisa ser escrito como 98.9. 
 
 
 O próximo passo é clicar em Solve and Analyse, Solve the Problem. 
 
 No caso de problemas de caixeiro viajante, o WinQSB possui quatro métodos diferentes pra 
fornecer a solução ótima do problema. Como a maioria dos métodos utilizados consiste em métodos 
heurísticos, ou seja, métodos cuja solução é aproximada, pode haver diferença entre as soluções 
obtidas pelos diferentes métodos. Nesse caso, para que tenhamos sempre a melhor solução possível, o 
ideal é resolver o problema utilizando, a cada vez, um método diferente e, ao final, escolher a solução 
de menor custo total. 
 
Pelo primeiro método, temos a seguinte solução: 
 
 
 
 
Para obtermos as demais soluções e decidirmos, de fato, qual delas é a que minimiza a distância total percorrida, 
precisaremos clicar no ícone que está localizado próximo ao canto superior esquerdo do WinQSB e, em seguida, 
resolvermos novamente o problema. 
Utilizando o segundo método, a solução obtida é: 
 
 
 
Observe que ocorreu uma alteração na rota e que a distância total percorrida é menor do que a obtida 
anteriormente. No entanto, precisaremos verificar as demais soluções. 
Pelo terceiro método, temos: 
 
 
 
Nesse caso, houve um empate na distância total. Em relação à rota, observe que na primeira linha aparecem as 
cidades De Arapongas e Maringá. Como a rota é cíclica, a leitura da resposta deve ser feita na linha 4 que está na 
segunda metade da tabela, onde aparecem as cidades de Curitiba e Londrina. Mas antes de verificarmos qual é a 
melhor rota, devemos ainda verificar qual é a solução fornecida pelo quarto método: 
 
 
 
 
 
 
 
 Para o nosso exemplo, a melhor solução obtida foi através dos métodos Cheapest Insertion 
Heuristic, Two-way Exchange Improvement Heuristic e Branch and Bound. No caso de empate, 
independentemente do método utilizado, o importante é escrevermos corretamente a rota ótima bem 
como a distância total percorrida. 
Rota ótima: Curitiba – Londrina – Arapongas – Maringá – Ponta Grossa – Curitiba 
Distância total: 915 km 
 Note que, por exemplo, a solução obtida pelo método da vizinhança mais próxima (Nearest 
Neighbor Heuristic), o total a ser percorrido é maior do que a solução ótima do problema e, 
consequentemente, a rota fornecida por esse método também é diferente. 
 
 Por esse motivo é interessante resolver o problema de caixeiro viajante pelos quatro métodos 
oferecidos pelo WinQSB.