HEURÍSTICA GRASP PARA O PROBLEMA DO ......Figura 6.12 - Parâmetros de Configuração da GRASP 112 Figura 6.13 - Resultado do Processamento 112 Figura 6.14 - Visualização das Rotas

II

HEURÍSTICA GRASP PARA O PROBLEMA DO ROTEAMENTO DE

VEÍCULOS COM MULTI-COMPARTIMENTOS E SUA INTEGRAÇÃO

COM O SISTEMA DE INFORMAÇÃO GEOGRÁFICA GEO-ROTA

CARLOS LEONARDO RAMOS PÓVOA

“Tese apresentada ao Centro de Ciências e Tecnologia, da Universidade Estadual do Norte Fluminense, como parte das exigências para obtenção do título de Doutor em Ciências de Engenharia na área de concentração de Engenharia de Produção”.

Orientador: prof. Geraldo Galdino de Paula Jr., D.Sc.

CAMPOS DOS GOYTACAZES – RJ

Outubro - 2005

III




CARLOS LEONARDO RAMOS PÓVOA

“Tese apresentada ao Centro de Ciências e Tecnologia, da Universidade Estadual do Norte Fluminense, como parte das exigências para obtenção do título de Doutor em Ciências das Engenharias”.

Aprovada em : __________________ Comissão Examinadora: __________________________________________________ Prof. Geraldo Galdino de Paula Jr. D.Sc., UENF (Presidente) __________________________________________________ Prof. José Ramón Arica Chávez D.Sc., UENF __________________________________________________ Prof. Rodrigo Tavares Nogueira D.Sc., UES __________________________________________________ Prof. José Elias Cláudio Arroyo D.Sc., UCAM

IV

DEDICATÓRIA

A Minha Esposa Fabiana e

a Meus Pais Carlos Augusto e Joana.

V

AGRADECIMENTOS

A Deus que me ajudou e me iluminou nos momentos de dificuldade e

dúvidas, mostrando sempre o melhor caminho.

A minha esposa e a meus pais pelo incentivo e compreensão, me

dando força nos momentos de dúvidas e dificuldades.

A meu orientador, professor Geraldo Galdino, pela grande amizade,

incentivo, compreensão e dedicação fundamental para a conclusão deste trabalho.

A meus amigos, colegas de doutorado e funcionários do CCT da

UENF, pela amizade e apoio.

A todos os professores do Laboratório de Engenharia de Produção,

especialmente a Arica, Gudélia e Alcimar pelas palavras de incentivo.

Aos profs. Rodrigo Tavares Nogueira de Castro, José Elias Cláudio

Arroyo e José Ramón Arica Chávez pela presença na banca examinadora,

apontando vários deslizes e pontos obscuros.

E a todos aqueles que, de uma forma ou de outra, contribuíram para a

conclusão deste trabalho em especial Frederico Galaxe e André Velasco,

companheiros de batalha desde da Uerj.

VI

Sumário

Lista de Figuras IX

Lista de Tabelas XII

Resumo XIII

Abstract XIV

Capítulo 1 - Introdução 15

1.1 - Objetivo 18

1.2 - Organização da Tese 18

Capítulo 2 – Problemas de Roteirização de Veículos 20

2.1 - Extensões do Problema de Roteamento de Veículos 21

2.2 - Classificação do Problema de Roteamento de Veículos 23

2.2.1 - Endereços 26

2.2.2 - Veículos 28

2.2.3 - Características do Problema 30

2.2.4 - Objetivos 33

2.3 - Estratégias e Métodos de Soluções 34

2.3.1 - Algoritmos Exatos 36

2.3.2 - Métodos Heurísticos 36

Capítulo 3 – Sistemas de Informação Geográfica - SIG 45

3.1 - Definições 45

3.2 - Breve Histórico 46

3.3 - Componentes 48

3.4 - Modelagem de Dados 50

3.5 - Modelagem Conceitual de Banco de Dados Geográficos 51

3.6 - Modelagem Orientada a Objetos 52

VII

3.7 - O FrameWork GeoFrame 53

3.7.1 - Tema e Região Geográfica 54

3.7.2 - Objeto e não Geográfico e Fenômeno Geográfico 55

3.7.3 - Campo Geográfico e Objeto Geográfico 56

3.7.4 - Objeto Espacial 56

3.7.5 - Representação de Campo Geográfico 58

3.8 - Especificando Fenômenos e Objetos Geográficos 58

3.9 - Especificando o Componente Espacial dos Fenômenos

Geográficos 59

Capítulo 4 – Modelagem Conceitual do Sistema de Informação Geográfica

Geo-Rota 61

4.1 - Requisitos de Softwares para Roteirização de Veículos 61

4.1.1 - Sistemas para Roteirização de Veículos 61

4.1.2 - Utilização de Sistemas de Roteirização no

Contexto da Distribuição no Brasil 63

4.2 - Descrição do Sistema de Informação Geográfica Geo-

Rota 65

4.3 - Considerações sobre Rede de Vias e Modelagem de

Dados 65

4.4 - Esquema Conceitual de Dados do SIG Geo-Rota 67

4.4.1 - Tema Frota_Veículos 67

4.4.2 - Tema Rota_Entrega 68

4.4.3 - Tema Rede_Vias 68

4.4.4 - Modelo Completo 69

Capítulo 5 – Heurística GRASP para o Problema de Roteamento de

Veículos com Multi-Compartimentos 72

5.1 - O Problema de Roteamento de Veículos com Multi-

Compartimentos 72

5.1.1 - Modelo Matemático 73

VIII

5.2 - Metaheurística GRASP 73

5.3 - GRASP para o Problema de Roteamento de Veículos com

Multi-Compartimentos 77

5.3.1 - Determinação do Custo 78

5.3.2 - Condições de Viabilidade 79

5.3.3 - Procedimento de Melhoria (Busca Local) 80

5.4 - Implementação Computacional 80

5.5 - Experimentos Computacionais 81

5.5.1 - Testes Utilizando Algoritmos Exatos 82

5.5.2 – Testes com Instâncias Aleatórias 83

Capítulo 6 – Sistema de Informação Geográfica Geo-Rota 105

6.1 - Principais Funções do SIG – Geo-Rota 105

6.1.1 - Gerenciamento de Projetos 105

6.1.2 - Gerenciamento de Mapas 105

6.1.3 - Gerenciamento de Clientes 107

6.1.4 - Gerenciamento da Frota de Veículos 107

6.1.5 - Funções de Roteamento de Veículos 109

Capítulo 8 – Considerações Finais 114

7.1 – Conclusões 115

7.2 - Sugestões para Trabalhos Futuros 115

REFERÊNCIAS BIBLIOGRÁFICAS 116

APÊNDICE 1 124

IX

LISTA DE FIGURAS

Figura 2.1 - Problema básico de Roteamento de Veículos 21

Figura 3.1 - Relacionamento entre os componentes de um SIG 49

Figura 3.2 - Notação gráfica do diagrama de classes UML (resumido) 54

Figura 3.3 - Diagrama de Classes do GeoFrame 55

Figura 3.4 - Estereótipos para generalização 59

Figura 3.5 - Estereótipos para associação 60

Figura 4.1 - Único nó representando a interseção 67

Figura 4.2 - Representação expandida de uma interseção 67

Figura 4.3 - Tema Frota_Veículos 68

Figura 4.4 - Tema Rota_Entrega 69

Figura 4.5 - Tema Rede de Vias 70

Figura 4.6 - Modelo conceitual de dados do SIG – Geo-Rota 71

Figura 5.1 - Veículos com Multi-Compartimentos 73

Figura 5.2 - Problema básico de Roteamento de Veículos com Multi-

Compartimentos 74

Figura 5.3 - Pseudocódigo da metaheurística GRASP 75

Figura 5.4 - Pseudocódigo da fase de construção 76

Figura 5.5 - Pseudocódigo da fase de busca local 77

Figura 5.6 - Procedimento Seleção de Sementes 78

Figura 5.7 - Procedimento Construir Solução 79

Figura 5.8 - Procedimento de Busca Local 80

Figura 5.9 - Modelo UML – GRASP 82

Figura 5.10 - Gráfico Comparativo – Iterações 85

Figura 5.11 - Gráfico Comparativo – Lista de Candidatos Restritos 86

Figura 5.12 - Avaliação dos parâmetros δ1, δ2 e δ3 (Inst1) 87

Figura 5.13 - Variação da função objetivo – L.C.R – Inst2_20 Clientes 89




Figura 5.17 - Variação da função objetivo - δ1, δ2 e δ3 (Inst2_20) 91


X























Figura 6.1 - Funções de Gerenciamento de projetos 106

Figura 6.2 - Funções de Gerenciamento de mapas 106

Figura 6.3 - Configuração para Endereçamento Automático 107

Figura 6.4 - Busca por Endereço e Cadastro de Clientes 108

Figura 6.5 - Cadastro de Veículos 108

Figura 6.6 - Caminho mais Curto entre Clientes 109

Figura 6.7 - Rota MultiPonto – Problema do Caixeiro Viajante 110

Figura 6.8 - Projeto de Roteamento 110

Figura 6.9 - Seleção do Depósito de Partida 111

Figura 6.10 - Arquivo de Demanda dos Clientes 111

Figura 6.11 - Seleção de Veículos 112

XI

Figura 6.12 - Parâmetros de Configuração da GRASP 112

Figura 6.13 - Resultado do Processamento 112

Figura 6.14 - Visualização das Rotas no Mapa 113

XII

LISTA DE TABELAS

Tabela 3.1 - Evolução da tecnologia de SIGs 47

Tabela 4.1 - Requisitos e características de um sistema para roteirização

de veículos 62

Tabela 5.1 - Resultados algoritmo exato 83

Tabela 5.2 - 50 Iterações 84




Tabela 5.6 - Resultados Médios - Iterações 86

Tabela 5.7 - Resultados Médios – L.C.R 86

Tabela 5.8 - Resultados Médios 87

Tabela 5.9 - Avaliação dos parâmetros δ1, δ2 e δ3 (Inst1) 87

Tabela 5.10 - Resultados Médios L.C.R – Inst2 88






Tabela 5.16 - Resultados Médios L.C.R – Inst5_385 100

Tabela 5.17 - Avaliação dos parâmetros δ1, δ2 e δ3 (Inst5_385) 101

Tabela 5.18 - Resultados Médios L.C.R – Inst6_1034 102

Tabela 5.19 - Avaliação dos parâmetros δ1, δ2 e δ3 (Inst6_1034) 103

XIII




Carlos Leonardo Ramos Póvoa

06 de Outubro de 2005

Resumo

Há uma série de serviços que são considerados problemas de distribuição como entrega bancária, entrega postal, entrega de mercadorias, rotas de ônibus escolar, coleta de lixo industrial, serviço de entregas noturnas, operações de frete etc. Esses problemas são conhecidos como problemas de roteamento de veículos e a utilização de modelagem matemática aliada a soluções computacionais tem-se mostrado satisfatória na solução desses problemas. Algumas empresas utilizam veículos com mais de um compartimento para o serviço de distribuição de mercadorias, podem-se citar as empresas de distribuição de combustível e as de alimento que podem ter o seu transporte feito em veículos que possuem divisões de temperaturas de acordo com o tipo de produto. Esta parece ser uma tendência mundial para o transporte de cargas heterogêneas, já que várias empresas estão adotando essas soluções. Os sistemas de informação geográfica (SIG) têm sido bastante usados como forma de armazenamento e manipulação das informações necessárias para a tarefa de entrega de mercadorias. Nesses sistemas são armazenados todos os dados relevantes à tarefa de roteirização, como a localização das vias de acesso, localização dos pontos de entrega (clientes), topologia viária e toda a base cartográfica de apoio necessária. Nessa tese é demonstrada a solução do problema de roteamento de veículos com multi-compartimentos através de um algoritmo heurístico GRASP (Greedy Randomized Adaptive Search Procedure). Para manipular as informações necessárias foi desenvolvido um SIG, aqui chamado de Geo-Rota, que foi modelado usando o framework GeoFrame.

Palavras Chaves: Sistema de Informação Geográfica, Roterização de Veículos, GRASP, Heurística.

Orientador: Prof. Geraldo Galdino de Paula Jr.

XIV

GRASP HEURISTIC FOR VEHICLE ROUTING PROBLEM WITH

MULTI-COMPARTMENTS AND YOUR INTEGRATOR WITH

GEOGRAPHIC INFORMATION SYSTEM GEO-ROTA

Carlos Leonardo Ramos Póvoa

October 06, 2005 Advisor: Prof. Geraldo Galdino de Paula Jr.

Abstract

There is a series of services that are considered distribution problems, as bank delivery, postal service, delivery of goods, broken of school bus, collects of industrial garbage, service of night deliveries, freight operations etc. Those problems are known as problems of vehicle routing and the use of mathematical modeling and computational solutions it has been showing satisfactory in the solution of those problems. Some companies use vehicles with more than a compartment for the service of distribution of goods, the companies of distribution of fuel can be mentioned and the one of food that can have your transport done in vehicles that possess divisions of temperatures in agreement with the product type. This seems to be a world tendency for the transport of heterogeneous loads, since several companies are adopting those solutions. The geographical information systems (GIS) they have been enough used as storage form and manipulation of the necessary information for the task of delivery of goods. In those systems all are stored the important data to the routing task, as the location of the access roads, location of the delivery points (customers), road topology and the whole cartographic base of support necessary. In this article the solution of the problem of vehicle routing is demonstrated with multi-compartments through a heuristic algorithm GRASP (Greedy Randomized Adaptive Search Procedure). To manipulate the necessary information a GIS it was developed, here call of Geo-Rota that was modeled using the framework GeoFrame.

Key Words: Geographical Information Systems, vehicle routing, GRASP, Heuristic.

15

___________________________________________________________________

1 INTRODUÇÃO

A logística vem se destacando como fator primordial de sobrevivência

empresarial. Um completo sistema logístico abrange o processo de movimentação

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

fornecedores a fábrica, o movimento desses produtos para vários centros de

distribuição ou depósitos, e a entrega destes produtos ao consumidor final.

Segundo Ballou (1993) 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 é uma utopia. Uma região tende a

especializar-se na produção daquilo em que tiver vantagem econômica para fazê-lo.

Isto cria um hiato de tempo e espaço entre fontes de matéria-prima 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 da logística. Ou seja, sua

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

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

A atividade de distribuição física de produtos de uma empresa compreende

toda a movimentação de bens entre a fábrica e os centros de distribuição. A última

etapa nessa movimentação, dos centros de distribuição para os consumidores, a

qual pode ser definida como transporte local ou entrega, representa o elo mais caro

da cadeia de distribuição (Christofides, 1981). Para esta etapa ser realizada de

maneira eficiente, a empresa deve desenvolver o planejamento e a execução desta

atividade de transporte de forma racional e otimizada (Bodin et al., 1983).

Ballou (1993) identifica que os custos logísticos de produtos tangíveis

representam cerca de 23% do PIB, no Estados Unidos, e destes custos, o transporte

representa algo em torno de dois terços.

As atividades relacionadas ao transporte e à distribuição física buscam, cada

vez mais, o aprimoramento da qualidade e da produtividade, de forma a garantir um

16

melhor aproveitamento da frota e diminuição dos roteiros dos veículos. O aumento

do número de entregas e sua dispersão geográfica em decorrência da política de

redução de estoque das empresas, que as leva a efetuar pedidos menores e com

maior freqüência, causam um impacto significativo nas operações e nos custos

associados aos sistemas de distribuição. Concomitantemente, aumentam as

exigências dos clientes com relação a prazos, datas e horários de entrega.

Um dos pontos de destaque na atividade de transporte de mercadorias

consiste na definição do percurso ou rota de entrega a ser feita pelos veículos, de

forma a percorrer todos os pontos de entrega (passagem obrigatória) com um custo

mínimo de operação. Numa malha viária, ou rede de vias, pode-se obter o percurso

mínimo para os veículos considerando: os custos de operação mínimos; os tempos

de percurso mínimos, as distâncias mínimas ou menor consumo de combustível.

Esse problema é conhecido como problema de roteamento de veículos, que

segundo Laporte et al. (2000) consiste em definir roteiros que minimizem o custo

total de atendimento, cada um dos quais iniciando e terminando no depósito ou base

de veículos, assegurando que cada ponto seja visitado exatamente uma vez

(clientes) e a demanda em qualquer rota não exceda a capacidade do veículo que a

atenda.

Por outro lado, o interesse e a demanda pela aplicação de modelos de

roteirização para problemas reais, através de softwares comerciais disponíveis no

mercado, têm crescido muito nos últimos anos, em particular no Brasil,

principalmente após a estabilização da economia, conforme discutido em detalhes

por Cunha (1997). Entre as razões podem-se destacar as exigências dos clientes

com relação a prazos, datas e horários de entregas; o agravamento dos problemas

de trânsito, acesso, circulação e estacionamento de veículos nos centros urbanos,

em particular, caminhões; o aumento da competitividade pelo mercado e a busca de

eficiência trazida pela estabilização da economia; o custo do capital levando à

redução de estoques e ao aumento da freqüência de entregas.

Os mapas assumem importância primordial para a aplicação prática de

problemas de roteamento. Em uma base cartográfica usada para fins de logística de

17

distribuição, geralmente uma planta cadastral, por exemplo, podem-se representar

as ruas, os sinais, os postes, etc. Bem como se a rua é de mão dupla ou única, a

velocidade máxima permitida na mesma, quais trechos que estão geralmente

engarrafados em determinado horário. Destaca-se, também, a importância de

localizar os pontos de entrega (clientes) nessa base.

Na década de 60 apareceram os primeiros sistemas que, além de representar

as feições presentes em um mapa no formato digital, possibilitaram também o

relacionamento com atributos de natureza não gráfica. Nesses sistemas,

denominados Sistemas de Informação Geográfica (SIG), encontram-se presentes,

dentre outras, as funções de análise que são capazes de permitir ao usuário

operações sobre aspectos espaciais dos dados georrefenciados, sobre atributos não

espaciais destes dados, ou sobre atributos espaciais e não espaciais combinados.

Deve-se destacar que são raros os softwares de roteamento baseados realmente

em sistemas de informação geográfica (SIG), conforme Cunha (1997).

Tem se observado em diversas aplicações, principalmente no caso brasileiro,

que, embora a seleção e a implantação de softwares de roteirização tenham sido

feitas com cuidado, os benefícios obtidos com a sua utilização resultam aquém das

expectativas iniciais, mesmo se tratando de produtos consagrados no mercado,

conforme descrito em Cunha (1997).

Isso decorre nem sempre da fragilidade dos algoritmos de solução

incorporados nos softwares, na maioria das vezes extensivamente testados e

validados, com inúmeros casos de sucesso nos seus países de origem, mas

principalmente de condicionantes locais e particularidades dos problemas que não

podem ser considerados, assim como da fragilidade dos dados de entrada que

alimentam os modelos.

Algumas empresas utilizam veículos com mais de um compartimento para o

serviço de distribuição de mercadorias, podem-se citar as empresas de combustível

e as de alimento que podem ter o seu transporte feito em veículos que possuem

divisões de temperaturas de acordo com o tipo do produto. Esta parece ser uma

18

tendência mundial para o transporte de cargas heterogêneas, já que várias

empresas estão adotando essas soluções (Moreira, 2000).

A motivação em trabalhar com esse tipo de problema é justificada pela falta

de estudos sobre este assunto e a relevante importância do mesmo para reduzir

custos de entrega nestas empresas. É com base nos elementos observados acima

que são definidos os objetivos desse trabalho, apresentados a seguir.

1.1 OBJETIVO

Conforme discutido acima o objetivo dessa tese é modelar e resolver, através

de um algoritmo heurístico (GRASP), o problema de roteamento de veículos com

multi-compartimentos, bem como promover sua integração com o sistema de

informação geográfica Geo-Rota (Póvoa, 2000) que foi remodelado (esquema

conceitual de dados) utilizando o framework GeoFrame (Lisboa, 2000). Deve-se

destacar que até o presente momento desconhece-se a concepção de alguma

heurística para resolver o problema de roteamento de veículos com multi-

compartimentos.

1.2 ORGANIZAÇÃO DA TESE

A presente tese está organizada em 6 capítulos. Após este capítulo

introdutório, segue o capítulo 2 onde são apresentados os principais problemas de

roteamento de veículos, bem como estratégias de solução.

O capítulo 3 trata das definições de sistemas de informação geográfica (SIG),

bem como questões de armazenamento e modelagem conceitual de dados

geográficos. No capítulo 4 é apresentada a modelagem conceitual do SIG Geo-Rota.

O capítulo 5 apresenta a heurística GRASP desenvolvida para resolver o

problema de roteamento de veículos com multi-compartimentos bem como os

experimentos computacionais realizados.

19

O capítulo 6 descreve os aspectos inerentes à implementação do modelo de

dados do SIG Geo-Rota, bem como suas principais funções.

Por fim, o capítulo 7 apresenta as conclusões e sugestões para trabalhos

futuros.

20

_______________________________________ 2 PROBLEMAS DE ROTEIRIZAÇÃO DE VEÍCULOS

Christofides (1985) considera o problema de distribuição como sendo aquele

em que os veículos, localizados em um depósito central são requisitados para visitar

clientes geograficamente dispersos, para cumprir suas exigências. Este problema

aparece em um grande número de situações práticas, relativas à distribuição de

mercadorias e é conhecido pelo nome genérico de Problema de Roteirização de

Veículos (PRV). O PRV é também conhecido na literatura como programação de

veículos (Clark & Wright, 1964; Gaskell, 1967), despacho de caminhões (Dantiz &

Ramser, 1959; Christofides & Eilon, 1969; Krolak et al. 1972), ou simplesmente

problemas de entrega (Hays, 1967). Freqüentemente, eles aparecem também em

situações que não estão relacionadas com a entrega de mercadorias. Por exemplo,

a coleta de cartas em caixas de correio, roteirização para serviços de atendimento

médico domiciliar, roteirização de carteiros, etc.

O PRV básico roteiriza os veículos (uma rota por veículo, começando e

terminando no mesmo depósito), de forma que todos os clientes são atendidos em

suas demandas e o custo total de viagem é minimizado.

Uma formulação de programação matemática para o problema de roteamento

de veículos foi dada por Bodin et al. (1983). A formulação considera o depósito como

o nó 0 e os clientes são numerados de 1 a n (Fig. 2.1).

As restrições 2.2 e 2.3 asseguram que cada cliente é servido exatamente uma

vez. A continuidade da rota é garantida pela restrição 2.4, aonde se um veículo

chega no ponto de entrega deve também partir daquele ponto. A restrição 2.5 é a

restrição da capacidade do veículo. A restrição 2.6 limita o máximo comprimento da

rota. As restrições 2.7 e 2.8 asseguram que cada veículo é usado não mais do que

uma vez.

21

vji t

vi

vQq

jix

vjic

kn

kjix

kvx

kvx

kvTxtx

kvQxq

npxx

nix

njx

xc

vij

vij

vij

n

i

vi

n

j

vj

n

j

n

i

n

jv

vij

vij

k

v

vij

vi

n

jv

n

i

vijj

n

i

n

j

vpj

vip

n

j

k

v

vij

n

i

k

v

vij

n

i

n

j

k

v

vij

vi

veículoo para nó o para nó do viagemde tempo

veículoo para cliente do mentodescarrega de tempo

veículodo capacidade cliente; do pedido do tamanho

contrário caso 0, nó ao nó do viaja veículoo se 1,

veículoo para nó ao nó do viagemde custo

veículosde Número clientes; de número :Onde

(2.9) ,, }1,0{

(2.8) ,...,1 1

(2.7) ,...,1 1

(2.6) ,...,1

(2.5) ,...,1

(2.4) ,...,1 0

(2.3) ,...,1 1

(2.2) ,...,1 1

a Sujeito

(2.1) Minimize

vij

vi

vi

10

10

1 0 01

0 0

0 0

0 1

0 1

0 0 0

=

=

==

=

===

∀∈

=≤

=≤

=≤+

=≤

==−

==

==

∑

∑

∑ ∑ ∑∑

∑ ∑

∑ ∑

∑ ∑

∑ ∑

∑ ∑ ∑

=

=

= = ==

= =

= =

= =

= =

= = =

δ

δ

Fig. 2.1 – Problema básico de Roteamento de Veículos.

2.1 EXTENSÕES DO PROBLEMA DE ROTEAMENTO DE VEÍCULOS

O problema básico de roteirização ignora um grande número e variedade de

restrições adicionais e de extensões que são freqüentemente encontradas em

22

problemas ou situações reais. Algumas destas restrições e extensões são listadas

em Chistofides et al. (1982):

- O PRV básico não permite que um cliente seja servido por mais de um

veículo. Podemos relaxar esta restrição permitindo que o cliente seja servido

por mais de um veículo, se isto beneficia o custo total (no caso distância), isto

pode ocorrer se a demanda do cliente estiver próxima da capacidade do

veículo, essa variação é conhecida como roteamento de veículos com divisão

de entregas (PRVDE).

- Cada cliente deve ser visitado durante seu horário de funcionamento ou em

um determinado período compreendido em uma janela de tempo. Esse

problema é conhecido como problema de roteamento de veículos com janela

de tempo (PRVJT).

- O problema pode envolver tanto entregas como coletas de clientes.

Adicionalmente, é possível misturar entregas e coletas em uma única rota ou

alternativamente, pode ser exigido que o veículo execute primeiro todas as

entregas na rota antes das coletas. Este último caso é conhecido como

backhauling.

- O tempo consumido para realizar a atividade também deve ser considerado.

Isto inclui: tempo de descarga (ou tempo de carregamento, no caso de

coletas) em cada cliente; tempo de carregamento do veículo no depósito e por

último o tempo de deslocamento entre os clientes, considerando a velocidade

média em cada trecho de via.

Por outro lado, existem algumas considerações práticas que também ocorrem

freqüentemente e que não se ajustam adequadamente dentro da formulação básica

para o PRV. Podem-se citar algumas:

- Múltiplos Depósitos: empresas com mais de um depósito, onde estes

operam de forma dependente, ou seja, o veículo pode sair de um depósito e

depois de visitar os clientes retorna a outro depósito, podendo ser carregado

23

novamente e continuar em uma viagem subseqüente. Neste caso, os

depósitos não podem ser considerados isoladamente. Quando o depósito é

autônomo, ou seja, cada um tem sua própria frota de veículos e sua própria

área de cobertura geográfica para atendimento dos clientes, o problema deve

ser simplificado em vários problemas similares de roteirização de veículos

com um único depósito.

- Nível de Serviço ao Consumidor: o nível de serviço é medido pelo período

de tempo durante o qual as exigências dos clientes são cumpridas. Como os

clientes e seus pedidos consistem em um processo dinâmico e não periódico,

qualquer tentativa para definir o problema de roteirização de veículos para um

dado período deve ser uma aproximação ou uma arbitrariedade imposta. Uma

forma alternativa para definir um período para atender os clientes é alocar

uma prioridade, ou nível de serviço, para cada cliente.

- Múltiplas Mercadorias: em alguns problemas de roteirização, os veículos

são compartimentados de forma que diferentes mercadorias são

armazenadas em compartimentos segregados. Cada cliente pode requerer

quantidades específicas de diferentes tipos de mercadorias. Tais problemas

aparecem na distribuição de combustível, alimentos (congelados ou não),

etc., e envolvem – além do problema de roteirização de veículos – aspectos

do problema da mochila (Reeves, 1993).

2.2 CLASSIFICAÇÃO DOS PROBLEMAS DE ROTEIRIZAÇÃO DE VEÍCULOS

Encontram-se na literatura vários esquemas para classificação dos problemas

de roteirização de veículos. Bodin et al. (1983) propõem uma estrutura que classifica

os problemas em função de suas restrições de aspectos espaciais e/ou temporais.

Assad (1988) alega que a maior dificuldade em encontrar um esquema de

classificação apropriada para problemas de roteirização, está em o que tomar como

base para classificá-los: os requisitos do problema ou a técnica de solução proposta.

O autor sugere que cada problema prático seja caracterizado particularmente, de

24

acordo com um conjunto de elementos por ele listado. Outra possível classificação

baseia-se no tempo em que as informações das demandas estão disponíveis. Nos

problemas clássicos de roteirização, assume-se que a demanda é conhecida

antecipadamente (demanda determinística). Na roteirização dinâmica, a demanda é

estocástica, ou seja, ocorre em tempo real e é inserida no roteamento em

andamento.

Desrochers et al. (1990) propuseram um esquema muito elegante, que além

de servir para classificar uma grande variedade de problemas de roteirização de

veículos, dá suporte ao desenvolvimento de modelos para sistemas dessa área. A

idéia é dar diretrizes para uma representação teórica do problema real, servindo

como base para o desenvolvimento de modelos e sistemas, possibilitando uma

escolha apropriada do algoritmo que irá tratá-lo.

Tal esquema manipula informações em três diferentes níveis. No primeiro

nível, está o problema situado na vida real. Ele pode conter muitos aspectos que não

são relevantes para a seleção de um método de solução. No segundo nível está o

problema tipo teórico, obtido do problema situado na vida real por determinação e

modelagem das entidades relevantes que são descritas em termos de decisões,

objetivos e restrições. No terceiro nível estão os algoritmos de solução.

Inicialmente, é proposta uma linguagem para definir o problema teórico em

roteirização de veículos. A linguagem proposta faz uso de quatro campos.

O primeiro campo descreve as características e restrições que são relevantes

somente para um único endereço (clientes e depósitos). É preferido o termo

“endereço” a “clientes” devido à grande variedade de tipos de clientes: os usuais

clientes de um único endereço; clientes correspondentes a um par origem-destino;

ou clientes que são definidos como sendo todos os endereços localizados em um

segmento de logradouro.

O segundo campo especifica as características relevantes somente para um

único veículo. O terceiro campo contém todas as características do problema que

25

não podem ser identificadas com os endereços ou veículos. O quarto campo define

uma ou mais funções objetivo.

O quinto campo pode ser usado para descrever informações adicionais sobre

uma instância específica da classe do problema. Embora essas informações não

façam parte do modelo definido pelos quatro campos, elas podem ser úteis para a

seleção de um algoritmo adequado.

O esquema de classificação é projetado para descrever o problema real em

uma forma padrão, de maneira que exista uma correspondência entre as

características do problema real e os componentes do esquema.

Todos os elementos na definição do problema são, em princípio,

unidimensionais. No entanto, um sobrescrito pode ser adicionado para indicar

restrições multidimensionais. Por exemplo, capi indica que a capacidade do veículo é

limitada em uma dimensão, que pode ser, por exemplo, peso ou volume; capi2 indica

restrição de capacidade em duas dimensões, que pode significar que os limites tanto

de peso e de volume estão sendo levados em conta.

A linguagem de classificação consiste em um conjunto de regras que definem

uma estrutura permissível. Cada regra define um símbolo não terminal em termos de

outro símbolo não terminal (campo, subcampo e elementos) e símbolo terminal

(valor dos elementos ou sinais); o símbolo V é usado para representar a disjunção,

“ou”. Cada símbolo não terminal é colocado entre colchetes angulares. O símbolo q é usado para indicar um valor padrão, que geralmente é o valor mais freqüente.

Para uma notação conveniente, dois símbolos sucessivos são separados por

uma barra vertical se eles pertencerem a campos diferentes e por uma vírgula se

pertencerem ao mesmo campo. Assim, o esquema de classificação segue com a

seguinte estrutura:

26

::=

2.2.1 Endereços

O primeiro campo define as características que podem ser associadas a um

único endereço. Os endereços deverão estar localizados sobre uma rede (grafo)

com um conjunto V de nós e conjunto E de arestas. Este campo é composto de

quatro subcampos.

O primeiro subcampo especifica o número de depósitos. Existem problemas

de um único depósito e problemas onde o número de depósitos é dado como parte

da instância do problema.

O segundo subcampo especifica o tipo de demanda. Existem três partes. A

primeira corresponde à localização da demanda : ° indica que o cliente está

localizado sobre o nó, ARESTA indica que o cliente está localizado nos arcos da

rede, MISTO indica que os clientes estão localizados tanto nos nós como nos arcos,

e TAREFA indica que cada cliente está associado a um par origem-destino; a carga

é recolhida em um endereço de origem e entregue em um endereço destino. A

segunda parte deste subcampo especifica se todas as demandas são do mesmo

tipo (só entregas ou só coletas) ou não (mistura de entregas e coletas). A terceira

parte especifica a natureza da demanda: determinística ou dinâmica.

O terceiro subcampo especifica restrições de programação dos endereços,

isto é, os aspectos temporais da demanda. Podem não existir restrições temporais,

ou o horário de entrega é fixo (programação fixa), ou é restrito por um único intervalo

de entrega (janela de tempo única), ou por um conjunto de intervalos (janela de

tempo múltipla)

27

O último subcampo especifica a restrição de seleção dos endereços. Existem

três subclasses: todos os endereços devem ser visitados; um dado subconjunto de

endereços deve ser visitado e os outros serão visitados se for vantajoso; ou os

endereços são particionados em subconjuntos e pelo menos um endereço em cada

subconjunto deve ser visitado.

::=

::= 1 V l

1 [um depósito]

l [especificado como parte da instância do problema]

::=

::= ° V Aresta V Misto V Tarefa

° [roteirização dos nós]

Aresta [roteirização dos arcos]

Misto [roteirização mista (nós e arcos)]

Tarefa [roteirização tarefa]

::= ° V ±

° [só entregas ou só coletas]

± [mistura entrega e coletas]

::= ° V ~

° [demanda determinística]

~ [demanda estocástica]

::= ° V pf j V jtj V jmj

° [sem restrição de horário]

pfj [programação fixa]

28

jtj [janela de tempo fixa]

jmj [janela de tempo múltipla]

::= ° V subconjunto V escolha V período

° [planejamento simples; todos endereços devem ser visitados]

subconjunto [planejamento simples; subconjunto de endereços deve ser

visitado e os outros serão visitados se for vantajoso]

escolha [planejamento simples; pelo menos um endereço de cada

subconjunto particionado deve ser visitado]

período [planejamento construído para um dado período de tempo]

2.2.2 Veículos

O segundo campo define as características do veículo em suas rotas. Há três

tipos de informações neste campo: o número de veículos, a característica física do

veículo, e as restrições temporais sobre uma rota.

O primeiro subcampo especifica o número de veículos: o número de veículos

é uma constante, especificado como parte de um tipo de problema, ou uma variável,

especificado como parte da instância do problema. O símbolo “=” pode ser usado

para indicar que todos os veículos devem ser utilizados.

O segundo e terceiro subcampos especificam as características físicas do

veículo: a capacidade e a presença de compartimentos. A frota pode ser homogênea

(todos os veículos têm a mesma capacidade) ou heterogênea. Alguns têm

compartimentos especiais, usados para armazenar tipos específicos de mercadorias:

por exemplo, comidas congeladas e vegetais frescos devem ser colocadas em

compartimentos especiais separados.

O quarto e quinto subcampos especificam restrições temporais. É onde

podem ser encontrados os intervalos de disponibilidade dos veículos e os limites

inferiores e superiores na duração da rota.

29

::=

::=

::= ° V =

° [no máximo β1 veículos podem ser utilizados]

= [todos os β1 veículos devem ser utilizados]

::= ° V cap V capi

° [nenhuma restrição de capacidade]

cap [veículos com capacidades idênticas]

capi [veículos com diferentes capacidades]

::= ° V esp

° [sem divisões de compartimentos]

esp [veículos com compartimentos especiais]

::= ° V jt V jti

° [nenhuma restrição de horário]

jt [limites de duração das rotas idênticos]

jti [limite de duração das rotas varia]

::= ° V dur V duri

° [não há restrições de tempo de duração das rotas]

dur [limites iguais de tempo de duração das rotas]

duri [diferentes limites de tempo de duração das rotas]

30

2.2.3 Características do Problema

O terceiro campo define o tipo de rede utilizada, a estratégia de serviços, e

as restrições nas relações entre os endereços e os veículos.

O primeiro subcampo especifica as propriedades da rede (direcionada, não

direcionada ou mista). O segundo subcampo especifica a estratégia de serviço

adotada. Há quatro tipos de estratégias de decisão:

- O primeiro tipo permite ou não a quebra de demanda. A quebra de demanda

ocorre quando é decidido, a princípio, que a demanda deve ser satisfeita

por mais de uma visita ao cliente.

- No caso de roteirização de nós que envolve coletas e entregas, pode-se

escolher backhauling, isto é, as entregas são realizadas primeiro para

esvaziar o veículo e depois realizam-se as coletas no caminho de volta para

o depósito.

- Na maioria dos casos um veículo realiza no máximo uma rota por período,

mas é possível permitir mais que uma rota por veículo.

- Geralmente os veículos são restringidos a começar e terminar no mesmo

depósito, mas isto pode ser relaxado de forma a permitir rotas multi-

depósitos.

Os outros subcampos especificam possíveis relações entre dois endereços,

entre um endereço e um veículo, ou entre dois veículos. Tais relações são causadas

por um número de diferentes fatores. A mais conhecida destas relações é a restrição

de precedência entre dois clientes: o veículo deve visitar um cliente antes de visitar o

outro. Note que este requisito de precedência não tem nada a ver com a restrição

implícita de precedência na roteirização de um par origem-destino.

A maioria das outras relações são restrições de inclusão e exclusão. Pode ser

que um endereço deva ser visitado por um veículo partindo de determinado

31

depósito, deva ser alocado em uma mesma rota que outro endereço específico, ou

deva ser visitado por um veículo específico. Por exemplo, uma restrição de endereço

veículo ocorre se o veículo deve ser equipado com um dispositivo de

descarregamento porque o cliente não possui uma doca para descarregar a

mercadoria. Pode ser também, que um endereço não possa ser atendido por um

determinado depósito, ou não deva ser alocado na mesma rota que outro endereço,

ou não deva ser visitado por um determinado veículo.

O último tipo de restrição é a sincronização dos veículos, que ocorre quando

dois ou mais veículos devem trocar cargas ou assistir um ao outro.

::=

::= ° V dir V mix

° [rede não direcionada]

dir [rede direcionada]

mix [rede direcionada e não direcionada]

::=

::= ° V / V ÷

° [não é permitida a quebra de demanda]

/ [permitida a quebra de demanda no princípio]

÷ [permitida a quebra de demanda no final]

::= ° V back

° [nenhuma restrição de backhauls]

back [backhauls, no caso de roteirização em nós]

::= ° V ≥1R/r

32

° [no máximo uma rota por veículo]

≥1R/r [permite mais de uma rota por veículo]

::= ° V ≥1D/r

° [uma rota começa e termina no mesmo depósito]

≥1D/r [permite rotas multi-depósitos]

::=

::= ° V prec

° [sem restrição de precedência]

prec [com restrição de precedência]

::= ° V DE

° [sem restrição depósito-endereço]

DE [com restrição depósito endereço]

::= ° V EE

° [sem restrição endereço-endereço]

EE [com restrição endereço-endereço]

::=

::= ° V DV

° [sem restrição depósito-veículo]

DV [com restrição depósito veículo]

::= ° V EV

° [sem restrição endereço-veículo]

EV [com restrição endereço-veículo]

::= ° V VV

° [sem restrição veículo-veículo]

VV [sincronização necessária entre veículos]

33

2.2.4 Objetivos

O quarto campo define as funções objetivo. Para especificá-la são

introduzidos cinco elementos quantitativos.

O tempo de viagem e de atendimento do veículo i, isto é, a duração da rota

deste veículo será denotada por Ti.

Para ser capaz de expressar funções objetivo mais realistas, é introduzida

uma função custo do veículo Ci, uma função custo do endereço Cj, uma função

penalidade do endereço Pj. Uma função custo do veículo pode ser usada para

modelar situações onde, adicionada a roteirização, é requisitada também a

determinação do tamanho e tipo de frota. Uma função custo no endereço leva em

consideração o custo incorrido ao divergir do nível de serviço pretendido. As funções

penalidades permitem modelar os custos incorridos com a violação de restrições

flexíveis. Há restrições que podem ser violadas até um certo custo; horas extras de

motoristas são um exemplo. As restrições que são consideradas flexíveis são

listadas como argumentos das funções penalidades do veículo e endereço.

Na prática os problemas têm uma função objetivo composta. O usuário pode

especificá-la pela listagem dos componentes da função objetivo em ordem

decrescente de importância.

Nas regras seguintes, nota-se que, no caso de um único veículo, os

operadores sum e max são retirados dos objetivos relacionados à rota e ao veículo.

::=

::= sum V max

sum [minimizar a soma do valor da função custo]

max [minimizar o valor da função custo máximo]

::= Ti V Ci V Pi () V Cj V Pj ()

34

Ti [duração da rota]

Ci [custo do veículo]

Pi [penalidade do veículo]

Cj [custo do endereço]

Pj [penalidade do endereço]

2.3 ESTRATÉGIAS E MÉTODOS DE SOLUÇÕES

Bodin et al. (1983) classificam as estratégias de solução para os problemas

de roteirização de veículos da seguinte forma:

1) Agrupa – Roteiriza (cluster first – route second): consiste no procedimento de

agrupar os nós ou arcos de demanda primeiro, e depois construir rotas

econômicas para cada agrupamento. Exemplos destas idéias são aplicadas nos

trabalhos de Gillett e Miller (1974), Gillett e Johnson (1976), Chapleau et al.

(1981) e Karp (1977) para o problema básico de roteirização de veículos.

2) Roteiriza - Agrupa (route first - cluster second): primeiro, uma grande (geralmente

inviável) rota ou ciclo é construída incluindo todas as entidades de demanda (nós

e/ou arcos). Posteriormente esta grande rota é dividida em um número menor de

rotas viáveis. Golden et al. (1982) desenvolveram um algoritmo que utiliza esse

conceito para o problema de roteirização com frota heterogênea de veículos.

Newton e Thomas (1969) e Bodin e Berman (1979) utilizaram esta estratégia para

roteirização de ônibus escolares, considerando uma única escola. Bodin e Kush

(1978), utilizaram esta estratégia para o problema de varrição de ruas.

3) Economias ou Inserções: A lógica do método é começar com um veículo-modelo

que serve a cada ponto de entrega e que retorna ao depósito. Em seguida, duas

paradas são combinadas na mesma rota de modo que um veículo possa ser

eliminado e a distância de viagem reduzida. Para determinar quais paradas

combinar em uma rota, a distância economizada é calculada antes e depois da

combinação. O processo é iterativo continua até que todas as paradas sejam

consideradas. Exemplos de procedimentos de economia / inserção são descritas

35

por Clarke e Wright (1964), Golden et al. (1977), Norback e Love (1979), e Golden

e Wong (1981). Hinson e Mulherkar (1975) usaram uma variação deste

procedimento para roteirização de aviões.

4) Melhoria - Troca: procedimento heurístico também conhecido como troca de arcos

ou arestas onde em cada etapa uma solução viável é alterada, resultando em

outra solução com custo menor. Este processo continua até que não sejam mais

possíveis reduções adicionais no custo. Procedimentos de troca são também

conhecidos como procedimentos r-opt, onde r é o número de arcos ou arestas

trocadas a cada iteração. Em um algoritmo r-opt, todos os r arcos são testados

até não existir nenhuma troca viável que melhore a solução. O número de

operações necessárias para testar todas as r trocas cresce rapidamente com o

aumento do número de pontos de entrega. Assim, valores de r=2 (2-opt) e r=3 (3-

opt) são os mais usados. Bodin e Sexton (1979), modificaram este método para

programação de microônibus no problema dial a ride (programa de transporte

público pré-agendado por telefone).

5) Programação matemática: inclui algoritmos que são diretamente baseados em

uma formulação de programação matemática de problemas de roteirização de

veículos. Maiores detalhes podem ser encontrados em Magnanti (1981). Esse

método é bastante limitado devido ao problema ser NP-Hard. Podem-se citar

alguns casos de sucesso utilizando branch and bound e programação dinâmica,

como em Christofides et al. (1981)

Laporte (1992), Christofides (1985) e Osman (1993) classificaram os métodos

de soluções em algoritmos exatos e heurísticos, enquanto Cunha (1997) propôs a

classificação dos métodos de solução nas seguintes categorias, que serão

discutidas na seqüência deste capítulo:

- Métodos exatos, que garantem a solução ótima.

- Métodos heurísticos (tradicionais), que não garantem a solução ótima, mas

geralmente resultam em soluções sub-ótimas de grande qualidade a um

esforço computacional menor.

36

- Métodos emergentes, que reúnem as técnicas mais recentes, baseadas em

sistemas especialistas ou baseados em metaheurísticas do tipo busca

tabu, algoritmos genéticos, VNS, GRASP, etc.

2.3.1 Algoritmos Exatos

Como uma generalização do problema do caixeiro viajante, o problema de

roteirização de veículos pertence à classe dos NP-hard, e algoritmos determinísticos

de tempo polinomial para achar a solução ótima são improváveis de existir. Por isso,

pouca atenção tem sido dada à busca de soluções ótimas (Osman, 1993).

Christofides (1985) apresenta três formulações que têm sido utilizadas como

base para os métodos de soluções dos PRV. Duas destas formulações consistem

em programação inteira, enquanto a terceira para programação dinâmica. Fisher e

Jaikumar (1978) utilizaram a formulação para programação inteira do PRV básico na

construção de um algoritmo de otimização baseado na decomposição de Bender,

além de utilizar técnicas de branch and bound e relaxação lagrangiana.

Christofides et. al. (1981) definiram o problema de roteirização de veículos,

adaptando o problema de particionamento de conjunto (set covering ou partitionig

problems) com uma restrição a mais, através de uma formulação para programação

inteira. Em uma outra tentativa, os autores utilizaram a formulação de programação

dinâmica do PRV básico e técnicas de relaxação lagrangiana (space relaxation) para

calcular o limite usado no algoritmo de branch and bound para o PRV.

2.3.2 Métodos Heurísticos

Reeves (1993) define heurística como uma técnica de busca boas (isto é,

perto da ótima) soluções, com um custo computacional razoável, sem garantir

soluções ótimas, e em muitos casos não é capaz de declarar o quão próximo uma

solução está do ótimo.

37

Além da teoria da complexidade computacional representar uma forte

justificativa para a utilização de métodos heurísticos na solução do PRV, outro forte

argumento apresentado pelo autor corresponde à possibilidade de modelar o

problema real com maior precisão, uma vez que as heurísticas são mais flexíveis e

aptas a operar com funções objetivos e/ou restrições mais complicadas (e mais

próximas de situações reais) do que os algoritmos exatos. Colocando isto de uma

outra forma, o que traz mais benefícios: uma solução exata de um modelo

aproximado ou uma solução aproximada de um modelo exato?

Christofides (1985) classifica as heurísticas para roteirização de veículos nas

seguintes categorias:

- Métodos construtivos;

- Método das duas fases;

- Método de otimização incompleta.

Os métodos construtivos ainda podem se diferenciar de acordo com a

maneira como a rota é construída (seqüencial ou paralela) e o critério utilizado para

expandir a rota.

O método construtivo mais utilizado consiste no método da economia (ou

inserção) de Clarke e Wright (1964). Este método inicia com uma solução inviável

em que cada cliente é atendido por um veículo e procede da seguinte forma:

Passo 1: calcula-se a economia sij para todos os pares de clientes i e j. A economia

é dada pela seguinte fórmula sij = c1i – cij + c1j.

Passo 2: Ordenar as economias em ordem decrescente.

Passo 3: iniciando do topo da lista, fazer:

Versão Paralela

Passo 4: se ao incluir o link (i, j) na rota, resultar em uma rota viável de acordo com

as restrições do PRV a ser resolvido, então anexar este link à solução; se não,

rejeitar o link.

38

Passo 5: tentar com o próximo link da lista e repetir o passo 4 até que todos os links

já tenham sido investigados.

Versão Seqüencial

Passo 4: buscar o primeiro link viável da lista, que pode ser usado para estender um

dos extremos da rota em construção.

Passo 5: se a rota não pode ser mais estendida, terminar a rota. Escolher o primeiro

link factível na lista para começar uma nova rota.

Passo 6: repetir os passos 4 e 5 até que nenhum link possa ser escolhido.

Muitas modificações têm sido propostas para o método de Clarke e Wright

(1964), buscando diferentes resultados. Gaskel (1967) e Yellow (1970) introduziram

um novo conceito de economia dado por sij - θ cij, onde θ é um parâmetro escalar.

Variando o valor do parâmetro θ, é possível dar maior o menor ênfase aos custos de

viagem entre dois nós, dependendo da sua posição relativa ao depósito. Este

parâmetro pode ser alterado, obtendo-se diferentes soluções.

Golden et. al. (1977) reduziram substancialmente o tempo de processamento

da heurística de Clarke e Wright, utilizando técnicas de estrutura de dados. Outras

heurísticas de construção podem ser encontradas em Mole e Jameson (1976),

Nelson et al. (1985), Paessens (1988), Altikemer e Gavish (1991).

Desrochers e Verhoog (1990) apresentam uma nova heurística de construção

para o PRV com frota homogênea, baseada em sucessivas fusões de rotas. A cada

iteração, a melhor fusão é selecionada através do algoritmo MBSA (Matching Based

Saving Algorithm). Este critério pode ser considerado menos míope do que as usuais

heurísticas de construção.

O método das duas-fases é baseado em métodos do tipo agrupa-roteiriza ou

roteiriza-agrupa. O método agrupa-roteiriza identifica antes o conjunto de clientes

que será designado para cada veículo e então é computado o custo mínimo do

problema do caixeiro viajante para a rota de cada veículo.

39

Gillet e Miller (1974), através da técnica agrupa-roteiriza, utilizaram um

algoritmo de “varredura” para a fase 1 em que a localização dos clientes é

representada em um sistema de coordenadas polares com a origem do depósito

central. Um cliente é escolhido de forma aleatória e o raio da origem do cliente é

“varrido” no sentido horário ou anti-horário. Os clientes são designados aos veículos,

no decorrer da “varredura”, até atingir a restrição de capacidade. Depois um novo

veículo é selecionado e a varredura continua até que a capacidade do novo veículo

seja atingida e assim continua até que a capacidade do novo veículo seja atingida e

assim continua até que todos os clientes tenham sido “varridos” para um dado

veículo.

Outras heurísticas que utilizam o método agrupa-roteiriza podem ser

encontradas em Christofides et al. (1979) e Fisher e Jaikumar (1981). Neste último, a

fase de agrupamento é resolvida otimamente através da utilização de um algoritmo

rápido para o problema de designação generalizada (Fisher et al., 1979).

O método roteiriza-agrupa constrói uma rota ótima para o problema do

caixeiro viajante e depois particiona em rotas viáveis para o PRV (Beasley, 1983;

Haimovich e Rinnooy Kan, 1985).

Um exemplo de heurística baseada em otimização incompleta é encontrado

em Christofides et al. (1978). Este consiste essencialmente em um algoritmo branch

and bound, transformado em uma heurística através de finalização prematura.

Segundo Fisher e Jaikumar (1981), as heurísticas que vêm sendo

desenvolvidas para o PRV são modificações de heurísticas para o problema do

caixeiro viajante. Assim como Osman (1993), eles classificam estas heurísticas de

maneira similar a Christofides (1985), no entanto, apontam mais uma categoria:

métodos de melhorias.

A maioria dos métodos de melhorias envolve a aplicação sucessiva de dois

módulos: um método de construção, que produz uma solução viável inicial S de

custo total C(S); e uma técnica de melhoria iterativa que mantém a viabilidade e

diminui gradativamente o custo da rota. Esta última envolve três conceitos

40

fundamentais: um mecanismo de geração para alterar a solução inicial; estratégias

de seleção das soluções alternativas e um critério de parada. Nestas heurísticas

uma dada solução é melhorada através de sucessivos procedimentos iterativos de

troca de arestas. Procedimentos de troca para o PRV foram sugeridos por

Christofides e Eilon (1969) e Russell (1977). Stewart e Golden (1984) usaram

relaxação lagrangiana para transformar o múltiplo problema do caixeiro viajante em

PRV e depois aplicaram procedimento de troca de arcos similar a Lin e Kernighan

(1973).

Metaheurísticas, tais como busca tabu, algoritmos genéticos e simulated

annealing, podem ser vistas como métodos de melhorias (Gendrau et al., 1994),

embora alguns autores as reconheçam como uma categoria diferente dos métodos

heurísticos tradicionais (Cunha, 1997; Souza, 1993).

Vários procedimentos eficientes de busca têm sido elaborados. Em especial,

pesquisadores adaptaram idéias de outras áreas no desenvolvimento de

metaheurísticas, ou técnicas que, superpondo-se a métodos heurísticos, guiam a

busca vista à superação da otimalidade local e à obtenção de soluções de melhor

qualidade. As mais promissoras destas técnicas, na área de roteirização, incluem

simulated annealing (SA), algoritmos genéticos (AG), e busca tabu (BT).

Simulated annealing, proposta por Kirkpatrick et al. (1983), parte de conceitos

de mecânica estatística, e é baseada em uma analogia com o processo de

recozimento de sólidos. A cura física refere-se ao processo de obtenção de estados

de baixa energia de um sólido onde, a partir da substância derretida, passa-se a

diminuir lentamente a temperatura, até atingir a do ponto de congelamento. Se o

resfriamento for feito de forma lenta e apropriada, a configuração de mínima energia

do sólido terá uma estrutura particular, como a observada em cristais. Caso

contrário, o sólido resultante ficará congelado em uma estrutura localmente ótima, tal

como um vidro ou um cristal com vários defeitos em sua estrutura.

Em analogia com problemas de otimização combinatória, os diferentes

estados da substância correspondem as diferentes soluções viáveis do problema, e

a energia do sistema, à função a ser minimizada. SA explora o espaço de soluções

41

através da geração seqüencial e aleatória de soluções candidatas. O mecanismo de

geração geralmente consiste de uma prescrição simples para gerar a transição de

uma solução a outra através de uma pequena perturbação.

As soluções que implicam na melhoria da função objetivo são aceitas

incondicionalmente. Caso contrário, aplica-se um critério de aceitação estocástico. A

probabilidade de aceitação da solução depende não só do valor da deterioração da

função objetivo resultante, mas de um parâmetro T. O valor de T é gradualmente

reduzido ao longo do processo e desempenha o mesmo papel que a temperatura

em um sistema termodinâmico. Para altos valores de T, as configurações são

equiprováveis e o algoritmo pode visitar praticamente qualquer uma delas. Com o

decrescimento de T, reduz-se à probabilidade de aceitação de soluções

deteriorantes (e portanto, o número de soluções acessíveis) até o momento em que

o algoritmo atinge uma solução de baixo custo.

Simulated annealing assegura que a probabilidade da solução piorar tende a

zero com o crescimento do número de iterações. Este método foi aplicado ao PRV

por Osman (1993).

Algoritmos genéticos, introduzidos por Holland (1975), procuram emular o

fenômeno biológico da reprodução evolutiva. Ao contrário das outras

metaheurísticas que exploram o espaço de soluções seqüencialmente, estes

algoritmos trabalham com populações de soluções, guiando a busca usando o

“princípio da sobrevivência das mais aptas” (soluções de melhor qualidade). A

aptidão (fitness) de cada solução é medida por uma função equivalente a função

objetivo, e a busca prossegue por uma número de gerações onde a contribuição de

cada indivíduo para a próxima geração é proporcional à sua aptidão. Isto é obtido

selecionando-se indivíduos aleatoriamente e usando uma função de probabilidade

ponderada, onde os pesos refletem os valores reais de aptidão. Três operadores

padrões são utilizados: reprodução, “crossover” (cruzamento) e mutação. A

reprodução copia um indivíduo de uma geração para a próxima, cruzamento

combina características de dois ou mais pais para produzir um ou mais filhos, e

mutação realiza pequenas mudanças locais. Reprodução e cruzamento de

indivíduos aptos são os mecanismos que impulsionam o melhoramento da função

42

objetivo, enquanto a mutação mantém a diversidade da mutação e permite a

exploração de novas regiões.

Os algoritmos genéticos são limitados na solução do problema de roteamento

de veículos, visto que, apesar dos bons resultados alcançados, o tempo

computacional é muito elevado. Pode-se destacar o trabalho de Drummond et al.

(2001) que utiliza um algoritmo genético paralelizado na solução do problema.

A busca tabu pode ser considerada uma técnica que incorpora conceitos

selecionados de inteligência artificial (Glover, 1989; Glover, 1990). Seu objetivo é de

emular usos inteligentes de memória com o objetivo de cruzar as fronteiras dos

mínimos locais.

A BT utiliza três componentes: construção de uma solução viável,

normalmente feita por uma outra heurística, geração de lista tabu (movimentos

proibidos) e critérios de aspiração. A lista tabu tem como objetivo evitar a formação

de ciclos e fugir de ótimos locais, se esta lista for muito grande pode tornar inviável,

na prática, sua utilização. Os critérios de aspiração são instrumentos que permitem

em algumas circunstâncias, retirar o status tabu de um determinado movimento,

incluído na lista tabu.

Uma das primeiras tentativas em aplicar busca tabu em PRV foi feita por

Willard (1989). Em seu trabalho, o problema foi primeiro transformado em um

problema do caixeiro viajante com a reprodução do depósito, e a busca foi

restringida a soluções vizinhas que podem ser obtidas por meio de trocas 2-opt (Lin,

1965) ou 3-opt (Lin e Kernighan, 1973), satisfazendo as restrições do PRV.

Na heurística desenvolvida por Semet e Taillard (1993) para solucionar um

PRV real contendo várias restrições, o movimento tabu básico consiste em mudar

uma cidade de sua rota para uma outra.

Em Pureza e França (1991), a busca procede de uma solução para a

próxima, trocando e inserindo vértices entre duas rotas e realizando movimentos 2-

43

opt em cada um. Osman (1993) usa uma combinação de movimentos 2-opt,

reindicação de vértices para diferentes rotas, e troca de vértices entre duas rotas.

Uma nova abordagem foi introduzida por Taillard (1993), na qual o conjunto

de vértices é decomposto em subproblemas que podem ser resolvidos

independentemente, conseguindo maior velocidade no método de busca iterativa.

Resultados indicam que este método tem melhor desempenho do que os outros. Na

realidade, dois diferentes esquemas de decomposição foram propostos: um para

problemas uniformes e outro para problemas não uniformes. A decomposição em

regiões polares mostrou apresentar melhor performance no caso de problemas

uniformes, onde o depósito está quase no centro e os vértices se encontram

uniformemente distribuídos ao seu redor. Depois de uma pré-resolução dos

subproblemas, vértices e rotas são trocados entre subproblemas. Um método de

decomposição baseado na arborescência do caminho mínimo partindo do depósito

para todos os vértices é recomendado para problemas não uniformes, onde os

vértices não estão regularmente distribuídos ao redor do depósito. Neste algoritmo

vértices e rotas não são transferidos entre as soluções.

Em todos estes algoritmos, não é permitido que uma solução viável venha a

ficar inviável, enquanto em Gendreau et al. (1994) são permitidos movimentos que

resultam em soluções inviáveis quando são consideradas as restrições de

comprimento da rota e capacidade do veículo.

Barbarosoglu e Ozgur (1999) desenvolveram um algoritmo que usa a maioria

dos princípios de busca tabu aplicados por Taillard (1993), mas propõem um novo

procedimento de busca local sem qualquer diversificação e um novo esquema de

intensificação. A intensificação da busca começa em soluções que se suspeita estar

no limite da região de ótimo local ou na região do ótimo global. Durante o estágio de

melhoria da solução, o comportamento da função objetivo é avaliado, e as soluções

que pioram depois de uma série de melhorias são guardadas como um indicador de

início de um vale em potencial ao redor do mínimo global. A intensificação é

executada ao redor destas soluções para explorar estas regiões. Os autores

decidiram não colocar mecanismos de diversificação para diminuir os custos

computacionais.

44

Kelly e Xu (1999) desenvolveram uma heurística de busca tabu genérica para

o PRV. Esta heurística consiste de duas etapas, na primeira das quais utiliza-se uma

heurística simples para gerar um número suficiente de rotas distintas. Depois, na

segunda fase, são identificadas as “boas” soluções, que são melhoradas usando um

algoritmo de particionamento de números. Dado que este algoritmo é NP-hard, foi

desenvolvida uma heurística de busca tabu para resolvê-lo de forma aproximada.

Adicionalmente, novas rotas são criadas, combinando de forma inteligente rotas

obtidas por técnicas de busca local. O método de busca local envolve o uso do

algoritmo de busca tabu proposto por Taillard (1993).

Neste capítulo mostrou-se o problema de roteamento de veículos, bem como

uma proposta de classificação. Destaca-se que a maioria dos métodos de solução

apresentados são aplicados ao problema básico de roteamento, ou seja com frota

homogênea.

No próximo capítulo serão discutidos conceitos de sistemas de informações

geográficas (SIG), bem como aspectos da modelagem de dados que compõem esse

sistema (modelagem de dados geográficos).

45

_______________________________________ 3 SISTEMAS DE INFORMAÇÃO GEOGRÁFICA - SIG

Neste capítulo serão apresentados as definições formais de Sigs, um breve

histórico de sua evolução, seus principais componentes e aspectos relevantes da

modelagem de dados geográficos.

3.1 DEFINIÇÕES

Burrough (1987) define SIG como um conjunto de ferramentas destinadas à

aquisição, armazenamento, recuperação, transformação e visualização de dados

espaciais do mundo real para uso em diversos campos de aplicação. Os dados

geográficos descrevem objetos do mundo real em termos de sua posição em relação

a um sistema de coordenadas, seus atributos e seu relacionamento espacial com

outros objetos (relacionamento topológico).

Arnoff (1989) inicia sua abordagem dizendo que SIGs são sistemas

computacionais usados para armazenar, manipular e analisar objetos e fenômenos,

onde a localização geográfica é uma característica importante ou crítica para a

análise. Acrescenta ainda que a despeito do poder de análise desta tecnologia, deve

haver também facilidades, equipamentos e um sistema organizacional envolvendo

as pessoas num todo, o que possibilitará a sua implementação e manutenção.

Um SIG proporciona aos profissionais os meios necessários para melhorar

sua eficiência e eficácia nos trabalhos que envolvem informações contidas nos

mapas e em atributos não gráficos. (Almeida, 1993)

As definições de SIGs refletem, cada uma à sua maneira, a diversidade de

usos e visões possíveis desta tecnologia e apontam para uma perspectiva

interdisciplinar de sua utilização. A partir destes conceitos é possível indicar duas

importantes características dos SIGs:

46

- permitem a integração, em uma única base de dados, de informações

geográficas provenientes de fontes diversas tais como dados

cartográficos, dados de censo e cadastro urbano e rural, etc. ;

- oferecem mecanismos para recuperar, manipular e visualizar estes dados,

através de algoritmos de manipulação e análise.

Um SIG não pode existir sem os dados descritos na primeira característica,

logo, confunde-se a capacidade do SIG de integração de dados, e a sua exigência

dos mesmos.

3.2 BREVE HISTÓRICO

Os primeiros projetos SIGs propriamente ditos datam dos anos 60. Seu

desenvolvimento, no Canadá, fez parte de um plano estratégico governamental de

longo prazo para criar um inventário automatizado de recursos naturais e uso do

solo (Reinhold et. al., 1991).

Durante os anos 70, desenvolveram-se fundamentos matemáticos voltados

para a cartografia. Surgiu, então, a topologia aplicada, permitindo análises espaciais

entre elementos cartográficos.

Até então, apenas grandes organizações utilizavam SIGs em sistemas de

grande porte. Segundo Tom (1994), a maioria das aplicações estava voltada ao

mapeamento digital, com funções analíticas. Nos anos 80, com a popularização e

barateamento das estações de trabalho, computadores pessoais e banco de dados,

o uso de SIGs foi difundido com a incorporação de muitas funções de análise

espacial.

Atualmente, as aplicações de SIGs variam na extensão da área geográfica

considerada (que pode abranger desde um quarteirão de uma cidade até o globo

terrestre); do equipamento utilizado (desde um computador pessoal até

supercomputadores); e na abrangência (de interesse particular até patrocínio de

47

agências governamentais abrangendo diferentes países). Recentemente, os SIGs

começaram a incorporar novas tecnologias, tais como sistemas especialistas e

técnicas de orientação a objeto (Davis, 1994; Worboys et al., 1994).

Segundo Câmara et al. (1996), existem três gerações de SIGs, resumidos na

Tabela 3.1.

1a geração

(1980 –1990)

2a geração

(1990 –1997)

3a geração

(1997-?)

Tecnologia CAD, cartografia BD, imagens Sist. distribuídos

Uso principal Desenho de mapas Análise espacial Centro de dados

Ambiente Projetos isolados Cliente-servidor Multi-servidores

Sistemas Pacotes separados Sistema integrado Interoperabilidade

Tabela 3.1: Evolução da tecnologia de SIGs

A primeira geração, baseada em CAD (Projeto auxiliado por computador),

caracteriza-se por sistemas herdeiros da tradição da cartografia, com suporte e

banco de dados limitado, e cujo paradigma típico de trabalho é o mapa (chamado de

“cobertura” ou de “plano de informação”). Esta classe de sistemas é utilizada

principalmente em projetos isolados, sem a preocupação de gerar arquivos digitais

de dados. Esta geração também pode ser caracterizada como sistemas orientados a

projeto.

A segunda geração de SIGs, baseada em bancos de dados geográficos,

chegou ao mercado no início da década de 90 e caracteriza-se por ser concebida

para uso em ambiente cliente-servidor, acoplado a gerenciadores de banco de

dados relacionais, e com pacotes adicionais para processamento de imagens.

Desenvolvida em ambientes multiplataforma com interfaces em janelas, esta

geração também pode ser vista como sistemas para suporte a instituições privadas e

públicas.

Pode-se prever, para os próximos anos, o aparecimento de uma terceira

geração de SIGs, baseada em bibliotecas digitais geográficas ou centros de dados

geográficos, caracterizada pelo gerenciamento de grandes bases de dados

geográficos, com acesso através de redes locais e remotas, públicas ou privadas.

48

Para esta terceira geração, o crescimento dos bancos de dados geográficos e a

necessidade de seu compartilhamento com outras instituições requerem o recurso

de tecnologias como banco de dados distribuídos. Estes sistemas deverão seguir os

requisitos de interoperabilidade, de maneira a permitir o acesso a informações

espaciais por SIGs distintos. A terceira geração de SIGs pode ainda ser vista como o

desenvolvimento de sistemas orientados à troca de informações entre uma

instituição e os demais componentes da sociedade.

3.3 COMPONENTES

Numa visão abrangente, pode-se considerar que um SIG tem os seguintes

componentes: interface com o usuário, entrada de dados, funções de

processamento e análise, visualização e plotagem, armazenamento e recuperação

de dados (Câmara et al, 1996; Abel et al., 1992). A Figura 3.1 indica o

relacionamento entre esses componentes. Segue-se uma breve descrição dos

mesmos.

Historicamente, o primeiro tipo de interface utilizado foi a linguagem de

comandos que, mesmo podendo possuir um grande poder expressivo, torna-se

complexa na medida em que o sistema cresce em funcionalidade, o que dificulta o

seu uso (Câmara et al, 1996). A disponibilidade de sistemas operacionais mais

interativos deu origem a interfaces baseadas em menus e barras de comando,

tornando os SIGs mais operacionais.

Existem basicamente duas formas de entrada de dados em SIGs: a entrada

de dados via levantamento direto no campo e a conversão analógica digital. Nesta

parte, é muito importante aproveitar o investimento já feito eventualmente por outras

instituições.

As funções de processamento são naturalmente dependentes dos tipos de

dados envolvidos. A análise geográfica engloba funções como superposição,

medidas (área, perímetro e distância), tabulações cruzadas, entre outras. Operações

49

sobre rede incluem caminhos ótimos, caminhos críticos e ligação topológica. Já as

consultas aos bancos de dados podem ser sobre atributos espaciais ou não.

Os ambientes de visualização de um SIG são conseqüências do tipo de

interface usado. Alguns sistemas dispõem de recursos altamente sofisticados de

impressão, englobando a definição de uma área de plotagem, colocação de

legendas, textos explicativos e notas de crédito.

Os dados de um SIG são geralmente organizados sob a forma de um banco

de dados geográfico. Tradicionalmente, os SIGs armazenavam os dados geográficos

em arquivos internos (binários). Este tipo de solução vem sendo substituída pelo uso

cada vez maior de sistemas gerenciadores de banco de dados (SGBD).

Esses componentes se relacionam de forma hierárquica. No nível mais

próximo ao usuário, a interface homem-máquina define como o sistema é operado e

controlado. No nível intermediário, um SIG deve ter mecanismos de processamento

de dados espaciais (entrada, edição, análise, visualização e saída). No nível mais

interno, um sistema de gerência de banco de dados geográficos oferece

armazenamento e recuperação dos dados espaciais e seus atributos.

Fig. 3.1 - Relacionamento entre os componentes de um SIG

Banco de dados Geográfico

Armazenamento e Recuperação

Visualização e Plotagem

Interface

Funções de Processamento

Entrada e Integr. de Dados

50

3.4 MODELAGEM DE DADOS

O sucesso do desenvolvimento de sistemas de informação tem como um de

seus pontos chave a realização da análise de requisitos de forma metodológica e

não ambígua. A abstração de conceitos e entidades existentes no mundo real é uma

parte importante da criação de sistemas de informação. Esta funciona como uma

ferramenta que nos ajuda a compreender o sistema, dividindo-o em componentes

separados. Cada um desses componentes pode ser visualizado em diferentes níveis

de complexidade e detalhe, de acordo com a necessidade de compreensão e

representação das diversas entidades de interesse do sistema de informação.

Ao longo dos anos, desde o surgimento dos primeiros sistemas gerenciadores

de bancos de dados (SGBD), foram criados vários modelos de dados. Esses

modelos podem ser classificados em: modelos de dados conceituais, modelos de

dados lógicos e modelos de dados físicos (Elmasri e Navathe, 1994). Os modelos de

dados lógicos se destinam a descrever a estrutura de um banco de dados

apresentando um nível de abstração mais próximo das estruturas físicas de

armazenamento. Os modelos de dados conceituais são os mais adequados para

capturar a semântica dos dados e, conseqüentemente, para modelar e especificar as

suas propriedades.

Eles se destinam a descrever a estrutura de um banco de dados em um nível

de abstração independente dos aspectos de implementação. Como exemplo desse

tipo de modelo, temos o modelo entidade-relacionamento proposto por Chen (1976),

o modelo funcional (Sibley e Kerschberg, 1977; Shipman, 1981), o modelo binário

(Abrial, 1974) e os modelos orientados a objetos (Dittrich, 1986). Já os modelos de

dados físicos são utilizados para descrever as estruturas físicas de armazenamento.

A orientação a objetos é uma tendência em termos de modelos para

representação de aplicações geográficas (Oliveira et al., 1997; Kösters, 1996; Perez

et al., 1997; Bennet, 1997; Nativi e Federici, 1994; Egenhofer e Frank, 1992;

Worboys et al., 1990; Davis et al., 1994). Conforme Câmara et al. (1996) “a

modelagem orientada a objetos não obriga o armazenamento em SGBD orientado a

objetos, mas simplesmente visa dar ao usuário maior flexibilidade na modelagem

51

incremental da realidade.” Os objetos geográficos se adequam bem aos modelos

orientados a objetos, ao contrário, por exemplo, do modelo de dados relacional que

não se adequa aos conceitos natos que o homem tem sobre dados espaciais.

3.5 MODELAGEM CONCEITUAL DE BANCO DE DADOS GEOGRÁFICOS

O processo de modelagem conceitual é sempre feito com base em algum

formalismo conceitual, independente do nível de abstração empregado (Cen, 96). O

resultado do processo de modelagem, denominado esquema conceitual, é

apresentado através de uma linguagem formal de descrição que possui uma sintaxe

e uma notação gráfica. Para cada formalismo conceitual, existem diversas

linguagens de descrição de esquema que são compatíveis com o formalismo.

O formalismo fornece um conjunto de conceitos, elementos e regras que são

usados no processo de modelagem da realidade, enquanto que a linguagem de

descrição fornece uma gramática para a apresentação do esquema conceitual

resultante da modelagem. A linguagem léxica possibilita o processamento

computacional do esquema, enquanto a notação gráfica é mais adequada para

facilitar o entendimento e a comunicação entre seres humanos (ex.: usuários e

projetistas).

Existem diversos modelos conceituais de dados propostos na literatura

especificamente para aplicações de sistemas de informação geográfica (SIG) como,

por exemplo, Modul-R, GeOOA, Geo-ER, GMOD, Geo-OMT e MADS. A maioria

deles é baseada nos formalismos Entidade-Relacionamento e da orientação a

Objetos. No entanto, os modelos diferem muito em relação à notação gráfica e

quanto à linguagem léxica (quando definida).

A modelagem conceitual apresenta grandes vantagens quando usada para

modelar dados geográficos entre eles pode-se citar a facilidade dos usuários

expressar seus conhecimentos sobre a a

Documents

HEURÍSTICA GRASP PARA O PROBLEMA DO ......Figura 6.12 - Parâmetros de Configuração da GRASP 112 Figura 6.13 - Resultado do Processamento 112 Figura 6.14 - Visualização das Rotas