UNIVERSIDADE FEDERAL DO PARANÁ ALEXANDRE CHECOLI …

1

UNIVERSIDADE FEDERAL DO PARANÁ

ALEXANDRE CHECOLI CHOUEIRI

CURITIBA

2018

2

ALEXANDRE CHECOLI CHOUEIRI

Dissertação de Mestrado apresentada ao Programa

de Pós-Graduação em Métodos Numéricos em

Engenharia, Setor de Tecnologia, Universidade

Federal do Paraná, como requisito parcial à

obtenção do título de Mestre em Métodos

Numéricos.

Orientador: Prof. Dr. Cassius Tadeu Scarpin

Coorientador: Prof. Dr. Gustavo Valentim Loch

CURITIBA

2018

Was erschrickst du deshalb? – Aber es ist mit dem Menschen wie mit dem Baume. Je mehr er hinauf in die Höhe und Helle will, um so stärker streben seine Wurzeln erdwärts, abwärts, ins Dunkle, Tiefe – ins Böse (Zarathustras)

RESUMO

Neste trabalho apresenta-se uma nova heurística para o Problema de

Roteirização para um Único Operador (“Single Picker Routing Problem”), abordando

características complexas de problemas reais. Este problema consiste em determinar

a menor rota a ser realizada, dentro de um armazém, de forma a coletar - manualmente,

todas as caixas (ou itens) de um pedido. Os trabalhos na literatura que tratam sobre o

tema, o abordam considerando somente a distância percorrida em uma rota. Na revisão

da literatura realizada, não foi encontrado nenhum trabalho que apresente uma

abordagem heurística que considere restrições de empilhamento máximo no

carregamento em uma rota, integrado ao roteamento e a política LIFO na sequência de

coleta. Deste modo, as heurísticas propostas abordam características e restrições

reais, como o posicionamento das caixas nos paletes, o sequenciamento de coleta e a

distância percorrida, as restrições de empilhamento máximo foram tratadas com uma

abordagem recursiva e divisão e conquista do problema, junto a uma estrutura em

árvore. As heurísticas desenvolvidas foram aplicadas ao problema de carregamento e

ao problema de carregamento e roteamento integrado. Foram testadas em um variado

conjuntos de dados, considerando diversos cenários e estratégias. As heurísticas de

carregamento obtiveram um desempenho aceitável, pois foram processadas de forma

rápida (menos de 1 segundo) e eficiente em relação ao volume total ocupado, com

média de 85% de ocupação, considerando somente as restrições de carregamento

simples, e a 64% de ocupação com todas as restrições práticas. Todas as soluções

encontradas nas instâncias de carregamento e roteamento foram melhoradas por uma

heurística de melhoria, também proposta neste trabalho.

Palavras-chave: Roteamento em Centros de Distribuição, Restrições práticas,

Carregamento de contêineres (ou de paletes).

ABSTRACT

In this work, a heuristic approach for the single picker routing problem is

proposed, along with more complex and practical constraints. This is the problem of

determining the least cost tour for a warehouse worker, so that he can collect all item in

a request. Literature on the theme shows that the problem is mostly considered only

regarding the routes. The proposed heuristic deals with much more realistic

considerations, such as pallet volume capacity, boxe´s positions inside of it and

maximum stacking, considered here as box maximum weight, so far, it is unknown of a

work that takes into account routing and stacking of the cargo, along with an LIFO policy.

Both loading and routing heuristics were extensively tested in a variety of scenario and

strategy. The loading heuristic have performed well, achieving the results in a small

period (less than one second) and effective regarding the total volume on those that

considered all restrictions. For the routing and loading heuristic instances, all of them

were optimized regarding their initial solution by a proposed improvement heuristic. Up

to now, there is no knowledge of heuristic that perform the routing and also takes into

account maximum stacking in their restrictions.

Keywords:.Warehouse Routing, Practical Restrictions, Container-Loading.

LISTA DE FIGURAS

FIGURA 1 – FLUXO DE ATIVIDADES EM CD´s ........................................................ 17

FIGURA 2 – TIPOS DE PICKING POR PEDIDO ........................................................ 18

FIGURA 3 – NÍVEIS ALTO E BAIXO EM UM CD........................................................ 19

FIGURA 4 – REPRESENTAÇÃO DE UM CD: FÍSICA E POR GRAFOS .................... 20

FIGURA 5 – CENTRO DE DISTRIBUIÇÃO ................................................................ 21

FIGURA 6 – MEDIDAS UTILIZADAS NO CD ............................................................. 21

FIGURA 7 – ESPAÇO CENTRADO NA ORIGEM....................................................... 23

FIGURA 8 – RESTRIÇÕES DE EMPILHAMENTO MÁXIMO ...................................... 24

FIGURA 9 –TIPOS DE ROTAÇÃO DAS CAIXAS ....................................................... 25

FIGURA 10 – DUPLICAÇÃO DE ARESTA ................................................................. 27

FIGURA 11 – SUBSTITUIÇÃO DE ARESTA .............................................................. 28

FIGURA 12 – GRAFO BIPARTIDO ............................................................................. 32

FIGURA 13 – GRAFO E SUBGRAFO ......................................................................... 33

FIGURA 14 – NÍVEIS DE UMA ÁRVORE ................................................................... 34

FIGURA 15 – MÉTODO HÚNGARO: CHRISTOFIDES .............................................. 35

FIGURA 16 – MÉTODO HÚNGARO: PAPADIMITRIOU ............................................. 36

FIGURA 17 – TIPOLOGIA DE MÉTODOS DE RESOLUÇÃO .................................... 39

FIGURA 18 – ABORDAGEM DO TSP VIA CONCEITO DE ÁRVORE ........................ 43

FIGURA 19 – MÉTODOLOGIA HEURÍSTICA CHRISTOFIDES 3/2 ........................... 44

FIGURA 20 – HEURÍSTICA VIZINHO MAIS PRÓXIMO ............................................. 45

FIGURA 21 – HEURÍSTICA K-VIZINHO MAIS PRÓXIMO .......................................... 45

FIGURA 22 – MOVIMENTO 3-OPT ............................................................................ 46

FIGURA 23 – ESCOLHA DOS CONJUNTOS X E Y ................................................... 47

FIGURA 24 – HEURÍSTICA S SHAPE ........................................................................ 50

FIGURA 25 – HEURISTICA DO RETORNO ............................................................... 51

FIGURA 26 – HEURISTICA DO PONTOS MÉDIO ..................................................... 52

FIGURA 27 – HEURISTICA DO MAIOR GAP ............................................................. 52

FIGURA 28 – HEURISTICA COMBINADA .................................................................. 53

FIGURA 29 – DISCRETIZAÇÃO DE PONTOS CORREDOR ..................................... 54

FIGURA 30 – COMPARAÇÃO MÉTODOS DE RESOLUÇÃO DESIGNAÇÃO ........... 56

FIGURA 31 – ALTERAÇÃO 1 ..................................................................................... 57

FIGURA 32 – ALTERAÇÃO 2 ..................................................................................... 58

FIGURA 33 – ROTA INVIÁVEL SPRP ........................................................................ 59

FIGURA 34 – TIPOS DE VIOLAÇÕES ........................................................................ 62

FIGURA 35 – RELIGAÇÕES DE ROTA ...................................................................... 63

FIGURA 36 – ARCOS A SEREM REMOVIDOS ......................................................... 65

FIGURA 37 – RELIGAÇÃO DE ARCOS ..................................................................... 65

FIGURA 38 – INSERÇÃO DE ITEM NO OBJETO ...................................................... 67

FIGURA 39 – GERAÇÃO DE ESPAÇOS .................................................................... 68

FIGURA 40 – FLUXOGRAMA ROTINA EMPACOTAMENTO .................................... 69

FIGURA 41 – TIPOS DE ESPAÇOS ........................................................................... 71

FIGURA 42 – EXPANSÃO ARVORE DE CARREGAMENTO ..................................... 72

FIGURA 43 – EXPANSÃO ÁRVORE EMPILHAMENTO MÁXIMO ............................. 73

FIGURA 44 – FLUXOGRAMA ROTINA FACTIBILIZA ................................................ 76

FIGURA 45 – VOLUME OCUPADO POR ROTAS ...................................................... 77

FIGURA 46 – ESCOAMENTO DE ROTAS MENOR ................................................... 78

FIGURA 47 – VISUALIZAÇÃO DA HEURISTICA DE CORREÇÃO DE ROTAS ........ 81

FIGURA 48 – GRÁFICO DE TEMPOS RESOLUÇÃO TSP ÁRVORES ...................... 84

FIGURA 49 – VISUALIZAÇÃO DE CARGA 1 ............................................................. 87

FIGURA 50 – VISUALIZAÇÃO DE CARGA 2 ............................................................. 88

FIGURA 51 – GRAFICO APROVEITAMENTO CARREGAMENTO MÉDIO ............... 90

FIGURA 52 – INTERVALOS COM 95% DE CONFIANÇA PARA COMPARAÇÃO DE

MÉDIAS.................................................................................................. 91

FIGURA 53 – APROVEITAMENTO MÉDIO VOLUME PALETE ................................. 92

FIGURA 54 – PERCENTUAL DE MELHORIA ............................................................ 94

FIGURA 55 – GRÁFICO TEMPOS DE RESOLUÇÃO HEP ........................................ 96

FIGURA 56 – GRÁFICO TEMPOS DE RESOLUÇÃO HEP ........................................ 96

FIGURA 57 – EMPILHAMENTO MÁXIMO - PRESSÃO ............................................. 99

LISTA DE TABELAS

TABELA 1 – METODOLOGIA LIN-KERNIGHAN ........................................................ 47

TABELA 2 – COMPARAÇÃO DE MÉTODOS DE RESOLUÇÃO PARA O AP ........... 55

TABELA 3 – RESTRIÇÕES VIOLAÇÕES ................................................................... 60

TABELA 4 – PSEUDOCÓDIGO DA HEURÍSTICA DE CORREÇÃO DE ROTAS ....... 60

TABELA 5 – LISTAS DE RESTRIÇÃO ........................................................................ 63

TABELA 6 – LISTA DE VIOLAÇÕES .......................................................................... 63

TABELA 7 – PSEUDOCÓDIGO EXPANDE_NO ......................................................... 70

TABELA 8 – PSEUDOCODIGO FUNÇÃO DE FACTIBILIZAÇÃO .............................. 75

TABELA 9 – ESCOAMENTO MENOR ........................................................................ 77

TABELA 10 – PSEUDOCÓDIGO DA HEURISTICA HEP ........................................... 79

TABELA 11 – RESULTADO HEURISTICA DE CORREÇÃO ...................................... 83

TABELA 12 – TEMPOS RESOLUÇÃO TSP EM ARVORE ......................................... 83

TABELA 13 – RESULTADOS HEURISTICA DE CORREÇÕES ................................. 84

TABELA 14 – RESULTADOS MÉDIA CARREGAMENTO .......................................... 89

TABELA 15 – APROVEITAMENTO MÉDIO VOLUME PALETE ................................. 92

TABELA 16 – PORCENTAGEM DE MELHORIA POR ESTRATEGIAS ..................... 94

TABELA 17 – MÉDIAS DE TEMPOS RESOLUÇÃO HEP .......................................... 95

LISTA DE SIGLAS

SPRP – Single Picker Routing Problem

TSP – Traveling Salesman Problem

AP – Assignment Problem

DFJ – Dantzig, Fulkerson, Johnson

CD – Centro de Distribuição

ANOVA – Análise de Variância

LIFO – Last In First Out

SUMÁRIO 1 INTRODUÇÃO ........................................................................................ 12 1.1 OBJETIVOS.............................................................................................. 13 1.1.1 Objetivo Geral .......................................................................................... 13 1.1.2 Objetivos Específicos .............................................................................. 13 1.2 RELEVÂNCIA E IMPORTÂNCIA.............................................................. 13 1.3 LIMITAÇÕES.............................................................................................15 1.4 ESTRUTURA............................................................................................. 15 2 DESCRIÇÃO DO PROBLEMA ............................................................... 16 2.1 ATIVIDADE DE PICKING (ORDER PICKING)……………………………. 17 2.2 SINGLE PICKER ROUTING PROBLEM (SPRP)…………………………. 20 2.3 O PROCESSO DE PICKING CAPACITADO (CSPRP)............................ 22 3 REVISÃO DE LITERATURA ................................................................... 27 3.1 TRABALHOS CORRELATOS.................................................................. 27 3.2 ROTEIRIZAÇÃO COM CARREGAMENTO............................................. 29 3.3 FUNDAMENTAÇÃO TEÓRICA............................................................... 31 3.3.1 CONCEITOS DE GRAFOS ..................................................................... 31 3.3.2 PROBLEMA DE DESIGNAÇÃO (AP) ...................................................... 34 3.3.3 O PROBLEMA DO CAIXEIRO VIAJANTE .............................................. 37 3.3.4 MÉTODOS DE ROTEIRIZAÇÃO EM CD´s ............................................. 50 4 IMPLEMENTAÇÕES ............................................................................... 55 4.1 COMPARAÇÕES DE IMPLEMENTAÇÕES DO MÉTODO HÚNGARO.. 55 4.2 MÉTODO DE EXPLORAÇÃO DA ÁRVORE............................................ 56 4.3 HEURÍSTICA DE CORREÇÃO DE ROTAS EM CD................................ 58 4.3.1 Descrição da heurística ........................................................................... 59 4.4 HEURÍSTICA DE EMPACOTAMENTO.................................................... 66 4.4.1 Descrição da heurística ........................................................................... 66 4.5 HEURÍSTICA DE ESCOAMENTO DE PONTOS (HEP). 74 5 RESULTADOS E DISCUSSÃO .............................................................. 81 5.1 HEURÍSTICA DE CORREÇÃO DE ROTAS EM CD................................ 81 5.2 HEURÍSTICA DE EMPACOTAMENTO................................................... 87 5.3 HEURÍSTICA DE ESCOAMENTO DE PONTOS (HEP).......................... 93 6 CONSLUSÕES ........................................................................................ 97 REFERÊNCIAS ......................................................................................................... 100

12

1 INTRODUÇÃO

A área de Pesquisa Operacional (PO) surgiu em 1934 na Inglaterra, quando da

invenção do radar. Em 1936 é criada a Estação de Pesquisa Manor Bawdsey para

estudar como a tecnologia do radar poderia ser utilizada para interceptar aviões de

guerra inimigos. Com o início da segunda guerra mundial e a necessidade de se

trabalhar com recursos escassos, os estudos no campo da PO aumentaram,

estendendo-se às atividades operacionais da guerra, como manutenção de veículos,

decisões de quais aviões deveriam ser utilizados, etc. Daí em diante, não demorou até

que a atuação da PO entrasse no escopo das indústrias (ARENALES et al., 2007).

As atividades de Logística desempenham o gerenciamento estratégico da

compra, transporte e armazenagem de matérias-primas e produtos acabados, de

maneira que a lucratividade seja maximizada por meio de entregas de encomendas

com menor custo associado (CHRISTOPHER, 2010). Os armazéns são responsáveis

por grande parte dos custos logísticos, de acordo com (KEARNEY, A, 2014), atividades

em armazém foram responsáveis por 20% dos custos logísticos em 2003.

O presente trabalho tem por objetivo o estudo das operações logísticas dentro

de armazéns e centros de distribuição (CD), mais especificamente às atividades de

roteirização de picking nos CD´s (determinar a melhor rota para que seja realizada a

coleta dos itens de um pedido das prateleiras até as docas de carregamento). O

problema da roteirização em armazéns é conhecido como Single Picker Routing

Problem (SPRP) e pode ser resolvido por modelos clássicos de Programação Inteira

do problema do caixeiro viajante (Traveling Salesman Problem – TSP) (DANTZIG et al.,

1954).

Além de se determinar uma rota a ser realizada por um operador em um CD,

também deve-se levar em consideração algumas restrições práticas, tal como a

disposição dos itens nos paletes de coleta, e até mesmo se um item pode ser inserido

acima de outro (restrição de empilhamento máximo), sendo esta a maior contribuição

do trabalho. Os modelos e métodos existentes para resolução do SPRP consideram

somente a roteirização como um fator de importância a ser considerado.

O presente trabalho visa preencher esta lacuna no estudo de roteirizações em

armazéns incluindo informações dos itens a serem coletados, tais como dimensões e

13

carga máxima permitida, de forma a estruturar um método heurístico que otimize tanto

as rotas a serem percorridas por um operador como o posicionamento dos itens nos

paletes quando da coleta e, ainda, a verificação de restrições de empilhamento máximo

desses itens.

1.1 OBJETIVOS

1.1.1 Objetivo Geral

Propor e avaliar métodos heurísticos que consideram as restrições práticas de

roteirização, empilhamento máximo e política LIFO (Last In First Out) de carregamento

para o Capacitated Single Picker Routing Problem (CSPRP).

1.1.2 Objetivos Específicos

Para que se possa atingir o objetivo geral, os seguintes objetivos específicos

devem ser seguidos:

Implementar os métodos de resolução para o problema de designação.

Implementar um método de resolução em árvores para TSP.

Adaptar a lógica de redução de pontos em um armazém de (SCHOLZ et

al., 2016) em um método que não dependa de solvers comerciais.

Combinar o método de resolução em árvores à lógica de redução de

pontos em uma nova heurística.

Avaliar a aplicabilidade da heurística por meio de testes computacionais.

Adaptar a heurística de roteamento para o carregamento tridimensional

do palete.

Inserir restrições de empilhamento máximo na heurística proposta e

avaliar seu desempenho.

1.2 RELEVÂNCIA E IMPORTÂNCIA

Com o aumento da capacidade de processamento dos computadores, muitos

problemas da área de otimização combinatória são resolvidos unicamente por meio de

14

solvers comerciais. Assim como também são aplicadas heurísticas híbridas

(Matheuristics), que interoperacionalizam heurísticas e/ou meta-heurísticas com

métodos exatos ou de relaxação que resolvem modelos matemáticos de programação

linear.

Apesar destes solvers satisfazerem parte das necessidades acadêmicas de

otimização linear, sendo muito eficientes e liberados sob licença gratuita para

estudantes, o mesmo não pode ser dito em se tratando de aplicações reais nas

empresas. Estas, independente de seu porte, podem ser cobradas um valor que pode

parecer alto de início (apesar das reduções que o mesmo proporciona a médio prazo),

fato que muitas vezes influencia negativamente a tomada de decisão, por parte da

empresa, de obter o solver.

As heurísticas, por outro lado, podem ser desenvolvidas e implementadas por

qualquer profissional de programação que possua uma linguagem com compilador ou

mesmo, por exemplo, a linguagem de programação presente em todos os aplicativos

da Microsoft (Visual Basic for Application), os quais são líderes de mercado de

softwares, tornando-as muito mais atrativas no meio empresarial. Desta forma, o

gerente de logística ou mesmo o responsável pelo armazém tem a possibilidade de

entender os métodos propostos neste trabalho e implementa-los.

A atividade mais onerosa em um armazém é o picking (WHITE J et al., 2010) –

coleta de itens para um pedido e, devido a isso, parte da literatura dedica-se a pesquisar

as características que afetam essa atividade e o seu roteamento. O roteamento trata

da sequência de itens que o operador/separador deverá seguir ao realizar a coleta de

um determinado pedido, quão menor for a distância total da rota, menor o tempo de

picking.

As heurísticas clássicas existentes na literatura sobre o roteamento em

depósitos (s-shape, retorno, ponto-médio, combinada) tem uma complexidade

computacional baixa. Estas são desenvolvidas de forma que possam se apropriar da

forma retangular dos armazéns para que menos pontos de coleta sejam considerados.

O problema destes métodos se dá quando características e restrições mais práticas

precisam ser inseridas, como por exemplo o empilhamento máximo e/ou o

sequenciamento do carregamento respeitando a política LIFO de carga/descarga no

pallet. Se por um lado ganham em velocidade de obtenção de resposta, por outro

perdem ao ficarem muito restritas e não realísticas, de forma que uma heurística que

resolva o CSPRP

15

1.3 LIMITAÇÕES

No presente trabalho foram considerados somente centros de distribuição com

Layout de bloco único, e ainda, o modelo base para a heurística de roteirização

(SCHOLZ et al., 2016) não foi implementado, devido aos resultados dos testes

computacionais da heurística proposta.

1.4 ESTRUTURA

O presente trabalho está organizado na forma de capítulos, sendo os principais

tópicos de cada um apresentado abaixo:

2 – Contextualização e descrição do problema original (SPRP) junto ao novo

problema proposto CSPRP (Capacitated Single Picker Routing Problem)

3 – Trabalhos correlatos sobre o SPRP e sobre carregamento com roteirização,

junto a toda base teórica utilizado no trabalho. Conceitos de grafos, problema de

designação e TSP são abordados com maior minúcia. Também são apresentadas 5

heurísticas de roteirização em armazéns e o modelo matemático proposto por

(SCHOLZ et al., 2016).

4 – O capitulo 4 apresenta a descrição de todas as heurísticas implementadas,

uma para correção de rotas, uma para carregamento e uma para roteirização e

carregamento em armazéns.

5 – Resultados computacionais das heurísticas propostas e análise dos mesmos

são apresentados neste capítulo.

6 – Apresenta-se as conclusões deste trabalho e sugestões para trabalhos

futuros sobre o tema.

16

2 DESCRIÇÃO DO PROBLEMA

Os armazéns cumprem um papel fundamental em diferentes níveis de uma

cadeia de suprimentos. De acordo com (KEARNEY, A, 2014), atividades em armazém

foram responsáveis por 20% dos custos logísticos em 2003. São geralmente utilizados

para o armazenamento de materiais entre pontos de origem e destino de mercadorias

(KOSTER, DE et al., 2007).

Se além de realizar as atividades de armazenagem também é do escopo do

armazém o transporte dos materiais estocados, o mesmo recebe o nome de Centro de

distribuição (CD), utilizado a partir de agora até o fim deste estudo.

Os estudos de (LAMBERT, D et al., 1998) mostram que existem mais de

750.000,00 CD´s no mundo, desde centros com alto nível de gerenciamento até

aqueles de pequeno porte.

Dentre as principais atividades em CD´s, estão: recebimento, armazenamento

dos itens, separação de picking e expedição.

O recebimento inclui as atividades de transbordo dos produtos que chegam por

algum meio de transporte ao CD, verificação de possíveis inconsistências entre o

material entregue e o pedido bem como a atualização do inventário. Após o

recebimento, é necessário realizar a armazenagem dos itens para seus devidos locais.

Nesta fase, pode-se fazer necessário o reprocessamento de alguns materiais

(reembalagem e/ou inserção em caixas padronizadas). A separação de picking,

doravante chamado de picking, consiste na obtenção da quantia exata de determinados

produtos para um conjunto de pedidos de clientes, colhidos em locais específicos para

tal atividade. A expedição é a acumulação de itens referentes a pedidos individuais

(clientes), o carregamento aos devidos caminhões e a liberação da carga com toda a

documentação necessária.

De todas as atividades de um CD, o picking é a mais onerosa em CD´s que se

utilizam da coleta manual como método primário de coleta. Estima-se que de todas as

atividades desempenhadas no CD, o picking é responsável por mais de 55% dos custos

totais (KOSTER, DE et al., 2007).

É mostrado na FIGURA 1 o fluxo de atividades em um CD.

17

FIGURA 1 – FLUXO DE ATIVIDADES EM CD´s

FONTE: Adaptado de (TOMPKINS, J et al., 2010)

Para que o gerenciamento dos CD´s possam ser realizados de forma efetiva,

os gestores precisam saber quando e como as atividades devem ser realizadas e a

melhor forma de utilizar os recursos disponíveis (maquinários e funcionários). Para o

auxílio nestas tomadas de decisão, frequentemente são utilizados softwares comerciais

específicos para o gerenciamento de CD, o mais conhecido sendo o WMS (Warehouse

Management System ou Sistema de Gerenciamento de Depósitos) (SCARPIN, 2012).

Embora os WMS´s comerciais supram grande parte das necessidades

gerenciais de um CD em relação aos produtos, tais como: quantidades, localizações,

volumes, tipos de embalagem e ressuprimento de picking, algumas mais complexam

não fazem parte do escopo de um WMS (SCARPIN, 2012). Frequentemente os

gestores de CD´s devem se preocupar em decidir como seus funcionários realizarão a

separação dos itens do picking para o carregamento de um caminhão, qual o melhor

posicionamento dos paletes dentro do caminhão, levando em consideração a ordem de

entrega dos pedidos e a política LIFO (Last In First Out), dentre outras decisões

operacionais.

2.1 ATIVIDADE DE PICKING (ORDER PICKING)

18

O processo de picking de pedidos consiste em separar os itens do pedido de

um cliente. Os pedidos dos clientes consistem de linhas de pedido agrupadas, em que

cada linha contém um item (stock keeping unit - SKU) e uma certa quantidade do

mesmo. Existem diversas formas de se realizar o picking do pedido, na FIGURA 2 uma

diferenciação destas formas é mostrada de acordo com o tipo de operador que realiza

a coleta, se humano ou automático com máquinas.

FIGURA 2 – TIPOS DE PICKING POR PEDIDO

FONTE: Adaptado de (KOSTER, DE et al., 2007)

Picker-to-parts: São aqueles em que o operador anda pelos corredores

coletando itens e são divididos em dois grupos, de nível baixo e de nível alto. Nos

corredores de nível baixo os operadores percorrem coletando os SKU´s somente das

prateleiras mais próximas ao chão. Já nos sistemas de nível alto, o operador percorre

os corredores com uma empilhadeira e coleta os itens das prateleiras de níveis mais

altos, como mostrado na FIGURA 3. (KOSTER, DE et al., 2007)

19

FIGURA 3 – NÍVEIS ALTO E BAIXO EM UM CD

FONTE: O AUTOR (2018)

Os processos picker-to-parts de nível baixo são ainda separados em três

grupos: discreto, por lotes e por zonas.

No picking discreto, o operador separa todos os SKU´s de um único pedido,

para em seguida começar um novo. Se por um lado a integridade do pedido é mantida

pois será coletado por completo, por outro o operador pode gastar mais tempo

percorrendo rotas de coleta mais longas. No picking por lotes, o operador recebe um

lote de pedidos agrupados e é responsável pela coleta de todos os itens do lote em

uma viagem de separação. Já no picking por zonas, a cada operador é atribuído uma

parte do CD (como por exemplo algum corredor), sendo que todos os pedidos com itens

a serem coletados em uma determinada parte, serão de responsabilidade de coleta do

operador atribuído àquela parte.

Parts-to-picker: Nestes sistemas são utilizados guindastes para coletas –

sistemas automatizados de armazenagem e coleta (automated storage and retrieval

systems – AS/RS), em que os guindastes são presos aos corredores e coletam as

unidades de armazenagem completas (paletes), levando-as aos locais de picking. Com

o palete no chão, o operador realiza a coleta da quantidade de SKU´s do pedido e o

palete é recolocado nas prateleiras em seguida.

Put: Primeiramente é realizada uma pré-coleta dos itens com maior rotatividade

(geralmente em CD´s com baixa variabilidade de produtos), para que estes sejam

colocados em contendores à disposição dos operários. De acordo com os pedidos, os

20

operários coletam os itens dos contendores e colocam (“put”) em áreas separadas

especificas para cada pedido.

Automated: Somente são utilizados em casos especiais (como em itens com

muito valor agregado, muito pequenos ou delicados).

Neste trabalho, o sistema picker-to-parts de nível baixo é abordado, mais

especificamente os métodos de roteirização utilizados quando da coleta dos SKU´s de

um pedido, chamado de problema de roteirização de picker único (Single-Picker

Routing-Problem – SPRP).

2.2 SINGLE PICKER ROUTING PROBLEM (SPRP)

Os centros de distribuições (CD) tratados neste trabalho são os de bloco único,

sendo este o padrão da literatura ao se tratar da roteirização em CD´s. Na FIGURA 4 é

mostrado um CD em sua vista superior, em que os quadrados pretos representam os

SKU (a partir de agora chamados de itens) a serem coletados, junto à sua

representação via grafos.

FIGURA 4 – REPRESENTAÇÃO DE UM CD: FÍSICA E POR GRAFOS

FONTE: O autor (2018).

A FIGURA 5 representa um CD com 5 corredores de coleta e dois corredores

transversais: corredor transversal inferior (CTI) e corredor transversal superior (CTS).

O ponto inicial para início da coleta dos itens se localiza no canto inferior esquerdo, em

frente ao primeiro corredor de coleta. A distância entre dois locais de coleta, situados

no mesmo corredor e consecutivos entre si, é unitária. A distância entre corredores

21

consecutivos é de 5 unidades de medida (um), a distância ao sair de um corredor de

coleta e entrar em um corredor transversal é de 1(um), como mostrado na FIGURA 6. FIGURA 5 – CENTRO DE DISTRIBUIÇÃO


FIGURA 6 – MEDIDAS UTILIZADAS NO CD


A numeração dos itens a serem coletados é sequencial e de incremento unitário

para cada corredor, iniciando no CTI até chegar no CTS, do corredor mais à esquerda

até o mais à direita do CD (na FIGURA 4 por exemplo, embora os pontos de coletas

estejam nas prateleiras 3 e 7, são referentes aos pontos 1 e 2, respectivamente),já os

arcos de um determinado corredor são representados pelo conjunto (número do

corredor-(1º ponto, 2º ponto)) (o arco ligando o ponto 1 ao ponto 2 na FIGURA 4 é então

(1-(1,2)).

22

Neste trabalho considerou-se um CD com 10 corredores e 45 localizações de

produtos em cada lado do corredor, da mesma forma considerada no trabalho de

(HENN; WÄSCHER, 2012) .

Os itens a serem coletados são posicionados no centro de cada prateleira, de

forma que, se existem itens em ambas as prateleiras de uma posição (esquerda e

direita), o local de coleta é o mesmo.

As distâncias em um CD não são todas euclidianas, uma vez que itens em

corredores diferentes possuem prateleiras separando-os, nestes casos é calculada a

distância Manhattan. Para se calcular a distância entre 2 pontos no CD,

existem 3 possibilidades variando de acordo com as posições de e , mostradas a

seguir:

ou é o ponto de início da rota:

A distância entre os pontos é a distância entre e passando pelo

CTI.

e estão localizados em corredores diferentes:

Duas distâncias devem ser consideradas, de a passando pelo

CTI, e de a passando pelo CTS, a menor das duas é considerada na

matriz de distâncias.

e estão localizados no mesmo corredor:

A distância é simplesmente a diferença, em módulo, de posicionamento entre

os dois pontos no corredor.

O SPRP consiste em, dado um CD de bloco único e uma lista de posições com

localizações de itens a serem coletados, encontrar a rota de menor distância total, de

tal forma que, saindo de um ponto inicial, todos os locais com itens sejam visitados uma

única vez.

2.3 O PROCESSO DE PICKING CAPACITADO (CSPRP)

Embora os modelos e métodos para o SPRP supram uma grande demanda

nos CD´s, pode-se dizer que os mesmos ainda não consideram características práticas

reais que influenciam de forma direta a roteirização que será realizada, como por

exemplo, a verificação de volumes e posicionamentos dos SKU´s nos paletes.

23

Pode acontecer de uma rota satisfazer todos os critérios do SPRP e na prática

ser inviável pelo carregamento em um único palete, podendo ser impossível alocar

todos os SKU´s ditados na sequência da rota seja por volume ou por peso ou, até

mesmo, pela resistência dos itens colocados mais abaixo no palete. Neste trabalho é

abordado o Problema de Roteirização de Picking Capacitado (CSPRP).

Considera-se que cada SKU (a partir de agora chamado de caixa ou item) é um

hexaedro com todas as faces retangulares (uma caixa), e dimensões ) nos eixos

cartesianos, o canto inferior esquerdo frontal da caixa é localizado em

Da mesma forma que as caixas, os espaços vazios também são hexaedros

com todas as faces retangulares e também são representados por suas dimensões

e localização ) do canto inferior frontal esquerdo. A FIGURA 7

representa um espaço com dimensões e canto inferior esquerdo centrado na

origem (0,0,0).

FIGURA 7 – ESPAÇO CENTRADO NA ORIGEM


Além dos atributos geométricos, cada caixa possui mais 3 atributos : massa

própria, massa máxima e restrições de rotação:

: massa própria: massa total da caixa.

: massa máxima: somatório máximo de massas que a caixa suporta.

24

restrições de rotação: posições para as quais o objeto não pode ser

rotacionado.

Os atributos e dizem respeito à restrição de empilhamento máximo

permitido em uma caixa, como mostrado na FIGURA 8. Supondo que cada caixa

tenha massa de 1 unidade de massa (um.), a face em vermelho está sob efeito de 3

um., a face em amarelo sob 1 um. e as verdes sob nenhuma. Desta forma, supondo

que a massa máxima da caixa com face vermelha seja 3 um., fica proibida a inserção

de qualquer outra caixa acima da mesma, sob pena de violar o empilhamento máximo. FIGURA 8 – RESTRIÇÕES DE EMPILHAMENTO MÁXIMO


O atributo diz respeito a restrições de posicionamento que a caixa possa

ter (por exemplo caixas com restrição de “este lado para cima”). Cada caixa pode ser

rotacionada em no máximo 6 formas diferentes,como mostrado na FIGURA 9:

25

FIGURA 9 –TIPOS DE ROTAÇÃO DAS CAIXAS


Considerando que exista um (no incio é o palete inteiro), uma lista

com com tipos

distintos de caixas, cada uma com suas dimensões X Y e Z e sua massa e massa

máxima m,M, uma sequência com localizações para coleta em um

CD, um lista com quantidades de caixas do tipo para todas

as localizações, e, para cada elemento do conjunto uma sequência de posições

restritas .

O CSPRP consiste em encontrar as um conjunto de rotas (ou mesmo uma) e

para cada rota um conjunto de posições para todos os itens destas rotas, de

tal forma que:

todas as quantidades de itens dos pontos contidos em cada rota, estejam

dentro do O sem sobreposição, e respeitando as restrições de

empilhamento máximo e de posições restritas.

Todos os itens devem estar verticalmente estáveis (a superficie inferior de uma

caixa sempre deve estar completamente apoiada sobre a superficie superior de

outra caixa (ou espaço).

As caixas devem ser posicionadas no palete na ordem em que aparecem na rota

(LIFO), ou seja, ao se coletar itens de um ponto, não se pode retirar uma caixa e

recolocá-la novamente no palete.

O somátorio da distancia de todas as rotas deve ser minimizado

26

Neste capitulo foram definidos os dois problemas base para o desenvolvimento

das heuristicas propostas neste trabalho (SPRP e CSPRP). O CSPRP é uma extensão

do SPRP com restrições práticas de carregamento.

27

3 REVISÃO DE LITERATURA

3.1 TRABALHOS CORRELATOS

O objetivo das políticas de roteirização no SPRP é determinar uma boa

sequência para a realização das coletas de itens em um depósito. Dessa forma, as

políticas de roteirização nada mais são do que casos especiais do TSP com algumas

características especificas que devem ser levadas em consideração.

Diferentemente do TSP clássico, no SPRP nem todos os nós do grafo precisam

ser visitados. No caso da FIGURA 4, somente aqueles em preto precisam fazer parte

da rota final, sendo que os nós em branco representam os pontos de cruzamento entre

corredores. Também é permitido visitar os locais de coleta mais de uma vez, devido as

características físicas da estrutura de um CD. O TSP com essas características é

classificado como o Steiner TSP (STSP) e, para o mesmo, não existe algoritmo em

tempo polinomial que posso resolvê-lo (KOSTER, DE et al., 2007). No entanto, foi

mostrado por (RATLIFF; ROSENTHAL, 1983) que, para o tipo de CD da FIGURA 4,

existe um algoritmo que pode resolver o problema em tempo polinomial em função do

número de corredores e de locais de coleta.

Em (CORNUEJOLS et al., 1985), é mostrado que o algoritmo de

(GOETSCHALCKX; RATLIFF, 1998) pode ser estendido de tal forma que resolva o

STSP em grafos chamados “série-paralelo”. Grafos “serie-paralelo” são todos os grafos

que podem ser obtidos a partir da aplicação recursiva das seguintes regras, partindo

de um grafo inicial com uma aresta e dois vértices:

1 – Duplicar uma aresta (adicionar uma aresta unindo dois vértices já

existentes)

2 – Substituir uma aresta por duas arestas e , em que é um novo

vértice.

As operações 1 e 2 são representadas nas FIGURA 10 e FIGURA 11,

respectivamente

FIGURA 10 – DUPLICAÇÃO DE ARESTA

28


FIGURA 11 – SUBSTITUIÇÃO DE ARESTA


O trabalho de (KOSTER, DE; POORT, VAN DER, 1998) atualiza o algoritmo

de (GOETSCHALCKX; RATLIFF, 1998) para que o mesmo possa ser utilizado em

armazéns que não podem ser modelados como grafos em “série-paralelos” .O algoritmo

de (KOSTER, DE; POORT, VAN DER, 1998) encontra o menor caminho em um grafo

com depósito de item descentralizado, ou seja, os itens coletados nos corredores não

precisam ser levados à doca de expedição (doravante chamado de depot), mas podem

ser deixados nas saídas ou entradas dos corredores.

Como as atividades de picking geralmente precisam ser executadas o mais

rápido possível, uma prática comum entre os gestores da atividade de picking é deixar

de lado as soluções ótimas em função de soluções heurísticas, perdendo em qualidade

da solução, mas agregando valor em economia no tempo de geração das rotas

(KOSTER, DE et al., 2007). Além disso, deve-se notar que não existem, à priori,

algoritmos ótimos para todos tipos de layout de CD´s.

O problema de roteirização do picking pode ser resolvido de diversas formas.

A mais divulgada se faz via programação inteira, por meio de modelos clássicos do

caixeiro viajante (LAPORTE, 1992). Como as estruturas de depósitos são bem

definidas e raramente mutáveis (corredores e prateleiras de coleta), pode-se incorporar

informações a respeito do layout nos métodos de resolução, inclusive nos modelos

matemáticos.

Um modelo de programação inteira que se apropria destas informações é

proposto por (SCHOLZ et al, 2016). Neste estudo, todas as possíveis combinações de

rotas em um corredor são mapeadas, para que em seguida possam ser rastreados os

padrões de passagem entre pontos principais do corredor. Em consequência disto,

29

percebe-se que para os corredores, somente 4 pontos são necessários para que todos

os arcos com produtos sejam visitados (SCHOLZ et al., 2016).

Com essa informação, Scholz et al (2016) desenvolve um novo modelo

matemático para o (SPRP), em que pela primeira vez, ambas restrições e variáveis

crescem proporcionalmente ao número de corredores do depósito e não mais ao

número de itens que devem ser coletados.

A heurística de correção de rotas apresentada neste trabalho, procura adaptar

a idéia de discretização dos pontos em um CD apresentado por Scholz et al (2016). A

Proposta é desenvolver as heurísticas em uma estrutura de resolução que não dependa

de solvers, combinando métodos exatos de resolução do TSP, com uma abordagem

de correção de rotas inviáveis. Em seguida, restrições de cunho mais prático serão

inseridas, para que possa ser considerada a factibilidade do arranjo das caixas nos

paletes bem como o empilhamento máximo das mesmas.

3.2 ROTEIRIZAÇÃO COM CARREGAMENTO

O problema de carregamento de caixas retangulares em paletes foi estudado

por Hodgson (HODGSON, T, 1982), que distingue os problemas em duas categorias:

O Problema de Carregamento de Paletes do Produto (PCPP) e o Problema de

Carregamento de Paletes do Distribuidor (PCPD) .Os dois se diferem na medida em

que no PCPP existe apenas um tipo de caixa e no PCPD as caixas são heterogêneas.

O problema de carregamento de palete é o mesmo dos de carregamento de

contêineres, os quais, quando tratados com a roteirização, tem seu início no Problema

de Roteirização de Veículos Capacitados (Capacitated Vehicle Routing Problem –

CVRP).

A extensão natural do TSP em aplicações reais recai sobre os CVRP. É

assumido um depósito central localizado no vértice 0, sendo que uma frota de

veículos idênticos está disponível e clientes estão localizados nos vértices .

Todos os veículos possuem uma capacidade e todos os clientes possuem uma

demanda . O CVRP busca encontrar um conjunto

de no máximo rotas, cada uma visitando o depósito e um conjunto de clientes, de tal

forma que; todo cliente seja visitado por um único veículo, cada veículo realize

30

no máximo uma rota, a soma das demandas de cada rota não ultrapasse ; o

somatório de custos de todos os arcos seja mínimo (LAPORTE; LAPORTE, 2009).

No CVRP, as demandas dos clientes são expressas por um valor que

representa a massa dos itens a serem entregues, na medida em que nas aplicações

reais as demandas consistem não somente de massa, mas também de um formato.

Uma modelagem mais precisa pode envolver problemas do tipo; a ordem de carga e

descarga do itens, tratamento de itens frágeis, restrições de rotação dos itens, entre

outros (BORTFELDT; WÄSCHER, 2013). Um problema prático comum surge quando

deve-se garantir que todos os itens atribuídos a um veículo devem ter suas alocações

físicas viáveis dentro do mesmo.

As restrições de carga citadas estão relacionadas com o problema de

carregamento multidimensional, que são extensões do problema clássico de bin

packing unidimensional (MARTELLO; TOTH, 1991) (JR et al., 1997). Uma vasta

literatura trata dos problemas de carregamento multidimensional, destes, alguns que

foram tratados juntamente ao problema de roteamento são (IORI; MARTELLO, 2010):

Two –Dimensional Bin Packing Problem (2BPP): Empacotar um conjunto de

retângulos em retângulos maiores idênticos, de tal forma a minimizar o número de

retângulos maiores ( . Algoritmos exatos para o 2BPP são baseados em variações

do branch-and-bound capazes de resolver instâncias até 100 itens, à época da

publicação de (MARTELLO et al., 1998).

Two-dimensional Strip packing Problem (2SPP): Empacotar um conjunto de

retângulos em um retângulo maior com largura definida e comprimento infinito, de forma

a minimizar o comprimento total utilizado. Uma revisão sobre o assunto é apresentada

em (RIFF et al., 2009).

Three-Dimensional-Bin-Packing-Problem(3BPP): Empacotar um conjunto de caixas

retangulares em um número mínimo de caixas retangulares maiores. (MARTELLO et

al., 2000) propuseram algoritmos exatos para o problema.

Three-Dimensional Strip Packing Problem (3SPP): Empacotar um conjunto de

caixas retangulares com altura e largura definidos e profundidade infinita, com objetivo

de minimizar a profundidade total. Uma heurística para o problema é encontrada em

(BORTFELDT; MACK, 2007).

O problema de Roteamento de veículos com 3 dimensões (3L-CVRP) teve sua

primeira contribuição proposta na metaheurística de Gendreau (GENDREAU et al.,

31

2005). No 3L-CVRP, para cada veículo alocado, um problema de empacotamento 3D

deve ser resolvido. Este consiste em encontrar uma organização das caixas dentro do

volume do veículo de tal forma que não exista sobreposição. Além das restrições de

massa e de empacotamento, existem outras restrições que surgem de problemas reais.

Algumas caixas podem possuir restrições de fragilidade, ou seja, nenhuma caixa pode

ser alocada acima destas. Ainda, deve existir uma área de apoio mínima para manter

as caixas estáveis.

O 3L-CVRP consiste em encontrar um conjunto de no máximo rotas, tais que:

todo cliente seja visitado uma vez, nenhum veículo carregue uma massa maior

do que , – Para todo veículo existe um carregamento tridimensional que satisfaz

as restrições citadas acima (fragilidade, área de suporte e carregamento sequencial) e

a solução tenha custo mínimo.

O algoritmo de (GENDREAU et al., 2005) parte do seu próprio método de

resolução do problema de 2 dimensões, porém introduz uma nova maneira de se

determinar as cargas dos veículos por meio de uma lista Tabu.

(JUNQUEIRA, 2013) propõe o primeiro modelo de programação linear inteira

para o 3L-CVRP com restrições práticas, incluindo todas as abordadas por Gendreau,

porém, pela complexidade do problema, somente aqueles com tamanhos moderados

foram resolvidos na otimalidade (JUNQUEIRA et al., 2013). Como alternativa aos

modelos, Junqueira (2013) propõe algumas heurísticas, deixando de lado algumas das

restrições práticas.

Em suas heurísticas, Junqueira (2013) utiliza módulos específicos para cada

uma das partes do problema, no roteamento é usado o algoritmos de Clarke & Wright

(CLARKE; WRIGHT, 1964) e na parte de carregamentos o algoritmo base é o de

George & Robinson (GEORGE, J; ROBINSON, D, 1980), ao qual Junqueira realiza

diversas modificações, incluindo as 60 permutações propostas em (MORABITO, 2004).

3.3 FUNDAMENTAÇÃO TEÓRICA

3.3.1 CONCEITOS DE GRAFOS

Um grafo é uma estrutura que consiste em um conjunto finito

32

de elementos chamados nós/vértices e um conjunto não ordenado de pares de nós

chamados arcos/arestas. Um grafo dirigido ou dígrafo é definido similarmente, exceto

que, cada arco é um par ordenado (LAWLER, 1976).

Um grafo é dito bipartido se o seu conjunto de vértices pode ser particionado

em dois subconjuntos e , de tal forma que todos os arcos possuam um vértice em

e outro em como mostrado na FIGURA 12 (a). Se o grafo possuir arestas ligando

todos os vértices de a todos os vértices de é então chamado de bipartido completo

(CHRISTOFIDES, 1975), como mostrado na FIGURA 12 (b).

FIGURA 12 – GRAFO BIPARTIDO


Chama-se subgrafo de , o conjunto , tal que e

, como mostrado na FIGURA 13. Um caminho entre e é uma sequência de arcos

de forma e um subcaminho de um caminho é uma sequência de

arcos do caminho. Um é um caminho com pelo menos um arco. Um caminho

Euleriano é um caminho em que todos as arcos de aparecem somente uma vez.

33

FIGURA 13 – GRAFO E SUBGRAFO


Um grafo sem ciclos é chamado de acíclico. Dois nós são conectados se existe

um caminho entre eles e um grafo é conectado se todos os pares de nós são

conectados. Um ciclo Hamiltoniano é um ciclo em um grafo, tal que não existem

dois nós iguais no caminho de a exceto , e um grafo é Hamiltoniano se existe um

ciclo Hamiltoniano que passe por todos os nós do grafo (LAWLER, 1976). Uma subrota

em é um ciclo Hamiltoniano que não contém todos os nós de .

Uma árvore em é um subgrafo acíclico conectado com os nós de . Uma

árvore enraizada é uma árvore tal que:

A – Existe um nó especial chamado nó raiz, e

B – Os nós restantes (exceto a raiz) são particionados em conjuntos

disjuntos tal que cada elemento do conjunto é também uma árvore.

O nível de um nó definido em relação a é: o nó raiz tem nível 1 e os outros

têm um nível a mais do que eles têm em relação à subárvore de raiz que contém os

mesmos (KNUTH, DONALD, 1969).

Um filho de um nó é qualquer nó diretamente conectado à com um nível

mais alto do que , como mostrado na FIGURA 14. A raiz A contém dois nós filhos B

e C, que também são subárvores de A.

34

FIGURA 14 – NÍVEIS DE UMA ÁRVORE

FONTE: Adaptado de (KNUTH, DONALD, 1969).

3.3.2 PROBLEMA DE DESIGNAÇÃO (AP)

O Problema de Designação (Assigment Problem – AP) define-se em encontrar

a alocação ótima de n trabalhadores à n tarefas, visto que a cada tarefa existe um peso

indicando o quão bem cada trabalhador realiza a mesma. Uma designação ótima é

aquela em que faz a soma de pesos à máxima possível (no caso de pesos como

preferências do tipo “maior é melhor”), ou ainda, uma que faça a soma a menor possível

(no caso em que os pesos sejam o custo de designação, do tipo “menor é melhor”) e

para esta o modelo matemático de Programação Linear Binária é o que segue:

(MUNKRES, 1957):

Variáveis de decisão:

(3.1)

(3.2)

Sujeito a:

(3.3)

(3.4)

35

Em que é igual a 1, se o trabalhador é designado à tarefa e igual a 0 caso

contrário.

O AP também pode ser modelado e resolvido partindo de uma abordagem via

grafos: se, em um grafo bipartido completo, todas as suas arestas possuírem um peso

associado, o AP pode ser definido como: Encontrar um conjunto de arestas em de

tal forma que todos os vértices estejam ligados a um único vértice de e todos os

vértices de estejam ligados a um único vértice de , maximizando o somatório dos

custos de todas as arestas (PAPADIMITRIOU; STEIGLITZ, 1982).

Métodos de resolução: O método Húngaro é um dos algoritmos mais conhecidos para a resolução do

AP. Primeiramente foi desenvolvido por (KUHN, 1950) e posteriormente aprimorado por

(MUNKRES, 1957). Existem diversas implementações para o método, entre elas as de

(CHRISTOFIDES, 1975) e (PAPADIMITRIOU; STEIGLITZ, 1982).

A metodologia de (CHRISTOFIDES, 1975), que segue a ideia do algoritmo

aprimorado de Munkres, é apresentada na FIGURA 15. FIGURA 15 – MÉTODO HÚNGARO: CHRISTOFIDES

Método Húngaro – Christofides 1 Para cada coluna da matriz encontre o menor elemento e o subtraia de todos os elementos da

referida coluna. Armazene todos os mínimos em um vetor 2 Marque o máximo número de zeros na matriz, de tal forma que nenhum zero seja marcado mais

de uma vez em alguma linha ou coluna. 3 Encontre uma linha s sem zero marcado e inicialize um vetor . Se tal linha não existir, a

solução atual é ótima. 4 Começando em , com todas as outras linhas e colunas não marcadas

marque toda coluna não marcada k que contenha um 0 não marcado em uma linha marcada, com

5 Marque toda linha i não marcada, que tenha uma 0 marcado em uma coluna marcada, com

6 Repita as marcações 6 e 7 até que uma coluna t sem marcações seja marcada (A), ou até que nenhuma marcação seja possível (B).

7 (A) Um caminho melhorado foi encontrado, em que Inverter os zeros marcados e não marcados nas posições ( , dessa forma um elemento na solução atual. Os valores de são apagados e o processo se repete até que o número de zeros = n.

8 (B) Defina como o conjunto de todas as linhas e colunas marcadas, e as não marcadas e calcule: e atualize

9 para e para . Repita 6 e 7. FONTE: O autor (2018).

O algoritmo de Papadimitriou (PAPADIMITRIOU; STEIGLITZ, 1982) transforma

o grafo bipartido em uma rede com um subconjunto de todas as arestas de que

satisfaçam uma condição (linha 3 da FIGURA 16). Em seguida o algoritmo de Fluxo

36

Máximo de Ford-Fulkerson (FORD, L. R, 1963) é aplicado repetidas vezes. Para que o

subgrafo se transforme em uma rede e o algoritmo de Fluxo Máximo de Ford-Fulkerson

possa ser aplicado, insere-se uma fonte ligada à todos os vértices e todos os

vértices ligados a um sumidouro

O algoritmo de Fluxo Máximo de Ford-Fulkerson é aplicado em um subgrafo

de de tal forma que, quando o fluxo máximo é encontrado,

verifica-se se o número de emparelhamentos é igual a n. Se sim, o AP está com a

solução ótima, caso contrário, um novo subgrafo de é criado e o processo

repetido até que o número de emparelhamentos seja n. O algoritmo de Papadimitriou

(PAPADIMITRIOU; STEIGLITZ, 1982) é apresentado na FIGURA 16:

FIGURA 16 – MÉTODO HÚNGARO: PAPADIMITRIOU

Método Húngaro – Papadimitriou

1 Inicializar os vetores α e β com n posições,

2 Inserir uma fonte s ligada a todos os pontos e um sumidouro que esteja ligado a todos os pontos

3 Criar o Subgrafo de utilizando somente as arestas em que

.

4 Resolver o problema de fluxo-máximo pelo algoritmo de Floyd-Fulkerson em , armazenando as informações de vértices e marcados no processo.

5 No término do algoritmo de fluxo máximo: se o número de emparelhamentos é igual a n, então, ir para o passo IX, caso contrário armazenar e ir para o passo VI:

6 Calcular o valor, de todos os vértices marcados e não marcados

.

7 Atualizar as variáveis:

8 Voltar para o passo 3

9 Fim.


(LOCH, 2014) propôs uma nova abordagem de resolução para o problema do

transporte, comparando-o ao clássico e consolidado método MODI (REINFELD;

VOGEL, 1958). O novo método se diferencia na medida em que nem todas as variáveis

duais são atualizadas a cada iteração, como prevê o método MODI. Para se descobrir

quais custos reduzidos das variáveis devem e quais não devem ser atualizados, é

37

proposta uma resolução em árvores. Essa estrutura permite uma clara visualização dos

padrões de atualização dos custos reduzidos (LOCH, 2014) .

Além de não se atualizar todas as variáveis duais pelo método em si, é proposto

também um método de pricing. Ao se manter um registro contendo todas variáveis

duais, somente são atualizadas aquelas cuja razão de economia entre o valor atual e o

da iteração anterior ficar abaixo de uma tolerância pré-estabelecida.

O AP pode ser avaliado como um caso específico do problema de transporte,

considerando que existem fornecedores e clientes, com todas as demandas e

ofertas iguais a 1. Dessa forma, analisando as substanciais reduções em tempo

computacional que se consegue atingir com o método aplicado ao problema do

transporte, é natural testá-lo também ao problema de designação. Estes testes foram

realizados por (LOCH, 2014), porém comparando o novo método em árvore somente

com o método MODI para resolução da designação e não a algoritmos específicos de

resolução do AP. Com o método proposto, comparado a implementação do MODI

estruturada em quadros, houve uma redução de 95,18% em tempo médio de resolução.

3.3.3 O PROBLEMA DO CAIXEIRO VIAJANTE

Seja um grafo, sendo seu conjunto de vértices, e

seu conjunto de arestas, à cada aresta existe um custo

associado, formando a matriz . O problema do caixeiro viajante (Traveling Salesman

Problem TSP) se resume em determinar uma rota com menor distância dentre todos as

possíveis, passando exatamente uma vez por cada vértice do conjunto .

A matriz de distâncias pode ser simétrica ou assimétrica (Assimetric Traveling

Salesman Problem- ATSP); no primeiro caso têm-se que para todo e

no segundo, para pelo menos algum .

Diversas variações foram propostas para o TSP, parte destas baseando-se em uma

simples suspeita de que alguns problemas ou aplicações da vida real podem ser

modeladas como o TSP. Uma lista com alguns casos, é apresentada a seguir:

O Máximo TSP: O problema do TSP Máximo é equivalente ao do TSP com uma

função objetivo a ser maximizada ao invés de minimizada, ou seja, encontrar a

38

ordenação do conjunto de vértices de tal forma que a soma dos arcos

gerados seja a maior possível.

The Bottleneck TSP (BTSP): O BTSP consiste em encontrar um ciclo Hamiltoniano

tal que, de todos os arcos contidos na rota, o maior seja minimizado. O problema foi

introduzido por (GILMORE, P; GOMORY, E, 1964) e teve sua estrutura generalizada

por (AUTHORITY, 1978), que também explicitou uma aplicação nos ambientes de

machine scheduling.

TSP com múltiplas visitas: Neste caso, deve-se encontrar a rota mínima que

comece em um determinado vértice visitando todos pelo menos uma vez

e retornando ao vértice inicial, de tal forma que o custo da rota seja mínimo.

O problema do caminho mínimo: O problema define-se por, dados dois vértices

, encontrar o mínimo caminho Hamiltoniano em de a

TSP Clusterizado: neste caso existe uma segregação do conjunto de vértices de

em clusters , e o problema é então encontrar a rota única de menor custo,

sujeito a restrição de que cidades de um mesmo cluster devem ser visitadas

consecutivamente (GUTTMAN-BECK et al., 2000), (JONGENS; VOLGENANT, 1985).

Múltiplos TSP: Supondo que existam caixeiros-viajantes no nó 1 de , cada

caixeiro visita um subconjunto de nós de exatamente uma vez, retornando ao nó

inicial. Deve-se encontrar uma partição e uma rota para cada

partição, de forma que para todo , , para , e

a distância total percorrida por todos os caixeiros-viajantes seja minimizada. (BEKTAS,

2006).

Métodos de resolução:

39

Ao se lidar com problemas com complexidades NP/NP-Completos e NP-

difíceis, usualmente lança-se mão de métodos que não exploram a totalidade do

espaço de busca. Visa-se, assim, reduzir o tempo computacional dos cálculos, em

detrimento da melhor resposta que poderia ser obtida. Estes são conhecidos por

métodos aproximados. Apesar da dificuldade de resolução do TSP, alguns algoritmos

conseguem explorar todo o espaço em um tempo que, em média é polinomial, como o

algoritmo Simplex (CORMEN, 1996).

Métodos aproximados podem ainda ser classificados em duas famílias

distintas, os algoritmos aproximativos e as heurísticas. Os algoritmos aproximativos

fornecem bounds provados em algum aspecto do problema, seja em qualidade de

solução ou tempo computacional, na medida em que as heurísticas encontram soluções

consideradas boas em tempo computacional aceitável, porém não garantem nenhum

tipo de bound (TALBI, 2009).

Os métodos heurísticos, por sua vez, também podem ser classificados em dois

subtipos; heurísticas especificas e meta-heurísticas. As heurísticas específicas são

engendradas para resolver uma classe específica de problemas e/ou instâncias. Já as

meta-heurísticas podem ser utilizadas para se resolver problemas genéricos (TALBI,

2009). Arenales et. al (2007) ainda considera a subdivisão das heurísticas em duas;

construtivas e de busca local;

Uma árvore dos métodos é mostrada na FIGURA 17.

FIGURA 17 – TIPOLOGIA DE MÉTODOS DE RESOLUÇÃO


Métodos exatos:

40

A seguir são apresentados os modelos matemáticos mais comumente usados em

programação inteira para resolução do TSP, bem como os métodos de aproximação

clássicos encontrados na literatura.

Parte dos métodos exatos propostos para o TSP baseiam-se em de formulações

matemáticas desenvolvidas por Programação Linear Inteira, de forma que algumas

formulações e algoritmos derivados das mesmas são apresentados.

A primeira formalização de um modelo matemático para o TSP pode ser atribuída

a (DANTZIG et al., 1954) - DFJ, em que designa uma variável binária por arco,

indicando se o mesmo está contido na rota final ou não:


(3.5)

(3.6)

Sujeito a:

(3.7)

(3.8)

(3.9)

(3.10)

(3.11)

(3.12)

A restrição de eliminação de subrotas (3.9) proíbe a formação de rotas em

subconjuntos com menos do que vértices. As restrições desta formulação, crescem

exponencialmente a medida em que o número de pontos cresce linearmente.

41

Uma nova formulação é proposta por (MILLER et al., 1960), em que o número

total de restrições é reduzido significativamente :


(3.13)

(3.14)

(3.15)

Sujeito a:

(3.16)

(3.17)

(3.18)

(3.19)

(3.20)

A função objetivo minimiza o custo total da rota, as restrições (3.16) e (3.17)

garantem a entrada e saída de fluxo nos vértices. A restrição (3.18) exclui subrotas,

garantindo que a posição do vértice em uma rota sempre será menor do que a posição

atribuída ao vértice se o arco for utilizado.

Além de se avaliar o número de restrições gerado pelo modelo, avalia-se

também os limitantes inferiores quando da resolução do modelo de programação linear

relaxado, ou seja, trocando as restrições (3.11) e (3.19) por :

(3.21)

Por este critério, embora o modelo de (MILLER et al., 1960) tenha um aumento

de restrições de ordem linear, o mesmo tem um limitante inferior em sua relaxação

linear muito fraco (LANGEVIN et al., 1990), de forma que a relaxação do modelo DFJ

fornece limitantes próximos a 0.5% do ótimo (HELD; KARP, 1970).

Algoritmos Branch-and Bound (B&B) realizam uma enumeração sistemática

das soluções candidatas, armazenadas em uma árvore enraizada. O algoritmo explora

42

os ramos da árvore que representam conjuntos de soluções, depois de realizar uma

verificação dos Bounds já encontrados, se não existir possibilidade do ramo possuir

melhores Bounds do que os já encontrados o mesmo é descartado (ARENALES et al.,

2007).

Diversos algoritmos baseados em B&B foram propostos para se resolver o

ATSP (CARPANETO; TOTH, 1980), (BALAS; CHRISTOFIDES, 1981), (MILLER;

PEKNY, 12729BC).

A relaxação pode ser obtida pela remoção, de qualquer modelo do TSP, das

restrições que visam a eliminação de subrota. Em seguida o problema é resolvido

iterativamente verificando todas as soluções e se as mesmas possuem subrotas, se

sim, as restrições de eliminação de subrotas especificas para as que foram geradas

são adicionadas ao modelo, e o mesmo é resolvido novamente, até que uma solução

sem subrotas seja encontrada (restrições preguiçosas - lazy constraints). Uma

resolução que também usa esta abordagem é a relaxação via problemas de designação

e uma estrutura em árvore enumerativa de decisões (CHRISTOFIDES, 1975).

Estudos de base teórica sobre o TSP demonstram o resultado de que toda rota

t do TSP é uma solução viável para o AP e o custo deste é justamente o custo total de

t (BELLMORE; MALONE, 1971). Porém, nem toda solução do AP é uma rota do TSP,

podendo ser consideradas coleções de subrotas do TSP. As restrições 3.2 do modelo

de designação simplesmente garantem que a solução seja cíclica, dessa forma, se uma

nova restrição for adicionada garantindo que o ciclo formado seja único (Hamiltoniano),

tem-se um modelo matemático para o TSP.

O efeito equivalente às inserções de restrições para eliminação de subrotas

pode ser obtido ao se definir para algum que esteja contido em alguma

subrota e resolver o AP novamente, de forma que o arco não deve estar mais na

solução final, o mesmo processo pode ser repetido até o momento em que não existam

mais subrotas na solução.

Para organizar a estruturação da resolução em forma de árvore de decisão, o

AP inicial (P0) é considerado como o nó raiz da árvore. Por meio de inserções de

, de acordo com algum critério, novos subproblemas (P1, P2, etc.) são gerados a

partir de P0. Este processo é repetido para todos os subproblemas PK (onde K = 1, ..,

k) até que o melhor caminho Hamiltoniano seja encontrado.

43

As regras de inserção do valor podem variar. A regra utilizada neste

estudo segue a seguinte lógica, como mostrado na FIGURA 18:

1. Encontrar a menor subrota de um Problema Pk; Por exemplo (2,4,3) no nó 0.

2. Escolher um ponto da subrota; Por exemplo (2) no nó 0.

3. Formar todas combinações de arcos dos pontos escolhidos com todos os outros

da subrota; exemplo {(2,3) (2,4)}, {(3,2)(3,4)} e {(4,2)(4,3)}, para o nó 0 da FIGURA 18.

4. Para todos os arcos , encontrados no passo 3, criar um novo subproblema,

alterando a matriz do problema de origem do recém-criado, com .

Nota-se que ao executar o passo 2, a escolha do ponto que será combinado

com todos os outros gera o subproblema “filho”, dessa forma, existem tantas

possibilidades de ramificação quantos forem os nós daquela subrota.

A FIGURA 18 exemplifica uma estrutura de solução. Em cada nó estão as

informações das subrotas geradas e o valor da função objetivo. Os nós acinzentados

apresentam caminhos hamiltonianos, ou seja, são Bounds viáveis para o TSP. Como a

matriz de custos utilizada para a resolução do AP em qualquer nó filho (ex P2), é

herdada do nó pai (ex P0) com as inserções de para evitar alguma subrota,

necessariamente . Assim, obtém-se um critério de parada de ramificação

da árvore. Uma vez que um Bound do TSP é encontrado e armazenado, qualquer outro

nó com deve ser eliminado e não mais ramificado, finalizando assim a

exploração daquele ramo.

FIGURA 18 – ABORDAGEM DO TSP VIA CONCEITO DE ÁRVORE

44


Métodos aproximativos:

O algoritmo aproximativo de Christofides possui uma taxa de 1.5 para o STSP,

ou ainda, seja a solução ótima do problema, o algoritmo tem a garantia de nunca

produzir uma solução que seja maior do que 1.5 vezes . (CHRISTOFIDES, 1976). A

metodologia é apresentada na FIGURA 19:

FIGURA 19 – MÉTODOLOGIA HEURÍSTICA CHRISTOFIDES 3/2 Christofides_Heuristica_3/2

1 Encontrar a árvore geradora mínima do Grafo

2 Marcar os nós impares* da árvore

3 Encontrar o matching mínimo para os nós impares

4 Adicionar arcos aos nós com matchings mínimos

5 Encontrar o caminho Euleriano

6 Remover arcos extras


Por um longo tempo o algoritmo de Christofides manteve a melhor razão

aproximativa, até que (SUDAN; SZEGEDYL, 1992) desenvolveu uma metodologia que,

para qualquer fixo, pode-se computar soluções em tempo

polinomial. O algoritmo possui algumas idéias elementares, como o algoritmo de

dissecação de Karp (KARP, 1977), e o algoritmo de tempo exato de Smith (SMITH,

1988).

Ao conjunto de heurísticas formuladas com objetivo de prover uma solução

para o problema de modo construtivo, é dado o nome de “Heurísticas construtivas”. As

Heurísticas construtivas são inicializadas com uma solução nula e a cada iteração

adicionam uma variável de decisão ao problema, de acordo com algum critério.

As heurísticas do “Vizinho mais próximo” e do “k-Vizinho mais próximo” são as

construtivas mais populares em se tratando do TSP, pois são de simples

implementação e alta velocidade (com soluções não necessariamente boas) provêm

uma base para serem usadas junto a outras heurísticas e Meta-heurísticas

(RESENKRANTZ et al., 1977).

45

Os dois procedimentos partem do princípio Guloso (Greedy) na construção da

solução, ou seja, a cada inserção de um elemento na rota, avaliam qual seria a melhor

escolha considerando unicamente o último ponto inserido. Construções deste tipo

podem prover soluções pobres ao final, na medida em que não consideram a estrutura

completa do problema. Os pseudocódigos são apresentados abaixo, FIGURA 20 e

FIGURA 21.

FIGURA 20 – HEURÍSTICA VIZINHO MAIS PRÓXIMO

1 Inserir ponto inicial na rota 2 Enquanto a rota estiver incompleta fazer 3 Escolher o ponto mais próximo ao último ponto inserido na rota 4 Adicionar este ponto a rota 5 Fim enquanto


FIGURA 21 – HEURÍSTICA K-VIZINHO MAIS PRÓXIMO 1 Para k=0 até o número de pontos 2 Resolver Heuristica_vizinho_mais_proximo(k) 3 Calcular custo da rota 4 Se o custo for melhor que o custo atual 5 Melhor custo recebe custo atual 6 Fim se 7 Fim

para


As heurísticas de melhoria são iniciadas com alguma solução e tentam

melhorá-la por meio de mudanças iterativas, usualmente por meio de manipulações

simples na estrutura da solução. Em se tratando de problemas em grafos, estas

estruturas podem ser nós, arcos, subcaminhos, ou qualquer outra relacionada à grafos.

A método 2-opt proposto por Lin (LIN, 1965) é uma heurística de melhoria que,

a partir de uma solução, realiza trocas iterativas entre os arcos verificando se existe

melhoria no custo total da rota. Os arcos não adjacentes e são

substituídos por outros e , sendo estes os únicos que podem ser

substituídos para manter a rota viável. Para que a ordem dos arcos (predecessores-

sucessores) seja mantida, um dos dois subcaminhos formado após a remoção dos dois

primeiros arcos deve invertida. A alteração no custo da solução produzida pela troca

pode ser expressa por . Uma solução

46

2-opt ótima é alcançada realizando trocas 2-opt até que não exista troca possível em

que .

O procedimento 2-opt pode ser generalizado para que arcos sejam trocados,

existem maneiras de se eliminar k arcos e substituir por k novos, e

maneiras de reconectar os subcaminhos formados. Uma complexidade em tempo

computacional de , dessa forma, a utilização de melhorias com k>3

devem ter alguma inteligência para restrição do espaço de busca, caso contrário pode

se tornar um método não prático computacionalmente.

O método proposto por (LIN, 1965) teve uma adaptação de (EILON;

CHRISTOFIDES, 1972) que utilizaram e . Com base nesta adaptação,

(LIN; KERNIGHAN, B, 1973) propuseram uma nova abordagem, em que a decisão dos

valores de é alterada dinamicamente pelo algoritmo.

O algoritmo é definido por trocas (ou movimentos) que podem transformar uma

rota em outra. Dada uma rota inicial, o algoritmo repetidamente realiza trocas de tal

forma que o custo total da rota atual seja reduzido, até que uma rota encontrada não

possua mais trocas que reduzam o seu custo. Este processo pode ser repetido diversas

vezes com soluções iniciais diferentes.

Seja a rota atual. A cada iteração o algoritmo tenta encontrar dois conjuntos

de arcos, e , de tal forma que, se os arcos forem

removidos e substituídos pelos arcos , o resultado é uma rota de menor distância

total. Essa troca é chamada de movimento . A FIGURA 22 ilustra um movimento

3-opt.

FIGURA 22 – MOVIMENTO 3-OPT

FONTE: Adaptado de (LIN; KERNIGHAN, B, 1973).

47

Os conjuntos e são construídos elemento a elemento, inicialmente ambos

são conjuntos vazios. Na iteração um par de arcos, e são adicionados a e

respectivamente. Para que a factibilidade seja mantida, e devem compartilhar um

ponto, e também devem e . Seja um dos dois pontos de , têm-se

genericamente: ) , ) e ) como na FIGURA

23. Para cada escolha dos conjuntos, é necessário que o ganho , sendo que

é o ganho pela troca de por , então é a soma

. FIGURA 23 – ESCOLHA DOS CONJUNTOS X E Y


A TABELA 1 apresenta uma metodologia para o método: TABELA 1 – METODOLOGIA LIN-KERNIGHAN

1 Gerar solução inicial aleatória

2 Seja i=1. Escolher

3 Escolher

4 Escolher tal que

Se não for possível, ir para o passo 12

5 Seja i = i+1

6 Escolha tal que:

(a) Se se juntar a o resultado é uma rota T´

(b) para todo

Se T´ é uma rota de menor custo do que T, então T = T´ e vá para o passo 2

7 Escolher tal que:

(a)

(b) para todo

(c) existe

Se tal existe, ir para o passo 5

48

8 Se existir uma alternativa não escolhida para , i=2 e vá para o passo 7




12 Se existir uma alternativa não escolhida para , vá para o passo 2

13 Fim (ou volte ao passo 1 com uma nova solução inicial)


Esse procedimento produz soluções quase-ótimas, porém é imbuído de uma

implementação com maior complexidade. Helsgaun (2006) propõem uma

implementação melhorada do método em linguagem C (Helsgaun Lin Kernighan -HLK),

quando utilizado para resolver instâncias simétricas do TSPlib, em alguns casos, como

em ali535, d657, d493 e pr1002, de 100 testes realizados, os valores ótimos foram

encontrados nas 100 vezes em menos de 3s. (HELSGAUN, 2006).

Todas as variações do método de (LIN, 1965) requerem uma matriz simétrica,

pois a vizinhança se baseia na troca de arcos. Apesar disso, Helsgaun (2016) utilizou

o método proposto por (JONKER; VOLGENANT, 1983) para transformar uma matriz

assimétrica em simétrica, ao custo de quase duplicar o seu tamanho e aplicou o seu

algoritmo em todas as instâncias do ATSP contidas no TSPLib, resultando que a

solução ótima foi encontrada para todas as instâncias (HELSGAUN, 2000).

A Meta-heurística Simulated Annealing (SA) é baseada nos conceitos

mecânicos de aquecimento e arrefecimento de sólidos. Para que um material atinja o

seu estado de mais baixa energia, é necessário um aquecimento até que suas

partículas estejam randomicamente distribuídas em estado líquido, para então, reduzir

gradativamente a temperatura até que o sistema atinja um estado de mínima energia.

Em sua máxima temperatura todos os possíveis estados do material podem ser

alcançados, na medida em que, quando da diminuição da mesma, as possibilidades

vão se restringindo até a convergência para um estado estável (TALBI, 2009).

A primeira aparição do SA aplicado a problemas de otimização foi no problema

de particionamento de grafos proposto em (KIRKPATRICK et al., 1983). A associação

em problemas de otimização é a seguinte: a temperatura do material é equivalente a

permissividade de novas soluções serem incorporadas ou não a solução atual, desta

forma se é alto, existe uma vasta diversificação, muitas soluções serão aceitas (até

mesmo soluções piores do que a atual), conforme ocorre a redução em , o número

49

de movimentos permitidos também é reduzido, até o momento em que nenhum

movimento possa ser realizado, momento do encontro de um mínimo local.

Para um determinado valor de , o SA funciona como uma heurística de

, considerando que a solução atual se encontra no ponto , toda a vizinhança é

vasculhada, e uma solução pode ser aceita, mesmo se seu valor for superior a ,

para evitar que a solução permaneça em um mínimo local. Diversos autores utilizaram

o S.A no TSP, como (BONOMIT, 1984),(GOLDEN; SKISCIM, 1986) e (NAHAR et al.,

1989)..

A Busca Tabu (GLOVER, 1989) funciona por um mecanismo de restrição de

movimentos; inicialmente uma lista de movimentos é gerada, a cada iteração um

movimento da lista é selecionado e durante iterações o movimento permanece em

uma lista de memória de curto prazo, enquanto o movimento estiver contido nesta lista,

nenhuma solução pode utilizá-lo. Além disto, existe uma lista de memória de longo

prazo, sendo este o mecanismo de diversificação do algoritmo.

Os algoritmos genéticos (AG) propostos por Holland 1975 (HOLLAND, J, 1992)

pretendem simular o processo de seleção natural descrito por Darwin. Nela a evolução

de uma população de indivíduos só é possível se existir um certo grau de mutação para

que, desta forma, exista diversidade na população e os indivíduos mais aptos passem

suas características para populações seguintes.

Em se tratando de otimização, cada solução do problema é considerada como

um indivíduo e um conjunto de indivíduos perfaz uma população. Os indivíduos podem

ser codificados como vetores (representando a ordem dos pontos, no caso do TSP). O

algoritmo passa a atualizar a população inicial por meio de cruzamentos e mutações.

Os cruzamentos são combinações de materiais de indivíduos pais para geração de

filhos (os filhos recebem parte da rota dos dois pais) e a mutação é responsável por

alterações pontuais em soluções, como por exemplo uma troca (swap) entre dois

elementos da solução. Após os cruzamentos e mutações, os indivíduos que

continuarão e os que serão descartados da população são selecionados por algum

critério, dando início assim, a uma nova rodada de seleção. O AG híbrido de (NGUYEN;

YOSHIHARA, 2007) encontrou soluções ótimas em casos em que nem mesmo o HLK

conseguiu.

50

3.3.4 MÉTODOS DE ROTEIRIZAÇÃO EM CD´s

Em seguida são apresentadas algumas das heurísticas para o problema

abordado neste trabalho. Estas podem ser aplicadas a uma lista de tamanho genérico

de itens a serem coletados, porém não faz sentido utilizar métodos heurísticos se essa

lista não contiver pelo menos 3 itens; Com apenas um item, a menor distância é

simplesmente o menor caminho entre o depot e o item. Com dois itens, a distância

sempre será a mesma, independentemente da ordem de coleta

Heurística S-shape (ou heurística transversal): Consiste em atravessar um

corredor inteiro caso exista algum item a ser coletado. Corredores que não possuem

itens não são visitados. Uma rota realizada pela heurística é apresentada na FIGURA

24. (KOSTER, DE et al., 2007)

FIGURA 24 – HEURÍSTICA S SHAPE


Heurística do retorno: O operador sempre entra e sai pelo mesmo lado do corredor

após realizar a coleta dos itens. A heurística do retorno requer uma implementação

computacional simples, bem como a heurística S-Shape. Uma consideração referente

ao tipo de coleta dos itens pode ser analisada quando da escolha entre as duas; se o

picking a ser realizado será uni ou bi-lateral. Ou seja, ao passar por um corredor o

51

operador coleta itens de ambos os lados do corredor (picking bilateral) ou somente em

um (unilateral). (KOSTER, DE et al., 2007)

A heurística S-Shape é mais apropriada ao picking bilateral, na medida em que

os corredores são visitados somente uma vez, em contrapartida, a heurística de retorno

se faz mais apropriada ao picking unilateral. Dessa forma, ao se usar a heurística de

retorno, deve-se levar em consideração a largura dos corredores. Segundo

(GOETSCHALCKX; RATLIFF, 1998) a largura dos corredores deve ser muito grande

ou a densidade muito alta para que o picking bilateral seja viável. FIGURA 25 contém

uma rota calculada pela heurística de retorno.

FIGURA 25 – HEURISTICA DO RETORNO


Heurística do ponto médio: Esta heurística divide o CD em duas partes iguais,

uma contendo o CTI e uma com o CTS como mostrado pela linha vermelha tracejada

na FIGURA 26. O operador segue pelo CTI entrando em todos os corredores que

contenham itens a serem coletados, até no máximo a marca de divisão, para então

retornar ao CTI e continuar o processo até o último corredor da direita, que é

atravessado por completo até o CTS. No CTS o mesmo processo é realizado, o

operador entra somente nos corredores com itens para coleta, a uma distância máxima

determinada pela divisão previamente realizada, até chegar ao primeiro corredor, que

é atravessado por completo. Na FIGURA 26 a divisão do CD e uma rota calculada pela

heurística são ilustrados. (KOSTER, DE et al., 2007)

52

FIGURA 26 – HEURISTICA DO PONTOS MÉDIO


Heurística do maior Gap: Nesta heurística, o operador primeiro atravessa o

corredor inicial por completo até o CTS, em seguida entra nos próximos corredores até

atingir o maior Gap de distância, ou seja, a maior distância entre dois pontos

consecutivos de coleta, então retorna pelo mesmo lado até o CTS, continuando esse

processo até o ultimo corredor, que é novamente percorrido por completo até o CTI.

Em seguida o operador volta ao ponto inicial, entrando e percorrendo os corredores do

CTI até que o maior gap seja atingido, como apresentado na FIGURA 27.(KOSTER,

DE et al., 2007)

FIGURA 27 – HEURISTICA DO MAIOR GAP


Heurística combinada: Nesta heurística, características das heurísticas S-shape e

do retorno são mescladas. A cada corredor é avaliada qual é a menor entre as duas

53

distâncias: atravessar o corredor todo ou coletar o último item do corredor e retornar

(ROODBERGEN; KOSTER, 2010). A FIGURA 28 exemplifica uma rota calculada pela

heurística combinada:

FIGURA 28 – HEURISTICA COMBINADA

FONTE: O Autor (2018)

O trabalho realizado por (SCHOLZ et al., 2016) apresenta um estudo minucioso

das possíveis rotas em um CD, perfazendo 6 ao total. Com base nestas possibilidades,

os autores utilizam uma discretização dos pontos de um corredor, reduzindo-os para 4

em corredores de coleta e 2 para os transversais. Destes pontos, algumas duplicatas

são realizadas para que a restrição de visita única por ponto continue sendo satisfeita.

A discretização utilizada neste trabalho segue a mesma lógica, sendo necessários no

máximo 4 pontos por corredor, que são selecionados da seguinte maneira (somente

para corredores com mais de 4 pontos):

Pontos 1 e 4: 1º e último ponto do corredor, respectivamente.

Pontos 2 e 3: Os dois pontos com a maior distância entre quaisquer dois

pontos do corredor, exceto o 1 e o 4.

Uma discretização dos pontos do primeiro corredor de um CD é mostrado na

FIGURA 29, inicialmente 6 pontos seriam considerados na roteirização, sendo que

após a discretização, são somente 4.

54

FIGURA 29 – DISCRETIZAÇÃO DE PONTOS CORREDOR


Neste capitulo foi apresentada a fundamentação teórica vase para o

desenvolvimento das heurísticas propostas neste trabalho, alguns conceitos de

grafos, modelos e métodos para resolução do TSP e do AP.

55

4 IMPLEMENTAÇÕES

4.1 COMPARAÇÕES DE IMPLEMENTAÇÕES DO MÉTODO HÚNGARO

Foram realizados testes comparando os três métodos descritos na seção 3.3.2

para resolução do problema de designação, com intuito de se verificar qual obtém o

melhor desempenho, avaliado em tempo computacional à medida que o número de

designações ( ) aumenta. Para isso foram geradas 5 matrizes simétricas aleatórias

para cada tamanho , em seguida, a cada conjunto de 5 matrizes foi aplicado os 3

métodos de resolução e para cada método, o valor que aparece na TABELA 2 é a média

dos tempos de resolução.

TABELA 2 – COMPARAÇÃO ENTRE OS MÉTODOS DE RESOLUÇÃO PARA O AP

N Tempo médio (5 valores) Christofides Papadimitriou Loch

100 0,07 0,027 0,134 200 0,224 0,279 0,431 500 3,708 3,161 11,161 700 7,926 7,254 28,37 1000 31,871 30,897 134,69 2000 283,975 281,55 1054,51 3000 217,663 242,627 3557,49


Pela TABELA 2 então, para uma matriz de tamanho 100 x 100, a

implementação de Christofides obteve uma média de 0,07s, a de Papadimitriou de

0,027s e a de Loch de 0,134s. A última linha apresenta a média das médias para cada

método, percebe-se que neste, a implementação de Christofides se sobressai às

outras. No gráfico da FIGURA 30 são plotados os valores da TABELA 6.

A implementação utilizada neste trabalho foi a de Christofides

(CHRISTOFIDES, 1975).

56

FIGURA 30 – COMPARAÇÃO MÉTODOS DE RESOLUÇÃO DESIGNAÇÃO


4.2 MÉTODO DE EXPLORAÇÃO DA ÁRVORE

Para que uma busca explore a menor quantidade de nós possíveis em uma

árvore (resolução do TSP via árvores e AP, descrito na seção 3.3.3 – métodos exatos),

esta deve constantemente incorporar as informações armazenadas no nó. As buscas

propostas neste trabalho visam incorporar, além das informações que independem do

tipo de problema estudado, as características relevantes e intrínsecas ao TSP. As

características consideradas foram: 1) número de subrotas e 2) ligações com maior ou

menor custo.

Para isso, primeiramente foram realizados testes em instâncias do TSPlib

(http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html) para verificar qual tipo de

busca obtém melhores resultados.

Os testes foram realizados em 23 conjuntos de pontos do TSPlib, sendo que

destes a menor instância com 29 pontos e a maior com 2103. Cada instância foi

resolvida utilizando tanto os métodos de busca em largura quanto em profundidade pois

pela complexidade do problema, o tempo de testes (60 min) não permite que os

métodos explorem a árvore inteira, e desta forma pode haver diferenças nos resultados

encontrados por um ou por outro método.

Com os resultados obtidos nesta primeira etapa, verificou-se que a busca em

profundidade obteve melhores Bounds para o conjunto estudado. Desta forma, a nova

0

500

1000

1500

2000

2500

3000

3500

4000

100 200 500 700 1000 2000 3000

Tam

anho

da

mat

riz

Tempo (s)

Comparação métodos de designação

Christofides

Papadimitriou

Loch

57

busca apresentada neste trabalho parte da busca em profundidade, levando em

consideração o número de subrotas em cada nó da árvore e qual a ordem de

ramificações dos filhos de um determinado nó n.

Alteração 1

A primeira alteração realizada na busca em profundidade modifica qual nó será

expandido após a busca atingir o nível mais fundo da árvore. Testou-se duas novas

possibilidades para a escolha do próximo nó a ser expandido:

1) Escolher o nó com mais subrotas formadas, que possa ser expandido.

2) Escolher o nó com menos subrotas formadas, que possa ser expandido.

A FIGURA 31 apresenta o caminho de expansão para os três casos: busca em

profundidade tradicional (a), profundidade retornando ao nó com menos subrotas (b) e

retornando ao nó com mais subrotas(c). Os números ao lado nos nós indicam a

quantidade de subrotas existentes naquela solução, enquanto que os números dentro

dos nós indicam a sequência a ser explorada.

FIGURA 31 – ALTERAÇÃO 1


Alteração 2

58

Na medida em que os nós são ramificados, elementos recebem

sistematicamente o valor de ∞ para que alguma subrota da solução seja eliminada.

Dada uma subrota r composta pelos nós (1,3,2) é atribuído infinito aos elementos [(1,3),

(1,2)] – [(3,1), (3,2)] – [(2,1), (2,3)], gerando 3 novos subproblemas. Percebe-se que

existem tantas possibilidades de ramificação em um nó quantos forem os pontos da

sua menor subrota, no caso acima são três possibilidades.

A segunda alteração da busca em profundidade visa selecionar qual a melhor

ordem de expansão dos nós filhos, por meio de uma avaliação de custo dos arcos que

formam a subrota. O elemento (i, j) com menor (ou maior) custo é selecionado para que

as combinações sejam realizadas. Dessa forma, existem duas possibilidades para a

ordem de expansão dos filhos:

1. Realizar as combinações com os nós i ordenados de forma crescente

2. Realizar as combinações com os nós i ordenados de forma decrescente

A FIGURA 32 exemplifica as possibilidades de expansão do nó 2, de forma

decrescente (a) e crescente (b) de custos, com , e , a

numeração dentro dos nós se refere a ordem a que foram explorados.

FIGURA 32 – ALTERAÇÃO 2


4.3 HEURÍSTICA DE CORREÇÃO DE ROTAS EM CD

59

4.3.1 Descrição da heurística

Ao se discretizar os pontos de um corredor como descrito na seção 3.3.4, tem-

se que um aumento no número de pontos de coleta, não necessariamente implica em

um aumento dos pontos a serem considerados no roteamento, estes agora ficam

dependentes do número total de corredores com algum item a ser coletado.

Embora o número de pontos possa ficar reduzido, surge um problema de

factibilidade: simplesmente resolver o TSP não garante que todos os pontos de coleta

sejam visitados. A FIGURA 33 representa uma rota viável do TSP para os pontos

discretizados da FIGURA 29, porém inviável para o SPRP, na medida em que o arco

(1-(1,2)) deve, obrigatoriamente ser visitado, para que os itens entre os pontos 1 e 2

sejam coletados.

FIGURA 33 – ROTA INVIÁVEL SPRP


Desta forma, uma verificação deve ser realizada em cada corredor, a fim de

armazenar quais arcos do conjunto total devem ser visitados, para que não haja

infactibilidades. Os arcos que possuem tal característica são rotulado de “obrigatórios”

. Se um determinado conjunto de pontos possui um conjunto , e uma determinada

rota R não contém todos os arcos de , os arcos de que não estão contidos em R

são chamados de “violações”.

60

A heurística proposta tem por objetivo a identificação e posterior correção de

violações em um conjunto de rotas. Estas rotas são obtidas a partir da resolução em

árvore do TSP, armazenando todas aquelas que são viáveis.

O pseudocódigo da TABELA 4 explicita a rotina principal para implementação

computacional da heurística, nele estão algumas estruturas de dados necessárias à

compreensão do todo, são elas:

l_bounds: Lista de classes do tipo rota, cada classe do tipo rota, por sua vez, é

composta por uma lista de números inteiros, representando uma rota válida do TSP e

um número inteiro bound com o custo da rota.

arco: estrutura com duas variáveis inteiras.

hash_restricao: Mapa ordenado, em que a chave é o número do corredor e o

valor uma classe info_rest.

info_rest: Classe com 2 listas; l_bool_rest e l_bool_violacao, cada uma com

dois valores booleanos, o primeiro valor das listas l_bool_rest é preenchido como

verdadeiro se, para aquele corredor, existem pontos de coleta entre os pontos 1 e 2, e

o segundo valor também é verdadeiro se, entre os pontos 3 e 4 também existirem itens

a serem coletados (essas informações servem para garantir a obrigatoriedade de

passagem em alguns arcos).

Já os primeiros valores de l_bool_violacao recebem TRUE quando os mesmos

valores de l_bool_rest forem verdadeiros e o referido arco não está contida na rota, o

mesmo vale para o segundo valor, agora referentes aos pontos 3 e 4, Um exemplo da

hash_restricao para a FIGURA 33 é apresentado na TABELA 3

O conjunto info_rest verifica a factibilidade da rota para o SPRP.

TABELA 3 – RESTRIÇÕES VIOLAÇÕES CHAVE l_bool_restricao l_bool_violacao

1 TRUE TRUE

FALSE FALSE


TABELA 4 – PSEUDOCÓDIGO DA HEURÍSTICA DE CORREÇÃO DE ROTAS RESOLVE_SPRP()

61

1 solve_tsp(l_bounds)

Calcula_restricao(hash_restricao)

Melhor_bound <- integer.maxvalue

Iter <- n_l_bounds

Ordena_bounds(l_bounds)

2

3

4

5

6 Para i = 0 até iter

7 Limpa(rota_atual)

Limpa(hash_restricao)

Rota_atual <- l_bounds(i).rota

8

9

10 Fact_rota <- verifica_factibilidade_preenche_hash_restricao(rota_atual)

11 se (fact_rota == TRUE ) 12 Return

13 Fim se

14 Se (l_bounds.bound < melhor_bound)

15 Corrige_rota(rota_atual)

16 Custo_atual<-calcula custo(rota_atual) 17 se (custo atual<melhor_bound) then 18 melhor_bound <- custo_atual

19 Limpa(melhor_rota)

20 Melhor_rota<-rota_atual

21 Fim se 22 Fim se

23 Fim se


A primeira linha do código expande a árvore de busca para resolução do TSP,

armazenando todas as informações dos nós que possuem uma rota viável para o TSP

na lista l_bounds. A linha 2 calcula as listas l_bool_rest para o conjunto de pontos. A

linha 3 inicializa uma variável inteira com um valor muito alto (neste caso, o máximo

admissível para o tipo inteiro na máquina). A linha 4 recebe o número total de rotas

viáveis coletados e armazenados em l_bounds. Na linha 5 é realizado o ordenamento

da lista l_bounds crescentemente, em função de seus atributos bounds. O método de

ordenação aqui empregado foi o Heap Sort.

62

O laço de iteração da linha 6 percorre todos os elementos da lista l_bounds. As

linhas 7 e 8 reinicializam as variáveis rota_atual e hash_retricao e na linha 9 é feita a

atribuição à variável rota_atual a rota com índice i da lista l_bounds. A linha 10 atribui

à variável Fact_rota o valor TRUE se a rota atual já é viável para o SPRP. Para que

essa verificação seja realizada, todos os elementos das listas l_bool_violacao devem

ser TRUE, ou seja, nenhum corredor pode ter violação em seus arcos.

A verificação de violação por corredor, não necessariamente exige que um

determinado arco obrigatório (1-(1,2) por exemplo), esteja contido rota, qualquer arco

com ponto inicial em outro corredor, que se ligue ao ponto 2 do corredor 1, por meio do

CTI já satisfaz o critério de factibilidade.

A mesma lógica pode ser combinada a todos os pontos do corredor para

atribuição de FALSE às listas l_bool_violacao. Na FIGURA 34 tem-se os arcos

obrigatórios para o corredor 1 e na sequência (b,c e d) todas as possibilidades de

verificação para o segundo ponto do corredor 1 assumindo que o ponto ligado à ele

está também no 1º corredor.

FIGURA 34 – TIPOS DE VIOLAÇÕES


63

Os valores da lista l_bool_violacao para o corredor 1, em FIGURA 34 (a),

FIGURA 34 (b), FIGURA 34 (c) e FIGURA 34 (d), ficam (assumindo que todos são

inicializados com TRUE) como na TABELA 5:

TABELA 5 – LISTAS DE RESTRIÇÃO

L_bool_violacao

FIGURA 34(b) FALSE TRUE

FIGURA 34(c) FALSE FALSE

FIGURA 34(d) TRUE FALSE


Já na FIGURA 35, os pontos ligados ao ponto 2 do corredor 1 são de outro

corredor:

FIGURA 35 – RELIGAÇÕES DE ROTA


E os valores da lista l_bool_violacao ficam como mostrado na TABELA 6: TABELA 6 – LISTA DE VIOLAÇÕES

L_bool_violacao

DEP_7 (a) TRUE FALSE

DEP_7 (b) FALSE TRUE


64

Realizando o procedimento de verificação descrito acima, para todos os pontos,

em todos os corredores, verifica-se se a rota analisada é viável ou não para o SPRP.

As linhas 11, 12 e 13 do pseudocódigo tem por objetivo abortar a busca caso

alguma das rotas da lista l_bound seja viável para o SPRP, como inicialmente os

valores da lista foram ordenados, as próximas rotas que seriam avaliadas seriam piores

ou tão boas quanto a solução viável atual. Na linha 14, é realizada uma verificação do

custo associado à rota do TSP, caso o mesmo seja maior do que o melhor custo atual,

a rota não é corrigida (linha 15), na medida em que a correção de rotas não tem o

potencial de reduzir o custo, mas sim, na melhor hipótese, o manter constante.

A correção das rotas é realizada corredor a corredor, através do mapa

ordenado hash_rest para cada chave, se algum elemento da lista l_bool_violacao

estiver com valor TRUE, o corredor deve ser corrigido. Cada corredor pode ter no

máximo uma violação (haja vista que a solução sem correção é viável ao TSP), dessa

forma, a correção do corredor é feita por meio de 3 etapas:

Exclusão de arco.

Religação de arco removido.

Religação de arco viável.

Os arcos a serem removidos da rota dependerão da posição em que a violação

se encontra no corredor, X-(1,2) ou X-(3,4);

Se X-(1,2), remover os arcos que chegam ao 2º ponto.

Se X-(3,4), remover os arcos que chegam ao 3º ponto.

Os dois casos são mostrados na FIGURA 36, considerando que existem itens

a serem coletados tanto em 1-(1,2) como em 1-(3,4), os arcos em azul e vermelho

representam os que devem ser removidos.

65

FIGURA 36 – ARCOS A SEREM REMOVIDOS


A partir dos arcos excluídos, dois novos devem ser formados, religando-os ao

2º ou 3º ponto de cada corredor, dependendo, novamente, da localização da violação:

Se em X-(1,2), religar ao 3º ponto.

Se em X-(3,4), religar ao 2º ponto.

Na FIGURA 37 são mostrados os arcos religados da FIGURA 36:

FIGURA 37 – RELIGAÇÃO DE ARCOS


Dessa forma, a violação do corredor 1 foi removida. É importante ressaltar que

o processo descrito, pode por sua vez, gerar infactibilidade em locais em que as

66

mesmas não existiam previamente. Isso se deve ao fato de que sempre existem 2

caminhos entre 2 pontos em corredores diferentes (passando por CTI e CTS), pode

ocorrer que, após a remoção de um arco (que estava inicialmente passando pelo CTI),

o processo de religação com um ponto diverso dite que a menor distância entre os

pontos agora passa pelo CTS, quando isso ocorrer, ou seja, os custos dos arcos antes

e depois da remoção forem diferentes, deve-se forçar o valor a ficar igual o anterior.

Após a rota ser corrigida, seu novo custo é calculado (linha 16), e se for menor

do que o menor custo viável até o momento, o mesmo é substituído pelo menor

encontrado (linha 17). O cálculo do custo nesta etapa deve levar em consideração as

imposições realizadas sobre a matriz booleana, na medida em que o custo dos arcos

pode não necessariamente ser o que representa a menor distância.

Com esse algoritmo, todas as rotas que têm possibilidade de melhoria são

corrigidas, e ao final, a melhor destas é tomada como a solução.

4.4 HEURÍSTICA DE EMPACOTAMENTO

A heurística de empacotamento implementada neste trabalho é baseada no

paradigma de divisão e consquista, em que 3 etapas são consideradas.

Divisão do problema em certo número de subproblemas que são instâncias

menores do mesmo problema.

Conquista dos problemas, resolvendo-os recursivamente. Entretanto, se os

tamanhos dos subproblemas forem suficientementes pequenos, basta resolvê-los de

modo direto

Combinação das soluções dos subproblemas na solução do problema original

(CORMEN, 1996). Na heurística, o espaço a ser ocupado é recursivamente dividido em

outros espaços e ocupado por caixas, até o momento em que não existam mais

espaços ou caixas a serem alocadas.

4.4.1 Descrição da heurística

O método utilizado na heurística para atingir o objetivo parte da idéia de

recursivamente dividir o espaço (inicialmente o palete inteiro) em no máximo 3 outros

67

espaços do mesmo tipo, a divisão é realizada toda vez que uma caixa é alocada a um

espaço. Quando da ocorrência de uma inserção, os pontos do canto inferior esquerdo

do espaço e da caixa ficam iguais.

Os espaços gerados pelas inserções podem ser de 3 tipos, sendo eles:

-Espaço 0 (e0) : espaço criado na dimensão x da caixa.

-Espaço 1 (e1) : espaço criado na dimensão y da caixa.

-Espaço 2 (e2) : espaço criado na dimensão z da caixa.

A cada nova inserção de caixa, qualquer um dos 3 espaços pode ser gerado,

bem como uma combinação dos mesmos, ou até mesmo nenhum.

O espaço inicial (tracejado) e a primeira caixa inserida são representados na

FIGURA 38, na medida em que os três possíveis espaços gerados (e0 e1 e e2) são

ilustrados na FIGURA 39 (a), (b) e (c) ,respectivamente.

FIGURA 38 – INSERÇÃO DE ITEM NO OBJETO


68

FIGURA 39 – GERAÇÃO DE ESPAÇOS


Desta forma, a heurística consiste em sucessivas inserções de caixas em

espaços, e geração de novos espaços, o fluxograma da FIGURA 40 ilustra o processo.

69

FIGURA 40 – FLUXOGRAMA ROTINA EMPACOTAMENTO


70

Os espaços gerados e consumidos são armazenados em uma estrutura de

árvore em que cada nó representa um espaço gerado (na raiz da árvore está o espaço

total do palete), sendo que estes podem ou não conter caixas alocadas. Quando da

geração de um espaço, um teste de factibilidade é realizado; se a menor das dimensões

de todas as caixas é maior do que a menor dimensão do espaço, este é um espaço

descartado.

A exploração dos espaços da árvore é realizada recursivamente pelo

procedimento EXPANDE_NO, ver TABELA 7:

TABELA 7 – PSEUDOCÓDIGO EXPANDE_NO 1 Atualiza caixa

2 Gera espaço e0

3 Gera espaço e1

4 Gera espaço e2

5 Se(criterios criterios_continuidade() == FALSE) return;

6 Expande no(e0,caixa_atual)




A linha 1 atualiza o número de caixas a serem alocadas e em seguida os três

espaços podem ser gerados. Na linha 5 é verificado se ainda existem espaços para

inserção de caixas e caixas a serem alocadas. As linhas 6, 7 e 8 ditam em qual ordem

os espaços deverão ser preenchidos (na TABELA 7 a ordem de expansão é e0-e1-e2).

A ordem dos espaços expandidos pode ser alterada para levar em

consideração caracteristicas espaço inicial (palete, caminhão ou contêiner). Por

exemplo, se o espaço é referente a um caminhão ou mesmo um conteinêr, pode-se

iniciar a inserção pelo espaço e2, de forma que fica priorizada a formação de pilhas, como mostrado na FIGURA 41.

71

FIGURA 41 – TIPOS DE ESPAÇOS


A expansão de uma árvore pela combinação de espaços 2-0-1 junto às localizações dos objetos é mostrada na FIGURA 42, todos os nós da árvore possuem 3

arcos que representam os 3 possíveis espaços gerados, em ordem de 0 a 2 da

esquerda para a direita, e destes, os que estão com arcos pontilhados não foram

gerados.

72

FIGURA 42 – EXPANSÃO ARVORE DE CARREGAMENTO


Com os dados armazenados em árvore, é possível rastrear todas as caixas que

estão abaixo de uma determinada caixa, e que dessa forma são afetadas pela massa

da caixa recém inserida; para isso, basta percorrer todos os arcos pelo nós pais e

sempre que um destes for gerado pelo espaço 2, o nó pai possui uma caixa que será

afetada pela massa da caixa recém inserida.

73

Estas atualizações são mostradas na FIGURA 43, quando da atualização, os

arcos em vermelho na árvore indicam o caminho percorrido quando da geração por

espaços e2 e as caixas coloridas são aquelas afetadas pela nova inserção.

FIGURA 43 – EXPANSÃO ÁRVORE CARREGAMENTO EMPILHAMENTO MÁXIMO


74

Dessa forma, a cada inserção de uma nova caixa basta atualizar as massas acumuladas em todas as caixas da forma como é mostrado na FIGURA 43, e se alguma

caixa estiver com a massa acumulada maior do que a massa máxima, a inserção é

inviável.

A escolha da rotação que será utilizada na inserção da caixa é escolhida com

base na área ocupada sob o objeto (xy). Para todas as combinações de rotação que

não possuem restrições, calcula-se a razão (área espaço/área caixa) e seleciona-se

aquela que possuir a menor razão, ou seja, a rotação que fornece o maior

aproveitamento em área (x,y) sob o espaço.

4.5 HEURÍSTICA DE ESCOAMENTO DE PONTOS (HEP).

Duas abordagens poderiam ser utilizadas para que o roteamento e a carga

mantivessem uma interação entre si (BORTFELDT, 2013):

1- Determinar primeiro uma disposição de carga que seja viável entre todos os

pontos e as rotas já seriam determinadas, pois deve existir uma ordem de coleta.

2- Determinar primeiro um conjunto de pontos com alguma probabilidade de

terem o empacotamento viável, otimizar a rota e verificar se o empacotamento na

ordem determinada é possível.

A heurística utilizada segue a segunda idéia, na medida em que o objetivo é

minimizar os custos das rota, sempre escolhendo algum critério para selecionar pontos

e verificar se o conjunto selecionado é viável. O método tem duas fases principais,

encontrar uma solução inicial e buscar meios de melhorá-la.

Em ambas as partes o princípio utilizado é o mesmo aplicado de formas

diferentes; pontos sempre serão “transbordados” de uma rota a outra de forma a tentar

reduzir o custo de alguma das duas ou até mesmo eliminar a mesma do conjunto de

rotas. Desta forma, 4 estratégias de escoamento foram implementadas, a primeira para

encontrar a solução inicial e as restantes para a otimização. Após a realização do

transbordo, uma função de factibilização é responsavel por manter todas as rotas e

carregamentos viáveis, vale ressaltar que toda função de escoamento tem seus

argumentos passados por referência, de tal forma que se o custo da solução ao sair do

transbordo for menor do que o custo ao entrar, a solução já é atualizada.

A função de factibilização e as estratégias de transbordo são explicados a

seguir, seguido pelo fluxograma da HEP:

75

1- Função de factibilização (FF)

A entrada de dados da FF sempre será um conjunto de rotas e a saída um novo

conjunto em que todas as rotas são viáveis. A factibilidade é alcançada pela rotina descrita na TABELA 8, também representada em fluxograma na FIGURA 44:

TABELA 8 – PSEUDOCODIGO FUNÇÃO DE FACTIBILIZAÇÃO

1 Para todas as rotas na solução faça 2 Resolver o problema de empacotamento 3 Se solução viável

4 Se a rota for a última 5 Se o vetor V está vazio

5 Vá para 11 6 Senão

4 insira a rota do vetor V como última rota da solução 5 Fim se

6 Fim se

5 Senão 6 Se a rota atual é a última rota 7 inserir o último ponto da rota atual em um vetor V e

removê-lo da rota atual, 8 Senão 9 inserir o último ponto da rota atual na rota[rota+1] e

remover da rota atual 10 Fim se 11 Fim para


76

FIGURA 44 – FLUXOGRAMA ROTINA FACTIBILIZA


2- Escoamento inicial

O escoamento inicial é utilizado para que a primeira solução viável seja obtida.

O primeiro passo é resolver o problema de roteirização com todos pontos do problema.

O objetivo a partir desta etapa é de certa forma romper a rota inicial em subrotas que

tenham factibilidade no carregamento.

Como não há maneira de se saber se existe uma solução viável para um

determinado conjunto de caixas sem aplicar algum algoritmo, uma estimativa é

realizada com base nos volumes: começando no ponto inicial da rota, até o último.

Calcula-se o volume acumulado nos pontos e quando esse volume atinge um certo

77

percentual do volume total do objeto a rota é segmentada e o processo é

recomeçado.

Ao fim desse processo, tem se um conjunto de rotas em que os volumes

máximos das mesmas não ultrapassam ) como na FIGURA 45, em

seguida, o conjunto é submetido a função de factibiliação.

FIGURA 45 – VOLUME OCUPADO POR ROTAS


3- Escoamento Menor

A idéia do escoamento menor é a de se reduzir rotas e não o custo de uma

única rota. Para isso, tenta-se alocar os pontos das rotas com volumes mais baixos à

outras rotas com volumes baixos, o processo pode continuar sempre em que alguma

alteração gerar um custo total menor do que o custo antes da alteração. O pseudo

código do escoamento é apresentado na TABELA 9:

TABELA 9 – ESCOAMENTO MENOR Escoamento menor(solucao)

78

1 Ordenar de forma não decrescente as rotas em relação aos volumes totais 2 Para até total de rotas -1.

3 Para até número de rotas 4 Encontrar o ponto com volume total menor dentre a

5 Escoar o ponto para a

6 Aplicar função de factibilização na solução 7 Se o custo da nova solução for menor do que o da solução inicial 8 solução inicial = solucao atual 9 Fim se

10 Fim para 11 Fim para


O processo do escoamento inicial procura a rota com menor volume (maior

potencial de ser eliminada) e tenta escoar os seus pontos em outras rotas com volumes

mais baixos, processo representado pela FIGURA 46.

FIGURA 46 – ESCOAMENTO DE ROTAS MENOR


3- Escoamento Maior

Pode acontecer de, ao se submeter uma rota ao escoamento menor, o menor

volume de uma rota seja devido a uma quantidade pequena de caixas, cada uma com

volume alto, dessa forma a probabilidade destas caixas serem alocados à outras rotas

é muita baixa, por esse motivo foi implementado o escoamento maior, que segue todas

as idéias do escoamento menor exceto pela escolha a rota a se realizar o transbordo,

aqui a rota escolhida é a de maior volume, de forma que o vetor inicial deve ser

ordenado de forma não crescente em realação aos volumes.

79

4- Escoamento Aleatório

O escoamento aleatório é responsável pela diversificação nas solução, nele,

uma rota é selecionada aleatoriamente e desta rota, um ponto também o é. Em seguida

uma segunda rota é selecionada aleatoriamente e o ponto da primeira rota é escoado

para a segunda.

Escoamentos da HEP

Como visto, os métodos de escoamento são independentes uns dos outros e

podem ser aplicados em qualquer ordem, um número de vezes qualquer. Por esse

motivo alguns testes foram realizados com algumas destas combinações para avaliar

se algum dos escoamentos se sobressai sobre os outros ou, até mesmo, se algum não

desempenha nenhuma melhoria. Os resultados dos testes serão apresentados em mais

detalhes nas seções de resultados.

De forma geral, a lógica dos escoamentos utilizados na HEP é apresentado na

TABELA 10:

TABELA 10 – PSEUDOCÓDIGO DA HEURISTICA HEP

1 sol_inicial = escoamento_inicial()

2 escoamento_de_caixas_menor(sol_inicial)

3 escoamento_de_caixas_maior(sol_inicial)

4 Faça

80

5 melhoria = false;

6 custo = sol_inicial.custo_total

7 Para

8 escoamento_de_caixas_aleatorio(sol_inicial); //aleatorio_2

9 Se sol_inicial.custo_total < custo

10 melhoria = true;

11 escoamento_de_caixas_menor(sol_inicial)

//aleatorio_1

12 Fim se

13 Fim para

14 Enquanto (melhoria == true)


Ou seja, primero se encontra uma solução inicial, aplicando o escoamento

menor seguido do maior. Após esta etapa, aplica-se a parte aleatória do algoritmo, o

escoamento aleatório é aplicado até 100 vezes na solução. Se em alguma destas a

solução for melhorada, o escoamento melhor é então aplicado e uma nova rodada de

100 aleatórios é realizada. O processo só é interrompido se em alguma rodada de 100

resoluções, nenhuma melhorar a solução atual.

Neste capitulo foram apresentadas as heurísticas de correção de rotas,

carregamento e roteirização com carregamento.

81

5 RESULTADOS E DISCUSSÃO

Nesta seção são discutidos os resultados obtidos pelos testes computacionais

das heurísticas propostas no trabalho; correção de rotas, carregamento e roteamento

com carregamento.

5.1 HEURÍSTICA DE CORREÇÃO DE ROTAS EM CD

O algoritmo de correção de rotas foi programado na linguagem de programação

VB.Net, na IDE Visual Studio Community. Foi desenvolvido um aplicativo para geração

das soluções visuais das rotas no CD, na medida em que a simples leitura de uma

resposta não é garantia de que a solução está viável, uma instância resolvida é

mostrada na FIGURA 47. FIGURA 47 – VISUALIZAÇÃO DA HEURISTICA DE CORREÇÃO DE ROTAS


82

Para se avaliar a viabilidade de utilização da heurística proposta, testes

comparativos foram realizados comparando-a a 3 métodos, todos com duração máxima

de 1 hora:

Formulação do TSP proposta por Dantzig, aplicando a lazy constraints.

Formulação do TSP proposta por Miller, Tucker e Zemlin.

Heurística do ponto médio.

Foram geradas instâncias para um CD com 10 corredores, cada um contendo

45 pontos de coleta (nos lados esquerdo e direito, totalizando 90 pontos por corredor

atravessado). As posições dos pontos de coleta em cada corredor foram gerados

aleatoriamente por uma distribuição uniforme, entre 1 e 45, com incremento de 5 pontos

entre uma instância e outra e, desta forma, têm se a seguinte notação:

C_P: em que a instância contém C corredores com P pontos de coleta

Ao se terminar o preenchimento de um corredor (45 pontos), o próximo começa

a ser preenchido da mesma forma, porém acumulando os pontos dos anteriores, no

caso:

2_5: Contem 45 pontos do corredor 1 mais 5 do corredor 2, totalizando 50

pontos.

Para que se possa avaliar as duas partes da heurística (a resolução do TSP

em árvores e as correções de rotas) os dois tempos foram coletados separadamente.

Além dos tempos de resolução para a heurística, foram coletados também; as

distâncias totais das rotas, o número total de Bounds do TSP (N Bounds_tsp)

encontrados durante a exploração da árvore, se algum destes já é viável ao SPRP

(Bound_SPRP) e o melhor Bound encontrado para o SPRP (com correção ou já viável

- BB_SPRP).

Os resultados da TABELA 11 dizem respeito então, a uma instância com dois

corredores com 45 pontos cada, e um terceiro com 10, totalizando 100 pontos, em

que ambos os modelos, DFJ e de Miller, não obtiveram êxito em encontrar o ótimo. A

heurística de correção encontrou uma solução de distância total 248, levando 0,568s

para expandir a árvore completa do TSP e mais 0,323s para a correção das rotas

inviáveis as SPRP. O número total de rotas coletadas na árvore foi de 315, sendo que

destes o de número 310 já era viável ao SPRP, porém a melhor solução foi a de

número 288, que foi corrigida. A distância pela roteirização utilizando a heurística do

ponto médio foi de 144.

83

TABELA 11 – RESULTADO HEURISTICA DE CORREÇÃO Lazy Tucker Correção em Árvore

Instância T Z T Z T Z T_CORRECAO N Bounds_tsp Bound_SPRP BB_SPRP midpoint

3_10 - - - - 0,56 248 0,32 315 310 288 144 FONTE: O autor (2018).

Com os resultados coletados, além de avaliar e comparar a heurística, também foi

realizada uma análise do método de resolução do TSP via árvores. Para cada conjunto

de instâncias de mesmo corredor, em que a heurística encontrou resultados, os tempos

foram agrupados (pois o número de pontos discretizados cresce junto ao número de

corredores), e a média de todos calculada, bem como seus tempos mínimos e

máximos. Os resultados estão na TABELA 12 e ilustrados no gráfico da FIGURA 48,

em escala logarítmica.

TABELA 12 – TEMPOS RESOLUÇÃO TSP EM ARVORE Pontos Tempo médio Mínimo Máximo

4 0,037 0,033 0,044

8 0,046 0,04 0,06

12 1,224 0,102 0,452

16 258,764 0,635 1535,787

20 823,898 1,793 3570,514

24 1880,630 1654,879 2106,38


84

FIGURA 48 – GRÁFICO DE TEMPOS RESOLUÇÃO TSP ÁRVORES


TABELA 12 fica evidente que o método de resolução do TSP não é competitivo,

principalmente para as aplicações em CD propostas neste trabalho, as quais exigem

que as rotas sejam calculadas muitas vezes em um curto período de tempo. Isso se

deve ao fato de se tratar de um problema com matrizes simétricas e o método de

resolução prevê matrizes assimétricas.

Na TABELA 13 então, os 4 métodos de resolução são comparados.

TABELA 13 – RESULTADOS HEURISTICA DE CORREÇÕES

Lazy Tucker Correção em Árvore

Instância

Tempo

Z Tempo

Z Tempo Z T_CORRECAO

N Bounds_tsp

Bound_SPRP

BB_SPRP

midpoint

0 1 2 3 4 5 6 7 8 9

1_5 0,095 108

0,033 108

0,037 108

- - - - -

1_10 0,078 116

1,158 116

0,035 116

- - - - -

1_15 0,101 112

4,04 112

0,037 112

- - - - -

1_20 0,114 120

4,56 120

0,044 120

- - - - -

1_25 0,332 114

13,28 114

0,033 114

- - - - -

1_30 0,341 114

13,64 114

0.035 114

- - - - -

1_35 0,686 120

- 120

0,04 120

- - - - -

1_40 2,313 116

- 116

0,034 116

- - - - -

-4

-2

0

2

4

6

8

10

4 8 12 16 20 24

Tempo x Número de pontos

Tempo médio mínimo máximo

85

1_45 2,328 114

- 114

0,034 114

- - - - -

2_5 0,068 134

- - 0,04 134

- - - - -

2_10 0,591 134

- - 0,048 134

- - - - -

2_15 0,137 134

- - 0,06 134

- - - - -

2_20 0,151 134

- - 0,055 134

- - - - -

2_25 0,246 134

- - 0,041 134

- - - - -

2_30 0,9 134

- - 0,041 134

- - - - -

2_35 0,371 134

- - 0,044 134

- - - - -

2_40 0,152 134

- - 0,042 134

- - - - -

2_45 0,466 134

- - 0,041 134

- - - - -

3_5 - - - - 0,452 268

0,176 111 - 0 144

3_10 - - - - 0,568 248

0,323 315 310 288 144

3_15 - - - - 0,25 252

0,25 145 - 144 142

3_20 - - - - 1,467 258

0,31 323 319 1 146

3_25 - - - - 2,222 258

0,986 1091 - 336 146

3_30 - - - - 1,235 258

0,649 683 - 1 146

3_35 - - - - 0,102 260

0,055 33 - 1 146

3_40 - - - - 3,834 258

2,079 2335 - 70 146

3_45 - - - - 1,107 260

0,749 825 - 4 146

4_5 - - - - 4,31 382

1,171 1181 - 1171 272

4_10 - - - - 10,629 380

2,438 1681 - 1367 272

4_15 - - - - 232,477 372

182,554 24223 - 3360 274

4_20 - - - - 1535,787

374

795,87 437382 - 1401 274

4_25 - - - - - - - - - - 274

4_30 - - - - 20,104 382

3,112 2071 - 486 276

4_35 - - - - 0,635 378

0,337 204 - 186 276

4_40 - - - - 7,408 276

2,157 2201 1451 1450 276

4_45 - - - - 17,388 370

5,283 3773 - 11 270

5_5 - - - - 38,943 510

7,087 3536 - 1 402

5_10 - - - - 1,793 508

1,112 577 - 1 406

5_15 - - - - 117,073 402

38,611 20129 - 19595 402

5_20 - - - - - - - - - 402

5_25 - - - - - - - - 406

5_30 - - - - 9,393 510

3,686 1305 - 1 404

5_35 - - - - 3570,514

506

1756,125 468828 - 1 398

86

5_40 - - - - - - - - 398

5_45 - - - - 49,266 514

9,51 2731 - 1 404

6_5 - - - - 197,263 528

63,506 16617 - 3997 526

6_10 - - - - 2085,97 528

1084,041 250476 - 132232 532

6_15 - - - - 80,263 608

17,659 3723 - 3663 536

6_20 - - - - - - - - 532

6_25 - - - - 2088,505

538

466,077 102345 - 45775 534

6_30 - - - - 322,984 562

88,405 16715 - 15996 528

6_35 - - - - - - - - - - 532

6_40 - - - - 23,369 638

13,943 2758 - 2758 532

6_45 - - - - - - - - - - 532

7_05 - - - - - - - - - - 654

7_10 - - - - - - - - - - 660

7_15 - - - - - - - - - - 662

7_20 - - - - 1654,879

690

463,912 78440 - 78100 664

7_25 - - - - 2106,38 690

678,946 93507 - 93371 666

7_30 - - - - - - - - - - 662

7_35 - - - - - - - - - - 654

7_40 - - - - - - - - - - 660

7_45 - - - - - - - - - - 658

8_5 - - - - - - - - - - 790

8_10 - - - - - - - - - - 792

8_15 - - - - - - - - - - 792

8_20 - - - - - - - - - - 782

8_25 - - - - - - - - - - 778

8_30 - - - - - - - - - - 782

8_35 - - - - - - - - - - 790

8_40 - - - - - - - - - - 794

8_45 - - - - - - - - - - 790

9_5 - - - - - - - - - - 918

9_10 - - - - - - - - - - 918

9_15 - - - - - - - - - - 918

9_20 - - - - - - - - - - 918

9_25 - - - - - - - - - - 918

9_30 - - - - - - - - - - 920

9_35 - - - - - - - - - - 918

9_40 - - - - - - - - - - 922

9_45 - - - - - - - - - - 916

10_5 - - - - - - - - - - 1052

10_10 - - - - - - - - - - 1036

10_15 - - - - - - - - - - 1046

10_20 - - - - - - - - - - 1050

87

10_25 - - - - - - - - - - 1052

10_30 - - - - - - - - - - 1048

10_35 - - - - - - - - - - 1046

10_40 - - - - - - - - - - 1052

10_45 - - - - - - - - - - 1052


5.2 HEURÍSTICA DE EMPACOTAMENTO

Os algoritmos de empacotamento e a heurística HEP foram programados na

linguagem de programação C++ usando a IDE Qt, na distribuição Ubuntu do sistema

operacional Linux. Todas as análises estatísticas foram realizadas no Software R.

Para que as verificações de factibilidade da carga pudessem ser validadas mais

facilmente, um software gráfico foi programado utilizando a API OpenGL junto ao Qt,

para que a carga pudesse ser visualmente validada, a interface do software é mostrada

nas FIGURA 49 e FIGURA 50.

FIGURA 49 – VISUALIZAÇÃO DE CARGA 1


88

FIGURA 50 – VISUALIZAÇÃO DE CARGA 2


Para se avaliar a capacidade da heurística de empacotamento, 200 instâncias

foram geradas para cada uma das três situações: carregamentos simples,

carregamento com restrições de massa e carregamento com restrições de massa

e rotação das caixas.

Os dados foram gerados da seguinte maneira: Todas as variáveis aleatórias utilizadas na geração das instâncias seguem a

distribuição uniforme U(a,b).

As instâncias do tipo foram geradas com as dimensões de uma palete

cúbico (x=y=z) iniciando com valor de 5 e com incremento de 5. Para cada dimensão

de palete, 10 instâncias foram criadas variando o número de coletas a serem

realizadas, iniciando em 5 com incremento unitário a cada aumento nas dimensões do

palete. Todas as instâncias tem 5 tipos de caixas diferentes e suas 3 dimensões

geradas por U(1,0.2*dimensão do palete).O tipo de caixa de um ponto é selecionado

por U(1,total de caixas). O número de caixas em cada coleta é selecionado por

U(0.1*vol. palete, 0.4*vol. palete). Uma vez determinado o volume do ponto, o número

de caixas é determinado pela razão volume_ponto/volume caixa.

As instâncias do tipo geram também, para cada caixa, um número U(1,4)

que representa a massa da caixa, e outro U(4,6) sendo a massa máxima que a caixa

aguenta sobre si. Nas instâncias do tipo ainda são inseridas restrições de rotação

89

das caixas, onde U(1,3) caixas podem ter restrições de rotação e para cada caixa que

tiver U(1,4) rotações podem ser selecionadas como restritas.

Como mostrado na descrição da heurística, os tipos de espaços (e0, e1 e e3),

podem ser utilizados em qualquer ordem, por esse motivo 3 destas combinações foram

testadas.

Para as instâncias do tipo , foram realizados 3 testes, todos com intuito de

verificar qual das estratégias de utilização de espaços é mais eficaz (2-1-0 , 2-0-1 ,1-2-

0). Cada uma destas expansões guarda relações com a topologia geral em que as

caixas serão inseridas no palete; se da intenção de privilegiar a formação de pilhas, a

preferência será das estratégias que começam pelo espaço ‘2’, se, por outro lado, um

padrão de preenchimento em camadas horizontais é preferível, deve-se começar a

inserção com ‘0’ ou ‘1’.

Com os resultados, as médias da medida

Foram coletadas, para todas as instâncias com tamanhos de palete iguais (10 para

cada), como mostrado na TABELA 14 e na FIGURA 51.

TABELA 14 – RESULTADOS MÉDIA CARREGAMENTO

x,y,z Palete 2_1_0 2-0-1 1-2-0 Aproveitamento volume palete

5 100,00% 100,00% 100,00% 10 97,54% 77,82% 96,00% 15 91,42% 81,17% 85,94% 20 90,95% 80,59% 86,37% 25 91,95% 64,39% 86,50% 30 91,82% 55,34% 86,01% 35 84,55% 57,61% 78,85% 40 79,23% 48,42% 71,02% 45 88,26% 71,91% 77,29% 50 82,42% 67,52% 76,00% 55 86,40% 43,73% 75,69% 60 82,21% 43,81% 73,94% 65 79,87% 53,36% 69,84% 70 80,13% 59,77% 72,06% 75 73,53% 25,59% 64,41% 80 77,88% 56,77% 67,02% 85 79,11% 53,03% 74,19% 90 75,73% 54,15% 63,46% 95 74,03% 48,94% 62,15%

100 72,88% 52,54% 64,77% FONTE: O autor (2018).

90

FIGURA 51 – GRAFICO APROVEITAMENTO CARREGAMENTO MÉDIO


Pela análise do gráfico, percebe-se que a estratégia 2-0-1 detém um melhor

aproveitamento do palete em relação as outras, para que se possa afirmar

estatisticamente que as estratégias tiveram um desempenho diferente, um teste de

análise de variância (ANOVA) (MONTGOMERY, DOUGLAS, 1997) para comparação

de médias foi aplicado no software R, o teste rejeitou a hipótese de igualdade entre as

médias (valor p < 0.01), com isso, foi realizado um teste Tuckey (MONTGOMERY,

DOUGLAS, 1997) para comparações múltiplas entre as médias, como mostrado na

FIGURA 52, o qual também rejeitou a hipótese de igualdade entre as médias, quando

comparados dois a dois.

0%

20%

40%

60%

80%

100%

120%

5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100

Volu

me

ocup

ado

Coordenadas x,y,z palete

Aproveitamento palete X Tamanho palete

2_1_0 2_0_1 1_2_0

91

FIGURA 52 – INTERVALOS COM 95% DE CONFIANÇA PARA COMPARAÇÃO DE MÉDIAS


Ainda com as instâncias e utilizando a estratégia de expansão 2-1-0, mais

duas variações foram testadas com relação a escolha da rotação da caixa a ser inserida

no espaço; selecionar a caixa que nas dimensões apresentarem a maior e a

menor ocupação de área no espaço que será inserida. Os resultados, compilados da

mesma forma que os testes de estratégias, são mostrados na TABELA 15 e no FIGURA

53.

92

TABELA 15 – APROVEITAMENTO MÉDIO VOLUME PALETE x,y,z Palete maior área menor área

Aproveitamento volume palete 5 93,76% 96,36%

10 83,98% 90,79% 15 85,76% 90,33% 20 86,82% 89,18% 25 85,29% 86,43% 30 75,86% 82,34% 35 72,11% 76,68% 40 77,18% 81,11% 45 75,95% 77,73% 50 75,02% 80,21% 55 74,83% 71,76% 60 70,59% 76,07% 65 65,02% 74,61% 70 65,56% 68,13% 75 69,06% 74,17% 80 66,63% 75,03% 85 67,30% 71,65% 90 63,22% 67,82% 95 58,90% 63,96% 100 72,88% 52,54%


FIGURA 53 – APROVEITAMENTO MÉDIO VOLUME PALETE


0%

20%

40%

60%

80%

100%

120%

5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100

Volu

me

ocup

ação

Coordenadas x,y,z palete

Aproveitamento palete x Tamanho Palete

2_1_0_maior_area 2_1_0 menor area

93

5.3 HEURÍSTICA DE ESCOAMENTO DE PONTOS (HEP).

Como a heurística de correção não obteve um bom desempenho nos testes

computacionais, uma implementação da heurística Lin-Kernighan (LIN; KERNIGHAN,

B, 1973) foi utilizada para a parte de roteirização da HEP. As instâncias da HEP foram geradas como as de carregamento do tipo ,

com o acréscimo de um número de corredores e um número de pontos, para cada

combinação (corredores,pontos) 10 instâncias diferentes foram geradas.

Para se avaliar o desempenho dos diversos escoamentos na heurística HEP,

as seguintes estratégias foram adotadas:

1 - escoamento inicial

2 - escoamento inicial + escoamento menor

3 - escoamento inicial + escoamento menor + escoamento maior

4 - escoamento inicial + escoamento menor + escoamento maior + aleatorio1

5 - escoamento inicial + escoamento menor + escoamento maior + aleatorio2

Aleatório1 :Realizar o escoamento aleatório descrito na SEÇÃO 1 até 100

vezes. Se em alguma destas houver redução no custo da solução, aplicar o

escoamento de caixas menor e retomar as 100 iterações. Se em nenhuma iteração

houver melhoria a função é abortada

Aleatorio2: Realizar o escoamento aleatório descrito na SEÇÃO 1 seguido do

escoamento menor até 100 vezes. Se em alguma destas houver redução no custo da

solução, retomar as 100 iterações. Se em nenhuma iteração houver melhoria a função

é abortada.

Para cada resolução, o valor:

foi calculado, ou seja, a porcentagem de melhoria decorrente da estratégia de

escoamento considerada. Esses valores foram agrupados por números de pontos e

suas médias foram aferidas, como mostrado na TABELA 16 e plotados no gráfico da

FIGURA 54.

94

TABELA 16 – PORCENTAGEM DE MELHORIA POR ESTRATEGIAS

N de pontos sol_inicial sol_inicial

_menor sol_inicial_me

nor_maior sol_inicial_menor_maior_aleatorio1

sol_inicial_menor_maior_aleatorio2

10 0 9,322% 0,618% 7,898% 10,921% 15 0 0,524% 0,618% 7,898% 10,921% 20 0 3,893% 7,729% 15,200% 15,389% 25 0 10,195% 10,195% 13,659% 15,231% 50 0 5,563% 6,351% 8,824% 9,659% 55 0 9,184% 9,637% 11,486% 10,104% 60 0 4,267% 4,413% 8,789% 9,261% 65 0 5,342% 5,702% 7,956% 7,381% 75 0 4,874% 5,465% 8,191% 8,349% 80 0 5,940% 7,566% 10,159% 10,658% 85 0 3,723% 4,809% 7,033% 7,261% 90 0 4,582% 4,826% 6,439% 6,289% 100 0 6,063% 6,398% 8,793% 8,031% 105 0 9,186% 11,205% 11,865% 13,450% 110 0 6,232% 6,988% 8,310% 7,673% 115 0 4,486% 5,429% 8,875% 8,700%


FIGURA 54 – PERCENTUAL DE MELHORIA


0

0,02

0,04

0,06

0,08

0,1

0,12

0,14

0,16

0,18

10 15 20 25 50 55 60 65 75 80 85 90 100 105 110 115

Mel

horia

da

solu

ção

inici

al

Número de pontos

% Melhoria da estratégia x Número de Pontos

sol_inicial sol_inicial_menorsol_inicial_menor_maior sol_inicial_menor_maior_aleatorio1sol_inicial_menor_maior_aleatorio2

95

Os tempos médios em segundos de resolução também foram coletados

(médias em relação ao número de pontos) para todas as estratégias, como mostrado

na TABELA 17

TABELA 17 – MÉDIAS DE TEMPOS RESOLUÇÃO HEP

Número de

pontos sol_inicial sol_inicial+menor sol_inicial+menor+

maior sol_inicial+menor+maior+

aleatorio1

sol_inicial+menor+maior+aleatorio2

10 0,001 0,0014 0,0018 0,0536 0,1088 15 0,0022 0,0044 0,0076 0,2422 0,5168 20 0,0028 0,0086 0,0124 0,39 1,1262 25 0,0052 0,0232 0,034 1,0954 2,3238 50 0,0182 0,1452 0,2384 8,4502 22,1724 55 0,0328 0,3338 0,546 13,0408 31,1574 60 0,036 0,3558 0,5692 27,1496 58,765 65 0,0426 0,3364 0,5868 28,2664 44,1126 75 0,0572 0,8138 1,4416 25,7678 94,6116 80 0,0802 1,2552 1,9818 84,0532 179,407 85 0,035 0,7158 1,2344 56,6544 128,502 90 0,0916 0,8344 1,6318 76,9312 142,1288 100 0,1836 3,4498 5,235 124,1856 363,783 105 0,2266 5,722 8,5508 27,696 401,2188 110 0,1368 2,5714 4,7908 39,0494 292,5748 115 0,182 3,9622 7,6124 247,4114 341,067


Os gráficos de tempos das estratégias aleatórias, FIGURA 56, foram plotados

separadamente dos outros, FIGURA 55, na medida em que consumiram uma

quantidade muito maior de tempo, e isso impediria as outras representações de serem

visualizadas.

96

FIGURA 55 – GRÁFICO TEMPOS DE RESOLUÇÃO HEP


FIGURA 56 – GRÁFICO TEMPOS DE RESOLUÇÃO HEP


0,00

1,00

2,00

3,00

4,00

5,00

6,00

7,00

8,00

9,00

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Tem

po to

tal (

s)

Número de pontos

% Tempos de resolução x Número de Pontos

sol_inicial sol_inicial+menor sol_inicial+menor+maior

0,00

50,00

100,00

150,00

200,00

250,00

300,00

350,00

400,00

450,00

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Tem

po to

tal (

s)

Número de pontos

%Tempos de resolução x Número de Pontos

sol_inicial+menor+maior+aleatorio1 sol_inicial+menor+maior+aleatorio2

97

6 CONSLUSÕES

Neste trabalho foi apresentada uma proposta de heurística (HEP) para o

CSPRP. Para o desenvolvimento desta, duas outras heurísticas foram propostas e

avaliadas, uma para o SPRP (heurística de correção de rotas) com uma discretização

dos pontos do CD e uma de empacotamento, para a inserção das caixas no palete de

coleta.

A heurística de correção de rotas parte da resolução do TSP via AP e uma

estrutura em árvore de decisões, 3 métodos de resolução do AP foram implementados

e comparados entre si, sendo que a implementação de Christofides se sobressaiu. O

método de resolução do TSP via árvores foi então implementado e um estudo realizado

para se verificar qual abordagem (busca em largura ou em profundidade) de exploração

da árvore encontrava a solução mais rapidamente.

Os melhores resultados foram atingidos com a busca em profundidade, que foi

em seguida utilizada como base para uma nova proposta de busca, que considera

informações sobre as subrotas geradas para guiar a exploração de nós.

O desempenho do método de resolução do TSP se mostrou eficiente apenas

em instâncias muito pequenas (até 15 pontos), pois como a matriz de distâncias no CD

é simétrica, as ramificações possíveis na árvore ficam duplicadas (espelhadas), de

forma que a exploração completa da árvore demanda muito tempo e espaço em

memória.

A heurística de correção de rotas não obteve um bom desempenho

computacional. Comparando os resultados com os valores obtidos pela heurística do

ponto médio, percebe-se que a proposta não é viável por dois motivos:

Se por um lado o número de pontos é reduzido, o tempo requerido

para que o TSP seja resolvido pelo método de busca em árvore se

mostrou ineficiente quando aplicado em matrizes simétricas.

A reconstrução da rota para que exista a factibilidade do SPRP pode

deixar as distâncias muito maiores, na medida em que pode ser mais

vantajoso atravessar um corredor por completo, ao invés de remover

o arco central e retornar ao local de entrada.

98

A heurística de carregamento proposta se mostrou muito rápida (menos de 1

segundo por empacotamento) e com um percentual de volume ocupado alto (em média

85% sem restrições de empilhamento e 64% com as restrições), além de considerar o

empilhamento máximo das caixas (restrição abordada em poucas heurísticas da

literatura (BORTFELDT; WÄSCHER, 2013)).

Pela observação do gráfico da FIGURA 54, nota-se que existe uma tendência

em todos os conjuntos, no sentido de um desempenho superior na % de melhoria das

duas estratégias aleatórias, em compensação, seus tempos para solução também

foram superiores, FIGURA 56.

Com o algoritmo de (LIN; KERNIGHAN, B, 1973) e a heurística de

empacotamento, uma nova proposta de heurística de roteirização em CD (HEP) foi

proposta, com as considerações de carga LIFO e empilhamento máximo.

Pelos resultados computacionais, conclui-se que a heurística HEP garante

soluções iniciais com pouco processamento computacional, até para os maiores

problemas testados (170 pontos com uma média de 1800 caixas), e ainda, todas as

propostas de melhoria da solução inicial surtiram efeito, as que obtiveram melhor

desempenho (aleatorio1 e aleatorio2) com um tempo computacional médio de 5,5

minutos.

Muito ainda pode ser feito na HEP, principalmente na parte relacionada ao

carregamento, algumas delas são listadas abaixo:

Ao invés de massa máxima, adaptar o empilhamento para pressão

máxima suportada pela caixa, o que é mais fidedigno à realidade, na

medida em que somente uma porcentagem de área da superfície seria

afetada, como mostrado na FIGURA 57.

99

FIGURA 57 – EMPILHAMENTO MÁXIMO - PRESSÃO


Estudar um método mais rigoroso para a seleção da rotação a ser

utilizada, não somente maior e menor área, talvez a rotação que ocupe a

maior parte de alguma dimensão ou, até mesmo, ser variável de acordo

com o tipo de estratégia de ocupação de espaços utilizada.

Criar um novo método para utilização dos espaços, que não seja recursivo

ou, até mesmo, inserir uma nova, que percorra toda a árvore buscando

novos espaços para que as caixas possam ser inseridas.

Criar um mecanismo para a junção de espaços não utilizados; pode

acontecer de existir uma caixa que caiba em não um, mas em dois

espaços contíguos entre si, com , no momento os espaços são

descartados, mas se os dois fossem unidos em um novo espaço maior, a

caixa poderia ser alocada.

Criar um modelo matemático de programação linear que descreva o

problema para que se possa, pelo menos para instâncias pequenas,

realizar uma comparação na qualidade da solução da HEP.

Utilizar um método de roteirização com melhor desempenho do que a

heurística Lin-Kernighan.

Ao invés de se escoar pontos para melhorar as rotas, utilizar uma

adaptação do algoritmo de Split (CHU et al., 2006) que leve em

consideração os posicionamentos das caixas e não somente o volume

ocupado veículo.

100

REFERÊNCIAS

ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H. Pesquisa Operacional para Cursos de Engenharia. 2007.

AUTHORITY, T. V. The Bottleneck Traveling Salesman Problem : Algorithms and

Probabilistic Analysis. Journal of the Associaton for Computing Machinary, v. 25, n.

3, p. 435–448, 1978.

BALAS, E.; CHRISTOFIDES, N. A restricted Lagrangean approach to the traveling

salesman problem. Mathematical Programming, v. 21, n. 1, p. 19–46, 1981.

BEKTAS, T. The multiple traveling salesman problem: An overview of formulations and

solution procedures. Omega, v. 34, n. 3, p. 209–219, 2006.

BELLMORE, M.; MALONE, J. C. Pathology of Traveling-Salesman Subtour-Elimination

Algorithms. Operations Research, , n. December 2015, 1971.

BONOMIT, E. The N-City Travelling Salesman Problem : Statistical Mechanics and the

Metropolis Algorithm. SIAM Review, v. 26, n. 4, p. 551–568, 1984.

BORTFELDT, A. Computers & Operations Research Packing first , routing second — a

heuristic for the vehicle routing and loading problem. , v. 40, p. 873–885, 2013.

BORTFELDT, A.; MACK, D. A heuristic for the three-dimensional strip packing problem.

European Journal of Operational Research, v. 183, p. 1267–1279, 2007.

BORTFELDT, A.; WÄSCHER, G. Constraints in container loading-A state-of-the-art

review. European Journal of Operational Research, v. 229, n. 1, p. 1–20, 2013.

Elsevier B.V. Disponível em: <http://dx.doi.org/10.1016/j.ejor.2012.12.006>. .

CARPANETO, G.; TOTH, P. Some New Branching and Bounding Criteria for the

Asymmetric Travelling Salesman Problem. Management Science, v. 26, n. 7, p. 736–

743, 1980. Disponível em:

101

<http://mansci.journal.informs.org/cgi/doi/10.1287/mnsc.26.7.736>. .

CHRISTOFIDES, N. Graph Theory - An Algorithmic Approach. 1975.

CHRISTOFIDES, N. WORST-CASE ANALYSIS OF A NEW HEURISTIC PREPARED

FOR THE TRAVELING SALESMAN PROBLEM. Technical Report, , n. February,

1976.

CHRISTOPHER, M. Logística e gerenciamento da cadeia de suprimentos. 2th ed.

2010.

CHU, F.; LABADI, N.; PRINS, C. A Scatter Search for the periodic capacitated arc

routing problem. European Journal of Operational Research, v. 169, p. 586–605,

2006.

CLARKE, G.; WRIGHT, J. W. Scheduling of Vehicles from a Central Depot to a Number

of Delivery Points. Operations Research, v. 12, n. 4, p. 568–581, 1964.

CORMEN, T. H. Algoritmos : Teoria e Prática. 1996.

CORNUEJOLS, G.; FONLUPT, J.; NADDEF, D. The traveling salesman problem on a

graph and some related integer polyhedra. Mathematical Programming, 1985.

DANTZIG, G. B.; FULKERSON, D. R.; JOHNSON, S. Solution of a Large-Scale

Traveling-Salesman Problem. Journal of the Operations Research Society of America, v. 2, n. 4, p. 393–410, 1954.

EILON, S.; CHRISTOFIDES, N. Algorithms for Large-scale Travelling Salesman

Problems. Operational Research Quarterly, v. 23, n. 4, p. 511–518, 1972.

FORD, L. R, AND D. R. F. Flows in networks. 1963.

GENDREAU, M.; IORI, M.; LAPORTE, G.; et al. A Tabu Search Algorithm for a Routing

Container Loading Problem. Transportation Science, v. 40, n. 3, p. 342–350, 2005.

102

GEORGE, J, A.; ROBINSON, D, F. A HEURISTIC FOR PACKING BOXES INTO A

CONTAINER. Computers and Operation Research, v. 7, p. 147–156, 1980.

GILMORE, P, C.; GOMORY, E, E. Sequencing a One State-Variable Machine : A

Solvable Case of the Traveling Salesman Problem. Operations Research, , n. August

2015, 1964.

GLOVER, F. Tabu Search-Part I. Operations Research Society of America, v. 1, n.

3, p. 190–206, 1989.

GOETSCHALCKX, M.; RATLIFF, H. . Order Picking in an isle. IIE Transactions (Institute of Industrial Engineers), 1998.

GOLDEN, B. L.; SKISCIM, C. C. Using Simulated Annealing to Solve Routing and

Location Problems. Research Logistics Quarterly, v. 33, p. 261–279, 1986.

GUTTMAN-BECK, N.; HASSIN, R.; KHULLER, S.; RAGHAVACHARI, B. Approximation

Algorithms with Bounded Performance Guarantees for the Clustered. Algorithmica, p.

422–437, 2000.

HELD, M.; KARP, R. M. The Traveling-Salesman Problem and Minimum Spanning

Trees. , , n. September 2015, 1970.

HELSGAUN, K. An effective implementation of the Lin-Kernighan traveling salesman

heuristic. , v. 126, p. 106–130, 2000.

HELSGAUN, K. An Effective Implementation of K -opt Moves for the Lin-Kernighan TSP

Heuristic. Writings on Computer Science, , n. 109, p. 1–99, 2006.

HENN, S.; WÄSCHER, G. Tabu search heuristics for the order batching problem in

manual order picking systems. European Journal of Operational Research, v. 222,

n. 3, p. 484–494, 2012. Elsevier B.V. Disponível em:

<http://dx.doi.org/10.1016/j.ejor.2012.05.049>. .

103

HODGSON, T, J. A combined approach to the pallet loading problem. IIE Transactions (Institute of Industrial Engineers), 1982.

HOLLAND, J, H. 1992 - Adaptation in natural and artificial systems An in-troductory analysis with applications to biology, control and artificial intelligence.

1992.

IORI, M.; MARTELLO, S. Routing problems with loading constraints. , p. 4–27, 2010.

JONGENS, K.; VOLGENANT, T. The symmetric clustered traveling salesman problem.

European Journal of Operational Research, 1985.

JONKER, R.; VOLGENANT, T. Transforming asymmetric into symmetric traveling

salesman problems. Operational Research Letters, v. 2, n. 4, p. 161–163, 1983.

JR, C. E.; MR, G.; DS, J. Approximation algorithms for bin packing: a survey. PWS,

1997.

JUNQUEIRA, L. L EONARDO J UNQUEIRA, 2013.

JUNQUEIRA, L.; OLIVEIRA, F.; ANT, M.; MORABITO, R. An optimization model for the

vehicle routing problem with practical three-dimensional loading constraints.

International Transactions in Operational Research, v. 20, p. 645–666, 2013.

KARP, R. 1977 - Probabilistic analysis of partitioning algorithms for the

travelingsalesman in the plane - R.M. Karp.pdf. Math Oper, 1977.

KEARNEY, A, T. Excelence in Logistics. , 2014.

KIRKPATRICK, S.; GELATT, C, D.; VECCHI, M, P. Optimization by simulated

Annealing. Science, v. 220, n. 4598, p. 671–680, 1983.

KNUTH, DONALD, E. The Art of Computer Programming : Fundamental Algorithms. 1969.

104

KOSTER, R. DE; LE-DUC, T.; ROODBERGEN, K. J. Design and control of warehouse

order picking: A literature review. European Journal of Operational Research, v. 182,

n. 2, p. 481–501, 2007.

KOSTER, R. DE; POORT, E. VAN DER. Routing orderpickers in a warehouse : a

comparison between optimal and heuristic solutions. IIE Transactions (Institute of Industrial Engineers), , n. November 2014, p. 37–41, 1998.

KUHN, H. W. The hungarian method for the Assigment problem. , 1950.

LAMBERT, D, M.; STOCK, J, R.; ELLRAM, L, M. Fundamentals of Logistics Management. 1998.

LANGEVIN, A.; SOUMIS, F.; DESROSIERS, J. Classification of traveling salesman

problem formulations. Operations Research Letters, v. 9, n. March, p. 127–132, 1990.

LAPORTE, G. The traveling salesman problem: an overview 9of exact and approximate

algorithms. European Journal of Operational Research, v. 59, p. 231–47–231–47,

1992.

LAPORTE, G.; LAPORTE, G. Fifty Years of Vehicle Routing Fifty Years of Vehicle

Routing. , , n. April 2017, 2009.

LAWLER, E. L. Combinatorial Optimization : Networks and Matroids. 1976.

LIN, B. S. Computer Solutions of the Traveling Salesman Problem. Bell System Tech,

, n. 1, 1965.

LIN, S.; KERNIGHAN, B, W. An effective heuristic for the Traveling Salesman Problem.

Operations Research, 1973.

LOCH, G. V. GUSTAVO VALENTIM LOCH UMA NOVA ABORDAGEM NO PROCESSO ITERATIVO DE MELHORIA DE SOLUÇÃO NA RESOLUÇÃO DO Orientador : Prof . Dr . Arinei Carlos Lindbeck da CURITIBA. 2014.

105

MARTELLO, S.; TOTH, P. Knapsack Problems: Algorithms and Computer

Implementations. , v. 42, n. 6, p. 2–3, 1991.

MARTELLO, S.; VIGO, D.; ELETTRONICA, D. Exact Solution Finite Bin of the Packing

Problem. Management Science, v. 44, n. 3, p. 388–399, 1998.

MILLER, C. E.; TUCKER, A. W.; ZEMLIN, R. A. Integer Programming Formulation of

Traveling Salesman Problems. Journal of the ACM, v. 7, n. 4, p. 326–329, 1960.

MILLER, D. L.; PEKNY, J. F. Exact Solution of Large Asymmetric Traveling Salesman

Problems. Science, v. 251, n. 4995, p. 754–761, 12729BC.

MONTGOMERY, DOUGLAS, G. Design and Analysis of Experiments. 5th ed. 1997.

MORABITO, F. O. C. R. Refinamentos na heurística de George e Robinson para o

problema do carregamento de caixas dentro de contêineres. REVISTA TRANSPORTES , v. XI, n. 1980, 2004.

MUNKRES, J. Algorithms for the assigment and transportation problems. Journal of the society for indusrtial and applied Mathematics, v. 5, n. 1, p. 32–38, 1957.

NAHAR, S.; SAHNI, S.; SHRAGOWITZ, E. Simulated annealing and combinatorial

optimization. Journal of Computer Aided VLSI Design, p. 293–299, 1989.

NGUYEN, H. D.; YOSHIHARA, I. Implementation of an Effective Hybrid GA for Large-

Scale Traveling Salesman Problems. IEEE, v. 37, n. 1, p. 92–99, 2007.

PAPADIMITRIOU, C.; STEIGLITZ, K. Combinatorial Optimization. Dover

Publications, INC., 1982.

RATLIFF, H. D.; ROSENTHAL, A. S. Order-Picking in a Rectangular Warehouse: A

Solvable Case of the Traveling Salesman Problem. Operations Research, v. 31, n. 3,

p. 507–521, 1983. Disponível em:

106

<http://pubsonline.informs.org/doi/abs/10.1287/opre.31.3.507>. .

REINFELD, N. .; VOGEL, W. . Reinfeld, N.V. Mathematical Programming, 1958.

RESENKRANTZ, D.; STEARNS, R.; LEWIS, P. AN ANALYSIS OF SEVERAL

HEURISTICS FOR THE TRAVELING SALESMAN PROBLEM *. Journal of Computing, v. 6, n. 3, p. 563–581, 1977.

RIFF, M. C.; BONNAIRE, X.; NEVEU, B. A revision of recent approaches for two-

dimensional strip-packing problems. Engineering Applications of Artificial Intelligence Brief paper, v. 22, p. 823–827, 2009.

ROODBERGEN, K. J.; KOSTER, R. Routing methods for warehouses with multiple

cross aisles. International Journal of Production Research for warehouses with multiple cross aisles. , n. December 2014, p. 37–41, 2010.

SCARPIN, C. T. Uma metodologia para a previsão de demanda de produtos utilizando redes neurais artificiais de funções de bases radiais modificadas e uma proposta de logística de reposição, 2012. UFPR.

SCHOLZ, A.; HENN, S.; STUHLMANN, M.; WÄSCHER, G. A new mathematical

programming formulation for the Single-Picker Routing Problem. European Journal of Operational Research, v. 253, n. 1, p. 68–84, 2016.

SMITH, W. D. Finding the optimum N-city traveling salesman tour in the Euclidean plane

in subexponential time and polynomial space. , 1988.

SUDAN, M.; SZEGEDYL, M. Proof Verification and Hardness of Approximation

Problems. Computing Machinery, 1992.

TALBI, E.-G. Metaheuristics: from design to Implementation. 2009.

TOMPKINS, J, A.; WHITE, J, A.; BOZER, Y, A.; TANCHOCO, J, M, A. Facilities Planning. 4th ed. 2010.

Documents

UNIVERSIDADE FEDERAL DO PARANÁ ALEXANDRE CHECOLI …