APLICAÇÃO DE PESQUISA OPERACIONAL EM LOGÍSTICA: COMO

205

Anhanguera Educacional S.A. Correspondência/Contato Alameda Maria Tereza, 2000 Valinhos, SP - CEP 13278-181 [email protected] [email protected] Coordenação Instituto de Pesquisas Aplicadas e Desenvolvimento Educacional - IPADE Publicação: 5 de março de 2010

Trabalho realizado com o incentivo e fomento da Anhanguera Educacional S.A.

Ana Lúcia R. M. Vital de Oliveira

Professora Orientadora: Ms. Jeanne Dobgenski

Curso: Administração

FACULDADE ANHANGUERA DE VALINHOS

Trabalho apresentado no 9º Congresso Nacional de Iniciação Científica – CONIC.

Participação no Encontro Interno de Iniciação Científica - 2009.

RESUMO

Dentro das organizações a logística é considerada uma área essencial, cujo gerenciamento sempre tem em vista atender e satisfazer as necessidades dos clientes, os quais pesquisam preços menores e entregas rápidas. Em contrapartida, as organizações buscam menor custo para fabricação, alta produtividade e uma logística eficiente. Para se chegar a esses resultados é possível utilizar recursos matemáticos como as técnicas de Pesquisa Operacional que possui ferramentas apropriadas para solucionar problemas logísticos reais. Este trabalho se refere a um estudo sobre a modelagem matemática, com uso de grafos, de um problema real que tem por objetivo encontrar um bom percurso para coletar lixo seletivo num condomínio residencial. Na abordagem apresentada, especifica-se o modelo desenvolvido para o problema, buscando expor como foram definidas as etapas de sua construção e os resultados computacionais obtidos – melhoria de 50% na distância percorrida com relação à rota original.

Palavras-Chave: pesquisa operacional; logística; grafos; modelagem matemática; problema do caixeiro viajante.

ANUÁRIO DA PRODUÇÃO DE INICIAÇÃO CIENTÍFICA DISCENTE

Vol. XII, Nº. 13, Ano 2009

APLICAÇÃO DE PESQUISA OPERACIONAL EM LOGÍSTICA: COMO RESOLVER UM PROBLEMA DO CAIXEIRO VIAJANTE DE UMA COOPERATIVA DE COLETA DE LIXO RECICLÁVEL

ANUIC_N13_miolo_marcas.pdf 205 13/4/2010 12:25:28

206 Aplicação de pesquisa operacional em logística: como resolver um problema do caixeiro viajante de uma cooperativa de coleta de lixo reciclável

Anuário da Produção de Iniciação Científica Discente • Vol. XII, Nº. 13, Ano 2009 • p. 205-221

1. INTRODUÇÃO

Nota-se que a logística ocorre em praticamente todas as atividades que envolvem

planejamento, organização, controle e distribuição. Sendo ainda, uma atividade presente

tanto no ambiente pessoal quanto no empresarial.

Um simples exemplo que ilustra a logística no contexto pessoal é o planejamento

da atividade de fazer compras. Percebe-se que essa atividade requer a verificação de

alguns critérios e detalhes que se parece com os processos conhecidos de logística e que

são praticados dentro das organizações. Entre esses critérios decisivos em ambas as

situações, encontram-se, os custos dos produtos, a data de validade, a finalidade, a marca

e a qualidade do produto, os quais são exemplos de informações consideradas no

processo de compra. A análise desses dados influencia na escolha dos produtos, o que

interfere diretamente em decidir qual é o fornecedor mais adequado.

Por exemplo, observa-se que a realização de compras no supermercado envolve

tarefas como embalagem dos produtos, retorno à residência e a organização dos itens

comprados em seus respectivos lugares, as quais respeitam um planejamento definido

anteriormente. Partindo deste simples exemplo se verifica o quão importante é o ato de

planejar na operacionalização de processos que envolvem várias etapas.

A logística é definida pelo Conselho de Gerenciamento da Cadeia de

Suprimentos citado por Tadeu (2008, p. 17) como “processo de planejamento,

implementação e controle eficiente e eficaz do fluxo e armazenagem de mercadorias,

serviços e informações relacionadas desde o ponto de origem até o ponto de consumo,

com objetivo de atender às necessidades do cliente”. Ou seja, a logística por sua

concepção é utilizada de forma imperceptível em diversas situações corriqueiras dentro

ou fora das organizações. Este é um dos motivos pelos quais pesquisadores e empresários

tem mostrado interesse por essa área em busca de melhorias na execução dos processos,

serviços e produtos.

Nota-se um crescimento acelerado entre as organizações no que tange à

competitividade. Dentro das empresas a área de logística tem um papel de grande

relevância e atua em parceria com outras áreas, com a finalidade de melhorar

procedimentos, rotinas e outros fatores que sejam determinantes em seu desempenho.

A Pesquisa Operacional (PO) oferece ferramentas matemáticas que podem ser

usadas em diversos níveis de gestão, as quais simulam computacionalmente tomadas de

decisão. Esse fator mostra que o uso da PO oferece muitas vantagens aos gestores, pois

permite simular situações/decisões antes de realmente executá-las. E, ainda, partindo de


Ana Lúcia Rodrigues de Moraes Vital de Oliveira 207


pressupostos como minimizar custos, aumentar a produtividade, reduzir o tempo na

distribuição e, por conseqüência, maximizar o lucro, há empresas que investem em

ferramentas computacionais de PO que viabilizam alcançar tais resultados.

Nesse contexto, cita-se o trabalho desenvolvido por Cezar (2003, p. 5-6) que

propôs um método alternativo para solucionar um problema de carregamento de caixas

em container. A técnica desenvolvida é baseada em Algoritmos Genéticos – área da

Inteligência Artificial. Os resultados da pesquisa comprovaram que o desempenho do

método é 10% mais eficiente na alocação das caixas com relação à técnica que a empresa

utilizava.

A pesquisa realizada por Brasil (1999, p. 4-6) teve por objetivo mostrar a

possibilidade de empregar PO para resolver problemas comuns de uma cidade. A autora

estudou características como mapa, distribuição geográfica das escolas municipais e

população nos bairros, que são informações fundamentais a serem analisadas quando se

tem o objetivo de construir uma nova escola municipal. Na pesquisa realizada foram

apresentados dois modelos matemáticos que podem ser usados para representar esse

problema, possibilitando sua solução por técnica de PO.

Silveira et al. (2009, p.1) apresentaram um estudo sobre o uso de Programação

Linear (PL) – uma técnica de PO, para resolver um problema de logística, mais

especificamente o problema de alocação de produção e distribuição. Para isso os autores

exemplificaram a utilização de um Solver, baseado em PL, resolvendo um problema

amostral. Esse Solver é uma ferramenta computacional desenvolvida como um

complemento do Microsoft Excel, Lotus 1-2-3 e Quatro-Pro (SILVEIRA et al., 2009).

Para se ter uma visão clara e estruturada de um problema real e de sua

abordagem é possível usar algum recurso matemático para modelá-lo. Essa ação permite

visualizar características existentes que não são facilmente observadas sem uma análise

mais profunda do problema. Além disso, a modelagem facilita a identificação da melhor

técnica a ser utilizada para solucioná-lo, o que implica na necessidade do modelo ser o

mais próximo possível da situação real. No entanto, o processo de modelagem não é

simples e requer conhecimento das ferramentas disponíveis e muito estudo sobre a forma

mais adequada de representar o problema.

Muitos autores têm apresentado os estudos realizados para modelar o problema

que buscaram resolver. Mistro (1992) em sua dissertação de mestrado apresentou as

adaptações que realizou em equações matemáticas, propostos por outros autores, com o

objetivo de descrever o comportamento da concentração de mercúrio metálico em rios.




Estudou uma área específica do Rio Madeira, entre as cidades de Guajará-Mirim e Porto

Velho (Rondônia).

Maitelli e Silva (2004) desenvolveram um software com ambiente gráfico para

possibilitar que alunos do curso de Engenharia de Controle modelassem sistemas que

requerem um alto grau de conhecimento em matemática e física. Segundo os autores “o

software permite a construção de modelos de sistemas de diversos domínios da física

utilizando o conceito de grafo de ligação” (MAITELLI; SILVA, 2004).

Esses dois exemplos mostram duas formas distintas de modelagem de

problemas: uma usando equações matemáticas e outra com grafo. Neste trabalho,

apresenta-se um estudo realizado para modelar um problema real de coleta de lixo

seletivo, sendo que o modelo foi feito com a representação em grafo.

2. OBJETIVO

A proposta da pesquisa realizada foi mostrar a possibilidade de usar em logística

conhecimentos de PO como forma de melhorar os procedimentos adotados por uma

empresa. Nesse sentido, optou-se por estudar um problema real de coleta de lixo seletivo,

cujo objetivo é encontrar um percurso melhor do que o realizado pela cooperativa

responsável. O problema é clássico em logística - busca determinar uma rota, e a técnica

de PO a ser utilizada depende da abordagem do problema, ou seja, da sua modelagem

matemática. Portanto, optou-se realizar a modelagem em grafos devido à facilidade de

representar, visualizar os pontos da rota a ser percorrida e pela extensa oferta de métodos

matemáticos para solução computacional – tendo em vista que não era objetivo dessa

pesquisa desenvolver uma ferramenta específica para esse fim. Também, ressalta-se que

este estudo não buscou apresentar as equações matemáticas que podem representar o

problema abordado.

3. METODOLOGIA

Para compreender o problema abordado, base para as análises sobre a aplicação de PO em

logística, foi necessário entender as necessidades da cooperativa, os recursos disponíveis

para realizar a coleta e delimitar uma rota. Desta forma, escolheu-se estudar apenas o

percurso feito pela cooperativa dentro de um condomínio residencial, o qual será

chamado neste documento de Condomínio.




Como a cooperativa não possui um roteiro que descreva o percurso realizado

semanalmente no Condomínio - uma vez que o condutor que faz a coleta segue um

caminho padrão já memorizado, foi necessário que a pesquisadora mapeasse os pontos de

parada para coleta e a rota realizada. Para isso, indicaram-se no mapa do Condomínio os

pontos de parada e o percurso realizado. Também foi registrada a distância percorrida e o

tempo gasto.

Tendo os dados necessários para iniciar o processo de modelagem, seguiu-se

para um levantamento bibliográfico e leitura de artigos relacionados com o tema, com a

finalidade de estudar as características e etapas necessárias para sua realização.

Após a modelagem do problema, efetuou-se a sua validação que é uma etapa

indispensável para identificar se o modelo proposto é adequado à solução do problema

ou não. Essa fase mostrou a fundamental importância de levantar o maior número

possível de informações sobre o problema a ser resolvido, pois após estudar o problema e

suas características, concluiu-se que se tratava do clássico Problema do Caixeiro Viajante e

são conhecidas várias técnicas heurísticas para resolvê-lo. No entanto, a modelagem

realizada não está adequada à solução pelos procedimentos computacionais disponíveis –

cedidos por alunos de Ciência da Computação. Ou seja, para validar o modelo construído

foi necessário desenvolver um programa computacional com um algoritmo de busca de

solução que fosse compatível com o grafo resultante.

Por fim, foram feitos os testes computacionais e as análises sobre os resultados

encontrados.

4. DESENVOLVIMENTO

A primeira necessidade para modelar um problema é entender como ocorre o processo de

modelagem. Segundo Goldbarg e Luna (2005, p.1) “os modelos, para serem

implementáveis, devem ser livres de pequenos detalhes onerosos.”, ou seja, devem ser

simplificados sem deixar de apresentar uma equivalência adequada com o problema real.

Desta forma, tendo em vista o objetivo a ser alcançado, deve-se identificar as

características, parâmetros e demais informações que levem à correta interpretação e

apresentação do modelo.

Um fator de extrema importância a ser considerado é que a modelagem permitirá

ou não atingir o objetivo desejado. Segundo o esquema apresentado na Figura 1

(RANGEL, 2001) é possível identificar na fase de simulação se o modelo precisa ou não de




ajustes. Por isso é fundamental programar uma fase de testes antes de estabelecer o

modelo final.

Figura 1 – Esquema para construção de modelos matemáticos (RANGEL, 2001).

Como requisito fundamental para compreender o estudo realizado, descreve-se o

cenário do problema abordado. Para isso considera-se, ainda, o esquema da Figura 1,

apresentando um paralelo do problema e a sua representação em cada etapa do esquema.

Para isso, estabelecem-se as referências apresentadas no Quadro 1.

Quadro 1 – Referências estabelecidas entre as etapas do esquema e o estudo realizado.

Etapa esquema Etapa estudo

Sistema Real Problema da Coleta de Lixo Seletivo

Definição e Descrição do Problema Coleta de Dados

Modelo Matemático Modelagem do Problema com o uso de grafos

Solução do Modelo Simulação Computacional do Modelo Proposto

Implementação da Solução Etapa a ser realizada na continuação da pesquisa

Os quatro primeiros itens indicados no Quadro 1 são apresentados na seqüência,

de forma a explicar como foram considerados e representados no estudo realizado. A

última etapa – Implementação da Solução – como foi descrito, faz parte da continuação da

pesquisa e não será apresentado neste documento, pois depende de uma apresentação

dos resultados à cooperativa e do empenho dela em operacionalizar a solução proposta.

4.1. Problema da coleta de lixo seletivo no condomínio

Situado interior de São Paulo o Condomínio possui atualmente 181 moradias, 18 obras em

andamento e 59 terrenos, totalizando 258 lotes. Estes lotes são interligados por ruas de

circulação de mão dupla - vai e volta; ruas sem saída e a avenida principal que possui

uma pista de rolagem para ir e outra para voltar – separadas por um canteiro central.

Sistema Real

Definição e Descrição do Problema

Modelo Matemático

Solução do Modelo

Implementação da SoluçãoDecisão Teórica x Política

Revisão

Sistema Real

Definição e Descrição do Problema

Modelo Matemático

Solução do Modelo

Implementação da SoluçãoDecisão Teórica x Política

Revisão




Como essa avenida está diretamente conectada à guarita (portão de entrada e/ou saída do

Condomínio) ao seguir em linha reta, ela é a via de maior tráfego no Condomínio (ver

Figura 2).

A Cooperativa recolhe o lixo reciclado uma vez por semana no Condomínio -

segunda-feira, preferencialmente, na parte da manhã. A coleta do lixo é feita por três

cooperados: o condutor do caminhão e dois ajudantes que pegam o lixo.

O condutor do caminhão é experiente e tem a preocupação de reduzir a distância

percorrida e o tempo para finalizar o processo completo. Mas, no percurso, muitas vezes,

encontram-se algumas dificuldades como carros parados nos dois lados na rua - o que

impede que o caminhão continue; ruas que são percorridas duas vezes durante a coleta e

ruas sem saídas.

4.2. Coleta dos dados

Sabendo-se que rota percorrida e os pontos de parada para a coleta seletiva era feita de

forma memorizada, pelo condutor do caminhão, houve a necessidade de mapeá-la. Na

Figura 2 pode ser observado o mapa do Condomínio com a rota – e os pontos de coleta –

que foi identificada durante o mapeamento realizado.

Considerou-se como ponto de partida a guarita do Condomínio, sendo que o

trajeto total foi realizado em 1h40min, foi percorrida uma distância de 9 km e, por fim,

parou-se em 70 pontos para coletar o lixo reciclável. Observando esse percurso, nota-se

que o mesmo está sujeito a modificações, ou seja, em diversas vezes o condutor passou

pelo mesmo caminho não se importando com a distância para se chegar de um ponto a

outro.




Figura 2 – Mapa original do Condomínio com os pontos de coleta/rota percorrida.

Todos os pontos de parada foram indicados no mapa (Figura 2), assim como a

direção tomada a partir de cada ponto continuar o caminho. Essa união de direções

compõe o percurso feito pelo condutor do caminhão. As distâncias entre cada ponto de

parada foram definidas pelo próprio mapa do Condomínio, pois a informação de

dimensão de cada lote é conhecida. Além disso, a localização dos pontos de coleta

permitiu estabelecer as possíveis ligações entre eles, ou seja, se existe a viabilidade de sair

do Ponto A e ir até o Ponto B e vice-versa.

Esse tipo de definição faz parte dos critérios usados para a modelagem do

problema, o que é discutido na seqüência.

4.3. Modelagem do problema com uso de grafo

Segundo Rocha (2005) “grafo é uma estrutura matemática usada para representar as

relações entre as coisas”. O autor detalha em vários exemplos as representações de um

grafo, como cidades que se interligam entre si pelas estradas – as cidades são os nós ou

vértices e as estradas as arestas ou arcos; distribuição de água pluvial, desenho da

hierarquia de uma empresa, entre outros. Outro exemplo simples e de fácil entendimento

da representação de um grafo ocorre ao considerar uma rede de relacionamentos pela

internet, como o Orkut, na qual as pessoas se conectam e encontram caminhos para

chegar a outros amigos. Neste caso as pessoas são os nós e as arestas são as conexões entre

as redes de relacionamentos.

Em resumo, pode-se considerar um grafo como uma forma visual que modela

situações que permitem sua representação por dois elementos básicos: vértices e arestas.




Os vértices podem ser considerados objetos e as arestas o tipo de relacionamento que

ocorre entre os vértices (objetos).

A idéia de conexão entre pontos, mostra-se adequada para o problema abordado

neste estudo, pois foram identificados os pontos de parada para coleta de lixo e a

necessidade de sair de um desses pontos e se chegar a outro por um caminho válido.

Dessa forma, infere-se que os pontos de coleta são os nós e o caminho entre dois nós é

uma aresta.

A guarita, como já explicado, é o portão de entrada e saída do Condomínio e,

para fins de modelagem foi definida como nó Raiz do grafo a ser modelado. Desse nó

Raiz, pode-se atingir outros nós (pontos de coleta) por meio das arestas que os

interconectam e tem-se por norma que o percurso deve iniciar e terminar no nó Raiz.

O problema estudado apresenta uma característica importante e que não pode

ser desconsiderada no processo de modelagem: à distância para ir do Ponto A até o Ponto

B pode ou não ser igual a sair do Ponto B e ir ao Ponto A. Isto é, a distância entre dois

pontos de coletas pode ter caminhos distintos para sair de um e chegar ao outro. Isso

ocorre principalmente entre os nós que estão distribuídos pela avenida principal do

Condomínio, pois por possuir uma pista de rolagem num sentido e outra no sentido

contrário, separadas por um canteiro, faz com que o acesso entre dois pontos, nos dois

sentidos possíveis, seja distinto.

Para facilitar o processo de modelagem, foram estabelecidos os critérios a seguir

para a construção do grafo que representa o problema estudado.

A guarita é o nó Raiz do grafo e todo percurso inicia e se encerra nesse nó.

Um vértice ou nó é uma representação do ponto de parada para coleta de lixo.

Uma aresta é uma ligação válida entre dois nós, de forma que o acesso entre

ambos tenha a mesma distância – vale para a ida e para a volta.

Um arco é uma ligação direcionada entre dois nós: vale apenas para conectar o

nó A com o B – nesse sentido, e indica a distância para essa conexão.

Partir-se-á de um nó A para um nó B, preferencialmente, se B estiver na mesma

rua de A; ou se B estiver numa rua perpendicular a de A sendo o primeiro nó acessado

dessa rua quando se parte de A.

Em alguns casos a definição das arestas entre os nós foi feita com base na

coerência do percurso ao visualizar o mapa real, pois se isso não fosse feito, o modelo

poderia ficar muito restritivo – exigindo muitas análises e alterações no modelo.




No Quadro 2 estão apresentados os símbolos usados na modelagem do grafo e

suas definições.

Na Figura 3(a), apresenta-se o primeiro grafo resultante da modelagem realizada.

No entanto, no momento da validação do modelo foi necessário rever algumas conexões

entre nós para viabilizar uma solução para o problema. Desta forma, a Figura 3(b)

apresenta o modelo final utilizado para o problema. Pode ser observadas alterações

realizadas em conexões partindo do nó 8 e conexões entre os nós 2 e 3. É importante

observar que existem nós com maior número de conexões que outros. Na verdade serão

esses os nós mais representativos quando se estiver buscando uma rota mais adequada

(que passe por todos os nós e que tenha um percurso total menor que o originalmente

efetuado pelo condutor do caminhão), pois possibilitarão vários caminhos distintos.

Quadro 2 – Símbolos usados na modelagem do problema e seus significados.

Símbolo Definição

Representação do nó Raiz do grafo.

Representação dos vértices/nós que são os pontos de parada para coleta do lixo seletivo.

Identificação dos pontos de parada - nomeados de 1 a 70.

Representação de aresta que é a distância (medida em metros) para sair do vértice A e ir até o vértice B e vice-versa.

Representação usada para arco sendo que a cor preta define que existe percurso válido apenas do vértice A para o B – neste caso o inverso não é possível.

Representação usada para arco sendo que a cor azul define que existe um percurso válido do vértice A para o B e outro de B para A – sendo que cada percurso tem uma distância distinta.

Na Figura 4 são mostradas as distâncias (em metros) entre cada conexão

representada na Figura 3. Um fator importante a ser observado é que há nós que só

possuem conexão numa direção, por exemplo, do Ponto 3 para o Ponto 4. Logo, na matriz

de distâncias (Figura 4) pode ser verificado que essa conexão tem valor 20 (olhando-se a

intersecção da linha 3 com a coluna 4).

Outra informação importante sobre a construção da matriz de distância

apresentada é que a linha e coluna 0 se referem ao nó Raiz (guarita) do grafo modelado, o

mesmo para os demais nós de 1 a 70. Para encontrar a distância do caminho que liga o nó

1 ao nó 2, deve-se olhar na linha 1 com a coluna 2 e ver o valor da intersecção (25 metros).

Ou seja, sempre o ponto de partida é considerado o ponto correspondente na linha da

1




matriz e o ponto de chegada na coluna. Para esse mesmo caso citado, vale observar que o

valor do nó 2 ao nó 1 é diferente (15 metros) o que também é indicado no grafo pelos

arcos em azul (Figura 3 a, b).

10

1 2

3

4

5

6

7

8 9 11

12

13

14

15

16

18

19

17

20

37 38

45

44

33

36 35 34

70 68 69 67 49

48

39

40

41

42

43 47

46

50 51

66

59

52 53

54

55

56

57 58

65

64

63 62 61 60

32

31

30

21

22 23 24

25 26 27 28

29

Nó Raiz

Figura 3(a) – Mapa do Condomínio com a primeira modelagem em grafo para o problema.

Figura 3(b) – Mapa do Condomínio com a modelagem definitiva para o problema.

nós 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70

0 0 40 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 130 0 0 0 0 0 0 0 150 160 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 0 0 25 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 02 40 15 0 70 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 150 0 0 0 0 0 0 0 190 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 03 0 0 280 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 04 0 0 0 0 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 05 0 0 0 0 0 0 80 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 110 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 06 0 0 0 0 0 0 0 190 0 80 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 180 210 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 07 0 0 0 0 0 0 0 0 40 90 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 50 60 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 08 0 0 280 0 0 0 120 0 0 30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 170 130 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 09 0 0 0 0 0 0 0 195 0 0 60 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 100 0 0 0 125 195 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

10 0 0 0 0 0 0 0 0 0 60 0 70 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 011 0 0 0 0 0 0 0 0 0 0 70 0 60 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 70 140 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 012 0 0 0 0 0 0 0 0 0 0 0 60 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 150 150 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 013 0 0 0 0 0 0 0 0 0 0 0 0 20 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 014 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 015 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 016 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 017 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 018 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 019 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 020 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 50 20 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 021 130 175 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 50 0 25 0 0 0 0 0 0 100 60 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 022 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 25 25 0 60 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 023 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 25 0 60 0 120 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 024 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 120 0 60 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 025 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 60 0 40 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 026 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 40 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 027 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 028 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 029 150 170 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 100 0 0 0 0 0 0 50 0 100 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 030 160 180 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 60 0 0 0 0 0 0 0 100 0 80 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 031 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 80 0 100 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 032 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 100 0 40 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 033 0 0 0 0 0 0 0 0 0 100 30 70 150 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 40 0 220 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 034 0 0 0 0 0 0 0 0 0 0 0 140 150 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 220 0 60 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 24035 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 60 0 40 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18036 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 40 0 60 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13037 0 0 0 0 0 0 0 40 0 175 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 60 0 60 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 22038 0 0 0 0 0 0 0 70 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 60 0 50 0 0 0 0 0 0 0 0 210 220 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 039 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 50 0 20 0 0 0 0 0 0 0 140 180 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 040 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 041 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 042 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 043 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 044 0 0 220 0 0 0 140 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 40 40 180 0 0 190 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 045 0 0 170 0 0 0 110 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 40 0 80 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 046 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 40 80 0 100 0 0 120 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 047 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 180 0 100 0 60 0 150 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 190 0 0 0 048 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 210 140 0 0 0 0 0 0 0 60 0 140 200 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 175 210 0 0 049 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 220 180 0 0 0 0 0 0 0 0 140 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 315 80 0 0 050 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 190 0 120 150 200 0 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 051 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 40 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 052 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 40 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 053 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 60 40 0 0 0 0 0 0 0 0 0 0 0 0 0 0 054 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 60 0 80 0 0 0 0 0 0 0 0 0 0 0 0 0 0 055 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 40 80 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 056 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 40 0 0 0 0 0 0 0 0 0 0 0 0 057 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 40 0 70 0 0 0 0 0 0 60 0 0 0 0 058 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 70 0 240 0 0 0 0 0 150 160 0 0 0 059 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 240 0 20 0 0 0 0 0 100 0 0 0 060 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 20 0 0 0 0 0 0 0 0 061 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 20 0 0 0 0 0 0 0 062 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 20 0 0 0 0 0 0 063 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 80 0 0 0 0 0 064 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 80 0 60 0 0 0 0 065 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 60 150 0 0 0 0 0 60 0 0 0 0 0 066 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 190 175 315 0 0 0 0 0 0 0 0 160 100 0 0 0 0 0 0 0 0 0 0 067 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 210 80 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 40 0 068 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 40 0 60 069 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 60 0 14070 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 240 180 130 220 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 140 0

Figura 4 – Tabela ou Matriz de Distâncias entre os Vértices – dados em metros.

Distância entre os 10 primeiros nós – pontos de coleta.

nós 0 1 2 3 4 5 6 7 8 9 100 0 40 0 0 0 0 0 0 0 0 01 0 0 25 20 0 0 0 0 0 0 02 40 15 0 70 0 0 0 0 0 0 03 0 0 280 0 20 0 0 0 0 0 04 0 0 0 0 0 20 0 0 0 0 05 0 0 0 0 0 0 80 0 0 0 06 0 0 0 0 0 0 0 190 0 80 07 0 0 0 0 0 0 0 0 40 90 08 0 0 280 0 0 0 120 0 0 30 09 0 0 0 0 0 0 0 195 0 0 60

10 0 0 0 0 0 0 0 0 0 60 0




4.4. Simulação Computacional do Modelo Proposto

Concluída a etapa de modelagem em grafos, inicia-se a fase da simulação computacional –

aplicação de testes com os dados coletados. Nesta fase a validação da modelagem seria

efetivada com o auxílio de um programa computacional gentilmente cedido por Coelho

(2002), que resolve via métodos heurísticos o Problema do Caixeiro Viajante (PCV), sendo

um dos mais conhecidos e tradicionais problemas de programação matemática. E é nesse

problema que o problema de percurso tratado nesse trabalho se encaixa, conforme foi

adiantado na seção metodologia.

O PCV consiste em determinar rotas sobre pontos que podem ser representados

por cidades, pontos de trabalhos ou atendimentos, armazéns ou depósitos,

seqüenciamento de atividades, programação de produção entre outros.

Sua denominação faz referência a um tradicional caixeiro viajante que visita seus

clientes em determinadas cidades. Se desejar seguir viagem para uma cidade (um ponto

de parada, ou seja, nó ou vértice de um grafo), passando uma única vez em cada cidade e

retornando ao ponto de partida ao final; devem-se possuir os valores necessários para

calcular os custos da viagem completa. Isso pode significar, por exemplo, possuir o valor

da distância entre as cidades a serem visitadas. O PCV não possui um método que

encontre a melhor de todas as soluções para o problema - solução ótima. É possível

conhecer essa solução ótima se for realizada uma busca exaustiva, o que não é

aconselhável pelo aspecto exponencial que esse problema apresenta. Por exemplo, um

grafo completo com 5 nós possui 120 rotas possíveis, ao aumentar apenas um nó, 6 nós,

existirão 720 rotas possíveis, para 7 nós serão 5040 possibilidades e assim sucessivamente.

Por esse motivo são mais usados métodos heurísticos para resolver essa classe de

problemas que, no contexto de uma pesquisa, fornecem novos conhecimentos e novas

descobertas, pois se trata de um método de aproximação da solução dos problemas.

Seguem direcionamentos claros, que são baseados em alguma fundamentação lógica e/ou

circunstancial para buscar novas alternativas de solução.

Dentre as muitas pesquisas voltadas ao desenvolvimento de heurísticas que

resolvem o PCV - disponíveis na literatura especializada, pode-se destacar: Heurística do

Vizinho mais Próximo e Heurística de Inserção de Vizinho mais Próximo/Distante. O

método heurístico do Vizinho mais Próximo se inicia partindo de uma cidade k qualquer.

Neste ponto ocorre um ciclo até o final da busca, pois o método escolherá a cidade mais

próxima de k, ainda não visitada. A nova cidade é colocada no percurso visitado,

nomeada de k e a busca será repetida, sucessivamente, até que todas as cidades sejam

incluídas na rota. A Heurística de Inserção do Vizinho mais Próximo é iniciada com um




ciclo inicial de três nós aleatórios. Em seguida o algoritmo escolhe o próximo nó mais

próximo do ciclo e identifica o par de nós mais vantajoso para fazer sua inserção. Esse

processo é repetido enquanto existirem nós disponíveis a serem inseridos no

ciclo/percurso.

Eram exatamente essas duas heurísticas que seriam usadas para validar o

modelo proposto nesse trabalho. Mas, o modelo foi idealizado para a situação específica

da cooperativa e o grafo, como pode ser observado na Figura 3(b), não é completo – com

conexões entre todos os nós. Por isso, não foi possível usar o software cedido para esse fim.

Esse problema foi contornado ao desenvolver uma heurística construtiva

específica para a modelagem estabelecida.

O algoritmo criado é bem simples e usa idéias das heurísticas descritas

anteriormente, sendo apresentado resumidamente no Quadro 3.

Quadro 3 – Sequência dos passos do algoritmo.

Passo 1: Escolher (usuário) três nós que formem um ciclo inicial.

Passo 2: Escolher (usuário) um par de nós do ciclo.

Passo 3: Escolher (usuário) pelo método apresentado no Passo 4 ou no Passo 5.

Passo 4: Inserir o nó candidato mais próximo do nó inicial do par indicado.

Se o nó escolhido não tiver conexão com o nó final do par, então fazer esse nó ser origem e voltar a 1 do Passo 4.

Se não for encontrado um nó candidato que feche o ciclo com o nó final do par, retornar que não houve sucesso.

Voltar ao Passo 2 ou finalizar a busca.

Passo 5: Buscar entre todos os nós candidatos que tenham conexão com o nó inicial do par indicado, aquele que tem menor custo de inserção entre o par.

Se não for encontrado um nó candidato, retornar que não houve sucesso.

Voltar ao Passo 2 ou finalizar a busca.

Como pode ser observado, a heurística proposta é guiada pelo usuário que define

em quais pontos, nós, prefere que a busca seja intensificada. Isso foi fundamental para

viabilizar em pouco tempo uma solução para o problema, pois um método mais eficiente

pode ser desenvolvido, mas o tempo de estudo será significativo, sendo que não era esse o

foco da pesquisa.

5. RESULTADOS

Esta pesquisa foi realizada por ter sido identificada a oportunidade de aplicar os conceitos

de logística e PO para melhorar processos da cooperativa considerada neste estudo. Entre

as várias possibilidades de ações de melhoria, buscou-se estudar a rota efetuada no




Condomínio com o objetivo de apresentar aos cooperados esses conceitos e ferramentas

que poderão ser muito úteis para o desempenho da cooperativa.

A modelagem do problema real foi feita levando-se em consideração as

informações mais significativas do problema que são:

• o local dos pontos de coleta do lixo seletivo;

• a rota percorrida pelo condutor do caminhão;

• as conexões possíveis entre cada ponto de coleta;

• o sentido permitido nas ruas do Condomínio;

• a distância entre cada ponto de coleta.

Mais uma vez, destaca-se que a identificação dos pontos de coleta foi feita pelo

acompanhamento in loco de uma coleta do lixo seletivo no Condomínio, para isso a

pesquisadora participou do processo completo de coleta: acompanhou o motorista do

caminhão, anotou os pontos de parada, a rota percorrida, a distância total e o tempo gasto

para isso. Essa ação foi fundamental para obter as informações básicas que possibilitassem

a modelagem do problema, uma vez que a cooperativa não dispunha desses dados.

Embora exista uma rota já definida pelo condutor, percebe-se que ela não é

eficiente por passar em alguns lugares mais de uma vez. Mesmo assim, usou-se a rota

original, cujo percurso é de 9 km, como referência na identificação das possíveis conexões

entre os pontos de parada (nós do grafo).

Como já mencionado, o problema descrito é conhecido na literatura clássica de

PO como Problema do Caixeiro Viajante e, sabe-se, que é difícil de ser resolvido. Mas, o

intuito dessa pesquisa não é buscar a melhor solução que existe para o problema e, sim,

melhorar a solução que a cooperativa adota, mostrando a enorme vantagem de aliar o uso

das ferramentas e conceitos de PO na logística. Mesmo assim os resultados

computacionais foram surpreendentes, pois houve uma melhoria de 50% na distância

total do percurso final, ou seja, um percurso de 4545m ou 4,5 km (Figura 5).




10

1 2

3

4

5

6

7

8 9 11

12

13

14

15

16

18

19

17

20

37 38

45

44

33

36 35 34

70 68 69 67 49

48

39

40

41

42

43 47

46

50 51

66

59

52 53

54

55

56

57 58

65

64

63 62 61 60

32

31

30

21

22 23 24

25 26 27 28

29 Nó Raiz

Figura 5 – Solução encontrada para o problema com a heurística desenvolvida – percurso de 4,5 km.

Com do desenvolvimento desta pesquisa, observou-se que na organização

estudada: Cooperativa Recupera de Lixo Reciclado, é visível a necessidade de

implantação de um planejamento correto do percurso (rota) dentro do Condomínio, pois a

rota atual percorrida é feita com base no tempo, não havendo a preocupação referente à

distância percorrida. Em alguns pontos a distância é percorrida em marcha ré, ou seja,

passando por uma rua e retornando o percurso de ré, dificultando a visualização do

motorista, aumentando o tempo, devido a velocidade bem reduzida, e a possibilidade de

causar de acidentes com pedestres.

O resultado obtido mostra como um planejamento mais cuidadoso é importante

para uma empresa em diversos aspectos, principalmente em produtividade e gestão

financeira. Além disso, a possibilidade de trazer para a realidade das empresas técnicas

mais difundidas no meio acadêmico, disseminando boas práticas, é estimulante e

recompensador, pois mostra a importância da pesquisa para o crescimento da sociedade.

6. CONSIDERAÇÕES FINAIS

O estudo realizado e apresentado nesse artigo mostrou como é possível visualizar um

problema real quando se usa alguma técnica de modelagem. O emprego de grafos foi

natural, principalmente por se tratar de uma ferramenta gráfica que permite uma fácil

compreensão na transição que houve do problema real para o modelo desenvolvido.




Uma das contribuições desse trabalho é um material que poderá auxiliar outros

alunos pesquisadores a entender como ocorre o processo de modelagem, quais são os

principais passos a serem seguidos nesse tipo de tarefa, como usar ferramentas

computacionais adequadas ao problema para validar o modelo proposto.

Este trabalho atingiu seus objetivos e foi além: mostrar como aliar ferramentas de

PO com logística e encontrar um rota melhor que a executada pela cooperativa – essa

última com uma diminuição no percurso de 50%. Com essa melhoria a empresa poderá

optar por fazer mais de duas coletas no período da manhã e, conseqüentemente, poderá

aumentar o número de coletas no período da tarde. Desta forma, a produção e o lucro

também poderão aumentar, ou seja, quanto maior o volume de lixo coletado, maior a

recompensa financeira a ser distribuída entre os colaboradores.

Existem muitas alternativas para a continuidade deste trabalho, sendo uma das

possibilidades a construção do grafo completo que representa o problema e o teste das

heurísticas padrão para o PCV. Outra é obter a rota realizada pela empresa que coleta lixo

orgânico e verificar se os pontos de parada são os mesmos. Se forem, será possível fazer a

comparação entre os percursos, além de estudar quais são os melhores pontos de coleta de

lixo seletivo/orgânico a serem estabelecidos e/ou remodelados no Condomínio.

REFERÊNCIAS

BRASIL, Luciana de Fáveri, Uma contribuição para a compreensão do emprego da Pesquisa Operacional em problemas reais, Universidade Estadual do Centro-Oeste - Unicentro Departamento de Matemática, 1993. 34 p. Trabalho de Conclusão de Curso.

CEZAR, Douglas Fujita de Oliveira, Otimização de espaço em container. Valinhos: Faculdades de Valinhos/Departamento de Ciências Administrativas, 2003. 35 p. Trabalho de Conclusão de Curso.

COELHO, Pedro Aparecido (et all). Problema do Caixeiro Viajante – Heurísticas. Trabalho apresentado na Disciplina de Programação Sistemática e Algoritmos do Curso de Ciência da Computação – 2ª série, 2002, Faculdade Anhanguera de Valinhos.

LUNA, Henrique Pacca; GOLDBARG, Marco César. Otimização Combinatória e Programação Linear, modelos e algoritmos. Rio de Janeiro: Elsevier, 2005.

MAITELLI, A. L.; SILVA, G. A. Um Ambiente Computacional para Modelagem Simbólica de Sistemas Físicos Lineares Utilizando Grafos. Revista Brasileira de Informática na Educação, v.12, n. 1, 2004. Disponível em: <http://bibliotecadigital.sbc.org.br/download.php?paper=609>. Acesso em: 03 set. 2009.

MISTRO, Diomar Cristina. O problema da poluição em rios por mercúrio metálico: modelagem e simulação numérica. 1992. Dissertação (Mestrado) – Universidade Estadual de Campinas, UNICAMP, Campinas. Disponível em <http://libdigi.unicamp.br/document/?code=000042243>. Acesso em: 01 set. 2009.

RANGEL, Socorro. Modelagens de problemas de otimização. XIII Semana da Matemática. Disponível em: <http://www.dcce.ibilce.unesp.br/~socorro/XIIISEMAT/.../model.ppt >. Acesso em: 05 set. 2009.




ROCHA, Daniel Amaral de Medeiros. Introdução a Teoria dos Grafos. Curso preparatório para a Maratona de Programação 2005, Sociedade Brasileira de Computação (SBC). Disponível em: <http://danielamaral.wikidot.com/introducao-a-teoria-dos-grafos>. Acesso em: 05 set. 2009.

SILVEIRA et al., Pesquisa operacional no ensino da logística. Disponível em: <http://www.inpeau.ufsc.br/>. Acesso em: 10 abr. 2009.

TADEU , Hugo Ferreira Braga. Logística Empresarial. Belo Horizonte: Fundac-BH, 2008.



Documents

APLICAÇÃO DE PESQUISA OPERACIONAL EM LOGÍSTICA: COMO