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