PESQUISA OPERACIONAL - PROBLEMA DE ROTEAMENTO DE VEÍCULOS

Prévia do material em texto

1.3 O Problema de Roteamento de Veículos 
 
Um grande número de aplicações reais já mostrou que a introdução de técnicas de otimização e 
programação matemática para a gestão efetiva da distribuição de bens e serviços, no planejamento do 
processo de distribuição, traz reduções consideráveis no custo total de transporte, geralmente entre 5% 
e 20%. O impacto desta redução como um todo é significativo para a economia, tendo em vista que o 
custo de transporte está relacionado diretamente no processo produtivo e representa de 10% a 20% do 
custo final dos produtos. 
 
Dentre os fatores que contribuíram para o aumento no custo operacional destacam-se o alto custo 
associado aos benefícios da mão-de-obra empregada, os altos custos envolvidos na manutenção da 
frota de veículos e o aumento do nível de serviço exigido pelos clientes. O Problema de Roteamento 
de Veículos (PRV) surge como uma boa opção para dar um suporte às empresas no tocante a 
distribuição dos seus produtos. O PRV apresenta uma enorme dinamicidade, foi proposta a subdivisão 
desta classe de problemas a fim de se estudar de maneira específica algumas destas situações presentes 
em instâncias reais. Uma delas é a consideração da capacidade de carga do veículo e o tempo em que 
os clientes podem ser atendidos (janela de tempo), tendo apenas um depósito central de mercadorias, 
ficando conhecido como Problema de Roteamento de Veículos com Janela de Tempo (PRVJT) que 
pode ser formulado da seguinte maneira: Um conjunto de veículos idênticos, representado pelo 
conjunto V={1, ..., M}, necessita realizar entregas em uma região. Os n clientes dentro desta região 
estão representados pelo conjunto C, que são vértices de um grafo G = (C, A), com A sendo o conjunto 
de arestas. Adicionalmente, incluem-se dois outros vértices, os vértices 0 e n+1 que representam o 
depósito central de onde partirão e chegarão todos os veículos, respectivamente. São dados os tsi, tij e 
cij que representam respectivamente o tempo de serviço usado para descarregar a encomenda no 
cliente i, o tempo e a distância necessários para ir do cliente i ao cliente j. Em se tratando de veículos 
com o mesmo padrão de velocidade, podemos adotar tij = cij. Cada cliente i tem uma demanda, ou seja, 
uma quantidade de encomenda qi. Além disso, cada cliente deverá ser atendido por um único veículo, 
não sendo permitido a divisão de uma encomenda por dois ou mais veículos. Quanto à janela de 
tempo, dada pelo intervalo [ai, bi], indica que a partir do instante inicial ai é permitido o início da 
entrega ou coleta no cliente i. Caso a chegada do veículo no cliente i se dê antes do instante ai, o 
veículo deverá esperar. O veículo nunca poderá chegar depois do instante bi, pois viola a restrição de 
tempo do problema. Este tipo de restrição de tempo é conhecido na literatura como janela de tempo 
rígida ou hard time window. Os veículos são idênticos e possuem uma capacidade máxima de carga K. 
O PRVJT tem como objetivo fazer a entrega da demanda de todos os clientes minimizando a distância 
total percorrida. 
 
O modelo matemático do PRVJT leva em consideração os dados descritos no parágrafo anterior e as 
seguintes variáveis: 
a) rjv é o instante de chegada do veículo v ao cliente j, j=1, 2,..., n; 
 
b) Xijv é uma variável binária definida por 
 





=
contrário. caso , 0
j cliente ao i cliente do ediretament vaiele v veículodo rota na se , 1
X ijv , com v ∈ V e (i, j) ∈ A; 
 
c) W=104×Max{tij} é um número bastante grande. 
 
 
Assim, modelamos o problema da seguinte forma: 
 
(PRVJT) : Minimizar z = ∑∑∑
= =
+
=
M
v
n
i
n
j
ijvij Xc
1 0
1
1
 (1) 
 
 Sujeito a: 
∑∑
=
+
=
∈∀=
M
v
n
j
ijv CiX
1
1
1
,1 (2) 
 ∑∑
==
∈∀=
n
j
ijv
n
i
i VvKXq
11
, (3) 
 ∑
=
∈∀=
n
j
jv VvX
1
0 ,1 (4) 
 ∑ ∑
= =
∈∈∀=−
n
j
n
j
hjvihv ChVvXX
1 1
,,0 (5) 
 ∑
=
+
∈∀=
n
i
ni VvX
1
v)1( ,1 (6) 
 VvCjirXWttsr jvijvijiiv ∈∈∀≤−−++ ,,,)1( (7) 
 VvCibra iivi ∈∈∀≤≤ ,, (8) 
 VvjiGjiX ijv ∈≠∈∀∈ ,,,},1,0{ (9) 
 
Onde: A Função objetiva (1) minimiza a distância a ser percorrida para realizar a entrega das 
encomendas de cada cliente; O grupo de restrições do tipo (2) faz com que somente um veículo faça a 
entrega de um cliente; Em (3) é dado o limite da capacidade de ocupação de cada veículo, não 
ultrapassar K unidades; O grupo de restrições do tipo (4) obriga cada veículo usado na entrega iniciar 
sua rota pelo depósito, enquanto que (6) dar-se-á o retorno ao depósito. As restrições do tipo (5) fazem 
com que o veículo usado na entrega do cliente i dirija-se para um outro cliente ou retorne ao depósito 
central. As restrições (4), (5) e (6) trata de traçar uma rota para cada veículo usado na entrega; O grupo 
de restrições (7) determina que o instante de chegada de um veículo v a um cliente j só poderá ocorrer 
depois do instante finalizado da entrega do cliente imediatamente anterior a j. A constante W torna o 
grupo de restrição (7) verdadeira para qualquer valor de Xijv; As restrições dos tipos (8) e (9) 
determinam os possíveis valores para as variáveis do modelo conforme definidas anteriormente. 
 
Encontrar solução para o PRVJT implica em obter simultaneamente a solução de vários problemas tais 
como o Problema do Caixeiro Viajante (PCV) e o Problema da Mochila (Knapsack Problem), sendo 
conseqüentemente considerado NP-Difícil. Dado que o espaço de busca das soluções dos problemas 
NP-Difíceis não pode ser explorado integralmente em tempo hábil, técnicas de otimização 
combinatória são utilizadas para buscar soluções satisfatórias para tais problemas. A seguir 
descrevemos uma forma de aplicar a Heurística Permutacional no PRVJT, modelando-o como um 
POCP. 
 
Exercício 01: Determine o número de variáveis e restrições do modelo matemático do PRVJT. 
Exercício 02: Crie uma instância do PRVJT com 5 clientes e 5 veículos de tal forma que a capacidade 
de cada veículo não possa alocar mais que duas entregas dos clientes. 
Exercício 03: Modele e determine a solução ótima do PRVJT criado no exercício anterior, 
interpretando a solução ótima encontrada na resolução do modelo matemático do 
problema em questão. 
 
1.3.1 O PRVJT como um POCP 
 
Podemos modelar o PRVJT como sendo um POCP, onde S é o conjunto de todas as permutações 
possíveis dos n clientes. Tendo o primeiro cliente em s prioridade para ser realizada a entrega de toda 
a sua demanda, depois o segundo e assim sucessivamente até que a capacidade do veículo alocado não 
ultrapasse o limite K. Um segundo veículo será alocado para fazer a entrega dos clientes que não 
foram alocadas no primeiro veículo, seguindo a ordem em que os mesmos se encontram em s. Este 
processo se repete até que a entrega de todos os clientes seja alocada aos veículos usados na 
distribuição das demandas. Sabe-se que a entrega de cada cliente deve ser feita dentro da janela de 
tempo, assim também como ser atendida integralmente em um veículo. Desta forma o procedimento g 
usado para avaliar uma solução s de S leva em consideração a ordem em que os clientes se encontram 
na permutação s e o número de veículos utilizados para fazer a entrega das demandas. O procedimento 
g dado abaixo calcula o valor de z do modelo matemático (PRVJT) para a solução s. A solução s será 
inviável quando este procedimento retornar o valor zero para g(s), conforme Linha 13 (o instante de 
chegada do veículo v está fora da janela de tempo do cliente i). 
 
01 Input: s (Uma permutação dos n clientes) 
02 Output: z (custo da solução s) 
03 z=0; 
04 v=1; 
05 custo[v]=0; 
06 i=1; 
07 While (i<=n) do 
08 If a entrega do cliente s[i] cabe em v then 
09 { If s[i] é o primeiro cliente de v then 
10 custo[v]= custo[v] + c0s[i] ; 
11 Else 
12 custo[v]= custo[v] + cs[i-1]s[i];13 If ai≤riv≤bi then Return 0; 
14 if i=n then z= z + custo[v] + cs[n](n+1); 
15 i=i+1; 
16 } 
17 Else 
18 { z= z + custo[v] + cs[i-1](n+1); 
19 v= v +1; 
20 custo[v]=0; 
21 } 
22 Return z 
 
Portanto, mesmo para problemas de grande porte podemos usar a Heurística Permutacional e o 
procedimento acima para determinar soluções do PRVJT, assim como foi feito nos problemas 
anteriores. 
 
Exercício 04: Resolva o problema do exercício 02 usando a Heurística Permutacional e o 
procedimento g dado anteriormente para o PRVJT, comparando o desempenho de 
cada solução gerada por este método com o valor da solução ótima. 
 
Neste capítulo mostramos ao leitor como usar técnicas de Otimização Combinatória para gerar 
soluções de alguns problemas de grande porte existentes na Pesquisa Operacional, quando os mesmo 
são complexos e de difícil resolução computacional de forma exata.