Dimensionamento de Sistemas Logísticos

Prévia do material em texto

Dimensionamento de Sistemas Logísticos. José Eugenio Leal 1 
CAPÍTULO I: FUNDAMENTOS DA ANÁLISE ESPACIAL AGREGADA. ............................................... 3 
1. MÉTRICAS ESPACIAIS. ............................................................................................................. 3 
1.1. INTRODUÇÃO ......................................................................................................................... 3 
1.2. Métricas........................................................................................................................................ 3 
2. DETERMINAÇÃO DO PONTO CENTRAL......................................................................................... 5 
2.1. Métrica Euclideana (L2) ............................................................................................................... 5 
2.2. Ponto Central : Métrica Retangular.............................................................................................. 7 
2.2.1. Solução: Método de Fibonaci ............................................................................................... 7 
2.2.2. Método da Derivada para a métrica Retangular. .................................................................. 9 
3. DISTRIBUIÇÃO ESPACIAL ALEATÓRIA ........................................................................................ 10 
3.1. Estimativa De Pontos Em Uma Área. ........................................................................................ 10 
3.2 Estimativa de Distância Entre Pontos Próximos ......................................................................... 13 
4. REFERÊNCIAS BIBLIOGRÁFICAS. ................................................................................................ 15 
5. QUESTÕES DAS SEÇÕES. ............................................................................................................ 15 
CAPÍTULO II. ANÁLISE DE SISTEMAS DE COLETA E DISTRIBUIÇÃO. ............................................. 17 
1. O PROBLEMA DA COLETA E DISTRIBUIÇÃO........................................................................ 17 
1.1. INTRODUÇÃO. ...................................................................................................................... 17 
2. ESTIMATIVA DE TEMPOS E DISTANCIAS ASSOCIADAS A UM SERVIÇO. ............................... 18 
2.1 Tempo de ciclo............................................................................................................................ 18 
2.2 Quilometragem........................................................................................................................... 19 
2.3. Distância Média entre pontos..................................................................................................... 20 
2.4. Exemplo. ................................................................................................................................... 21 
3. DIVISÃO DE ZONAS DE ENTREGA EM FAIXAS ........................................................................... 24 
4. RESTRIÇÕES DE CAPACIDADE E DE TEMPO............................................................................. 26 
4.1. RESTRIÇÃO POR CAPACIDADE FÍSICA ................................................................................ 26 
4.1.1. Exemplo ............................................................................................................................. 29 
4.2. Limitação de tempo de ciclo por Jornada de Trabalho .............................................................. 30 
4.2.1. Exemplo: ............................................................................................................................. 34 
5. DIVISÃO DA REGIÃO EM ZONAS. ................................................................................................. 36 
5.1. Cálculo da área admissível na restrição por tempo:.................................................................. 36 
5.2. Cálculo da área admissível na restrição por carga.................................................................... 37 
5.3. Procedimento............................................................................................................................. 37 
6. ALGORITMO DE AGRUPAMENTO DE CLIENTES À VEÍCULOS................................................. 40 
6.1. SOLUÇÃO HEURÍSTICA........................................................................................................... 41 
6.2. SELEÇÃO DO CONJUNTO DE SEMENTES............................................................................ 42 
7. REFERÊNCIAS BIBLIOGRÁFICAS: ................................................................................................ 43 
8. QUESTÕES...................................................................................................................................... 43 
CAPÍTULO III. ESTRATÉGIAS DE DISTRIBUIÇÃO. ............................................................................. 47 
1. INTRODUÇÃO ................................................................................................................................. 47 
2. CÁLCULO DO ESTOQUE MÉDIO NA TRANSFERÊNCIA INDUSTRIA - DISTRIBUIDOR............ 48 
2.1. ESTOQUE NA INDÚSTRIA....................................................................................................... 49 
2.2. ESTOQUE EM TRÂNSITO........................................................................................................ 50 
2.3. ESTOQUE NO DISTRIBUIDOR ................................................................................................ 51 
2.4. ESTOQUE MÉDIO TOTAL........................................................................................................ 52 
2.5. CUSTO MÉDIO TOTAL DE ESTOQUE POR UNIDADE PRODUZIDA.................................... 52 
2.6. CUSTO DE TRANSFERÊNCIA................................................................................................. 53 
2.7. CUSTO MÉDIO TOTAL DE ESTOQUE E MOVIMENTAÇÃO .................................................. 55 
2.8. EXEMPLO.................................................................................................................................. 56 
3. DISTRIBUIÇÃO VIA DEPÓSITO DE TRIAGEM .............................................................................. 57 
3.1. CUSTO MÉDIO DE ESTOQUE................................................................................................. 59 
3.2. CUSTOS DE TRANSPORTE .................................................................................................... 59 
3.3. CUSTO MÉDIO TOTAL............................................................................................................. 59 
3.4. EXEMPLO.................................................................................................................................. 60 
4. QUESTÒES...................................................................................................................................... 62 
5. BIBLIOGRAFIA................................................................................................................................. 62 
Capítulo IV. ROTEIRIZAÇÃO DE VEÍCULOS ...................................................................................... 63 
1. INTRODUÇÃO. ................................................................................................................................ 63 
2. DEFINIÇÕES.................................................................................................................................... 63 
3. COBERTURA DE VIAS.................................................................................................................... 63 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal2 
3.1 Solução do Problema do Carteiro Chinês................................................................................... 65 
4. PROBLEMA DO CAIXEIRO VIAJANTE (P.C.V.). ............................................................................ 67 
5. ROTEIRIZAÇÃO COM RESTRIÇÕES MÚLTIPLAS........................................................................ 70 
5.1. Método de Clarke e Wright. ....................................................................................................... 71 
5.2. Ajuste de tempos de ciclo no procedimento. ............................................................................ 74 
5.3. Exemplo. ................................................................................................................................... 75 
6. ROTEIRIZAÇÃO COM JANELAS DE TEMPO. .............................................................................. 77 
7. REFERÊNCIAS BIBLIOGRÁFICAS: ................................................................................................ 82 
8. QUESTÕES...................................................................................................................................... 83 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 3 
CAPÍTULO I: FUNDAMENTOS DA ANÁLISE ESPACIAL AGREGADA. 
1. MÉTRICAS ESPACIAIS. 
1.1. INTRODUÇÃO 
Este é o texto inicial de um conjunto que visa dar elementos para o dimensionamento de 
componentes de um sistema logístico. Nele abordam-se problemas básicos relacionados a 
localização de pontos em uma área a ser servida pela logística. É baseado no capítulo Métricas 
Espaciais do livro do Prof. Antônio Galvão Novaes (1989) 
 
Para tratar alguns problemas logísticos associados ao aspecto espacial, pode-se assumir dois 
tipos de abordagens: 
 
- Análise de Redes 
- Análise Agregada 
 
Na análise de rede se trata de modelar o problema através de um grafo e tentar representar, da 
forma mais aproximada possível, a localização dos pontos de interesse: fábricas, depósitos, 
pontos de consumo e a rede de transportes da região. Problemas de roteirização de veículos, por 
exemplo, fazem uso desta abordagem. 
 
Na análise agregada trata-se de fazer uma aproximação agregada e freqüentemente contínua do 
problema e tentar encontrar soluções, as mais realistas possíveis, de alguns problemas de 
localização e de distribuição de produtos. Este texto trata de procedimentos dentro de uma 
análise agregada do problema. 
 
1.2. Métricas. 
 
Para a estimativa de distância entre dois pontos pode-se trabalhar com dos tipos de métricas 
distintas: métrica Euclidiana, também denominada métrica L2. 
 métrica Retangular, também denominada métrica L1, ou métrica de Manhatan. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Y 
 
 (XB,YB) 
 
 
 
 
 
 (XA,YA) 
 
 
 
 X 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 4 
 
Figura 1: Métrica Euclidiana. 
A métrica Euclidiana representa a localização dos pontos da rede através de duas coordenadas 
associadas aos eixos tradicionalmente denominados de x e y. Nesta métrica, a distancias entre 
dois pontos A e B seria dada por: 
 
2122 ])()[( ABABAB yyxxDE −+−= 
 
A Distância Real difere um tanto da distancia Euclidiana, que é uma distancia em linha reta, ou 
linha aérea, entre dois pontos. Então, a distância real ABD é aproximada pela distância 
Euclideana ABDE 
 
Pode-se obter uma relação entre a distancia euclidiana e a real através de um fator de correção. 
Este fator pode ser obtido por regressão. Neste caso, o fator de correção corresponderia ao 
coeficiente b, da equação, desde que a constante a seja pequena. 
 
Estimativa por regressão: D a bDEAB AB= + 
 
 
 
A distância, na métrica retangular, é aquela que se observa em uma rede de ruas em forma de 
malhas ou quadrículas regulares. Por isto também, o nome de métrica de Manhatan. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 2: Métrica Retangular. 
 
 
Neste caso, a distancia entre dois pontos A e B tem duas parcelas nos eixos x e y. 
A 
B N
I 
J
K 
L 
Y 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 5 
 
D R x x y yA B B A B A= − + −| | | | 
 
Trata-se de uma distância única independente das rotas usadas. Para o exemplo da figura 2, 
tanto faz seguir o caminho A,N,B , como o caminho A,I,J,K,L,B, que a distancia total será a 
mesma. Aqui o problema da diferença entre a distancia real e a da fórmula é menos crítico. 
Diferenças significantes ocorreriam apenas em malhas com trechos de ruas muito grandes e 
sinuosos, o que em geral não corresponde à métrica retangular. 
 
Novaes (1989) exemplifica relações entre as distancias reais e as obtidas com as métricas.: 
 
Rodovias: )Km60DEPara(DE11.19.23D ≥+= 
 
 D D E D E K m= <1 48 60. ( ) 
 
Ferrovias: D DE= +9 8 1 25. . 
 
Vias Urbanas: DED 3.1≈ 
 
 São Paulo: D DR= +113 1048. . , 
 
onde DE significa distância, na métrica euclidiana, e DR, na métrica retangular. Ballou (1995) 
sugere um fator médio de 1.41 para a correção da métrica euclidiana. 
 
2. DETERMINAÇÃO DO PONTO CENTRAL 
 
O problema da determinação de ponto central ocorre quando se deseja localizar uma facilidade 
para atender a um conjunto de pontos. Esta facilidade pode ser uma fábrica, ou loja, um 
depósito, ou centro de prestação de serviço, etc. Dependendo do tipo de facilidade, o critério 
para a localização pode mudar. Assim, para a localização de fábricas ou depósitos, o critério 
dominante pode ser o custo total de investimento, transporte e estoque. Já para a localização de 
uma loja, o critério receita, proveniente da acessibilidade dos clientes potenciais pode ser o 
determinante (Ballou, 1995). 
 
2.1. Métrica Euclideana (L2) 
 
Deseja-se encontrar as coordenadas X e Y de um ponto central para servir a um conjunto de 
pontos i. Definindo um peso Pi para cada ponto i, que denote a importância do ponto i, a função 
que se deseja minimizar é: 
 
 M in f xy P i x x y yi i
i
N
( ) [( ) ( ) )]= − + −
=
∑ 2 2
1
2
1
 
 
Derivando-se com respeito a cada variável e igualando-se a zero: 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 6 
 0
x
)y,x(f
=
∂
∂
 
 
 
 0
y
)y,x(f
=
∂
∂
 
chega-se a solução: 
 
 
∑
∑
=
=
=
N
1i
ii
N
1i
iii
DE/p
DE/xp
X
 
∑
=
∑
==
N
1i
iDE/ip
N
1i
iDE/iyip
Y
 
 
aonde: 
2
12
i
2
ii ])yy()xx[(DE −+−= 
 
Como )y,x(fDEi = não há solução analítica direta. 
 
 
A solução usa um método iterativo, apresentado a seguir. 
 
Para encontrar uma solução inicial, supõe-se 
 
...DEDE 21 = DEDE N = 
 
Com isso elimina-se DE no numerador e no denominador e pode-se calcular os valores iniciais 
de X e Y. 
 
∑
∑
=
i
ii0
p
xp
X 
∑
∑
=
i
ii0
p
yp
Y 
 
Em geral, na k-ésima iteração, calcula-se a distancia de cada ponto ao ponto central dado pelo 
par de coordenadas (xk,yk). 
 
2
12
i
k2
i
k)k(
i ])yy()xx[(DE −+−= 
 
e se introduz na equação: 
 
∑
∑
=
=
=+
N
1i
)K(
ii
N
1i
)k(
iii
1k
DE/p
DE/xp
X 
∑
∑
=
=
=+
N
1i
)k(
ii
N
1i
)k(
iii
1k
DE/p
DE/yp
Y 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 7 
 
Prosseguir até Xk+1 ≈ Xk e yk+1 ≈ yk 
 
A relação torna-se indefinida se ponto central C coincide com um ponto i (no caso DE=0). 
Para evitar esta situação, faz-se um artifício com a fórmula: 
 
D])yy()xx[(DE 2
12
i
2
i
i ∆+−+−= , 
 
aonde ≈∆D 0.05*unidade, sendo unidade a unidade usada na medida da distância 
(quilômetros, milhas, etc). 
 
2.2. Ponto Central : Métrica Retangular 
 
No caso da métrica retangular,a função a minimizar para encontrar o ponto central é: 
 
(MIN) ∑ −+−=
=
N
1i
iii |]yy||xx|[p)y,x(f 
 
Esta função é separável em X e Y: 
 
∑ ∑ −+−=
= =
N
1i
N
1i
iiii |yy|p|xx|p)y,x(f 
 
)y(f)x(f)y,x(f 21 += 
 
Minimizar )y,x(f é minimizar separadamente )x(f1 e )y(f 2 
 
2.2.1. Solução: Método de Fibonaci 
 
O método de Fibonaci para calcular mínimos de função pode ser usado para solucionar o 
problema. Basta então mostrar o procedimento de solução para x, que é igual para y. 
 
O Processo é também iterativo. Define-se uma Iteração genérica k e um No máximo de 
iterações: NIT. A figura 3 mostra o significado das variáveis. 
 
Passos: 
 
1. Determina XI = min xi 
 
 XS = max xi 
 
 k = 0 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 8 
2. k = k+1 Se k > NIT, pare. 
3. Faz S1 = XI e S2 = XS 
 
O Segmento S1 - S2 é dividido em 3 partes pelos pontos R1 e R2, sendo: 
 
R1 = (1-F) . (S2 - S1) + S1 e R2 = F . (S2 - S1) + S1 
 
onde: 
618.0
51
2
F =
+
= (inverso da seção Áurea) 
 
4. Avalia-se a função nos pontos R1 e R2, ou seja, calcula-se G1 = f1 (R1) e G2 = f1 (R2) 
 
Tem-se dois pontos G1 e G2 na função. Trata-se de, na busca do ponto mínimo, descartar uma 
parte da função, situada à direita de G2, como no caso da figura 3, ou à esquerda de G1. 
 
Se G1 ≤ G2 → S1 ≤ xMin ≤ R2 
 
 Então (abandona-se segmento R2 - S2) 
 Faz-se S2 = R2 e volta-se para o passo 2 
 
Se G1 > G2 R2 ≤ xMin ≤ S2 
 
 Então (abandona-se S1 - R1) 
 Faz-se S1 = R1 e volta-se para o passo 2 
 
 S1 + S2 
No final, após NIT iterações: xMin = 
___________ 
 2 
 
A precisão do procedimento é dada por : 
NIT
51
2






+
=∈ . Ou seja, pode-se definir NIT e 
verificar o grau de exatidão, ou dar o grau de exatidão e definir o número NIT, de iterações 
necessárias. 
 
 
 
 
 
 
 
 
 
 
 
Figura 3: Método de Fibonaci. 
 
 F(x) 
 
 
 G1 G2 
 
 
 
 
 S1 R1 R2 S2 X 
 F(x) 
 
 
 
 
 
 
 
 S1 R1 R2 S2 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 9 
2.2.2. Método da Derivada para a métrica Retangular. 
 
Este método é semelhante ao método da mediana para localizar pontos centrais usado no 
projeto de lay-out. Neste caso, busca-se encontrar um ponto aonde a derivada da função dada 
inicialmente por DIF, muda de sinal, por isso o nome de ‘Método da derivada’. 
 
O procedimento é aplicado uma vez para x e outra vez para y. 
 
1. Ordena-se os pontos por ordem de valor da coordenada, em conjunto com seus respectivos 
pesos. 
 
 x1 ≤ x2 ≤ .... ≤ xi ≤ ≤ xn 
 
 p1 p2 pi pn 
 
 
2. Calcula-se: DIF = ∑−
=
N
1k
kp 
 
 
3. i =0 
 
 Enquanto DIF < 0 faça 
 
 Início: 
 
 1ii += 
 
 DIF ← DIF + 2* pi 
 
 FIM enquanto 
 
 xMin = xi 
 
 
O mesmo procedimento é aplicado para y. 
 
Seja um exemplo com os seguintes dados: 
 
Ponto x y Peso 
1 230 153 2000 
2 328 166 3000 
3 198 245 1000 
4 313 277 2000 
 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 10 
Para achar a coordenada X ordena-se os pontos segundo o valor crescente de X. 
 
Ponto x Peso Ordem 
1 230 2000 2 
2 328 3000 4 
3 198 1000 1 
4 313 2000 3 
DIF -8000 
 
 
Toma-se na ordem: 
 
Ponto 3: 
-8000+ 2*1000= -6000. 
 
Ponto 1: 
-6000+2*2000= -2000 
 
Ponto 4: 
-2000+2* 2000= 2000 >0 
 
A coordenada X do ponto central será X4= 313. 
 
Um procedimento similar é feito para a coordenada Y. Evidentemente a coordenada Y poderá 
ser igual à de outro ponto que não o ponto 4. 
 
 
3. DISTRIBUIÇÃO ESPACIAL ALEATÓRIA 
 
3.1. Estimativa De Pontos Em Uma Área. 
 
Objetivo desta análise é: dada uma certa área, estimar o número de pontos com uma certa 
atividade (por ex: clientes). Este problema ocorre quando, por exemplo deseja-se calcular o No 
de pontos de entrega em função da área da região e da densidade média de pontos por Km2. 
 
Supõe-se que a distribuição de pontos segue um processo de Poisson, que é dado pela fórmula: 
 
 
!N
e*)t(
)t(P
tN
N
λ−λ
= 
 
aonde: 
 
)t(PN : Probabilidade de ocorrer N eventos no intervalo de tamanho t t( )≥0 . 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 11 
 λ : taxa média de eventos 
 
Média: t)t(N λ= 
 
Uma característica da distribuição de Poisson é que a média é igual à variância. 
Variância : tλ 
 
 
Na presente aplicação, a variável contínua t corresponde à Área A e a taxa média de eventos 
representa a densidade média de ocorrência de certo fenômeno na área A. Tem-se a 
probabilidade de ocorrência de N eventos: 
 
 
!N
e)A(
)A(P
AN
N
λ−λ
= ; A ≥ 0 
 
Média: A)A(N λ= 
 
Variância = Aλ 
 
 
Um propriedade interessante da distribuição de Poisson é que, para eventos independentes com 
a mesma taxa média λ, tem-se que os processos de Poisson são aditivos. Assim dadas duas 
áreas A1 e A2, com suas respectivas distribuições: 
 
 
!N
e.)A(
)A(P
1
1A1N
1
1N
λ−λ
= e 
!N
e.)A(
)A(P
2
2A2N
2
2N
λ−λ
= 
 
pode-se agregar as duas áreas com: 2121 NNN;AAA +=+= e calcular a probabilidade de 
ocorrer N eventos em A. 
 
⇒ 
!N
e.)A(
)A(P
AN
N
λ−λ
= 
 
 
É importante observar que, em geral, quando o número de casos segue: 15N ≥ , pode-se 
aproximar a distribuição de Poisson por uma distribuição Normal com 
Média = N e desvio padrão N=σ 
 
Para um intervalo de Confiança de 95% sabe-se que, para uma distribuição normal vale: 
 
 N96,1NN σ±= , 
Podendo-se então calcular os valores limites N1 e N2 da variação de N. 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 12 
 N1 96.1NN σ+= 
 
 N2 96.1NN σ−= 
 
No exemplo a seguir (Novaes, 1989) são dados: 
 
 Densidade média populacional: 2000/Km2 
 
 Consumo médio de 0.20 / hab / mês [garrafões de água/hab/mês]. 
 
 Área de entrega: 4 Km2 
 
Deseja-se calcular a variação dos números de pontos a serem servidos em uma distribuição de 
garrafões de água, que é realizada uma vez por semana. 
 
 dia/Km/.U33.13
30
20.0x2000
;.t.A.N 2==λλ= 
 
O número médio de pontos servidos na viagem semanal é: 
 
 Viagem/U33.3737x4x33.13N == ← (semanal) 
 
A estimativa do desvio padrão é: .U32.1933.373 ==σ 
Aproximando-se a distribuição por uma função normal, pode-se estimar: 
 
 32.19*96.133.373N ±= 
Então vale: 
 335.46 ≤ N ≤ 411.2 
 
 
 
Neste tipo de problema é importante definir bem as unidades e fazer as conversões corretas. 
O objetivo do cálculo é obter o numero médio de unidades por período T (dias). A base para o 
cálculo é obter Nd: número médio em unidades/dia. 
 
Nd [U/dia] = λ[U/Km
2-dia]*A[Km2]. 
 
N N Ktd= * 
 
Kt : fator de conversão do período desejada para dias. 
 
Sendo dados: 
• densidade populacional :den[hab/Km2] 
• índice de consumo por habitante em um período T: Cons[U/hab-T]. 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 13 
Converte-se consumo em unidades/hab-dia 
 Cons’=Cons/Kt 
 
Exemplos de fator de conversão de tempo são: T[mes]: Kt=30; T[semana]: Kt=7. 
 
A densidade em U/Km2-dia será calculada por: 
 
λ λ= ′ =cons dens ou cons dens Kt* * / 
 
Com isto pode-se calcular Nd e depois converter para o período desejado. 
 
 
Aplicando este procedimento ao problema, tem-se: 
 
λ= 0.20*2000/30 = 13.33 U/Km2-dia 
 
Nd=13.33*4 = 53.33 
 
N=53.33*7 [U/semana] 
 
 
3.2 Estimativa de Distância Entre Pontos PróximosNeste problema deseja-se encontrar o ponto mais próximo de um dado ponto tomado como 
referência. Este método é usado para problemas do tipo: 
• Fixação de itinerários 
• Localização de unidades de serviço (ex: viaturas de socorro mecânico) 
 
 
Tem-se uma Área A com uma densidade de pontos λ. Para a Métrica Euclidiana, a análise é a 
seguinte: 
 
Seja um círculo com raio r e centro P. 
 
A Área total é : π r2 . A Probabilidade De se encontrar N pontos em A (seguindo Poisson) é: 
 
 
!N
e)r(
)A(P
2rN2
N
λπ−πλ
= 
 
A probabilidade de não haver outro ponto, dentro do raio r (N=0) é: 
 
 P (d > r) ou: Po (A) = 
2re πλ− 
 
A probabilidade acumulada de haver pelo menos um ponto dentro de r é o complemento desta: 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 14 
 Prob (d ≤ r) = ( ) 0ddFe1
2r ≥=− πλ− 
 
Para esta função soma, a função de densidade é: 
2de.d2)d(f πλ−πλ= 
 
Rayleigh (segundo Novaes, 1989) calculou a média e o desvio padrão para esta função:
 2
1
2
1
261.0d;.5.0d
−−
λ=σλ= 
 
O Coeficiente de variação (razão do desvio padrão para a média) é: 523.0
d
d
CV =
σ
= 
 
 
Para a Métrica Retangular parte-se da análise de uma Área de um Quadrado de lado 
2r2A;2r = . 
 
A probabilidade de ocorrerem N pontos em r é: 
 
!N
e.)r2(
)A(P
2r2N2
N
λ−λ
= 
 
de forma semelhante ao procedimento para a métrica Euclidiana, chega-se, para a métrica 
retangular a: 
 
 ( )
2d22d2 e.d4dfe)0d(e1)d(F λ−λ− λ=≥−= 
Aqui também Rayleigh chegou às fórmulas de média e desvio padrão: 
 2
1
627.0d
−
λ= 
 2
1
327.0d
−
λ=σ 
 
 Cv = σ d
d = 0 523.
 
 
 
Exemplo: Em um serviço de reparação deseja-se saber a distancia média de um ponto para o 
ponto mais próximo: 
 
É dada a densidade de No chamadas / Km2 : λ = 0.7 
 
A Distância média na Métrica Retangular é dada por: 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 15 
 .Km.749.0)7.0(.627.0d 2
1
== − 
 Km390.0)7.0(.327.0d 2
1_
==σ 
 
Se for usado um coeficiente de correção da distancia de 1.3 chega-se a: 
 
 m508dem973d =σ= 
 
 
4. REFERÊNCIAS BIBLIOGRÁFICAS. 
Novaes, Antônio Galvão. Sistemas Logísticos. Ed Bluecher. São Paulo, 1989. 
 
Ballou, Ronald H. Logística Empresarial. Ed. Atlas. São Paulo. 1995. 
 
5. QUESTÕES DAS SEÇÕES. 
 
1. Defina os tipos de métricas usadas para a análise agregada da distribuição. 
 
2. Mostre os passos do método para o cálculo do ponto central com métrica Euclidiana. 
 
3. Mostre os passos do método de Fibonaci para o cálculo do ponto central com métrica 
Retangular. 
 
4. Dados os 5 pontos abaixo calcule o ponto central pelo método da derivada. 
 
 
Ponto X Y Peso 
1 157 94 1500 
2 230 153 2000 
3 328 166 3000 
4 198 245 1000 
5 313 277 2000 
 
 
5. Dada uma taxa de consumo de 0.24 unidades/habitantes-mes, uma densidade populacional de 
2000 hab/ Km2 e uma área de entrega de 3 km2, calcule a variação do número de pontos de 
entregas semanais, supondo uma distribuição de Poisson para o número de pontos por zona e 
aproximando depois para uma distribuição normal. 
 
 
 
 
 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 16 
 
 
6. Calcule o ponto central pela métrica retangular para os 4 pontos (sem o depósito atual que é 
o ponto zero) da tabela abaixo. 
 
 
Ponto X Y Ton 
0 272 189 0 
1 141 232 9 
2 398 241 3 
3 275 119 6 
4 392 162 5 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 17 
CAPÍTULO II. ANÁLISE DE SISTEMAS DE COLETA E 
DISTRIBUIÇÃO. 
1. O PROBLEMA DA COLETA E DISTRIBUIÇÃO 
 
1.1. INTRODUÇÃO. 
 
O problema que se coloca neste capítulo é o de definir um sistema de coleta ou distribuição 
para uma empresa. Basicamente, tem-se um depósito central localizado em um certo ponto 
geográfico, que deve servir a uma zona de coleta ou distribuição atendendo as seguintes 
condições: 
 
 
• A região geográfica é dividida em zonas 
 
• Cada zona será servida por um veículo e uma equipe de serviço 
 
• Os veículos partem do depósito e retornam após realizar o serviço. 
 
• O serviço de cada veículo é descrito por um roteiro que inclui um número dado de locais de 
parada dentro da zona a ser servida, ordenados em uma certa seqüência. 
 
• O Serviço seja de coleta ou distribuição demanda um tempo total desde a partida do veículo 
do depósito até a sua volta, denominado de tempo de ciclo 
 
 
 
O problema como um todo envolve as seguintes questões: 
 
• Definição da divisão da região em zonas. 
 
• Seleção de veículos e da equipe para executar a tarefa. 
 
• Estimativas de parâmetros como a quilometragem média, o tempo de ciclo e os componentes 
dos tempos associados ao serviço além dos custos associados. 
 
• Parâmetros do nível de serviço como a fração de serviço não atendida. 
 
 
Nesta seção será feita uma análise concentrada em estimar os tempos e distancias associados ao 
certo serviço. Em seguida é apresentado um método de divisão de região em zonas, em forma 
de faixas. Posteriormente serão analisados os efeitos de restrições de capacidade e tempo no 
serviço de distribuição. 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 18 
2. ESTIMATIVA DE TEMPOS E DISTANCIAS ASSOCIADAS A UM 
SERVIÇO. 
 
São dados um depósito localizado em certo ponto e uma zona de serviço com uma media de N 
pontos a serem atendidos (figura 1). Chamamos o primeiro ponto na zona de P1 e o último 
ponto da seqüência, de PN. 
 
O Tempo de percurso do depósito Dep a P1 supõe-se igual ao Tempo de PN a Dep, igual a t . 
 
Similarmente, supõe-se distância d de ida de Dep a P1, igual a distancia d de volta de PN a Dep. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 1: Serviço de um veículo em uma zona partido de um Depósito Dep. 
 
Dentro de cada zona supõe-se: 
 
O Tempo consumido em cada parada é em média: tp 
 
O percurso entre dois pontos sucessivos implica em uma distância média δδδδ e um tempo médio 
de viagem, ττττ 
 
2.1 Tempo de ciclo. 
 
Assim o Tempo de Ciclo pode ser obtido com a fórmula: 
 
 Dep 
 
 
 
 
 d,t d,t 
 
 
 
 
 
 
 
 P1 PN 
 
 
 δ,τ 
 p 
 tp 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 19 
 
 TC = t + T*p + T
*
τ + t (1) 
 
aonde: 
 
T*p é o tempo total perdido em todas as paradas da zona. É uma variável aleatória, pois o 
número de pontos N varia aleatoriamente, assim como o tempo consumido em cada parada. 
 
 T*p = t
(1)
p + t
(2)
p + ... + t
(N)
p (2) 
 
 
N é uma Variável Aleatória com Média: E(N) e variância Var(N). Por sua vez o tempo em 
cada parada é uma variável aleatória com média E(tp) e variância Var(tp). 
 
Então pode-se estimar a média e a variância da variável T*p, que é uma variável composta de 
duas variáveis aleatórias: 
 
E (T*p) = E(N) *E (tp) (3) 
 
Var [T*p] = E[N]* Var [tp] + E
2 [tp] x Var [N] (4) 
 
Esse tipo de fórmula proposto por Novaes(1989) se aplica a estes tipos de variáveis compostas 
do produto de duas outras variáveis aleatórias. 
 
Analogamente podemos estimar a média e a variância do tempo total de percurso E [T*τ] e 
Var [T*τ], respectivamente. 
 
 
E [T*τ] = E [N]* E [τ] (5) 
 
Var [T*τ] = E [N]* Var [τ] + E
2 [τ] *Var [N] (6) 
 
 
Então, podemos agora estimar o valor esperado, E [TC] e a variância Var [TC], do tempo de 
ciclo, no serviço da zona considerada. 
 
E [TC] = 2 x E [t] + E [T*p] + E [T
*
τ] (7) 
 
Var [TC] = 2 *Var [t] + Var [T*p] + Var [T
*
τ] (8) 
 
2.2 Quilometragem. 
 
A quilometragemtotal do serviço pode ser dada pela fórmula: 
 
DC = d + D*δ + d (9) 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 20 
Porém trata-se aqui também de uma variável aleatória, já que o número de pontos e a distancia 
de percurso entre pontos são variáveis aleatórias. 
 
A distancia total percorrida dentro da zona, tem um valor esperado E [D*δ] e uma variância Var 
[D*δ] calculados como se segue, usando as fórmulas propostas por Novaes. 
 
A distancia total percorrida dentro da zona, é a soma das distancias entre paradas, derivada do 
número médio de pontos e da distancia média entre pontos. 
 
E [D*δ] = E [N]* E [δ] (10) 
 
e a variância da distancia total é calculada de forma análoga a usada no tempo total de parada e 
no tempo total de percurso. 
 
Var [D*δ] = E [N] * Var [δ] + E
2 [δ] * Var [N] (11) 
 
Para o percurso total deve-se incluir as distancias de ida e volta à zona, cada uma estimada 
como E(d). 
 
Logo chega-se a: 
 
E [DC] = 2 * E [d] + E [D*δ] (12) 
 
e 
 
Var [DC] = 2 * Var [d] + Var [D*δ], (13) 
 
respectivamente valor esperado e variância da distancia total percorrida no serviço de uma 
zona. A fórmula anterior pressupõe o conhecimento da distância média entre pontos dentro da 
zona, que é estimada a seguir. 
2.3. Distância Média entre pontos. 
 
A distribuição da distâncias entre um ponto qualquer e o seu vizinho mais próximo segue uma 
distribuição de POISSON. 
 
Foi visto que vale para a Métrica Euclidiana: 
 
 d = −0 5
1
2. λ σd = 0,261 λ −
1
2 
 
No entanto, esta fórmula não se aplica aqui, pois trata-se de estimar a distancia média entre 
vários pontos de um percurso e não a distancia média ao ponto mais próximo. Este problema 
foi tratado por diversos autores e chega-se a seguinte fórmula geral: 
 
Para pontos distribuídos segundo uma distribuição de Poisson com densidade λ , vale : 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 21 
Distância média: δ = k *λ −
1
2 (14) 
 
 com K ≥ 0.5 
 
STEIN, parte de L, que seria a extensão total do roteiro dentro de uma zona com N pontos. 
Ele define: 
 
 
 Lim Ak
N
]L[E
= (15) 
 N → ∞ 
 
com k sendo uma constante e A : Área compacta e convexa. Para Stein: k ≈ 0,765 
 
 
E [L] ≈ k NA . (16) 
 
mas sabe-se também que: 
 
E [L] = N * δ ; (17) 
 
logo → δ = 2
1
*k
N
A
k
−
λ= (18) 
 
A densidade pode ser expressa como: A
N=λ (19) 
 
Então a Fórmula de distancia média entre pontos se assemelha a de distancia média ao ponto 
mais próximo: 
 
δ λ λ= ≈ =
− −
0 765 0 5
1
2
1
2. * .d (20) 
 
A diferença está na constante: k = ≠0 765 0 5. . 
 
Para estimar a variância de δ, que é σδ ao quadrado, supõe-se dado um coeficiente de variação 
Cv. 
 
Por exemplo: se se supõe Cv = 0.52 ,então: σσδ 52.0= 
 
2.4. Exemplo. 
Novaes apresenta um exemplo aonde se deseja estimar a variação da quilometragem para um 
serviço de distribuição com as seguintes características: 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 22 
É dada uma Área de uma região com 400 Km2. Tem-se uma medida da densidade média de 
pontos de λ =
15
2
. p
Km
 e dia. A região é dividida em zonas de serviço com 15 zonas. 
 
 
Sendo N o No médio pontos para zona, tem-se o número total de zonas na região NT: 
 
NT = N* 15 
 
Ao mesmo tempo vale: 
 
NT = λ * A = 1.5 *400 = 600 pt / dia 
 
Estratégia de solução: Trata-se aqui de estimar a variação da quilometragem percorrida em 
cada zona. Isto exige o valor esperado da quilometragem total percorrida dado pela fórmula 
(12) e o valor do desvio padrão da quilometragem total percorrida da fórmula (13). Com isto 
pode-se supor uma distribuição normal para a quilometragem total percorrida e estimar a 
variação como : D E D D= ±( ) . *196 σ . 
 
A fórmula (12) exige o valor do número esperado de pontos E(N) e o valor esperado de 
distancia entre pontos E(δ). Estes valores e a variância de δ, necessários para estimar a 
variância de D, são calculados a seguir. 
 
Fixado o valor do número total de pontos de toda a região, pode-se definir o número esperado 
de pontos por zona, em função do número de zonas da região, como: 
 
E [N] = 40
15
600
==
M
NT 
 
Da fórmula (20) de STEIN temos o valor da distância média entre pontos, 
δ = =
−
0 765 15 0 625
1
2. ( . ) . Km 
 
Usando um coeficiente de correção da distância ideal para real de 1.35 chega-se a 
δ δ= =135 0 84. .x Km (Real) 
 
É dado o coeficiente de variação da distancia entre pontos Cv= 0.52. Então pode-se estimar o 
desvio padrão de δ e , a partir daí, a variância: 
 
 Cv = 0.52 → σ δ = =0 52 0 84 0 44.. * . . km 
 
 
O Valor médio da quilometragem percorrida é dado por: 
 
 E [D*δ] = E [N] * E [δ] 
 
e a variância de D por: 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 23 
 
 Var [Dδ] = E [N]* Var [δ] + E
2 [δ] * Var [N] 
 
Com a suposição de que o número de pontos seque uma distribuição de POISSON, pode-se 
assumir: Var [N] = E [N] 
 
Substituindo na fórmula acima, tem-se: 
 
 Var [D*δ] = E [N] * (Var [δ] + E
2 [δ]) 
 
 Com E [N] = 40 , tem-se: 
 
 E [D*δ] = 6,3384.0*40 = 
 
e 
 
Var [D*δ] = 968,35)84.0444.0(*6,33
22 =+ . 
 
Logo: 
 
997,5)( ** == δσ DVarD 
 
Seja que a distancia total D segue uma Distribuição Normal. Então para um intervalo de 
Confiança de 95% tem-se: 
 
 variação de D*δ D E D Dδ δ σ
* * *[ ] .= ± 196 
 
 
Para 15 zonas vai valer: KmD 76.116.3396.1*997,56,33* ±⇒±=δ 
 
Ou seja, a distância D varia entre: 21,85 e 45,35 Km. 
 
 
 
 
 
 
 
 
 
 
 
 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 24 
3. DIVISÃO DE ZONAS DE ENTREGA EM FAIXAS 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 2: Divisão de Região em Faixas (Daganzo) 
 
Esta abordagem, proposta por Daganzo, trata de dividir uma região de serviço em setores ou 
faixas de forma a encontrar uma boa solução, com uma redução da distancia média entre pontos 
e, ao mesmo tempo, facilitar a definição do roteiro para a entrega. 
 
Deseja-se definir a Largura de faixa W (figura 2) em uma região com densidade uniforme de 
pontos λ. Cada faixa terá N pontos e corresponderá a uma zona de serviço. 
 
A Distância total em cada faixa é: E [L] = N * wδ (21) 
 
δ w = dist. Média entre pontos para faixa de largura w, a determinar. 
 
Segundo Daganzo os valores da distancia média entre pontos δ w em cada métrica é: 
 
 métrica retangular wδ = 
w
1
3
w
λ
+ (22) 
 
 métrica Euclidiana δ w = 
w
1
3
w
λ
+ ∅ (x) (23) 
 
Para realizar o cálculo faz-se: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 w 
 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 25 
x = λw2 e (24) 
∅ (x) = ]x)x1(lnx)x1[(
x
2
2
−++





 (25) 
 
Busca-se a largura de faixa w, que torna mínimo o valor da distancia média wδ 
 
O Valor é ótimo para métrica retangular e, aproximado, para métrica Euclidiana. 
 
 w* = 





λ
3
 (26) 
 
Substituindo nas fórmulas 22 e 23 chega-se para ambas as métricas a uma fórmula do tipo: 
 δ w = k λ
− 12 (27) 
 
Com k = 1.15 métrica retangular 
 k = 0.90 métrica Euclidiana 
 
Lembra-se que na fórmula de Stein para a métrica Euclidiana, k = 0.765. Logo na abordagem 
de Stein a distancia média é menor, mas com a divisão em faixas, o roteamento do veículo de 
entrega é mais fácilmente visualizado e realizado sobre um mapa da região. 
 
Observe-se que esta é a terceiraformulação baseada unicamente na densidade de pontos na 
zona de serviço. Portanto este dado, que é obtido por pesquisas de mercado, é fundamental para 
o cálculo de elementos do sistema logístico. A obtenção deste dado é, em geral, uma tarefa do 
setor de marketing da empresa. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 26 
4. RESTRIÇÕES DE CAPACIDADE E DE TEMPO 
 
Ao tratar dos problemas de distribuição deve-se levar em conta que as variáveis envolvidas no 
problema, notadamente os pontos a serem servidos, assim como as quantidades de entrega e 
coleta e os tempos perdidos nas operações, não são determinísticas, ou seja não podem ser 
previstas com certeza absoluta. Assim um Modelo determinístico é precário sendo necessário 
adotar um Modelo Estocástico. 
 
No caso da entrega, ou coleta de carga, deve-se considerar os seguintes aspectos: 
 
1) Capacidade física dos veículos - Dada a variabilidade da carga a ser transportada em cada 
ponto, pode haver carga rejeitada, por falta de capacidade em algum dia? 
 
2) Tempo máximo de jornada de tripulantes. A jornada do pessoal que trabalha nos veículos 
(motoristas e ajudantes) tem que respeitar os limite da lei. Além disto, acordos sindicais 
limitam o tempo máximo de trabalho contínuo. 
 
3) Desequilíbrio de produção entre veículos em zonas mais próximas e mais longínquas. Ao ser 
feita uma programação de distribuição, com a divisão de uma região em zonas deve-se tentar 
evitar que a carga de trabalho seja desigual entre as zonas. 
4.1. RESTRIÇÃO POR CAPACIDADE FÍSICA 
 
Um primeiro problema que merece atenção é a restrição devido à capacidade física do veículo 
utilizado, na distribuição em uma zona. Dada uma capacidade do veículo, a variabilidade do 
número de pontos a serem atendidos e das demandas associadas a cada ponto, há o problema 
tanto de falta de capacidade, que implica no não atendimento do cliente, como do excesso de 
capacidade, que implica em desperdício de recursos. 
 
Com relação à carga, há dois tipos de limitação. Para cargas leves, o limite será dado pelo 
volume da carga. Um exemplo extremo é o de transporte de algodão, aonde, com uma 
tonelagem relativamente pequena, preenche-se todo o volume disponível no veículo. Para 
cargas pesadas, o limite será o próprio peso. O transporte de bobinas de produtos siderúrgicos, 
por exemplo, preenche a capacidade do veículo com grande sobra de espaço. 
 
 
Seja ∇ a Capacidade útil do veículo (Novaes, 1989). 
 
Seja Ui o volume associado ao i-ésimo cliente. U é uma variável aleatória com média E[Ui] e 
variância Var [U]. 
 
A carga útil total ocupada pela carga de todos os clientes será representada por W: 
 
W = U1 + U2 + U3 + .... + UN (28) 
 
W é também uma variável aleatória, que é um produto das variáveis aleatórias N e U. Logo vale 
para o valor esperado de W: 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 27 
 
E [W] = E [N] * E [U] (29) 
 
e para a variância: 
 
Var [W] = E [N] * Var [U] + E2 [U] *Var [N] (30) 
 
 
Ao considerar a capacidade útil do veículo, deve-se levar em conta o problema de quebra de 
estiva. Isto implica em uma perda devido a forma das peças, ou à necessidade de deixar um 
vão livre para acesso dos carregadores. Então, haverá uma perda de p% da capacidade, que 
também pode ser expressa em um coeficiente de redução R . Vale: 
 
 R = 1 - 
p
100
 (31) 
 
Para a carga total transportada, vale a restrição de capacidade: 
 
 W ≤ R ∇ (32) 
 
Supõe-se que W segue uma distribuição normal, como mostrado na figura 3. A média da 
carga total dos cliente é E(W). A figura mostra o valor onde W iguala a capacidade útil do 
veículo. 
 
O número de ocorrências de não atendimento dos clientes está associado à área hachureada. O 
Objetivo da análise é calcular o nível de serviço associado ao atendimento, como a 
probabilidade de que a capacidade do veículo seja ultrapassada. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 3: Distribuição de carga total dos clientes. 
 f(w) 
 
 
 
 
 
 Ocorrência de demanda não 
 atendida 
 
 
 
 
 
 
 
 
 
 
 E(w) R∇ SW (Sobra média :Spill) 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 28 
 
 
Para realizar a análise, trabalha-se com a distribuição normal normalizada. A variável original é 
transformada em uma variável padronizada η. Com o uso de um tabela de distribuição normal 
obtem-se f(η) e ∅(η), respectivamente ordenada e área da distribuição normal, `a esquerda do 
ponto η. Para o problema em questão interessa a área à direita, que corresponde a probabilidade 
do valor de η ser ultrapassado. Este valor é dado na tabela anexa como ∅*(η). Para o 
problema a variável original é w, e o valor da carga a ser comparado é R∇, a capacidade prática 
do veículo. Para este valor a variável padronizada é dada por: 
 
 
( )
w
wER
σ
η
−∇
= (33) 
onde : 
 ]w[VarW =σ (34) 
 
 
Entrando com este valor de η na tabela obtém-se os valores de f(η) e ∅*(η). Este último indica 
a probabilidade da capacidade ser ultrapassada pela demanda w. 
 
Inversamente, pode-se calcular a capacidade necessária para atender a um dado nível de 
serviço. Para isso define-se o nível de serviço desejado, por exemplo 95%. Isto indica que a 
probabilidade de ser ultrapassada a capacidade deve ser menor que 0,05. Entrando na tabela 
normal normalizada com este valor na coluna de ∅*(η), encontra-se na coluna ao lado o valor 
de η, correspondente. O valor da capacidade nominal do veículo será dado por: 
 
( )
∇
+
=+=∇
−∇
=
)(*
log)(*log
wE
RowERo
wER w
w
w
ση
ση
σ
η 
 
Também pode-se, dada uma capacidade fixa, determinar o número de clientes que podem será 
atendidos, garantindo um certo nível de serviço. 
Para isso deve-se recordar que: 
 
E [W] = E [N] * E [U] e Var [W] = E [N] * Var [U] + E2 [U] *Var [N], ou 
 
Var [W] = E [N] * (Var [U] + E2 [U]), se N seguir a distribuição de Poisson. 
 
Pode-se escrever em função de N: 
( )
))()(((*)(
)**
2 UEUVarNE
UENER
+
−∇
=η 
Para simplificar chamamos E(U) de U, E(N) de N, Var(U) de VarU e R∇ de Cap. 
 
Passando o denominador para o outro lado: 
UNCapUVarUN *)(*(* 2 −=+η . 
 
Elevando ao quadrado dos dois lados e rearranjando chega-se a: 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 29 
22222 ***2*)(** CapUNCAPUNUVarUN +−=+η 
0)**2)(*(** 22222 =+++− CapUCAPUVarUNUN η 
Fazendo: 
2222 **2)(* CapceUCAPUVarUbUa =++== η 
Resolve-se a equação de segundo grau chegando a dois valores de N, que correspondem ao 
valor absoluto de η dado. Como o η entra elevado ao quadrado na equação, tanto o valor 
positivo como negativo de η, vão ficar positivos, na equação. Mas somente o de menor valor de 
N, atende ao nível de serviço desejado. Em geral a valores negativos de η, corresponde o maior 
valor de N e valores positivos de η, que indicam melhor nível de serviço estão associados com 
o menor valor de N. 
 
4.1.1. Exemplo 
 
Novaes(1989) apresenta um exemplo de entregas parceladas, aonde pretende-se estimar o 
número médio de clientes não atendidos. 
 
Dados: 
O número médio de pontos a serem atendidos é 30 pontos por veiculo por dia. 
 
O volume Médio de cada cliente é : 300 dm3 e o desvio padrão σ U = 70 dm
3 
 
O Compartimento de carga do veículo tem uma capacidade volumétrica de : ∇ = 17 m3 e o 
coeficiente de redução é dado: R = 0.6 
 
Estratégia de solução: trata-se de encontrar os valores de η correspondentea capacidade útil do 
veículo, para calcular o nível de serviço dado por 1- ∅* (η). Estas fórmulas demandam a média 
e o desvio padrão da carga total, a partir das fórmulas 29 e 30. Estas, por sua vez demandam os 
valores esperados e as variâncias de N e de U. 
 
Cálculo do valor esperado e da variância de N. 
Supõe-se que Número diário de pontos de entregas segue uma distribuição de POISSON. 
Logo a variância é igual à média. 
 
 E [N] = 30 → Var [N] = 30 
 
 
Cálculo da média e da variância do total de carga. 
 
Dados :E [U] = 300 e σ U = 70. logo : Var [U] = 4.900 [dm
3 ]2. 
 
E [W] = E [N] * E [U] = 30 *300 = 9000 → 9 m3 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 30 
 
Var [W] = E [N] * Var [U] + E2 [U] * Var [N]. 
 
Var [W]= 30 x 4900 + 3002 x 30 = 284.7 * 104 [dm3]2 
 
Cálculo do desvio padrão do total de carga. 
 
σ w Var w= =[ ] 1.687 dm
3 = 1,69 m3 
 
 
Cálculo do valor de R ∇ como variável de uma normal normalizada (valor padronizado) e dos 
valores da ordenada e da área. 
 
η= 71.0
69.1
0.92.10]w[ER
w
=
−
=
σ
−∇
 
 
Com η pode-se calcular f ( )η = 0.310 e ∅* (η) = 0.239 a partir de tabelas da distribuição 
normal normalizada. 
 
Portanto, o nível de serviço para esta distribuição está em 76%, o que é muito baixo. A 
capacidade necessária para atender a um nível de serviço de 95% seria: 
 
Para ∅* (η)=0,05, η= 1,622 
 
R
wEw )(* +=∇
ση
 o que dá uma capacidade nominal necessária de 19,84 m3 
4.2. Limitação de tempo de ciclo por Jornada de Trabalho 
 
A análise da conseqüência da limitação por jornada de trabalho sobre o serviço de distribuição 
parte da definição dos seguintes limites: 
 
H0 - Jornada normal de trabalho, em horas. 
 
H1 - Máximo tempo contínuo de trabalho. Este valor inclui as horas normais e as horas extras. 
 
Tem-se então três situações, considerando o tempo total t, dispendido no serviço de 
distribuição: 
 
I) Nível Normal t ≤ H0 
II) Serviço com horas extras: H < t ≤ H1 
III) Nível Crítico t > H1 
 
Na verdade, o nível crítico não pode ser tolerado e o nível com horas extras, deve ser avaliado 
com cuidado pela empresa. 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 31 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 4: Distribuição do tempo de ciclo. 
 
Seja TC o tempo de ciclo. Parte-se da hipótese de que se trata de uma variável aleatória que 
segue uma distribuição normal. 
 
Na figura P0 indica a probabilidade do tempo de ciclo ultrapassar H0 e P1 a probabilidade do 
tempo de ciclo ultrapassar H1. 
Como o serviço completo implica em cumprir o tempo de ciclo, P0 e P1 podem ser vistos como 
níveis de serviço, quando se trabalha respectivamente com tempos de ciclo sem usar horas 
extras (H0) e usando horas extras (H1). 
 
)()(1dx)x(f1dx)x(fP 0
*
0
0
00 η∅=∫ ∫ η∅−=−==
∞
η
η
∞−
 (39) 
 
)()(1dx)x(fP 1
*
1
11 η∅=∫ η∅−==
∞
η
 (40) 
 
e η é o valor da variável padronizada, a ser usada na distribuição normal normalizada. 
CT
)TC(EH
σ
−
=η (41) 
 
 f(TC) 
 
 
 
 
 
 
 
 
 P0 
 
 
 I A P1 
 
 B 
 II 
 
 III 
 
 E(TC) H0 H1 TC 
 
 SH0 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 32 
Usando nesta fórmula, os valores de H0 e H1, obtém-se respectivamente os valores de η0 e η1. 
Com estes valores entra-se na tabela e obtém-se as ordenadas da distribuição normal 
normalizada e as probabilidades P0 e P1. 
Outra vez o problema pode ser colocado como o Tempo de ciclo admissível que vai garantir 
certo nível de serviço pré-definido. 
O problema aqui é que de certa forma há uma relação entre E(TC) e σTC. Mas supondo σTC fixo 
pode-se calcular E(TC). Dado um valor de ∅* (η) desejado, encontra-se na tabela o valor 
correspondente de η. Daí: 
 
CTHTCE ση*)( −= 
 
O nível II de horas extras (H0 - H1 ) serve como uma folga de tempo para enfrentar a 
variabilidade dos tempos de ciclo, que são altamente dependentes de diversas fatores, desde do 
tempo gasto em cada ponto, até as variações do tempo no tráfego. Por outro lado, trabalhar com 
TC muito abaixo de H0, implica em uma subutilização do equipamento e da mão de obra. 
 
Pode-se calcular a área de serviço que corresponde e um nível de serviço dado. Para isto é 
necessário reescrever as fórmulas em função da área e da densidade de pontos por área e 
período. 
 
A fórmula do tempo de ciclo para a distribuição para uma zona desde um depósito, pode ser 
escrita em função da área e da densidade de pontos por km2 e período. 
 
Sabendo que: 
2/1*765,0* λδλ == eAN , pode-se escrever: 
 
tpA
v
AtTC **
*
765,0
***2 λ
λ
λ ++=
. 
 
)*
765,0
*(**2 tp
v
AtTC λλ ++=
 
 
Por outro lado, supondo que N segue uma distribuição de Poisson, o desvio padrão de TC pode 
ser escrito como: 
 
))var((**))var((**)var(*2 2 tptpAAtTC ++++= λττλσ 
 
Mas: 
Supondo um coeficiente de variação da distância média entre pontos igual a 0,523, pode-se 
supor: 
2*
16,0
var:log
*
40,0
*
765,0
*523,0
v
o
vv λλλ
σ ττ ===
 
 
sendo v a velocidade média de viagem dentro da zona. 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 33 
 
Usando estas estimativas de E(τ) e var(τ), pode-se estimar o desvio padrão de TC como: 
 
 
))var((**)
*
16,0
*
765,0
(**)var(*2 2
22
2
tptpA
vv
AtTC ++++= λ
λλ
λσ
 
 
))var((**
745,0
*)var(*2 2
2
tptpA
v
AtTC +++= λσ
 
 
)))var((*
745,0
(*)var(*2 2
2
tptp
v
AtTC +++= λσ
 
 
Chamando: 
)*
765,0
*(1 tp
v
K λλ += e ))var((*
745,0
(2 2
2
tptp
v
K ++= λ 
 
Tomando os valores de tempo em minutos e a velocidade em km/h, tem-se que definir 
constantes de conversão de unidades: 
)*
60*765,0
*(1 tp
v
K λλ += e ))var((*
3600*745,0
(2 2
2
tptp
v
K ++= λ 
 
Definido um nível de serviço estas fórmulas podem ser usadas para estimar a área admissível 
em um serviço de distribuição para garantir um nível de serviço sem horas extras (dentro de 
H0) ou com horas extras (dentro de H1). O nível de serviço vai estar associado a uma variável 
padronizada η. Com ela pode-se obter o TC admissível para garantir o nível de serviço. 
 
TC
TC
HTCou
TCH
ση
σ
η *+=
−
=
 
 
 
Usando K1 e K2 como definido anteriormente, e colocando as horas em minutos, , tem-se: 
 
2*var*2*60*1**2 KAtHKAt ++=+ η ou: 
 
2*var*2*)*260*(1* KAttHKA +=−− η 
 
Elevando-se ambos os termos ao quadrado: 
 
)2*var*2(*)*260*()*260*(*1**21* 2222 KAttHtHKAKA +=−+−− η 
 
Rearranjando, chega-se a: 
 
0var*2*)*260*()2*)*260*(*1*2(*1* 22222 =−−++−− ttHKtHKAKA ηη 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 34 
 
 
Chamando: 
21Ka = , 
)2*)*260*(*1*2( 2 KtHKb η+−−= e 
ttHc var*2*)*260*( 22 η−−= , 
encontra-se o valor de A que atende ao valor de η, correspondente ao nível de serviço desejado, 
resolvendo a equação de segundo grau: 
a
cabb
A
*2
**42 −±−
=
. 
Observa-se que para valores de η positivos, que correspondem a níveis de serviço altos (acima 
de 50%),o valor de A correto é obtido usando o sinal de menos na equação de solução. Para 
valores de η negativos, correspondentes a níveis de serviço baixos (abaixo de 50%) usa-se o 
sinal positivo na equação. É claro que maiores valores de área tendem a fazer crescer o tempo 
de ciclo e a maiores probabilidades de ultrapassar H, enquanto que menores valores de A 
tendem a produzir níveis de serviços melhores. 
 
 
4.2.1. Exemplo: 
Novaes(1989) apresenta o seguinte exemplo. Pretende-se estimar o número de horas extras, em 
um serviço de distribuição, com as condições expressas pelos dados abaixo: 
 
Tempo médio depósito a zona. 
E (t) = 20 min 
 
Coeficiente de variação de t. 
Cvt = 20% 
 
Tempo médio de viagem entre pontos, dentro da zona: 
E (τ) = 8 min 
 
Coeficiente de variação de τ: 
CVτ = 50% 
 
Tempo médio em cada parada. 
E (tp) = 10 min 
 
Coeficiente de variação de tp. 
Cvt p = 40% 
 
Horas da jornada normal e máxima. 
H0 = 8.5 hrs ; H1 = 10 hrs 
 
Número médio de paradas na zona : 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 35 
N = 27.3 / dia 
 
Coeficiente de variação de N: 
CVN= 0.182. 
 
Estratégia de solução: Para se calcular o nível de serviço, P0 e P1 usam-se as fórmulas 41, 39 
e 40, respectivamente. Estes, por sua vez, necessitam do valor das ordenadas padronizadas das 
variáveis H0 e H1, respectivamente ηo e η1 (Fórmula 41). Além disto, necessita-se do valor 
esperado e do desvio padrão do tempo de ciclo (Fórmulas 7 e 8, que dá a variância). Estes 
últimos valores são os primeiros a serem calculados, nos passos 1 a 5 a seguir. 
 
1) Cálculo da variância de N a partir do desvio padrão. 
 
 
σN= 0.182 x 27.3 = 4.97 
Var [N] = 24.7 
 
 
2) Média e variância de Tp
* (Soma de Tp) 
 
 E [Tp
*] = E [N] . E [Tp] = 27.3 . 10 = 273 min 
 
 Var [tp] = (0.4 x 10)2 = 16 [min]2 
 
 Var [Tp
*] = E [N] . Var [tp] + E2 [tp] . Var [N] = 
 
 27.3 - 16 + 102 . 24. 7 = 2.906.8 [min]2 
 
 
3) Média e variância de Tτ
* (Soma de Tτ) 
 
 E [Tτ
*] = E [N] . E [τ] = 27.3. 8 = 218.4 
 
 Var [τ] = (0.5 x 8)2 = 16 [min]2 
 
 Var [Tτ
*] = E [N] . Var [τ] + E2 [τ] . Var [N] 
 
 = 27.3 x 16 + 82 x 24.7 = 2017.6 [min]2 
 
4) Variância de t 
 
 Var [t] = (Cvt . E (t))
2 = (0.2 x 20)2 = 16 min2 
 
5) Tempo de ciclo do caminhão 
 
 E [TC] = 2 x E [t] + e [Tp
*] + E [Tτ
*] 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 36 
 = 2.20 + 273 + 218.4 = 5314 = 8.86 h 
 
 Var [TC] = 2 Var [t] + Var [Tp
*] + Var [Tτ
*] = 
 
 = 2.16 + 2.906,8 + 2.017,6 = 4.956,4 min2 
 
 σTC = 70,4 min = 1,17 h 
 
6) Cálculo de η0 e η1 
 
 31.0
17.1
86.85.8]TC[EH
TC
0
0 −=
−
=
σ
−
=η 
 97.0
17.1
86.810]TC[EH
TC
1
1 +=
−
=
σ
−
=η 
 
 
7) Cálculo dos níveis de serviço 
 
Para η0 =-0,31, o valor de P0 é: 0,6217, logo o nível de serviço é 37,8%, ou (1-P0)*100. 
 
Para η1=0,97, o valor de P1 é: 0,1635 e o nível de serviço é 83,7% 
 
5. DIVISÃO DA REGIÃO EM ZONAS. 
Este procedimento faz uma divisão da região em zonas de forma a garantir um nível de serviço 
dado pelas restrições de tempo e capacidade. Dado um nível de serviço desejado, encontra-se na 
tabela normal o valor de eta (variável normal padronizada). Este valor é usado para calcular a 
área admissível segundo as restrições de tempo e capacidade. 
 
5.1. Cálculo da área admissível na restrição por tempo: 
 
 
Define-se 
)*
765,0
*(1 tp
v
K λλ += e ))var((*
745,0
(2 2
2
tptp
v
K ++= λ (48) 
Chamando: 
21Ka = , 
)2*)*260*(*1*2( 2 KtHKb η+−−= e (52) 
ttHc var*2*)*260*( 22 η−−= , 
encontra-se o valor de A que atende ao valor de η, correspondente ao nível de serviço desejado, 
resolvendo a equação de segundo grau e tomado o menor valor da solução (sinal negativo antes 
da raiz): 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 37 
a
cabb
A
*2
**42 −−−
= . 
 
 
5.2. Cálculo da área admissível na restrição por carga. 
 
Define-se: 
 
2222 **2)(* CapceUCAPUVarUbUa =++== η (39) 
 
A área A2 é calculada como: 
 
A2=N/λ e 
a
cabb
N
*2
**42 −−−
= 
 
O que vale é o menor valor de A: A*=min(A,A2). 
 
5.3. Procedimento. 
 
Toma-se a região dividida em distritos, com área de cada um, valores de densidade e de 
distância ao deposito, que vão se refletir em tempos de viagem depósito -zona. 
 
Tem-se a matriz de vizinhança. A matriz de vizinhança é uma matriz quadrada de nXn sendo n 
o numero de distritos. A célula recebe valor 1 se i é vizinho de j e zero em caso contrário. 
 
Dados os valores de área admissível para cada distrito, aplica-se um procedimento guloso, 
agregando os distritos até o limite de área total admissível. 
 
 
Sejam 8 distritos em um setor da região segundo o desenho: 
 
 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 38 
 
 
 
A matriz de vizinhança é então: 
 
 1 2 3 4 5 6 7 8 9 
1 0 1 1 0 0 0 0 0 0 
2 1 0 1 1 1 0 0 0 0 
3 1 1 0 0 0 1 0 0 1 
4 0 1 0 0 1 1 1 0 0 
5 0 1 0 1 0 0 1 0 0 
6 0 1 1 1 0 0 1 1 1 
7 0 0 0 1 1 0 0 1 0 
8 0 0 0 0 0 1 1 0 1 
9 0 0 1 0 0 1 0 1 0 
 
Seja um valor de área admissível de 4 e valores de área de distritos de: 
 
 Área 
1 0,8 
2 0,4 
3 0,5 
4 0,3 
5 0,6 
6 0,7 
7 0,6 
8 0,8 
9 0,3 
Zoneamento “guloso”: 
 
1 
2 
3 
4 
5 
6 
7 
8 
9 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 39 
Um procedimento “guloso” de formação de zonas pode ser encontrado partindo de um distrito 
semente e ir agregando distritos vizinhos a algum já na zona, como se segue. 
 
Começando pelo distrito 1 tem-se: 
Vizinhos de 1 são: 2 e 3 Total da área: 1,7 
Vizinho de 2 são 4 e 5 Total da área: 2,9 
Vizinho de 3: 6 e 9 Total da área: 3,9 
Vizeinho de 4 é 7 Total da área: 4,58. Não é admissível 
 
Sobram as distritos 7 e 8 que poderiam ser agregadas em outro setor vizinho, ou definidas como 
uma zona de área 1,4. Caso se deseje equilibrar o serviço nas distritos pode-se redistribuir 
distritos vizinhos a 6 e 7 para equilibrar as áreas. 
 
Em geral, esse tipo de procedimento é completado por um procedimento de troca de distritos 
até melhorar o valor total. 
 
 
 
Distrito Área Área acumulada 
1 0,8 0,8 
2 0,4 1,2 
3 0,5 1,7 
4 0,3 2 
5 0,6 2,6 
6 0,7 3,3 
9 0,3 3,6 
7 0,6 4,2 Fechou a zona com 3,6. 
 
Uma redistribuição possível seria: 
 
Partindo da zona 7 puxar a zona 6. Distritos 6,7 e 8 teriam 2,1 e as demais teriam 2,9. 
 
 
Zoneamento equilibrado: 
 
Para reduzir a necessidade de ajustes após a primeira divisão, pode-se a priori estimar a área 
média de cada zona, a partir da área total da região e da área admissível por zona. 
 
Calcula-se o número de zonas com a fórmula: 
 
+






=
*A
AT
NZ 
onde: AT: área total da zona; A* : Área admisível da zona; [x]+: inteiro maior ou igual a x. 
 
A área média por zona é então: 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 40 
NZ
AT
AM = 
 
Aplicado ao exemplo teríamos: 
NZ=[5/4]+= 2. 
 
AM=5/2=2,5. 
 
Então o objetivo seria formar zonas contíguas com área de valor em torno de 2,5. 
 
Começando de 1 teriamos: 
Distrito Área Área acumulada 
1 0,8 0,8 
2 0,4 1,2 
3 0,5 1,7 
4 0,3 2 
5 0,6 2,6 <=2,5 
Começando a segunda zona pelo distrito 6 tem-se: 
Distrito Área Área acumulada 
6 0,7 0,7 
7 0,6 1,3 
8 0,8 2,1 
9 0,32,4 
 
Esse procedimento garante uma distribuição mais equilibrada. Eventualmente procedimentos 
de melhorias podem ainda ser aplicados para encontrar uma melhor solução. 
 
Observações sobre a influência do tempo t na fórmula. 
Na fórmula de área em função do tempo, o tempo depósito-zona e a sua variância, são uma das 
variáveis de cálculo. Cabe uma análise desta variável sobre o tamanho da zona de distribuição. 
Para faixas de distancias ao depósito pode-se calcular a área pelo critério do tempo.Para um 
exemplo calculado, os valores de área e t foram os seguintes: 
 
t 65 75 55 95 
Área 2,993811 2,854494 3,133435 2,576862 
 
 El= -0,01393 -0,01395 -0,01391 
 
Daí resulta uma elasticidade (área contra t) aproximada de -0,014. Ou seja a variação de uma 
unidade de minuto de t dá uma variação de 0,014 de área. Isso sugere uma influência 
relativamente pequena do tempo deposito-zona, na área admissível. 
Basicamente o que se sugere é dividir a região por faixas, por exemplo de 20 em 20 minutos e 
fazer a agregação de distritos dentro da faixa. 
 
6. ALGORITMO DE AGRUPAMENTO DE CLIENTES À VEÍCULOS 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 41 
Este seção apresenta um procedimento de agrupamento de clientes a veículos que corresponde a 
definir zonas de atendimento. O método foi proposto por Yiannis A. Koskosidis e Warren 
Powell no trabalho Clustering algorithms for consolidation of customer orders into vehicle 
shipments. 
 
O Problema pode ser denominado como de agrupamento capacitado, em inglês: clustering 
capacited problem (CCP). O trabalho apresenta uma heurística baseada em heurísticas 
anteriores de Mulvey e Beck e Fisher e Jaikumar. Propõe também um método iterativo para 
determinar as sementes, que serão definidas a seguir. 
 
Este problema tem aplicações como: 
- Agrupar clientes a veículos de tal forma que a rota não exceda a capacidade do veículo. 
 
- Agrupar clientes a rotas com restrições de tempo para tomar e deixar carga. 
 
- Agrupar cargas de mudanças de casas em um mesmo veículo. 
 
- Alocar clientes a veículos em serviços dial-a-ride. 
 
6.1. SOLUÇÃO HEURÍSTICA 
 
Tem-se: 
- I clientes, 
- J candidatos a semente; 
- K veículos. 
- Custo cij entre viagem de i para j. 
- Carga qi em cada cliente 
- Capacidade V do veículo. 
 
O método vai agrupar clientes em torno de alguns pontos iniciais para cada grupo, denominado 
de semente. O algoritmo se inicia com um conjunto de K sementes e aloca clientes à semente 
mais próxima, de forma a não ultrapassar a capacidade do veículo. Depois de alocar todos os 
clientes, novas sementes são selecionadas em cada grupo de forma a minimizar o custos nos 
grupos. Se a nova semente é diferente da anterior, para pelo menos um grupo, a alocação de 
clientes à sementes é refeita. Finalmente, são tentadas melhorias através de intercâmbios entre 
pares de clientes pertencentes a diferentes grupos. 
 
O algoritmo itera entre as três fases: alocação, relocação de sementes e melhorias. 
 
Fase 1: 
Os clientes são alocados à sementes seguindo uma função de arrependimento (regret function). 
Esta função é definida como a diferença entre o primeira e a segunda semente mais próxima, 
para um cliente i: Regret(i) = Cij1 - Cij2, onde j1 é a semente mais próxima e j2 a segunda 
semente. 
A função de arrependimento representa a penalidade de alocar o cliente a segunda semente mais 
próxima, em vez da primeira. 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 42 
 
Para cada cliente é calculada esta função. 
 
Em seguida eles são ordenados em ordem decrescente de arrependimento. Então eles são alocados 
seguindo esta ordem à semente viável mais próxima. Por viabilidade se entende que, se devido à 
capacidade, não se pode alocar um cliente a semente j1, se aloca a j2 e assim sucessivamente. Caso 
um cliente não seja alocado a nenhuma semente o conjunto atual de sementes é inviável. Inclui-se 
mais uma semente, coincidindo com o cliente não alocado e reinicia-se o processo. Ao final da fase 1 
todos os clientes devem estar alocados e os grupos formados. Os autores lembram que o uso da 
função de arrependimento lembra o método de Vogel para a solução inicial do problema de transporte. 
 
 
Fase II. Relocação da semente. 
Na formação de um grupo, provavelmente, a semente atual não estará no meio da zona. Na 
segunda fase, em cada grupo é buscado o ponto que minimiza a distância total dentro do grupo. 
O cliente torna-se a nova semente. Se houver uma mudança de semente, volta-se a fase I e 
refaz-se a alocação de clientes a sementes. É feita uma iteração entre as fases I e II até não ser 
mais possível melhorias. 
 
Fase III. Intercâmbios locais. 
Na fase final tenta-se melhorar a solução atual considerando todas os possíveis intercâmbios 
entre pares de clientes em diferentes grupos. Para cada intercâmbio volta-se a fase II e, se for o 
caso, à fase I. 
 
O intercâmbio é feito entre os clientes r do grupo A, com centro em a e o cliente s do grupo B, 
com centro em b se: 
 
Crb + Csa < Cra + Csb. 
 
Isto equivale a supor uma função objetivo atual Z e uma nova Z’. Na troca a nova função Z’ 
será: 
 
Z’ = Z - Cra + Crb -Csb + Csa. 
 
Se Z’ < Z o custo total se reduz, ou: 
Z - Cra + Crb -Csb + Csa < Z, ou: 
Crb + Csa < Cra + Csb. 
 
6.2. SELEÇÃO DO CONJUNTO DE SEMENTES 
 
Uma boa solução inicial vai servir para reduzir o tempo total de processamento. Aqui 
apresenta-se três alternativas de criação do conjunto inicial. 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 43 
 
Algoritmo 1: Pseudo-knapsack. 
Cada cliente j é tomado como semente potencial. Os demais clientes i são ordenados em ordem 
crescente de Cij/qi. Toma-se os p primeiros clientes na ordem de forma a não exceder a 
capacidade V. O custo do candidato j é: 
Cj = ∑Cij/qi i=1,p 
 
Repete-se o processo para todos os clientes. Finalmente os clientes são ordenados na ordem 
crescente de Cj e os K (que é número de veículos) primeiros são selecionados como semente. 
 
Algoritmo 2: Pseudo-knapsack com eliminação. 
Neste procedimento cada vez que um grupo é formado em torno de um ponto j, este ponto e os 
p pontos do grupo são eliminados e prossegue-se o algoritmo sem estes pontos. Este método 
pode eventualmente indicar menos grupos que o total de veículos K a serem usados. 
 
Algoritmo 3: Pseudo-knapsack com eliminação parcial. 
Neste caso, apenas o ponto j é eliminado, mas os demais pontos do grupo de j são deixados para 
serem usados para calcular o custo dos demais candidatos a semente. 
 
Os autores testaram os três algoritmos e mostraram que o primeiro e o terceiro algoritmos 
tiveram melhor desempenho. 
 
 
 
 
 
 
 
7. REFERÊNCIAS BIBLIOGRÁFICAS: 
Novaes Antônio Galvão. Sistemas Logísticos. Ed Bluecher. São Paulo. 1989. 
Koskosidis Yiannis A. e Powell, Warren. Clustering algorithms for consolidation of customer 
orders into vehicle shipments. Transportation Research, Vol. 26B, No. 5, pp. 365-379, 1992. 
Bittencourt, M. A. P. Componentes de um sistema computacional para análise de sistemas 
logísticos. Dissertação de Mestrado. Depto. de Engenharia Industrial. PUC-Rio. 2005. 
 
8. QUESTÕES. 
 
1. Mostre em um esquema e descreva os componentes da fórmula do tempo de ciclo de um 
veículo de distribuição. 
 
2. Mostre a fórmula geral do cálculo da quilometragem e explique a fórmula de cada 
componente. 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 44 
3. Dada uma região de 400 km2 e 20 zonas, com uma densidade de pontos de 1.5 pontos por 
km2 e por dia, calcule a variação da quilometragem total percorrida por cada caminhão de 
entrega. Suponha o coeficiente de variação igual a 0.52.4. Como definir de forma rápida um roteamento de veículos usando a divisão de zonas em 
faixas pelo método de Daganzo? 
 
5. Quais os limites temporais impostos pela jornada de trabalho às viagens de distribuição? 
Mostre numa figura uma curva normal da distribuição do tempo de ciclo e os valores referentes 
a cada limite. 
 
 
7. Dados: 
E(t) = 20 min. cvt = 20% E(τ) = 8 min. CVτ= 50% 
E(t) = 10 min Cvtp = 40% distancia D-Zona : 10 Km 
dist. média entre paradas: 2 km H0= 8.5 h H1 = 10 h. 
E(N) = 27.3 VAR(N) = 24.7 
Calcule o nível de serviço esperado sem horas extras e com horas extras. 
 
8. Calcule o nível de serviço de um serviço de distribuição com as seguintes características: 
N. médio de ponto atendidos por dia: 50 
Demanda média por cliente[dm3]: 260 
Desvio padrão da demanda média [dm3]: 30 
Capacidade do veículo [m3]: 21 
Perda de capacidade do veículo [%]: 30 
 
Suponha que o número de pontos de entrega segue uma distribuição de Poisson. Use a tabela 
em anexo. 
 
9. Calcule o valor esperado de horas extras entre H0 e H1 e o valor de horas extras maior que 
H0 para um problema de distribuição com os seguintes dados: 
 
N : Número médio de paradas na zona : 18 
CVN : Coeficiente de variação de N : 0.236 
E[t] : tempo médio de percurso entre o depósito e a zona : 46.65 horas. 
Cvt : Coeficiente de variação de t : 16.06 %. 
E[τ] : Tempo médio de percurso entre paradas sucessivas na zona : 6.92 horas. 
CVτ : Coeficiente de variação de τ : 17.36 %. 
E[tp] : Tempo médio de parada em cada ponto : 9.42 horas. 
Cvtp : Coeficiente de variação de tp :40 %. 
H0 : Tempo de trabalho diário normal : 7.71 horas. 
H1 : Tempo máximo de trabalho diário : 9.683 horas. 
 
 
 
 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 45 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Eta f(eta) F*(eta) eta f(eta) F*(eta) 
-3,878 0,000212 0,999947 1,122 0,213785 0,130931 
-3,778 0,000311 0,999921 1,222 0,190238 0,110854 
-3,678 0,000452 0,999882 1,322 0,167599 0,093084 
-3,578 0,000651 0,999827 1,422 0,146186 0,077513 
-3,478 0,000926 0,999747 1,522 0,126239 0,064005 
-3,378 0,001305 0,999635 1,622 0,107930 0,052402 
-3,278 0,001822 0,999477 1,722 0,091358 0,042535 
-3,178 0,002517 0,999258 1,822 0,076561 0,034227 
-3,078 0,003443 0,998958 1,922 0,063522 0,027303 
-2,978 0,004663 0,998549 2,022 0,052179 0,021588 
-2,878 0,006253 0,997999 2,122 0,042435 0,016919 
-2,778 0,0083 0,997265 2,222 0,034168 0,013142 
-2,678 0,010909 0,996297 2,322 0,027237 0,010116 
-2,578 0,014195 0,995031 2,422 0,021496 0,007718 
-2,478 0,018287 0,993394 2,522 0,016797 0,005835 
-2,378 0,023324 0,991297 2,622 0,012994 0,004371 
-2,278 0,029453 0,988637 2,722 0,009952 0,003244 
-2,178 0,036822 0,985297 2,822 0,007547 0,002386 
-2,078 0,045576 0,981145 2,922 0,005666 0,001739 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 46 
-1,978 0,055851 0,976036 3,022 0,004211 0,001256 
-1,878 0,067761 0,969809 3,122 0,003099 0,000898 
-1,778 0,081393 0,962298 3,222 0,002258 0,000637 
-1,678 0,096794 0,953326 3,322 0,001628 0,000447 
-1,578 0,113964 0,942717 3,422 0,001163 0,000311 
-1,478 0,132845 0,930296 3,522 0,000822 0,000214 
-1,378 0,153312 0,915898 3,622 0,000576 0,000146 
-1,278 0,175173 0,899375 3,722 0,000399 0,000099 
-1,178 0,19816 0,880602 3,822 0,000274 0,000066 
-1,078 0,221932 0,859483 3,922 0,000186 0,000044 
-0,978 0,246083 0,835963 4,022 0,000125 0,000029 
-0,878 0,270148 0,810028 4,122 0,000083 0,000019 
-0,778 0,293615 0,781716 4,222 0,000055 0,000012 
-0,678 0,315946 0,751114 4,322 0,000036 0,000008 
-0,578 0,336592 0,718368 4,422 0,000023 0,000005 
-0,478 0,355019 0,683675 4,522 0,000015 0,000003 
-0,378 0,370728 0,647285 4,622 0,000009 0,000002 
-0,278 0,383281 0,609494 4,722 0,000006 0,000001 
-0,178 0,392315 0,570639 4,822 0,000004 0,000001 
-0,078 0,397568 0,531086 4,922 0,000002 0,000000 
0,022 0,398885 0,491224 5,022 0,000001 0,000000 
0,122 0,396219 0,451449 5,122 0,000001 0,000000 
0,222 0,389657 0,412157 5,222 0,000000 0,000000 
0,322 0,379391 0,373726 5,322 0,000000 0,000000 
0,422 0,365721 0,336513 5,422 0,000000 0,000000 
0,522 0,349034 0,300835 5,522 0,000000 0,000000 
0,622 0,329795 0,266971 5,622 0,000000 0,000000 
0,722 0,308515 0,235147 5,722 0,000000 0,000000 
0,822 0,285736 0,205538 5,822 0,000000 0,000000 
0,922 0,262007 0,178264 5,922 0,000000 0,000000 
1,022 0,237857 0,15339 6,022 0,000000 0,000000 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 47 
 
 
 
CAPÍTULO III. ESTRATÉGIAS DE DISTRIBUIÇÃO. 
 
 
1. INTRODUÇÃO 
 
A questão da estratégia de distribuição é parte do problema logístico. Se é verdade 
que um enfoque tradicional confundia limitava a logística ao tratamento deste, a sua 
importância no processo logístico não pode ser desprezada. Autores importantes 
como Robeson e Copacino (1990), Bowersox (1996), Lambert (1998), abordam a 
questão logística de forma abrangente, mas apenas tangenciam esta questão. 
 
Este texto aborda o problema e apresenta uma abordagem simples proposta por 
Novaes para comparar o custo logístico de selecionar uma estratégia para o envio 
dos produtos. 
 
Em um sentido mais amplo a estratégia de distribuição implica em decisões sobre a 
forma básica de entrega, se direta, ou via intermediários, ou ainda usando 
parcialmente cada estratégia, dependendo de condições do mercado (Yao e Liu, 
2002). A estratégia de distribuição também depende de decisões sobre o modelo 
adotado para o momento de término do produto. Os modelos são o de especulação, 
que termina o produto e espera o momento de distribuí-lo para o mercado e o modelo 
de especulação, que posterga a finalização do produto, acumulando estoques semi-
acabados. (Dornier et alii, 2000). Em geral observa-se uma tendência a redução de 
envios diretos desde a fábrica e a uma crescente importância da distribuição via 
grandes atacadistas ou empresas distribuidoras. 
 
Ballou (1993) cita três tipos de estratégias de distribuição. Uma empresa de produtos 
de limpeza industrial tem quatro plantas. Ela faz uso de armazenagem em cerca de 
100 depósitos públicos (armazéns alugados). A distribuição é feita a partir destes 
depósitos, por transportadores contratados. Os estoques são controlados em 
centralmente por computador. Grandes clientes são abastecidos direto da fábrica por 
caminhões completos. No caso da falta de estoques no depósito, há envios diretos da 
fábrica mesmo com uso de caminhões sem completar a carga. 
 
Uma empresa de produtos químicos para uso industrial, recebe 80.000 pedidos 
anuais. São dez plantas e trinta pontos de distribuição. Para produtos comprados em 
pequenas quantidades e com entrega em 24 horas, havia cinco depósitos próprios e 
nove alugados. A empresa tinha caminhões e vagões ferroviários próprios e os 
usava quando tinha garantia de retorno, ou para transportes especiais. Há uma 
grande proporção de distribuição direta ao cliente. 
 
Um terceiro exemplo é de uma empresa de bens de consumo. Ela tem quatro plantas 
nos Estados Unidos e vende uma grande parte para distribuidores que revendem 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 48 
para varejistas. A empresa usa 50 depósitos públicos. O produto é altamente 
sazonal e os armazéns ficam vazios vários meses ao ano. Por isso questiona-se a 
posse de armazéns. No entanto, como o pedido médio dos distribuidores é de 12000 
lb, que não completa um caminhão, o uso de armazéns, permite consolidar carga 
para envia-la por caminhões completos, aos depósitos e daí para os destinos,com 
veículos menores. Esse tipo de distribuição é típico de produtos de consumo, 
permitindo adaptar a oferta ao tamanho e a freqüência de pedidos de clientes. 
 
O processo de distribuição envolve a formação de estoques. Durante a distribuição 
estes estoques se formam em diversas fases do processo. Após a fabricação dos 
produtos acumulam-se estoques na fábrica. Durante o processo de transporte, 
acumulam-se estoques em pontos intermediários e nos destinos finais, ou nos 
depósitos atacadistas, dependendo qual seja o cliente para o qual é transferida a 
propriedade do estoque (Novaes, 1989). A estas etapas estão associados custos 
como descritos a seguir. 
 
a) Após a Fabricação ocorrem custos de Estoque na Industria 
 
b) Em intervalos dados são realizadas Transferências da Indústria para um Depósito 
de Triagem, incorrendo em Custos de Transporte e estoque em trânsito. 
 
c) Nos Depósitos são feitas operações de: Recepção, Classificação separando os 
produtos por boxes para cada destino, implicando em Custos de Manipulação, abrigo 
e retenção. 
 
d) Na distribuição final ocorrem custos de transporte e estoque em trânsito 
 
e) No estoque no comércio até consumo final também há custos de estoque e 
armazenagem envolvidos. 
 
Há vários tipos de estratégias de transferências e usos de depósitos intermediários. 
Os principais são; 
a) Transferência direta, Produtor-Distribuidor. 
b) Transferência via um depósito de triagem. 
 
Em geral o custo do estoque é obtido calculando o estoque médio no sistema em estudo, em um 
certo período e multiplicando este valor pelo valor do produto em estoque. O custo de 
oportunidade relacionado a este valor de estoque é multiplicado pela taxa de juros do mercado. 
Esta abordagem será aplicada a cada tipo de transferência 
 
 2. CÁLCULO DO ESTOQUE MÉDIO NA TRANSFERÊNCIA INDUSTRIA - 
DISTRIBUIDOR 
 
Aqui é analisada a transferência direta industria-cliente sem uso de instalações intermediárias 
do tipo depósito ou armazém (figura 1). 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 49 
A B
Transferência
Fabricação (Estoque) (Estoque) Consumo
Estoque em trânsito
 
Figura 1: Esquema da transferência direta fábrica-cliente. 
 
Para analisar o problema definem-se as seguintes variáveis: 
Q : Taxa média mensal de Consumo do distribuidor e de produção na fábrica [t/mês] 
ou [m3/m] 
 
µµµµ : Valor médio unitário do produto [$/ton ; $/m3] 
 
ττττ : Tempo médio de transferência Fábrica - Distribuidor 
 
αααα : Taxa de custo financeiro/mês (juros, despesas de estocagem, outras despesas 
financeiras) 
 
U: Tamanho médio dos lotes de transferência entre A e B 
 
tR : Intervalo de tempo entre remessas [dias] 
 
U = [Consumo médio diário]*[Intervalo entre remessas] = Q/30. tR 
 
A análise do estoque implica em considerar três estágios: na indústria, em transito e 
no destino final. 
 
 
 
 
2.1. ESTOQUE NA INDÚSTRIA 
 
Novaes (1989) analisa uma fábrica com uma produção diária de Q/30 unidades/dia. 
Esta produção transforma-se em estoque, que é acumulado até uma remessa, ou 
envio de tamanho de U unidades. Os envios são realizados com intervalos regulares 
de tR dias. Logo após um envio o estoque na fábrica reduz-se ao valor de um 
estoque de reserva ER. Após tR dias, ou imediatamente antes de um envio, existe um 
estoque máximo de EM unidades, como visto na figura 2. 
 
Tem-se então: 
ER: Estoque de reserva 
 
EM: Estoque máximo 
 
 Estoque 
 
 
 EM 
 
 
 EA 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 50 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 2: Curva de estoque na Fábrica. 
 
Vale: 
 
(1) EM = ER + U 
O estoque médio na fábrica A é E A calculado como: 
 
(2) E
E E
E
U
A
M R
R=
+
= +
2 2
 
 
Mas U é o estoque produzido e acumulado entre dois envios espaçados de tR. Logo 
vale também: 
 
(3) U
Q
t R= 30
 
 
 
 
2.2. ESTOQUE EM TRÂNSITO 
 
ME é Momento de estoque entre t1 e t2 dado pela fórmula: 
 
(4) M E f t d t
t
t
= ∫ ( )
1
2
 
 
Ou simplesmente a área debaixo da curva de estoque em um gráfico estoque x 
tempo. Finalmente, define-se E o Estoque médio no intervalo t1 e t2 como : 
 
(5) E
M E
t t
=
−2 1
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 51 
 
O gráfico do estoque em transito apresentado na figura 4, permite estabelecer a 
fórmula do estoque em transito. Na figura identifica-se: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 4; Gráfico do estoque em transito. 
 
tR é o Intervalo entre remessas. Durante a transferência observa-se o Momento de 
estoque: U*τ 
 
Durante o período tR- τ , não há movimento de produtos e tem-se um Momento 
zero. Logo o estoque médio é: 
 
(6) E E s t o q u e M e d i o E
U
t
T T
R
:
*
=
τ
 
Usando a fórmula (3) de U, chega-se a outra fórmula de estoque médio em trânsito: 
Dado que 
(7) U Q t E QR T= → =3 0 3 0
. τ 
 
2.3. ESTOQUE NO DISTRIBUIDOR 
 
Para estimar o estoque no distribuidor, ou no destino da carga, supõe-se que a taxa 
de produção está ajustada a taxa de consumo que é também de Q/30 por dia: 
 
 
 
 
 
 
 
 
 
 Estoque 
 ! tR ! 
 τ 
U D E 
 
 
 
 
 
Et G H 
 
 C F I 
 
 k k+1 k+2 Tempo 
 
 Estoque 
 
EM 
 
 U 
EB 
 
 
ER 
 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 52 
 
 
 
 
 
 
 
 
 
 
Figura 5: Estoque no destino. 
 
Imediatamente após uma nova remessa o estoque é máximo dado por EM e 
imediatamente antes da chegada do envio o estoque é mínimo dado por ER. 
 
Supõe-se que o estoque mínimo que o distribuidor deseja equivale a um estoque de 
reserva dado por este valor e que o pedido para o envio do lote U é feito de forma a 
que o envio chegue no momento que o estoque atinge este nível. Vale a relação: 
 
 
(8) EM = ER + U 
 
O estoque médio no destino B vai ser então igual ao estoque na origem: 
 
(9) E
E E
E
U
B
M R
R=
+
= +
2 2
 
 
2.4. ESTOQUE MÉDIO TOTAL 
 
O estoque médio total por dia E é a soma dos estoques médios em cada etapa, 
ou: 
 
(10) E E E E E U
Q
A T B R= + + = + +2 3 0
. τ
 
 
 
 
2.5. CUSTO MÉDIO TOTAL DE ESTOQUE POR UNIDADE PRODUZIDA 
 
No mês o estoque médio também vale: E . Sendo α a Taxa mensal de custo 
financeiro, e µ o Valor unitário da mercadoria, o Custo médio mensal do estoque, 
CME, vale: 
 
(11) C M E E= α µ. . 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 53 
Sendo Q a produção Mensal, o custo de estoque por unidade de produção é: 
 
CE : Custo médio de estoque por unidade (ton.). 
 
(12) C E
E
Q Q
E U
Q
R= = + +α
µ α µ τ
.
.
[ .
.
]2
3 0
 
O valor do produto vai depender da situação do produto no mercado. Se o produto 
tem potencial para ser vendido imediatamente, então o valor do produto é o seu valor 
de venda para a empresa. Se, por outro lado, este produto não pode ser vendido 
imediatamente, como é o caso de produtos com alta concentração sazonal (ex: ovos 
de páscoa) o valor do produto é seu custo de produção. Aqui a empresa pode dispor 
de recurso para aplicar no mercado se deixar de produzir o bem. 
 
2.6. CUSTO DE TRANSFERÊNCIA 
 
O custo de movimentação de carga, ou transferência, compõe-se dos custos 
transporte e do custo de cargae descarga nos terminais. 
 
O custo de transporte compõe-se de uma parcela fixa CF ou Custo Fixo, rateado por 
hora de operação [$/hora de operação] e uma parcela variável por quilometro, CKM: 
Custo/Km [$/Km]. No seu livro, Novaes apresenta exemplos deste custo no Quadro 
8.1(Novaes). 
 
Denomina-se d como distância fábrica-distribuidor [Km]. Para ilustrar, supõe-se a 
velocidade média de um caminhão a partir da estimativa de um percurso diário de 
300 Km/dia → V K m h= 3 0 0 2 4/ [ / ] . Supõe-se que o tempo perdido em 
cada terminal na origem e no destino é de 12 hs. Logo o tempo total perdido na 
viagem seria: 
 
τ = +





 = +2 12
300
24 24
12 5
x
d
x
d
horas
.
[ ] 
 
O custo total de transporte, incluindo carga e descarga será: CT: Custo total de 
transferência A→ B 
 
(13) C C W f CF CKM dT D R= + +. [ . . ]τ 
 
Onde CD é o Custo médio de carga/descarga $/ton 
 
W: Capacidade de carga: 1 veículo 
 
τ : Tempo total de viagem 
 
fR: Fator de custo p/ retorno vazio (fR = 1.5), para compensar o fato de que o 
caminhão retorna vazio, em geral. 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 54 
 
Na realidade interessa o custo de transferência por unidade de produção, em geral 
por tonelada. 
 
Novaes segue exemplificando: 
 
Para um custo de carregamento de CD = 300 $/ton e uma distância variável de d= 
500 a 3.000 Km, Novaes constrói curvas de custo usando regressão. E chega a 
seguinte fórmula: 
 
(14) CT = a0 + a1 . W
b 
 
Onde a0 , a1 , b são coeficientes da regressão. Observa-se que como W
b, há 
economias de escala para valores de b < 1.0. 
Tabela 1: Parâmetros de custo de transferência para diferentes distâncias. 
 
Dada a fórmula anterior, o custo médio de transferencia por tonelada de transporte 
será: 
 
C C u s t o u n i t a r i o m e d i o t o n
C
W
T
T
= =[ $ / ] 
 
(15) bT W
a
W
a
C
−
+=
1
10 
 
 
Na prática o custo de estoque pode ser aproximado para: 1
0 a
W
a
C T += 
 
 
A figura 6 ilustra a forma das curvas. Ela indica que para uma quantidade w de carga 
fixa, o custo sobe com a distancia. Por sua vez, para uma distancia fixa, o custo cai 
com o aumento da carga indicando ganhos de escala. 
 
 
 
 
 
 
 
 
 
d a0 a1 b R
2 
500 5000 7090.7 0.590 0.975 
1000 9000 11145.4 0.594 0.973 
2000 18000 18148.9 0.615 0.971 
3000 26000 26253.4 0.611 0.970 
 CT 
 5 
 
 4 
 
 3 D=3000 Km 
 D=2000 Km 
 2 
 D=1000 Km 
 1 
 
 5 10 15 20 W 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 55 
 
 
 
 
 
 
 
Figura 6: Curvas de custos unitários de transporte por faixas de distancia. 
 
Uma outra forma de abordar custos de transferência (Daganzo, 1995) é definir uma 
função de custo como; 
 
(16) CT = cf + cv*U 
 
Aonde cf é um custo fixo e cv um custo variável por tonelada transportada. 
 
Nessa hipótese o custo de transferência por unidade seria: 
 
(17) C
cf
U
cvT = + 
 
2.7. CUSTO MÉDIO TOTAL DE ESTOQUE E MOVIMENTAÇÃO 
 
O custo médio total de estoque e movimentação, por unidade de produção é então, 
segundo Novaes: 
 
(18) C C C
Q
E U
Q a
W
a
W
E T R b= + = + + + + −
α µ τ
[ .
.
]2
3 0
0 1
1 
 
Sendo W a capacidade do veiculo ou tonelagem máxima. Repare-se que W não é o valor do 
lote transportado e pode-se verificar a relação entre lote U e tonelagem transportada por 
veículo. 
 
W = U se U ≤ 25 ton. 
 
W = U/N se U ≥ 25 ton. 
 
N = Round [U/W]; onde round significa o valor inteiro superior da divisão 
 
U: tamanho do lote. 
 
Cálculo do lote econômico 
O lote econômico é aquele que minimiza os custos médios totais. Dada a função F de 
custo, pode-se obter este valor fazendo 
∂
∂
C
U
= 0 . Porém na fórmula do Novaes, F 
é descontínua. Fazendo hipóteses simplificadoras: 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 56 
 
Se W = U e b = 1, a fórmula de custo total torna-se: 
 
(19) C
Q
E U
Q a
U
aR= + + + +
α µ τ
[ . ]2
3 0
0
1 
 
Agora se pode calcular a derivada com respeito a U e igualar zero: 
 
∂
∂
α µC
U Q
a
U
= − =02 0 
 
chega-se a: 
 
(20) U
a Q
=






0
1
2
α µ 
 
Com a outra fórmula (17) de custo unitário de transporte em função da tonelagem, a 
fórmula de custo total fica, sem simplificações: 
 
 
(21) C
Q
E U
Q cf
U
cvR= + + + +
α µ τ
[ . ]2
3 0
 
 
A derivada com respeito a U, igualada a zero fica: 
∂
∂
α µC
U Q
c f
U
= − =2 0 
 
E o lote ótimo é dado por: 
 
(22) U
cf Q
=






α µ
1
2
 
 
Esta fórmula é do mesmo tipo da fórmula 20, permitindo interpretar a0 como um custo 
fixo de transporte. 
 
2.8. EXEMPLO 
 
Pede-se para calcular o Lote econômico em função de µ, Valor unitário de carga e d, 
distancia. Novaes varia parametricamente o valor de D. É dado também: 
 
α = 16% /mês 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 57 
Q = 100 ton/mês 
 
Os parâmetros a0, a1, b são tirados da tabela 1. 
 
O estoque de reserva ER é igual a 10 ton. 
 
Pela fórmula observa-se que C min não depende da ER e τ, para configuração dada, 
já que a variável U não aparece nas parcelas aonde ER e τ, aparecem, 
desaparecendo no cálculo de 
∂
∂
C
U
= 0 
 
C
E
Q
U
Q
a
W
a
W
R
b= + + + + −2 30
0 1
1.
.α µ α µ α µ τ
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 7: Curvas de custo mínimo em função de U, d e µ. 
 
Na figura 7 observa-se que para um d fixo, quanto maior o valor de µ menor é o lote 
econômico U. Ou seja, quanto maior o valor da carga, mais vale a pena enviar por 
lotes menores, com maior freqüência. Por outro lado para um µ fixo, quanto maior d 
maior o lote econômico U. Ou seja, para um valor de carga dado, quanto maior a 
distancia maior deve ser o tamanho do lote, o que implica em envios de maior volume 
e menor freqüência relativa. Isto explica o uso de Caminhões mais pesados na longa 
distância 
 
3. DISTRIBUIÇÃO VIA DEPÓSITO DE TRIAGEM 
 
Quando há grandes volumes a serem transferidos a opção de realizar a transferência 
direta da fábrica ao destino parece a mais viável. Quando os lotes de envio, ou os 
volumes, são relativamente pequenos sem preencher um veículo, a opção de fazer o 
envio via um depósito de triagem pode ser mais vantajosa. Esta opção pode ocorrer 
usando uma transportadora, que tenha depósitos de triagem, ou a frota e o depósito 
da própria empresa, se for o caso (figura 8) 
 
 
 U 
 
 2000 
 
! 
 
 1000 
 
| 
 
 500 Km 
 
 
 
 
 A � � B 
ESTOQUE 
 COLETA TRANSFERENCIA DISTRIBUIÇÃO 
 Depósito 1 Depósito 2 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 58 
 
 
 
 
 
 
Figura 8: Esquema de transferência via um depósito de triagem. 
 
A transferência via depósito de triagem, apresenta algumas vantagens: 
 
I) Há ganhado de custos na consolidação de lotes de vários clientes. Isto conduz a 
um menor custo por tonelada transportada. 
 
II) Há um ganho por adensamento de pontos na região de coleta. Isto vai provocar 
um melhor desempenho, pela menor distancia média entre pontos de entrega. 
 
Por outro lado aumentam os custos de movimentação de carga nos depósitosintermediários. A questão é saber se os maiores custos são compensados com os 
ganhos. 
 
As variáveis usadas na análise são (figura 8): 
 
Q1: fluxo médio mensal de produtos entre pontos A e B [t/mês] ou [m3/m] 
 
Q2: fluxo médio mensal de produtos dos demais clientes juntos. 
 
µµµµ : Valor médio unitário do produto [$/ton; $/m3] 
 
ττττ : Tempo médio de transferência Depósito 1- Depósito 2. 
 
αααα: Taxa de custo financeiro/mês (juros, despesas de estocagem, outras d. f) 
 
U: Tamanho médio dos lotes de transferência entre A e B 
 
t: Intervalo de tempo entre remessas sucessivas na zona de destino[dias] 
 
tA: tempo de coleta + triagem do produto na origem : do momento da coleta no cliente 
até o despacho no Dep1[horas]. 
 
CA: Custo médio de coleta mais triagem na origem[$/ton ou $/m
3] 
 
CT: custo unitário de transferência.[$/ton] 
 
tB: tempo de triagem e distribuição final [horas] 
 
CB: Custo médio de triagem no Dep2 e distribuição final [$/ton]. 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 59 
A abordagem supõe que Q1 é muito menor que Q2. Logo o custo médio de transferir 
Q1+Q2 é praticamente o mesmo de transferir Q2. A contribuição de Q1 é desprezível. 
Aqui usaremos Q, no lugar de Q1 e Q2 não será considerado nas fórmulas. 
 
Para a transferência direta o custo é, como já foi visto: 
 
C C C
Q
E U
Q a
W
a
W
E T R b= + = + + + + −
α µ τ
[ .
.
]2
3 0
0 1
1 
 
Via depósito de triagem, o custo se calcula como se segue 
 
3.1. CUSTO MÉDIO DE ESTOQUE 
 
No tempo de estoque em transito entram três parcelas: ta+ τ + tB.. A fórmula fica: 
 
(24) C E
Q
E U
Q t t
R
A B= + +
+ +α µ τ
[ .
. ( )
]2
3 0
 
O intervalo entre envios entre A e B, por parte do transportador é t . O intervalo de 
envios por parte da fábrica deve ser um valor inteiro de t, já que a fábrica deve se 
ajustar a programação do transportador. Se o transportador envia a cada semana, a 
fábrica vai enviar cada semana, ou a cada duas semanas, ou três semanas, etc. 
 
tR= K*t (K inteiro). 
 
logo o tamanho do lote será: 
 
(25) U
Q
K t= 1
30
* * 
 
Então a fórmula de custo médio de estoque fica: 
 
(26) ]
30
).(
**
30
.2[ BAR
ttQ
tK
Q
E
Q
CE
++
++=
τµα
 
 
3.2. CUSTOS DE TRANSPORTE 
 
O custo médio de distribuição mais transporte é: 
 
CTT = CA + CT + CB 
 
3.3. CUSTO MÉDIO TOTAL 
 
O custo unitário total é: 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 60 
 
C CE CTT= + 
 
Repare que o custo de transporte não depende de U. Logo o custo mínimo é dado 
para o envio com periodicidade igual ao do transportador (k=1). 
 
O mínimo custo médio unitário de estoque é: 
(27) ]
30
).(
*
30
.2[ BAR
ttQ
t
Q
E
Q
CE
++
++=
τµα
 
 
E o custo unitário total é: 
(28) BTA
BA
R CCC
ttQ
t
Q
E
Q
C +++
++
++= ]
30
).(
*
30
.2[
τµα
 
Com esta fórmula pode-se comparar os custos de transferência direta e o de 
transferência via depósito e optar pela forma de menor custo. 
 
3.4. EXEMPLO 
 
Novaes apresenta um problema, aonde vai variando o custo unitário do produto µ e o 
volume produzido mensalmente Q, para uma distancia de 1000 Km. Para um dado 
veículo define o fluxo de transição entre alternativas de transportar diretamente ou via 
depósito de triagem. O fluxo de transição é aquele para o qual, dado um valor de µ 
fixo, o custo de enviar de uma ou outra forma é igual. 
 
Pela figura 9 observa-se o seguinte: 
 
Para baixos valores de Q e µ, a melhor opção é via o depósito de triagem. Para altos 
valores de Q e µ, é mais vantajoso enviar direto da fábrica para o cliente. 
 
O fluxo de transição cai quando µ cresce, ou seja: para a distancia fixa, quanto maior 
o valor da carga, menor o volume para o qual é melhor enviar via depósito de triagem. 
Isto é intuitivo, uma vez que o envio via depósito tende a ser mais demorado e o 
custo do estoque imobilizado aumenta. Por outro lado, para um µ fixo, quanto maior a 
distancia, maior a vantagem de se enviar por depósito de triagem. 
 
Evidentemente o critério de custo não é o único a ser considerado. Outros fatores, 
como a segurança contra roubos e avarias e a confiabilidade com relação ao tempo 
total de viagem, são também importantes. 
 
 
 
 
 
 
 
 
 150 Q 
 
 D=1000 Km 
 
 100 
 Direto da Fábrica 
 
 � 
 
 50 
 Via Depósito. � 
 
 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 61 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 9: Fluxo de transição entre enviar direto, ou via depósito de triagem. 
 
 
 
 
 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 62 
 
 
 
 
4. QUESTÒES 
 
1. Descreva, em linhas gerais as etapas e os custos do processo de distribuição. 
 
2. Para o problema de distribuição direta da indústria para o distribuidor, defina os 
tipos de estoque. 
 
3. Defina Momento de estoque, estoque médio e use os conceitos para definir 
estoque em transito. 
 
4. Explique a fórmula de estoque médio por unidade. 
 
5. Como se chega a fórmula de Custo unitário médio de transporte 
 
6. Defina lote econômico e explique a fórmula para calculá-lo. 
 
7. Descreva o problema de distribuição via depósito de triagem. 
 
5. BIBLIOGRAFIA 
 
Novaes, A Galvão. Sistemas Logísticos. Ed. Bluecher, 1989. 
 
Yao, D, Liu, J. Chanel redistribution with direct selling. European Journal of 
Operational Research. (uncorrected proof). 
 
Robeson, J. F., Copacino, W.C. The Logistics Handbook. The Free Press. 1995 ?? 
 
Lambert, D.M, Stock, J.R., Ellram, L.M. Fundamentals of Logistic Management. 
Mcgraw-Hill International Editions. 1998. 
 
Bowersox, D. , Closs, D.. Logistical Management. Mcgraw-Hill International Editions. 
1996. 
 
Dornier, P, Ernst, R, Fender, M.; Kouvelis, P. Logística e operações Globais. Editora 
Atlas, 2000. 
 
Daganzo, C. Logistics system anlaysis. Springer, 1995. 
 
Ballou R. H. Logística Empresarial. Ed Atlas. 1993. 
 
 
 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 63 
Capítulo IV. ROTEIRIZAÇÃO DE VEÍCULOS 
 
1. INTRODUÇÃO. 
 
A roterirização de veículos é um problema logístico associado a redes de transporte. 
Trata-se de definir a melhor rota para a execução de uma tarefa de coleta ou 
distribuição de produtos, ou de prestação de serviços. Pelo fato de se tratar de um 
problema associado a redes de transporte, o seu estudo exige o conhecimento básico 
de alguns conceitos sobre grafos e redes. 
 
2. DEFINIÇÕES. 
 
Uma rede de transporte pode ser representada por um Grafo. Um grafo é definido 
como : 
 
Grafo G (N, A) N, conjunto de Nós 1, 2, .... , 6 
 A, conjunto de : Arcos (1, 2); (2, 3) ... (5, 6) 
 
Este capítulo faz usos de conceitos introduzidos no capítulo I: 
 
O Semi-grau interior; Semi-grau exterior e Grau de um nó. 
 
Caminho, circuito, cadeia e ciclo. 
 é um caminho cujo nó final coincide com o nó inicial 
 
Um Grafo fortemente conectado ; grafo conectado. 
 
Subgrafo G’ (N’, A’) e Grafo parcial G’ = (N, A’). 
 
Árvore de um grafo, não orientado: um grafo parcial, conectado e sem ciclos. 
 
Árvore completa (estendida) em G(N,A) é uma árvore que cobre todo o conjunto de 
nós N. Então para N nós vão existir n - 1 arcos na árvore estendida. 
 
3. COBERTURA DE VIAS 
 
O problema de cobertura de vias se aplica a casos em que é necessário percorrer 
cada via, pelo menos uma vez. Em geral é interessante realizar a tarefa, com um 
custo total mínimo. Exemplos de aplicação são: 
 
Coleta de Lixo: Percorrer Redes 
Entrega Postal (Correio) 
Limpeza de Ruas 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal64 
Este problema foi tratado por EULER ao tentar resolver o Problema das 7 pontes de 
Königsberg. O problema consistia em passar uma procissão pelas 7 pontes da 
cidade, passando apenas uma vez em cada ponte. Euler não pode resolver o 
problema, que era insolúvel, mas descobriu as propriedades básicas do problema. O 
problema foi resolvido, anos mais tarde, em uma publicação da revista Chinese 
Mathematics e é conhecido como o Problema do carteiro chinês (PCC). 
 
O problema se enuncia como: Dado um Grafo não orientado G(N,A); arcos com 
extensão l(i, j) > 0 Encontrar um percurso que cubra todos os arcos de G pelo menos 
uma vez e que tenha extensão mínima. Sendo L a extensão total do percurso tem-se: 
 
 ∑=
∈∀ A)j,i(
)j,i(l.)j,i(nL 
 
onde n (i, j) significa: No de vezes que arco (i, j) é percorrido 
 
Usam-se algumas definições de Euler: 
 
Roteiro de Euler: Ciclo que atravessa todos os arcos de G somente uma vez. 
 
Caminho (Cadeia) de Euler: Cadeia que cobre todos os arcos somente uma vez. No 
inicial ≠ nó final. 
 
Lembra-se a definição de Grau de um nó como o Número total de arcos incidentes 
ao nó. Com estas definições apresenta-se os teoremas que permitem resolver o 
problema. 
 
TEOREMAS DE EULER: 
 
Um grafo conexo G (não orientado) possui um roteiro de Euler (ciclo de Euler) se e 
somente se não contiver nenhum nó impar. 
 
Um grafo conexo G possui uma cadeia de Euler se e somente se G contiver 
exatamente dois nós de grau impar. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 2 3 
 
 
 
 
 
 1 4 
 
 
 
 
 2 4 
 
 3 
 
 
 
 1 5 
 
 
 6 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 65 
 
Figura 1: Grafo para um roteiro de Euler. Figura 2: Grafo para uma 
cadeia de Euler. 
 
Na figura 1 observa-se que todos os nós tem grau par e que um dos roteiros de Euler 
possíveis é: 
 
1-4-3-1-2-3-1 (pelo arco externo). 
 
Neste problema a restrição á passar por cada arco uma vez, podendo-se passar por 
um nó mais de uma vez. O nó final é igual ao nó inicial do roteiro, o que define um 
ciclo. Repare que não se leva em conta a orientação dos arcos. 
 
Na figura 2 os nós 2 e 4 tem grau impar, logo não é possível um roteiro de Euler. No 
entanto, como existem apenas dois nós de graus impar, pode-se fazer uma cadeia de 
Euler, que pode ser: 
2-1-5-6-1-3-5-4-3-2-4. 
 
No caso do roteiro de Euler o nó final é diferente do nó inicial. 
 
Um outra propriedade é necessária para resolver o PCC : 
 
O no de nós de grau impar em G é sempre par. 
 
3.1 Solução do Problema do Carteiro Chinês 
 
Trata-se de definir um Roteiro saindo do depósito e cobrindo todos os arcos da rede 
com custo mínimo. Um Roteiro de Euler nem sempre viável, então alguns arcos 
usados mais de uma vez. O procedimento é o seguinte: 
 
Identificar na rede os nós com grau impar. Criar arcos fictícios ligando pares de nós 
impares formando uma rede G’(N, A’). Os arcos artificiais ligando diretamente os nós 
impares, são na verdade percursos que usam mais de uma vez algum arco já usado. 
Na definição das ligações entre pares de nós de grau impar coloca-se a questão de 
qual conjunto de arcos artificiais dá extensão total mínima. Os passos do 
procedimento são os seguintes: 
 
PASSOS: 
 
a) Identificar os nós grau impar em G. Sejam “m” nós (m : par). 
 
b) Determinar combinações possíveis e ligação de cada par de nós de grau ímpar. 
 
c) Selecionar combinação com menor extensão de arcos artificiais criando a rede G’ 
(N, A’). 
 
Definir roteiro de Euler em G’ que vai ser a solução ótima para o problema do carteiro 
chinês. 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 66 
 
 Extensão total encontrada é: 
 
 ∑ ∑+
∈ −∈A)j,i( )A'A()J,I(
)j,i(l)j,i(l 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 3: exemplo para o problema do carteiro chinês. 
 
 
O exemplo da figura 3 tem 8 nós de grau ímpar. O número total de combinação 
possível de pares é: 
 
 
 ∏ −=
−
2
m
1i
)1i2(Nc 
Para m = 8 , tem-se Nc = 105 combinações possíveis de pares de nós. Combinar 
dois pares para criar um arco artificial ligando-os, significa encontrar uma caminho 
mínimo entre estes nós, que será percorrido na solução do roteiro de Euler. Os arcos 
pertencentes a este caminho mínimo serão percorridos mais de uma vez na solução 
final. Havendo mais de um par de nós trata -se de encontrar uma combinação de nós, 
dois a dois, cuja soma dos caminhos mínimos entre os nós de cada par, seja a 
mínima. A solução do problema pode ser por programação matemática, encontrando 
a combinação de pares que resulta na distancia mínima total, ou por um método 
aproximado manual, que forneça uma boa combinação de pares. 
 
 
 
 
 C E J K 
 
 
 
 
 B D F I 
 
 L 
 
 
 A G H M 
 
 Nó de grau ímpar. 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 67 
Uma solução é dada pela combinação de pares de nós da figura 4, mostrada por 
linhas tracejadas. A solução do roteiro de Euler sobre a nova rede é: 
 
 
 A - B - C - E - J - K - L - M - H - M* - L* - 
 I - H - G - F - I - J - E* , D, B, D*, F , G*, A 
 
Observa-se que no caso da seqüência H-M*-L*, os arcos H-M e L-M foram percorrido 
duas vezes. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 4: Solução do problema do carteiro chinês. 
 
 
4. PROBLEMA DO CAIXEIRO VIAJANTE (P.C.V.). 
 
Vimos um problema de tentar passar por todos os arcos de uma rede, que é o 
problema do certeiro chinês. Outro problema importante trata de passar por todos os 
NÓS de uma rede com um percurso de custo mínimo. É o problema do caixeiro 
viajante (Traveling Salesman Problem. TSP) 
 
Tem-se uma rede com N nós. Deve-se sair de uma base, ou depósito e passar pelo 
menos uma vez para cada nó e retornar à base. Este problema ocorre na 
Distribuição Física de Produtos e em certos Roteiros de Serviços (ex. Telemar). Há 
métodos exatos para resolver o problema que são pouco eficientes por isto faz-se 
uso de procedimentos heurísticos. 
 
Supõe-se as seguinte simplificações: 
 
 
 C E J K 
 
 
 
 
 B D F I 
 
 L 
 
 
 A G H M 
 
 - - - - - - - - :ARCOS ARTIFICIAIS. 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 68 
Parte-se de um ponto, visita-se n-1 nós e retorna ao ponto inicial. Com n Pontos tem-
se uma rede conectada com arcos, cada um com um custo l(i, j) 
 
a) Hipótese de desigualdade triangular . supõe-se que : 
 l (i, j) ≤ l (i, k) + l (k, j). 
Ou seja ao caminho direto entre dois pontos é sempre igual, ou melhor que caminhos 
indiretos. 
 
b) As distâncias são simétricas : l (i, j) = l (j, i) ∀ i,j 
 
O Procedimento heurístico para a solução parte do Grafo G(N, A) e segue os 
seguintes passos: 
 
a) Determinar árvore de extensão mínima ⇒ T 
Separar No nós de Grau Impar (No par). Combinar estes nós dois a dois. Escolher a 
seleção com extensão total mínima. Tem-se o grafo Grafo M (Só os nós e arcos 
de ligação). 
 
O Grafo T ∪M = H admite um roteiro de Euler 
 
Encontrar um roteiro de Euler em H que é a primeira solução aproximada para P.C. 
 
b) Melhora-se a solução através de Identificar os Nós visitados mais de uma vez e 
estudar substituição de percursos triangulares para ligações diretas . 
 
segundo LARSON E ODONIa Solução Heurística é apenas cerca de 10% acima do 
mínimo. 
 
A figura 5 apresenta um exemplo com 8 nós a serem visitados a partir de um 
depósito D. Determinada a árvore de extensão mínima, os nós de grau ímpares 
estão marcados na figura. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 2 3 
 
 
 
 1 4 
 
 
 
 5 7 
 
 
 6 
 8 
 Grafo T D 
 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 69 
 
 
 
 
Figura 5: Árvore de extensão mínima para o problema de TSP. 
 
A ligação dos pares de nós de grau ímpar é dada na figura 6. A figura 7 apresenta o 
roteiro de Euler no grafo T+M. A figura 14 apresenta a solução melhorada. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 6: Ligação de pares de nós de grau ímpar. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 2 3 
 
 
 
 1 4 
 
 
 
 5 7 
 
 
 6 
 
 T + M 8 D 
 
 
 
 
 
 2 3 
 
 
 4 
 1 
 
 
 5 7 
 
 6 
 
 8 D 
 
 
 2 3 
 
 
 4 
 1 
 
 
 5 7 
 
 
 6 
 
 8 D 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 70 
Figura 7: Roteiro de Euler no grafo T+M. Figura 8: Solução 
melhorada 
 
A solução melhorada considera por exemplo que : 
 
l14 < l15 + l54 , 
l12 < l14 + l42 , 
l7D < l76 + l6D . 
5. ROTEIRIZAÇÃO COM RESTRIÇÕES MÚLTIPLAS. 
 
O problema do caixeiro viajante PCV não considera restrições do tipo tempo ou 
capacidade. Em muitos casos reais de distribuição física esta é uma restrição 
determinante. O método anterior não se aplica inicialmente. É necessário antes 
identificar subconjuntos de nós que atendidos respeitem a às restrições. Cada grupo 
ou subconjunto de nós deve ser atendido em uma viagem de um veículo. Se o serviço 
é simultâneo, cada grupo de nós representa um roteiro servido por um veículo. Para 
encontrar esta solução inicial faz-se uso do método de Clarke e Wright, que 
apresenta o conceito de ganho, que é mostrado a seguir: 
 
É dado um depósito D e n pontos a serem servidos com retorno a D. 
 
Um primeira solução evidentemente ineficiente é usar n veículos cada um fazendo 
um roteiro atendendo um ponto. 
 
 Roteiro : D → ponto → D (figura 9) 
 
 
O percurso total desta solução é: 
 
 ∑=
=
n
1i
i,Dl*2L 
 
No entanto, para dois nós i e j, se depois de passar pelo nó i o veículo passar por j 
haverá um ganho (figura 10) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 j 
 
 i 
 
 
 
 D 
 
 
 
 i j 
 
 
 
 
 
 D 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 71 
Figura 9: Solução ineficiente. Figura 10: Solução com ganho. 
 
O Ganho S(i,j) pode ser calculado como: 
 
 S(i, j) = La - Lb = 2 . dD,i + 2. dD, j - [ dD, j + di, j + dj, D ] ou: 
 
 
 S (i, j) = dD, i + dD, j - di, j 
 
 
O procedimento faz uso deste conceito buscando pares de pontos i, j com maior valor 
de ganho e que não violem as restrições de tempo e capacidade. 
 
5.1. Método de Clarke e Wright. 
O método de Clarke e Wright segue os seguintes passos. 
 
a. Calcular ganhos s(i,j) para todo i e j, i≠D, j≠D. 
b. Ordenar pares de nós, na ordem decrescente de ganhos. 
c. Enquanto não terminar a lista de ganhos: Tomar pares i,j na ordem. 
 
Usar o procedimento a seguir, considerando se nós i e j estão, ou não incluídos am 
algum roteiro já existente. Antes de incluir algum nó, testar restrição de tempo e de 
capacidade. 
 
• 1. Se i e j não estão em nenhum roteiro, 
 então criar um roteiro com i e j . (D-i-j-D).(Figura 11) 
 Senão (i, ou j, ou ambos estão em algum roteiro) 
• 2. Se somente um nó, ou i, ou j,está em um roteiro 
 então : 
 se este nó é um extremo de um roteiro, 
 então: agrega i,j ao roteiro. (Figura 12) 
 Senão: (Figura 13) 
 abandona par i,j. 
 Senão: (os dois nós estão em algum roteiro). 
 3. Se i e j estão em roteiros diferentes, 
 então: 
 Se i e j são extremos de seus roteiros: (Figura 140) 
 então: Une os dois roteiros. 
 Senão: Abandona o par i,j. (Figura 15) 
 4. Senão (i e j estão no mesmo roteiro) 
 abandona o par i,j. 
 
Se ao terminar a lista, sobrar algum nó k não incluído em roteiro, criar roteiros 
individualizados: D-k-D. 
 
Deve-se lembrar sempre de fazer os testes para ver se a inclusão, ou união de 
roteiros viola as restrições de tempo e capacidade. 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 72 
 
 
 
 
 
 
 
 
 
Figura 11: Criação de um roteiro. 
Ao se incluir algum par i,j em um roteiro, sendo j o nó já no roteiro, o tempo total de 
percurso do roteiro varia de: tDi + tij- tjD (Figura 18). A este valor se inclui o tempo de 
parada do novo nó (i) na rota. No caso da união de dois roteiros, cada um com um 
tempo atual de TR1 e TR2, o valor do roteiro resultante será: TR1 + TR2 - tjD - tiD + tij. 
(Figura 21) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 12: Inclusão de um par i,j em roteiro existente. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 k 
 
 j 
 i 
 
 
 l 
 
 
 
 
 
 D 
 
 
 
 i 
 
 
 j 
 k 
 
 
 
 l 
 
 
 
 
 
 
 D 
 
 
 i 
 j 
 
 
 
 
 D 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 73 
 
 
 
Figura 13: Não inclusão de par i,j em um roteiro. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 14: Possibilidade de união de dois roteiros através do par i,j. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 15: Impossibilidade de união de dois roteiros pelo par i,j. 
 
 
 
 
 i j 
 b l 
 
 
 Roteiro 2 Roteiro 1 
 m 
 a 
 
 
 
 
 
 
 D 
 
 
 
 i l 
 b j 
 
 
 Roteiro 2 Roteiro 1 
 m 
 a 
 
 
 
 
 
 
 D 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 74 
5.2. Ajuste de tempos de ciclo no procedimento. 
 
Durante o procedimento é necessário calcular e refazer a cada etapa o tempo de 
ciclo da rota recém criada, ou modificada. O tempo de ciclo inclui o tempo do 
depósito ao primeiro ponto da rota, mais o tempo do último ponto da rota ao depósito, 
mais o tempo de percurso entre pontos sucessivos na rota e mais o tempo total 
perdido em paradas nos pontos. 
 
Ao ser criada uma rota com um par de pontos i,j, o tempo de ciclo fica: 
TC = tDi + tij + tjD + 2tp 
 
Ao ser incluído um par qualquer j,k a uma rota já existente, aonde o nó j já pertence 
à rota, o novo tempo de ciclo da rota fica: 
TC’ = TC - tjD + tjk + tkD + tp. 
 
E ao serem unidas duas rotas através do par i,j, sendo i em uma rota e j em outra 
rota, o novo tempo de ciclo parte dos tempos de ciclo TC1 e TC2 das rotas 
existentes: 
 
TC = TC1 + TC2 -tiD - tjD + tij 
 
É importante eventualmente, aproveitar a informação já contida no cálculo dos 
ganhos. Se o ganho for calculado em tempo e não em distancia, os cáculos ficam: 
 
Para o cáculo de uma nova rota com o par i,j e ganho Sij. 
 
TC = Sij + 2*tij + 2*tp. 
 
Para o novo valor de tempo de ciclo de uma rota na qual se incluiu o nó j, ligado pelo 
par i,j a i. 
 
TC’ = TC - Sij + 2*tjD + tp 
 
Para a união de duas rotas: 
 
TC= TC1 + TC2 - Sij, 
 
 
 
 
 
 
 
 
 
 
 
 
 
 2 
4 6 
 
 1 
 3 
 
 5 
 
 
 D 
 
Dimensionamento deSistemas Logísticos. José Eugenio Leal 75 
Figura 16: Exemplo para o problema de roteirização com restrições 
 
 
5.3. Exemplo. 
 
Novaes (1989) apresenta uma aplicação com um grafo de 6 Pontos e um Depósito. 
(figura 16) 
 
O veículo tem capacidade para 6 ton. O tempo de ciclo TC é igual a 12h e em cada 
parada o tempo perdido é tp = 1,5 h . A velocidade média do veículo é: V = 60 
Km/h. As coordenadas de cada ponto e a carga a ser transportada são dadas a 
seguir. 
 
 
 
Nó X Y Carga (t) 
0 0 0 0 
1 14 40 3,0 
2 10 83 2,7 
3 27 60 0,9 
4 67 80 1,2 
5 80 57 0,8 
6 90 93 2,6 
 
O primeiro passo é ordenar calcular os ganhos de cada par de arcos e ordená-los em 
ordem decrescente. 
 
 Ganhos Ordenados (em km) 
 
 ARCOS GANHO ARCO GANHO 
1 4,6 248,8 9 3,5 133,1 
2 5,6 228,3 10 2,5 128,6 
3 4,5 211,4 11 1,3 101,2 
4 2,6 158,9 12 1,2 99,3 
5 2,4 157,0 13 1,4 96,4 
6 3,4 150,0 14 1,6 95,0 
7 3,6 148,9 15 1,5 86,9 
8 2,3 144,9 
 
A matriz de tempos de viagem em horas é a seguinte: 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 76 
De/Para 1 2 3 4 5 6 
0 0.85 1.67 1.32 2.09 1.96 2.59 
1 0.00 0.86 0.48 1.33 1.36 1.85 
2 0.86 0.00 0.57 1.14 1.49 1.61 
3 0.48 0.57 0.00 0.89 1.06 1.42 
4 1.33 1.14 0.89 0.00 0.53 0.53 
5 1.36 1.49 1.06 0.53 0.00 0.75 
6 1.85 1.61 1.42 0.53 0.75 0.00 
 
Seguindo os passos do procedimento tem-se: 
 
1. ROTEIRO: inclui o primeiro arco da lista. D- 4 - 6-D. Lembrar que todo roteiro se 
inicia e termina no depósito. 
 
A seguir vão sendo tomados os outros arcos da lista: 
 
 Arco 5 - 6. Tem um nó comum que é extremo do roteiro atual. Pode 
incluir. Antes tem que verificar o TC e a carga total. 
 TC (D-4 - 6 - 5-D) = 9,8 h ok 
 carga = 1,2 + 2,6 + 0,8 = 4,6 ok 
 
novo roteiro 1: D- 4 - 6 - 5-D 
 
 Arco 4,5. Nós já incluídos no roteiro. Abandona o par de nós. 
 
 Arco 2,6 : O Nó 6 não é extremo do roteiro atual. Abandona. 
 
 Arco 2,4 : O nó 4é nó extremo. Verifica-se as restrições: 
 TC: (D-2 - 4 - 6-5-D) = 12,1 > TC adm. 
 TON: 4,6 + 2,7 = 7,3 → Abandona o arco 2,4. 
 
 Arco 3,4 : O 4 nó é extremo. Verificação das restrições: 
 TC = 11,5 ok ; TON = 4,6 + 0,9 = 5,5, OK. 
 
O NOVO ROTEIRO é : D- 3 - 4 - 6 - 5-D 
 
 Arco 3,6: Nós já no roteiro. Abandona o par. 
 
 Arco 2,3: Poderia entrar, mas TC > TC adm. 
 
 Arco (1, 2). Os dois nós estão fora do roteiro. 
 
 Cria-se um Novo Roteiro 1,2. Verificação de restrições. 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 77 
 TC = 6,4 h TON = 5,7 ton 
 
 Arco 1,4 : Tem um nó em cada roteiro. Poderia permitir a ligação dos dois 
roteiros. No entanto isto conduziria a violação das restrições de tempo e capacidade 
 
O resultado final são dois roteiros (figura 17): 
 
 1 : D - 3 - 4 - 5 - 6 - D Carga = 5,5 ton; TC = 11,5 h L = 327 
Km 
 2 : D - 1 - 2 - D Carga = 5,7 ton TC = 6,4 h L = 203 Km 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 17: Solução final do problema de roteirização com restrições. 
 
 
6. ROTEIRIZAÇÃO COM JANELAS DE TEMPO. 
Método do vizinho mais próximo. 
 
Trata-se de definir um conjunto de roteiros em que os nós têm que ser visitados 
dentro de uma janela de tempo (JT) que se inicia em Inii e termina em fimi. Em cada 
nó há uma perda de tempo devido ao serviço de valor tservi. Como entre cada nó 
existe um tempo de viagem tij, o começo do serviço em cada nó depende do fim do 
serviço no nó anterior mais o tempo de viagem entre os nós. Devem ser respeitadas 
ainda as restrições de tempo de ciclo e de capacidade do veículo. 
 
 
Define-se: 
tij: tempo de viagem entre nós i e j; 
inii: início da janela de tempo no nó i; 
fimi: fim da janela de tempo no nó i; 
tservi: tempo de serviço no nó i; 
 
 2 
 4 6 
 
 1 3 
 
 5 
 
 
 D 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 78 
Começoi: início do serviço no nó i. 
 
Para a otimização usa-se uma distancia virtual que incorpora o tempo de viagem mais 
valores de espera e da folga para o serviço, denominada de urgência. 
 
Calcular a distância com a fórmula: 
 
 
Onde: 
 
 
A espera indica se e quanto tempo o veículo deve esperar em j. 
 
 
A urgencia indica quanto tempo ainda resta para o veículo servir o nó j. 
 
O serviço não pode se iniciar antes do início da JT. 
Então: 
 
 
A viabilidade é definida se o começo é menor que o fim da JT em j. 
 
 
Observa-se que dij depende da urgência e da espera e estes valores dependem do 
começo do serviço no nó anterior. Logo a matriz dij pode se modifificar durante o 
procedimento. 
 
Procedimento do vizinho mais próximo para janela de tempo : 
 
O algoritmo parte do deposito como nó atual. 
Toma o nó atual e busca o nó mais próximo segundo a distancia dij. 
Se chegada j<fimj então incorpora o nó ao roteiro. 
Se não houver nenhum nó que atenda a condição, encerre o roteiro e volte ao 
depósito. 
 
Condições. 
Teste de capacidade: Verificar capacidade do veículo. 
Teste de tempo de ciclo: Verificar sempre se o tempo de partida de j mais o tempo de 
viagem tj-deposito é menor que o tempo de ciclo. 
 
Dados: 
Matriz T de tij. 
 vetor INICIO de início da JT em cada nó 
 Vetor FIM de fim da JT em cada nó. 
 Parâmetros α, β e γ. 
 
Supõe-se inicialmente vetor COMEÇO=INICIO. 
 Calcula-se as matrizes ESPERA e URGENCIA, com valores provisórios de 
COMEÇO. 
jjijij urgenciaesperatd *** γβα ++=
}0),(max{ ijiijj ttservcomeçoinicioespera ++−=
)( ijiijj ttservcomeçoFimurgencia ++−=
.))(,max( viáveléjsettservcomeçoiniciocomeço ijiijj ++=
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 79 
 
Estas matrizes contem os valores de espera e urgencia nos nós j (colunas) quando 
precedidos pelo nó i (linha). 
 
Calcula-se matrizes: 
 α*T, β*ESPERA e γ*URGENCIA. 
 
Calcula a matriz D: 
Dij= α*T+ β*ESPERA + γ*URGENCIA. 
 
Na matriz Dij, a primeira linha correspondente ao depósito já é a correta e pode-se 
selecionar o nó mais próximo. Trata-se do nó ainda não visitado com menor valor de 
dij e com valor correspondente de Urgencia >=0. 
 
Corrige-se o valor de começo do nó atual a partir do começo do nó anterior. Se 
começo é maior que início altera os valores de ESPERA e URGENCIA da linha do nó 
atual. Se mudou começo, atualiza os valores de Dij na linha do nó atual. 
 
Exemplo: São dados os valores de alfa, beta e gama, a matriz de tempo e os demais 
valores de cada nó. 
 
alfa 0,6 
beta 0,2 
gama 0,2 
 
De/par
a 
0 1 2 3 4 5 
0 0 1,68 5,24 2,06 2,83 3,99 
1 1,68 0 5,8 3,39 2,61 4,88 
2 5,24 5,8 0 3,58 3,38 1,54 
3 2,06 3,39 3,58 0 2,7 2,12 
4 2,83 2,61 3,38 2,7 0 2,93 
5 3,99 4,88 1,54 2,12 2,93 0 
Matriz de tempo de viagem tij. 
 
 
Dados dos nós: 
Nó: 0 1 2 3 4 5 
Ini 0 3 4 5 8 12 
FIM 18 5 7 6 10 14 
TSERV 0 1 2 2 1 1 
Carga 0 2 2 2 1 1 
 
 
 
alfa*tij 0 1 2 3 4 5 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 80 
0 0 1,008 3,144 1,236 1,698 2,394 
1 1,008 0 3,48 2,034 1,566 2,928 
2 3,144 3,48 0 2,148 2,028 0,924 
3 1,236 2,034 2,148 0 1,62 1,272 
4 1,698 1,566 2,028 1,62 0 1,758 
5 2,394 2,928 0,924 1,272 1,758 0 
 
 
Matriz dij inicial: 
 
 
Parte do zero: 
 
Menor valor é 1, com urgencia positiva, portanto viável. 
 0 1 2 3 4 5 
 
 
 
Novo começo em 1:Max{Inicio1 ,(começo0 + t01 + tserv0)} 
 
Max { 3, (0 + 1,68 + 0)} max=3 
 
Começo: 0 3 4 5 8 12 
 
 
Começo em 1 ficou como início. Logo a linha de 1 em Dij permanece como antes. 
 0 1 2 3 4 5 
 
 
Urgencia desde 1. 
 
 
Nos zero e 1 já foram visitados, nós 2 e 3 tem urgencia negativa e entre 4 e 5 o 
menor dij é 4 
 
Novo começo em 3: 
Max {8, {3+1+2,61)} = Max(8; 6,61)=8. 
1 4,608 1 4,88 3,234 3,844 6,352
dij 0 1 2 3 4 5
0 3,6 2,072 4,544 2,624 4,532 6,596
1 4,608 1 4,88 3,234 3,844 6,352
2 6,744 4,48 1,4 3,348 4,028 4,816
3 4,836 3,034 3,548 1,2 3,62 4,848
4 5,298 2,566 3,428 2,82 2 4,572
5 5,994 3,928 2,324 2,472 3,758 2,8
0 3,6 0,664 0,352 0,788 1,434 2,002
2,464 0,2 -0,56 -0,278 0,678 1,024
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 81 
Não muda o valor do começo: linhas de dij, espera e urgencia do nó 4 
permanecem como antes. 
 
D5j 
 0 1 2 3 4 5 
 
 
Urgencia desde 5 
 
 
Nós 0,1,4 e 5 foram visitados e não há mais nós com urgencia positiva. 
 
Volta para o depósito. 12+1+3,99= 16,99 < 18 horas 
 
Se muda o valor de começo de algum nó, há mudanças em espera e urgência e, 
eventualmente, em dij. 
 
A variação de começo é: 
 
 
O novo valor de espera é: 
 
 
 
E de urgencia: 
 
 
 
O novo valor de dij será de: 
 
 
 
A segunda parcela só será acrescentada se o novo valor de espera for positivo. 
 
 
A seguir são mostradas as matrizes beta*ESPERA, gama*URGÊNCIA E D, além da 
indicação do valor de começo. 
 
 
 
 
 
 
 
 
beta*espera 0 1 2 3 4 5 começo 
0 0 0,6 1,448 1 1,6 2,4 0 
5,794 3,928 2,524 2,672 3,758 2,8
0,202 -2,576 -1,508 -1,824 -1,186 0,2
01 começocomeçocomeço −=∆
)}(,0max{ 01 começoesperaespera ∆−= β
começourgenciaurgencia ∆−= *01 γ
)0( >∆−∆−= jiiijij esperasecomeçocomeçodd βγ
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 82 
1 0,936 0,8 2,16 1,678 1,6 2,4 3 
2 1,848 2,16 1,2 1,916 1,676 2,4 4 
3 1,412 1,878 2,116 1,4 1,74 2,4 5 
4 2,166 2,322 2,676 2,54 1,8 2,4 8 
5 3,198 3,576 3,108 3,224 3,186 2,6 12 
 
 
 
 
 
gama*urgencia 0 1 2 3 4 5 começo 
0 3,6 0,664 0,352 0,788 1,434 2,002 0 
1 2,464 0,2 -0,56 -0,278 0,678 1,024 3 
2 1,352 -1,36 0,2 -0,716 0,124 1,292 4 
3 1,788 -1,078 -0,716 -0,2 0,06 0,976 5 
4 1,234 -1,322 -1,076 -1,14 0,2 0,414 8 
5 0,202 -2,576 -1,508 -1,824 -1,186 0,2 12 
 
 
dij 0 1 2 3 4 5 começo menor precedente 
0 3,6 2,272 4,944 3,024 4,732 6,796 0 1 0 
1 4,408 1 5,08 3,434 3,844 6,352 3 4 1 
2 6,344 4,28 1,4 3,348 3,828 4,616 4 
3 4,436 2,834 3,548 1,2 3,42 4,648 5 
4 5,098 2,566 3,628 3,02 2 4,572 8 5 4 
5 5,794 3,928 2,524 2,672 3,758 2,8 12 
 
 
 
7. REFERÊNCIAS BIBLIOGRÁFICAS: 
Novaes Antônio Galvão. Sistemas Logísticos. Ed. Bluecher. São Paulo. 1989. 
 
 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 83 
8. QUESTÕES. 
 
1 - Defina grau de um nó i; caminho e circuito. 
 
 2 - Defina árvore e árvore completa (estendida). 
 
 3 - Explique o que significa a expressão 
d(i,j)= Min{ dk-1(i,j) ; dk-1(i,k)+dk-1(k,j) } no algorítimo de Floyd. 
 
 4 - Calcule a árvore de extensão mínima da rede dada em aula. 
 
 5 - Explique as condições para um roteiro (circuito) de Euler e para um caminho de 
Euler. Dê um pequeno exemplo de cada. 
 
 6 - Resolva o problema do Carteiro chinês para a rede dada em aula. 
 
 7 - Defina o problema do caixeiro viajante. Resolva o problema para a rede dada em 
aula. 
 
 8 - Qual a diferença entre o problema do caixeiro viajante e o de roteamento 
(roterização) com múltiplas restrições? 
 
 9 - Explique e exemplifique o conceito de ganho de Clarke e Wright. 
 
10 - Resolva o problema do caixeiro viajante para a rede e os dados do problema 
dado em aula. 
 
11. Encontre uma solução para o problema de roteamento, aplicando o algorítmo de 
Clarke e Wright. São dados 4 pontos de entrega e um ponto de depósito ( o ponto 
zero), com as coordenadas e as cargas dadas na tabela 1. Na matriz estão dados 
os tempos de viagem, em horas, entre os pontos. Suponha tempos simétricos do 
depósito a cada ponto. Calcule, para cada par de pontos, os ganhos em valores de 
tempo a partir da matriz e aplique o algorítmo usando todos os pares de pontos e 
mostrando todos os passos necessários. A capacidade de cada veículo é de 12 ton e 
o tempo de ciclo admissível é de 24 horas. O tempo de parada em cada ponto é de 
1.5 horas. 
 
 
 
 
 
Tabela 1. 
Pont
o 
 X Y Ton 
0 272 189 0 
1 141 232 9 
2 398 
241 
 3 
Dimensionamento de Sistemas Logísticos. José Eugenio Leal 84 
3 275 
119 
 6 
4 392 
162 
 5 
 
Matriz de tempos de viagem, em horas. 
De\Para 1 2 3 4 
0 2.76 2.73 1.40 2.46 
1 0.00 5.14 3.51 5.21 
2 5.14 0.00 3.46 1.58 
3 3.51 3.46 0.00 2.49 
4 5.21 1.58 2.49 0.00