Baixe o app para aproveitar ainda mais
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.
Compartilhar