ABORDAGEM HEURÍSTICA E META- HEURÍSTICA NA .de trajeto do motoboy. ... As prestações de serviço

Embed Size (px)

Text of ABORDAGEM HEURÍSTICA E META- HEURÍSTICA NA .de trajeto do motoboy. ... As prestações de serviço

ABORDAGEM HEURSTICA E META-

HEURSTICA NA OTIMIZAO DO

PROCESSO OPERACIONAL DE UMA

EMPRESA DE TRANSPORTES RPIDOS

JULIO CESAR FERREIRA (PUCPR)

ferreira.julio@pucpr.edu.br

Maria Teresinha Arns Steiner (PUCPR)

tere@mat.ufpr.br

Mariana de Siqueira Guersola (PUCPR)

marianaguersola@gmail.com

Osiris Canciglieri Junior (PUCPR)

osiris.canciglieri@pucpr.br

Este trabalho trata da continuidade do trabalho do Ferreira (2013),

que aborda a otimizao de um processo operacional de uma empresa

de transportes rpidos, aqui denominada de ABC, localizada na

Cidade Industrial de Curitiba (CIC), no municpio de Curitiba, PR. O

objetivo geral do presente trabalho definir de forma otimizada os

grupos (clusters) de pontos de demanda a serem atendidos pelos

veculos da empresa ABC, assim como os seus roteiros dentro de cada

grupo. Para isto, fez-se uso das heursticas de Teitz & Bart, dos

Savings de Clarke e Wright e do mtodo do Custo Mnimo, alm da

meta-heurstica Simulated Annealing. Desta forma, foram avaliados

dois cenrios: o primeiro consiste em comparar os procedimentos

heursticos e meta-heurstico com o resultado otimizado por Ferreira

(2013), com a formao de trs grupos de demanda. O melhor

resultado foi referente a combinao da heurstica Teitz & Bart com a

meta-heurstica Simulated Annealing com uma aproximao de 7,18%

em relao ao resultado timo. O pior desempenho foi da combinao

da meta-heurstica Simulated Annealing com a heurstica dos Savings

de Clarke e Wright com 14,7% acima do resultado timo. O segundo

cenrio consiste em comprar os procedimentos heursticos e meta-

heurstico com a soluo atual adotada pela empresa estudada, que

envolve a formao de cinco grupos de demanda. O melhor resultado

tambm foi referente a combinao da heurstica de Teitz & Bart com

a meta-heurstica Simulated Annealing com uma aproximao de 2,6%

em relao ao resultado timo. O pior desempenho foi da combinao

da heurstica de Teitz & Bart com a heurstica dos Savings de Clarke e

Wright com 10% acima do resultado timo. Em relao soluo

atual adotada pela ABC, a melhor combinao heurstica e meta-

heurstica proporcionou uma reduo de 31,8% em relao ao tempo

de trajeto do motoboy. J o resultado timo proporcionou 33,5% de

otimizao.

XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO Perspectivas Globais para a Engenharia de Produo Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.

XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO Perspectivas Globais para a Engenharia de Produo Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.

2

Palavras-chave: Otimizao, Problemas de Localizao de Facilidades

(PLF), Problema do Caixeiro Viajante (PCV), Heurstica, Meta-

Heurstica (MH)

XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO Perspectivas Globais para a Engenharia de Produo Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.

3

1. Introduo

Os algoritmos Heursticos (H) e os Meta-Heursticos (MH) so alternativas em relao aos

mtodos exatos devido ao alto custo computacional dos modelos matemticos. Os mtodos H

procuram alcanar os resultados para os problemas rapidamente, mas no garantem que a

soluo obtida seja a soluo tima; mas apresentam resultados satisfatrios em um tempo

computacional aceitvel. Por outro lado os mtodos e algoritmos MH so de uso e aplicao

geral, normalmente eles no se prendem a timos locais e buscam o timo global

(TAVORA, 2011 e DETRO, 2013). Assim como os mtodos H, as MH tambm procuram

alcanar os resultados para os problemas rapidamente, sem garantir que a soluo obtida seja

a soluo tima; e, alm disso, diferentemente dos mtodos H, vrios parmetros devem ser

ajustados dependendo do problema particular que se est resolvendo.

O presente artigo d continuidade ao trabalho de Ferreira (2013). A empresa pesquisada

realiza servios de entregas rpidas (trata-se de uma agncia de Motoboy). Para preservar a

identidade, ela ser chamada de ABC. Pretende-se junto a esta empresa, otimizar o tempo

de atendimento, minimizando as distncias a serem percorridas e, assim, obter a maximizao

dos lucros empresa e uma maior satisfao de seus clientes.

Este trabalho visa responder a seguinte pergunta: Como minimizar o tempo de entrega na

prestao de servio sem perder (ou, inclusive, melhorar) a qualidade no atendimento?

O presente trabalho est organizado da seguinte forma: na seo 2 est a descrio do

problema; na seo 3 est a reviso da literatura relacionada ao tema aqui abordado. Na seo

4 so apresentados os resultados e, finalmente, na seo 5, as concluses.

2. Descrio do problema

Segundo Ferreira (2013), a empresa ABC fundada em 2008, aqui analisada, uma prestadora

de servio de Entregas Rpidas e Encomendas Expressas (agncia de motoboys) que est

localizada na Cidade Industrial de Curitiba (CIC), Curitiba, PR. Para realizar suas atividades

ela utiliza motocicletas, utilitrios e/ou caminhes. Ela no possui restrio de cobertura para

os seus clientes.

As prestaes de servio ofertadas pela empresa ABC podem ser classificadas de duas

formas: Rotas Planejadas e as Rotas no Planejadas. As Rotas Planejadas so previamente

estabelecidas, pois o contratante solicita que a empresa realize entregas em diversos

XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO Perspectivas Globais para a Engenharia de Produo Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.

4

endereos. Nestes casos so realizadas entregas de notas fiscais, boletos bancrios e revistas.

As Rotas no Planejadas so a prestao de servio mais solicitada, pois as empresas

conveniadas contatam a Empresa ABC para realizar a atividade conforme suas necessidades.

Estas solicitaes podem ocorrer de diversas formas, tais como coletar na empresa solicitante

e levar a um ou mais destino (s) especfico (s) e realizar pagamento de uma fatura em uma

agncia bancria ou casa lotrica.

Este trabalho tem foco na otimizao de uma das rotas programadas que possui 50 endereos.

Para preservar a identidade dos clientes, eles foram simplesmente numerados de 1 a 50.

O foco deste estudo foi otimizar o tempo do percurso em uma atividade planejada que

inicialmente era realizada em cinco dias (de segunda a sexta-feira) e foi otimizada para ser

executada em trs dias (3., 4. e 5.-feiras). Isto porque a ABC considerou que na 2. e na 6. -

feiras, a empresa recebe mais solicitaes de Rotas no Planejadas. Desta forma, ela julgou

disponibilizar melhor a mo de obra dos seus colaboradores.

Em Ferreira (2013), o cenrio atual (Tabela 1) foi comparado com o proposto pelo autor

(Tabela 2) que fez uso dos modelos matemticos do Problema de Localizao de Facilidades

(PLF) e do Problema do Caixeiro Viajante (PCV).

Tabela 1 - Programao dos roteiros realizados no cenrio atual

Grupo Caminho Tempo (min.)

2.-feira (ABC - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - ABC) 89

3. -feira

(ABC - 10 - 11 - 12 - 13 - 14 - 15 - 16 17 -

18 - 19 - ABC) 114

4. -feira

(ABC - 20 - 21 - 22 - 23 - 24 - 25 - 26 27 -

28 - 29 - 30 - ABC) 136

5. -feira

(ABC - 31 - 32 - 33 - 34 - 35 - 36 - 37 38 -

39 - 40 - 41 - 42 - ABC) 156

6. -feira

(ABC - 43 - 44 - 45 - 46 - 47 - 48 - 49 50 -

ABC) 120

Total 615

Fonte: Adaptado de Ferreira e Steiner (2013).

Tabela 2 - Proposta de programao otimizada para os roteiros

Grupo Caminho Tempo (min.)

3.-feira

(ABC 2 4 1 9 8 7 5 3 29

18 17 24 28 41 42 6 ABC) 87

4.-feira

(ABC 19 22 21 20 16 10 14

13 37 25 26 23 40 15 49 47

50 48 46 33 31 36 32 38 39

34 35 27 ABC) 165

5. feira (ABC 30 12 11 45 43 44 ABC) 80

XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO Perspectivas Globais para a Engenharia de Produo Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.

5

Total 332

Fonte: Adaptado de Ferreira e Steiner (2013).

A Tabela 1 abordou a roteirizao exercida pelos motoboys, para realizar as entregas, sendo

que os percursos foram definidos por eles prprios. Desta forma, a atividade levou 615 min. A

Tabela 2 visa atender as necessidades da ABC, onde o colaborador realiza as atividades de

forma otimizada. Assim, atravs dos modelos matemticos do PLF e do PCV, se tem a

proposta de realizar esta mesma atividade em 332 min. Por fim, foi possvel realizar uma

otimizao de 46% de disponibilidade de mo de obra para realizar outras atividades, sendo

este o resultado do objetivo principal da pesquisa de Ferreira (2013).

3. Fundamentao terica

Segundo Tavora (2011) e Detro (2013), a Otimizao Combinatria (OC) trata de problemas

cuja soluo envolve a otimizao de uma ou mais funes objetivo e juntamente satisfaz as

restries sobre as suas variveis de deciso. Existem diversas abordagens para solucionar os

problemas de OC, dente eles esto os mtodos exatos, H e MH.

3.1. Modelo matemtico do PCV

Seja G(V, A) um grafo, onde V = {1, 2, 3, ..., n} um conjunto de ns e A um conjunto de

arcos. Os ns podem