ABORDAGEM HEURÍSTICA E META- HEURÍSTICA NA …abepro.org.br/biblioteca/TN_STO_211_250_26415.pdf · de trajeto do motoboy. ... As prestações de serviço ofertadas pela empresa

ABORDAGEM HEURÍSTICA E META-

HEURÍSTICA NA OTIMIZAÇÃO DO

PROCESSO OPERACIONAL DE UMA

EMPRESA DE TRANSPORTES RÁPIDOS

JULIO CESAR FERREIRA (PUCPR)

[email protected]

Maria Teresinha Arns Steiner (PUCPR)

[email protected]

Mariana de Siqueira Guersola (PUCPR)

[email protected]

Osiris Canciglieri Junior (PUCPR)

[email protected]

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

que aborda a otimização de um processo operacional de uma empresa

de transportes rápidos, aqui denominada de ABC, localizada na

Cidade Industrial de Curitiba (CIC), no município de Curitiba, PR. O

objetivo geral do presente trabalho é definir de forma otimizada os

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

veículos da empresa ABC, assim como os seus roteiros dentro de cada

grupo. Para isto, fez-se uso das heurísticas de Teitz & Bart, dos

Savings de Clarke e Wright e do método do Custo Mínimo, além da

meta-heurística Simulated Annealing. Desta forma, foram avaliados

dois cenários: o primeiro consiste em comparar os procedimentos

heurísticos e meta-heurístico com o resultado otimizado por Ferreira

(2013), com a formação de três grupos de demanda. O melhor

resultado foi referente a combinação da heurística Teitz & Bart com a

meta-heurística Simulated Annealing com uma aproximação de 7,18%

em relação ao resultado ótimo. O pior desempenho foi da combinação

da meta-heurística Simulated Annealing com a heurística dos Savings

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

cenário consiste em comprar os procedimentos heurísticos e meta-

heurístico com a solução atual adotada pela empresa estudada, que

envolve a formação de cinco grupos de demanda. O melhor resultado

também foi referente a combinação da heurística de Teitz & Bart com

a meta-heurística Simulated Annealing com uma aproximação de 2,6%

em relação ao resultado ótimo. O pior desempenho foi da combinação

da heurística de Teitz & Bart com a heurística dos Savings de Clarke e

Wright com 10% acima do resultado ótimo. Em relação à solução

atual adotada pela ABC, a melhor combinação heurística e meta-

heurística proporcionou uma redução de 31,8% em relação ao tempo

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

otimização.

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

XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO Perspectivas Globais para a Engenharia de Produção

Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.

2

Palavras-chave: Otimização, Problemas de Localização de Facilidades

(PLF), Problema do Caixeiro Viajante (PCV), Heurística, Meta-

Heurística (MH)



3

1. Introdução

Os algoritmos Heurísticos (H) e os Meta-Heurísticos (MH) são alternativas em relação aos

métodos exatos devido ao alto custo computacional dos modelos matemáticos. Os métodos H

procuram alcançar os resultados para os problemas rapidamente, mas não garantem que a

solução obtida seja a solução ótima; mas apresentam resultados satisfatórios em um tempo

computacional aceitável. Por outro lado os métodos e algoritmos MH são de uso e aplicação

geral, normalmente eles não se “prendem” a ótimos locais e buscam o ótimo global

(TAVORA, 2011 e DETRO, 2013). Assim como os métodos H, as MH também procuram

alcançar os resultados para os problemas rapidamente, sem garantir que a solução obtida seja

a solução ótima; e, além disso, diferentemente dos métodos H, vários parâmetros 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 serviços de entregas rápidas (trata-se de uma agência de Motoboy). Para preservar a

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

de atendimento, minimizando as distâncias a serem percorridas e, assim, obter a maximização

dos lucros à empresa e uma maior satisfação de seus clientes.

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

prestação de serviço sem perder (ou, inclusive, melhorar) a qualidade no atendimento?

O presente trabalho está organizado da seguinte forma: na seção 2 está a descrição do

problema; na seção 3 está a revisão da literatura relacionada ao tema aqui abordado. Na seção

4 são apresentados os resultados e, finalmente, na seção 5, as conclusões.

2. Descrição do problema

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

de serviço de Entregas Rápidas e Encomendas Expressas (agência de motoboys) que está

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

ela utiliza motocicletas, utilitários e/ou caminhões. Ela não possui restrição de cobertura para

os seus clientes.

As prestações de serviço ofertadas pela empresa ABC podem ser classificadas de duas

formas: Rotas Planejadas e as Rotas não Planejadas. As Rotas Planejadas são previamente

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



4

endereços. Nestes casos são realizadas entregas de notas fiscais, boletos bancários e revistas.

As Rotas não Planejadas são a prestação de serviço mais solicitada, pois as empresas

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

Estas solicitações podem ocorrer de diversas formas, tais como coletar na empresa solicitante

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

agência bancária ou casa lotérica.

Este trabalho tem foco na otimização de uma das rotas programadas que possui 50 endereços.

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 três dias (3ª., 4ª. e 5ª.-feiras). Isto porque a ABC considerou que na 2ª. e na 6ª. -

feiras, a empresa recebe mais solicitações de Rotas não Planejadas. Desta forma, ela julgou

disponibilizar melhor a mão de obra dos seus colaboradores.

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

(Tabela 2) que fez uso dos modelos matemáticos do Problema de Localização de Facilidades

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

Tabela 1 - Programação dos roteiros realizados no cenário 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 programação 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



5

Total 332

Fonte: Adaptado de Ferreira e Steiner (2013).

A Tabela 1 abordou a roteirização exercida pelos motoboys, para realizar as entregas, sendo

que os percursos foram definidos por eles próprios. 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, através dos modelos matemáticos do PLF e do PCV, se tem a

proposta de realizar esta mesma atividade em 332 min. Por fim, foi possível realizar uma

otimização de 46% de disponibilidade de mão de obra para realizar outras atividades, sendo

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

3. Fundamentação teórica

Segundo Tavora (2011) e Detro (2013), a Otimização Combinatória (OC) trata de problemas

cuja solução envolve a otimização de uma ou mais funções objetivo e juntamente satisfaz as

restrições sobre as suas variáveis de decisão. Existem diversas abordagens para solucionar os

problemas de OC, dente eles estão os métodos exatos, H e MH.

3.1. Modelo matemático do PCV

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

arcos. Os nós podem representar cidades e os arcos, os pares ordenados de cidades por meio

das quais é possível realizar uma viagem. Para o arco (i, j) pertencente a A, cij é o tempo da

viagem/trajeto da cidade i para a cidade j. O problema em questão é encontrar uma rota que

forme um ciclo hamiltoniano, ou seja, que inicie e termine na cidade “1”, que tenha o tempo

de viagem mínimo e visite todas as cidades apenas uma vez. Assumindo que as variáveis xij=1

representam que a cidade j foi visitada na sequência da cidade i; caso contrário xij = 0, tem-se

o modelo matemático de Proglemação Linear Inteira Binária (PLIB) para o PCV de (1)-(5) a

seguir (COLIN, 2007).



6

A equação (1) é a função objetivo, onde deseja-se minimizar a distância total a ser percorrida.

As equações (2) e (3) representam dois conjuntos de restrições, que fazem com que na rota

final “entre” apenas um arco em cada nó e que “saia” apenas um arco de cada nó,

respectivamente. As variáveis binárias xij em (5) assumem valor igual a “1”, caso de o arco

(i,j) satifaça uj para integrar a solução, ou o valor “0”, caso contrário. A inequação em (4),

garante que a solução ótima não continha sub-rotas. Se não for introduzido este grupo de

restrições, não há como garantir que a solução proposta possua uma rota única. As variáveis ui

e uj são auxiliares e não tem significado físico. Em contra partida, as restrições das subrotas

(4) podem ser definidas de forma alternativa. Ao considerar um conjunto de cidades S com s

cidades, em que 2 s<n , a inequação (6) garante que as sub-rotas não foram formadas para o

conjunto de cidades S. Desta forma, pode ser reformulado como em (6) (COLIN, 2007).

A expressão S contida em V representa que uma restrição deve ser formada para cada

subconjunto possível de V.

3.2. Algoritmo heurístico dos Savings de Clarke e Wright

O algoritmo de Clarke & Wright, 1964, também é conhecido como Heurística das Economias

ou dos Savings de C&W. Este é um dos algoritmos H clássicos de construção de rotas. Está

apresentado a seguir (LOPES et al. 2013).

INÍCIO

Passo 1: Iniciar pelo vértice “1”, selecionado por algum critério ou aleatoriamente;



7

Passo 2: Calcular os savings:

para todo i, j = 2, 3, 4 ..., n. Considerar sij=0, se i=j, i=1 e j=1;

Passo 3: Ordenar os savings em ordem decrescente;

Passo 4: Iniciando do topo da lista dos savings ate o final, forme sub-rotas maiores fazendo a

ligação dos nós i e j apropriados.

FIM

3.3. Modelo Matemático do PLF

Segundo Gandolpho e Pizzolato (2009), o problema das p-Medianas ou PLF procura localizar

p instalações que fornecem um determinado serviço de modo a minimizar a distância

ponderada dos clientes a instalação mais próxima. Este problema é solucionado por meio do

modelo matemático PLIB, conforme (8) a (12) a seguir.

onde: [dij]nxm é a matriz simétrica de distâncias, com dij= 0, para todo i; [xij]nxm é a matriz de

alocação, com xij= 1 caso o vértice i estiver alocado ao vértice j, e xij=0, caso contrário; xjj =1

caso o vértice j for uma mediana, e xjj=0, caso contrário; p é o número de medianas a serem

localizadas; N é o conjunto de postos considerados, N={1, 2, ..., n}; wi é o peso do vértice i.

Em (8), a função objetivo busca a distânca mínima; as restrições em (9) e (11) exigem que

cada vértice i seja alocado somente a um único vértice j. A restrição (10) determina

exatamente o número de medianas (p) a serem buscadas; as variéveis em (12) são binárias,

assumindo o valor “1” quando pertence a uma mediana e “0”, caso contrário.

3.4. Método do Custo Mínimo

Segundo Gandolpho e Pizzolato (2009), o método do Custo Mínimo (CM) prioriza a

atribuição de valores às células de menor custo. Desta forma se faz a variável correspondente



8

igual ao mínimo entre a capacidade e a demanda. Assim que a capacidade ou a demanda for

esgotada, esta será excluída e passa-se a buscar a célula de menor custo dentre as células

remanescentes. O método segue buscando a célula mais econômica dentre as remanescentes.

As escolhas posteriores são triviais, sempre escolhendo em ordem crescente.

3.5. Algoritmo de Teitz & Bart

A partir de Lopes et al. (2013), o algoritmo de Teitz & Bart (T&B) é uma das H mais

conhecidas para resolver este tipo de problema. Ela se baseia na substituição de medianas da

solução, ou seja, define os pontos da mediana. Desta forma, utiliza uma solução inicial para

melhorar o valor da função objetivo em cada interação. A seguir está a descrição do

algoritmo.

INÍCIO

Passo 1: Por meio de algum critério estabelecido ou aleatoriamente selecione um conjunto S,

com |S| = p para formar uma aproximação inicial para as p-medianas;

Passo 2: Rotule todos os vértices vi que não pertencem a S como não avaliados;

Passo 3: Enquanto existirem vértices não avaliados em V-S, faça: selecione o vértice vi

pertencente a V-S, não analisado, e calcule a redução (13) do número de transmissão, para

todo vj pertencente a S, por meio de (13).

Faça io = [ i, j]:

Se i,j >0 faça S (S U {vi} – {vj,0}) e rotule vj,0 como analisado;

Passo 4: Se durante a execução do Passo 3, houver alguma modificação no conjunto S, volte

ao Passo 2, caso contrário, pare, e apresente o conjunto S com uma aproximação para a

solução do problema da p-medianas.

FIM

3.6. Meta-heurística Simulated Annealing

A partir de Lopes et al. (2013) e Lorena et al. (2012), o Simulated Annealing (SA;

Recozimento Simulado) utiliza uma estratégia diferente dos métodos exatos, pois a partir de

critérios probabilísticos ele aceita soluções que pioram a função objetivo a fim de escapar de

mínimos locais. O método foi proposto por Kirkpatrick et al. (1983) que se baseou no trabalho

de Metropolis et al. (1953). A nomenclatura recozimento é derivada do processo de

aquecimento de um sólido até o seu ponto de fusão, seguido de um suave resfriamento. O



9

processo do resfriamento lento é fundamental para a manutenção do equilíbrio térmico para

que os átomos se reorganizem com uma energia mínima.

A função objetivo corresponde á energia do sólido de forma similar ao recozimento em

termodinâmica. Caso surja uma solução viável, ela será aceita e será o novo centro de busca,

senão ela poderá ser aceita se atender ao critério probabilístico (14).

onde: p = função aceite da nova solução gerada aleatoriamente; Δf = variação da função

objetivo; T = parâmetro de temperatura que mede a probabilidade de piora da função objetivo.

A nova solução será aceita somente se p for maior que um número entre zero e um, gerado

randomicamente. Caso contrário, a solução anterior será mantida. O valor de T decresce

devido ao fator de redução α, até que o critério de parada seja satisfeito.

A cada novo vizinho s’ de s, é calculado a sua variação, onde se:

a) Δf < 0: há redução de energia, a nova solução s’ é aceita e passa a ser a nova solução;

b) Δf = 0: não ocorre alteração de energia, a nova solução s’ é aceita e passa a ser a nova

solução;

c) Δf > 0: há um aumento de energia, a solução depende do critério probabilístico para

ser aceita.

Quando a temperatura esta elevada, há mais chances de escapar de mínimos locais em

relação a temperaturas inferiores. O procedimento finaliza quando a temperatura chega

próximo de “0” e as soluções não são mais aceitas.

3.4. Trabalhos correlatos

Existem diversas obras referentes ao PCV e ao problema das p-Medianas (PLF), dentre as

quais destacam-se as seguintes: Távora (2011) utilizou o PCV para realizar um tour otimizado

aos diversos grupos de visitantes em comemoração ao bicentenário da Academia Militar das

Agulhas Negras (AMAN), sediada em Resende, RJ. O autor fez uso do software Matlab para

resolver o problema utilizando o Algoritmo Colônia de Formigas (ACO) e o ACO

Modificado. Battarra et al. (2013) trataram do PCV com Draft Limits (TSPDL, ou seja,

Traveling Salesman Problem with Draft Limits; PCV com Limite de Projeto), que é uma

variante do PCV muito conhecida no meio do transporte marítimo, devido a restrições sobre



10

as infraestruturas portuárias. Os autores propuseram três formulações matemáticas e

compararam os seus desempenhos computacionais.

Carvalho (2013) aplicou o PCV no contexto de roteirização de um veículo envolvendo a

distribuição de alimentos refrigerados e congelados, em aspectos logísticos, melhorando o

cenário atual de perdas e danos deste tipo de mercadoria. Assim, foi possível constatar que

para este tipo de sequência, não se pode garantir a temperatura ideal da carga transportada.

Lorena et al. (2012) apresentam uma nova abordagem para o Berth Allocation Problem (BAP;

Problema de Alocação de Berço), no contexto de otimização em terminais marítimos. Os

autores modelaram o BAP em caso discreto e proporam uma nova abordagem para resolvê-lo,

onde se baseia na aplicação do método Clustering Search (CS; Pesquisa de Agupamento)

usando o Simulated Annealing (AS; Recozimento Simulado).

Alem e Toso (2013) propuseram um projeto ótimo de planejamento de localização, para

reciclagem de resíduos sólidos urbanos que se enquadram dentro do orçamento financeiro

acordado entre o governo municipal e o Banco Nacional de Desenvolvimento Econômico e

Social, no município de Sorocaba, SP. Confirmaram a possibilidade de melhoria sem a adição

de investimentos. Khamjan et al. (2013) abordam o problema de localização das estações de

carregamento de cana-de-açúcar na Tailândia. O estudo de caso abrange mais de 5.500

pequenos campos, cerca de 5.400 ha.

4. Obtenção dos Resultados

Para a metodologia busca-se aplicar métodos exatos, H, MH a fim de resolver o problema

descrito na seção 2. A Figura 1 sintetiza a proposta desta seção.

Figura 1 – Cenários 1 e 2

Fonte: Ferreira (2013).



11

A otimização proposta por Ferreira (2013) possui três agrupamentos. Assim, o primeiro

cenário realizará a comparação com procedimentos H e MH, a fim de verificar a proximidade

destes resultados com a solução ótima.

O segundo cenário utiliza cinco agrupamentos, visto que esta quantidade refere-se a prática

realizada pela empresa ABC. Desta forma, será realizada a comparação entre a prática, os

procedimentos H e MH e os procedimentos exatos. Os resultados exatos para o PLF e o PCV

foram obtidos por meio do software LINGO 12.0 e os resultados para os procedimentos

heurísticos para o PLF e o PCV foram obtidos por meio do programa computacional Matlab

versão R2013a, desenvolvidos na linguagem do referido software. Para os experimentos foi

utilizado um notebook com processador Intel Core i3-3217U CPU 1.80GHz , 4GB de RAM.

Os procedimentos H e MH estão ilustrados na Figura 2.

Conforme a Figura 2, os procedimentos H e MH acontecem de forma pura e mista. No

primeiro caso, aplica-se a MH S.A. para a obtenção dos pontos das medianas e, na sequencia,

o Método do CM para a definição dos agrupamentos, sendo que até este ponto está

relacionado ao PLF. A partir de então, aplica-se a MH S.A. no caso do PCV para a definição

do roteiro do motoboy. Este procedimento é apenas MH e trata do primeiro resultado.

Figura 2 – Procedimentos H e MH




12

Ainda no primeiro caso, se tem procedimentos mistos, considerando que para o PCV se aplica

a H dos Savings de C&W. Este será o segundo resultado. A mesma lógica é aplicada para o

segundo caso, que inicia com o procedimento H de T&B para o terceiro e o quarto resultado,

sendo que o terceiro resultado é misto e o quarto resultado é H.

Vale ressaltar que a MH S.A. foi escolhida para resolver o PLF e o PCV, pois é aplicável às

duas situações (PCV e PLF) e permite testar soluções mais distantes da solução atual, o que

contribui para chegar mais próximo do ótimo global. O parâmetro “Quantidade de Iterações”

ficou definido com o valor 200 e os parâmetros “Número de Perturbações” e “Número de

Sucessos” ficaram definidos com o valor 10, após vários experimentos realizados pelo autor.

A H de T&B foi selecionada, pois tem apresentado excelentes resultados em vários dos

trabalhos analisados. O mesmo acontece com a H dos Savings de C&W. O método CM,

usualmente utilizado para se determinar uma solução inicial para problemas de transportes, foi

aqui selecionado pelo fato de cumprir o papel de atribuir as ofertas às demandas. Em outras

palavras, atribui as “não medianas” para as “medianas”, formando os agrupamentos.

A solução otimizada por Ferreira (2013) forneceu três agrupamentos, dentre eles o

agrupamento para 4ª.-feira que apresentou 165 mim para percorrer os endereços. Na prática,

este trajeto é difícil de ser cumprido com sucesso, pois o funcionário deveria permanecer por

menos de 11 min no estabelecimento e não poderia ocorrer nenhum imprevisto; caso

contrário, ele extrapolaria a carga horária diária de oito horas. Devido a possibilidade deste

roteiro ser inviável, foram mantidos os cinco agrupamentos para os testes com as MH e as H.

A Tabela 3 apresenta o comparativo do Cenário 1.

Tabela 3 – Cenário 1

PLF S.A. T&B Ótimo

PCV S.A. Savings S.A. Savings

Terça 94,4 92,4 104,4 117,4 87

Quarta 105,43 118,43 102,43 104,43 165

Quinta 164 170 149 142 80

Total: 363,83 380,83 355,83 363,83 332


A partir da Tabela 3 verifica-se que o melhor resultado foi o terceiro resultado parcial,

referente a combinação da H de T&B com a MH S.A com uma aproximação de 7,18% em

relação ao resultado ótimo. O pior desempenho foi da combinação da MH S.A com a H dos



13

Savings de C&W com 14,7% acima do resultado ótimo. A Figura 3 apresenta o melhor roteiro

H e MH e o roteiro ótimo inicialmente proposto por Ferreira (2013). A Tabela 4 apresenta o

Cenário 2 .

Figura 3 – Roteiros


Tabela 4 – Cenário 2

PLF Prática da

ABC

S.A. T&B Ótimo

PCV S.A. Savings S.A. Savings

Segunda 89 53 58 96 109,43 70

Terça 114 75 79 71,40 75,4 98,43

Quarta 136 89 101 66 66 71,4

Quinta 156 102 107 77 88 89

Sexta 120 105 103 109 111 80

Total: 615 424 448 419,4 449,83 408,83


A partir da Tabela 4 verifica-se que o melhor resultado também foi o terceiro resultado

parcial, referente a combinação da H T&B com a MH S.A com uma aproximação de 2,6% em

relação ao resultado ótimo. O pior desempenho foi da combinação da H T&B com a H

Savings de C&W com 10% acima do resultado ótimo. Figura 4 apresenta a solução atual da

ABC, o melhor roteiro H e MH e o roteiro ótimo.

Figura 4 – Roteiros



14


Em relação as práticas da ABC, a melhor combinação H e MH proporcionou uma otimização

de 31,8% em relação ao tempo de trajeto do motoboy. Já o resultado ótimo proporcionou

33,5% de otimização.

5. Considerações Finais

Este trabalho, que dá continuidade ao trabalho desenvolvido por Ferreira (2013), aborda a

otimização de um problema real, mais especificamente, de entrega de mercadorias por uma

empresa de motoboys. O objetivo do trabalho é utilizar técnicas exatas, H e MH,

comparativamente, para solucionar a formação de agrupamentos dos pontos de demanda

envolvidos (PLF) e, na sequencia, formar os roteiros de entrega dentro de cada agrupamento

(PCV), a fim de demonstrar a sua viabilidade.

As H e as MH aqui abordadas apresentaram um resultado muito satisfatório em relação à

proximidade com a solução ótima e em relação ao tempo computacional. O mais importante é

enfatizar que esta metodologia não é aplicável apenas ao nível estratégico da organização,

mas também é extremamente útil em outros níveis, como neste caso, a decisão sobre as ações

operacionais. Em trabalhos futuros pode-se utilizar outros procedimentos H e MH.

Agradecimentos: à CAPES e a Fundação Araucária pela bolsa concedida.

REFERÊNCIAS

ALEM, Douglas; TOSO, Eli Angela V. Effective location models for sorting recyclables in public management.

European Journal of Operational Research, Vol. 234, p. 839-860, 2014.

ARENALES, Marcos; ARMENTANO, Vinícius; MORABITO, Reinaldo; YANESSE, Horaccio. Pesquisa

Operacional. Rio de Janeiro: Elsevier, 2007.



15

BATTARRA, Maria; PESSOA, Artur. Alves; SUBRAMANIAN, Anand; UCHOA, Eduardo. Exact algorithms

for the traveling salesman problem with draft limits. European Journal of Operational Research. Vol. 235,

p.115–128, 2014.

CARVALHO, Carolina Correia de. Otimização dinâmica da logística de distribuição de produtos

alimentícios refrigerados e congelados. 254 f. Tese (Doutorado) - Faculdade de Engenharia Civil, Arquitetura

e Urbanismo, Universidade Estadual de Campinas, Campinas, 2013.

COLIN, Emerson. Pesquisa operacional: 170 aplicações em estratégia, finanças, logística, produção, marketing

e vendas. Rio de Janeiro: LTC, 2007

DETRO, Silvana Pereira. Otimização na localização e na capacidade de armazenamento de soja e milho

para o estado do Paraná. 112 f. Dissertação (Mestrado) - Programa de Pós-Graduação em Engenharia de

Produção e Sistemas. Pontifícia Universidade Católica do Paraná, Curitiba, 2013.

FERREIRA, Júlio César. Otimização do processo operacional de uma empresa de transportes rápidos. 63 f.

Trabalho de Conclusão de Curso (Engenharia de Produção) - Pontifícia Universidade Católica do Paraná,

Curitiba, 2013.

FERREIRA, Júlio César; STEINER, Maria Teresinha Arns. Otimização do processo operacional de uma

empresa de transportes rápidos. XXXIV Encontro Nacional de Engenharia de Produção, Curitiba (PR), out.

2014.

GANDOLPHO, André Alves; PIZZOLATO, Nélio. Técnicas de Otimização. Rio de Janeiro: LTC, 2009.

KHAMJAN, S; KHAMJAN, W; PATHUMNAKUL, S. Determination of the locations and capacities of sugar

cane loading stations in Tailand. Computers & Industrial Engineering, Vol. 63, p.663-674, 2013.

LOPES, Heitor Silveiro; RODRIGUES, Luiz Carlos de Abreu; STEINER, Maria Teresinha Arns. Meta-

Heurísticas em Pesquisa Operacional. 1ª Edição. Curitiba, PR: Omnipax, 2013.

LORENA, Luiz Antonio Nogueira; MAURI, Geraldo Regis; OLIVEIRA, Rudinei Martins de. Clustering Search

for the Berth Allocation Problem. Expert Systems with Applications, Vol. 39, p. 5499-5505, 2012.

TÁVORA, Rogério Carvalho Mendes. Grupos de visitação na AMAN:um estudo de caso do problema do

caixeiro viajante. 107 f. Dissertação (Mestrado) - Instituto de Matemática, Estatística e Computação Científica,

Universidade Estadual de Campinas, Campinas, 2011.

Documents

ABORDAGEM HEURÍSTICA E META- HEURÍSTICA NA …abepro.org.br/biblioteca/TN_STO_211_250_26415.pdf · de trajeto do motoboy. ... As prestações de serviço ofertadas pela empresa