( PDF ) Roteirização de veículos de carga com múltiplos depósitos em sistema de informação geográfica livre

Download PDF

ads:

MINISTÉRIO DA DEFESA

EXÉRCITO BRASILEIRO

DEPARTAMENTO DE CIÊNCIA E TECNOLOGIA

INSTITUTO MILITAR DE ENGENHARIA

CURSO DE MESTRADO EM ENGENHARIA DE TRANSPORTES

ORIVALDE SOARES DA SILVA JÚNIOR

ROTEIRIZAÇÃO DE VEÍCULOS DE CARGA COM

MÚLTIPLOS DEPÓSITOS EM SISTEMA DE INFORMAÇÃO

GEOGRÁFICA LIVRE

Rio de Janeiro

2009

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

INSTITUTO MILITAR DE ENGENHARIA

ORIVALDE SOARES DA SILVA JÚNIOR

ROTEIRIZAÇÃO DE VEÍCULOS DE CARGA COM MÚLTIPLOS

DEPÓSITOS EM SISTEMA DE INFORMAÇÃO GEOGRÁFICA LIVRE

Dissertação de Mestrado apresentada ao Curso de

Mestrado em Engenharia de Transportes do Instituto

Militar de Engenharia, como requisito parcial para a

obtenção do título de Mestre em Ciências em Engenharia

de Transportes.

Orientador: Prof. Luiz Antônio Silveira Lopes - D. Sc.

Co-orientador: Prof. Ulf Bergmann - D. Sc.

Rio de Janeiro

2009

ads:

c2009

INSTITUTO MILITAR DE ENGENHARIA

Praça General Tibúrcio, 80 - Praia Vermelha

Rio de Janeiro - RJ CEP: 22290-270

Este exemplar é de propriedade do Instituto Militar de Engenharia, que poderá incluí-lo

em base de dados, armazenar em computador, microfilmar ou adotar qualquer forma de

arquivamento.

É permitida a menção, reprodução parcial ou integral e a transmissão entre bibliotecas

deste trabalho, sem modificação de seu texto, em qualquer meio que esteja ou venha a ser

fixado, para pesquisa acadêmica, comentários e citações, desde que sem finalidade comercial

e que seja feita a referência bibliográfica completa.

Os conceitos expressos neste trabalho são de responsabilidade do(s) autor(es) e do(s)

orientador(es).

388.324 Silva Júnior, Orivalde Soares da

5586 r Roteirização de veículos de carga com múltiplos depó-

sitos em sistema de informação geográfica livre / Orivalde

Soares da Silva Júnior - Rio de Janeiro: Instituto Militar de

Engenharia, 2008.

134 p.: il.

Dissertação (mestrado) – Instituto Militar de Engenha-

ria, 2008.

1. Engenharia de transportes – teses. 2. Transporte de

cargas – roteirização. 3. Sistema de informação geográfica.

4. Software livre. I. Título. II. Instituto Militar de

Engenharia.

CDD 388.324

INSTITUTO MILITAR DE ENGENHARIA

ORIVALDE SOARES DA SILVA JÚNIOR

ROTEIRIZAÇÃO DE VEÍCULOS DE CARGA COM MÚLTIPLOS

DEPÓSITOS EM SISTEMA DE INFORMAÇÃO GEOGRÁFICA LIVRE

Dissertação de Mestrado apresentada ao Curso de Mestrado em Engenharia de

Transportes do Instituto Militar de Engenharia, como requisito parcial para a obtenção do

título de Mestre em Ciências em Engenharia de Transportes.

Orientador: Prof. Luiz Antônio Silveira Lopes - D. Sc.

Co-orientador: Prof. Ulf Bergmann - D. Sc.

Aprovada em 06 de março de 2009 pela seguinte Banca Examinadora:

Rio de Janeiro

2009

Aos meus pais, minha irmã e minha namorada por apoiarem a

concretização de mais um sonho em minha vida.

AGRADECIMENTOS

Ao Instituto Militar de Engenharia, pela realização deste curso de mestrado, bem como a

CAPES pelo apoio financeiro durante o curso.

Ao meu orientador, professor Luiz Antônio Silveira Lopes, pela amizade, apoio,

ensinamento e ferramentas apresentadas que possibilitaram a conclusão desta dissertação.

Ao meu co-orientador, professor Ulf Bergmann, pelos ensinamentos em programação

orientada a objetos com Java, conceitos de software livre e criação de plugins para o Sistema

de Informação Geográfica OpenJUMP.

Às professoras Maria Cristina Fogliatti de Sinay e Vânia Barcellos Gouvêa Campos,

pelos seus ensinamentos tanto técnicos como de vida.

Ao professor Altair dos Santos Ferreira Filho, pelos ensinamentos de logística e

simulação, assim como o auxílio na obtenção dos dados utilizados no estudo de caso desta

dissertação.

Ao professor José Eugênio Leal, por ter gentilmente aceito o convite para a participação

na banca examinadora desta dissertação.

A meus pais, minha irmã e minha namorada que me ajudaram de todas as formas que

puderam para que eu chegasse até aqui.

Aos meus amigos Roberto, Vanda, David e Bárbara por não terem apenas estudado

comigo, mas por terem me inserido em suas vidas.

Aos meus amigos Castilho, Custódio, Amorim, Hotta e Tarcísio pela amizade e pela

satisfação de estudar ao lado de militares de alto nível.

Aos amigos que ainda espero revê-los no Rio e aos que deixaram o Rio, André Manta,

Rosana, José Mauro, Leandro, Manoel, Marcílio, Marcela, Sabrina, Mariana, Bruno, Ávila,

Cazeli, Marcelo, Renato, Clauber, André Gasparini, Guerson, Isolina, Amilcar, André

Medeiros, Cristina, entre tantos outros.

Aos meus amigos que generosamente traduziram o protótipo desenvolvido nesta

dissertação: Lucas traduziu para italiano, Rodrigo para japonês, Amílcar para espanhol e

Roberto para francês.

A todos os meus familiares e amigos por estarem sempre ao meu lado.

"A imaginação é mais importante que o conhecimento."

Albert Einstein

SUMÁRIO

LISTA DE ILUSTRAÇÕES .................................................................................................... 12

LISTA DE TABELAS ............................................................................................................. 14

1 INTRODUÇÃO .................................................................................................... 17

1.1 O Problema............................................................................................................. 17

1.2 Objetivo.................................................................................................................. 17

1.3 Justificativas........................................................................................................... 18

1.4 Estrutura da Dissertação......................................................................................... 18

2 LOGÍSTICA, TECNOLOGIA DA INFORMAÇÃO E DISTRIBUIÇÃO

FÍSICA .................................................................................................................. 20

2.1 Introdução............................................................................................................... 20

2.2 Definições da Logística.......................................................................................... 20

2.3 Evolução da Logística ............................................................................................ 21

2.4 Gerenciamento Logístico ....................................................................................... 23

2.5 Tecnologia da Informação...................................................................................... 25

2.6 Tecnologia da Informação Aplicada a Logística.................................................... 26

2.6.1 Aplicações de Hardware......................................................................................... 27

2.6.2 Aplicações de Software.......................................................................................... 27

2.7 Distribuição Física.................................................................................................. 28

2.7.1 Componentes de um Sistema de Distribuição Física ............................................. 29

2.8 Considerações Finais.............................................................................................. 30

3 O PROBLEMA DE ROTEIRIZAÇÃO DE VEÍCULOS COM MÚLTIPLOS

DEPÓSITOS......................................................................................................... 31

3.1 Introdução............................................................................................................... 31

3.2 Definição do Problema........................................................................................... 34

3.3 Métodos de Solução do Problema.......................................................................... 36

3.3.1 Método de um Estágio............................................................................................ 37

3.3.1.1 Soluções do Problema por um Estágio................................................................... 37

3.3.2 Método de dois Estágios ........................................................................................ 37

3.3.2.1 Primeiro Estágio - Problema de Atribuição ........................................................... 38

3.3.2.1.1 Atribuição com Prioridades.................................................................................... 38

3.3.2.1.1.1 Atribuição Simplificada ........................................................................................ 38

3.3.2.1.1.2 Atribuição Paralela................................................................................................ 41

3.3.2.1.1.3 Atribuição por Varredura ...................................................................................... 40

3.3.2.1.2 Atribuição Cíclica .................................................................................................. 40

3.3.2.1.3 Atribuição por Cluster............................................................................................ 41

3.3.2.1.3.1 Coeficiente de Propagação.................................................................................... 41

3.3.2.1.3.2 Três Critérios de Clusterização ............................................................................. 42

3.3.2.1.4 Atribuição usando o Problema de Transportes ...................................................... 42

3.3.2.2 Segundo Estágio - Problema de Roteamento de Veículos ..................................... 43

3.3.2.2.1 Métodos Exatos...................................................................................................... 44

3.3.2.2.2 Métodos Heurísticos............................................................................................... 44

3.3.2.2.2.1 Heurísticas Construtivas........................................................................................ 45

3.3.2.2.2.2 Heurísticas de Melhora Iterativa ........................................................................... 47

3.3.2.2.2.3 Heurísticas de duas Fases...................................................................................... 48

3.3.2.2.3 Metaheurísticas....................................................................................................... 48

3.3.2.2.3.1 Busca Tabu............................................................................................................ 48

3.3.2.2.3.2 Algoritmos Genéticos............................................................................................ 48

3.3.2.2.3.3 Simulated Annealing............................................................................................. 50

3.3.2.2.3.4 GRASP - Greedy Random Adaptive Search Procedure........................................ 51

3.3.2.2.3.5 VND - Variable Neighborhood Descent ............................................................... 52

3.3.2.2.3.6 ACS - Ant Colony Systems................................................................................... 52

3.3.2.2.3.7 Scatter Search........................................................................................................ 54

3.3.2.3 Soluções do Problema por dois Estágios................................................................ 54

3.4 Comparação entre os Métodos de Solução do Problema ....................................... 58

3.5 Considerações Finais.............................................................................................. 61

4 SISTEMA DE INFORMAÇÃO GEOGRÁFICA LIVRE................................ 62

4.1 Introdução............................................................................................................... 62

4.2 Sistema de Informação Geográfica ........................................................................ 62

4.2.1 Origens ................................................................................................................... 62

4.2.2 Definição ................................................................................................................ 63

4.2.3 Componentes de um SIG........................................................................................ 64

4.2.4 Modelos de dados em SIG ..................................................................................... 65

4.2.4.1 Dados Vetoriais...................................................................................................... 65

4.2.4.1 Dados Raster .......................................................................................................... 66

4.2.5 Aplicações de SIG.................................................................................................. 67

4.2.5 SIG para Transportes.............................................................................................. 67

4.2.5.1 Análise da Rede...................................................................................................... 67

4.2.5.2 Planejamento e Modelos de Geração de Viagens .................................................. 68

4.2.5.3 Logística e Roteirização de Veículos..................................................................... 69

4.3 SIG Livre................................................................................................................ 72

4.3.1 Softwares................................................................................................................ 73

4.3.2 Liberdades do Software Livre................................................................................ 75

4.4 Considerações Finais.............................................................................................. 75

5 PROCEDIMENTO PROPOSTO PARA ROTEIRIZAÇÃO DE VEÍCULOS

COM MÚLTIPLOS DEPÓSITOS ..................................................................... 77

5.1 Introdução............................................................................................................... 77

5.2 Formulação Matemática Proposta.......................................................................... 77

5.3 Escolha do Método do MDVRP para adotar no Procedimento ............................. 78

5.2 Estrutura do Procedimento Proposto...................................................................... 79

6 PROTÓTIPO........................................................................................................ 83

6.1 Introdução............................................................................................................... 83

6.2 Funcionamento do OpenJUMP .............................................................................. 83

6.2.3 Topologia JUMP .................................................................................................... 84

6.2.4 Desenvolvimento de Plugins.................................................................................. 84

6.3 Levantamento de Requisitos .................................................................................. 85

6.3.1 Requisitos Funcionais ............................................................................................ 85

6.3.2 Requisitos Não Funcionais..................................................................................... 86

6.4 Especificação.......................................................................................................... 87

6.4.1 Diagrama de Casos de Uso..................................................................................... 87

6.4.2 Diagrama de Atividades......................................................................................... 87

6.4.3 Diagrama de Classes .............................................................................................. 88

6.5 Implementação ....................................................................................................... 91

6.5.1 Pacote Plugin.......................................................................................................... 91

6.5.1.1 Classe VehicleRoutingPluginExtension................................................................. 91

6.5.1.2 Classe VehicleRoutingPlugin................................................................................. 92

6.5.1.3 Classe VehicleRoutingDialog ................................................................................ 93

6.5.1.4 Classe ProgressDialog............................................................................................ 94

6.5.2 Pacote Matrix ......................................................................................................... 95

6.5.2.1 Classe Matrix.......................................................................................................... 95

6.5.2.2 Classe Path ............................................................................................................. 96

6.5.2.3 Classe ShortestPathMatrix ..................................................................................... 96

6.5.3 Pacote Model.......................................................................................................... 97

6.5.3.2 Classe Locality ....................................................................................................... 97

6.5.3.3 Classe Client........................................................................................................... 98

6.5.3.4 Classe Depot........................................................................................................... 98

6.5.3.4 Interface Local........................................................................................................ 99

6.5.3.5 Classe LocalGroup ............................................................................................... 101

6.5.3.6 Classe Route......................................................................................................... 101

6.5.3.7 Classe RouteGroup............................................................................................... 102

6.5.4 Pacote Algo .......................................................................................................... 102

6.5.4.1 Classe MDVRPData............................................................................................. 103

6.5.4.2 Classe VRPSolver ................................................................................................ 104

6.5.4.3 Classe CWLS ....................................................................................................... 105

6.5.4.4 Classe AssignmentSolver..................................................................................... 106

6.5.4.5 Classe ParallelAssignment ................................................................................... 107

6.5.4.6 Interface MDVRPSolver...................................................................................... 108

6.5.4.7 Classe ParallelAssignmentAndCWLS ................................................................. 108

7 ESTUDO DE CASO........................................................................................... 110

7.1 Introdução............................................................................................................. 110

7.2 A Empresa............................................................................................................ 110

7.3 Descrição do Caso................................................................................................ 111

7.3.1 Informações da Malha Viária............................................................................... 112

7.3.2 Informações dos Clientes ..................................................................................... 113

7.3.3 Informações dos Depósitos .................................................................................. 114

7.3.4 Informações dos Veículos .................................................................................... 115

7.3.5 Informações dos Produtos .................................................................................... 116

7.4 Geração das Rotas ................................................................................................ 116

7.4.1 Carrega Camada da Malha Viária ........................................................................ 116

7.4.2 Carrega Camadas de Clientes e Depósitos........................................................... 117

7.4.3 Informa Dados da Malha Viária........................................................................... 117

7.4.4 Informa Dados dos Clientes ................................................................................. 118

7.4.5 Informa Dados dos Depósitos .............................................................................. 119

7.4.6 Informa Dados dos Veículos................................................................................ 120

7.4.7 Gera Rotas............................................................................................................ 120

7.5 Comparação com o TransCAD ............................................................................ 125

7.6 Considerações Finais............................................................................................ 127

8 CONCLUSÕES E RECOMENDAÇÕES ........................................................ 128

8.1 Conclusões ........................................................................................................... 128

8.2 Recomendações.................................................................................................... 129

9 REFERÊNCIAS BIBLIOGRÁFICAS ............................................................. 130

LISTA DE ILUSTRAÇÕES

FIG. 2.1 Custos Logísticos em relação ao PIB - Brasil x EUA em 2004............................. 25

FIG. 3.1 Seqüência de tomadas de decisão no MDVRP ...................................................... 34

FIG. 3.2 Um exemplo do MDVRP....................................................................................... 35

FIG. 3.3 Atribuição de um cliente ao depósito pelas atribuições: paralela e simplificada... 39

FIG. 3.4 Depósito determinado (D) na atribuição por varredura ......................................... 40

FIG. 3.5 Atribuição cíclica ................................................................................................... 41

FIG. 3.6 Distâncias na atribuição por Coeficiente de Propagação ....................................... 42

FIG. 3.7 Distância média para os clusters ............................................................................ 42

FIG. 3.8 O problema de transportes...................................................................................... 43

FIG. 3.9 Passo inicial do algoritmo de Clark and Wright .................................................... 46

FIG. 3.10 União de rotas pelo algoritmo de Clark and Wright .............................................. 46

FIG. 3.11 Dois possíveis novos percursos.............................................................................. 47

FIG. 3.12 Exemplo do funcionamento da Busca Tabu........................................................... 49

FIG. 3.13 Soluções (filhos) obtidos a partir do cruzamento de dois resultados (pais) ........... 50

FIG. 3.14 Representação do resfriamento em relação ao tempo ............................................ 51

FIG. 3.15 Representação do funcionamento do GRASP........................................................ 52

FIG. 3.16 Comportamento de uma colônia de formigas ao se deparar com um obstáculo.... 53

FIG. 4.1 Componentes de um Sistema de Informação Geográfica ...................................... 64

FIG. 4.2 Exemplos de dados espaciais tipo vetor................................................................. 65

FIG. 4.3 Modelo Raster (representação)............................................................................... 66

FIG. 4.4 Exemplo de um caminho........................................................................................ 68

FIG. 4.5 Exemplo de fluxo sobre uma rede.......................................................................... 69

FIG. 4.6 Exemplo de roteirização para entregas................................................................... 71

FIG. 4.7 Exemplo de roteirização para coleta de resíduos sólidos....................................... 71

FIG. 6.1 Esquema de funcionamento do OpenJUMP........................................................... 83

FIG. 6.2 Diagrama de caso de uso........................................................................................ 87

FIG. 6.3 Diagrama de atividades .......................................................................................... 88

FIG. 6.4 Diagrama de classes simplificado .......................................................................... 89

FIG. 6.5 Pacotes do protótipo............................................................................................... 91

FIG. 6.6 Classe VehicleRoutingPlugInExtension ................................................................ 91

FIG. 6.7 Classe VehicleRoutingPlugIn ................................................................................ 93

FIG. 6.8 Classe VehicleRoutingDialog ................................................................................ 94

FIG. 6.9 Classe ProgressDialog............................................................................................ 95

FIG. 6.10 Classe Matrix.......................................................................................................... 95

FIG. 6.11 Classe Path ............................................................................................................. 96

FIG. 6.12 Classe ShortestPathMatrix ..................................................................................... 97

FIG. 6.13 Classe GeographicPosition..................................................................................... 97

FIG. 6.14 Classe Locality ....................................................................................................... 97

FIG. 6.15 Classe Client........................................................................................................... 98

FIG. 6.16 Classe Depot........................................................................................................... 99

FIG. 6.17 Interface Local...................................................................................................... 101

FIG. 6.18 Classe LocalGroup ............................................................................................... 101

FIG. 6.19 Classe Route......................................................................................................... 102

FIG. 6.20 Classe Route......................................................................................................... 102

FIG. 6.21 Classe MDVRPData............................................................................................. 104

FIG. 6.22 Classe VRPSolver ................................................................................................ 105

FIG. 6.23 Classe CWLS ....................................................................................................... 106

FIG. 6.24 Classe AssignmentSolver..................................................................................... 106

FIG. 6.25 Classe ParallelAssignment ................................................................................... 107

FIG. 6.26 Interface MDVRPSolver...................................................................................... 108

FIG. 6.27 Classe ParallelAssignmentAndCWLS ................................................................. 109

FIG. 7.1 Presença da Parmalat no mundo........................................................................... 110

FIG. 7.2 Malha viária brasileira.......................................................................................... 113

FIG. 7.3 Clientes da Parmalat............................................................................................. 114

FIG. 7.4 Depósitos da Parmalat.......................................................................................... 115

FIG. 7.5 Tela do OpenJUMP com camadas carregadas ..................................................... 117

FIG. 7.6 Tela para informar os dados da malha viária ....................................................... 118

FIG. 7.7 Tela para informar os dados dos clientes ............................................................. 119

FIG. 7.8 Tela para informar os dados dos depósitos .......................................................... 119

FIG. 7.9 Tela para informar os dados dos veículos ............................................................ 120

FIG. 7.10 Tela com o estado da execução da geração das rotas........................................... 121

FIG. 7.11 Atributos da camada de rotas ............................................................................... 121

FIG. 7.12 Detalhamento de duas rotas.................................................................................. 122

FIG. 7.13 Rotas utilizando a distância euclidiana ................................................................ 123

FIG. 7.14 Tela do TransCAD com camadas carregadas ...................................................... 125

LISTA DE TABELAS

TAB. 2.1 Custos Logísticos no Brasil em 2004..................................................................... 24

TAB. 2.2 Matriz de transporte de cargas do Brasil em 2004................................................. 24

TAB. 3.1 Classificação dos principais problemas de roteirização de veículos...................... 32

TAB. 3.2 Comparação entre os trabalhos sobre o MDVRP................................................... 59

TAB. 5.1 Comparação entre os Algoritmos de Atribuição.................................................... 79

TAB. 5.2 Etapas da Metodologia........................................................................................... 81

TAB. 6.1 Requisitos funcionais ............................................................................................. 85

TAB. 6.2 Requisitos não funcionais....................................................................................... 86

TAB. 7.1 Comparação das rotas utilizando a distância euclidiana ajustada e malha viária 124

TAB. 7.2 Comparação das rotas obtidas pelo protótipo desenvolvido e pelo TransCAD... 126

RESUMO

Esta dissertação tem como objetivo contribuir para o gerenciamento da logística de

distribuição física de produtos, buscando uma maior eficiência e produtividade na roteirização

de veículos com múltiplos depósitos apoiada por um Sistema de Informação Geográfica (SIG)

livre.

Em um processo de distribuição, devem ser consideradas as características físicas e

operacionais da empresa como: múltiplos depósitos, restrições de carga e volume dos veículos

e depósitos, de limite de jornada de trabalho, de tempo de descarga no cliente, assim como

restrições do sistema viário. Estes fatores, entre outros, tornam o processo de roteirização

bastante complexo, necessitando-se de ferramentas que auxiliem a tomada de decisão. Com

esta constatação, nesta dissertação apresenta-se o desenvolvimento de uma ferramenta

computacional a partir do procedimento desenvolvido.

A ferramenta computacional foi desenvolvida utilizando a linguagem de programação

Java dentro do paradigma de orientação a objetos. Esta ferramenta foi concebida como um

plugin do SIG livre OpenJUMP, o qual permite a associação de um banco de dados a um

mapa georreferenciado, facilitando o cadastramento dos clientes e a visualização das rotas

geradas.

Para ilustrar o procedimento e o protótipo desenvolvido, foi realizado um estudo de caso

com uma empresa do setor alimentício. Este permitiu demonstrar, além da aplicabilidade do

procedimento, a potencialidade do mesmo, em fornecer subsídios à tomada de decisão por

parte de seus operadores. Além disto, validou-se o protótipo desenvolvido através da

comparação dos resultados obtidos com um software comercial chamado TransCAD, a qual

demonstrou que o protótipo permite a obtenção de soluções com menores custos.

ABSTRACT

The objective of this dissertation is to contribute to the management of the products load

distribution logistics in urban area, looking for a major efficiency and productivity in the

multi-depot vehicle routing based by a open source Geographic Information System (GIS).

In a process of physical distribution, there are considers the characteristics physical of the

firm such as: multi-depot; restrictions of load and capacity in the vehicles and depots;

maximum work time; limit of download time in the client; such as restrictions of road system.

These factors, among others, contribute to make the process of routing a complex one,

needing then, tools to assist the decision making process. With this evidence, this work

presents the development of a computational tool for the developed procedure.

The computational tool was developed using the Java programming language with in side

oriented object paradigm. This tool was created like a plugin of the open GIS OpenJUMP,

which permit the associates a data base to a map, easing the identification of the customers

and depots, and the visualization of the generated routes.

To illustrate the procedure and the prototype developed, a case study was realized with a

firm of aliment sector. This was very important for demonstrating the applicability of the

procedure and the potential for providing subsidies for the decision making process of an

operators. There more, the prototype was valid across of obtained results compare of

commercial software TransCAD, which demonstrated that the prototype permit obtain

solutions with smaller costs.

1 INTRODUÇÃO

1.1 O PROBLEMA

Um elemento chave de muitos sistemas de distribuição física é o roteirização e a

programação de veículos através de um conjunto de clientes que requerem o serviço de

entrega. O Problema de Roteirização de Veículos (PRV) envolve a geração de um conjunto de

rotas para veículos com custo mínimo, originando e terminando num depósito central, para

uma frota dos veículos que atenda um conjunto de clientes com demandas conhecidas. Para

cada cliente é prestado o serviço de entrega exatamente uma vez e, além disso, todos os

clientes devem ser atribuídos aos veículos sem exceder as capacidades do veículo (BODIN,

1983).

Visto que o PRV foi estudado extensamente, o Problema de Roteirização de Veículos

com Múltiplos Depósitos (PRVMD) atraiu menos a atenção por pesquisadores da área. No

PRVMD, os clientes devem ser atendidos por um dos diversos depósitos pertencentes à

empresa. Assim como no PRV, cada veículo deve sair e retornar ao mesmo depósito e a

capacidade dos veículos deve ser respeitada.

O PRVMD é NP-hard (LENSTRA, 1981), conseqüentemente, o desenvolvimento de

algoritmos heurísticos para esta classe do problema é de essencial interesse e pode ser visto

como um problema de atribuição no sentido que a saída é um conjunto de roteirizações dos

veículos para clientes atribuídos a cada depósito. Esta interpretação sugere uma classe de

aproximação que atribui clientes e então roteiriza os veículos para cada conjunto.

1.2 OBJETIVO

Desenvolver um procedimento para solucionar o Problema de Roteirização de Veículos

com Múltiplos Depósitos (PRVMD) utilizando um método de dois estágios, que consiste em

resolver inicialmente um problema de atribuição de clientes aos depósitos e logo após as

roteirizações separadas para os conjuntos de clientes. O objetivo do problema é minimizar o

custo total (distância) respeitando a restrição de capacidade dos veículos. Este procedimento

será integrado a um Sistema de Informação Geográfica (SIG) livre.

1.3 JUSTIFICATIVAS

O transporte é uma área chave de decisão dentro do sistema logístico e absorve, em

média, a porcentagem mais elevada de custos do que qualquer outra atividade logística

(BALLOU, 2001). Visando a redução destes custos, as empresas procuram ser cada vez mais

competitivas no mercado, buscando por soluções de apoio às atividades logísticas que

atendam as suas características reais de planejamento. Uma das características é o

planejamento do transporte englobando todos os depósitos que uma empresa possua.

Com o uso de Sistema de Informação Geográfica é possível levar em consideração as

características reais de uma malha viária, como a distância real entre os depósitos e clientes e

o sentido das vias. Quanto à sua característica de ser livre, torna-se uma considerável

contribuição ao meio acadêmico para que este trabalho seja continuado e aprimorado, sem as

restrições impostas por softwares proprietários.

1.4 ESTRUTURA DA DISSERTAÇÃO

No primeiro capítulo desta dissertação é apresentado o objetivo e a justificativa do

trabalho assim como a sua estrutura.

Para se chegar ao desenvolvimento de um procedimento que faça a roteirização de

veículos com múltiplos depósitos, foi necessário estudar sobre diversos assuntos, os quais

foram separados em capítulos conforme são apresentados a seguir.

No segundo capítulo apresenta-se uma visão geral sobre logística, distribuição física e

tecnologia da informação, posicionando-se o problema de roteirização de veículos.

No terceiro capítulo apresenta-se um estudo do estado da arte sobre o problema de

roteirização de veículos com múltiplos depósitos.

No quarto capítulo apresenta-se uma visão geral sobre Sistema de Informação Geográfica

Livre, assim como o seu funcionamento, suas aplicações em transportes e as suas liberdades

por ser um software livre.

No quinto capítulo descreve-se o procedimento desenvolvido e justifica-se a escolha dos

métodos adotados no procedimento.

No sexto capítulo descreve-se o protótipo do software que foi desenvolvido para servir de

ferramenta operacional para roteirização de veículos com múltiplos depósitos.

No sétimo capítulo descreve-se um estudo de caso realizado com uma empresa do setor

alimentício e avaliam-se os métodos relacionados ao procedimento desenvolvido fazendo uma

comparação com um software existente no mercado.

No oitavo e último capítulo são apresentadas as conclusões finais e recomendações para

prosseguimento das pesquisas. Em seguida são apresentadas as referências bibliográficas.

2 LOGÍSTICA, TECNOLOGIA DA INFORMAÇÃO E DISTRIBUIÇÃO FÍSICA

2.1 INTRODUÇÃO

Atualmente, devido às necessidades de satisfazer as demandas cada vez maiores do

cliente, a logística tornou-se reconhecida como uma área vital importância para todos os

setores do mercado. É necessário fornecer serviço ao cliente e que não seja superado por

ninguém, e satisfazer totalmente às necessidades de escolha do produto, entrega em tempo e

disponibilidade de estoques a um preço competitivo. Para diminuir custos deve-se aplicar a

logística na cadeia de suprimentos.

Uma área promissora da logística na busca do crescimento é o uso da tecnologia da

informação, uma vez que essa é capaz de fornecer as informações certas no momento certo

para tomar a decisão certa pelo motivo certo. Estas informações são essenciais para o

planejamento e gerenciamento logístico da distribuição física de produtos.

2.2 DEFINIÇÕES DA LOGÍSTICA

Segundo EILON (1971), logística pode ser definida como a provisão de bens e serviços

de um ponto de oferta para um ponto de demanda. Um completo sistema logístico abrange o

processo de movimentação de matéria-prima (e outros insumos necessários à produção) de

fornecedores para a fábrica, a conversão desses insumos em produtos na fábrica, o movimento

destes produtos para vários armazéns ou depósitos, e a eventual entrega destes produtos ao

consumidor final.

Com outras palavras, CHRISTOPHER (1999) define a logística como sendo um processo

com o qual se dirige de maneira estratégica a transferência e armazenagem de materiais,

componentes e produtos acabados, começando dos fornecedores, passando através das

empresas, até chegar aos consumidores.

Para BALLOU (2001) a logística associa estudo e administração dos fluxos de bens e

serviços e da informação que os põe em movimento. Caso fosse viável produzir todos os bens

e serviços no ponto onde eles são consumidos ou caso as pessoas desejassem viver onde as

matérias-primas e a produção se localizam, então a logística seria pouco importante. Mas isto

não ocorre. Uma região tende a especializar-se na produção daquilo que tiver vantagem

econômica para fazê-lo. Isto cria um hiato de tempo e espaço entre matérias-primas e

produção e entre produção e consumo. Vencer tempo e distância na movimentação de bens ou

na entrega de serviços de forma eficaz e eficiente é tarefa do profissional de logística. Ou seja,

sua missão é colocar as mercadorias ou os serviços certos no lugar e no instante correto e na

condição desejada, ao menor custo possível.

2.3 EVOLUÇÃO DA LOGÍSTICA

No início entendia-se a logística apenas como a responsável pela distribuição de

produtos. No decorrer dos anos com as grandes mudanças na economia mundial, a crescente

globalização, a mudança no perfil e exigências do cliente, a diminuição do ciclo de vida dos

produtos e a elevada utilização da tecnologia, a logística foi abrangendo novas atividades ao

longo da cadeia de produção. Assim surgiram novos conceitos, desde a administração

logística até a logística integrada, onde não se busca apenas a redução do custo de uma

atividade individual, mas sim o custo logístico total da empresa - transporte, estocagem,

armazenagem, processamento de pedidos, lotes de produção, de compras e serviço ao cliente.

Mais tarde forma-se o Council of Logistics Management (CLM) para desenvolver a teoria

e a compreensão do processo logístico, promover a arte e a ciência de administrar os sistemas

logísticos e ainda promover o diálogo e a evolução desse campo, operando sem fins lucrativos

e em cooperação com empresas e instituições. Sua definição:

“Logística é o processo de planejamento, implementação e controle do

fluxo eficiente e eficaz de mercadorias, serviços e das informações

relativas desde o ponto de origem até o ponto de consumo com o

propósito de atender às exigências dos clientes.”

Com a globalização da economia, ou seja, com a integração dos mercados em nível

mundial no sentido de que um produto e sua matéria-prima, independentemente de sua origem

ou procedência possa estar sendo oferecido para consumo em qualquer parte do mundo,

tornou-se condição essencial à integração das atividades na empresa. Passou-se a ser

necessário a preocupação com o todo e, em 1998 o Global Supply Chain Forum define o

Supply Chain Management (SCM), como a integração dos processos comerciais críticos

desde o usuário final até os fornecedores originais, que fornecem produtos, serviços e

informação que adicionam valor aos clientes e outros parceiros (LAMBERT, 1999).

De acordo com FLEURY (2000), o SCM representa o esforço de integração dos diversos

participantes do canal de administração, por meio da administração compartilhada de

processos-chave de negócios que interligam as diversas unidades organizacionais e membros

do canal, desde o consumidor final até o fornecedor inicial de matérias-primas.

Resumidamente, enquanto a logística integrada representa uma integração interna das

atividades, o SCM representa sua integração externa, pois estende a coordenação dos fluxos

de materiais e de informações aos fornecedores e ao cliente final. Como conseqüência dessa

evolução, observa-se diversas tendências da logística sendo que são incorporadas pelas

empresas. Dentre as diversas tendências, destacam-se:

• Centralização;

• Diminuição da quantidade de centros de distribuição;

• Uso de instalações intermediárias de quebra de carga, onde são realizadas operações de

crossdocking, que consiste num fracionamento de grandes cargas em pequenas cargas,

em docas de descarga e despacho respectivamente, operação esta sem necessidade de

estocagem;

• Transporte intermodal;

• Terceirização - uso de operadores logísticos;

• Estratégias conjuntas de componentes da cadeia para melhorar a eficiência, cujo

principal representante é o movimento ECR Brasil, que consiste na parceria entre

grandes redes de supermercados e seus fornecedores;

• Uso intensivo de tecnologia da informação.

Diante deste novo quadro, as empresas, através da logística, procuram uma vantagem

competitiva que permite sobreviver à atual economia mundial. Elas precisam otimizar seus

lucros através da vantagem de custo ou da vantagem de percepção de valor pelo cliente. A

logística começa a ser vista como um sistema integrado capaz de agregar valor por meio dos

serviços prestados (FLEURY; WANKE; FIGUEIREDO, 2000).

Para NOVAES (2001), estes valores que a logística deve agregar para o cliente são

quatro, sendo eles: valor de lugar, de tempo, de qualidade e de informação. Isso porque, o

cliente terá satisfação se o produto estiver no lugar certo, na hora certa, com a qualidade

desejada e, no caso de carga de alto valor agregado, por exemplo, se também souber onde se

encontra o seu produto.

Assim, o autor entende que a logística moderna deve incorporar:

• Prazos previamente acertados e cumpridos integralmente;

• Integração efetiva e sistêmica entre todos os setores da empresa;

• Integração efetiva e estreita (parcerias) com fornecedores e clientes;

• Busca da otimização global, envolvendo a racionalização dos processos e a redução de

custos;

• Satisfação plena do cliente, mantendo nível de serviço preestabelecido e adequado.

2.4 GERENCIAMENTO LOGÍSTICO

Ante as considerações anteriores, constata-se que a missão do gerenciamento logístico é

planejar e coordenar todas as atividades necessárias para alcançar níveis desejáveis dos

serviços e qualidade ao custo mais baixo possível. Portanto, a logística deve ser vista como o

elo de ligação entre o mercado e a atividade operacional da empresa. O raio de ação da

logística estende-se sobre toda a organização, do gerenciamento de matérias-primas até a

entrega do produto final. Os princípios de gerenciamento logístico levaram uns 70 anos ou

mais para ser claramente definidos.

Segundo CHRISTOPHER (1999), o gerenciamento logístico, do ponto de vista de

sistemas totais é o meio pelo qual as necessidades dos clientes são satisfeitas através da

coordenação dos fluxos de materiais e de informações que vão do mercado até a empresa,

suas operações e, posteriormente, para seus fornecedores. Para o autor, o gerenciamento

logístico tem potencial para auxiliar a organização a alcançar tanto a vantagem em

custo/produtividade como a vantagem em valor. Em síntese, as organizações que serão líderes

de mercado no futuro serão aquelas que atingirem os picos gêmeos da excelência: liderança

de custos e de serviços.

Desta forma, as empresas reconhecem que devem estar prontas para enfrentar desafios

logísticos, pois o impacto nas mudanças do conteúdo competitivo é muito grande, trazendo

com isso novas complexidades e problemas para a gerência. Em verdade, dos muitos

problemas estratégicos que as organizações enfrentam talvez o mais desafiante seja o da

logística. BOWERSOX, CLOSS e COOPER (2006) afirmam que as empresas líderes

percebem que um sistema logístico bem projetado e bem operado pode ajudar a alcançar

vantagem competitiva.

Em resumo, a busca pela liderança no mercado não é apenas a redução dos custos

logísticos, mas também a vantagem em valor, visando à plena satisfação do cliente.

Analisando os custos logísticos, define-se numa visão macroeconômica como sendo a

união dos custos das seguintes atividades: transporte, estoque, armazenagem e administração.

Na pesquisa sobre os custos logísticos da economia brasileira desenvolvida pelo Centro

de Estudos em Logística (CEL/Coppead), LIMA (2006) observa que os custos logísticos no

Brasil em 2004 de cada uma das atividades logísticas chegam a um total de R$ 222 bilhões, o

equivalente a 12,6% do PIB (TAB. 2.1).

TAB. 2.1 - Custos Logísticos no Brasil em 2004

Atividade % do

PIB

Transportes 7,5

Estoque 3,9

Armazém 0,7

Administrativo 0,5

Total dos Custos logísticos

12,6

Fonte: LIMA, 2006

Com relação ao total de carga transportada, observa-se que o modo mais utilizado é o

rodoviário, com 59,3% de toneladas por quilometro útil (TKU) e com custo de R$ 109,2

bilhões (TAB. 2.2).

TAB. 2.2 - Matriz de transporte de cargas do Brasil em 2004

Modo de

Transporte

Bilhões de

TKU

% TKU

Custo

(Bilhões R$)

R$ / (TKU

x 1000)

Aéreo 1

0,1%

1,9

1.762

Dutoviário 39

4,5%

2,1

Aquaviário

105

12,2%

7,3

Rodoviário 512

59,3%

109,2

213

Ferrovia 206

23,8%

7,5

TKUs estimados com dados do Geipot atualizados através de percentuais de variação de toneladas da FIPE -

exceto modal aéreo que utiliza dados do DAC e Infraero.

Excluído o custo portuário referente a exportação e importação.

Fonte: LIMA, 2006

Já nos EUA, os custos logísticos (domésticos) equivalem a 8,26% do PIB. Entre os custos

das atividades, o de estoque é relativamente o que apresenta a maior diferença na comparação,

3,9% no Brasil contra 2,1% nos EUA. A outra parte da diferença é relativa ao custo de

transporte, 5,1% e 7,5%, respectivamente. A FIG. 2.1 apresenta o gráfico com esta

comparação.

FIG. 2.1 - Custos Logísticos em relação ao PIB - Brasil x EUA em 2004

Fonte: LIMA, 2006

A partir das comparações dos custos logísticos do Brasil com os EUA, nota-se que

existem diferenças significativas nas atividades de estoque e transporte. Um dos fatores que

reflete na eficiência e conseqüente redução dos custos logísticos pelos EUA é o uso intensivo

da Tecnologia da Informação.

Observando que, de um modo geral, os custos logísticos se concentram na atividade de

transportes e que pela realidade brasileira o modo mais utilizado continua sendo o rodoviário,

conclui-se que se deve ser dada uma atenção especial no gerenciamento logístico desta

atividade, utilizando-se soluções promissoras a partir da aplicação da tecnologia da

informação na logística.

2.5 TECNOLOGIA DA INFORMAÇÃO

A Tecnologia da Informação (TI) em conjunto com as telecomunicações são os principais

responsáveis por esta nova fase econômica e competitiva atual, já que não só aumentou o

número de clientes, como também o número de concorrentes. LICKER (1997) demonstra que

a TI habilitou a competição global, pressionando as empresas a pensar globalmente, em vez

de meramente local ou regionalmente, e salienta que a competição global implica em

desenvolver redes de informação, sistemas interorganizacionais e sistemas que podem

trabalhar em qualquer lugar.

Quanto ao conceito de tecnologia da informação, para OLIVEIRA (1998) informação é

todo dado coletado, tratado e estruturado de forma a gerar algo útil para a tomada de decisão.

Para gerar uma informação competitiva é necessário um gerenciamento sistemático e

dinâmico da informação.

O termo tecnologia de informação para BERALDI et al. (2000) representa todas

tecnologias necessárias para coletar, tratar, interpretar e distribuir as informações em tempo

hábil e de maneira adequada. Sendo assim, pode-se considerar como componente da

tecnologia de informação os sistemas computacionais, incluindo quaisquer softwares e

hardware utilizados como ferramentas para o tratamento de informações em qualquer nível.

Pode-se deduzir que a tecnologia da informação é tudo aquilo que é utilizado para

manipular a informação com o intuito de melhorar a produtividade, a distribuição, a eficácia e

a competitividade das organizações.

2.6 TECNOLOGIA DA INFORMAÇÃO APLICADA A LOGÍSTICA

Todos os objetivos da empresa têm que ser bem delineados e têm que se desenvolver

estratégias em função das mudanças do ambiente externo e interno, que permitam manter a

competitividade. As novas tecnologias não somente mudam o ambiente como também ajudam

a ser competitivos e a logística tem que se valer da TI como uma arma competitiva, a qual se

torna um pré-requisito para o sucesso (CLOSS, 1997). Através da TI pode-se criar e modelar

sistemas de informação destinados a dar suporte à tomada de decisão no gerenciamento da

cadeia logística. A TI deve também ser capaz de agilizar os processos logísticos dando não

apenas maior velocidade, mas também fidelidade à informação.

NOVAES (2001) observa que ocorreu uma grande queda dos custos logísticos globais

nos Estados Unidos no período de 1980 a 1998 e que uma das explicações para este fenômeno

é justamente o uso intensivo e extensivo da Tecnologia da Informação que possibilitou o

melhor aproveitamento da frota, do pessoal e das instalações fixas.

O setor de informática tem apresentado uma dinamicidade impressionante,

experimentando mudanças numa velocidade espantosa, acompanhada de uma redução dos

custos associados à inovação tecnológica. Essa dinamicidade tem permitido aos diversos

setores de negócios se adaptarem às mudanças contextuais de modo relativamente rápido. A

logística não foge a essa regra, tendo incorporado diversas inovações no que diz respeito à

tecnologia da informação. A propósito, a disponibilidade de informações precisas e a tempo é

fundamental para a operação eficaz dos sistemas logísticos, especialmente devido a 3 razões

básicas (FLEURY, 2000):

• Os clientes percebem que informações sobre estado do pedido, disponibilidade de

produtos, programação de entrega e faturas são elementos necessários de serviço total

ao cliente;

• Os executivos percebem que a informação pode reduzir de forma eficaz as

necessidades de estoque e recursos humanos;

• A informação aumenta a flexibilidade.

Assim sendo, as empresas de logística têm utilizado intensivamente a tecnologia da

informação, destacando-se as seguintes aplicações:

2.6.1 APLICAÇÕES DE HARDWARE

• Microcomputadores;

• Palmtops e smartphones;

• Códigos de barra - identificação do produto, contendo destino final, preço acordado,

etc.;

• Rádio freqüência - contato com motoristas;

• Transelevadores - operação de armazenagem;

• Sistemas GPS - acompanhamento da carga por satélite;

• Computadores de bordo - controle de velocidade, rotas, paradas dos caminhões, etc.;

• Picking automático - coleta do produto no local de armazenagem e despacho através de

esteiras.

2.6.2 APLICAÇÕES DE SOFTWARE

• Roteirizadores - definem as melhores rotas para entrega;

• WMS (Warehouse Management System) - Sistema de Gerenciamento de Armazéns;

• GIS (Geographical Information System) - Sistema de Informação Geográfica (mapas

digitalizados, etc.);

• MRP (Manufacturing Resource Planning) - Planejamento dos Recursos da Manufatura;

• Simuladores;

• ERP (Enterprise Resource Planning) - Gestão Empresarial Integrada;

• Previsão de Vendas;

• EDI (Electronic Data Interchange) - Troca Eletrônica de Dados entre Componentes da

Cadeia Produtiva.

Nas aplicações de software, uma prática que se torna cada vez mais comum é a

centralização das informações de uma empresa e de suas filiais numa única base de dados,

pois permite que o gerenciamento logístico e administrativo seja unificado. Uma das

vantagens que podem ser obtidas com o gerenciamento logístico unificado é a redução dos

custos com a distribuição física, pois ele permite a realização do planejamento apontando a

melhor solução global. Na utilização de um roteirizador, por exemplo, isto significa escolher

o centro de distribuição mais adequado para entregar o produto ao cliente.

2.7 DISTRIBUIÇÃO FÍSICA

BALLOU (1993) define a distribuição física como o ramo da logística que trata de

movimentação, estocagem e processamento de pedidos dos produtos finais da empresa.

Significa dizer que a distribuição física está atuando nas transferências dos produtos entre

fábricas e armazéns próprios ou de terceiros, nos seus estoques, nos subsistemas de entrega

urbana e interurbana de mercadorias, nos armazéns e depósitos do sistema, além de outros

aspectos, sendo a área que possui maior interação com a área de marketing.

Para NOVAES (2001), a distribuição física cobre os segmentos que vão desde a saída do

produto da fábrica, até sua entrega final ao consumidor. Entre os esquemas de distribuição

física, os mais comuns são: distribuição da fábrica para um depósito de um atacadista, da

fábrica para um centro de distribuição varejista e da fábrica para a loja de varejo. A

determinação do esquema de distribuição física a ser aplicado é condicionante ao tipo de

produto a ser transportado, pois cada produto requer tratamento diferenciado de acordo com

suas características físicas.

2.7.1 COMPONENTES DE UM SISTEMA DE DISTRIBUIÇÃO FÍSICA

Para NOVAES (2001) a distribuição física se baseia em componentes físicos e

informacionais. Esses componentes são:

• Instalações fixas (centros de distribuição, depósitos) - Espaços destinados a armazenar

produtos até que sejam transferidos para as lojas ou para os clientes. São locais que

possuem um conjunto de equipamentos destinados a descarga dos produtos, transporte

interno e carregamento dos veículos de distribuição;

• Estoque de produtos - Considerado hoje o grande problema de toda empresa, porque

se traduz em custos para armazenagem. Acontece tanto na fábrica, nos centros de

distribuição dos atacadistas, distribuidores e varejistas, nas lojas de varejo e até mesmo

nos veículos de transporte;

• Veículos - Como os produtos normalmente são fabricados em locais, às vezes, bem

distante dos pontos de comercialização, se faz necessário transportá-los. Para isso

existem dois tipos de deslocamentos que envolvem veículos com diferentes

características. Quando o deslocamento é feito entre a fábrica e centros de distribuição,

normalmente são utilizados veículos maiores. Quando o deslocamento é para suprir as

lojas, normalmente são utilizados veículos menores, pois as condições de trânsito em

regiões urbanas não permitem o emprego de veículos maiores. A capacidade máxima

de peso e volume imposta pelos veículos é uma restrição que afeta a distribuição física;

• Informações diversas - Para operar um sistema de distribuição é fundamental se

dispor de um cadastro do cliente com informações como razão social, endereço,

coordenadas geográficas (para uso em Sistema de Informação Geográfica e software de

roteirização), bem como quantidade a ser entregue, condições como restrições de

horário para atendimento, entre outros;

• Hardware e Software - Hoje grande parte das atividades de distribuição é planejada,

programada e controlada por meio de softwares que auxiliam no controle de pedidos,

roteirização de veículos, monitoramento e rastreamento da frota, entre outros. Para que

esses softwares funcionam, faz-se necessário toda uma estrutura de hardware, como

sistemas de GPS, computadores de bordo, coletores de dados, entre outros;

• Estrutura de Custos - Nos casos em que o transporte de carga é realizado de um ponto

para outro e com a lotação do veículo por completo, o frete é cobrado em função da

distância percorrida e pela quantidade de carga deslocada. Já nos casos em que a carga

é fracionada, o veículo não é lotado e a carga é compartilhada por diversos clientes, o

frete é cobrado em função das horas de trabalho do pessoal e do equipamento alocado.

Isto ocorre devido à existência de clientes que demoram muito tempo para receber a

mercadoria, forçando o veículo a esperar em fila durante diversas horas, sem, contudo,

implicar em nenhum aumento da quilometragem percorrida;

• Pessoal - Com a sofisticação dos equipamentos e do tratamento da informação é

importante dispor de pessoal capacitado e constantemente treinado.

É essencial uma boa definição e utilização destes componentes para que possam

representar uma boa gestão e tornar uma empresa mais competitiva.

De uma maneira geral, a literatura apresenta a centralização do planejamento da

distribuição física como uma nova tendência originada pela globalização e pelos novos

conceitos do SCM, que possibilita a otimização global da distribuição entre os centros de

distribuição (depósitos) e os clientes.

2.8 CONSIDERAÇÕES FINAIS

Não se pode pensar em logística de forma estratégica sem associá-la a tecnologia da

informação, que é uma poderosa ferramenta da logística no seu trabalho, pois a tecnologia da

informação vem contribuindo para que a logística forneça altos níveis de competitividade e

eficiência para as empresas.

Um fator essencial é o uso de sistemas de informação que dêem suporte à tomada de

decisão no gerenciamento logístico integrando toda cadeia logística da empresa. Com a

centralização das informações destes sistemas é possível realizar o gerenciamento logístico da

distribuição física englobando todos os depósitos que uma empresa possui, gerando assim

uma vantagem competitiva.

3 O PROBLEMA DE ROTEIRIZAÇÃO DE VEÍCULOS COM MÚLTIPLOS

DEPÓSITOS

3.1 INTRODUÇÃO

O problema de roteirização de veículos (Vehicle Routing Problem - VRP) tem sido

extensivamente estudado por causa da sua abrangente aplicabilidade em muitas situações

reais, incluindo operações logísticas como a distribuição física. O VRP possui uma descrição

simples, mas é difícil de ser resolvido.

Considera-se uma empresa que possui um único depósito e capacidade ilimitada, uma

frota de veículos com capacidade homogênea (iguais) e um conjunto de clientes com as

informações de demanda e localização. Geralmente a demanda total dos clientes excede a

capacidade de um veículo, assim utiliza-se mais de um veículo para distribuir os produtos do

depósito para todos os clientes.

No VRP, cada veículo é designado para uma rota e um cliente é atendido por um veículo

em uma única rota. Cada rota inicia e termina no depósito. Os responsáveis pelas tomada de

decisões na empresa precisam determinar quais clientes são atendidos por quais veículos ou

rotas, que é o problema de roteirização. Também é necessário considerar a seqüência de

atendimento dos clientes em cada rota, que é o problema de programação. O objetivo do VRP

é determinar a menor distância ou tempo total gasto para atender todos os clientes.

O VRP é similar ao conhecido problema do caixeiro viajante (Traveling Salesman

Problem - TSP), exceto que neste não é considerada a capacidade do veículo, atendendo

assim todos os clientes numa única rota. Em outras palavras, o TSP é considerado

simplesmente como um problema de programação, e é conseqüentemente mais simples que o

VRP, que soluciona ambos os problemas de programação e roteirização.

O VRP possui diversas variantes e um ponto em comum é que todas são baseadas num

único depósito, conforme demonstra a TAB. 3.1.

TAB. 3.1 - Classificação dos principais problemas de roteirização de veículos

• TSP - Problema do caixeiro-viajante

• CPP - Problema do carteiro chinês

• MTSP - Problema de múltiplos caixeiros-viajantes

• VRP - Problema clássico de roteirização de veículos

• MDVRP - VRP com múltiplos depósitos

• CARP - VRP com demanda em arcos

• SVRP - VRP com demanda estocástica

• VRPSD - VRP com entregas fracionadas

• FSVRP - VRP com dimensionamento de frota homogênea

• HFFVRP - VRP com frota heterogênea fixa

• FSMVRP - VRP com dimensionamento de frota heterogênea

• PVRP - VRP periódico

• TDVRP - VRP com tempo dependente

• VRPTW - VRP com janelas de tempo

• VRPSTW - VRP com janelas de tempo flexíveis

• PDP - Problema de coleta e entrega (VRP + precedência)

Embora o problema com um único depósito possua maior atração entre os pesquisadores da

área, não são apropriados para alguns casos onde a empresa possui mais de um depósito. Nestes

casos, torna-se necessária a solução do problema de roteirização de veículos com múltiplos

depósitos (Vehicle Routing Problem Multi-depot - MDVRP). Neste problema uma empresa

possui mais de um depósito (ou centro de distribuição) que são utilizados para armazenar e

distribuir os produtos. Neste tipo de problema os tomadores de decisão também precisam

determinar quais clientes serão atendidos por quais depósitos, isto é, solucionando primeiro um

problema de atribuição antes dos problemas de roteirização e programação. Obviamente, este

tipo de problema é mais complexo que o problema com apenas um depósito. Adicionalmente,

tanto o TSP quanto todas as suas variantes, assim como o MDVRP são do tipo NP-Completo,

que é uma subcategoria dos problemas NP (Non-deterministic polynomial time). Isto significa

que, à medida que o problema aumenta o esforço computacional para resolvê-lo cresce de

maneira exponencial. Mesmo com o avanço da tecnologia dos computadores, problemas de

maior porte encontrados em aplicações práticas apresentam muitas variáveis e restrições a serem

consideradas, impossibilitando até o mais avançado computador disponível no mercado a

resolver o problema por um algoritmo exato e obter a solução ótima em tempo de processamento

aceitável.

Assim uma aproximação razoável deve dividir o problema em vários subproblemas de

roteirização e programação atribuindo os clientes para cada depósito e resolver estes

subproblemas individualmente (RENAUD et al., 1996).

3.2 DEFINIÇÃO DO PROBLEMA

No planejamento da distribuição física de uma empresa com múltiplos depósitos considera-

se que o número e posição dos depósitos são predeterminados. Cada depósito uma capacidade

física de armazenamento previamente conhecida. Uma frota de veículos com capacidade limitada

é utilizada para transportar os produtos dos depósitos aos clientes. Cada veículo começa e

termina sua rota no mesmo depósito. A posição e a demanda de cada cliente são conhecidas

previamente. Cada cliente é atendido por um veículo exatamente uma vez.

Este problema prático de distribuição é considerado como o MDVRP e ele fornece apoio à

tomada de três decisões, conforme a figura 3.1.

FIG. 3.1 - Seqüência de tomadas de decisão no MDVRP

Os responsáveis pela tomada de decisão inicialmente devem atribuir os clientes a serem

servidos pelo mesmo depósito, isto é, o problema de atribuição. Logo após, atribuem os clientes

do mesmo depósito a diversas rotas de modo que a capacidade do veículo seja respeitada, o

Atribuir clientes para

depósitos

Atribuição

Atribuir clientes em

cada depósito para rotas

Roteirização

Seqüenciar cada rota

de todos os depósitos

Programação

problema de roteirização. Por último, deve ser decidida a seqüência da entrega de cada rota é

feita.

Geralmente, o objetivo do MDVRP é minimizar a distância total ou o tempo gasto para

servir todos os clientes. Um tempo de entrega menor resulta em um nível mais elevado da

satisfação de cliente. Adicionalmente, o objetivo pode também ser o minimizar o número dos

veículos necessários. Poucos veículos implicam na redução da frota e conseqüentemente no

custo total da operação. Assim, pode se concluir que o objetivo final do MDVRP é aumentar a

eficiência da entrega e reduzir os custos da empresa (HO, et al., 2007).

FIG. 3.2 - Um exemplo do MDVRP

Para melhor compreensão do MDVRP, um exemplo prático com dois depósitos e 12 clientes

é ilustrado na figura 3.2. Os valores entre parênteses ao lado dos depósitos, acima ou abaixo dos

clientes representam as coordenadas. Os segundos valores entre parênteses acima ou abaixo dos

clientes se referem à demanda requisitada pelos clientes. Cada depósito possui uma capacidade

limitada de armazenamento e vários veículos com capacidade homogênea (iguais) e limitada.

Neste exemplo, cada depósito possui capacidade de 24 unidades de produtos e cada veículo pode

Depósitos

Clientes

Rota 2

Rota 1

Rota 2

Rota 1

(10, 10) (4)

(12, 9) (4)

(12, 7) (4)

(10, 6) (3)

(10, 2) (6)

(14, 5) (3)

(14, 3) (7)

(16, 1) (2)

(16, 6) (4)

(16, 9) (3)

(14, 12) (5)

(20, 5)

(24)

(12)

(5, 5)

(24)

(12)

(12, 4) (3)

transportar até 12 unidades de produtos por a rota, que é mostrada nos segundos valores entre

parênteses ao lado dos depósitos.

Para resolver o MDVRP acima, três decisões devem ser feitas seqüencialmente.

Na primeira decisão, os clientes são agrupados para serem servidos pelo depósito A ou pelo

depósito B. Assim, os clientes são atribuídos aos depósitos adjacentes de modo que a distância

do percurso pelo veículo seja mais curta e que a demanda total dos clientes atendidos não

ultrapasse a capacidade do depósito. Neste caso, os clientes 1-6 estão atribuídos ao depósito A,

visto que os clientes 7-12 estão agrupados para ser servidos pelo depósito B.

Na segunda decisão, os clientes de cada grupo são divididos em rotas diferentes. O objetivo

desta decisão é minimizar o número das rotas, ou de veículos utilizados, respeitando a

capacidade do veículo. Para o depósito A, há diversas combinações possíveis de roteirização. O

número mínimo de rotas é dois, por exemplo. Então os clientes 1, 2, e 4 ficam na primeira rota e

os clientes 3, 5, e 6 na segunda rota. Isto é necessário para que a quantidade de produtos

entregues em ambas as rotas não exceda a capacidade máxima do veículo de 12 unidades.

Na terceira decisão, faz-se o seqüenciamento da entrega em cada rota, ou seja, o problema

de programação. Este problema é equivalente ao conhecido TSP (Problema do caixeiro-viajante)

para encontrar uma seqüência ótima de modo que a distância total seja a menor.

3.3 MÉTODOS DE SOLUÇÃO DO PROBLEMA

Os métodos para solução do MDVRP são classificados de acordo com o número de estágios

necessários para sua solução. Cada estágio consiste na solução independente de um problema

complexo. No primeiro estágio a decisão de atribuir os clientes aos depósitos é solucionada pelo

problema de atribuição (Assigment Problem - AP). No segundo estágio as decisões de atribuir os

clientes do mesmo depósito a diversas rotas e de seqüenciá-los para entrega são solucionadas

pelo problema de roteirização de veículos (VRP). O primeiro método para solução do MDVRP

possui um estágio e consiste na solução do AP e do VRP simultaneamente. O segundo método

possui dois estágios e consiste na solução do AP e do VRP separadamente, ou seja, inicialmente

faz-se a atribuição dos clientes aos depósitos e soluciona os subproblemas um a um pelo VRP.

A principal vantagem do primeiro método em relação ao segundo é a obtenção de melhores

soluções com a solução dos dois estágios conjuntamente, pois uma má atribuição pode

influenciar na solução dos subproblemas de roteirização. Sua desvantagem recai sobre a

capacidade de resolver apenas problemas de pequeno porte.

Assim, a escolha do método mais adequado para uso baseia-se no tamanho do problema a

ser solucionado, ou seja, de acordo com o número de depósitos e clientes que o problema possui.

A seguir descrevem-se os métodos de um e dois estágios:

3.3.1 MÉTODO DE UM ESTÁGIO

O método de um estágio possui poucas soluções, pois atraiu menos a atenção de

pesquisadores pelo fato de resolverem apenas problemas de pequeno porte. As soluções

encontradas na literatura utilizam programação inteira.

3.3.1.1 SOLUÇÕES DO PROBLEMA POR UM ESTÁGIO

LAPORTE et al. (1984) formulou problemas simétricos como programação inteira por

branch and bound. Usando a teoria de grafos, o autor explica que cada subproblema do VRP

pode ser definido como um grafo G = (V, A), onde V = {v1,..., vn} é um conjunto de vértices

representando cidades ou consumidores, e A = {(vi, vj): i ≠ j; vi, vj V} é um conjunto de arcos

ligando os clientes. Existe uma matriz de custos C = (cij) de modo que a cada arco (vi, vj) é

associado um custo cij representando a distância, custo ou tempo de viagem. O problema é

definido como simétrico se cij = cji para todo vi, vj V.

Outro algoritmo exato foi proposto por LAPORTE et al. (1988) para o problema assimétrico

do MDVRP. O algoritmo transforma primeiro o problema em um equivalente problema de

atribuição. Soluções ótimas são encontradas pelo algoritmo de branch and bound para cada

subproblema de roteirização. Obteve-se sucesso para instâncias com até três depósitos e 80

clientes.

3.3.2 MÉTODO DE DOIS ESTÁGIOS

Este método é indicado para solução de problemas maiores e utiliza-se de heurísticas para

solução dos dois estágios. Na literatura encontram-se diversos métodos para solução dos dois

estágios individualmente. A partir da união de um dos métodos de solução de ambos os

problemas é obtida uma solução para o MDVRP. Algumas das soluções do AP e do VRP não

foram encontradas em aplicações para o MDVRP. Contudo, também são descritas por serem

potenciais soluções. A seguir descrevem-se as soluções encontradas na literatura para o primeiro

estágio e para o segundo estágio.

3.3.2.1 PRIMEIRO ESTÁGIO - PROBLEMA DE ATRIBUIÇÃO

Os métodos de atribuição descritos nas seguintes seções atribuem clientes aos depósitos de

modo que a capacidade dos depósitos não seja excedida. Estes métodos são de alguma forma,

adaptações ou soluções heurísticas. TANSINI et al. (2001) realiza uma comparação entre

diversos métodos de atribuição para o MDVRP. O autor explica o funcionamento das seguintes

classes de algoritmos de atribuição:

a) atribuição com prioridades,

b) atribuição cíclica,

c) atribuição por clusters

d) atribuição usando o problema do transportes.

3.3.2.1.1 ATRIBUIÇÃO COM PRIORIDADES

Esta classe de algoritmos atribui os clientes com prioridade mais elevada inicialmente. A

prioridade é uma maneira para definir um relacionamento de precedência entre clientes. Este

relacionamento de precedência determina a ordem em que os clientes são atribuídos aos

depósitos. As heurísticas que pertencem a esta classe são: o Algoritmo de Atribuição Paralela, o

Algoritmo de Atribuição Simplificada e o Algoritmo de Atribuição por Varredura. Variam

somente na maneira que suas prioridades são calculadas.

3.3.2.1.1.1 ATRIBUIÇÃO SIMPLIFICADA

Esta heurística é uma variante dos algoritmos mais comuns de atribuição encontrados na

literatura. Neste caso, somente dois depósitos são envolvidos na avaliação de prioridade; a

comparação está entre o custo de atribuir um cliente a seu depósito mais próximo com o custo de

atribuí-lo a seu segundo depósito mais próximo.

3.3.2.1.1.2 ATRIBUIÇÃO PARALELA

A atribuição paralela é assim chamada devido ao fato de que a prioridade para cada cliente é

calculada considerando todos os depósitos ao mesmo tempo. Esta heurística compara o custo de

atribuir um cliente a seu depósito mais próximo com o custo de atribuir o cliente a outro

depósito, conforme figura 3.3

FIG. 3.3 - Atribuição de um cliente ao depósito pelas atribuições: paralela e simplificada

Esta heurística possui o seguinte funcionamento: cada usuário pertence a somente um dos

seguintes conjuntos: 1) Se um cliente foi atribuído para um depósito, 2) NA se o cliente ainda

não foi atribuído para um depósito. Cada depósito Cada depósito pertence apenas a um dos

seguintes conjuntos: 1) DS se a demanda do depósito já foi satisfeita, 2) DNS se a demanda do

depósito ainda não foi satisfeita. Uma atribuição de um cliente para um depósito é possível se: a)

o depósito pertence ao conjunto DNS, b) o cliente pertence ao conjunto NA. Calcula-se então a

urgência u de cada cliente pela seguinte fórmula:

∑

∈

−

DcdDcdu

*)),(*(),((

Depósito

Cliente

Diferença de distância

com um depósito mais

Cria-se uma lista de clientes ordenada em ordem decrescente pelo valor da urgência u e o

cliente com a maior urgência é atribuído ao depósito mais próximo que esteja contido no

conjunto DNS. A heurística termina quando todos os clientes forem atendidos.

3.3.2.1.1.3 ATRIBUIÇÃO POR VARREDURA

Nesta heurística, os clientes são atraídos no sentido do depósito com a maior demanda.

Primeiramente, é necessário determinar um depósito com a demanda mais elevada. A prioridade

é medida a partir da diferença entre a atribuição de um cliente ao seu depósito mais próximo e ao

depósito determinado. Uma prioridade elevada significa que é mais conveniente atribuir o cliente

ao seu depósito mais próximo do que ao depósito com determinado. A figura 3.4 ilustra o

funcionamento da heurística.

FIG. 3.4 - Depósito determinado (D) na atribuição por varredura

3.3.2.1.2 ATRIBUIÇÃO CÍCLICA

O procedimento para esta classe de algoritmos consiste na atribuição de maneira cíclica, um

cliente em determinado tempo a cada depósito. Inicialmente, o algoritmo atribui a cada depósito

o cliente o mais próximo. Atribui então a cada depósito, o cliente mais próximo ao último cliente

atribuído ao depósito, conforme ilustra a figura 3.5. Em geral, a atribuição é muito inconveniente

para os últimos clientes atribuídos.

Depósito

Cliente

Diferença de distância

com um depósito mais

FIG. 3.5 - Atribuição cíclica

3.3.2.1.3 ATRIBUIÇÃO POR CLUSTER

Esta classe dos algoritmos constrói conjuntos compactos de clientes para cada depósito. É

definido um conjunto constituído por um depósito e os clientes atribuído a ele. Quando um

cliente é atribuído a um conjunto, significa que este cliente está atribuído àquele depósito. A

seguir são apresentados os algoritmos que alocam os clientes aos depósitos por Coeficiente de

Propagação e por Três Critérios de Clusterização.

3.3.2.1.3.1 COEFICIENTE DE PROPAGAÇÃO

A maneira como os clientes são incorporados a um conjunto é definida associando

coeficientes de atração aos clientes e aos depósitos já atribuídos. Estes coeficientes representam

as distâncias. Se um cliente ou um depósito possuir um coeficiente de atração menor de 1,

encurtam-se as distâncias a outros clientes (os atrai). Por outro lado, se o coeficiente for maior

que 1, as distâncias serão maiores (os rejeita). Para o caso do coeficiente ser igual a 1, as

distâncias permanecem as mesmas. Este algoritmo é altamente interativo, por causa da seleção

dos coeficientes iniciais (GIOSA, 1999). A figura 3.6 demonstra as distâncias na atribuição por

Coeficiente de Propagação.

Depósito

Cliente

Distância para o cliente mais

próximo não atribuído

Depósito

Cliente

Distância real

Distância escalar

FIG. 3.6 - Distâncias na atribuição por Coeficiente de Propagação

3.3.2.1.3.2 TRÊS CRITÉRIOS DE CLUSTERIZAÇÃO

Este algoritmo é uma adaptação do procedimento proposto para atribuir clientes aos dias da

semana (RUSSELL, 1998). Os três critérios usados nesta aproximação para incluir um cliente

em um conjunto são:

1) Distância média aos conjuntos;

2) Variação da distância média dos clientes nos conjuntos;

3) Distância ao cliente o mais próximo em cada conjunto.

A figura 3.7 ilustra o funcionamento de um dos três critérios de clusterização.

FIG. 3.7 - Distância média para os clusters

3.3.2.1.4 ATRIBUIÇÃO USANDO O PROBLEMA DE TRANSPORTES

O Problema de Transportes consiste em minimizar o custo de transporte total para

transportar produtos de vários depósitos para vários clientes, dado as ofertas nos depósitos e as

demandas dos clientes (BROOKE, 1996). Cada cliente é servido ao menos por um depósito,

atribuindo assim os clientes aos depósitos. Esta solução fornece a atribuição ótima, mas para o

caso de serem resolvidos problemas maiores, torna-se inviável computacionalmente. Sua

formulação matemática é representada por:

Depósito

Clientes num cluster

Cliente

Distância

Onde m é o número de depósitos e n é o número de clientes. A capacidade de cada

depósito i é representada por ai e a demanda de cada cliente j é representada por bj. O custo por

unidade transportada entre o depósito i e o cliente j é representado por cij. A variável de decisão

xij é o somatório das unidades transportadas do depósito i para o cliente j. A figura 3.8 ilustra um

exemplo do funcionamento deste problema, com os depósitos do lado esquerdo, com os valores

de suas capacidades e os clientes do lado direito com os valores de sua demanda. Suas ligações

representam os custos associados a cada origem e destino.

FIG. 3.8 - O problema de transportes

3.3.2.2 SEGUNDO ESTÁGIO - PROBLEMA DE ROTEIRIZAÇÃO DE VEÍCULOS

Uma descrição geral para o problema de roteirização é atribuir e programar a seqüência dos

clientes a cada rota. Os algoritmos para o problema de roteirização de veículos são descritos nas

seguintes seções. Para esta classe de problema foi encontrada uma ampla documentação, desta

forma, estes algoritmos estão divididos em métodos exatos, métodos heurísticos e

metaheurísticas.

464

513

654

867

352

416

690

791

995

682

388

685

[300]

[600]

[250]

[200]

[400]

[350]

[200]

3.3.2.2.1 MÉTODOS EXATOS

Os métodos exatos são aqueles que possuem a capacidade de garantir uma solução

matematicamente ótima para o problema de roteirização. Esses métodos para o VRP produzem

resultados eficientes em termos de tempo computacional quando aplicados a problemas

pequenos, enquanto problemas maiores podem resultar em um consumo de tempo de

processamento de computador muito longo e grande necessidade de memória. Podem-se ressaltar

dois métodos: o método da busca em árvore direta e a programação dinâmica.

O método da busca em árvore direta consiste na construção incremental das rotas dos

veículos por meio de uma árvore branch and bound, onde cada nó corresponde a uma única rota

viável para um veículo. Portanto a árvore terá tantos níveis quanto o número de veículos. Em

cada nó uma lista de rotas passando por um cliente i é gerado para ramificá-lo. O cliente i deve

ser escolhido de maneira que o número de rotas seja pequeno, isto é, será escolhido o cliente tem

um pedido grande ou que seja distante de outros clientes, e que não possa ser inserido em uma

rota já existente. Os limites são geralmente calculados a partir de relaxações do problema

original (LAPORTE et. al, 1986).

O método de programação dinâmica procura resolver um problema de otimização através da

análise de uma seqüência de problemas mais simples que o original. A resolução do problema

original, de N variáveis, é caracterizada pela determinação de uma variável e pela resolução de

um problema com N-1 variáveis.

3.3.2.2.2 MÉTODOS HEURÍSTICOS

Heurísticas são técnicas que procuram boas soluções (próximas da ótima) a um custo

computacional razoável, sem, no entanto, estar obrigada a garantir a solução ótima, bem como

garantir quão próxima uma determinada solução está da solução ótima. As heurísticas foram

desenvolvidas com a finalidade de resolver problemas de elevado nível de complexidade em

tempo computacional razoável. Ao se pensar em um problema altamente combinatório, uma

opção seria analisar todas as combinações possíveis para conhecer a melhor. Se o problema

possui um universo de dados pequeno, realmente esta é a maneira correta de se buscar a melhor

solução, mas os problemas reais, normalmente, possuem um número de combinações muito

grande, o que torna inviável a análise de todas as combinações, uma vez que o tempo

computacional exigido fica impraticável.

Embora os métodos heurísticos não garantam que uma solução ótima seja encontrada, os

benefícios de tempos de processamento de computador e necessidades de memória razoável, as

boas representações da realidade e a qualidade de solução satisfatória são razões para considerar

esta abordagem para o roteirização (BALLOU, 2001). Os métodos heurísticos que se aplicam

aos problemas de roteirização podem ser separados, conforme sua estrutura de execução, em:

Heurísticas construtivas, Heurísticas de melhora iterativa, Heurísticas de duas fases e

Metaheurísticas.

3.3.2.2.2.1 HEURÍSTICAS CONSTRUTIVAS

São métodos para construir uma solução passo a passo, onde em cada passo se adiciona

componentes individuais: nós, arcos, variáveis, etc. As rotas começam vazias e a cada iteração

elas vão sendo expandidas (construídas). A cada iteração, além da geração de novos elementos é

feita a eliminação dos elementos que não satisfaçam a um critério determinado para a

permanência na lista, guardando-se o melhor conjunto de seqüências (melhor rota) encontrado.

As principais heurísticas construtivas são os procedimentos de economia e inserção, destacando-

se as heurísticas de CLARK AND WRIGHT (1964) e de MOLE AND JAMESON (1976).

a) HEURÍSTICA DE CLARK AND WRIGHT

A heurística das economias de Clark and Wright se baseia na noção de economias, que pode

ser definida como o custo da combinação, ou união, de duas sub-rotas existentes. Inicialmente,

cada cliente é servido por um veículo, constituindo rotas entre o depósito e cada cliente, como

demonstra a figura 3.9.

FIG. 3.9 - Passo inicial do algoritmo de Clark and Wright

Seja cij o custo de viagem partindo de um cliente i a um cliente j, podendo ser dado em

distância percorrida ou tempo de deslocamento. Duas rotas que contêm os clientes i e j podem

ser combinadas, desde que i e j estejam ou na primeira ou na última posição de suas respectivas

rotas e que a demanda total das rotas combinadas não ultrapasse a capacidade do veículo e/ou o

tempo total da jornada de trabalho. Em cada iteração, analisam-se todas as combinações de rotas

através da fórmula s

= c

+ c

- c

, onde 0 representa o depósito. As duas rotas que renderem a

maior economia de combinação são unidas, conforme ilustra a figura 3.10 (LIU e SHEN, 1999).

FIG. 3.10 - União de rotas pelo algoritmo de Clark and Wright

O algoritmo de CLARK and WRIGHT é detalhado a seguir:

1. Calcular os ganhos Sij para todos os pares ij (i j, i 0, j 0).

2. Ordenar os pares ij na ordem decrescente dos valores do ganho Sij.

3. Começar pelo par ij com maior ganho Sij e proceder na seqüência obtida em 2.

4. Para um par de nós ij, correspondente ao k-ésimo elemento da seqüência 2 verificar se i e j

estão ou não incluídos num roteiro já existente:

4.1. Se i e j não estão incluídos em nenhum dos roteiros já abertos, então criar um novo

roteiro com os nós i e j.

4.2. Se exatamente um dos pontos i ou j já pertence a um roteiro pré-estabelecido, verificar

se esse ponto é o primeiro ou o último do roteiro (adjacente ao nó 0, depósito). Se isso ocorrer,

acrescentar o arco ij a esse roteiro. Caso contrário, passar para a etapa seguinte, saltando o par ij.

4.3. Se ambos os nós já pertencem a dois roteiros pré-estabelecidos (roteiros diferentes),

verificar se ambos são extremos dos respectivos roteiros (adjacentes ao nó 0). Nesse caso fundir

os dois roteiros num só. Caso contrário, passar para a etapa seguinte, pulando o par ij.

4.4. Se ambos os nós i e j pertencem a um mesmo roteiro, pular para a etapa seguinte.

5. Continuar o processo até que o total de clientes da lista de ganhos tenha sido exaurido. Se

sobrar algum ponto não incluído em nenhum roteiro, deverão ser formados roteiros

individualizados, ligando o depósito a cada ponto e retornando à base.

3.3.2.2.2.2 HEURÍSTICAS DE MELHORA ITERATIVA

São heurísticas que, a partir de uma solução inicial, realizam iterações sucessivas, tentando

buscar soluções que forneçam um menor custo a cada iteração. Os algoritmos comuns deste tipo

de heurística são os baseados na troca k-OPT, como a 2-OPT e 3-OPT (GOLDBARG e LUNA,

2000). A figura 3.11 demonstra o funcionamento da heurística 3-OPT com dois possíveis novos

percursos.

FIG. 3.11 - Dois possíveis novos percursos

3.3.2.2.2.3 HEURÍSTICAS DE DUAS FASES

Objetivam reunir os clientes, designando os veículos aos grupos e então encontrar o melhor

percurso dentro deste grupo. A ordem das fases pode ser: primeiro agrupar para depois roteirizar

ou primeiro roteirizar para depois agrupar (GOLDBARG e LUNA, 2000). Os algoritmos de

varredura (algoritmos de busca que percorrem todos os vértices do problema) são normalmente

utilizados na resolução deste tipo de problema.

3.3.2.2.3 METAHEURÍSTICAS

A grande desvantagem das heurísticas reside na dificuldade de fugir de ótimos locais, o que

deu origem à outra metodologia, chamada de metaheurística, que possuem ferramentas e algum

tipo de memória que possibilitam sair destes ótimos locais, permitindo a busca em regiões mais

promissoras. Além disso, normalmente possuem como parte do algoritmo alguns elementos

probabilísticos associados. O grande desafio é produzir, em tempo mínimo, soluções tão

próximas quanto possíveis da solução ótima.

Dentre os procedimentos enquadrados como metaheurísticas que surgiram ao longo das

últimas décadas, destacam-se: Algoritmos Genéticos (AGs), Simulated Annealing, Busca Tabu

(BT), Greedy Randomized Adaptative Search Procedure (GRASP), Variable Neighborhood

Descent (VND), Colônia de Formigas (AC) e Scatter Search (SS).

CORDEAU et al. (2005) faz uma revisão das melhores metaheurísticas propostas e

GRENDEAU et al. (2007) cria uma bibliografia categorizada das principais metaheurísticas para

solução do VRP e de suas extensões. Os autores também explicam o funcionamento básico de

cada metaheurística, assim como é feito a seguir.

3.3.2.2.3.1 BUSCA TABU

A Busca Tabu é um procedimento de otimização local que admite soluções de piora para

escapar de ótimos locais. Em sua forma original, a cada iteração procura-se um ótimo local

selecionando-se o melhor vizinho s’ da vizinhança N(s) da solução corrente s.

Independentemente de f(s’) ser melhor ou pior que f(s), s’ será sempre a nova solução corrente,

conforme ilustra a figura 3.12. Entretanto, apenas esse mecanismo não é suficiente para escapar

de ótimos locais, uma vez que pode haver retorno a uma solução previamente gerada. Para evitar

isso, o algoritmo usa o conceito de lista tabu. Esta lista define todos os movimentos com certo

atributo como sendo tabu por um determinado número de iterações, conhecido como tempo tabu.

Tais movimentos são proibidos a menos que a solução satisfaça a certo critério de aspiração, em

geral que essa solução seja melhor que a melhor solução encontrada até então.

FIG. 3.12 - Exemplo do funcionamento da Busca Tabu

Os atributos são escolhidos para prevenir o retorno a soluções visitadas recentemente e por

possuírem características fáceis de detectar. O procedimento chega ao fim quando alcança certo

critério de parada, geralmente um determinado número de iterações sem melhoras.

Segundo TANURE (1999), as dificuldades presentes nesta técnica são relacionadas à

construção do algoritmo de Busca Tabu. É necessária uma considerável experiência e

experimentação para a construção das regras e para avaliar se a natureza da dinâmica está sendo

controlada corretamente.

3.3.2.2.3.2 ALGORITMOS GENÉTICOS

O Algoritmo Genético (AG) foi desenvolvido por HOLLAND (1975). Mais tarde,

GOLDBERG (1989) disseminou o uso do AG aplicando-o a uma série de problemas de

otimização. Os Algoritmos Genéticos empregam um processo adaptativo e paralelo de busca de

soluções em problemas complexos, o que o torna uma técnica muito útil em problemas de

otimização. São procedimentos de pesquisa iterativos baseados no processo biológico de seleção

natural e hereditariedade genética. Lidam com populações em vez de soluções individuais: as

soluções interagem, misturam-se e produzem “filhos” que se espera que retenham as boas

características dos pais.

Inicialmente, é gerada uma população de cromossomos formada por um conjunto aleatório

de indivíduos que podem ser vistos como possíveis soluções do problema. Durante o processo

evolutivo, esta população é avaliada: para cada indivíduo é dada uma nota, ou índice, refletindo

sua habilidade de adaptação a determinado ambiente. Uma porcentagem dos mais adaptados são

mantidos, enquanto os outros são descartados (darwinismo). Os membros mantidos pela seleção

podem sofrer modificações em suas características fundamentais através de mutações e

cruzamento (crossover) ou recombinação genética gerando descendentes para a próxima geração

(figura 3.13). Este processo, chamado de reprodução, é repetido até que uma solução satisfatória

seja encontrada.

FIG. 3.13 - Soluções (filhos) obtidos a partir do cruzamento de dois resultados (pais)

3.3.2.2.3.3 SIMULATED ANNEALING

O Simulated Annealing - SA é um método de busca local que aceita movimentos de piora

para escapar de ótimos locais. Ele foi proposto originalmente por KIRKPATRICK et al. (1983),

e se fundamenta em uma analogia com a termodinâmica ao simular o resfriamento de um

conjunto de átomos aquecidos. Esta técnica começa sua busca a partir de uma solução inicial

qualquer e o procedimento pára quando a temperatura chega a um valor próximo de zero,

conforme ilustra a figura 3.14.

FIG. 3.14 - Representação do resfriamento em relação ao tempo

A cada geração de uma solução s’ para uma s é avaliada conforme a função objetivo. Se s’

for melhor que s então s’ é aceito como nova solução. Se não for, mesmo assim ela poderá ser

aceita, com um fator regulador, que adéqua a probabilidade de aceitação de uma solução de pior

custo (NEVES, 2004).

3.3.2.2.3.4 GRASP - GREEDY RANDOM ADAPTIVE SEARCH PROCEDURE

O processo de busca adaptativa gulosa e randômica é um método iterativo, proposto por

FEO e RESENDE (1995) que consiste de duas fases:

• Uma fase de construção, na qual uma solução é gerada, elemento a elemento;

• Uma fase de busca local, na qual um ótimo local na vizinhança da solução construída é

pesquisado.

A melhor solução encontrada ao longo de todas as iterações GRASP realizadas é retornada

como resultado. Na fase de construção do algoritmo GRASP, uma solução viável é construída

iterativamente, um elemento da solução por vez, até que a solução esteja completa. Os elementos

candidatos que compõem a solução são ordenados em uma lista, chamada de lista de candidatos,

a qual contém todos os candidatos. Esta lista é ordenada por uma função gulosa que mede o

benefício que o mais recente elemento escolhido concede à parte da solução já construída.

Um subconjunto denominado lista restrita de candidatos (LRC) é formado pelos melhores

elementos que compõem a lista de candidatos, o tamanho da lista restrita de candidatos é

controlado por um parâmetro α [0,1], onde para α = 0 tem-se um comportamento puramente

guloso do algoritmo e para α = 1 um comportamento aleatório. A componente probabilística do

método é devida à escolha aleatória de um elemento da lista restrita de candidatos, conforme

demonstra a figura 3.15. Este procedimento permite que diferentes soluções de boa qualidade

sejam geradas.

FIG. 3.15 - Representação do funcionamento do GRASP

3.3.2.2.3.5 VND - VARIABLE NEIGHBORHOOD DESCENT

No método VND, proposto por MLADENOVIC e HANSEN (1997), explora-se o espaço de

soluções através de trocas sistemáticas de estruturas de vizinhança. Uma nova solução é aceita

somente quando for de melhora em relação à solução corrente e retornam-se à primeira estrutura

quando isto acontece. A melhora é definida pela função de avaliação de cada solução.

Os mesmos autores propuseram outro método chamado VNS - Variable Neighborhood

Search, que também explora o espaço de soluções através de trocas sistemáticas de estruturas de

vizinhança. Esse método se difere do método VND por gerar vizinhos da solução corrente de

forma aleatória, prevenindo assim a ciclagem, situação que pode ocorrer se alguma regra

determinística for usada.

3.3.2.2.3.6 ACS - ANT COLONY SYSTEMS

O algoritmo de colônia de formigas artificial ou Ant Colony Systems (ACS) é inspirado pelo

comportamento de colônias de formigas reais, em particular, pelo seu comportamento na procura

de alimento. Uma das idéias centrais do ACS, proposto originalmente por DORIGO et al. (1991),

é a comunicação indireta baseado em trilhas (caminhos ou trajetos) de feromônios entre uma

colônia de agentes denominadas formigas (ants).

Algoritmo

Guloso

Randomização

Melhor Solução Encontrada

Espaço de Soluções

FIG. 3.16 - Comportamento de uma colônia de formigas ao se deparar com um obstáculo

Quando é inserido um obstáculo no caminho já existente, são explorados novos caminhos

aleatoriamente e com o passar do tempo haverá uma concentração maior de feromônios no

caminho mais curto. Este comportamento é ilustrado na figura 3.16.

O ACS é uma técnica da inteligência coletiva (swarm intelligence) baseada em uma

população de agentes (formigas) e que possui as seguintes características:

(i) é um algoritmo não-determinístico baseado em mecanismos presentes na natureza, isto é,

ele é baseado no comportamento de formigas para a determinação de caminhos através de suas

colônias para procura eficiente de fontes de comida;

(ii) é um algoritmo paralelo e adaptativo, pois uma população de agentes move-se

simultaneamente, de forma independente e sem um supervisor (não há um controle ou supervisão

central);

(iii) é um algoritmo cooperativo, pois cada agente (formiga) escolhe um caminho com base

na informação (trilhas de feromônios) depositadas por outros agentes que tenham selecionado

previamente o mesmo caminho. Este comportamento cooperativo tem ingredientes de

autocátalise (catálise provocada por feromônios que se formam no próprio sistema reativo), isto

é, o ACS providencia uma realimentação positiva, desde que a probabilidade de um agente

escolher o caminho aumenta com o número de agentes que escolheu previamente aquele

caminho.

3.3.2.2.3.7 SCATTER SEARCH

A metaheurística Scatter Search (SS), também conhecida como busca dispersa (BD) é um

procedimento metaheurístico para resolver problemas de otimização de natureza combinatória e

apresenta similaridades com os algoritmos genéticos, a qual difere no uso de estratégias

determinísticas para atingir diversificação e intensificação e no tamanho da população. Ela

baseia-se na combinação de soluções que aparecem no chamado conjunto de referência (RefSet).

Este conjunto armazena boas soluções que foram encontradas durante o processo de busca

GLOVER et al. (2003).

3.3.2.3 SOLUÇÕES DO PROBLEMA POR DOIS ESTÁGIOS

A partir da combinação dos métodos de solução do AP e do VRP que foram descritos,

obtém-se diferentes soluções para o MDVRP. Não existem propostas para a maioria destas

combinações, pois nem todas fornecem boas soluções. A seguir descrevem-se as soluções

encontradas na literatura para o MDVRP.

Um dos primeiros métodos de dois estágios foi criado por TILLMAN (1969), que utilizou a

heurística das economias de Clarke e Wright. O algoritmo atribui inicialmente os clientes ao

depósito mais próximo (atribuição paralela) e reconstrói rotas entre depósitos e clientes. Logo

após, é feita uma união gradual entre rotas longas utilizando o critério das economias.

TILLMAN E HERING (1971) utilizam a mesma idéia, mas desta vez com uma melhoria no

processo ao considerar o efeito de cada decisão de atribuição potencial nas próximas iterações.

Finalmente em TILLMAN E CAIN (1972), o processo original de TILLMAN (1969) é usado

com um esquema parcial e numerado que maximiza o critério das economias. Todas heurísticas

acima são construtivas e não são utilizadas na fase da pós-otimização.

WRAEN E HOLLIDAY (1972) apresentam uma heurística que constrói soluções pelo

processo de varredura e pode ser aplicado ao VRP ou ao MDVRP. Em primeiro lugar ele atribui

temporariamente cada cliente ao seu depósito mais próximo, usa a referência de eixos e computa

seu ângulo polar com o respectivo depósito. Então todo cliente é escolhido através da ordenação

do seu ângulo polar. Estes são atribuídos interativamente a novas ou antigas rotas, que envolvem

a última distância adicionada. São feitas alocações a diferentes depósitos. Estes autores também

apresentam uma maneira diferente de calcular o ângulo polar que leva em consideração a

configuração do ponto em volta de cada depósito. Esta nova ordenação é usada para gerar quatro

diferentes soluções iniciais atribuindo inicialmente clientes a quatro diferentes posições na lista

ordenada. A melhor destas quatro soluções é escolhida como entrada a uma fase de melhorias.

Esta última fase utiliza sete procedimentos repetidamente até que nenhuma melhoria possa ser

feita. O resultado é reportado em dois problemas com dois depósitos e com mais de 176 cidades.

GILLETT e JOHNSON (1976) também apresentam uma heurística que constrói soluções

pelo processo de varredura. Inicialmente clientes são inicialmente atribuídos a depósitos para

formar grupos compactos e desunidos. Vários VRPs são resolvidos independentemente ao fim da

atribuição dos clientes a cada depósito, utilizando o algoritmo de varredura de GILLETT e

MILLER (1974). Para melhorar a solução, o algoritmo seleciona possíveis clientes que estejam

localizados entre dois depósitos. Cada depósito se transforma em um centro de atração para cada

cliente. Os VRPs são novamente resolvidos e o algoritmo pára após todos os clientes serem

atendidos pelos depósitos. Os autores apresentam resultados para os problemas de

CRISTOFIDES E ELION (1969) e introduzem quatro novos problemas de 246 cidades tendo

entre 2 e 5 depósitos.

GOLDEN et al. (1977) propõe duas aproximações para o MDVRP. O primeiro é baseado no

método proposto por YELLOW (1970) para o método das economias. Por outro lado, para

limitar os requisitos de armazenagem de informação, eles utilizaram uma estrutura de grade do

problema e apenas consideraram a união de vértices em células adjacentes nesta grade. Na

segunda aproximação, o MDVRP é resolvido em duas fases. Primeiro os clientes são atribuídos e

um VRP separado é então resolvido para cada depósito. O processo utilizado para atribuir

clientes a depósitos é baseado na idéia de clientes fronteiriços, ou seja, é obtida diferença entre as

distâncias do cliente para dois depósitos mais próximos e se este valor resultante exceder um

parâmetro pré-determinado, então o cliente é declarado fronteiriço. Todo cliente fronteiriço é

atribuído a depósitos usando o primeiro algoritmo. O VRP é então resolvido para cada depósito e

ele é seguido por uma fase de melhoria. Os resultados são apresentados contendo mais de 100

clientes e 4 depósitos.

RAFT (1982) apresenta uma técnica de solução que pode manipular outros objetivos com a

minimização do comprimento da rota. Esta heurística é um algoritmo modular que decompõe o

problema em pequenos subproblemas. O algoritmo começa uma fase de atribuição de rotas.

Depois de estimar o número de veículos necessário, o algoritmo constrói grupos de clientes, cada

um atribuído à um veículo. Estes grupos não são atribuídos a nenhum depósito e são construídos

para proporcionar uma menor distância. Na próxima fase, cada rota é atribuída a um depósito.

Por fim, o processo de melhoria 2-OPT expandido de LIN (1965) é aplicado a cada rota. O teste

resulta em 6 problemas e 149 cidades e indica que este algoritmo é comparável com o algoritmo

de GILLET e JOHNSON (1976).

CHAO et al. (1993) descreve uma heurística de várias fases. Os clientes são atribuídos aos

seus depósitos mais próximos e um VRP é resolvido para cada depósito utilizando o algoritmo

modificado das economias de GOLDEN et al (1977). Esta solução é melhorada pela

movimentação de clientes para diferentes depósitos. Os autores utilizam a melhoria de

“gravação-por-gravação” aproximado de DUECK (1990) que permite melhoramentos da solução

atual. Dois processos de reinicializacão são também utilizados para diversificar a procura. Os

resultados são apresentados para os 11 problemas de benchmark de GILLET e JOHNSON

(1976) e para 12 novas instâncias mais de 360 clientes e 9 depósitos.

RENAUD et al. (1996) propõe uma nova heurística para solução do MDVRP com restrições

de capacidade e tamanho da rota. Na fase de atribuição é utilizada a heurística Improved Petal

proposta por RENAUD et al. (1996), que atribui cada cliente ao seu depósito mais próximo. Na

fase de roteirização é utilizada a metaheurística busca tabu. O autor explora o desempenho dos

mecanismos de diversificação e intensificação embutidos no método. Os resultados são

apresentados para os 11 problemas de CHRISTOFIDES E EILON (1969) e GILLET e

JOHNSON (1976) e para 12 novas instâncias de CHAO et at.(1993).

CHAN e BAKER (2005) propõem uma solução para o MDVRP com Freqüência de Serviço.

Os clientes são atribuídos aos depósitos utilizando a heurística de floresta geradora mínima e um

VRP é resolvido para cada depósito utilizando o algoritmo modificado das economias. A

heurística foi aplicada ao Serviço de Correio do Departamento de Defesa dos EUA que realiza a

distribuição por transporte aéreo numa rede com 12 depósitos regionais e 181 locais de demanda

(clientes). Os autores relatam esta instância do problema como sendo de grande porte, inclusive

maior do que outras encontradas na literatura, então a consideram como método de validação do

procedimento proposto.

NAGY e SALHI (2004) estudam o VRP e o MDVRP com Coletas e Entregas. Os autores

utilizam-se da heurística construtiva de múltiplas rotas gigantes (SALHI et al. 1992) para

resolver o VRP com Coletas e Entregas, que podem ser do tipo mista ou simultânea. Por fim,

desenvolveram uma adaptação ao funcionamento com múltiplos depósitos, utilizando-se da

heurística de clientes fronteiriços (borderline customers) (SALHI e SARI, 1997). Os resultados

são apresentados para os problemas de CHRISTOFIDES et al. (1979) com um único depósito e

para os problemas de GILLET e JOHNSON (1976) com 2 à 5 depósitos.

LIM e WANG (2005) estudam o MDVRP com Distribuição Fixa de Veículos. Neste

problema, cada depósito possui um número limitado de veículos. São propostas duas

aproximações para solução do problema. Na primeira utilizou-se o método de um estágio e

modelou-se como um problema de programação binária. Na segunda utilizou-se o modelo de

dois estágios. No estágio de atribuição utilizaram-se da heurística de Alocação-Roteirização de

SALHI e SARI (1997) e no estágio de roteirização utilizaram-se da metaheurística Busca Tabu.

Os autores apresentam resultados para 22 instâncias do problema e compararam com os

resultados de CHAO et al. (1993) e GIOSA et al. (2002). Segundo os autores, o trabalho foi

baseado em vários trabalhos de consultoria que desenvolveram para empresas de transporte de

Hong Kong.

BONASSER (2005) estuda o MDVRP com Frota Heterogênea Fixa. Na fase de alocação

utilizou-se da heurística de designação por urgências, versão paralela. Na fase de roteirização, foi

criada uma metaheurística híbrida batizada de Routing AnTS, que baseia-se na heurística das

economias, busca tabu e colônia de formigas. O autor também explora o desempenho dos

mecanismos de diversificação e intensificação embutidos nos métodos. São utilizados com a

finalidade de testar as estratégias de solução conjuntos de instâncias clássicas para problemas de

roteirização de veículos em sua forma padrão, com frota heterogênea e com múltiplos depósitos.

O autor conclui que a busca tabu efetua a intensificação com maior eficiência, enquanto a

colônia de formigas promove melhor diversificação. A metaheurística híbrida, por sua vez,

apresenta melhor desempenho que as estratégias anteriores de uma maneira geral. Além da

utilização dos problemas retirados da literatura, aplicaram-se as estratégias de solução para uma

situação real da Força Aérea Brasileira, no caso, a operação de assistência humanitária realizada

pela mesma.

CREVIER et al. (2007) propõe solução para o MDVRP com Rotas entre Depósitos. Neste

problema os veículos podem ser reabastecidos em depósitos intermediários ao longo de sua rota.

Na fase de alocação utilizaram-se do método exato de branch and bound. No estágio de

roteirização utilizaram-se da metaheurística Busca Tabu e aplicam a pós-otimização para as

rotas. Os autores apresentam resultados para instâncias do MDVRP estudadas por CORDEAU et

al. (1997) e concluem que a heurística fornece soluções robustas com um tempo computacional

reduzido.

HO et al. (2007) propõe uma solução híbrida para o MDVRP baseada em algoritmo genético

com soluções iniciais aleatórias ou heurísticas. Para a solução inicial aleatória são gerados

resultados aleatórios para os problemas de atribuição e roteirização. Já para a solução inicial

heurística é gerada a atribuição pela heurística paralela e a roteirização pelo algoritmo das

economias de Clark e Wright. As duas soluções iniciais são submetidas às fases de melhora, de

avaliação, de seleção e finalmente às operações genéticas de cruzamento e mutação. O autor

compara as duas soluções finais obtidas e verifica que se obteve melhores resultados partindo de

uma solução inicial heurística e que houve um melhoramento significativo com a aplicação do

algoritmo genético.

3.4 COMPARAÇÃO ENTRE OS MÉTODOS DE SOLUÇÃO DO PROBLEMA

Nos itens 3.3.1.2 e 3.3.2.3 foram descritos os principais problemas de roteirização de

veículos com múltiplos depósitos encontrados na literatura. Este item tem como objetivo

apresentá-los de uma forma mais simplificada e genérica, a fim de facilitar o entendimento e

mostrar a evolução e os métodos utilizados solução.

A partir da TAB. 4, comparam-se as soluções do MDVRP quanto aos métodos utilizados

para solução do AP e do VRP e quanto ao tamanho do maior problema que pôde ser solucionado,

indicado pelo número de clientes e depósitos.

Entre as soluções do problema por um estágio, aquela que solucionou os maiores problemas

foi proposta por LAPORTE et al. (1988), que utilizando o método exato de branch and bound,

reportou resultados para o problema assimétrico com até com 3 depósitos e 80 clientes.

Já entre as soluções do problema por dois estágios, aquela que solucionou o maior problema

encontrado na literatura foi proposta por CHAN e BAKER (2005), que aplicaram a heurística de

floresta geradora mínima para solução da primeira fase e o método das economias de Clark and

Wright na segunda fase. Os autores reportaram resultados para o problema com até 12 depósitos

e 181 clientes.

Observa-se que o método de solução por dois estágios predomina sobre o conjunto de

soluções encontradas na literatura. Para cada um dos estágios verifica-se que existem diversos

métodos de solução, resultando diversas combinações do problema. Porém, as mesmas poderiam

ser adicionadas ao resultando em novos métodos de solução. Obviamente, se fossem

consideradas todas as combinações, o número de métodos de solução seria muito grande.

TAB. 3.2 - Comparação entre os trabalhos sobre o MDVRP

Autor (ano) Método de solução do AP Método de solução do VRP Tamanho

TILLMAN (1969)

Heurística

Paralela

heurística construtiva

economias (Clarke and Wright)

d = #, c = #

WREN e HOLLIDAY (1972)

Heurística

Paralela

heurística construtiva

agrupa-roteiriza

d = 2, c = 176

GILLETT e MILLER (1974)

Heurística

Paralela

heurística construtiva

agrupa-roteiriza

d = 2 a 5, c = 249

GOLDEN et al. (1977)

Heurística

Varredura

heurística construtiva

economias (Clarke and Wright modificado)

d = 4, c = 100

LAPORTE (1984)

método exato (problema simétrico)

branch and bound

d = 2, c = 50

LAPORTE (1988)

método exato (problema assimétrico)

branch and bound

d = 3, c = 80

CHAO et al. (1993)

Heurística

Varredura

heurística construtiva

economias (Clarke and Wright modificado)

d = 9, c = 360

RENAUD et al. (1996)

Heurística

Improved Petal

Metaheurística

busca tabu

d = 9, c = 360

NAGY e SALHI (2004)

Heurística

borderline customers (SALHI e SARI, 1997)

heurística construtiva

múltiplas rotas gigantes (SALHI et al.)

d = 5, c = 50 a 249

LIM e WANG (2005)

Heurística

borderline customers (SALHI e SARI, 1997)

Metaheurística

busca tabu

d = #, c = 200

BONASSER (2005)

Heurística

Paralela

metaheurística híbrida

busca tabu e colônia de formigas (AnTS)

d = 7, c = 182

CHAN e BAKER (2005)

Heurística

floresta geradora mínima

heurística construtiva

economias (Clarke and Wright)

d = 12, c = 181

CREVIER et al. (2007)

Método exato

branch and bound

Metaheurística

busca tabu

d = 7, c = 288

HO et al. (2007)

Heurística

Paralela

metaheurística híbrida

algoritmo genético

d = 2, c = 50 a 100

d indica o número de depósitos, c indica o número de clientes e “#” indica um valor desconhecido

3.5 CONSIDERAÇÕES FINAIS

Demonstraram-se os principais métodos de solução encontrados na literatura para o

MDVRP. Como o problema é do tipo NP-Difícil, a maioria das estratégias de solução utiliza

métodos heurísticos ao invés de métodos exatos. Diversos trabalhos utilizam heurísticas

construtivas e de melhoria, com o objetivo de encontrar uma solução de boa qualidade em um

tempo computacional razoável. Para obter melhores soluções que as soluções obtidas através de

heurísticas construtivas, diversos trabalhos utilizaram as metaheurísticas.

Identificou-se também o grande potencial das soluções híbridas, mostrando que vale a pena

investir na combinação das metaheurísticas a fim de aproveitar as suas melhores características.

A partir da comparação realizada entre todos os métodos para solução do problema,

identificou-se que para solução de problemas de grande porte, o uso de heurísticas é o mais

recomendado devido sua maior capacidade em relação aos métodos exatos e seu menor tempo

computacional em relação às metaheurísticas.

4 SISTEMA DE INFORMAÇÃO GEOGRÁFICA LIVRE

4.1 INTRODUÇÃO

Entre as diversas aplicações incorporadas pela Tecnologia da Informação uma das que mais

se destacam é o Sistema de Informação Geográfica (SIG), que fornece suporte à tomada de

decisão para as mais diversas áreas de planejamento e operação. Sua principal vantagem é a

possibilidade de incorporar a posição geográfica aos objetos do mundo real. Entre as aplicações

de um SIG se encontra a roteirização de veículos que se utiliza de diversas das funcionalidades

para encontrar soluções cada vez melhores.

4.2 SISTEMA DE INFORMAÇÃO GEOGRÁFICA

O conceito de representar num mesmo mapa temas diferentes, remonta há alguns séculos

atrás. Como exemplo tem-se os mapas da batalha de Yorktown, da Revolução Americana,

mostrando os movimentos de tropas através desse recurso, o "Atlas to Accompany the Second

Report of the Irish Railway Commissioners" mostrando dados acerca de população, fluxo de

tráfico, geologia e topografia sobrepostos no mesmo mapa básico. Na área da saúde, o exemplo

clássico e pioneiro foi o mapa elaborado pelo Dr. John Snow, que mostrava as localizações dos

casos de morte por cólera no centro de Londres em setembro de 1853 (BRETERNITZ, 2001).

Com o avanço dos conhecimentos e a complexidade das atividades, o volume de dados

concentrados no ambiente de trabalho tornou-se muito grande para ser utilizado manualmente.

O avanço dos recursos computacionais permitiu o desenvolvimento de tecnologias capazes

de gerenciar grande quantidade de informações de forma rápida e a custos baixos.

4.2.1 ORIGENS

Segundo BRETERNITZ (2001), a criação do primeiro SIG, como se conhece hoje, remonta

a década de 1960, no Canadá. Convergiram para a sua criação a preocupação emergente pelas

questões ambientais, o reconhecimento pelo governo da necessidade de gerenciar os recursos

naturais e os avanços no campo computacional, tanto ao nível de hardware quanto de software.

Somente computadores poderiam manipular grandes quantidades de dados necessários as

atividades que deveriam ser desenvolvidas. O SIG criado foi denominado CGIS (Canada

Geograph Information System) e foi utilizado no inventário das terras daquele país. Em seguida,

outros projetos se seguiram:

• STORET (1964), do Serviço de Saúde Pública dos Estados Unidos;

• MIDAS (1964), do Serviço Florestal americano;

• DIME, do U.S. Bureau of the Census, também dos anos 60;

• criação, pela Universidade de Harvard, do "Harvard Laboratory for Computer Graphics

and Spatial Analysis".

Porém, a grande explosão no uso e desenvolvimento de SIG's se deu a partir de meados dos

anos de 1990, quando as novas gerações de microcomputadores aliaram alta capacidade de

processamento e armazenamento com baixos custos e, em outra frente, cada vez mais dados

sócio-econômicos e ambientais espacialmente identificados (georreferenciados) foram

disponibilizados.

4.2.2 DEFINIÇÃO

Primeiramente, deve-se entender um SIG como o resultado do desenvolvimento de várias

áreas da ciência, onde cada uma delas interage com as demais visando uma melhor

produtividade/desempenho. Dentre essas áreas, tem-se a Geografia, a Cartografia, o

Sensoriamento Remoto, o Fotogrametria, a Geodésica, a Estatística, a Ciência da Computação, a

Engenharia de Software, a Matemática e a Avaliação.

Dada essa multidisciplinaridade, é natural que não exista um consenso sobre uma definição

única que conceitualize um SIG. Entre diversas definições, BURROUGH & MCDONNELL

(1998), CÂMARA (1996) e CARVALHO et al. (2000), concordam que o SIG é um conjunto de

hardware e software utilizado para armazenar, manipular, analisar e visualizar dados espaciais

georreferenciados.

4.2.3 COMPONENTES DE UM SIG

Uma das principais características de um SIG é sua capacidade de manipular dados gráficos

(cartográficos) e não gráficos (descritivos) de forma integrada, provendo uma ferramenta

consistente para análise e consulta. Portanto, é possível ter acesso às informações descritivas de

um fenômeno geográfico a partir de sua localização e vice-versa.

CÂMARA et al. (2000) apresenta a estrutura geral de um SIG através dos seguintes

componentes:

• Interface com o usuário;

• Entrada e integração de dados;

• Funções de processamento gráfico de imagem;

• Visualização e plotagem;

• Armazenamento e recuperação de dados.

Estes componentes se relacionam de hierarquicamente, estando no nível mais próximo ao

usuário, a interface e no mais interno do sistema, o sistema gerenciador de banco de dados

geográfico, conforme mostra o esquema da figura 4.1.

FIG. 4.1 - Componentes de um Sistema de Informação Geográfica

FONTE: adaptada de CÂMARA (1995)

4.2.4 MODELOS DE DADOS EM SIG

Os dados espaciais ou objetos espaciais são um dos fundamentos de um SIG. Compreendem

os elementos que podem ser georreferenciados. Elementos georreferenciados, ou referenciados

geograficamente, são aqueles que descrevem fenômenos geográficos cuja localização está

associada a uma posição sobre/sob a superfície terrestre, num determinado sistema de

coordenadas. Esses dados podem ou não ser observáveis no mundo real.

No primeiro caso têm-se como exemplos os rios, estradas, edifícios, já no segundo caso tem-

se os limites de um município ou reserva biológica, curvas de nível e áreas de influência dentre

outros. Os dados espaciais são divididos em duas categorias, cada uma com suas vantagens e

desvantagens, conforme a área onde são utilizados. O uso ou a escolha de uma delas determina o

modo como eles são obtidos, como são integrados dentro do SIG e como as análises sobre os

mesmos são efetuadas.

4.2.4.1 DADOS VETORIAIS

O uso de dados espaciais no formato vetorial parte do princípio que qualquer desses dados

pode ser representado por uma figura geométrica, que neste caso seria um ponto, uma linha ou

uma área (polígono) (CARVALHO et al., 2000). A partir do exemplo mostrado na figura 4.2,

observa-se que um ponto é representado por um par de coordenadas (latitude, longitude, por

exemplo), uma linha é a união de dois ou mais pontos através de segmentos de reta e uma área é

um conjunto de linhas conectadas de modo a delimitar uma região.

FIG. 4.2 - Exemplos de dados espaciais tipo vetor

Essa forma apresenta como vantagens um baixo volume de dados armazenados, melhor

precisão pela elevada resolução e mais facilidades no tratamento de análises da área de transporte

e logística. Além disso, cada tipo de figura permite associar a ela, atributos específicos. Por

exemplo, um ponto pode ser representado por uma estrela, um círculo, um quadrado, de um

tamanho N (independente da escala). Já uma linha pode ser tracejada, pontilhada, fina, grossa e

uma área pode ser preenchida com motivos ou cores diversas.

4.2.4.1 DADOS RASTER

O modelo raster, também conhecido como formato matricial, utiliza células de uma matriz

dividida regularmente. A localização de objetos geográficos é definida pela posição nas linhas e

colunas dessa matriz, segundo CARVALHO et al. (2000). Cada célula terá um valor

correspondente ao tema mais freqüente naquela localização espacial, registrando assim, a

condição ou atributo da superfície terrestre daquele ponto, explicam CÂMARA (1995).

Seu uso é mais comum nas áreas de estudos ambientais e agronegócios, onde muito

freqüentemente encontramos a necessidade de sobrepor mapas.

FIG. 4.3 - Modelo Raster (representação)

Na figura 4.3, um objeto quadrado e com duas cores, teria sua representação conforme a

matriz apresentada, onde cada célula representa uma parte do objeto e cada número uma cor

associada.

4.2.5 APLICAÇÕES DE SIG

Um SIG é muito mais do que um gerador de mapas. A forma como integra numa só

ferramenta dados espaciais e seus atributos permite análises que antes de sua existência eram

inviáveis devido a fatores como altos custos, grandes volumes de dados e tempo necessário para

elaboração de relatórios e mapas. Existem algumas funções que são comuns a todos os SIG's ou

senão a grande maioria deles (SÁRKÖZY, 1999):

• Localização: apontar um objeto espacial em particular, com seus atributos;

• Geração de mapas temáticos;

• Geração de mapas através da sobreposição de camadas ou mapas;

• Importação, exportação e conversão de dados espaciais nos mais diversos tipos de

coordenadas e formatos;

• Estatísticas espaciais tais como distâncias, áreas, perímetros;

• Rede: caminhos mínimos, roteirização, tempos de viagem;

• Simulação de cenários;

• Consulta: obter respostas à consulta tanto sobre os dados espaciais quanto seus atributos.

Várias áreas se utilizam dessas funções em seus estudos. A lista que se segue é apenas um

exemplo daquelas que mais se destacam, conforme LISBOA FILHO (1995):

• Infra-estrutura pública: redes de água, luz, esgoto, telefone, viária, ferroviária, rede

hospitalar, rede de ensino;

• Transportes e logística: roteirização de veículos, cartas náuticas e aéreas, monitoramento

de veículos, distribuição de produtos, transporte de matéria-prima, localização de

facilidades;

• Planejamento de serviços públicos: cadastramento territorial urbano e rural, serviços de

atendimentos emergenciais, facilidades turísticas (museus, bares, restaurantes, etc), limpeza

urbana, controle epidemiológico, mapeamento eleitoral;

• Agro-negócio: planejamento agropecuário, estocagem e escoamento da produção

agrícola, classificação de solos, gerenciamento de bacias hidrográficas, levantamento

topográfico e planimétrico, mapeamento do uso da terra;

• Gestão ambiental: controle de queimadas, estudos climáticos, controle de emissão de

poluentes, gerenciamento florestal, áreas de risco, reservas e parques, extrativismo vegetal e

mineral.

4.2.5 SIG PARA TRANSPORTES

Um Sistema de Informação Geográfica para Transportes (SIG-T) é aquele que se destina à

análise dos sistemas de transporte e logística. Das aplicações de um SIG, essa é a que apresenta

maior desenvolvimento. As análises realizadas pelo SIG-T envolvem uma rede de transporte em

uma determinada área. Porém, a transformação dessa rede real para sua representação

equivalente na forma de um grafo, não é tarefa fácil. A visão da rede pode variar com o tipo de

usuário (malha viária municipal, estadual ou federal), com a escala utilizada (só as principais

vias). A representação de intersecções, relações intermodais e movimentos ao longo do tempo

(rastreamento) também são fatores bastante complexos. As aplicações de um SIG-T podem ser

divididas por áreas, conforme descrito nos tópicos a seguir. Obtiveram-se os exemplos de cada

aplicação a partir de alguns dos trabalhos já desenvolvidos pelo próprio autor.

4.2.5.1 ANÁLISE DA REDE

Resolve problemas de redes de transporte tais como:

• Caminhos mínimos: caminhos mais curtos, rápidos ou de menor custo entre dois ou mais

pontos;

• Problema do caixeiro viajante: como visitar pontos de uma rede de modo mais eficiente;

• Particionamento: como dividir uma rede em sub-redes obedecendo a um determinado

critério.

FIG. 4.4 - Exemplo de um caminho

A figura 4.4 apresenta um o caminho mínimo entre dois pontos no mapa, representada pela

linha na cor azul. Em segundo plano se destaca uma malha viária e uma imagem de satélite da

região da cidade de Laranjal Paulista, no interior de São Paulo.

4.2.5.2 PLANEJAMENTO E MODELOS DE GERAÇÃO DE VIAGENS

Utilizado para prever as mudanças dos padrões de deslocamentos (viagens) e

conseqüentemente, da utilização do sistema de transportes, ocasionadas pela inclusão de novos

elementos (uma auto-estrada, por exemplo), mudanças nas atividades econômicas ou variação

populacional (TRANSCAD, 2008). Tem-se:

• Modelo de geração de viagens que são originadas ou atraídas para os pontos em análise;

• Modelo de equilíbrio de viagens: busca a igualdade entre oferta e demanda;

• Modelos de distribuição das viagens: utilizados para prever os padrões de fluxo entre os

pontos em análise;

• Modelos de divisão modal: para análise e previsão das escolhas de viagens considerando

diferentes modais de transporte;

• Modelos de atribuição de fluxo em rede: atribuem fluxo aos elementos da rede, segundo

determinados critérios, permitido análises como o de pontos de engarrafamento, por

exemplo.

FIG. 4.5 - Exemplo de fluxo sobre uma rede

A figura 4.5 mostra a variação da capacidade de fluxo (espessura das linhas) na Rodovia

Raposo Tavares e nos seus acessos no trecho entre Bauru e Presidente Epitácio no estado de São

Paulo.

4.2.5.3 LOGÍSTICA E ROTEIRIZAÇÃO DE VEÍCULOS

Nessa categoria, têm-se as seguintes divisões (TRANSCAD, 2008):

• Roteirização: roteiro de veículos, considerando vários centros de distribuição (depósitos),

vários pontos de entrega, restrições de tempo nos pontos de entrega, restrição de

capacidade dos veículos;

• Cobertura de arcos: consiste em passar por todos os arcos da rede. São exemplos a

roteirização da coleta de lixo, do carteiro;

• Fluxo em rede e análise da distribuição: como levar de maneira eficiente de pontos de

oferta para pontos de demanda. Aqui estão incluídos o clássico problema dos transportes,

o problema do fluxo com mínimo custo e o problema de matching;

• Localização de facilidades: determinar a melhor localização para uma facilidade (hospital,

fábrica, depósito), com base em critérios como tempo de acesso, custo de deslocamento,

área de cobertura.

FIG. 4.6 - Exemplo de roteirização para entregas

FIG. 4.7 - Exemplo de roteirização para coleta de resíduos sólidos

A figura 4.6 mostra um exemplo de roteiros de entregas de produtos aos clientes (nós)

representados por círculos na cor verde, a partir de dois depósitos representados por quadrados

vermelhos. A 4.7 mostra um exemplo de roteiros em ruas (arcos) para coleta de resíduos sólidos

urbanos, onde cada cor representa um percurso de um caminhão coletor.

4.3 SIG LIVRE

Existem vários softwares que auxiliam na realização das tarefas de SIG. Hoje em dia, os

softwares mais consagrados mundialmente, em empresas, em universidades e em órgãos

públicos, são patenteados e comercializados. Neste caso, os diversos pacotes de programas, em

arquivos binários, resultantes da compilação do código fonte, são comercializados para sistemas

operacionais específicos.

Porém, há também para este fim algumas alternativas interessantes em software livre, que

são desenvolvidas por diversos grupos em todo o mundo. Os softwares livres também são

expressivos na sua capacidade desenvolver tarefas de SIG. Segundo KINBERGER &

PUNCHER (2005), o uso de softwares livres na área de geoprocessamento está ganhando cada

vez mais espaço em empresas e na administração pública, pois são capazes de substituir, na

maioria dos casos, o uso de softwares comerciais.

Por software livre são compreendidos, neste trabalho, os softwares cujos códigos fonte são

distribuídos gratuitamente, normalmente licenciados pela GNU General Public License ou pela

LGPL (GNU Lesser General Public License).

O uso de softwares livres oferece a vantagem de não haver custos financeiros na compra do

software. Isto pode ser vantajoso em certas situações, por exemplo, quando um grande número

de cópias deve ser instalado, em várias estações de trabalho. Além disso, o software livre pode

oferecer a vantagem de suprir atualizações de software mais facilmente, perante a rápida

evolução do hardware. Porém, no que se refere à mão de obra para instalação, treinamento, e

manutenção, é atualmente mais difícil encontrar profissionais qualificados em softwares livres do

que em softwares patenteados.

No desenvolvimento de softwares específicos para SIG, sejam livres ou proprietários,

podem ser percebidas duas correntes claras, também relacionadas à licença para uso. Por um

lado, se coloca o desenvolvimento de sistemas completos e complexos, que são capazes de

realizar quase todas as funções envolvidas, oferecendo interfaces gráficas amigáveis para os

usuários. Esse é o caso dos softwares proprietários. No software livre, o desenvolvimento ocorre

de forma diferente. A iniciativa é normalmente financiada por fundos de pesquisa e

desenvolvimento, tanto em empresas como em universidades e órgãos públicos, em todo o

mundo. Além disso, há também os entusiastas programadores, que contribuem também de

maneira decisiva. O desenvolvimento fica assim mais pulverizado, sendo criados softwares

normalmente de menor porte, voltados para necessidades mais específicas. CÂMARA &

ONSRUD (2004) chegaram, em sua análise, a uma conclusão semelhante a esta.

A característica do desenvolvimento pulverizado não implica, porém, na incompatibilidade

entre as diversas ferramentas criadas. Uma prova disso é a existência do OpenGIS (OpenGIS

Consortium, Inc, 1999), que é um padrão para a linguagem SQL que define o suporte para o

armazenamento, consulta e atualização de dados georreferenciados via Open Data Base

Connectivity (ODBC).

Estes, entre outros fatos e discussões relacionados com o tema, tornam interessante a

identificação de um conjunto de softwares livres que, trabalhando de forma integrada, seja capaz

de armazenar dados georreferenciados e oferecer ferramentas para gerenciamento, consultas,

processamento e visualização de informações alfanuméricas e geométricas, constituindo um SIG.

Com este trabalho, é buscado satisfazer esta tarefa, onde possíveis soluções para estações de

trabalho (desktops) são analisadas.

Partindo do princípio que a falta de conhecimento em software livre seja pela falta de

documentação ou pela maior dificuldade associada é um fator que dificulta a decisão por esta

alternativa, os softwares escolhidos neste trabalho deverão ser de uso o mais amigável e intuitivo

possível. Isto implica em estarem disponíveis interfaces gráficas para a realização do maior

número de tarefas possível, evitando o uso de terminais de linha de comando. Além disso, o grau

de desenvolvimento do software e a consistência do sistema montado também são fatores

decisivos na escolha. Ao final do trabalho, deve estar caracterizado um SIG completo,

constituído exclusivamente de softwares livres.

4.3.1 SOFTWARES

O processo de busca de softwares pode ser feito com o auxílio de uma ferramenta de busca

na internet. Os grupos desenvolvedores de software livre mantêm normalmente páginas na

internet onde é possível obter o código fonte dos softwares, pacotes pré-compilados para

sistemas operacionais específicos, documentação, entre outros recursos. É grande a quantidade

de softwares que pode ser encontrada desta forma. O trabalho de eleição de um software, de

acordo com os critérios apresentados, implica na sua instalação e na realização de testes com

alguns dados.

Podem ser estabelecidos três grupos principais de softwares, que trabalhando de forma

conjunta são capazes de constituir um SIG completo. São eles os softwares específicos para

operações de SIG, os softwares para bancos de dados e os softwares de apoio.

Primeiramente, foram buscados softwares específicos para SIG, que englobam funções de

leitura e gravação de dados, ferramentas para consultas, visualização e processamento. Foram

escolhidos, dentre vários outros softwares analisados, o Quantum GIS (versão 0.8.0 Preview 1,

obtida em http://download.qgis.org), o GRASS (versão 6.0.1, obtida em

http://grass.itc.it/download/index.php) e o OpenJUMP (versão 1.2.0, obtida em

http://sourceforge.net/projects/jump-pilot).

O Quantum GIS é um SIG com interface gráfica amigável para o usuário, com

características que competem principalmente com o software comercial ArcView, da empresa

ESRI. É capaz de carregar, utilizando bibliotecas de apoio, uma grande variedade de dados, em

formato raster e vetorial, e tem grande capacidade de edição de propriedades visuais de camadas.

Possibilita a edição de informações alfanuméricas e geométricas de camadas vetoriais em

arquivos e diretamente no banco de dados. Oferece ainda uma ferramenta para a confecção de

mapas impressos (layouts).

O GRASS (Geographic Resources Analysis Support System) é um SIG completo,

englobando mais de 350 funções para análise geoespacial, modelagem ambiental, mapas

temáticos, integração de banco de dados, processamento de imagens e visualização. Possui

também interface gráfica bem desenvolvida para utilização, mas ela não é tão intuitiva como no

Quantum GIS. O GRASS é normalmente utilizado para executar operações de SIG mais

complexas. De acordo com KINBERGER & PUNCHER (2005), as possibilidades oferecidas

pelo GRASS são hoje até mesmo dificilmente alcançadas com o uso de softwares proprietários,

onde o suporte de GIS para dados raster e vetorial são combinadas com técnicas de visualização

e processamento de imagens.

O projeto OpenJUMP é um SIG com interface gráfica amigável para o usuário e também é

capaz de carregar uma grande variedade de dados, em formato raster e vetorial. É um SIG

totalmente desenvolvido em Java e possui alta modularidade, facilitando o desenvolvimento de

novos plug-ins. Também é possível encontrar diversos plug-ins já desenvolvidos que solucionam

problemas das diversas áreas de atuação de um SIG.

Quanto ao armazenamento dos dados geográficos em banco de dados livre, a alternativa

mais atraente e mais adotada (por exemplo em UCHOA & FERREIRA, 2004) é o PostgreSQL

(versão 8.1.3, obtida em www.postgresql.org), pela sua robustez, seu desempenho e por sua

compatibilidade com os softwares livres para SIG. Outra grande vantagem deste banco de dados

relacional é a existência do módulo espacial PostGIS (versão 1.4.4, obtida em

http://postgis.refractions.net), que possibilita o armazenamento de informações geométricas e a

realização de diversas consultas espaciais.

4.3.2 LIBERDADES DO SOFTWARE LIVRE

Apesar da “concepção” já existir a muito tempo, o conceito de software livre começou a ser

formalizado em 1983 com a criação do Projeto GNU por Richard M. Stallman. O objetivo deste

projeto era desenvolver uma versão do Unix com código-fonte aberto, acompanhada de

aplicativos e ferramentas compatíveis e igualmente livres. Visando garantir a liberdade dos

sistemas desenvolvidos neste projeto, o Richard Stallman estabeleceu as liberdades que um

software livre deveria possuir e criou dispositivos legais para garanti-las através da licença

GNU/GPL. As 4 liberdades do software livre são:

• Executar o programa, para qualquer propósito (liberdade nº 0);

• Estudar como o programa funciona e adaptá-lo para as suas necessidades (liberdade nº 1).

Acesso ao código fonte é um pré-requisito para esta liberdade;

• Redistribuir cópias de modo que você possa ajudar ao seu próximo (liberdade nº 2);

• Aperfeiçoar o programa e liberar os seus aperfeiçoamentos, de modo que toda a

comunidade se beneficie (liberdade nº 3). Acesso ao código-fonte é um pré-requisito para

esta liberdade.

4.4 CONSIDERAÇÕES FINAIS

O uso de um Sistema de Informação Geográfica é essencial para análise de dados

geográficos. Na solução de problemas de roteirização suas principais vantagens obtidas são: a

consideração das características reais de uma malha viária como a distância real entre os

depósitos e clientes e o sentido das vias. Estas características permitem a geração de rotas mais

precisas, essenciais ao planejamento da distribuição física.

O número de softwares livres que se dispõem a realizar tarefas de SIG é grande. Há muitas

possibilidades para a escolha, sendo que, cada uma possui vantagens específicas. Também há

vários graus diferentes de desenvolvimento entre elas.

Levando em consideração os requisitos estabelecidos para a escolha dos softwares para

constituir um SIG completo, que são a disponibilidade dos códigos fonte, o grau de

desenvolvimento, a estabilidade do sistema e a facilidade de uso, escolheu-se o OpenJUMP.

Além destas vantagens, o uso de software livre constitui uma grande contribuição ao

principalmente ao meio acadêmico para continuidade e melhoramento dos trabalhos

desenvolvidos.

5 PROCEDIMENTO PROPOSTO PARA ROTEIRIZAÇÃO DE VEÍCULOS COM

MÚLTIPLOS DEPÓSITOS

5.1 INTRODUÇÃO

Este capítulo tem como objetivo apresentar o procedimento proposto de roteirização de

veículos com múltiplos depósitos visando uma economia de distância percorrida e um melhor

atendimento ao cliente.

5.2 FORMULAÇÃO MATEMÁTICA PROPOSTA

O MDVRP é classificado como NP-Difícil, limitando com isso o uso de métodos exatos

para a solução do problema de maneira viável. Entretanto, mesmo com estas limitações, é

reconhecida a importância de desenvolver uma formulação matemática destes problemas, tanto

para avaliar os resultados de métodos aproximados em instâncias pequenas, como para se obter

limites inferiores de qualidade para o valor ótimo (valor ou função objetivo associado à solução

ótima). Desta forma, propõe-se nesta seção uma formulação matemática do MDVRP,

modelando-o como um problema de programação inteira com restrições lineares e não lineares.

Portanto, considere a seguinte notação:

Assim, temos as seguintes constantes e variáveis empregadas neste modelo:

{

}

( ) ( ) ( )

( ) ( )

{ }

2||||2

nós de próprio conjunto-sub

depósitos,,1

veículos,,1

nós depar cada para arcos todos

)1,(,,2,,1,

,2,,3,2,1,2

,1,,3,1,2,1

nós,,1

−≤≤∋

⊂





















−

nnnn

Parâmetros:

= tamanho máximo da rota para o veículo i

CAP

= capacidade máxima do veículo i

MAX

= número máximo de veículos disponíveis para o depósito j

dist

k,l

= distância do arco (k,l)

dem

= demanda do cliente localizado no nó k

Variáveis de Decisão













contrário caso0

l)(k, arco pelo passandoj depósito ao atribuido é i veículoo se1

contrário caso0

j depósito ao atribuido é i veículoo se1

ijkl

Função Objetivo:

∑

∈ ∈ ∈

Ii Jj Alk

ijklijkl

),(

min

Restrições:

Capacidade do Depósito:

JjMAXx

∈∀≤

∑

∈

Posição do Veículo

∑

∈

∈∀≤

Iix 1

Viagem ao longo dos arcos:

Deve usar um veículo encontrado

AlkJjIixx

ijijkl

∈

∀

≤

),(,,

Apenas um veículo chega num cliente

∑

∈ ∈ ∈

∈∀=

Ii Jj Alkk

ijkl

Vlx

),(:

Apenas um veículo sai de um cliente

∑

∈ ∈ ∈

∈∀=

Ii Jj Alkl

ijkl

Vkx

),(:

O veículo que chega deve ser igual ao veículo que sai

VlJjIixx

Aml

ijlm

Alk

ijkl

∈∈∈∀=−

∑

∈∈

,,0

),(),(

Limite da sub-rota

:),(

≥

∑

∈ ∈

∈∈

∈

Ii Jj

UVlUk

Alk

ijkl

Tamanho da rota

∑

∈ ∈

∈∀≤

Jj Alk

iiijklkl

IRLxdist

),(

Capacidade do Veículo

∑

∈ ∈

∈∀≤

Jj Alkk

iiijklk

ICAPxdem

),(:

5.3 ESCOLHA DO MÉTODO DO MDVRP PARA ADOTAR NO PROCEDIMENTO

O procedimento proposto para solução do MDVRP baseia-se no método de dois estágios

(item 3.2). Apesar deste método não fornecer uma solução ótima, ao não considerar os dois

estágios simultaneamente, optou-se pela sua vantagem no que se refere à capacidade de

solucionar problemas de grande porte.

Escolheu-se para o primeiro estágio, o algoritmo de Atribuição Paralela (item 3.3.2.1.1.1)

para a atribuição dos clientes aos depósitos. Optou-se por este algoritmo devido ao seu bom

desempenho computacional e à sua simplicidade de implementação.

Como pode ser observada na tabela 5.1, a atribuição paralela possui capacidade de resolver

problemas com 400 clientes e 30 depósitos com tempo de execução menor que 1 segundo.

Observa-se também que outros algoritmos possuem ganho médio no estágio de roteirização

comparado com a atribuição paralela, mas eles perdem no tempo de execução para problemas de

grande porte e na simplicidade de implementação.

TAB. 5.1 - Comparação entre os Algoritmos de Atribuição

Algoritmo de Atribuição

Ganho médio no

estágio de

roteirização (%)

comparado com *

Tempo de

execução com

400 clientes

30 depósitos

Tempo de

execução com

100 clientes

6 depósitos

Três Critérios de Clusterização 6,48 57 segundos < 1 segundo

Coeficiente de Propagação 4,74 3 segundos < 1 segundo

Problema de Transportes 2,55 < 1segundo < 1 segundo

Varredura 0,30 1 segundo < 1 segundo

Paralela * 0,00 < 1 segundo < 1 segundo

Simplificada -0,20 < 1 segundo < 1 segundo

Cíclica -29,80 < 1 segundo < 1 segundo

Adaptado de GIOSA (2002)

Para o segundo estágio, escolheu-se a heurística construtiva das economias de Clark and

Wright (item 3.3.2.2.2.1) para a roteirização e a programação dos veículos de cada conjunto de

clientes atribuídos ao seu depósito. Escolheu-se esta heurística, pois ela fornece bons resultados

em tempo computacional reduzido. Segundo BALLOU (1993), a utilização desse algoritmo pode

resultar em soluções próximas a 2% em relação à solução ótima. Este método também pode ser

considerado como o mais flexível dentre os existentes, pois permite incorporar diversos tipos de

restrições que se adaptem às características de uma empresa.

5.2 ESTRUTURA DO PROCEDIMENTO PROPOSTO

A metodologia divide a elaboração do problema em

cinco etapas básicas, logicamente

interligadas, com as atividades e dados necessários

para execução de cada uma delas. Estas

etapas correspondem ao

primeiro nível de informações. Cada uma destas etapas é detalhada

utilizando um segundo nível de aplicação, conforme a tabela 5.2.

TAB. 5.2 - Etapas da Metodologia

1º NÍVEL 2º NÍVEL

1ª ETAPA

Entrada de dados

Criação ou importação da malha viária

Cadastro dos clientes

Cadastro dos depósitos

Cadastro de informações veículos

2ª ETAPA

Criação da matriz de distâncias

Leitura da malha viária

Criação de um grafo misto, ponderado e conexo

com a malha viária

Criação da matriz de distâncias utilizando o

algoritmo de caminho mínimo de Dijkstra

3ª ETAPA

Atribuição dos clientes aos

depósitos

Verificação da capacidade dos depósitos e da

demanda dos clientes

Atribuição dos clientes aos depósitos utilizando o

algoritmo de atribuição com urgências paralela

4ª ETAPA

Roteirização e programação

Roteirização e programação dos veículos de cada

depósito utilizando o algoritmo de Clark and

Wright

Aplicação da pós-otimização utilizando o

algoritmo 2-OPT

5ª ETAPA

Emissão de relatórios

Geração das rotas graficamente no SIG

Geração dos itinerários para cada veículo

A primeira etapa trata a obtenção dos dados da malha viária, dos depósitos, dos clientes e

dos veículos. Estes dados podem ser informados a partir da criação ou importação de camadas

(layers) no SIG. A camada da malha viária é representada por linhas e as camadas de clientes e

depósitos por pontos. As informações dos veículos com a capacidade de carga, velocidade

média, custo médio por quilômetro percorrido, tempo de descarga médio e tempo máximo da

jornada de trabalho são informadas a partir da digitação manual.

A segunda etapa trata a geração da matriz de distâncias. Para isto, podem ser utilizadas a

distância euclidiana corrigida por um coeficiente de ajuste para vias ou a distância real obtida por

um caminho mínimo sob a malha viária. Para obtenção do caminho mínimo cria-se um grafo do

tipo misto, ponderado e conexo a partir da malha viária. A partir da localização dos depósitos e

dos clientes, cria-se uma matriz de distâncias mínimas para cada origem e destino utilizando o

algoritmo de caminho mínimo de DIJKSTRA (1959).

A terceira etapa trata a atribuição dos clientes aos depósitos. Verifica-se primeiro se a

capacidade dos depósitos é suficiente para atender a demanda dos clientes. Caso não seja

suficiente, faz-se necessária a alteração da capacidade de algum depósito ou a remoção de algum

cliente até que a capacidade seja maior ou igual à demanda. Logo após, atribui-se os clientes aos

depósitos utilizando o algoritmo de atribuição paralela.

A quarta etapa trata a roteirização e programação dos veículos. Para cada subproblema

gerado pelo algoritmo de atribuição, faz-se a roteirização e programação dos veículos de cada

depósito utilizando o algoritmo de Clark and Wright. Em seguida, na fase de pós-otimização,

aplica-se o algoritmo de melhora iterativa 2-OPT (item 3.3.2.2.2.2).

A quinta etapa trata a emissão de relatórios. Gera-se uma nova camada para visualização

gráfica no SIG de todas as rotas. Em cada rota são inseridas as informações sobre o itinerário do

veículo, a distância total percorrida, o tempo total, o custo total da rota e a demanda total

atendida pelo veículo.

6 PROTÓTIPO

6.1 INTRODUÇÃO

Neste capítulo serão apresentados os aspectos técnicos referentes ao desenvolvimento do

protótipo de software desenvolvido com base no procedimento proposto. Utilizou-se a linguagem

Java dentro do paradigma da Orientação a Objetos. O sistema foi concebido como um plugin do

Sistema de Informação Geográfica Livre OpenJUMP, apresentado no item 4.3.1. Para o

detalhamento da implementação e das rotinas do software são demonstrados os seus aspectos

principais através dos diagramas de classes, caso de uso e atividades.

6.2 FUNCIONAMENTO DO OPENJUMP

Existem 4 formas de estender a funcionalidade do JUMP. São elas: plugins, ferramentas de

cursor, renderes e dataSources. Os principais componentes da arquitetura JUMP são mostrados

na figura 6.1.

FIG. 6.1 - Esquema de funcionamento do OpenJUMP

Ao ser inicializado, o Workbench carrega extensions, que adicionam funcionalidade ao

Workbench. Esta funcionalidade adicional pode tomar forma de plugins (itens de menu),

ferramentas de cursor (botões da barra de ferramenta), renderes (forma de desenhar dados), e

dataSources (forma de carregar e salvar várias formas de formatos de dados). Para melhor

compreensão do funcionamento do JUMP, recomenda-se a leitura do Guia do Usuário e do Guia

do Desenvolvedor, disponíveis no site www.openjump.org.

6.2.3 TOPOLOGIA JUMP

O JUMP utiliza o JTS Topology Suit. É uma API Java que implementa uma série de

operações espaciais de dados usando modelos explícitos de precisão e algoritmos geométricos

robustos.

O JTS foi feito para ser utilizado no desenvolvimento de aplicações que suportam validação,

limpeza, integração e pesquisa de dados espaciais. O JTS busca implementar as especificações

SFS10 OpenGL de uma forma precisa. Em alguns casos o SFS omite a especificação; neste caso

o JTS escolhe uma alternativa razoável e consistente. Estas diferenças são evidenciadas na

documentação do JTS.

A utilização desta topologia é importante para a comunicação do JUMP com outros sistemas

de informações geográficas, conferindo portabilidade aos dados gerados, além da importação de

dados tratados nestes outros sistemas.

6.2.4 DESENVOLVIMENTO DE PLUGINS

A extensão das funcionalidades do OpenJUMP através da implementação na forma de

plugins não apresenta dificuldades. Esta pode ser feita de duas maneiras: inserir o código dentro

do próprio código do projeto do OpenJUMP ou exportar o projeto do plugin em arquivo com

formato jar.

A primeira maneira é recomendada apenas para a fase de desenvolvimento, pois facilita a

tarefa de testes. A página do OpenJUMP na internet demonstra como instalar um projeto do

Eclipse como plugin ao JUMP.

A segunda maneira é a indicada para os plugins já prontos e testados. O desenvolvedor

exporta o projeto do plugin desenvolvido em um arquivo do tipo jar e basta que o usuário o copie

para o diretório lib/ext dentro do diretório de instalação do OpenJUMP, para que o programa

reconheça e execute o arquivo na inicialização dos sistema.

6.3 LEVANTAMENTO DE REQUISITOS

A fase mais importante no desenvolvimento de qualquer software é determinar o que o

usuário deseja no programa.

Segundo PRESSMAN (1995) uma compreensão completa dos requisitos de um software é

fundamental para que o seu desenvolvimento seja bem-sucedido. Não adianta bem projetar ou

codificar um sistema se este foi, na origem, mal analisado e especificado. A tarefa de levantar o

que o software deverá realizar para funcionar corretamente é feita pelo levantamento dos

requisitos.

Para a roteirização de veículos de carga levantou-se os requisitos funcionais e não funcionais

a partir do estudo de sistemas semelhantes e da necessidade do cliente.

6.3.1 REQUISITOS FUNCIONAIS

LIMA (2005) afirma que os requisitos funcionais especificam ações que o sistema deve

executar independente de exigências físicas ou tecnológicas, ou seja, é o conjunto das

necessidades do cliente que devem ser satisfeitas para resolver um problema ou alcançar um

objetivo em seu negócio. A tabela 6.1 apresenta os requisitos funcionais atendidos pelo sistema.

TAB. 6.1 - Requisitos funcionais

RF1

O sistema deverá possibilitar a importação das informações dos clientes a serem

atendidos, dos depósitos da empresa e da malha viária da região utilizada a partir de

arquivos com o formato Shapefile ou por conexão em banco de dados geográfico.

RF2

Os usuários devem poder selecionar os atributos referentes à descrição, endereço e

demanda dos clientes.

RF3 Os usuários devem poder selecionar os atributos referentes à descrição, endereço e

capacidade dos depósitos.

RF4

Os usuários devem poder escolher entre o uso da distância euclidiana ou uma malha

viária.

RF5

O sistema deve possibilitar o uso de um fator de correção ao utilizar a distância

euclidiana.

RF6

O sistema deve possibilitar a escolha dos atributos referente ao nome e custo da malha

viária e se as vias possuem sentido ou não.

RF7

O usuário deve poder digitar as informações referentes ao veículo utilizado como a

capacidade de carga, o tempo médio de descarga, a velocidade média, a jornada máxima

de trabalho e o custo médio por quilômetro.

RF8

O sistema deve gerar as rotas graficamente e o itinerário para cada veículo com

informações sobre o custo total, tempo total de viagem, distância total e demanda total

atendida.

6.3.2 REQUISITOS NÃO FUNCIONAIS

Para LIMA (2005), requisitos não funcionais estão ligados, relacionados com as

características do sistema ou do ambiente em que ele está inserido. Estética, interface amigável,

segurança, desempenho e custos são alguns requisitos classificados como não funcionais. A

tabela 6.2 apresenta os requisitos não funcionais atendidos pelo sistema.

TAB. 6.2 - Requisitos não funcionais

RNF1

O sistema deve possuir portabilidade e funcionar em qualquer plataforma como

Windows e Linux.

RNF2

O sistema deve possuir internacionalização e alterar o idioma automaticamente de

acordo com o idioma utilizado pelo usuário.

RNF3

O sistema deve exibir as rotas com cores diferentes para cada veículo.

RNF4

O sistema deve exibir uma barra de progresso e o tempo de execução de cada etapa na

geração das rotas.

RNF5

O sistema deve ser codificado em idioma inglês (nome das classes, atributos e variáveis)

6.4 ESPECIFICAÇÃO

A especificação do software proposto se dará através dos seguintes diagramas da Unified

Modeling Language (UML), os quais foram desenvolvidos com auxílio da ferramenta CASE

Jude Community.

diagrama de casos de uso;

diagrama de classes;

diagrama de atividades.

6.4.1 DIAGRAMA DE CASOS DE USO

Segundo LIMA (2005), diagramas de caso de uso mostram conceitualmente o conjunto de

funções que o sistema deve executar para atender aos requisitos do cliente, servindo também,

como um contrato entre o cliente e o desenvolvedor. No caso de uso, o sistema é visto com a

perspectiva do usuário, apresentando suas principais funcionalidades e as possíveis ações a

serem tomadas.

As possíveis ações a serem tomadas pelo usuário na roteirização de veículos de carga podem

ser verificadas no diagrama de casos de uso conforme ilustra a figura 6.2. Observa-se que as

quatro ações de informar dados possuem dependência (include) à ação carrega camadas de

clientes e depósitos, assim como a ação gera rotas possui dependência às ações de informar

dados. Esta dependência existe para que a ferramenta de roteirização seja habilitada apenas

quando houver alguma camada carregada. A ação informa dados da malha viária possui uma

dependência não essencial (extend) à ação carrega camada da malha viária, por não ser

necessária mediante a escolha do uso da distância euclidiana.

FIG. 6.2 - Diagrama de caso de uso

6.4.2 DIAGRAMA DE ATIVIDADES

O objetivo do diagrama de atividades é mostrar o fluxo de atividades em um único processo

demonstrando como uma atividade depende uma da outra. Ele é dividido em regiões

denominadas raias (swimlanes) que representam os diversos papéis de pessoas ou grupos

envolvidos no processo. Os objetos situados sobre as fronteiras das raias representam objetos

partilhados entre os papéis. Em um processo de negócio, eles podem representar tanto objetos

físicos quanto informacionais. Um losango de decisão tem como saídas subfluxos alternativos.

Uma seta representa o fluxo da atividade. Uma seta pontilhada representa a relação de

dependência que uma atividade possui com relação à atividade apontada.

O diagrama de atividades do protótipo proposto, conforme ilustra a figura 6.3, divide-se em

três raias. A primeira representa o usuário, a segunda representa o OpenJUMP e a terceira

representa o Sistema de Roteirização de Veículos.

FIG. 6.3 - Diagrama de atividades

6.4.3 DIAGRAMA DE CLASSES

Para LIMA (2005), um diagrama de classes mostra a estrutura estática do modelo, em que os

elementos são representados por classes, com sua estrutura interna e seus relacionamentos.

Um diagrama de classes pode oferecer três perspectivas, cada uma para um tipo de usuário

diferente. São elas:

Conceitos ou Entidades:

Representa os conceitos do domínio em estudo. Perspectiva

destinada ao cliente;

Classes

: Tem foco nas principais interfaces da arquitetura, nos principais métodos, e não

como eles irão ser implementados. Perspectiva destinada as pessoas que não precisam

saber detalhes de desenvolvimento, tais como gerentes de projeto.

Classes de Software

: Aborda vários detalhes de implementação, tais como

navegabilidade e tipo dos atributos. Perspectiva destinada aos desenvolvedores.

Com intuito de apresentar um diagrama de classes simplificado do software proposto,

utilizou-se a perspectiva de conceitos ou entidades, conforme a figura 6.4. Os nomes das classes,

atributos e métodos estão em inglês (requisito RNF5).

FIG. 6.4 - Diagrama de classes simplificado

6.5 IMPLEMENTAÇÃO

Implementou-se o sistema seguindo as cinco etapas do procedimento proposto no item 5.2.

Para tanto, foram criadas diversas classes agrupadas em pacotes, conforme ilustra a figura 6.5.

FIG. 6.5 - Pacotes do protótipo

6.5.1 PACOTE PLUGIN

Agruparam-se neste pacote as classes responsáveis por: incluir a funcionalidade do plugin

no OpenJUMP, organizar a execução das fases do procedimento proposto e obter os dados com o

usuário.

6.5.1.1 CLASSE VEHICLEROUTINGPLUGINEXTENSION

A classe VehicleRoutingPlugInExtension é responsável pelo carregamento do plugin na

inicialização do OpenJUMP. O principal método é o configure, que é utilizado para inicializar o

plugin. Os métodos getName e getVersion retornam o nome e a versão do plugin. A figura 6.6

ilustra a classe VehicleRoutingPlugInExtension.

FIG. 6.6 - Classe VehicleRoutingPlugInExtension

6.5.1.2 CLASSE VEHICLEROUTINGPLUGIN

A classe VehicleRoutingPlugIn é a principal classe do plugin. Ela é responsável pela

organização da execução das etapas do procedimento proposto. O atributo name contém o nome

do plugin e o atributo process contém o processo criado para execução da geração das rotas. Os

métodos initialize, execute e getName foram sobrescritos da classe estendida AbstractPlugIn, do

OpenJUMP. Descrevem-se a seguir os principais métodos desta classe:

•

initialize: adiciona o item Roteirização no menu principal do OpenJUMP. Este item é

ativado se existir pelo menos uma camada carregada;

•

execute: exibe a janela principal do plugin para entrada de dados;

•

getName: retorna o nome do plugin;

•

readMDVRPData: faz a leitura dos dados informados na janela principal do plugin;

•

createGraph: cria um grafo para representação da malha viária;

•

createShortPathMatrix: cria uma matriz de distâncias com caminhos mínimos;

•

verifyCapacityAndDemand: verifica se a capacidade total dos depósitos atende a demanda

total dos clientes;

•

assignmentProblem: resolve o problema de atribuição dos clientes ao depósitos;

•

vehicleRoutingProblem: resolve o problema de roteirização dos veículos para cada

depósitos com seus clientes;

•

createGraphicRoutes: cria uma nova camada no OpenJUMP com informações da rota de

cada veículo para cada depósito;

•

I18N: método estático utilizado para internacionalização do plugin (requisito RNF2).

Apesar do OpenJUMP já possuir este método implementado, ele foi reimplementado para

possibilitar a internacionalização apenas do plugin desenvolvido.

A figura 6.7 ilustra a classe VehicleRoutingPlugIn.

FIG. 6.7 - Classe VehicleRoutingPlugIn

6.5.1.3 CLASSE VEHICLEROUTINGDIALOG

Esta classe é responsável pela entrada de dados informados pelo usuário. Seus atributos são

estáticos e são utilizados internamente para realizar o controle do tipo de atributo que pode ser

informado de cada camada selecionada. Os dados da malha viária, clientes e depósitos são

obtidos a partir das suas respectivas camadas que carregadas previamente no OpenJUMP. Ao

selecionar uma camada, são exibidos os seus atributos disponíveis para utilização (requisitos

RF2, RF3 e RF6). Os dados dos veículos e restrições das rotas são informados a partir da sua

digitação em caixas de texto (requisitos RF7). A maior parte de seus métodos é responsável pela

obtenção e atribuição dos dados utilizados pelo plugin, conforme ilustra a figura 6.8.

FIG. 6.8 - Classe VehicleRoutingDialog

6.5.1.4 CLASSE PROGRESSDIALOG

A classe ProgressDialog é responsável pela exibição do estado da execução da roteirização

(requisito RNF4). Seus principais métodos são: writeStatus adiciona uma mensagem numa caixa

de texto indicando a fase de execução (ex: atribuição, roteirização, etc) e os possíveis erros (ex:

capacidade dos depósitos insuficiente, etc); upProgressBar aumenta o estado da barra de

progresso; setMaximum atribui o número máximo de estados à barra de progresso, possibilitando

sua atribuição dinâmica a partir de um calculo preliminar que utiliza o número de clientes e

depósitos. A figura 6.9 ilustra a classe ProgressDialog.

FIG. 6.9 - Classe ProgressDialog

6.5.2 PACOTE MATRIX

Agruparam-se neste pacote as classes responsáveis pela criação da matriz de distâncias entre

todas as localidades (clientes e depósitos). Cada distância é representada por um caminho (Path)

que representa um caminho mínimo, obtido a partir de uma malha viária (grafo) ou um caminho

em linha reta, obtido a partir do cálculo da distância euclidiana corrigida com um fator de ajuste

para vias.

6.5.2.1 CLASSE MATRIX

A classe Matrix é responsável pela representação de uma estrutura de dados com formato

matricial onde cada elemento é do tipo Object. Possui os atributos: A contém os elementos da

matriz; lins e cols que contém respectivamente, o número de linhas e colunas da matriz. Seus

principais métodos são: Matriz(n, m), construtor de uma matriz com n linhas e m colunas; clone:

faz uma cópia idêntica da matriz; setElement(i, j) e getElement(i, j) atribui e obtém

respectivamente, o elemento localizado na linha i e coluna j da matriz. A figura 6.10 ilustra a

classe Matrix.

FIG. 6.10 - Classe Matrix

6.5.2.2 CLASSE PATH

A classe Path é responsável pela representação de um caminho. Ela possui os atributos: cost

contém o custo do caminho (ex: distância, tempo, etc); type assume os valores:

EUCLIDIAN_DISTANCE (caminho utilizando a distância euclidiana) ou ROADS_DISTANCE

(caminho mínimo utilizando uma malha viária) (requisito RF4). Seus principais métodos são:

Path(cost, type) construtor de um caminho com o custo e tipo informados; getCust e getType,

obtém, respectivamente, o custo e o tipo do caminho. A figura 6.11 ilustra a classe Path.

FIG. 6.11 - Classe Path

6.5.2.3 CLASSE SHORTESTPATHMATRIX

A classe ShortestPathMatrix é responsável pela representação de uma matriz de caminhos

assim como o cálculo para obtenção de cada caminho, seja utilizando o caminho mínimo de uma

malha viária ou utilizando a distância euclidiana corrigida por um fator de ajuste (requisito RF5).

O único atributo chamado graph contém um grafo quando é utilizada uma malha viária.

Descrevem-se a seguir os principais métodos desta classe:

•

ShortestPathMatrix(i, j): construtor de uma matriz de caminhos com n linhas e m colunas;

•

clone: faz uma cópia idêntica da matriz;

•

getCost: obtém o custo do caminho com origem i e destino j;

•

getPath: obtém o caminho com origem i e destino j;

•

calcShortestPathList: calcula o caminho mínimo a partir das coordenadas de origem e

destino utilizando o algoritmo de Dijkstra sobre o grafo;

•

shortPathToCost: obtém o custo do caminho mínimo calculado pelo método

calcShortestPathList;

•

calcEuclidianDistanceAjusted: calcula o custo do caminho em linha reta e multiplica por

um fator de ajuste (distância euclidiana ajustada);

A figura 6.12 ilustra a classe ShortestPathMatrix.

FIG. 6.12 - Classe ShortestPathMatrix

6.5.3 PACOTE MODEL

Agruparam-se neste pacote as classes responsáveis pelo modelo de dados utilizado para

representar os clientes, depósitos e rotas. Os clientes (Client) e depósitos (Depot) foram

considerados como um tipo de localidade (Locality), para que possam formar uma lista de

localidades as quais representarão as origens e destinos da matriz de distâncias.

6.5.3.1 CLASSE GEOGRAPHICPOSITION

A classe GeographicPosition é responsável pelo armazenamento de uma posição geográfica.

Seu único atributo chamado geometry é do tipo Geometry (JTS) e contém uma geometria. Seus

principais métodos são: GeographicPosition, construtor de uma posição geográfica; setGeometry

e getGeometry, atribui e obtém a geometria, respectivamente. A figura 6.13 ilustra a classe

GeographicPosition.

FIG. 6.13 - Classe GeographicPosition

6.5.3.2 CLASSE LOCALITY

A classe Locality é responsável pelo armazenamento da posição geográfica com um

identificador único. Possui os seguintes atributos: localID contém um identificador único;

address contém um endereço físico (ex: Avenida Presidente Vargas, 1030, Centro, Rio de

Janeiro, RJ); geographicPosition contém a posição geográfica real da localidade;

geographicPositionRoad contém a posição geográfica do início ou fim da rodovia mais próxima

de geographicPosition e que é calculada utilizando o algoritmo do vizinho mais próximo.

Possui um método construtor e métodos get e set para obtenção e atribuição de seus

atributos, conforme ilustra a figura 6.14.

FIG. 6.14 - Classe Locality

6.5.3.3 CLASSE CLIENT

A classe Client é responsável pelo armazenamento das informações do cliente a ser

atendido. Outras informações utilizadas no algoritmo de atribuição também foram inseridas nesta

classe. Possui os seguintes atributos: name contém o nome do cliente; demand contém a

demanda de produtos (kg) solicitada pelo cliente; locality contém a localidade do cliente;

depotAssigned e urgency contém respectivamente, o depósito que deverá atender o cliente e a

urgência, calculados pelo algoritmo de atribuição.

Possui dois métodos construtores, métodos get e set para obtenção e atribuição de seus

atributos e outros métodos auxiliares, conforme ilustra a figura 6.15.

FIG. 6.15 - Classe Client

6.5.3.4 CLASSE DEPOT

A classe Depot é responsável pelo armazenamento das informações do depósito a ser

utilizado para distribuição física de produtos. Outras informações utilizadas no algoritmo de

atribuição também foram inseridas nesta classe. Possui os seguintes atributos: name contém o

nome do depósito; capacity contém a capacidade física de armazenamento de produtos (kg) do

depósito; locality contém a localidade do depósito; current_capacity e client4Today contêm

100

respectivamente, a capacidade atual e uma lista dos clientes que deverão ser atendidos pelo

depósito, calculados pelo algoritmo de atribuição.

Possui dois métodos construtores, métodos get e set para obtenção e atribuição de seus

atributos e outros métodos auxiliares, conforme ilustra a figura 6.16.

FIG. 6.16 - Classe Depot

6.5.3.4 INTERFACE LOCAL

A interface Local representa um tipo genérico de localização que é implementado pelas

classes Client e Depot. Assim, torna-se possível a criação de uma lista de locais com clientes e

depósitos, pois estas classes são obrigadas a implementar os métodos existentes em Local. Seus

principais métodos são:

•

getLocalID: obtém o identificador único do local;

•

getLocalName: obtém o nome do local;

•

getCoordinate: obtém a coordenada (latitude e longitude) do local;

•

setCoordinateRoad e getCoordinateRoad: atribui e obtém a coordenada da rodovia mais

próxima da coordenada do local;

•

getLocality: obtém a localidade do local;

101

•

getDemandCapacity: obtém a demanda ou capacidade do local (demanda se for um cliente

e capacidade se for um depósito);

•

isDepot: obtém um valor booleano que define se o local é um depósito (1) ou cliente (0).

A figura 6.17 ilustra a interface Local.

FIG. 6.17 - Interface Local

6.5.3.5 CLASSE LOCALGROUP

A classe LocalGroup é responsável pelo armazenamento de uma lista locais. Seu único

atributo chamado listLocal contém uma lista de objetos do tipo Local. Seus principais métodos

são add e remove que, respectivamente, adiciona e remove um elemento da lista, conforme

ilustra a figura 6.18.

FIG. 6.18 - Classe LocalGroup

6.5.3.6 CLASSE ROUTE

A classe Route é responsável pelo armazenamento das informações da rota que um veículo

executa para distribuição física de produtos. Possui os seguintes atributos: visitedLocals contém

uma lista de locais visitados na melhor seqüência encontrada pelo algoritmo de roteirização;

102

totalDistance contém a distância total percorrida na rota (km); time contém o tempo total

necessário para percorrer a rota (horas); cost contém o custo total da rota (R$); demand contém a

demanda total atendida pelo veículo na rota (kg).

Para facilitar o calculo dos atributos pelo algoritmo de roteirização a cada inclusão de um

local visitado, todos os atributos desta classe são públicos, podendo ser alterados sem o

intermédio dos métodos get e set, conforme ilustra a figura 6.19.

FIG. 6.19 - Classe Route

6.5.3.7 CLASSE ROUTEGROUP

A classe RouteGroup é responsável pelo armazenamento de uma lista de rotas. Seu único

atributo chamado routes contém uma lista de objetos do tipo Route. Seus principais métodos são:

add, adiciona uma rota na lista; remove, remove uma rota da lista; getRoutes, obtém a lista de

rotas. A figura 6.20 ilustra a classe RouteGroup.

FIG. 6.20 - Classe Route

6.5.4 PACOTE ALGO

Agruparam-se neste pacote as classes responsáveis pelos algoritmos de resolução do

problema de atribuição e do problema de roteirização de veículos. Para isto, criaram-se: uma

classe para armazenamento das informações utilizadas (clientes, depósitos, matriz de distâncias,

103

etc); duas classes abstratas representando um tipo genérico do problema de atribuição e do

problema de roteirização e outras duas classes estendidas implementando-as, uma interface

representando um tipo genérico do problema de roteirização de veículos com múltiplos depósitos

e outra classe implementando-a.

6.5.4.1 CLASSE MDVRPDATA

A classe MDVRPData é responsável pelo armazenamento das informações utilizadas pelo

algoritmo de roteirização de veículos com múltiplos depósitos. Possui os seguintes atributos:

•

clientList contém uma lista de objetos do tipo Client;

•

depotList contém uma lista de objetos do tipo Depot;

•

localList contém uma lista de objetos do tipo Local;

•

speed contém a velocidade média dos veículos;

•

costPerKm contém o custo médio por quilômetro percorrido pelo veículo;

•

downloadTime contém o tempo de descarga médio do veículo ao entregar a carga para o

cliente (horas);

•

vehicleCapacity contém a capacidade dos veículos utilizados (kg);

•

maximumWorkTime contém o tempo máximo da jornada de trabalho de cada veículo

(horas);

•

coefficientAdjust contém o coeficiente de ajuste para rodovias utilizado no cálculo da

distância euclidiana ajustada (ex: 1: sem ajuste; 1,2: adiciona 20% na distância);

•

isUseRoadsLayer contém um valor booleano que define se é utilizada uma camada com a

malha viária (1) ou não seja utilizada (0);

•

shortestPathMatrix contém a matriz de distâncias;

•

roadsLayer contém a camada do que representa a malha viária;

•

graph contém um grafo quando é utilizada uma malha viária;

•

vehicleRoutingPlugIn, context, localIDSequence e factory são atributos para controle

interno.

Possui um método construtor, métodos get e set para obtenção e atribuição de seus atributos

e outros métodos auxiliares, conforme ilustra a figura 6.21.

104

FIG. 6.21 - Classe MDVRPData

6.5.4.2 CLASSE VRPSOLVER

A classe VRPSolver é responsável pela representação de um tipo genérico solucionador do

problema de roteirização de veículos. Possui os seguintes atributos: cliente4Today contém uma

lista dos clientes que deverão ser atendidos pelo depósito; bestSolution contém a melhor solução

obtida na roteirização; depot contém o depósito do problema de roteirização de veículos; speed,

costPerKm, downloadTime, vehicleCapacity, maximumWorkTime e shortestPathMatrix contém

105

os valores dos atributos correspondentes na classe MDVRPData. Seu único método chamado

searchRoutes é abstrato, ou seja, não possui implementação e deve ser implementado pelas

classes que estenderem esta classe. A figura 6.22 ilustra a classe VRPSolver.

FIG. 6.22 - Classe VRPSolver

6.5.4.3 CLASSE CWLS

A classe CWLS é responsável pela solução do problema de roteirização de veículos pelo

algoritmo de Clark and Wrigth (método das economias). Ela estende a classe VRPSolver e

implementa a solução no método searchRoutes. Utiliza-se dos atributos herdados e possui outros

atributos para solução interna: posicionList, clientList e numero_rotas. Seus métodos são:

•

CWLS, construtor do algoritmo de Clark and Wrigth;

•

searchRoutes, obtém as rotas de cada veículo;

•

maximo, calcula o custo máximo de s(i,j);

•

combinacao_possivel, obtém um valor booleano que define se o a união de duas rotas

pode ser realizada (1) ou se não pode ser realizada (0);

•

combina, combina duas rotas;

•

elimina, elimina a rota após ter sido combinada com outra rota;

•

melhora_rotas, melhora a solução obtida para cada rota separadamente;

•

intercambio_rota, realiza a troca de arcos entre clientes (2-OPT);

•

converter_rotas, converte a solução interna em rotas que são armazenadas num objeto do

tipo RouteGroup;

•

distancia_trajeto, calcula a distância do trajeto;

•

custo_rota, calcula o custo da rota;

106

•

posicoes_rota, obtém as posições das localidades na rota;

•

custo_trajeto, calcula o custo do trajeto;

•

tempo_trajeto, calcula o tempo do trajeto.

A figura 6.23 ilustra a classe CWLS.

FIG. 6.23 - Classe CWLS

6.5.4.4 CLASSE ASSIGNMENTSOLVER

A classe AssignmentSolver é responsável pela representação de um tipo genérico

solucionador do problema de atribuição. Possui os seguintes atributos: cliente4Today contém

uma lista dos clientes que deverão ser atendidos; depot4Today contém uma lista dos depósitos

que deverão ser utilizados para atender os clientes; shortestPathMatrix contém o valor do

atributo correspondente na classe MDVRPData. Seu único método chamado searchAssignments

é abstrato, ou seja, não possui implementação e deve ser implementado pelas classes que

estenderem esta classe. A figura 6.24 ilustra a classe AssignmentSolver.

FIG. 6.24 - Classe AssignmentSolver

107

6.5.4.5 CLASSE PARALLELASSIGNMENT

A classe ParallelAssignment é responsável pela solução do problema de atribuição pelo

algoritmo de atribuição com urgências paralela. Ela estende a classe AssignmentSolver e

implementa a solução no método searchAssignments. Sua solução é inserida nos próprios objetos

que representam os clientes e depósitos. Em cada depósito é armazenada uma lista com seus

clientes a serem atendidos e em cada cliente é armazenado o depósito que irá atendê-lo. Utiliza-

se dos atributos herdados e possui os atributos estáticos BIG_NUMBER e SMALL_NUMBER

para representação de um número grande e outro pequeno. Seus principais métodos são:

•

ParallelAssignment, construtor do algoritmo de atribuição paralela com urgências;

•

searchAssignments, obtém as atribuições dos clientes aos depósitos;

•

getCust4Depot, obtém o custo de atribuir um cliente a um depósito;

•

getClientWithMaxUrgency, obtém o cliente não atribuído que possui a maior urgência;

•

getClosestDepot4Client, obtém o depósito mais próximo ao cliente;

•

getClosestAndFeasibleDepot4Client, obtém o depósito mais próximo e que possua

capacidade atual suficiente para atender o cliente;

•

getParallelUrgency, calcula a urgência para cada cliente.

A figura 6.25 ilustra a classe ParallelAssignment.

FIG. 6.25 - Classe ParallelAssignment

108

6.5.4.6 INTERFACE MDVRPSOLVER

A interface MDVRPSolver representa um tipo genérico de solução do problema de

roteirização de veículos com múltiplos depósitos. Seus principais métodos são:

searchAssignments, obtém a solução da atribuição dos clientes aos depósitos; searchRoutes,

obtém a solução da roteirização dos veículos para cada deposito; getSolution, obtém uma lista de

solucionadores do problema de roteirização (VRPSolver), pois cada um armazena a melhor

solução do problema de roteirização encontrada para cada depósito. A figura 6.26 ilustra a

interface MDVRPSolver.

FIG. 6.26 - Interface MDVRPSolver

6.5.4.7 CLASSE PARALLELASSIGNMENTANDCWLS

A classe ParallelAssignmentAndCWLS é responsável pela solução do problema de

roteirização de veículos com múltiplos depósitos utilizando o algoritmo de atribuição com

urgências paralela e o algoritmo de roteirização de Clark and Wrigth. Ela implementa a interface

MDVRPSolver.

Possui os seguintes atributos: client4Today e depot4Today contém os valores dos atributos

correspondentes na classe MDVRPData, input contém o valor da própria MDVRPData;

parallelAssignment contém o solucionador do problema de atribuição com urgências paralela;

bestSolution contém uma lista de solucionadores do problema de roteirização (VRPSolver).

Seus métodos são: ParallelAssignmentAndCWLS, construtor do problema;

searchAssignments, obtém a solução para o problema de atribuição; searchRoutes, obtém a

solução para o problema de roteirização dos veículos de cada depósito; getSolution, obtém a

solução do problema.

A figura 6.27 ilustra a interface ParallelAssignmentAndCWLS.

109

FIG. 6.27 - Classe ParallelAssignmentAndCWLS

110

7 ESTUDO DE CASO

7.1 INTRODUÇÃO

Este capítulo tem como objetivo realizar um estudo de caso para ilustrar a aplicação do

procedimento proposto e validar o protótipo de software desenvolvido. Para tanto, procurou-se

uma empresa que necessitasse de uma ferramenta de apoio à decisão ao problema de roteirização

de veículos com múltiplos depósitos.

A partir de um trabalho de tarifação de fretes desenvolvido pelo autor para uma empresa do

setor alimentício, constatou-se esta necessidade da empresa a qual forneceu e autorizou o uso das

informações necessárias para realização deste estudo de caso.

7.2 A EMPRESA

Realizou-se o presente estudo de caso com uma conceituada empresa italiana de produtos

alimentícios, a Parmalat. Fundada em 1961 em Collecchio, a poucos quilômetros de Parma, por

Calisto Tanzi, a Parmalat foi pioneira no enchimento asséptico em embalagens da Tetra Pak

conhecendo uma rápida ascensão.

FIG. 7.1 - Presença da Parmalat no mundo

111

A figura 7.1 ilustra a presença da Parmalat no mundo: em azul os países com presença direta

(17 países) e em verde os países com presença com licença (9 países).

A subsidiária no Brasil, a Parmalat Brasil, assim como a Parmalat no mundo, entrou em fase

de falência. A subsidiária brasileira entrou na antiga lei de falências, mas com a aprovação da

nova lei, ela entrou em recuperação judicial e substituiu a antiga lei, onde seu plano foi aprovado

dando fôlego a empresa em continuar sua operações como a Varig e a Vasp.

A Parmalat teve, em 2007, dois lotes de leite apreendidos pela ANVISA, porque estavam

com suspeita de adulteração com soda cáustica e peróxido de hidrogênio, H2O2. Após os testes

necessários, foi constatado que a marca não possuía nenhum lote envolvido no escândalo do

leite. Escândalo que desvendou a adulteração em duas cooperativas de Minas Gerais que

vendiam leite não só para a Parmalat e também para outras grandes marcas.

7.3 DESCRIÇÃO DO CASO

Ao adquirir novas unidades fabris a Parmalat teve um acréscimo em sua capacidade

produtiva, porém segundo relatos internos, não houve o aumento da demanda proporcional à

nova capacidade instalada.

Um dos pontos hipotéticos que fragiliza o aumento das vendas, gerando diferença entre

oferta e demanda é a restrição na distribuição existente no modelo atual, tendo como principal

cliente os grandes varejistas. Os grandes varejistas consomem, de acordo com entrevista

realizada na Parmalat, 70% da produção das plantas.

O ponto positivo é a redução no custo logístico, devido à baixa capilaridade de entrega

realizada pela sua frota própria através de carretas fechadas (cada veículo transporta toda a sua

carga para um único destino). Porém, o problema é o grande grau de dependência gerado por este

modelo.

Em busca de minimizar a capacidade ociosa gerada pela compra de novas plantas, a

Parmalat tem analisado a modificação de seu modelo a partir diversificação de sua matriz de

venda simulando clientes de diversos portes. Este procedimento poderá dar maior capilaridade na

abrangência do atendimento da Parmalat, potencializando a produção atualmente acima da

demanda e minimizando o grau de dependência junto aos grandes varejistas. O aumento da

abrangência visará aumentar o número de fornecedores em diversas bacias leiteiras no Brasil,

112

minimizando o risco e dependência causada pela excessiva concentração de fornecedores e de

clientes de grande porte.

Visando esta futura modificação na matriz de vendas, a Parmalat passou a se preocupar com

a sua logística, buscando por ferramentas que forneçam apoio à decisão à roteirização de

veículos e que atendam suas características físicas e operacionais, como por exemplo:

•

Múltiplos depósitos: possui 13 fábricas, 12 centros de distribuição próprios e 1 cross

docking (centro de distribuição sem armazenagem), totalizando 26 depósitos de acordo

com a denominação utilizada neste trabalho;

•

Frota homogênea e com restrição de capacidade: sua frota própria é constituída por

veículos de grande porte (carretas com capacidade de 26 mil quilos cada);

•

Grande quantidade de clientes: são 400 os clientes a serem atendidos;

•

Depósitos e clientes georreferenciados e uso da malha viária: deve ser utilizado um

Sistema de Informação Geográfica.

A partir destas características, identificou-se que o problema pode ser solucionado pelo

protótipo desenvolvido no capítulo anterior. Utilizando-se de um trabalho de tarifação de fretes

desenvolvido pelo autor para Parmalat, foram extraídas as informações necessárias para

execução do protótipo. Estas informações são: região da malha viária, clientes, depósitos,

veículos e tipo do produto transportado.

7.3.1 INFORMAÇÕES DA MALHA VIÁRIA

A área de estudo foi o território brasileiro. A base geográfica da malha viária foi obtida junto

ao Instituto Militar de Engenharia, esta, porém encontra-se em fase final de atualização e existem

trechos não conectados. Ela é constituída por rodovias federais, estaduais e municipais,

totalizando 6.756 trechos. A figura 7.2 ilustra a malha viária utilizada.

113

FIG. 7.2 - Malha viária brasileira

Cada trecho é representado por uma linha e possui algumas informações da via como, por

exemplo: nome, tipo, tamanho, sentido, nível de serviço, aspecto físico e volume médio diário

anual (VMDA) por tipo de veículo. Neste estudo de caso utilizou-se o tamanho da via como

custo a ser reduzido, mas ressalta-se que o sistema desenvolvido permite a utilização de qualquer

atributo da camada de vias.

Uma opção interessante é a combinação da distância com outras informações sobre a via,

como por exemplo, o tempo de percurso, o nível de serviço (A, B, C, D ou E), o tipo do

pavimento (asfalto ou terra), o aspecto físico (bom, regular ou mau) e o nível de risco de

acidentes e roubos de carga. Esta combinação é calculada a partir da geração de um novo campo

calculado com base nas informações, que será posteriormente utilizado como atributo de custo a

ser reduzido.

7.3.2 INFORMAÇÕES DOS CLIENTES

A base de clientes foi obtida com a Parmalat, a qual possui 400 clientes. As informações

contidas nesta base são: descrição, endereço e demanda. Os atributos descrição e endereço

114

contêm, respectivamente, o nome e o endereço do cliente, mas por questões éticas, não serão

mostrados, os quais serão substituídos pelo nome da cidade onde estão localizados. O campo

demanda contém o peso total (kg) dos produtos solicitados pelo cliente.

A partir do atributo endereço, georreferenciou-se cada cliente em sua localização real.

Assim, cada cliente é representado por um ponto, assim como ilustra a figura 7.3.

FIG. 7.3 - Clientes da Parmalat

7.3.3 INFORMAÇÕES DOS DEPÓSITOS

A base de depósitos foi obtida com a Parmalat, a qual possui 26 depósitos. As informações

contidas nesta base são: descrição, endereço e capacidade. Os atributos descrição, endereço e

capacidade contêm, respectivamente, o nome, o endereço do depósito e o peso total (kg) dos

produtos que cada depósito possui armazenado.

A partir do atributo endereço, georreferenciou-se cada depósito em sua localização real.

Assim, cada depósito é representado por um ponto, assim como ilustra a figura 7.4.

115

FIG. 7.4 - Depósitos da Parmalat

7.3.4 INFORMAÇÕES DOS VEÍCULOS

Conforme a descrição deste estudo, a Parmalat possui uma frota própria homogênea, ou seja,

todos os veículos possuem a mesma capacidade de carga. Descrevem-se as informações dos

veículos a seguir:

•

Capacidade (kg): 26.000, capacidade de um veículo (carreta);

•

Velocidade média (km/h): 80, velocidade média dos veículos em viagens intermunicipais;

•

Custo por km (R$): 3, custo por quilômetro percorrido, incluindo combustível, pedágios,

manutenção e outras despesas adicionais;

•

Tempo de descarga (h): 0.5, tempo médio de descarga necessário para descarregar o

veículo, conferir a carga entregue e obter a assinatura do cliente confirmando o

recebimento dos produtos;

•

Jornada máxima de trabalho (h): 9999, tempo máximo que um veículo pode trabalhar

durante um dia de trabalho. Neste estudo foi assumido um valor alto (9999), pois esta

116

restrição não é utilizada em viagens intermunicipais, as quais demandam às vezes vários

dias para realizar uma entrega.

7.3.5 INFORMAÇÕES DOS PRODUTOS

O principal produto transportado pela frota própria da Parmalat é o leite em caixa,

considerado como o principal elemento de vendas. Este produto também possui alto potencial em

termos de otimização do transporte, pois sua característica física permite que a carga seja

organizada no veículo sem espaços vazios. Realizando uma comparação aproximada, constata-se

que a 1 kg de produto solicitado pelo cliente é equivalente a 1 litro de leite a ser transportado.

Sendo assim, um veículo transporta 26 mil litros de leite.

7.4 GERAÇÃO DAS ROTAS

Conforme o diagrama de caso de uso ilustrado pela figura 6.2 no capítulo anterior, o usuário

deve executar uma seqüência de ações para informar os dados necessários para geração das rotas.

Estas ações são detalhadas a seguir.

7.4.1 CARREGA CAMADA DA MALHA VIÁRIA

Para carregar uma camada no OpenJUMP existem duas opções. Na primeira, o usuário clica

com o botão direito sob a categoria desejada e depois em carregar dados geográficos. Exibe-se

uma tela para escolha do arquivo a ser carregado, o qual pode possuir os formatos aceitos pelo

OpenJUMP, como por exemplo, JUMP GML, GML 2.0, FME GML, WKT e ESRI Shape File.

Na segunda opção adiciona-se uma camada a partir de uma tabela de um banco de dados

geográfico, como por exemplo, o Postgres com a extensão para dados geográficos chamada

PostGIS.

Devido à malha viária obtida junto ao Instituto Militar de Engenharia estar no formato ESRI

Shape File, carregou-se esta camada utilizando a primeira opção.

117

7.4.2 CARREGA CAMADAS DE CLIENTES E DEPÓSITOS

As camadas de clientes e depósitos foram criadas com os dados informados pela Parmalat

em arquivo com o formato ESRI Shape File, visando a padronização dos dados utilizados.

Carregaram-se estas camadas utilizando a primeira opção, conforme o item anterior. Para

auxiliar a visualização do território brasileiro, carregou-se também uma camada representando o

contorno do país, conforme ilustra a figura 7.5.

FIG. 7.5 - Tela do OpenJUMP com camadas carregadas

7.4.3 INFORMA DADOS DA MALHA VIÁRIA

Para informar os dados da malha viária, o usuário deve informar inicialmente se será

utilizada a distância euclidiana ou uma camada de linhas representando a malha viária. Ao

escolher a distância euclidiana o usuário deve informar o valor do coeficiente de ajuste para

118

correção da distância, a qual forneceu uma representação aproximada da distância real.

Escolhendo uma camada de linhas, o usuário deve selecionar a camada carregada que representa

a malha viária, informar se deve ser utilizada a direção das vias e escolher os atributos da camada

de linhas que contém o custo e o nome da via, conforme ilustra a figura 7.6.

FIG. 7.6 - Tela para informar os dados da malha viária

7.4.4 INFORMA DADOS DOS CLIENTES

Para informar os dados dos clientes, o usuário deve escolher a camada de pontos carregada

que representa os clientes a serem atendidos e os atributos que contém a descrição, o endereço e

a demanda solicitada, conforme ilustra a figura 7.7.

119

FIG. 7.7 - Tela para informar os dados dos clientes

7.4.5 INFORMA DADOS DOS DEPÓSITOS

FIG. 7.8 - Tela para informar os dados dos depósitos

120

Conforme ilustra a figura 7.8, para informar os dados dos depósitos, o usuário também deve

escolher a camada de pontos carregada que representa os depósitos que atenderão os clientes e os

atributos que contém a descrição, o endereço e a capacidade de armazenagem.

7.4.6 INFORMA DADOS DOS VEÍCULOS

Para informar os dados dos clientes, o usuário deve informar os valores solicitados para

capacidade dos veículos, velocidade média, custo por quilômetro percorrido, tempo de descarga

e jornada máxima de trabalho, conforme ilustra a figura 7.9.

FIG. 7.9 - Tela para informar os dados dos veículos

7.4.7 GERA ROTAS

Para obter as rotas de cada veículo o cliente deve clicar no botão gerar rotas. Para indicar o

estado da execução é exibida uma tela com uma barra de progresso e com as etapas realizadas. A

121

qualquer momento o usuário poderá cancelar a execução clicando no botão cancelar, conforme

ilustra a figura 7.10.

FIG. 7.10 - Tela com o estado da execução da geração das rotas

Ao término da execução, será mostrado o custo total da solução encontrada, ou seja, a soma

do custo de todas as rotas encontradas (FIG. 7.10).

FIG. 7.11 - Atributos da camada de rotas

Conforme ilustra a figura 7.11, também é criada uma nova camada no OpenJUMP

representando as rotas de cada veículo que contém as seguintes informações:

•

Rota: nome único dado a cada rota (ex: “Rota 1”, “Rota 2”, e assim sucessivamente);

•

Depósito: depósito que enviou o veículo com seus produtos;

122

•

Veículo: nome único dado a cada veículo por depósito (ex: “Veículo 1”, “Veículo 2”, e

assim sucessivamente);

•

Distância: distância total percorrida em quilômetros;

•

Tempo: tempo total necessário em minutos;

•

Demanda: demanda total atendida pelo veículo;

•

Custo: custo total em reais;

•

Caminho: a rota propriamente dita, representada por uma seqüência de locais que o

veículo deve percorrer. Cada rota inicia e termina no seu depósito de origem.

Para facilitar a visualização das rotas individualmente, criaram-se graficamente no

OpenJUMP com diferentes cores, conforme ilustra a figura 7.12 a qual possui duas rotas.

FIG. 7.12 - Detalhamento de duas rotas

Para efeitos de comparação as rotas foram geradas utilizando a distância euclidiana corrigida

por um coeficiente de ajuste para rodovias de 1,2 e utilizando a malha viária, conforme ilustra a

figura 7.13.

123

FIG. 7.13 - Rotas utilizando a distância euclidiana

Observa-se na figura 7.13 que nem todos os caminhos utilizam a malha viária. Isto ocorre,

pois a malha viária utilizada não é conexa, ou seja, existem alguns trechos de rodovia que não

estão interligados aos outros, impossibilitando assim a obtenção de um caminho de qualquer

origem para qualquer destino. Sendo assim, o protótipo utilizou a distância euclidiana ajustada

nestes caminhos.

A tabela 7.1 apresenta as informações das rotas agrupadas por depósito utilizando a distância

euclidiana e a malha viária. Observa-se que existe certa diferença entre os valores obtidos com as

rotas utilizando a distância euclidiana ajustada e utilizando a malha viária. Isto comprova a

utilidade do uso da malha viária, que permite a obtenção de valores mais próximos à realidade

como, por exemplo: o número de veículos necessários, a distância total percorrida, o tempo

necessário para entrega e custo total.

124

TAB. 7.1 - Comparação das rotas utilizando a distância euclidiana ajustada e a malha viária

Distância Euclidiana Ajustada Malha Viária Depósito

Veículos

(unidade)

Distância

(km)

Tempo

(h)

Custo

(R$)

Veículos

(unidade)

Distância

(km)

Tempo

(h)

Custo

(R$)

Bebidas Jundiaí

4.678,55

64,48

14.035,66

4.819,94

69,25

14.459,84

Biscoitos Jundiaí

2.340,04

30,75

7.020,14

3.005,87

45,07

9.017,62

Malibu

3.854,28

55,68

11.562,85

4.114,80

57,43

12.344,41

Itaperuna

10.848,51

139,10

32.545,55

13.968,91

179,11

41.906,74

Barra Mansa

6.662,21

92,78

19.986,66

7.480,15

102,01

22.440,43

Frutal

7.980,23

105,25

23.940,69

9.392,33

127,90

28.177,00

Sonata

3.375,05

48,19

10.125,16

3.481,66

49,52

10.444,98

Carazinho

15.414,47

223,18

46.243,42

14.302,98

206,30

42.908,94

Santa Helena

20.178,54

268,23

60.535,60

18.315,07

241,94

54.945,21

Ouro Preto

37.003,98

487,54

111.011,96

38.036,03

498,94

114.108,07

Garanhuns

7.313,04

104,92

21.939,11

8.153,83

115,41

24.461,48

Feira de Santana

4.064,97

52,31

12.194,92

4.355,14

55,94

13.065,40

Centro de Distribuição Jundiaí

2.559,92

41,50

7.679,73

2.084,05

27,55

6.252,13

Centro de Distrib. Duque de Caxias

2.499,30

33,74

7.497,92

2.515,30

33,44

7.545,89

Centro de Distribuição Rio Bonito

3.860,62

52,26

11.581,86

4.336,46

62,20

13.009,37

Cross Docking Brasília

9.811,73

130,15

29.435,19

6.915,89

93,45

20.747,67

Centro de Distribuição Simões Filho

5.243,05

70,04

15.729,16

4.478,79

60,98

13.436,37

Centro de Distribuição Viana

5.110,56

70,89

15.331,67

7.655,76

100,70

22.967,28

Centro de Distribuição Contagem

2.551,54

39,40

7.654,62

5.292,93

74,16

15.878,78

Centro de Distribuição São José

3.946,90

60,84

11.840,71

4.024,59

61,80

12.073,77

Centro de Distribuição Pinhais

5.084,95

71,57

15.254,85

4.357,00

63,46

13.071,01

Centro de Distribuição Londrina

5.080,02

74,50

15.240,04

6.118,15

87,48

18.354,44

Centro de Distribuição Porto Alegre

3.405,93

46,08

10.217,78

3.366,26

45,58

10.098,75

TOTAL

100

172.868,39

2.363,38 518.605,25

101

180.571,89

2.459,62 541.715,58

125

7.5 COMPARAÇÃO COM O TRANSCAD

Visando a validação dos resultados obtidos com o auxílio do protótipo desenvolvido,

realizou-se o mesmo procedimento utilizando o software TransCAD. Conforme ilustra a figura

7.14, utilizou-se as mesmas informações fornecidas pela empresa.

FIG. 7.14 - Tela do TransCAD com camadas carregadas

Segundo CALIPER (2000), o TransCAD é a única ferramenta computacional que se

classifica como uma ferramenta SIG e que contém ferramentas de planejamento, modelagem de

transportes e aplicações de logística. Nele, soluciona-se o problema de roteirização de veículos

com múltiplos depósitos em duas fases:

Atribuição dos clientes aos depósitos: utiliza o Problema de Transportes;

Roteirização de veículos: utiliza o algoritmo de Clark and Wright.

126

TAB. 7.2 - Comparação das rotas obtidas pelo protótipo desenvolvido e pelo TransCAD

Protótipo desenvolvido TransCAD Depósito

Veículos

(unidade)

Distância

(km)

Tempo

(h)

Custo

(R$)

Veículos

(unidade)

Distância

(km)

Tempo

(h)

Custo

(R$)

Bebidas Jundiaí

4.819,94 69,25 14.459,84

6 5.012,74 71,66 15.038,21

Biscoitos Jundiaí

3.005,87 45,07 9.017,62

2 3.186,22 47,32 9.558,67

Malibu

4.114,80 57,43 12.344,41

3 4.361,69 60,52 13.085,06

Itaperuna

13.968,91 179,11 41.906,74

4 14.527,67 186,09 43.583,00

Barra Mansa

7.480,15 102,01 22.440,43

8 7.629,75 103,88 22.889,26

Frutal

9.392,33 127,90 28.177,00

7 10.331,56 139,64 30.994,69

Sonata

3.481,66 49,52 10.444,98

3 3.725,38 52,57 11.176,13

Carazinho

14.302,98 206,30 42.908,94

13 14.732,07 211,66 44.196,21

Santa Helena

18.315,07 241,94 54.945,21

8 18.681,37 246,52 56.044,11

Ouro Preto

38.036,03 498,94 114.108,07

7 39.937,83 522,71 119.813,49

Garanhuns

8.153,83 115,41 24.461,48

11 8.724,60 122,54 26.173,79

Feira de Santana

4.355,14 55,94 13.065,40

2 4.790,65 61,38 14.371,96

Centro de Distribuição Jundiaí

2.084,05 27,55 6.252,13

2 2.146,57 28,33 6.439,71

Centro de Distrib. Duque de Caxias

2.515,30 33,44 7.545,89

2 2.741,68 36,27 8.225,03

Centro de Distribuição Rio Bonito

4.336,46 62,20 13.009,37

2 4.466,55 63,83 13.399,66

Cross Docking Brasília

6.915,89 93,45 20.747,67

2 7.607,48 102,09 22.822,44

Centro de Distribuição Simões Filho

4.478,79 60,98 13.436,37

3 4.747,52 64,34 14.242,55

Centro de Distribuição Viana

7.655,76 100,70 22.967,28

3 7.808,88 102,61 23.426,63

Centro de Distribuição Contagem

5.292,93 74,16 15.878,78

3 5.716,36 79,45 17.149,09

Centro de Distribuição São José

4.024,59 61,80 12.073,77

3 4.306,31 65,32 12.918,93

Centro de Distribuição Pinhais

4.357,00 63,46 13.071,01

2 4.574,85 66,18 13.724,55

Centro de Distribuição Londrina

6.118,15 87,48 18.354,44

2 6.485,24 92,07 19.455,72

Centro de Distribuição Porto Alegre

3.366,26 45,58 10.098,75

3 3.500,91 47,26 10.502,73

TOTAL

101

180.571,89 2.459,62 541.715,58

101 189.743,88 2.574,27 569.231,64

127

A tabela 7.2 apresenta as informações das rotas agrupadas por depósito, a qual possibilita a

comparação entre a solução obtida através do protótipo desenvolvido e do TransCAD. Observa-

se que a solução obtida pelo protótipo desenvolvido apresentou menores custos do que a solução

obtida através do TransCAD.

7.6 CONSIDERAÇÕES FINAIS

Este capítulo apresentou um estudo de caso que possibilitou a aplicação do procedimento

proposto e validação do protótipo de software desenvolvido. Descreveram-se os dados obtidos

com a empresa os quais foram utilizados na roteirização e demonstrou-se a execução do

protótipo passo a passo.

Validou-se o protótipo desenvolvido através da comparação dos resultados obtidos com um

software comercial chamado TransCAD, a qual demonstrou que o protótipo permite a obtenção

de soluções com menores custos.

Seria interessante comparar a solução obtida neste estudo de caso com uma solução que

fosse utilizada pela empresa para identificar a redução de tempo, frota e custos a obtidos a partir

do uso do protótipo desenvolvido. Mas como a empresa ainda está analisando a modificação de

seu modelo a partir diversificação de sua matriz de venda e não existem soluções de roteirização,

tornou-se inválida esta comparação.

128

8 CONCLUSÕES E RECOMENDAÇÕES

8.1 CONCLUSÕES

Neste trabalho foi desenvolvido um procedimento para roteirização de veículos com

múltiplos depósitos que utiliza uma tecnologia de informação (SIG) em um sistema de

distribuição física. Ele foi elaborado para contemplar, restrições de carga e volume dos veículos

e depósitos, de limite de jornada de trabalho, tempo de descarga no cliente, assim como

restrições do sistema viário, essa obtida com a utilização do SIG.

Para tanto, foi necessário um estudo dos principais métodos existentes de solução para

problemas de roteirização de veículos com múltiplos depósitos. Devido à complexibilidade

operacional existente em resolver um problema de grande porte, com mais de um depósito,

optou-se por utilizar um método de duas fases com algoritmos heurísticos. Na primeira fase, a de

atribuição dos clientes aos depósitos, utilizou-se o algoritmo de atribuição com urgências

paralela. Na segunda fase, a de roteirização dos veículos, utilizou-se o método das economias de

Clark and Wright e uma fase de pós-otimização 2-OPT. Estes se mostraram bastante eficientes e

de fácil desenvolvimento.

Como conseqüência, desenvolveu-se um protótipo que demonstrou a integração do SIG

OpenJUMP com o procedimento de roteirização, o qual foi concebido como um plugin. Utilizou-

se para o seu desenvolvimento a linguagem Java dentro do paradigma da Orientação a Objetos e

para seu detalhamento foram utilizados diagramas conceituais de UML.

A realização de um estudo de caso possibilitou a aplicação do procedimento proposto e

validação do protótipo de software desenvolvido, o qual permitiu obter rapidamente uma solução

e fornecer uma série de benefícios como redução da distância percorrida, menor consumo de

combustível, menor número de horas extras e redução do tempo de entrega do produto.

Validou-se o protótipo desenvolvido através da comparação dos resultados obtidos com um

software comercial chamado TransCAD, a qual demonstrou que o protótipo permite a obtenção

de soluções com menores custos.

129

8.2 RECOMENDAÇÕES

Todo o procedimento, assim como o protótipo, pode ser aprimorado para permitir outras

restrições operacionais como, por exemplo, janelas de tempo de clientes e depósitos e coletas e

entregas simultâneas. Poderia ser aprimorado também para tratar veículos de diferentes tipos,

como são os casos dos veículos refrigerados, veículos que transportam cargas perigosas, etc. Isso

permitiria uma maior aplicação do procedimento.

Outra tecnologia da informação bastante difundida atualmente é o GPS (Geografic Position

System), o qual poderia ser utilizado em conjunto com o SIG para resolução do problema

dinâmico de roteirização de veículos, pois com a localização em tempo real obtida pelo GPS é

possível que tomador de decisão altere as rotas durante a efetivação das soluções.

Dentre os métodos de solução existentes, verificou-se que as metaheurísticas estão sendo

muito difundidas na literatura. A aplicação de uma metaheurística para solucionar roteirizações

que envolvam rotas com grande número de clientes seria bastante interessante, podendo obter

melhores soluções do que o método de economias de Clark and Wright.

O estudo de caso desenvolvido requer uma análise para avaliar o grau de redução dos custos

de transportes. Isso seria de grande importância para comprovar a eficiência do procedimento.

Após a modificação do modelo de distribuição da empresa, tornará válida a comparação entre a

solução obtida a partir do uso do protótipo desenvolvido com a solução utilizada pela empresa

sem auxilio de software.

Sendo que o protótipo desenvolvido permite a escolha de atributos calculados da malha

viária, para contemplar atrasos devido à própria operação dos veículos e congestionamentos,

seria interessante, ao invés de considerar a distância como parâmetro que determina a melhor

solução, utilizar o parâmetro tempo de viagem ao longo do sistema viário para definir a melhor

solução.

130

9 REFERÊNCIAS BIBLIOGRÁFICAS

BALLOU, Ronald H.

Logística empresarial: transporte, administração de materiais e

distribuição física

. São Paulo: Atlas, 1993. ISBN 8522408742.

BALLOU, Ronald H.

Gerenciamento da Cadeia de Suprimentos: Planejamento,

Organização e Logística Empresarial

. São Paulo: Bookman, 2001. ISBN 8573078510.

BALLOU, Ronald H.

Gerenciamento da Cadeia de Suprimentos / Logística Empresarial

São Paulo: Bookman, 2006. ISBN 8536305916.

BERALDI, Lairce Castanhera, ESCRIVÃO FILHO, Edmundo, RODRIGUES, Denise Marin.

Avaliação da adequação do uso te tecnologia de informação na pequena empresa

, In:

Simpósio de Engenharia de Produção - SIMPEP, n. 6, Bauru, 2000.

BONASSER, U.O.

Meta-heurísticas híbridas para solução do problema de roteirização de

veículos com múltiplos depósitos e frota heterogênea fixa: aplicação na força aérea

brasileira

. 2005. Tese (Doutorado) - Escola Politécnica, Universidade de São Paulo, São

Paulo, 2005.

BOWERSOX, Donald J., CLOSS, David J., COOPER, M. B.

Gestão Logística de Cadeia de

Suprimentos

, São Paulo: Bookman, 2006. ISBN 8522442762.

BRETERNITZ, Vivaldo J.

Sistemas de informações geográficas: uma visão para

administradores e profissionais de tecnologia da informação

. Jundiaí: Análise, v. 4, p.

41-55, 2001.

BROOKE, A., KENDRIK, D., MEERAUS, A.

GAMS Release 2.25, A User's Guide

. GAMS

Development Corporation, Washington, USA, 1996.

BURROUGH, P. A.; MCDONNELL, R. A.

Principles of geographical information systems

New York: Oxford University Press, 1998.

CALIPER, TransCAD.

Transportation GIS Software. User’s Guide Version 4.0 for

Windows

. Caliper Corporation, Newton, EUA, 2000.

CÂMARA, G.

Modelos, Linguagens e Arquiteturas para Bancos de Dados Geográficos

. São

José dos Campos: Tese de doutorado, Instituto Nacional de Pesquisas Espaciais - INPE,

1995.

131

CÂMARA, G; CASANOVA, M.A., HEMERLY, A.S., MAGALHÃES, G.C., MEDEIROS,

C.M.B.

Anatomia de Sistemas de Informações Geográficas

. Campinas: Escola de

Computação, Instituto de Computação, UNICAMP, 1996.

CÂMARA, G., SOUZA, R. C. M., PEDROSA, B. M., VINHAS, L., MONTEIRO, A. M. V.,

PAIVA, J. A. CARVALHO, M. T. AND GATASS, M.

TerraLib: technology in support

of GIS innovation.

In: Anais, Workshop Brasileiro de Geoinformática. São Paulo: Instituto

Nacional de Pesquisas Espaciais - INPE, 2000, p. 126-133.

CÂMARA, G.; ONSRUD, H.

Open source GIS software: myths and realities

. In: Julie M.

Esanu and Paul F. Uhlir, Eds, Open Access and the Public Domain in Digital Data and

Information for Science: Proceedings of an International Symposium. Washington: The

National Academies Press, 2004. ISBN 0-309-09145-4.

CARVALHO, M.S., PINA, M.F., SANTOS, S.M.

Conceitos Básicos de Sistema de

Informações Geográficas e Cartografia Aplicados à Saúde

. Organização Panamericana

da Saúde / Ministério da Saúde, Brasília, 2000.

CHAO, I. M., GOLDEN, B.L., WASIL, E.

A new heuristic for the multi-depot vehicle

routing problem that improves upon best-known solutions

. American Journal of

Mathematical and Management Mgmt Sciences, v. 13, p. 371-406, 1993.

CHAN, Yupo, BAKER, S.F.

The Multiple Depot, Multiple Traveling Salesmen Facility-

Location Problem: Vehicle Range, Service Frequency, and Heuristic Implementations

Mathematical and Computer Modeling, v. 41, p. 1035-1053, 2005.

CHRISTOFIDES, N., EILON, S.

An algorithm for one vehicle-dispatching problem

, OPL

Research, v. 20, p. 309-318, 1969.

CHRISTOFIDES, N., MINGOZZI, A., TOTH, P.

The vehicle routing problem

, Chichester:

Combinatorial Optimization, Wiley, p. 315-338, 1979.

CHRISTOPHER, Martin.

Logística e Gerenciamento da Cadeia de Suprimentos, Estratégias

para a Redução de Custos e Melhoria dos Serviços

. São Paulo: Pioneira, 1999. ISBN:

0750636262.

CLARK, G., WRIGHT, J.W.

Scheduling of Vehicles from a Central Depot to a Number of

Delivery Points

. Operations Research, 1964.

CLOSS, David J., GOLDSBY, Thomas J., CLINTON, Steven R.

Information technology

influences on world class logistics capability

, International Journal of Physical

Distribution & Logistics Management, 1997.

CORDEAU, J.F., GENDREAU, M., HERTZ, A., LAPORTE, G., SORMANY, J. S.

New

Heuristics for the Vehicle Routing Problem

, New York: A. Langevin and D. Riopel,

Logistic systems, design and optimization, Springer, p. 279-297, 2005.

132

CORDEAU, J.F., GENDREAU, M., LAPORTE, G.

A Tabu Search Heuristic for Periodic and

Multi-Depot Vehicle Routing Problems

, Networks, v. 30, p. 105-119, 1997.

CREVIER, B., CORDEAU, J.F., LAPORTE, G.

The Multi-Depot Vehicle Routing Problem

with Inter-Depot Routes

, European Journal of Operational Research, v. 176, p. 756-773,

2007.

DIJKSTRA, E. W.

A Note on Two Problems in Connection with Graphs

. Numerische Math.

1, 269-271, 1959.

DORIGO, M., MANIEZZO, V., COLORNI, A.

Positive feedback as a search strategy

Relatório Técnico n. 91-016, Dipartim ento di Elettronica e Informazione, Politecnico di

Milano, Italy, 1991.

DUECK, G.

New optimization heuristics, the great deluge algorithm and the record-to-

record travel

. Relatório Técnico, IBM Germany, Heidelberg Scientific Center, 1990.

EILON, S.; GANDY, W. CHRISTOFIDES.

Distribution management: Mathematical

modeling and Practical analysis

, New York: Hafner Publishing Company, 1971. ISBN:

9780852641910.

FEO, T.A., RESENDE, M.G.C.

Greedy randomized adaptive search procedures

, Journal of

Global Optimization, v. 6, p. 109-133, 1995.

FLEURY, Paulo Fernandes; WANKE, Peter; FIGUEIREDO, Kleber F.

Logística empresarial:

a perspectiva brasileira

, São Paulo: Atlas, 2000. ISBN: 8522427429.

GENDREAU, Michel, POTVIN, Jean-Yves, BRÄYSY, Olli, HASLE, Geir, LØKKETANGEN,

Arne.

Metaheuristics for the Vehicle Routing Problem and its Extensions: A

Categorized Bibliography

, Interuniversity Research Centre on Enterprise Networks,

Logistics and Transportation - CIRRELT, Canada, 2007.

GILLETT, B. E., MILLER, L. E.

A heuristic algorithm for the vehicle-dispatch problem

Operations Research, v. 22, p. 340-349, 1974.

GILLETT, B. E., JOHNSON, J. G.

Multi-terminal vehicle-dispatch algorithm

, Omega, v. 4, n.

6, p. 711-718, 1976.

GIOSA, D., TANSINI, L., VIERA, O.

Assignment algorithms for the Multi-Depot Vehicle

Routing Problem

, Buenos Aires, Argentina: Proceedings of the 28th Conference of the

Argentinian Operations Research Society, 41-47, 1999.

GIOSA, D., TANSINI, L., VIERA, O.

New assignment algorithms for the multi-depot vehicle

routing problem

, Journal of the Operations Research Society, v. 53, p. 997-984, 2002.

133

GOLDBARG, D.E.

Genetic Algorithms in Search, Optimization, and Machine Learning

New York: Addison-Wesley Publishing Company, Inc., 1989.

GOLDBARG, M.C., LUNA, H.P.L.

Otimização combinatória e programação linear:

modelos e algoritmos

. Rio de Janeiro: Campus, 2000.

GOLDEN, B.L., MAGNANTI, T. L., NGUYEN, H. Q.

Implementing vehicle routing

algorithms

, Networks, v. 7, p. 113-148, 1977.

HO, William, HO, George T.S, JI, Ping, LAW, Henry C.W.

A Hybrid Genetic Algorithm for

the Multi-depot Vehicle Routing Problem

. Engineering Applications of Artificial

Intelligence, 2007.

HOLLAND, John.

Adaptation in Natural and Artificial Systems

, Ann Arbor: University of

Michigan Press, 1975.

KINBERGER, M., PUCHER. A.

Open Source GIS als Alternative im Desktop-Bereich -

Evaluation freier Software im Bereich Geoinformation

. In: CORP 2005, Wien,

Österreich, 2005.

KIRKPATRICK, S., GELLAT, C.D., VECCHI, M.P.

Optimization by Simulated Annealing

Science, v. 220, p. 671-680, 1983.

LAMBERT, Douglas. In:

Seminário Internacional de Logística

, Belo Horizonte, 9 jul. 1999.

LAPORTE, Gilbert, NORBERT, Y., ARPIN, D.

Optimal solutions to capacitated multidepot

vehicle routing problems. Congressus Numerantiwn

. v. 44, p. 283-292, 1984.

LAPORTE, G., MERCURE, H., NOBERT, Y.

An Exact Algorithm for the Asymmetrical

Capacitated Vehicle Routing Routing Problem

. Networks, 1986.

LAPORTE, Gilbert, NORBERT, Y., TAILLEFER, S.

Solving a family of multi-depot vehicle

routing and location-routing problems

, Transp. Science, v. 22, 161-172, 1988.

LICKER, Paul S.

Management information systems: a strategic leadership approach

Orlando: The Dryden Press, 1997.

LIM, Andrew, WANG, Fan.

Multi-Depot Vehicle Routing Problem: A One-Stage Approach

IEEE Transactions on Automation Science and Engineering, v. 2, n. 4, p. 397-402, 2005.

LIMA, Maurício Pimenta.

Custos logísticos na economia brasileira

, Rio de Janeiro: Revista

Tecnologística, 2006.

LIMA, Adilson da Silva.

UML 2.0 do requisito à solução

. Primeira edição, São Paulo: Érica,

2005.

134

LIN, S.,

Computer solution of the traveling salesman problem

, Bell Systems Computer

Journal, v. 44, p. 2245-2269, 1965.

LISBOA FILHO, Jugurta.

Introdução a SIG - Sistemas de Informações Geográficas

. Porto

Alegre: CPGCC da UFRGS, 1995.

LIU, F.H.; SHEN, S.Y.

The fleet size and mix vehicle routing problem with time windows

Journal of Operational Research Society, 1999.

MLADENOVIC, Nenad, HANSEN, Pierre.

Variable neighborhood search

, Computer

Operations Research, v. 24, p. 1097-1100, 1997.

MOLE, R.H., JAMESON, S.R.

A sequencial route-building algorithm employing a

generalized savings criterion

. Operational Research, 1976.

MURAI, S.

SIG Manual Básico: Volume 1: Conceptos Fundamentales

. Japão: Universidade

de Tokio - Revista Selper, v. 15, nº 1, 1999.

NAGY, G., SALHI, S..

Heuristic algorithms for single and multiple depot vehicle routing

problems with pickups and deliveries

, European Journal of Operational Research, v. 162,

p. 126-141, 2004.

NEVES, Tiago A.

Resolução do problema de Roteamento de Veículos com Frota

Heterogênea e Janelas de Tempo

. Monografia - Apresentada no curso de Ciência da

Computação, da Universidade Federal de Ouro Preto, MG, 2004.

NOVAES, A. G.

Logística e gerenciamento da cadeia de distribuição: estratégia, operação e

avaliação

. Rio de Janeiro: Campus, 2001.

OLIVEIRA, Djalma de Pinho Rebouças.

Sistemas de informações gerenciais: estratégias,

táticas, operacionais.

5. ed. São Paulo: Atlas, 1998. ISBN 9788522446131.

OPENGIS CONSORTIUM, Inc:

OpenGIS Simple Features Specification for SQL

. Revision

1.1, 1999.

PRESSMAN, R. S.

Engenharia de Software

, Makron Books, São Paulo, Primeira edição, 1995.

RAFT, O. M.

A modular algorithm for an extended vehicle scheduling problem

, OPL

Research, v. 11, p. 67-76, 1982.

RENAUD, J., BOCTOR, F. F., LAPORTE, G.

An improved petal heuristic for the vehicle

routing problem

. The Journal of the Operational Research Society, v. 47, n. 2, p. 329-336,

1996.

135

RENAUD, Jacques, LAPORTE, Gilbert, BOCTOR, Fayez F.

A tabu search heuristic for the

multi-depot vehicle routing problem

, Computer Operations Research, v. 23, p. 229-235,

1996.

RUSSELL, R., IGO, W.

An assignment routing problem

. Networks, v. 9, p. 1-17, 1979.

SALHI, S., SARI, M., SAIDI, D., TOUATI, N.

Adaptation of some vehicle fleet mix

heuristics

, Omega, v. 20, p. 653-660, 1992.

SALHI, S., SARI, M.

Models for the multi-depot vehicle fleet mix problem,

European Journal

of Operational Research, v.103, p. 95-112, 1997.

SÁRKÖZY, Ferenc.

GIS Functions. Periodica Polytechnica Ser. Civ. Eng

. Hungary: v. 43, n.

1, p. 87-106, 1999.

TANSINI, L., URQUHART, M., VIERA, O.

Comparing assignment algorithms for the

multi-depot VRP

. Relatório Técnico n. 01-08, Instituto de Computación, Universidad de la

República, Montevideo, Uruguay, 2001.

TILLMAN, F. A.

The multiple terminal delivery problem with probabilistic demands

Transportation Science. v. 3, p. 192-204, 1969.

TILLMAN, F. A., HERING, R. W.

A study of a look-ahead procedure for solving the

multiterminal delivery problem

, Transportation Research, v. 5, p. 225-229, 1971.

TILLMAN, F.A., CAIN, T. M.

An upperbound algorithm for the single and multiple

terminal delivery problem

, Management Science, v. 18, p. 664-682, 1972.

UCHOA, H. N., FERREIRA, P. R.

Geoprocessamento em Software Livre

. Disponível em:

http://www.igc.usp.br/pessoais/guano/downloads/geoprocessamento_software_livre_Uchoa-

Robertov1.0.pdf, 2004.

WREN, A. HOLLIDAY, A.

Computer scheduling of vehicles from one or more depots to a

number of delivery points

. Operations Research, v. 23, p. 333-344, 1972.

YELLOW, P.

A Computational modification to the savings method of vehicle scheduling

OPL Research. v. 21, p. 281-283, 1970.

Livros Grátis
( http://www.livrosgratis.com.br )
 
Milhares de Livros para Download:
 
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas

Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
 
 