Definição de Um Modelo de Roteirização de Veiculos Para a Empresa Fitolog

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL

ESCOLA DE ADMINISTRAO

DEPARTAMENTO DE CINCIAS ADMINISTRATIVAS

JEFERSON MACHADO SANTOS

DEFINIO DE UM MODELO DE ROTEIRIZAO DE VECULOS

PARA A EMPRESA FITOLOG

Porto Alegre

2012

JEFERSON MACHADO SANTOS



Trabalho de concluso do curso de

graduao apresentado ao Departamento

de Cincias Administrativas da

Universidade Federal do Rio Grande do

Sul, como requisito parcial para a

obteno do grau de Bacharel em

Administrao

Orientador: Prof. Denis Borenstein

Porto Alegre

2012

Jeferson Machado Santos



Trabalho de concluso do curso de

graduao apresentado ao Departamento

de Cincias Administrativas da

Universidade Federal do Rio Grande do

Sul, como requisito parcial para a

obteno do grau de Bacharel em

Administrao

Conceito Final:

Aprovado em ...... de ............................... de ..........

BANCA EXAMINADORA

________________________________________________

Prof. Dr. ................................................................. UFRGS

________________________________________________

Prof. Dr. ................................................................. UFRGS

________________________________________________

Orientador Prof. Dr. Denis Borenstein UFRGS

AGRADECIMENTOS

Agradeo aos meus familiares e amigos que me acompanharam durante

todo o perodo de graduao, dando o suporte necessrio e motivao para

seguir em frente em todos os momentos.

Agradeo a todos os colegas com quem tive contato em minhas

experincias profissionais at o momento por contriburem e complementarem

minha formao acadmica e profissional.

Agradeo a todos os professores com quem tive oportunidade de

aprender durante este perodo de graduao e que com certeza deram uma

grande contribuio para os desafios que sero enfrentados nas prximas

etapas.

RESUMO

O transporte possui um alto impacto no desenvolvimento de uma nao e na

capacidade competitiva das empresas. Alm disso, a maior parte dos custos

logsticos das empresas se refere aos transportes e s decises quanto

roteirizao de veculos possuem um alto impacto sobre esse custo e sobre o

nvel de servio oferecido pela empresa. Dessa forma, a partir de uma anlise

da operao da Fitolog foi possvel identificar as principais variveis relevantes

no que diz repeito as suas operaes de transporte e definir um modelo de

roteirizao de veculos para a mesma a partir do problema de roteirizao de

veculos com janelas de tempo. Aps a definio do modelo, foi identificado o

melhor mtodo de soluo do modelo, atravs da comparao dos resultados

das heursticas de Clark e Wright e de Mole e Jameson.

Palavras chave: Transporte. Programao linear. Problema de roteirizao

de veculos. Problema de roteirizao de veculos com janelas de tempo

LISTA DE ILUSTRAES

Figura 1 Exemplo de janela de tempo de um cliente .......................................................... 23

Figura 2 O procedimento de economia ................................................................................ 24

Figura 3 Exemplo de aplicao da heurstica de Clark e Wright ....................................... 25

Figura 4 Lista de economias ................................................................................................. 25

Figura 5 Lista de proximidades da rota 0-5-0 ...................................................................... 28

Figura 6 Lista de proximidades da rota 0-3-0 ...................................................................... 29

Figura 7 Lista de economias da rota 0-4-3-0 ....................................................................... 29

Figura 8 Exemplo de aplicao da heurstica Mole e Jameson ........................................ 30

Figura 9 Lista de fatores relevantes para o modelo de roteirizao da Fitolog .............. 32

Figura 10 Primeira parte do algoritmo da heurstica de Clark e Wright ........................... 36

Figura 11 Segunda parte do algoritmo da heurstica de Clark e Wright .......................... 37

Figura 12 Primeira parte do algoritmo da heurstica de Mole e Jameson ........................ 38

Figura 13 Segunda parte do algoritmo da heurstica de Mole e Jameson ....................... 39

Figura 14 Ferramenta de roteirizao (insero de dados) ............................................... 40

Figura 15 Ferramenta de roteirizao (parametrizaes) .................................................. 40

Figura 16 Ferramenta de roteirizao (resultados) ............................................................ 41

Figura 17 Viso geral dos testes comparativos .................................................................. 42

Figura 18 Anlise dos testes comparativos (quantidade de rotas) .................................. 43

Figura 19 Anlise dos testes comparativos (pontos no roteirizados) ............................ 44

Figura 20 Anlise dos testes comparativos (custo total) .................................................. 45

Figura 21 Anlise dos testes comparativos (custo total e pontos no roteirizados) ..... 47

LISTA DE ABREVIATURAS E SIGLAS

GCS Gesto da Cadeia de Suprimentos

PPL Problema de Programao Linear

PPLI Problema de Programao Linear Inteira

PRV Problema de Roteirizao de Veculos

PRVJT Problema de Roteirizao de Veculos com Janelas de Tempo

LISTA DE SMBOLOS

tempo entre o trmino do servio no cliente e incio no cliente

tempo faltante at o ltimo momento possvel para iniciar o servio no

cliente

SUMRIO

INTRODUO ................................................................................................... 9

1. ORGANIZAO E AMBIENTE ............................................................. 11

2. DEFINIO DO PROBLEMA ............................................................... 13

3. JUSTIFICATIVA .................................................................................... 15

4. OBJETIVOS .......................................................................................... 16

4.1. OBJETIVO GERAL ................................................................................ 16

4.2. OBJETIVOS ESPECFICOS .................................................................. 16

5. FUNDAMENTAO TERICA ............................................................ 17

5.1. PROGRAMAO LINEAR .................................................................... 17

5.2. PROGRAMAO LINEAR INTEIRA ..................................................... 19

5.3. PROBLEMA DE ROTEIRIZAO DE VECULOS ................................ 20

5.4. PROBLEMA DE ROTEIRIZAO DE VECULOS COM JANELAS DE

TEMPO .................................................................................................. 21

5.5. ABORDAGENS DE SOLUO ............................................................. 23

5.5.1. Algoritmo de Clark e Wright ............................................................... 24

5.5.2. Heurstica do vizinho mais prximo orientada ao tempo ................. 26

5.5.3. Heurstica de Mole e Jameson ............................................................ 27

6. PROCEDIMENTOS METODOLGICOS .............................................. 31

6.1. IDENTIFICAO DAS VARIVEIS RELEVANTES .............................. 31

6.2. FORMULAO DA FUNO-OBJETIVO E DAS RESTRIES ......... 32

6.3. ESCOLHA DO MTODO MATEMTICO DE SOLUO ..................... 35

7. RESULTADOS DO ESTUDO ................................................................ 36

7.1. PROGRAMAO COMPUTACIONAL .................................................. 36

7.2. ANLISE COMPARATIVA ENTRE AS HEURSTICAS ......................... 41

8. CONSIDERAES FINAIS .................................................................. 48

REFERNCIAS ................................................................................................ 50

9

INTRODUO

O transporte a forma que permite s empresas que seus produtos e

servios cheguem at os canais em que estaro disponveis para seus clientes.

Como contribuio para o desenvolvimento da nao, o sistema de transportes

permite uma maior concorrncia entre as empresas e uma reduo nos preos

dos produtos (BALLOU, 2006). Alm disso, os custos de transporte

representam, em mdia, 60% dos custos logsticos de uma empresa

(BOWERSOX; COOPER; CLOSS, 2006). Esse impacto dos transportes numa

empresa representado principalmente pelas decises sobre o roteamento de

veculos da mesma, uma vez que tais decises podem trazer economias tanto

em termos de custo quanto de tempo de transporte. Em qualquer ramo em que

a atividade de transporte estiver presente, a roteirizao de veculos pode

trazer uma melhoria no sistema de distribuio de produtos e servios e um

aumento na satisfao dos clientes.

Atualmente, a empresa Fitolog, que atua no ramo de tratamento

fitossanitrio de embalagens para exportao, no possui um modelo definido

para roteirizao dos veculos que realizam seus servios. Dessa forma, este

trabalho realiza uma anlise do ambiente da empresa Fitolog no que tange ao

tema de transporte e define um modelo de roteirizao de veculos adequado

para esta realidade. Alm disso, tambm desenvolvida uma ferramenta que

permite a implementao deste modelo.

O trabalho se divide em oito captulos. O primeiro captulo dedicado

apresentao da empresa e do estgio em se encontra quanto roteirizao

de veculos. Os captulos 2, 3 e 4 so dedicados contextualizao do

problema em estudo e definio dos objetivos deste trabalho. O captulo 5 tem

o objetivo de apresentar alguns conceitos tericos sobre programao linear,

problema de roteirizao de veculos e problema de roteirizao de veculos

com janelas de tempo, que permitiram a construo do modelo de roteirizao

adequado realidade da Fitolog. Nos captulos 6 e 7 so apresentados os

procedimentos realizados para definio do modelo de roteirizao, bem como

a ferramenta desenvolvida e as anlises realizadas para que se atingisse o

10

objetivo do trabalho. Por fim, as concluses do trabalho so expostas no

captulo 8.

11

1. ORGANIZAO E AMBIENTE

A Fitolog atua no ramo de controle de pragas e tem como sua atividade

principal o tratamento fitossanitrio de embalagens de madeira para

exportao. Fundada em 2008, est situada em Porto Alegre e atua na regio

metropolitana desta cidade e em alguns outros municpios do Rio Grande do

Sul.

Atualmente, a empresa conta com 14 colaboradores. Atuando na diviso

fitossanitria, h 3 operadores que realizam os tratamentos fitossanitrios com

as unidades mveis. Os demais colaboradores esto distribudos nas reas

administrativas e de backoffice e nas outras divises da empresa. Alm disso,

a empresa possui trs veculos equipados com a estrutura necessria para

realizar os tratamentos fitossanitrios.

Quanto participao de mercado, conforme dados de 2011 da prpria

empresa, a Fitolog possui cerca de 40% do Market share em termo do nmero

de clientes. Atualmente, a diviso de tratamentos fitossanitrios possui cerca

de 75 clientes ativos.

O tratamento fitossanitrio em embalagens de madeira uma exigncia

legal para o exportador. Assim, todo pallet ou caixa de madeira a ser exportado

deve passar pelo tratamento atravs da modalidade de Brometo de Metila ou

Tratamento Trmico. O tratamento atravs do agrotxico Brometo de Metila

apresenta restries ambientais e riscos sade, devido ao nvel de toxidade

do gs. No Brasil, a utilizao do Brometo de Metila nos tratamentos

fitossanitrios ser proibida aps o ano de 2015. Alm disso, em diversos

pases as embalagens tratadas com Brometo de Metila so mal vistas e alguns

importadores j estabeleceram restries a elas. O Tratamento Trmico no

utiliza produtos txicos e menos nocivo ao meio ambiente. Este procedimento

realizado atravs da elevao da temperatura da madeira at um

determinado nvel e manuteno da mesma por 30 minutos. A dificuldade

original deste tipo de tratamento sua imobilidade, uma vez que as estufas

utilizadas normalmente so grandes e estticas. Identificando uma

oportunidade neste segmento, a empresa em estudo desenvolveu o Processo

de Cmara Porttil, permitindo que unidades mveis se dirijam at o local em

12

que as embalagens do cliente se encontram, reduzindo custos de

deslocamento das embalagens at uma estrutura fixa e reduzindo tempo de

operao.

13

2. DEFINIO DO PROBLEMA

O transporte possui um alto impacto no desempenho logstico de uma

empresa e tambm de uma nao. A evoluo do sistema de transporte

permite a uma economia passar de uma estrutura de produo e consumo em

reas geograficamente prximas, para uma estrutura com concentrao

populacional nos grandes centros, limitando a produo local a menos produtos

e melhorando o padro de vida do cidado (BALLOU, 2006). Conforme Ballou

(2006), um sistema de transporte contribui para intensificar a competitividade,

aumentar as economias de escala e reduzir os preos dos produtos. Alm

disso, os transportes possuem um alto impacto nos custos de uma empresa.

Segundo Bowersox, Cooper e Closs (2006), os custos referentes a transporte

representam cerca de 60% dos custos logsticos de uma empresa.

Nos ltimos tempos, uma srie de fatores vem se somando a estas

questes que j atribuem uma grande importncia s decises a respeito dos

transportes. A concentrao populacional nos grandes centros vem exigindo o

atendimento de um nmero cada vez maior de pontos de demanda e as

agncias reguladoras tem colocado um nmero cada vez maior de restries

quanto circulao de alguns tipos de veculos em determinados horrios e

locais. Alm disso, com o aumento do nvel de concorrncia entre as empresas

e com a disseminao dos conceitos de Gesto da Cadeia de Suprimentos

(GCS), os clientes exigem um nvel de servio cada vez melhor de seus

fornecedores. Dessa forma, a fim de melhorar o desempenho da distribuio de

seus produtos, as empresas esto passando a utilizar modelos e sistemas de

roteirizao e programao de veculos.

A roteirizao de veculos busca determinar roteiros de entregas a

serem realizados pelos veculos, buscando gerar o menor custo possvel e

atender ao nvel de servio esperado pelos clientes (GALHARDI, 2006). Esses

modelos tm o objetivo de simular situaes que ocorrem no cotidiano,

envolvendo diversas possibilidades de rotas, diferentes modelos de veculos,

etc. Os modelos de roteirizao podem ser de rota fixa quando se deseja

apenas distribuir cargas por rotas previamente determinadas ou de rotas

dinmicas, quando sugerida a melhor rota analisando uma srie de fatores,

14

como tipo da carga a ser distribuda, capacidades dos veculos e locais de

entrega (GHISI et al., 2004). Assim, vemos que os roteirizadores so

poderosas ferramentas no auxlio gesto dos transportes, permitindo que se

reduza um dos principais componentes de custo das empresas sem perder o

foco no nvel de servio exigido pelos clientes. Dessa forma, a roteirizao vem

cada vez mais despertando um interesse nas empresas que tem na distribuio

uma parte importante do seu processo de negcio e uma sria de empresas de

tecnologia da informao vem criando softwares roteirizadores que buscam a

z

confiabilidade, velocidade e flexibilidade, eficincia e pontualidade na

(GALHARDI, 2006).

Atualmente, a Fitolog no possui nenhum modelo de roteirizao para

suportar a distribuio de suas unidades mveis para atendimento dos clientes.

A determinao de quais clientes cada veculo atender e quais rotas estes

devem seguir feita empiricamente pelos funcionrios do BackOffice da

organizao. Alm disso, o atual cenrio do mercado de tratamento

fitossanitrio de embalagens para exportao e o desempenho da organizao

vm sinalizando que haver um crescimento da demanda pelo servio e que a

empresa precisar expandir sua estrutura para atender esta demanda.

Dessa forma, a Fitolog exps uma necessidade de possuir uma

ferramenta de suporte para a roteirizao de seus veculos. Essa ferramenta de

gesto auxiliar nas operaes atuais da empresa e tambm dar um suporte

para um crescimento futuro. Assim, este trabalho se prope a construir um

modelo de roteirizao para a organizao descrita e definir a melhor forma de

solucion-lo.

15

3. JUSTIFICATIVA

Atravs desse estudo, espera-se identificar as variveis impactantes nas

decises quanto roteirizao dos veculos da Fitolog e determinar um modelo

de roteirizao de acordo com sua realidade. Esse modelo auxiliar na tomada

de deciso quanto s rotas a serem realizadas pelos veculos para atender s

demandas dirias.

O modelo definido para a empresa poder ser implementado atravs de

ferramentas computacionais. Os colaboradores que hoje tomam as decises

das rotas a serem seguidas pelos veculos sem apoio metodolgico podero

inserir os dados do negcio, como capacidade dos veculos e pontos de

demanda, nessa ferramenta. Com esses dados, o modelo poder ser

executado e sugerir rotas a serem seguidas que minimizem os custos da

operao e atendam demanda dos clientes. Como a tendncia do mercado e

dos resultados da empresa indica um crescimento, esse modelo trar cada vez

mais benefcios para a Fitolog medida que seus negcios se expandirem.

16

4. OBJETIVOS

A partir da problemtica apresentada, foram definidos os seguintes

objetivos para o trabalho:

4.1. OBJETIVO GERAL

Determinar um modelo de roteirizao de veculos para a empresa

Fitolog, bem como a melhor maneira de solucion-lo.

4.2. OBJETIVOS ESPECFICOS

Analisar a realidade operacional da empresa quanto roteirizao

de veculos;

Identificar as variveis envolvidas na roteirizao dos veculos da

empresa;

Determinar a funo objetivo e as restries do modelo de

roteirizao;

Identificar as possveis abordagens de soluo para o modelo

construdo;

Determinar a melhor abordagem de soluo.

17

5. FUNDAMENTAO TERICA

Nesta etapa, busca-se formar uma base conceitual que suporte a

definio de um modelo de roteirizao de veculos para a empresa Fitolog.

Para isso, foram utilizados materiais cientficos confiveis para a

fundamentao terica.

Sero abordados conceitos a respeito de programao linear e

programao linear inteira para embasar a soluo de problemas que

envolvem a alocao de recursos escassos. Aps, sero abordados os

problemas de roteirizao de veculos e problemas de roteirizao de veculos

com janelas de tempo, a fim de focar no problema deste estudo. Por fim, sero

levantadas abordagens de soluo para estes dois ltimos problemas.

5.1. PROGRAMAO LINEAR

O Problema de Programao Linear (PPL) busca encontrar a melhor

distribuio possvel de recursos escassos entre as diversas tarefas que devem

z

j (ANDRADE 2 9, p. 26). Alm disso, esse tipo

de problema pode ser representado por um modelo de otimizao em que

todas as relaes matemticas so lineares (ANDRADE, 2009). Um modelo de

otimizao um modelo matemtico construdo para encontrar uma soluo

nica, que ser considerada tima. Esses modelos so utilizados em situaes

em que as variveis podem assumir diversos valores (ANDRADE, 2009).

Segundo Andrade (2009), os modelos de otimizao so diferentes dos

modelos de simulao pelo fato de buscarem uma nica soluo, enquanto

estes se focam na gerao e anlise de alternativas. Segundo Goldbarg e Luna

(2005), possvel formular de uma forma geral o PPL como se segue:

18

Otimizar

(1)

Sujeito a:

(2)

(3)

(4)

(5)

Em que:

j

j

z

O termo otimizar se refere possibilidade de maximizar ou minimizar a

funo objetivo (GOLDBARG; LUNA 2 5). A

dados a matriz A e os vetores b e c, achar o vetor de variveis contnuas x que

satisfaa o conjunto de restries e que otimize o valor do critrio z

(GOLDBARG; LUNA, 2005, p.26).

Segundo Goldbarg e Luna (2005), as duas principais dificuldades para

encontrar a melhor soluo possvel so como obter solues viveis bsicas e

como evitar o teste de todas as solues viveis bsicas possveis. Assim, o

algoritmo Simplex se apresenta como uma forma de soluo que supera essas

dificuldades e pode ser adaptvel ao clculo computacional (GOLDBARG;

LUNA, 2005). De forma geral, este algoritmo parte de uma soluo vivel do

sistema de equaes que constitui o PPL e, a partir desta soluo inicial,

identifica novas solues melhores ou iguais que a atual (GOLDABRG; LUNA,

2005).

19

5.2. PROGRAMAO LINEAR INTEIRA

O Problema de Programao Linear Inteira (PPLI) diferencia-se do PPL

ma ou mais variveis de deciso so representadas apenas

(LACHTERMACHER 2 9). Um exemplo de problema

que requer programao inteira o caso de uma companhia que precisa

determinar o nmero timo de trabalhadores a serem alocados em cada turno

(RAGSDALE, 2009). O Problema da Mochila representa de forma genrica o

PPLI, uma vez que possui um estreito relacionamento com diversos outros

modelos de programao (GOLDBARG; LUNA, 2005). Basicamente, o

problema trata do desafio de encher uma mochila com diversos itens sem

ultrapassar seu limite de peso, otimizando o valor total dos itens transportados

(GOLDBARG; LUNA, 2005). Segundo Goldbarg e Luna (2005), o Problema da

Mochila pode ser formulado da seguinte forma:

Maximizar

(6)

Sujeito a:

(7)

(8)

Em que representado na restrio (8) como uma varivel binria que

indica se o item foi colocado na mochila caso seu valor for igual a um; seu

valor ser zero caso contrrio. O valor de cada item representado por . O

peso de cada item representado por . A restrio (7) indica que a soma

do peso de todos os itens colocados na mochila no pode ser superior

capacidade total da mochila, representada por .

Conforme Goldbarg e Luna (2005) existem inmeras solues para o

PPLI, as quais podem ser classificadas como tcnicas de enumerao, de

cortes e hbridas. Uma tcnica de enumerao muito utilizada para solucionar

os PPLI o algoritmo Branch-and-Bound, em que so efetuadas parties no

espao das solues, criando novos e restritos problemas, mais fceis de

20

solucionar, para que ento seja realizado o teste de otimalidade entre as

solues encontradas nos problemas restritos (GOLDBARG; LUNA, 2005).

5.3. PROBLEMA DE ROTEIRIZAO DE VECULOS

O Problema de Roteirizao de Veculos (PRV) comumente descrito

como um problema em que veculos localizados em um depsito central devem

visitar clientes geograficamente dispersos a fim de atender suas demandas

(MARINAKIS; MIGDALAS, 2007). Conforme Marinakis e Migdalas (2007), o

PRV foi inicialmente introduzido por Dantzig e Ramser (1959), com o nome de

Problema de Despacho de Caminhes. O Problema de Despacho de

Caminhes caracterizado pelo fato de que a capacidade de cada veculo

inferior soma das quantidades demandadas em cada ponto de entrega

(DANTZIG; RAMSER, 1959). Logo, esse problema caracterizado pela

relao:

(9)

O objetivo deste problema identificar quais rotas entre os pontos de

demanda a serem atendidos minimizam a distncia total a ser percorrida pelos

veculos, sendo que a formulao geral proposta por Dantzig e Ramser (1959)

:

Minimizar

(10)

Sujeito a:

(11)

(12)

(13)

em que definido na equao (13) como uma varivel binria que indica

que o cliente atendido aps o cliente , ou seja, que a rota , utilizada,

21

caso seu valor seja um. Caso esta rota no seja utilizada, seu valor ser zero.

A restrio (11) indica que o total da demanda de todos os pontos

atendidos no pode ser superior capacidade do veculo, representada por .

5.4. PROBLEMA DE ROTEIRIZAO DE VECULOS COM JANELAS DE

TEMPO

O Problema de Roteirizao de Veculos com Janelas de Tempo

(PRVJT) determina que os clientes devem ser atendidos dentro de uma

determinada janela de tempo, ou seja, dentro de um especfico intervalo de

tempo (MARINAKIS; MIGDALAS, 2007). Fischer, Jrsten e Madsen (1997)

propuseram um modelo que busca atender s demandas dos clientes com os

veculos disponveis em um menor custo possvel, sujeito ao fato de que o

momento para iniciar o servio em um cliente deve estar dentro de um

determinado intervalo de tempo, a janela de tempo. Caso o veculo chegue

muito cedo ao cliente, ele dever esperar at que a janela esteja aberta. Segue

o modelo proposto por Fischer, Jrsten e Madsen (1997):

Minimizar

(14)

Sujeito a:

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

22

(26)

(27)

(28)


que o cliente atendido aps o cliente pelo veculo , caso seu valor seja

um; caso seu valor seja zero, o veculo no atender o cliente aps o cliente

. definido na equao (27) como uma varivel binria que indica que o

cliente atendido pelo veculo , caso seu valor seja um; caso seu valor seja

zero, o cliente no ser atendido pelo veculo . O momento para iniciar o

servio no cliente representado pela varivel . O momento de partida do

veculo do depsito determinado pela varivel , enquanto o momento do

retorno do veculo ao depsito determinado pela varivel . A restrio

(15) garante que cada veculo que visitar um ponto deixar aquele ponto em

seguida. A restrio (16) garante que cada rota se origina e termina no

depsito. As restries (17), (18) e (19) garantem a compatibilidade dos

horrios de chegada e execuo do servio nos diversos clientes. A restrio

(20) garante que o momento da chegada e incio do servio em um cliente est

de acordo com a respectiva janela de tempo. As restries (21) e (22)

garantem que os horrios de sada e chegada dos veculos no depsito

respeitam a janela de tempo do depsito. A restrio (23) garante que a

demanda de cada rota est de acordo com a capacidade mxima do veculo

que a atende. As restries (26) e (28) garantem que cada cliente visitado

apenas uma vez e que cada veculo deixa um cliente apenas uma vez,

respectivamente.

O modelo para o PRVJT apresentado um caso em que a janela de

tempo rgida. Segundo Koskosidis (apud Joubert, 2007, p.17), quando

nenhuma entrega permitida fora dos parmetros definidos para a janela,

dizemos que a janela de tempo rgida. Caso sejam permitidas entregas fora

dos parmetros definidos para a janela no cliente , dizemos que a janela de

tempo flexvel e o atraso no cliente ser penalizado a um custo . Alm

disso, o cliente poder determinar um atraso mximo permitido denotado por

(Joubert, 2007). A figura 1 ilustra um caso de um cliente que determina

23

uma janela de tempo para ser atendido das 07h30min s 15h30min. No

entanto, ele permite entregas atrasadas at s 17h:

Figura 1 Exemplo de janela de tempo de um cliente

Fonte: Joubert (2007, p. 17)

Conforme Joubert (2007), o atraso no cliente , denotado por , pode ser

calculado atravs da expresso:

(29)

em que horrio de chegada ao cliente . A expresso denota que o atraso

calculado pela diferena entre o horrio de chegada ao cliente , , e entre

o horrio final da janela de tempo no cliente , , desde que esta diferena seja

maior que zero e que o horrio de chegada seja menor ou igual que o horrio

mximo de entregas atrasadas determinado pelo cliente , . Assim, o

atraso penalizado atravs da introduo de um termo de penalidade funo

objetivo (14) (Joubert, 2007), resultando na equao (30).

Minimizar

(30)

em que o atraso determinado pela equao (29).

5.5. ABORDAGENS DE SOLUO

Nesta etapa sero apresentadas uma srie de heursticas que podem

ser utilizadas para solucionar os PRV. As heursticas foram selecionadas

conforme sua adaptao s variaes do PRV apresentadas nas etapas

anteriores.

24

5.5.1. Algoritmo de Clark e Wright

O algoritmo de Clark e Wright foi um dos primeiros propostos para

solucionar problemas do tipo do PRV, servindo de base para outros algoritmos

mais sofisticados (HEINEN, 2005). Este algoritmo caracterizado como um

procedimento de economia e insero, em que arcos entre os pontos de

demanda de menor custo devem substituir os arcos com maior custo,

melhorando a rota em termos de custo (GOLDBARG; LUNA, 2005).

O conceito bsico deste algoritmo obter as economias transformando

duas rotas em uma s, conforme exemplificado na figura 2 (GOLDBARG;

LUNA, 2005). Na figura 2, apresentado um grafo com trs nodos, em que o

nodo 1 representa o depsito, e os ns representam os clientes a serem

atendidos.

Figura 2 O procedimento de economia

Fonte: Goldbarg e Luna (2005, p. 400)

Assim, o custo total da figura 2 (a) dado por:

(31)

O custo total da figura 2 (b) dado por:

(32)

Combinando as duas rotas obtm-se a seguinte economia :

(33)

25 Quanto maior for o valor da economia , mais atrativo ser visitar os

pontos em uma mesma rota (GOLDBARG; LUNA, 2005).

Esse conceito das economias expandido para um problema com

diversos pontos de demanda a partir de um grafo representando os clientes e o

depsito central, os possveis caminhos e suas distncias (HEINEN, 2005).

Aps, deve-se criar rotas iniciais entre o depsito e cada cliente, em que

quantidade de nodos do grafo, conforme mostra a figura 3 (HEINEN, 2005):

Figura 3 Exemplo de aplicao da heurstica de Clark e Wright

Fonte: Heinen (2005, p. 4)

Em seguida, deve-se calcular as economias conforme a equao (33)

para cada possvel par de 2 nodos e orden-las de forma decrescente

(HEINEN, 2005). Para o problema utilizado como exemplo, as economias

foram calculadas e ordenadas como mostra a figura 4:

Figura 4 Lista de economias


26 Para cada linha desta tabela, deve-se verificar se possvel unir as rotas

que possuem os nodos e em uma mesma rota (HEINEN, 2005). Essas rotas

podero ser combinadas caso ambos os nodos estejam no extremo de rotas

diferentes (HEINEN, 2005). A medida que as rotas so unidas, deve-se realizar

os testes das restries de capacidade dos veculos e de janelas de tempo

(GOLDBARG; LUNA, 2005). No problema utilizado como exemplo, nota-se a

partir da figura 4 que a maior economia se d pela unio dos nodos 1 e 2. Uma

vez que esses nodos esto no extremo de suas rotas, eles podem ser unidos

formando uma nova rota, conforme a figura 3(b). O processo realizado da

mesma forma para os nodos 1 e 3, resultando na configurao conforme a

figura 3(c). Como a prxima linha da tabela envolve os ns 2 e 3, passa-se

para o prximo par, resultando na unio dos nodos 3 e 4, conforme a figura

3(d) (HEINEN, 2005). Nenhuma dessas unies seria efetuada caso o resultado

final violasse algumas das restries de capacidade ou janelas de tempo

(HEINEN, 2005).

5.5.2. Heurstica do vizinho mais prximo orientada ao tempo

Uma adaptao do mtodo das economias proposta por Solomon

(1987), chamada de heurstica do vizinho mais prximo orientada ao tempo.

Neste algoritmo, cada rota iniciada com o cliente mais prximo ao depsito

central que no est inserido em nenhuma rota e, nas iteraes seguintes,

busca-se o cliente mais prximo ao ltimo inserido na rota (SOLOMON, 1987).

A busca realizada entre todos os clientes que possuem viabilidade de serem

inseridos na rota, em termos de janela de tempo, momento de chegada do

veculo ao depsito e restries de capacidade. Sempre que essa busca falhar,

uma nova rota iniciada (SOLOMON, 1987).

A z z x

inserido na rota dada por:

, , (34)

Considerando que o ltimo cliente inserido na rota e qualquer

ponto disponvel que poderia ser visitado em seguida. As constantes definem

27

pesos para qual critrio deve ser priorizado no momento de inserir um cliente

em uma rota. representa a distncia entre os dois clientes, representa a

diferena de tempo entre o trmino do servio no cliente e o incio do servio

no cliente , e o tempo faltante at o ltimo momento possvel para o veculo

iniciar o servio no cliente (SOLOMON, 1987)

5.5.3. Heurstica de Mole e Jameson

Os algoritmos apresentados possuem a deficincia de os nodos internos

no serem candidatos a participar do teste de economia, uma vez que apenas

os nodos no extremo de cada rota podem ser unidos (GOLDBARG; LUNA,

2005). Assim, a heurstica elaborada por Mole e Jameson um algoritmo mais

sofisticado, e traz como um dos principais benefcios a capacidade de atacar

esta deficincia (GOLDBARG; LUNA, 2005). Como principal desvantagem do

algoritmo, destaca-se a maior complexidade computacional (HEINEN, 2005).

Este algoritmo inicia a partir de um grafo que apresenta todos os nodos

e as distncias entre eles, conforme a figura 8(a). O depsito central

representado pelo nodo 0 e os clientes pelos demais nodos (HEINEN, 2005).

Aps, deve-se selecionar um nodo para ser inserido na primeira rota de acordo

com algum critrio. Genericamente, ser utilizado o nodo livre mais prximo ao

depsito (HEINEN, 2005). No exemplo utilizado, o nodo 5 selecionado por ser

o mais prximo do depsito. Em seguida, os nodos passam a ser inseridos nas

rotas de acordo com os critrios de proximidade e economia (HEINEN, 2005).

O critrio de proximidade seleciona o nodo mais prximo da rota, conforme as

distncias calculadas por (HEINEN, 2005):

(35)

Caso nenhuma restrio do modelo seja violada, o nodo que apresentar

a menor distncia ser inserido na rota (HEINEN, 2005).

O critrio de economia tem o objetivo de selecionar o local para se

inserir o nodo selecionado, de acordo com a frmula (HEINEN, 2005):

(36)

28

Ser selecionado o local que apresentar maior economia (HEINEN,

2005). Esta heurstica possui dois parmetros que podem ser alterados

conforme as necessidades da estratgia de soluo (GOLDBARG; LUNA,

2005):

Com e a insero realizada considerando a

minimizao do aumento da rota pela incluso de um novo cliente;

Com e , a insero realizada considerando a

minimizao da distncia entre os dois ns vizinhos;

O caso em que , uma generalizao do critrio

de Gaskell (apud Heinen, 2005, p. 5);

Quando , a insero ocorrer considerando o

cliente mais distante do depsito.

No exemplo apresentado, so utilizados os valores de e ,

segundo o critrio de Gaskell (apud Heinen, 2005, p. 5).

Neste exemplo, montada uma tabela com as distncias de todos os

nodos livres com relao rota inicial, 0-5-0, conforme a figura 5 (HEINEN,

2005). Nesta tabela verifica-se que o nodo mais prximo o nodo 1 e que h

apenas um local para inseri-lo, uma vez que h apenas dois nodos na rota

(HEINEN, 2005).

Figura 5 Lista de proximidades da rota 0-5-0


No entanto, utilizando a frmula (36), a economia obtida com a insero

deste nodo , tornando invivel inserir este nodo na rota. (HEINEN, 2005).

Uma vez que no possvel inserir um nodo nesta rota, criada uma nova rota

com o nodo 3, conforme a figura 8(b). Calculadas as distncias dos nodos

livres em relao a esta rota, identifica-se atravs da figura 6 que o nodo 4

deve ser selecionado (HEINEN, 2005). A economia obtida pela insero deste

29

nodo calculada com a frmula (36) de 14, viabilizando a insero deste nodo

na rota, conforme mostra a figura 8(c) (HEINEN, 2005).

Figura 6 Lista de proximidades da rota 0-3-0


Mais uma vez, deve-se calcular a proximidade dos nodos livres em

relao rota 0-4-3-0 e, desta vez, o nodo 1 selecionado para ser inserido na

rota. Como h mais de dois nodos presentes na rota, necessrio calcular a

tabela de economias para identificar a melhor posio de insero do nodo 1,

conforme a figura 7 (HEINEN, 2005). Assim, a maior economia obtida ao

inserir o nodo 1 entre os nodos 0 e 3 (HEINEN). O algoritmo segue sendo

executado desta forma at que no existam mais nodos livres, conforme a

figura 8(d).

Figura 7 Lista de economias da rota 0-4-3-0


30

Figura 8 Exemplo de aplicao da heurstica Mole e Jameson


31

6. PROCEDIMENTOS METODOLGICOS

Neste captulo sero apresentados os procedimentos metodolgicos que

descrevero como os objetivos estabelecidos no captulo anterior sero

alcanados. A metodologia utilizada no estudo uma adaptao da

metodologia proposta por Andrade (2009).

6.1. IDENTIFICAO DAS VARIVEIS RELEVANTES

A escolha das variveis que compe o modelo muito importante, uma

vez que nessa etapa que se define o escopo do modelo a ser construdo

(ANDRADE, 2009). Deve-se incluir apenas as informaes relevantes, uma vez

que informaes em excesso podem prejudicar o processo de tomada de

deciso (ANDRADE, 2009). No estudo, foi analisada a operao da empresa e

identificados quais itens devem ser levados em considerao no momento de

tomada de deciso quanto roteirizao de veculos.

A Fitolog realiza os tratamentos fitossanitrios em embalagens para

exportao atravs do Processo de Cmara Porttil. Cada cmara porttil em

conjunto com um veculo forma uma unidade mvel que se dirige at os locais

onde se encontram as embalagens para exportao para que seja realizado o

tratamento. Os clientes costumam entrar em contato para agendar o tratamento

com a Fitolog, confirmando a data e o horrio para realizao do servio, bem

como a quantidade de embalagens a ser tratada. O equipamento possui uma

capacidade de 100 para cada sesso de tratamento. H situaes em que

so realizados mais de um tratamento em sequncia em um mesmo cliente,

em funo do maior nmero de embalagens a serem tratadas. O tratamento no

cliente costuma durar cerca de 2 horas e 20 minutos, sendo que 35 minutos

so gastos para preparao da estrutura, 1 hora para realizao do tratamento,

30 minutos para carimbagem das embalagens e 15 minutos para

desmontagem. Os veculos costumam sair do depsito no incio do dia, s 8

horas, e retornar ao final do dia, s 17 horas. Sempre que os veculos

ultrapassam esse tempo de 8 horas de trabalho por dia, os operadores

recebem horas extras.

32 Alm das variveis identificadas na descrio da operao quantidade

de veculos, horrio para incio do servio em cada cliente, tempo de durao

do tratamento e horrio de sada e chegada ao depsito outras variveis so

importantes para a definio de um modelo de roteirizao. Segue o quadro

com todos os fatores a serem considerados no modelo de roteirizao de

veculos para a Fitolog:

Figura 9 Lista de fatores relevantes para o modelo de roteirizao da Fitolog

Smbolo Descrio

Custo de deslocamento entre os pontos e

Momento para iniciar o servio no cliente

Durao do servio no cliente

Tempo de deslocamento entre os pontos e

Horrio mais cedo em que permitida a sada do depsito

Horrio mais tarde em que permitido o retorno ao depsito

Distncia entre os pontos e

Valor da hora extra

Fonte: Elaborado pelo autor

6.2. FORMULAO DA FUNO-OBJETIVO E DAS RESTRIES

Definidas as variveis relevantes para o problema, deve-se definir

formalmente as relaes entre elas atravs de termos matemticos

(ANDRADE, 2009). Nesta etapa, foi formalizado o modelo matemtico que

reflete da forma mais prxima possvel as condies existentes no que tange

roteirizao de veculos na empresa Fitolog.

Para a formulao do modelo, algumas das variveis definidas

anteriormente conforme a operao da empresa foram adaptadas a fim de

facilitar os clculos durante a soluo posterior. Assim, o custo de

deslocamento entre os pontos e uma funo da distncia entre esses

pontos e do custo por quilmetro rodado dos veculos:

33

(37)

O tempo de servio no cliente uma constante para todos os clientes:

(38)

O tempo de deslocamento entre os pontos e ser uma funo da

distncia entre esses pontos e a velocidade mdia de deslocamento dos

veculos:

(39)

O modelo de roteirizao que mais se adapta operao da Fitolog

um problema de roteirizao com janelas de tempo, em que os clientes devem

ser atendidos dentro de um horrio especificado. Alm disso, h uma

penalidade, expressa na forma de horas extras, para os veculos que

ultrapassam o tempo de trabalho de 8 horas dirias. Assim, o modelo definido

para a Fitolog uma adaptao dos modelos propostos por Fischer, Jrsten e

Madsen (1997) e por Joubert (2007):

Minimizar

(40)

Sujeito a:

(41)

(42)

(43)

(44)

(45)

(46)

(47)

34

(48)

(49)

(50)

(51)

(52)

(53)

(54)


que o cliente atendido aps o cliente pelo veculo , caso seu valor seja

um; caso seu valor seja zero, o veculo no atender o cliente aps o cliente

. definido na equao (53) como uma varivel binria que indica que o

cliente atendido pelo veculo , caso seu valor seja um; caso seu valor seja

zero, o cliente no ser atendido pelo veculo . O momento para iniciar o

servio no cliente representado pela varivel . O momento de partida do

veculo do depsito determinado pela varivel , enquanto o momento do

retorno do veculo ao depsito determinado pela varivel . A funo

objetivo (40) busca minimizar o custo da operao, considerao os custos

com deslocamento entre os pontos das rotas, bem como as horas extras

realizadas por cada veculo . A restrio (41) garante que cada veculo que

visitar um ponto deixar aquele ponto em seguida. A restrio (42) garante que

cada rota se origina e termina no depsito. As restries (43), (44) e (45)

garantem a compatibilidade dos horrios de chegada e execuo do servio

nos diversos clientes. A restrio (46) garante que o momento da chegada e

incio do servio em um cliente est de acordo com a respectiva janela de

tempo. A restrio (47) garante que o horrio de sada do depsito respeita a

janela de tempo do depsito. A restrio (49) calcula as horas extras realizadas

por cada veculo caso este ultrapasse nove horas de trabalho por dia (oito

horas trabalhadas e uma hora de almoo). As restries (51) e (53) garantem

que cada cliente visitado apenas uma vez e que cada veculo deixa um

cliente apenas uma vez, respectivamente. A restrio (54) garante que o valor

de deve ser positivo; caso seja negativo, seu valor ser zero.

35

6.3. ESCOLHA DO MTODO MATEMTICO DE SOLUO

Aps a definio do modelo na etapa anterior, deve-se identificar qual

mtodo matemtico o mais indicado para a soluo, considerando o prprio

modelo e as questes que buscam ser respondidas (ANDRADE, 2009). Como

os mtodos para soluo so grandes e complexos, h a necessidade de

serem programados para a soluo atravs de computadores (ANDRADE,

2009).

Dentre as abordagens de soluo analisadas na etapa de

fundamentao terica, foi realizada a programao computacional da

heurstica de Clark e Wright e da heurstica de Mole e Jameson. As heursticas

foram escolhidas por permitirem o teste das restries de tempo durante a

roteirizao dos pontos e por seu nvel de complexidade estar adequado

realidade da empresa, que no exige a roteirizao de um grande nmero de

ns em uma mesma programao. Alm disso, interessante comparar o

desempenho das duas heursticas, uma vez que a heurstica de Clark e Wright

trabalha apenas com a insero de novos pontos nas extremidades das rotas

em criao enquanto a heurstica de Mole e Jameson permite a insero de

novos ns em qualquer ponto da rota em criao. Dessa forma, essas

abordagens sero aplicadas e seus resultados comparados, de forma a

identificar qual traz melhores solues para o problema de roteirizao de

veculos da empresa Fitolog.

36

7. RESULTADOS DO ESTUDO

7.1. PROGRAMAO COMPUTACIONAL

O software selecionado para programao das heursticas adaptadas

realidade da Fitolog foi o Microsoft Visual Basic e os dados foram

implementados atravs do Microsoft Excel 2010. Alm disso, para

implementao das duas heursticas necessrio obter os dados de distncia

e tempo de deslocamento entre os pontos que fazem parte do problema. Esses

dados so obtidos atravs de conexo da ferramenta criada no Microsoft Excel

2010 com o Google Maps.

Na sequncia sero descritos os algoritmos que formam o cdigo de

implementao das heursticas. Primeiramente, ser apresentado o algoritmo

para implementao da heurstica de Clark e Wright. A primeira parte do

algoritmo consiste na informao dos dados dos ns a serem atendidos, a

obteno das distncias e tempos de deslocamento e clculo das economias,

conforma a figura 10. Neste momento tambm realizado o ordenamento das

economias em ordem decrescente.

Figura 10 Primeira parte do algoritmo da heurstica de Clark e Wright


A segunda parte do algoritmo consiste na parte principal da heurstica.

Nesta etapa so formadas as rotas e verificadas as restries de tempo

definidas no problema, conforme a figura 11. Ao final da heurstica, so

apresentados os resultados dos roteiros formados.

37

Figura 11 Segunda parte do algoritmo da heurstica de Clark e Wright


38 Quanto ao algoritmo de Mole e Jameson, a primeira parte tambm

consiste na informao dos dados dos ns a serem atendidos e na obteno

dos dados de distncia e tempo de deslocamento entre os pontos, conforme a

figura 12. No entanto, nesse algoritmo as economias no so calculadas nesta

primeira etapa.

Figura 12 Primeira parte do algoritmo da heurstica de Mole e Jameson


Da mesma forma que o algoritmo anterior, a segunda etapa trata-se da

parte principal do cdigo. Neste momento so formadas as rotas, testadas as

restries de tempo do problema e apresentados os resultados, conforme a

figura 13.

39 Figura 13 Segunda parte do algoritmo da heurstica de Mole e Jameson


Para implementao desses algoritmos, foi desenvolvida uma interface

no Microsoft Excel 2010. Esta ferramenta desenvolvida no Microsoft Excel 2010

tem o objetivo de permitir ao usurio informar os dados sobre os ns a serem

roteirizados, os parmetros de roteirizao e, aps a execuo do algoritmo,

visualizar as rotas geradas.

A ferramenta possui uma primeira interface em que o usurio poder

inserir os dados dos ns a serem roteirizados, informando o CEP, a cidade e o

estado em que se localiza o ponto, alm dos horrios mnimos e mximos de

chegada ao cliente. O primeiro n a ser informado dever ser o do depsito

central e poder ser mantido fixo para diversas roteirizaes. Nesta tela

tambm possvel informar o nmero de veculos disponveis.

40

Figura 14 Ferramenta de roteirizao (insero de dados)


O usurio tambm poder ajustar alguns parmetros importantes para a

gerao das rotas. Em outra interface, podero ser informados os dados de

tempo de durao de cada servio, custo da hora extra, consumo mdio de

combustvel de cada veculo e custo do combustvel.

Figura 15 Ferramenta de roteirizao (parametrizaes)


Por fim, h uma interface para apresentao das rotas geradas aps a

roteirizao. Nesta interface apresentada a sequncia de visita aos ns em

cada rota, bem como o horrio de chegada em cada um deles. Para cada rota

tambm apresentado o custo com deslocamento de cada rota e o custo de

horas extras, quando as mesmas so necessrias.

41

Figura 16 Ferramenta de roteirizao (resultados)


7.2. ANLISE COMPARATIVA ENTRE AS HEURSTICAS

Para identificao da melhor heurstica de soluo do modelo proposto

necessrio realizar a comparao do desempenho de ambas conforme alguns

critrios no momento de realizar a roteirizao de determinados pontos. Os

critrios utilizados para comparar o desempenho das heursticas foram os

seguintes: custo total das rotas geradas, calculado atravs da distncia

percorrida para visitar todos os pontos da rota vezes o custo de combustvel

por quilmetro rodado, mais o valor de hora extra caso o veculo retorne para o

depsito aps o horrio mximo de chegada ao depsito; tempo para gerao

das rotas; quantidade de rotas geradas; e quantidade de pontos no

roteirizados.

Para realizar a anlise conforme esses critrios foram realizadas doze

simulaes de roteirizao com diferentes quantidades de ns a serem

roteirizados. Os testes foram realizados com os dados de endereo de atuais

clientes da Fitolog e a seleo de quais clientes seriam utilizados em cada

teste ocorreu de forma aleatria. Para cada teste, foi realizada a roteirizao

dos pontos selecionados utilizando a heurstica de Clark e Wright e a heurstica

de Mole e Jameson atravs da ferramenta desenvolvida no Microsoft Excel

2010. Nestes testes, foi utilizado um valor do litro de combustvel de R$ 2,69;

uma taxa de consumo de combustvel de 0,125 litros por kilmetro rodado de

42

cada veculo; um valor de hora extra de R$ 10,00; e um tempo de servio de 2

horas. Segue abaixo a tabela com os dados obtidos em cada teste para cada

uma das heursticas conforme os critrios de anlise estabelecidos

anteriormente:

Figura 17 Viso geral dos testes comparativos

Teste N de

ns

Custo total (R$)

Tempo (min) Quantidade

de rotas Pontos no roteirizados

C&W M&J C&W M&J C&W M&J C&W M&J

1 5 205,79 275,22 0,98 1,02 1 2 1 0

2 5 50,18 63,01 0,95 1,02 1 2 1 0

3 6 114,24 113,30 1,30 1,32 2 2 0 0

4 6 48,93 79,71 1,28 1,33 2 2 0 0

5 7 250,42 256,51 1,72 1,75 2 2 2 0

6 7 244,49 270,43 1,68 1,72 1 3 2 0

7 8 221,70 257,32 2,12 2,05 1 3 3 0

8 8 221,70 259,45 2,12 2,07 1 2 3 0

9 9 228,00 285,39 2,47 2,55 1 2 4 0

10 9 113,79 133,31 2,50 2,53 2 2 1 0

11 10 79,08 148,5 3,03 3,03 1 3 6 0

12 10 79,08 122,38 3,03 3,1 1 3 6 0


Quanto ao critrio de tempo, o mesmo poder ser desconsiderado para

anlise de qual heurstica dever ser utilizada. De forma geral, o tempo gasto

para obter os resultados muito baixo e no se confirma como um fator de

deciso. Alm disso, os tempos para gerao de resultado de cada heurstica

so muito prximos em todos os testes e h, em mdia, uma diferena de

apenas 1% nos tempos de cada heurstica.

Quanto ao critrio de quantidade de rotas geradas, a heurstica de Mole

e Jameson gerou, na maioria dos testes, um nmero maior de rotas. Em mdia,

para cada um dos testes realizados, a heurstica de Mole e Jameson gerou

uma rota a mais que a heurstica de Clark e Wright, conforme a figura 18.

43

Figura 18 Anlise dos testes comparativos (quantidade de rotas)

Teste N de ns Quantidade de rotas

C&W M&J

1 5 1 2

2 5 1 2

3 6 2 2

4 6 2 2

5 7 2 2

6 7 1 3

7 8 1 3

8 8 1 2

9 9 1 2

10 9 2 2

11 10 1 3

12 10 1 3

Mdia 1,33 2,33


A gerao de um nmero maior de rotas implica na necessidade de um

maior nmero de veculos para atender os pontos roteirizados. Considerando

apenas este critrio, a gerao de um menor nmero de rotas seria uma

vantagem da heurstica de Clark e Wright.

No entanto, ao analisar os dados do critrio de pontos no roteirizados,

possvel identificar que a heurstica de Clark e Wright no realiza a

roteirizao de diversos pontos na maioria dos testes realizados, da o nmero

reduzido de rotas geradas identificado anteriormente. Em mdia, a heurstica

de Clark e Wright no roteiriza 2,42 pontos em cada um dos testes realizados,

enquanto a heurstica de Mole e Jameson realiza a roteirizao de todos os

pontos nos testes realizados.

44

Figura 19 Anlise dos testes comparativos (pontos no roteirizados)

Teste N de ns Pontos no roteirizados

C&W M&J

1 5 1 0

2 5 1 0

3 6 0 0

4 6 0 0

5 7 2 0

6 7 2 0

7 8 3 0

8 8 3 0

9 9 4 0

10 9 1 0

11 10 6 0

12 10 6 0

Mdia 2,42 0,00


Esse fato ocorre porque a heurstica de Clark e Wright realiza a

roteirizao dos ns conforme o conceito das economias, apresentado

anteriormente na seo 6.5.1. Para cada par da economia calculado, a

insero nas rotas em criao s poder ocorrer caso um dos pontos desse par

de economia se encontre em um dos extremos de alguma das rotas em

criao. Caso essa condio no seja atendida, o par de economias

desconsiderado e realizado o teste com o prximo par, at que no existam

mais economias viveis. Alm disso, para que seja criada uma nova rota,

necessrio que nenhum dos dois pontos do par da economia esteja inserido

em alguma das rotas em criao, restringindo ainda mais a insero de pontos

nas rotas.

Conforme o conceito das economias de Clark e Wright, calculada a

economia de se visitar os pontos i e j em uma mesma rota ao invs de visitar o

ponto e retornar ao depsito e visitar o ponto e retornar ao depsito

(GOLDBARG; LUNA, 2005). Dessa forma, pode-se considerar que os pontos

no roteirizados na heurstica de Clark e Wright sero visitados por um veculo

que retornar ao depsito aps visitar um novo ponto, formando novas rotas de

45

apenas um n. Esse ponto est diretamente relacionado anlise do critrio de

custo total de cada rota gerada. Na maioria dos testes realizados, o custo total

de cada rota foi inferior na heurstica de Clark e Wright. Em mdia, o custo total

de cada teste realizado com a heurstica de Mole e Jameson foi superior em R$

33,93 com relao ao teste realizado com a heurstica de Clark e Wright.

Figura 20 Anlise dos testes comparativos (custo total)

Teste N de ns Custo total (R$)

C&W M&J

1 5 205,79 275,22

2 5 50,18 63,01

3 6 114,24 113,30

4 6 48,93 79,71

5 7 250,42 256,51

6 7 244,49 270,43

7 8 221,70 257,32

8 8 221,70 259,45

9 9 228,00 285,39

10 9 113,79 133,31

11 10 79,08 148,50

12 10 79,08 122,38

Mdia 154,78 188,71


No entanto, ao considerar os pontos no roteirizados na heurstica de

Clark e Wright como novas rotas de um nico ponto a ser visitado, o custo total

dos testes da heurstica de Clark e Wright superior ao custo total dos testes

da heurstica de Mole e Jameson. Analisando detalhadamente o exemplo do

teste nmero 9, verifica-se que gerada uma rota com 5 ns e com custo total

de R$ 228,00:

Rota 1: 0 8 2 4 1 5 0

Custo total: R$ 228,00

46 Considerando que os demais ns no roteados formam rotas com

apenas um n, pode-se considerar a existncia das seguintes rotas com seus

respectivos custos:

Rota 2: 0 3 0


Rota 3: 0 6 0


Rota 4: 0 7 0


Rota 5: 0 9 0


Assim, para o teste nmero nove, a heurstica de Clark e Wright acaba

tendo um custo total de R$ 265,84 em funo dos ns no roteirizados,

enquanto a heurstica de Mole e Jameson possui um custo de R$ 285,39.

Realizando o mesmo procedimento para os demais testes, verifica-se os

seguintes resultados:

47

Figura 21 Anlise dos testes comparativos (custo total e pontos no roteirizados)

Teste N de ns

Custo total (R$) Pontos no roteirizados

Custo total C&W com pontos no

roteirizados (R$) C&W M&J C&W M&J

1 5 205,79 275,22 1 0 214,09

2 5 50,18 63,01 1 0 56,06

3 6 114,24 113,30 0 0 114,24

4 6 48,93 79,71 0 0 48,93

5 7 250,42 256,51 2 0 266,98

6 7 244,49 270,43 2 0 255,40

7 8 221,70 257,32 3 0 254,65

8 8 221,70 259,45 3 0 251,28

9 9 228,00 285,39 4 0 265,50

10 9 113,79 133,31 1 0 122,09

11 10 79,08 148,5 6 0 141,71

12 10 79,08 122,38 6 0 137,39

Mdia 154,78 188,71 183,10

Analisando o custo total considerando os pontos no roteirizados na

heurstica de Clark e Wright como novas rotas, identifica-se que o custo total

das rotas geradas pela heurstica de Mole e Jameson , em mdia, apenas 3%

superior ao custo das rotas geradas pela heurstica de Clark e Wright. Alm

disso, verifica-se tambm que, considerando os pontos no roteirizados pela

heurstica de Clark e Wright como novas rotas h a necessidade de um nmero

maior de veculos para atender a programao realizada por essa heurstica.

Dessa forma, considerando que o custo total das programaes geradas pelas

duas heursticas muito prximo e que a programao da heurstica de Clark e

Wright exigiria um nmero maior de veculos para ser atendida, representando

novos custos com ativos imobilizados para a empresa, identifica-se que a

melhor soluo dentre as analisadas para o modelo de roteirizao de veculos

da empresa Fitolog seja a utilizao da heurstica de Mole e Jameson.

48

8. CONSIDERAES FINAIS

Visto que os transportes possuem um grande impacto sobre as

operaes de uma empresa, tanto em termos de custo quanto em termos de

satisfao dos clientes, este estudo teve como objetivo definir um modelo de

roteirizao de veculos para a empresa Fitolog. Para atingir tal objetivo, foi

necessrio realizar uma anlise da operao da empresa no que diz respeito

ao transporte e utilizar os conceitos tericos sobre roteirizao de veculos para

que fosse definido um modelo adaptado realidade da empresa.

No que diz respeito roteirizao de veculos na empresa Fitolog,

identificou-se que a mesma no possui nenhum modelo de roteirizao para

suportar a distribuio de suas unidades mveis para atendimento dos clientes

e que a determinao de quais clientes cada veculo atender e quais rotas

estes devem seguir realizada de forma emprica. Alm disso, tambm se

identificou que a empresa tende a ter um crescimento na demanda por

tratamentos fitossanitrios, dado o cenrio econmico e legal, o que exige um

melhor planejamento de transportes.

Realizada a anlise da empresa, definiu-se um modelo de roteirizao

de veculos com janelas de tempo e sem restries de capacidade de carga. O

modelo foi definido dessa forma porque os veculos da Fitolog apenas realizam

o servio de tratamento fitossanitrio em seus clientes e no h necessidade

de entrega de produtos nos mesmos. As restries de janela de tempo ocorrem

porque os clientes podem ser atendidos dentro de um determinado horrio e os

veculos tambm devem retornar ao depsito em um horrio determinado.

Caso este horrio de retorno seja ultrapassado, h o acrscimo de custo de

horas extras pagas aos funcionrios que operam os veculos. Alm disso,

durante o tempo de realizao do servio, os veculos permanecem em cada

cliente.

Definido este modelo, foi necessrio definir um mtodo de soluo do

mesmo. Foram selecionadas as heursticas de Clark e Wright e de Mole e

Jameson para soluo do problema. Nesta etapa, o objetivo foi identificar qual

heurstica melhor se adaptava realidade da empresa e ao modelo proposto.

Foram escolhidas estas heursticas por permitirem o teste das restries de

49

tempo durante a roteirizao e pela baixa complexidade, uma vez que a

realidade da empresa no exige a roteirizao de um grande nmero de ns.

Alm disso, a comparao entre as heursticas vlida uma vez que a

heurstica de Clark e Wright trabalha apenas com a insero de novos pontos

nas extremidades das rotas em criao enquanto a heurstica de Mole e

Jameson permite a insero de novos ns em qualquer ponto da rota em

criao (GOLDBARG; LUNA, 2005). Para comparar as duas heursticas, os

algoritmos foram programados atravs do software Microsoft Visual Basic e a

ferramenta para implementao foi criada no Microsoft Excel 2010.

Os critrios determinados para analisar as duas heursticas foram o

custo total das rotas geradas; o tempo para gerao das rotas; a quantidade de

rotas geradas; e a quantidade de pontos no roteirizados. O desempenho das

duas heursticas foi muito semelhante nos critrios de custo total das rotas e

tempo para gerao das rotas. No entanto, a heurstica de Clark e Wright

apresentou um alto nmero de pontos no roteirizados em diversos testes

realizados. Esses pontos no roteirizados so classificados como novas rotas

de apenas um n, o que exige um maior nmero de veculos para atender a

programao. Alm disso, quanto maior o nmero de ns inseridos para serem

roteirizados, maior foi a representatividade dos ns no roteirizados. Dessa

forma, a heurstica selecionada para ser utilizada na ferramenta de roteirizao

de veculos da Fitolog foi a heurstica de Mole e Jameson.

O modelo definido e a ferramenta criada permitiro Fitolog melhores

decises no que diz respeito aos transportes da empresa. Alm disso, a

ferramenta trar cada vez mais benefcios medida que a demanda da

empresa e o nmero de clientes for crescendo, exigindo um maior nvel de

complexidade nas decises de transporte. O modelo proposto e a ferramenta

tambm podero ser adaptados para outros servios da empresa, como o ramo

de controle de pragas, conforme vontade j manifestada pelos gestores.

50

REFERNCIAS

ANDRADE, Eduardo Leopoldino de. Introduo Pesquisa

Operacional: Mtodos e modelos para a anlise de deciso. 4. ed. Rio de

Janeiro: Ltc, 2009. 204 p. CD-ROM.

BALLOU, Ronald H.. Gerenciamento da Cadeia de Suprimentos / Logstica

Empresarial. 5. ed. Porto Alegre: Bookman, 2006. 616 p.

BOWERSOX, Donald J.; COOPER, M. Bixby; CLOSS, David J.. Gesto

Logstica de Cadeias de Suprimentos. Porto Alegre: Bookman, 2006. 528 p.

DANTZIG, G. B.; RAMSER, J. H.. The truck dispatching problem. Management

Science, Hanover, Eua, p. 80-91. ago. 1959.

FISHER, Marshall L.; JRNSTEN, Kurt O.; MADSEN, Oli B. G.. Vehicle routing

with time windows: two optimization algorithms. Operations

Research, Heidelberg, p. 488-492. 1997.

GALHARDI, Antnio Csar. Tecnologia da informao e os processos de

roteirizao com restries de janela de tempo. In: SIMPSIO DE

ENGENHARIA DE PRODUO, 13., 2006, Bauru. Anais eletrnicos. So

Paulo: Unesp, 2006. p. 1 - 12. Disponvel em:

. Acesso em:

05 set. 2011.

GHISI, Marcos Angeli et al. Usos e benefcios de softwares de roteirizao na

gesto de transportes. In: SEMINRIOS EM ADMINISTRAO FEA-USP, 7.,

2004, So Paulo.Anais eletrnicos. So Paulo: Fea - Usp, 2004. p. 1 - 12.

Disponvel em: . Acesso em: 05

set. 2011.

51

GOLDBARG, Marco Cesar; LUNA, Henrique Pacca L.. Otimizao

combinatria e programao linear: modelos e algoritmos. 2. ed. Rio de

Janeiro: Elsevier, 2005. 518 p.

HEINEN, Milton Roberto. Anlise e Implementao de Algoritmos para o

Roteamento de Veculos. In: SIMPSIO DE INFORMTICA DA REGIO

CENTRO DO RS, 4., 2005, Santa Maria. Anais... . So Leopoldo: Unisinos,

2005. p. 1 - 8. Disponvel em:

. Acesso em: 20 out. 2011.

JOUBERT, Johannes Wilhelm. An integrated and intelligent metaheuristic

for constrained vehicle routing. 2007. 10 v. Tese (Doutorado) - University Of

Pretoria, Pretoria, 2007. Cap. 2. Disponvel em:

. Acesso em: 13 out. 2011.

LACHTERMACHER, Gerson. Pesquisa operacional na tomada de

decises. 4. ed. So Paulo: Pearson Prentice Hall, 2009. 223 p. CD-ROM.

MARINAKIS, Yannis; MIGDALAS, Athanasios. Annotated Bibliography in

Vehicle Routing. Operational Research: An International

Journal, Heidelberg, p. 27-46. jan. 2007.

RAGSDALE, Cliff T.. Modelagem e Anlise de Deciso. So Paulo: Cengage

Learning, 2009. 590 p.

SOLOMON, Marius M.. Algorithms for the Vehicle Routing and Scheduling

Problems with Time Window Constraints. Operations Research,Heidelberg, p.

254-265. mar. 1987.

Documents

Definição de Um Modelo de Roteirização de Veiculos Para a Empresa Fitolog