ABORDAGEM HEURÍSTICA E META-
HEURÍSTICA NA OTIMIZAÇÃO DO
PROCESSO OPERACIONAL DE UMA
EMPRESA DE TRANSPORTES RÁPIDOS
JULIO CESAR FERREIRA (PUCPR)
Maria Teresinha Arns Steiner (PUCPR)
Mariana de Siqueira Guersola (PUCPR)
Osiris Canciglieri Junior (PUCPR)
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)
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.
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
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.
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
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.
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).
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.
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;
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.
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
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.
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
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.
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
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.
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).
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.
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
Fonte: Ferreira (2013).
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.
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
Fonte: Ferreira (2013).
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
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.
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
Fonte: Ferreira (2013).
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
Fonte: Ferreira (2013).
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
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.
14
Fonte: Ferreira (2013).
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.
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.
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.