08 - Roteirização e Programação de Veículos

Prévia do material em texto

UNIVERSIDADE LUTERANA DO BRASIL 
PRO-REITORIA DE GRADUAÇÃO 
Curso de Administração 
 
 
 
Disciplina SISTEMAS LOGÍSTICOS DE TRANSPORTES 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
ROTEIRIZAÇÃO E PROGRAMAÇÃO DE VEÍCULOS 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Prof. Alexandre da Silva Paim 
 
 
 
 
 
 
 
 
2015	
  
O	
  transporte	
  representa	
  uma	
  parte	
  significativa	
  do	
  sistema	
  de	
  distribuição.	
  Aumentar	
  sua	
  eficiência	
  é,	
  portanto,	
  um	
  dos	
  objetivos	
  dos	
  profissionais	
  que	
  atuam	
  em	
  logística	
  de	
  distribuição.	
  Uma	
  das	
  abordagens	
  para	
  isso	
  é	
  otimizar	
  o	
  uso	
  dos	
  equipamentos	
  e	
  pessoal	
  envolvidos	
  através	
  de	
  roteirização	
  e	
  programação.	
  	
  	
  
Roteirização	
  de	
  Veículos	
  	
  Roteirização	
  (do	
  inglês	
  “routing”	
  ou	
  ”routeing”)	
  é	
  a	
  determinação	
  de	
  um	
  ou	
  mais	
  roteiros	
  ou	
  seqüências	
  de	
  paradas	
  a	
  serem	
  cumpridos	
  por	
  um	
  ou	
  mais	
  veículos	
  de	
  modo	
  a	
  atender	
  um	
  conjunto	
  de	
  pontos	
  geograficamente	
  dispersos.	
  	
  Dito	
  de	
  um	
  modo	
  mais	
  concreto	
  o	
  problema	
  de	
  roteirização	
  de	
  veículos	
  consiste	
  na	
  determinação	
  dos	
  roteiros	
  a	
  serem	
  seguidos	
  (utilizando	
  uma	
  rede	
  de	
  rodovias)	
  para	
  fazer	
  a	
  distribuição	
  de	
  produtos	
  para	
  um	
  conjunto	
  de	
  clientes	
  utilizando	
  um	
  conjunto	
  de	
  veículos	
  rodoviários	
  em	
  um	
  dado	
  período	
  de	
  tempo.	
  Estes	
  veículos	
  são	
  operados	
  por	
  um	
  conjunto	
  de	
  equipes	
  de	
  entrega	
  (motoristas	
  e	
  ajudantes)	
  e	
  podem	
  ser	
  lotados	
  em	
  um	
  ou	
  mais	
  depósitos.	
  	
  Dentre	
  os	
  objetivos	
  da	
  reteirização	
  pode-­‐se	
  citar:	
  	
  a) minimizar	
  a	
  distância	
  total	
  percorrida;	
  b) minimizar	
  o	
  tempo	
  total	
  de	
  percurso;	
  c) minimizar	
  o	
  número	
  de	
  veículos	
  (e	
  equipes)	
  necessárias	
  para	
  atender	
  os	
  clientes;	
  d) minimizar	
  as	
  penalidades	
  associadas	
  com	
  o	
  atendimento	
  parcial	
  dos	
  clientes.	
  	
  
Programação	
  de	
  Veículos	
  	
  A	
  programação	
  (do	
  inglês	
  “scheduling”)	
  refere-­‐se	
  à	
  definição	
  dos	
  aspectos	
  temporais	
  (horários	
  de	
  cada	
  uma	
  das	
  tarefas	
  ou	
  eventos	
  importantes)	
  de	
  um	
  ou	
  mais	
  roteiros.	
  	
  	
  Diversos	
  fatores	
  condicionam	
  a	
  programação	
  dos	
  veículos,	
  podendo-­‐se	
  citar	
  os	
  horários	
  de	
  saída	
  e	
  retorno	
  à	
  base,	
  tempos	
  de	
  viagem	
  ou	
  deslocamentos	
  entre	
  os	
  pontos	
  consecutivos	
  dos	
  roteiros,	
  tempos	
  necessários	
  para	
  o	
  atendimento	
  de	
  cada	
  ponto,	
  janelas	
  de	
  tempo	
  de	
  atendimento	
  (cumprimento	
  de	
  um	
  horário)	
  determinadas	
  pelos	
  clientes,	
  duração	
  máxima	
  da	
  jornada	
  do	
  motorista	
  (determinada	
  por	
  legislação	
  específica),	
  paradas	
  para	
  almoço,	
  exigências	
  de	
  prioridade	
  por	
  clientes,	
  etc.	
  
 
Classificação	
  dos	
  Problemas	
  de	
  Roteirização	
  e	
  Programaçãode	
  veículos	
  	
  Bodin	
  et	
  al.	
  (1983)	
  classificam	
  os	
  problemas	
  de	
  roteirização	
  e	
  programação	
  em	
  3	
  grupos:	
  1) Problemas	
  de	
  roteirização	
  pura;	
  2) Problemas	
  de	
  programação	
  de	
  veículos	
  e	
  tripulações;	
  3) Problemas	
  de	
  roteirização	
  e	
  programação.	
  
	
  
1)	
  Problemas	
  de	
  roteirização	
  pura	
  	
  Os	
  problemas	
  de	
  roteirização	
  pura	
  são	
  problemas	
  espaciais	
  que	
  não	
  consideram	
  as	
  variáveis	
  temporais	
  ou	
  precedências	
  entre	
  as	
  atividades	
  para	
  elaboração	
  dos	
  roteiros.	
  Neste	
  tipo	
  de	
  problema	
  existe	
  um	
  conjunto	
  de	
  exigências	
  a	
  serem	
  atendidas	
  para	
  a	
  formarão	
  uma	
  seqüência	
  de	
  locais	
  (rota)	
  de	
  modo	
  a	
  minimizar	
  o	
  custo	
  total	
  de	
  transporte.	
  	
  
Ballou	
  (2006)	
  separa	
  os	
  problemas	
  de	
  roteirização	
  pura	
  de	
  veículos	
  em	
  três	
  modelos	
  básicos:	
  	
  I. um	
  ponto	
  de	
  origem	
  e	
  um	
  ponto	
  de	
  destino;	
  	
  II. pontos	
  de	
  origem	
  e	
  destino	
  coincidentes;	
  	
  III. pontos	
  de	
  origem	
  e	
  destino	
  múltiplos.	
  
 
I.	
  Um	
  ponto	
  de	
  origem	
  e	
  um	
  ponto	
  de	
  destino	
  
 
Este problema consiste em determinar o melhor caminho a ser percorrido entre uma origem e um 
destino em uma rede de caminhos. Na determinação do que é o melhor caminho podem ser usados, 
entre outros, critérios como menor distância percorrida (provavelmente o mais usado), percurso mais 
rápido, percurso de menor custo, percurso mais seguro. 
 
 
A Figura 1 apresenta um problema de roteirização cujo objetivo é determinar o caminho mais curto 
entre o ponto 1 e o ponto 6. 
 
 
 
 
 
 
 
 
 
 
 
Figura 1: Rede de rodovias interligando cidades. 
Fonte: Lachtermacher (2009). 
 
Um modo de resolver esse problema é através de tentativa e erro. Após um exame rápido do mapa é 
possível identificar apenas três possíveis caminhos: trajeto 1-2-4-6 (123 km), trajeto 1-5-6 (54 km) e 
trajeto 1-3-5-6 (71 km). A solução para o problema é o trajeto 1-5-6 com percurso total 54 km. Isto 
foi possível porque o mapa é muito simples. Mapas muito complexos tornam a procura pela solução 
muito demorada. Neste caso recomenda-se o uso de métodos matemáticos ou de Inteligência 
Artificial para procurar a melhor solução. 
 
Um algorítmo que pode ser usado na obtenção do caminho mais curto é o de Dijkstra (pronuncia-se 
daicstra). Neste a rede de caminhos é percorrida desde o ponto de origem até o ponto de destino 
sendo acumuladas as distâncias mais curtas em cada nó de modo a obter a menor distância possível. 
 
Um outro modo de resolver este problema é através do uso de Programação Linear. 
 
A Figura 2 apresenta uma modelagem através da programação linear do problema apresentado na 
Figura 1 utilizando o programa LINGO conforme proposto por Lachtermacher (2009). 
 
1 
2 4 
3 
5 6 
41km 
37km 
45km 
27km 
44km 
50km 4km 
 
Figura 2: Modelagem do problema de roteirização de origens e destino diferentes através do 
programa LINGO. 
 
Neste modelo as variáveis são identificadas por nomes indicando origem e destino de cada via. 
Assim a rodovia que liga o ponto 1 ao ponto 5 é indicada pela variável X12 e assim por diante. Para 
mais explicações sobre o modelo consulte Lachtermacher (2009). 
A resposta apresentada pelo LINGO é X12=0, X13=0, X15=1, X24=0, X35=0, X46=0, X56=1 (o que 
indica que o trajeto a ser seguido percorre os trechos 1-5 e 5-6) com resultado 54. 
 
II.	
  Pontos	
  de	
  origem	
  e	
  destino	
  coincidentes	
  
 
Um exemplo típico do problema em que o veículo parte de uma origem, faz entregas em diversos 
pontos e volta à origem é o da distribuição de produtos para clientes a partir de um depósito ou CD. 
A Figura 3 mostra um mapa onde aparecem os clientes indicados por círculos e o ponto de origem 
(CD) indicado por um triângulo. Os números indicam as quantidades a serem entregues em cada 
ponto. O objetivo é atender todos os pontos percorrendo as menores distâncias.Figura 3: Rede de rodovias interligando cidades. 
 
Existem diversos métodos que podem ser usados para resolver este problema, desde os mais 
simples como os métodos da Varredura e dos Centróides até métodos mais sofisticados (resultados 
bem melhores) como o método das Economias (de Clarke e Wright). 
Uma abordagem simples para resolver este problema segue duas etapas: 
a) determinação dos pontos de cada rota e 
b) traçado das rotas. 
depósito 
clientes 
1 
2 
3 
3 
1 
2 
1 
3 
3 2 
2 
1 2 
2 
1 
1 
2 
1 
Para a determinação dos pontos de cada rota podem ser usados métodos simplificados como os da 
Varredura ou dos Centróides. 
Após isso podem ser traçadas as rotas adotando heurísticas (regras práticas) como: 
a) a formação de traçados em forma de pétalas ou gotas e 
 
 
 
 
 
 
 
 
b) o não cruzamento de linhas em uma mesma rota. 
 
 
 
 
 
 
 
 
Exemplo	
  
Vamos resolver, como exemplo, o problema de roteirização indicado pela Figura 3. 
Para resolve-lo seguiremos os dois passos indicados anteriormente: selecionar os pontos de 
entrega de mercadoria (utilizando o método da Varredura) e traçar os trajetos (aplicando as duas 
heurísticas). 
Vejamos então os passos a seguir que solucionam o problema. 
a) Inicialmente é traçada uma linha (vermelha tracejada) a partir do ponto de origem (o CD, no 
caso) e escolhido um sentido de giro (horário, no caso). 
 
 
 
 
 
 
 
 
 
b) Esta linha é girada no sentido indicado e à medida que passa por cima de um ponto ela o 
seleciona se não estiver sido ultrapassada a capacidade do veículo. 
Suponha que o veículo tenha capacidade de transportar 7 unidades. 
depósito 
clientes 
1 
2 
3 
3 
1 
2 
1 
3 
3 2 
2 
1 2 
2 
1 
1 
2 
1 
Forma de gota gera 
rotas mais curtas 
(melhor) 
Forma diferente da 
gota pode gerar rotas 
mais longas (pior) 
Forma sem 
cruzamentos gera rotas 
mais curtas (melhor) 
Forma com 
cruzamentos pode 
gerar rotas mais longas 
(pior) 
Neste caso os quatro primeiros pontos encontrados seriam suficientes para atingir a 
capacidade máxima do veículos (1 +3+2+1 = 7). 
 
 
 
 
 
 
 
 
 
c) Traçar um roteiro seguindo as heurísticas apresentadas anteriormente (forma de pétala sem 
cruzamentos). 
 
 
 
 
 
 
 
 
 
d) Este processo é repetido (2+2+1+1=6; 2+3+2=7; 1+2+1+3=7; 3+1+2=6) até ter selecionado 
todos os pontos (linha tracejada retorna ao início) e ter completado o traçado de todos os 
roteiros. 
 
 
 
 
 
 
 
 
 
Figura 4: Solução do problema de roteirização utilizando o método da varredura e heurísticas. 
 
 
 
 
depósito 
clientes 
1 
2 
3 
3 
1 
2 
1 
3 
3 2 
2 
1 2 
2 
1 
1 
2 
1 
depósito 
clientes 
1 
2 
3 
3 
1 
2 
1 
3 
3 2 
2 
1 2 
2 
1 
1 
2 
1 
depósito 
clientes 
1 
2 
3 
3 
1 
2 
1 
3 
3 2 
2 
1 2 
2 
1 
1 
2 
1 
III.	
  Pontos	
  de	
  origem	
  e	
  destino	
  múltiplos	
  
 
Um exemplo típico deste problema é o caso de diversas fábricas abastecendo diversos centros de 
distribuição com o mesmo tipo de carga. A Figura 5 apresenta um problema deste tipo. 
O objetivo deste problema é determinar as quantidades a serem transportadas em cada trajeto de 
modo a suprir os centros de distribuição CD1, CD2 e CD3 com produtos das fábricas Fab1 e Fab2, 
respeitando suas capacidades, com o menor custo total de transporte. Os valores nas setas 
indicam o custo em R$ para transportar cada tonelada de carga da fábrica até o CD. 
 
 
 
 
 
 
 
 
 
Figura 5: Problema de roteirização com diversas origens e diversos destinos. 
 
Uma maneira de resolver este problema é através de tentativa e erro. Vamos examinar, a seguir, 
duas possíveis soluções. 
 
Uma possível solução para este problema seria: 
 
 
 
 
 
 
Transportar 1 000 t da Fab1 para o CD1 a um custo de $/t 5 x 1 000 t = $ 5 000; 
Transportar 1 500 t da Fab1 para o CD2 a um custo de $/t 4 x 1 500 t = $ 6 000 e 
Transportar 500 t da Fab2 para o CD3 a um custo de $/t 5 x 500 t = $ 2 500. 
O custo desta solução é $ 5 000 + $ 6 000 + $ 2 500 = $ 13 500. 
 
Outra possível solução para este problema seria: 
 
 
 
 
 
 
Transportar 1 500 t da Fab1 para o CD2 a um custo de $/t 4 x 1 500 t = $ 6 000, 
Transportar 500 t da Fab1 para o CD3 a um custo de $/t 6 x 500 t = $ 3 000 e 
Transportar 1 000 t da Fab2 para o CD1 a um custo de $/t 5 x 1 000 t = $ 5 000. 
O custo desta solução é $ 6 000 + $ 3 000 + $ 5 000 = $ 14 000. 
$3/t 
$4/t $4/t 
$5/t 
$6/t 
$5/t 
Fab 1 (2500t) 
Fab 2 (1000t) 
CD 1 (1000t) 
CD 3 (500t) 
CD 2 (1500t) 
$4/t $4/t 
$6/t 
Fab 1 (2500t) 
Fab 2 (1000t) 
CD 1 (1000t) 
CD 2 (1500t) 1500 t 
1000 t 
500 t 
CD 3 (500t) 
$4/t 
$5/t 
$5/t 
Fab 1 (2500t) 
Fab 2 (1000t) 
CD 1 (1000t) 
CD 3 (500t) 
CD 2 (1500t) 
500 t 
1500 t 
1000 t 
 
Tem-se, portanto, que a primeira solução é a melhor considerando-se que o critério de decisão foi o 
custo do frete. 
 
O método de tentativa e erro é pouco eficiente mas pode ser usado em problemas pequenos (poucas 
origens e destinos ou poucas rotas). Mas à medida que o problema fica mais complexo pode se tornar 
impossível de ser resolvido em um tempo razoável. Neste caso devem ser usados métodos mais 
eficientes como a Programação Linear. 
 
Para resolver este problema por Programação Linear definem-se as variáveis do problema como 
sendo as quantidades de carga em toneladas que são transportadas em cada um dos seis trajetos que 
ligam as fábricas aos CDs. Recomenda-se que os nomes das variáveis sejam explicativos. 
Considerando isso optou-se por atribuir os seguintes nomes às variáveis: Fab1CD1, Fab1CD2, 
Fab1CD3, Fab2CD1, Fab2CD2 e Fab2CD3. 
 
O objetivo a ser atingido, neste caso, é definido como minimizar a seguinte equação de custo: 
 
Custo = 5.Fab1CD1 + 4.Fab1CD2 + 6.Fab1CD3 + 4.Fab2CD1 + 3.Fab2CD2 + 5.Fab2CD3. 
 
As restrições do problema são associadas às capacidades das fábricas e às demandas dos CDs: 
 
Fab1CD1 + Fab1CD2 + Fab1CD3 <= 2500; 
Fab2CD1 + Fab2CD2 + Fab2CD3 <= 1000; 
Fab1CD1 + Fab2CD1 = 1000; 
Fab1CD2 + Fab2CD2 = 1500; 
Fab1CD3 + Fab2CD3 = 500; 
 
O problema pode ser escrito da seguinte maneira para ser resolvido pelo software de programação 
linear LINGO. 
 
Min=5*Fab1CD1+4*Fab1CD2+6*Fab1CD3+ 4*Fab2CD1+3*Fab2CD2+5*Fab2CD3; 
Fab1CD1+Fab1CD2+Fab1CD3<=2500; !soma do que sai de Fab1 não pode ultrapassar 2500t; 
Fab2CD1+Fab2CD2+Fab2CD3<=1000; !soma do que sai de Fab2 não pode ultrapassar 1000t; 
Fab1CD1+Fab2CD1=1000; !soma do que chega em CD1 deve ser igual a 1000t; 
Fab1CD2+Fab2CD2=1500; !soma do que chega em CD2 deve ser igual a 1500t; 
Fab1CD3+Fab2CD3=500; !soma do que chega em CD3 deve ser igual a 500t; 
 
Após executar o programa LINGO é obtido como resultado Fab1CD1=1000, Fab1CD2=500, 
Fab1CD3=500, Fab2CD1=0, Fab2CD2=1000 e Fab2CD3=0 e custo = 13 000. Esta solução 
apresenta um custo menor que as outras duas vistas anteriormente. 
 
2)	
  Problemas	
  de	
  programação	
  de	
  veículos	
  e	
  tripulações 	
  Os	
  problemas	
  de	
  programação	
  (ou	
  escalonamento)	
  podem	
  ser	
  considerados	
  como	
  problemas	
  de	
  roteirização	
  com	
  restrições	
  adicionais	
  relacionadas	
  ao	
  tempo	
  e	
  Bodin	
  et	
  al.	
  (1983)	
  dividem	
  este	
  problema	
  em	
  dois	
  tipos:	
  programação	
  de	
  veículos	
  e	
  programação	
  de	
  tripulações.	
  	
  	
  A	
  programação	
  de	
  veículos	
  trata	
  daseqüência	
  das	
  atividades	
  para	
  os	
  veículos	
  no	
  espaço	
  e	
  no	
  tempo.	
  Ela	
  trata	
  do	
  agendamento	
  das	
  rotas,	
  ou	
  seja,	
  atribuição	
  das	
  rotas	
  aos	
  veículos	
  disponíveis.	
  Na	
  resolução	
  destes	
  problemas	
  deve	
  ser	
  consideradas	
  características	
  dos	
  veículos	
  disponíveis,	
  restrições	
  do	
  tipo	
  limite	
  de	
  tempo	
  que	
  um	
  veículo	
  pode	
  estar	
  em	
  serviço	
  antes	
  de	
  
retornar	
  ao	
  depósito,	
  tarefas	
  que	
  só	
  podem	
  ser	
  realizadas	
  por	
  tipos	
  específicos	
  de	
  veículos	
  e	
  presença	
  de	
  diferentes	
  depósitos.	
  	
  A	
  programação	
  de	
  tripulações	
  está	
  relacionada	
  à	
  movimentação	
  da	
  tripulação	
  no	
  espaço	
  e	
  no	
  tempo.	
  Ela	
  trata	
  da	
  elaboração	
  das	
  escalas	
  de	
  trabalho	
  dos	
  motoristas,	
  ajudantes,	
  etc.	
  Este	
  tipo	
  de	
  problema	
  apresenta	
  restrições	
  como	
  paradas	
  para	
  refeições,	
  legislação	
  trabalhista	
  e	
  acordos	
  sindicais.	
  	
  	
  Para	
  entender	
  melhor	
  o	
  problema	
  vamos	
  abordar	
  um	
  exemplo	
  muito	
  simples	
  de	
  programação	
  de	
  veículos.	
  Para	
  resolver	
  este	
  problema	
  aplicaremos	
  apenas	
  uma	
  heurística:	
  programar	
  primeiro	
  as	
  rotas	
  mais	
  demoradas	
  (maior	
  tempo	
  de	
  trajeto).	
  	
  
Exemplo	
  	
  Atribuir	
  as	
  rotas	
  a	
  seguir	
  aos	
  veículos	
  disponíveis	
  de	
  modo	
  a	
  utilizar	
  o	
  mínimo	
  possível	
  de	
  veículos	
  (ocupação	
  máxima	
  de	
  seu	
  tempo).	
  	
  A	
  disponibilidade	
  dos	
  veículos	
  é	
  de	
  9h	
  por	
  dia.	
  	
  	
   	
  
 
 
Uma possível solução é apresentada a seguir. 
 
Inicialmente ordenamos as rotas do maior para o menor tempo de trajeto para aplicar a heurística 
recomendada anteriormente. 
 
Rota R7 R4 R3 R1 R5 R2 R6 
Tempo (h) 6 5 4 3 3 2 2 
 
A seguir atribuimos cada rota, partindo da mais demorada, ao veículo mais acima na tabela a seguir 
que tiver tempo disponível. 
 
Veículo 8h-9h 9h-10h 10h-11h 11h-12h 12h-13h 13h-14h 14h-15h 15h-16h 16h-17h 17h-18h 
V1 R7 R7 R7 R7 X R7 R7 R1 R1 R1 
V2 R4 R4 R4 R4 X R4 R3 R3 R3 R3 
V3 R5 R5 R5 R2 X R2 R6 R6 
 Como	
  resultado	
  da	
  aplicação	
  deste	
  método	
  temos	
  a	
  tabela	
  anterior	
  com	
  as	
  rotas	
  atribuídas	
  a	
  cada	
  um	
  dos	
  3	
  veículos	
  necessários.	
  	
  Problemas	
  reais	
  são	
  muito	
  mais	
  complexos	
  que	
  isso	
  e	
  exigem	
  a	
  utilização	
  de	
  técnicas	
  matemáticas	
  (como	
  Programação	
  Linear)	
  ou	
  métodos	
  de	
  Inteligência	
  Artificial	
  para	
  determinar	
  uma	
  melhor	
  solução.	
  	
  	
  
Rota R1 R2 R3 R4 R5 R6 R7 TOTAL 
Tempo (h) 3 2 4 5 3 2 6 25 
R1	
  
R2	
  
R3	
  
R4	
  
R5	
  
R6	
  
R7	
  
3)	
  Problemas	
  de	
  roteirização	
  e	
  programação	
  	
  Os	
  problemas	
  de	
  roteirização	
  e	
  programação	
  são,	
  como	
  o	
  nome	
  sugere,	
  uma	
  combinação	
  dos	
  dois	
  tipos	
  de	
  problemas	
  vistos	
  anteriormente	
  sendo,	
  portanto,	
  mais	
  próximos	
  dos	
  problemas	
  do	
  mundo	
  real.	
  Eles	
  podem	
  incluir	
  restrições	
  de	
  janelas	
  de	
  tempo	
  (horário	
  ou	
  dias	
  de	
  atendimento)	
  para	
  as	
  atividades	
  de	
  coleta	
  e	
  entrega.	
  	
  	
  
Métodos	
  de	
  solução	
  para	
  os	
  problemas	
  de	
  roteirização	
  e	
  programação	
  	
  	
  Os	
  métodos	
  de	
  solução	
  para	
  os	
  problemas	
  de	
  roteirização	
  e	
  programação	
  podem	
  ser	
  agrupados	
  em:	
  exatos,	
  heurísticos	
  e	
  meta-­‐heurísticos. 	
  Os	
  métodos	
  exatos	
  buscam	
  uma	
  solução	
  ótima	
  através	
  da	
  minimização	
  de	
  uma	
  função	
  de	
  custo.	
  As	
  soluções	
  baseadas	
  em	
  programação	
  linear	
  se	
  enquadram	
  nesta	
  categoria.	
  	
  Os	
  Métodos	
  heurísticos	
  geram	
  soluções	
  de	
  boa	
  qualidade	
  para	
  o	
  problema,	
  utilizando	
  procedimentos	
  que	
  apresentam	
  um	
  pequeno	
  tempo	
  de	
  processamento.	
  Eles	
  empregam	
  regras	
  empíricas	
  de	
  agrupamento	
  ou	
  técnicas	
  baseadas	
  em	
  “economias”,	
  acrescentando	
  ou	
  excluindo	
  paradas.	
  	
  As	
  meta-­‐heurísticas	
  ou	
  métodos	
  emergentes	
  também	
  não	
  garantem	
  a	
  solução	
  ótima.	
  	
  Neste	
  grupo	
  estão	
  métodos	
  de	
  inteligência	
  artificial	
  como	
  Sistemas	
  Especialistas,	
  Redes	
  Neurais	
  Artificiais	
  e	
  Sistemas	
  Multiagentes	
  baseados	
  em	
  Inteligência	
  de	
  Enxames.	
  	
  	
  Bodin	
  et	
  al.	
  (1983)	
  classificam	
  a	
  maioria	
  das	
  estratégias	
  de	
  solução	
  para	
  os	
  problemas	
  de	
  roteirização	
  de	
  veículos	
  da	
  seguinte	
  forma: a) agrupa	
  e	
  roteiriza	
  (“cluster	
  first-­‐route	
  second”),	
  que	
  consiste	
  em	
  agrupar	
  a	
  demanda	
  dos	
  nós	
  e/ou	
  arcos	
  primeiro	
  e	
  então	
  desenvolver	
  rotas	
  econômicas	
  sobre	
  cada	
  agrupamento	
  (o	
  método	
  da	
  Varredura	
  visto	
  anteriormente	
  é	
  um	
  exemplo	
  disso);	
  b) roteiriza	
  e	
  agrupa	
  (“route	
  first-­‐cluster	
  second”)	
  que	
  inicia	
  com	
  criação	
  de	
  uma	
  grande	
  rota	
  ou	
  ciclo	
  que	
  inclui	
  todas	
  demandas	
  (usualmente	
  inviável)	
  e	
  segue	
  dividindo-­‐a	
  em	
  rotas	
  menores	
  e	
  factíveis;	
  c) 	
  economia/inserção	
  que	
  consiste	
  da	
  construção	
  de	
  soluções	
  que	
  são	
  comparadas	
  em	
  termos	
  de	
  alguma	
  função	
  ou	
  critério	
  adotado	
  de	
  modo	
  a	
  escolher	
  aquela	
  que	
  produz	
  a	
  maior	
  economia;	
  d) melhoria/troca	
  é	
  um	
  procedimento	
  heurístico	
  em	
  que	
  em	
  cada	
  etapa	
  uma	
  solução	
  factível	
  é	
  alterada,	
  resultando	
  em	
  outra	
  solução	
  factível	
  com	
  o	
  custo	
  total	
  reduzido,	
  até	
  que	
  não	
  seja	
  possível	
  reduções	
  adicionais	
  no	
  custo;	
  e) programação	
  matemática,	
  que	
  inclui	
  algoritmos	
  baseados	
  em	
  formulações	
  de	
  programação	
  matemática	
  do	
  problema	
  em	
  questão	
  (o	
  método	
  de	
  programação	
  linear	
  é	
  
um	
  exemplo);	
  f) procedimentos	
  exatos,	
  que	
  incluem	
  programação	
  linear	
  inteira,	
  	
  programação	
  inteira	
  mista	
  e	
  técnicas	
  de	
  branch	
  and	
  bound	
  e	
  g) otimização	
  interativa,	
  que	
  se	
  baseia	
  em	
  interação	
  humana	
  e	
  no	
  conhecimento	
  e	
  na	
  intuição.	
  Esta	
  classificação	
  proposta	
  por	
  Bodin	
  é	
  anterior	
  ao	
  desenvolvimento	
  da	
  maior	
  parte	
  das	
  técnicas	
  meta-­‐heurísticas.	
  	
  	
  
Zoneamento	
  	
  A	
  distribuição	
  física	
  de	
  produtos	
  numa	
  determinada	
  região	
  implica	
  frequentemente	
  na	
  subdivisão	
  da	
  mesma	
  em	
  zonas	
  ou	
  bolsões,	
  às	
  quais	
  são	
  alocados	
  veículos	
  de	
  coleta	
  ou	
  entrega.	
  Isto	
  envolve	
  criar	
  grupos	
  de	
  elementos	
  baseadas	
  em	
  proximidade	
  ou	
  medidas	
  de	
  similaridade.Esquema típico de zoneamento 
Fonte: Novaes () 	
  Novaes	
  (1989)	
  cita	
  que	
  esse	
  conceito	
  visa	
  tirar	
  vantagem	
  das	
  características	
  morfológicas	
  das	
  redes	
  de	
  transporte	
  e	
  da	
  utilização	
  de	
  um	
  único	
  veículo	
  para	
  atender	
  vários	
  pontos.	
  	
  A	
  subdivisão	
  da	
  região	
  em	
  zonas	
  depende	
  de	
  fatores	
  como:	
  a) distância	
  da	
  zona	
  ao	
  depósito	
  ou	
  armazém,	
  b) densidade	
  de	
  pontos	
  de	
  parada	
  por	
  km2,	
  c) condições	
  viárias	
  e	
  de	
  tráfego,	
  d) tipo	
  e	
  capacidade	
  dos	
  veículos.	
  	
  Na	
  prática	
  esta	
  subdivisão	
  ainda	
  é	
  feita	
  através	
  de	
  procedimentos	
  empíricos,	
  baseados	
  na	
  experiência.	
  	
  Para	
  Valente	
  et	
  al.	
  (2003),	
  em	
  um	
  estudo	
  de	
  zoneamento,	
  dois	
  princípios	
  devem	
  ser	
  observados:	
  	
  a) a	
  procura	
  pelo	
  menor	
  custo	
  operacional,	
  através	
  da	
  diminuição	
  do	
  comprimento	
  total	
  das	
  rotas	
  ou	
  do	
  número	
  de	
  veículos	
  necessários	
  para	
  atender	
  todos	
  os	
  pontos	
  (clientes)	
  e	
  	
  b) a	
  procura	
  pelo	
  menor	
  tempo	
  de	
  operação.	
  	
  	
  A	
  partir	
  destes	
  princípios,	
  alguns	
  critérios	
  podem	
  ser	
  estabelecidos:	
  compacidade,	
  morfologia,	
  balanceamento	
  e	
  homogeneidade.	
  
 A	
  Compacidade	
  está	
  associada	
  à	
  proximidade	
  dos	
  elementos	
  de	
  um	
  grupo	
  entre	
  si	
  (quanto	
  mais	
  próximos	
  forem	
  os	
  pontos	
  do	
  serviço	
  menor	
  o	
  comprimento	
  das	
  rotas).	
  A	
  Morfologia	
  considera	
  que	
  os	
  fatores	
  que	
  podem	
  determinar	
  a	
  forma	
  das	
  zonas	
  são	
  as	
  características	
  das	
  regiões	
  urbanas	
  (rios,	
  morros,	
  linhas	
  férreas,	
  vias	
  expressas,	
  etc.).	
  O	
  Balanceamento	
  determina	
  que	
  o	
  número	
  de	
  pontos	
  a	
  serem	
  servidos	
  deve	
  ser	
  dividido	
  igualmente	
  entre	
  os	
  diversos	
  grupos	
  e	
  seus	
  respectivos	
  veículos,	
  de	
  acordo	
  com	
  sua	
  capacidade	
  e	
  volume	
  de	
  serviço	
  demandado	
  nos	
  pontos	
  atendidos	
  com	
  o	
  objetivo	
  de	
  conseguir	
  um	
  melhor	
  aproveitamento	
  dos	
  veículos	
  nas	
  rotas.	
  
A	
  Homogeneidade	
  considera	
  se	
  há	
  ou	
  não	
  muita	
  variação	
  das	
  condições	
  de	
  tráfego	
  e	
  dos	
  volumes	
  envolvidos,	
  por	
  exemplo,	
  dentro	
  de	
  cada	
  	
  zona	
  na	
  determinação	
  das	
  especificações	
  dos	
  veículos	
  e	
  dos	
  equipamentos	
  envolvidos.	
  
 
Métodos	
  de	
  Zoneamento	
  
 O	
  zoneamento	
  pode	
  ser	
  importante	
  para	
  a	
  minimização	
  	
  dos	
  tempos	
  e/ou	
  distâncias	
  mínimas	
  das	
  rotas	
  para	
  estas	
  zonas.	
  Existem	
  diversos	
  métodos	
  para	
  fazer	
  o	
  zoneamento.	
  No	
  método	
  das	
  Quadrículas	
  Elementares	
  (NOVAES,	
  1991)	
  a	
  região	
  de	
  distribuição	
  é	
  divida	
  em	
  quadrículas	
  elementares.	
  Para	
  cada	
  quadrícula	
  são	
  determinadas	
  as	
  coordenadas	
  e	
  a	
  densidade	
  de	
  pontos	
  de	
  entrega/coleta	
  e,	
  juntamente	
  com	
  as	
  características	
  de	
  distribuição	
  e	
  restrições	
  dos	
  veículos,	
  é	
  determinada	
  a	
  divisão	
  da	
  região	
  em	
  zonas	
  de	
  distribuição	
  aproximadamente	
  ótimas.	
  Neste	
  método	
  a	
  região	
  analisada	
  pode	
  ter	
  qualquer	
  forma,	
  o	
  depósito	
  pode	
  estar	
  localizado	
  em	
  qualquer	
  ponto	
  da	
  região	
  e	
  a	
  densidade	
  pode	
  variar	
  ponto	
  a	
  ponto,	
  de	
  forma	
  não	
  uniforme.	
  	
  
 
Referências	
  	
  BALLOU,	
  R.	
  H.	
  Gerenciamento	
  da	
  Cadeia	
  de	
  Suplementos	
  /	
  Logística	
  Empresarial.	
  5.ed.	
  Porto	
  Alegre:	
  Bookman,	
  2006.	
  BODIN,	
  L.	
  D.;	
  GOLDEN.	
  B.;	
  ASSAD,	
  A.;	
  BALL,	
  M.	
  Routing	
  and	
  Scheduling	
  of	
  vehicles	
  
and	
  crews:	
  the	
  state	
  of	
  the	
  art.	
  Computers	
  and	
  Operations	
  Research,	
  v.10,	
  n.2,	
  1983.	
  
LACHTERMACER, G. Pesquisa operacional na tomada de decisões. São Paulo: Prentice Hall, 
2009. NOVAES,	
  A.	
  G.	
  Sistemas	
  Logísticos:	
  Transporte,	
  Armazenagem	
  e	
  Distribuição	
  de	
  
Produtos.	
  São	
  Paulo:	
  Edgard	
  Bluncher,	
  1989.	
  NOVAES,	
  A.	
  G.	
  Logística	
  e	
  Gerenciamento	
  da	
  Cadeia	
  de	
  Distribuição.	
  Rio	
  de	
  Janeiro:	
  Campus,	
  2004.	
  VALENTE,	
  A.	
  M.;	
  PASSAGLIA,	
  E.;	
  NOVAES,	
  A.	
  G.	
  Gerenciamento	
  de	
  Transporte	
  e	
  
Frota.	
  São	
  Paulo:	
  Pioneira,	
  2003.	
  
 
 
Exercícios 
 
1. Dado o depósito e os pontos de entrega (clientes) 
mostrados no MAPA À DIREITA traçar os roteiros 
considerando que cada veículo pode carregar no MÁXIMO 
7t e demanda de carga de cada cliente é indicada pelo 
número ao lado. USAR O MÉTODO DA VARREDURA 
INDICANDO LINHA TRACEJADA INICIAL E O 
SENTIDO DE GIRO. 
 
 
 
 
 
 
 
 
 
2. Dado o depósito e os pontos de entrega (clientes) 
mostrados no MAPA À DIREITA traçar os roteiros 
considerando que cada veículo pode carregar no 
MÁXIMO 5t e demanda de carga de cada cliente 
é indicada pelo número ao lado. USAR O 
MÉTODO DA VARREDURA INDICANDO LINHA 
TRACEJADA INICIAL E O SENTIDO DE GIRO. 
 
 
 
 
 
 
 
 
 
3. Dado o depósito e os pontos de entrega (clientes) 
mostrados no MAPA À DIREITA traçar os roteiros 
considerando que cada veículo pode carregar no 
MÁXIMO 10t e demanda de carga de cada 
cliente é indicada pelo número ao lado. USAR O 
MÉTODO DA VARREDURA INDICANDO LINHA 
TRACEJADA INICIAL E O SENTIDO DE GIRO. 
 
 
 
 
 
 
 
 
depósito 
clientes 
1 
2 
3 
3 
1 
2 
1 
3 
3 2 
2 
1 2 
2 
1 
1 
2 
1 
depósito 
clientes 
1 
2 
3 
3 
1 
2 
1 
3 
3 2 
2 
1 2 
2 
1 
1 
2 
1 
depósito 
clientes 
1 
2 
3 
3 
1 
2 
1 
3 
3 2 
2 
1 2 
2 
1 
1 
2 
1 
4. Faça UMA proposta de transporte para suprir as fábricas com suas necessidades de 
suprimentos e apresente o CUSTO TOTAL desta proposta. Os valores nas setas indicam o 
custo em R$/tonelada para o trajeto. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
5. Faça UMA proposta de transporte para suprir as fábricas com suas necessidades de 
suprimentos e apresente o CUSTO TOTAL desta proposta. Os valores nas setas indicam o 
custo em R$/tonelada para o trajeto. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
6. Dados as duas soluções (a) e (b) de transporte de produtos das fábricas até seus CDs 
CALCULE os custos de transporte e INDIQUE a opção de menor custo. Os valores entre 
parêntesis indicam as capacidades das fábricas e os consumos de cada um dos depósitos. 
Solução (a) 
Fab1 (600t) àCD1 
Fab1 (600t) àCD2 
Fab2 (600t) àCD2 
Fab2 (800t) àCD3 
Solução (b) 
Fab1 (800t) àCD3 
Fab2 (1200t) àCD2 
Fab1 (600t) àCD1 
Fornecedor (For 1) 
capacidade: 
até 500t 
Fornecedor (For 2) 
capacidade: 
até 700t 
Fornecedor (For 3) 
capacidade: 
até 400t 
Fábrica (Fab 1) 
necessidade: 600t 
Fábrica (Fab 2) 
necessidade: 300t 
 
Fábrica (Fab 3) 
necessidade: 500t 
 
R$5/t 
R$3/t 
 
R$3/t 
 
R$6/t 
R$5/t 
R$5/tR$6/t 
R$4/t 
R$3/t 
Fornecedor (For 1) 
capacidade: 
até 1500t 
Fornecedor (For 2) 
capacidade: 
até 300t 
Fornecedor (For 3) 
capacidade: 
até 1000t 
Fábrica (Fab 1) 
necessidade: 600t 
Fábrica (Fab 2) 
necessidade: 
1000t 
 
Fábrica (Fab 3) 
necessidade: 800t 
 
R$5/t 
R$3/t 
 
R$3/t 
 
R$6/t 
R$4/t 
R$5/t 
R$6/t 
R$4/t 
R$3/t 
$7/t 
$5/t $4/t 
$4/t 
$6/t 
$5/t 
Fab 1 (1600t) 
Fab 2 (1600t) 
CD 1 (600t) 
CD 3 (800t) 
CD 2 (1200t) 
7. Fazer a programação dos veículos de modo a atender todas as rotas listadas utilizando o 
mínimo possível de veículos. A disponibilidade dos veículos é de 9h por dia. 
 
Rota R1 R2 R3 R4 R5 R6 R7 R8 R9 
Tempo (h) 4 6 5 6 4 4 4 5 7 
 
 
Veículo 8:00 9:00 10:00 11:00 12:00 13:00 14:00 15:00 16:00 17:00 
V1 X 
V2 X 
V3 X 
V4 X 
V5 X 
V6 X 
V7 X 
V8 X 
 
 
8. Fazer a programação dos veículos de modo a atender todas as rotas listadas utilizando o 
mínimo possível de veículos. A disponibilidade dos veículos é de 10h por dia. 
 
Rota R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 
Tempo (h) 3 2 4 5 1 2 3 2 1 2 
 
 
Veículo 8:00 9:00 10:00 11:00 12:00 13:00 14:00 15:00 16:00 17:00 18:00 
V1 X 
V2 X 
V3 X 
V4 X 
V5 X 
V6 X 
V7 X 
V8 X