AULA 5 Problema do caixeiro viajante

Prévia do material em texto

PESQUISA OPERACIONAL 
AULA 5 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Prof. Ricardo Zanardini 
 
 
 
 
2 
CONVERSA INICIAL 
Olá! Seja bem-vindo à nossa aula de número 5! 
Veremos como é possível, dentre várias possibilidades, determinar qual é 
o menor caminho entre dois pontos, pois problemas dessa natureza são muito 
comuns no nosso cotidiano e no cotidiano de muitas empresas. 
Aprenderemos também que é possível resolver problemas de 
roteirização, também conhecidos como problemas do caixeiro viajante. 
Vamos começar com os problemas de caminho mínimo, preparado? 
Para que possamos ter uma ideia inicial sobre o que é um problema de 
caminho mínimo, é importante ver o exemplo a seguir. 
TEMA 1 - CAMINHO MÍNIMO 
Um veículo, após uma longa viagem, chegou ao perímetro urbano da 
cidade onde deverá fazer uma entrega. Nesse exato instante o veículo encontra-
se parado no ponto A. Observe na figura abaixo que há diferentes trajetos 
possíveis para que o motorista chegue ao destino que está localizado no mapa 
pelo ponto H. 
Considerando os sentidos de cada rua bem como as distâncias entre os 
cruzamentos, determine todos os trajetos possíveis entre os pontos A e H, sem 
que o motorista passe duas vezes pelo mesmo local, e a distância total de cada 
trajeto. Em seguida, determine qual é o trajeto mais curto entre os pontos A e H, 
o qual será adotado pelo motorista do caminhão. 
 
 
 
3 
 
Deu uma olhada no exemplo? Agora que tal pensar na solução intuitiva 
desse problema? 
Bom, agora que já temos uma ideia do que é um problema de caminho 
mínimo, vamos aprender como é possível resolver problemas assim, simples ou 
mais elaborados, utilizando a pesquisa operacional como ferramenta. 
Um problema de caminho mínimo consiste basicamente em determinar o 
caminho de menor custo entre dois nós de um determinado grafo (diagrama). Os 
nós desse grafo são pontos de referência de uma determinada região. Esses 
pontos podem ser esquinas, terminais de ônibus, portos, aeroportos ou outros 
locais específicos a serem considerados. Os arcos fornecem como informação, 
a distância, tempo, valor ou outro tipo de custo entre dois nós consecutivos. 
Problemas de caminho mínimo são bastante frequentes na área de logística. 
Para ilustrarmos um problema de caminho mínimo bem como a 
resolução do problema utilizando o WinQSB, vamos considerar o seguinte 
grafo ilustrando algumas localidades e as respectivas distâncias, em 
quilômetros, entre os nós. 
 
 
4 
 
Nesse caso, o nosso objetivo é determinar o menor caminho possível a 
ser percorrido para que um automóvel parta do ponto A e chegue ao ponto G. 
Para resolvermos um problema de caminho mínimo, o primeiro passo é 
construir uma tabela contendo os custos de cada arco, ou seja, os custos entre 
dois nós consecutivos. 
 
Para utilizarmos o WinQSB, vamos clicar em Iniciar, WinQSB. Em 
seguida, é só clicar em Network Modeling: 
 
 
5 
 
O próximo passo é clicar em File, New Problem. 
 
 
 
 
6 
Agora vamos selecionar a opção Shortest Path Problem. Para esse 
exemplo, devemos considerar 7 nós, ou seja, digitar o número 7 no campo 
Number of Nodes e depois clicar em OK. 
 
Fazendo isso, teremos a seguinte tabela no WinQSB: 
 
Precisamos agora efetuar a troca dos nomes dos nós. Basta clicar em Edit 
e selecionar a opção Node Names: 
 
 
 
7 
 
Agora é só digitar os respectivos nomes e clicar em OK: 
 
 
 
 
 
 
8 
Preenchendo a tabela de acordo com os dados do problema, temos: 
 
Para resolvermos o problema, podemos selecionar a opção Solve and 
Analyze, Solve the Problem ou então basta clicar no ícone para 
obtermos a respectiva solução. 
A tela a seguir mostra as opções de porto inicial e ponto final do problema. 
Nesse caso, selecionaremos os pontos A e G, respectivamente: 
 
Para obtermos a solução do problema, basta clicar em Solve. 
 
 
 
9 
A resposta do problema consiste em, partindo do nó A, passar pelos nós 
D e F até chegarmos ao destino que é o nó G. 
 
Caminho: A-D-F-G 
Total: 22 km 
Para compreender um pouco mais ainda sobre os problemas do caminho 
mínimo, leia a seguir um artigo muito interessante que envolve parâmetros 
incertos e restrições de tempo. 
http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-
74382009000200012 
TEMA 2 - PROBLEMA DO CAIXIERO VIAJANTE 
Outro tipo muito comum dos problemas de pesquisa operacional é o 
problema do caixeiro viajante. 
Problemas de caixeiro viajante são comuns em situações onde existe a 
necessidade de, partindo de uma certa origem, passarmos uma única vez por 
uma série de locais pré-estabelecidos e, em seguida, retornarmos ao local de 
origem, de maneira que o custo total seja o menor possível. 
 
 
 
10 
Esse custo pode ser considerado como o tempo, a distância, o valor... 
Existem problemas dessa natureza com restrições e problemas sem 
restrições, vamos conferir cada um deles! 
O exemplo a seguir nos mostra o que é um problema de caixeiro viajante 
sem restrições. 
Roteirização 
A figura abaixo apresenta a localização de um escritório, que se encontra 
no ponto A, e de três clientes desse escritório que estão localizados nos pontos 
B, C e D, de acordo com a figura a seguir. 
 
Um funcionário desse escritório precisa entregar alguns documentos a 
cada um desses clientes e, em seguida, retornar ao escritório. É fácil perceber 
que há alternativas diferentes em relação à ordem de entrega desses 
documentos. Por exemplo, o funcionário, partindo do ponto A, pode ir para B e 
depois para C e D, retornando logo após ao ponto A. Ele pode também partir de 
A, passar por C, D e B e retornar ao ponto A e assim por diante. A escolha da 
ordem das entregas pode interferir na distância total percorrida pelo funcionário. 
Para isso, é importante conhecer as distâncias entre todas as localidades 
envolvidas. A tabela a seguir apresenta as distâncias, em quilômetros, entre os 
pontos A, B, C e D. 
 
 
11 
 
Com base nessas informações, escreva todas as possibilidades de rotas 
existentes para que o funcionário, partindo de A, passe uma única vez pelas 
demais localidades apresentadas e, em seguida, retorne ao ponto A. Determine 
também a distância total percorrida em cada uma dessas rotas e indique, dentre 
as rotas apresentadas, qual é a rota cuja distância total percorrida é a menor 
possível. 
 
Se quiser aprender um pouco mais sobre problemas de caixeiro viajante, 
leia o texto a seguir atentamente, pois ele poderá ajudar e tirar alguma dúvida 
que tenha ficado. 
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 
 
 
12 
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. 
 
 
 
13 
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. 
 
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. 
 
 
14 
 
Fazendo isso, você irá ver uma tela como a apresentada abaixo. 
 
 
 
 
 
15 
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. 
 
 
16 
 
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. 
 
 
 
 
17 
 
No caso de problemas de caixeiro viajante, o WinQSB possui quatro 
métodos diferentes para 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. 
 
 
 
 
18 
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: 
 
 
 
19 
 
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: 
 
 
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. 
 
 
 
20 
 
Por esse motivo é interessante resolver o problema de caixeiro viajante 
pelos quatro métodos oferecidos pelo WinQSB. 
O texto a seguir irá nos mostrar que atualmente a aplicação da 
roteirização é um importante diferencial para as empresas de sucesso. 
http://www.administradores.com.br/artigos/economia-e-financas/a-
aplicacao-da-roteirizacao-de-transportes-como-diferencial-competitivo/48906/ 
O texto a seguir nos mostra um estudo de caso que trata da importância 
do uso de softwares de roteirização na gestão de transportes e os respectivos 
benefícios. É interessante dar uma conferida para aprimorar ainda mais seus 
conhecimentos! 
http://www.ead.fea.usp.br/Semead/7semead/paginas/artigos%20recebid
os/Opera%E7oes/OP18-_Softwares_de_roteiriza%E7%E3o.PDF 
E a seguir, no botão Saiba Mais, tem um texto sobre diversos sistemas de 
roteirização e programação de veículos que são utilizados atualmente. 
http://www.scielo.br/pdf/pope/v21n2/a07v21n2 
Sugestão de leitura 
Chegamos ao final de mais uma aula! Esperamos que esses assuntos 
possam ser úteis a você. 
Para saber mais sobre problemas de caminho mínimo, a sugestão é a 
leitura da seção 6.3 da obra Pesquisa Operacional, Hamdy A. Taha, editora 
Pearson, que pode ser facilmente encontrada na biblioteca virtual. 
 
 
 
21 
Veja uma excelente alternativa para sabermos mais sobre a teoria, 
algoritmos e problemas envolvendo grafos. 
http://www.ft.unicamp.br/~magic/ft024/apografos_ceset_magic.pdf