Prod - Mec Engª

Prévia do material em texto

UNIVERSIDADE FEDERAL DA PARAÍBA 
CENTRO DE TECNOLOGIA 
DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO 
CURSO DE GRADUAÇÃO EM ENGENHARIA DE PRODUÇÃO MECÂNICA 
 
 
 
 
 
 
HUGO HARRY FREDERICO RIBEIRO KRAMER 
 
 
 
 
 
 
 
 
 
 
 
FORMULAÇÕES MATEMÁTICAS PARA O PROBLEMA 
DE ROTEAMENTO DE VEÍCULOS COM COLETA E 
ENTREGA SIMULTÂNEA 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
JOÃO PESSOA - PB 
2008 
 
 
 
HUGO HARRY FREDERICO RIBEIRO KRAMER 
 
 
 
 
 
 
 
 
 
 
 
 
 
FORMULAÇÕES MATEMÁTICAS PARA O PROBLEMA DE 
ROTEAMENTO DE VEÍCULOS COM COLETA E ENTREGA 
SIMULTÂNEA 
 
 
 
 
 
 
 
Monografia apresentada como trabalho de conclusão do 
curso de graduação em Engenharia de Produção 
Mecânica, Departamento de Engenharia de Produção, 
Centro de Tecnologia, Universidade Federal da Paraíba. 
 
Orientador: Prof. Dr. Lucídio dos Anjos Formiga Cabral 
 
 
 
 
 
 
 
 
 
 
 
 
JOÃO PESSOA - PB 
2008 
 
 
 
 
 
 
K89f Kramer, Hugo Harry Frederico Ribeiro 
Formulações matemáticas para o problema de roteamento de 
veículos com coleta e entrega simultânea / Hugo Harry Frederico 
Ribeiro Kramer – João Pessoa: UFPB, 2008. 
33 f. il.: 
 
Orientador: Prof. Lucídio dos Anjos Formiga Cabral Dr. 
 
Monografia (Curso de Graduação em Engenharia de Produção 
Mecânica) – DEP /CT / Universidade Federal da Paraíba – UFPB. 
 
1. Formulações matemáticas 2. PRVCES 3. Lower bounds 
I. Título. 
 
CDU: 65.012.122(043) 
 
 
HUGO HARRY FREDERICO RIBEIRO KRAMER 
 
 
 
FORMULAÇÕES MATEMÁTICAS PARA O PROBLEMA DE 
ROTEAMENTO DE VEÍCULOS COM COLETA E ENTREGA 
SIMULTÂNEA 
 
 
 
 
Monografia apresentada e aprovada, em 9 de Setembro de 2008, como 
requisito parcial à obtenção do grau de Engenheiro de Produção Mecânica do 
Departamento de Engenharia de Produção da Universidade Federal da Paraíba, 
pela comissão formada pelos seguintes membros: 
 
 
 
BANCA EXAMINADORA 
 
 
 
_______________________________________________________ 
Prof. Dr. Lucídio dos Anjos Formiga Cabral - Orientador 
Departamento de Estatística - UFPB 
 
 
 
 
_______________________________________________________ 
Prof. Dr. Roberto Quirino do Nascimento - Examinador 
Departamento de Estatística - UFPB 
 
 
 
 
_______________________________________________________ 
Prof. Dr. Luiz Bueno da Silva - Examinador 
Departamento de Engenharia de Produção - UFPB 
 
 
AGRADECIMENTOS 
 
 
Aos meus pais. 
Ao Prof. Dr. Lucídio dos Anjos Formiga Cabral (DE/UFPB), por todo o apoio e 
orientação. 
Ao grande amigo Anand Subramanian, pela amizade e enorme apoio, confiança e 
incentivo para a execução deste e outros trabalhos. 
Ao Prof. Dr. Luiz Bueno da Silva (DEP/UFPB), por conceder uma bolsa de 
Iniciação Científica (CNPq). 
Ao Instituto de Computação (IC) da Universidade Federal Fluminense (UFF) por 
disponibilizar o solver CPLEX, versão 10, para as execuções realizadas nesta monografia. 
Ao Prof. Dr. Marcone Jamilson Freitas Souza (DECOM/UFOP), por disponibilizar 
o uso do solver CPLEX, versão 11, adquirido com recursos do projeto CNPq 474831/2007-8. 
A todos os amigos, em especial Carlos Eduardo G. L. Pires, e colegas, que, de uma 
maneira ou de outra, me ajudaram e apoiaram ao longo do curso. 
 
 
 
 
 
 
RESUMO 
 
 
Esta monografia realiza uma comparação entre diferentes formulações matemáticas 
propostas para o Problema de Roteamento de Veículos com Coleta e Entrega Simultânea (PRVCES). 
O objetivo é avaliar quais formulações são capazes de obter, em média, melhores lower bounds (LBs). 
Para tanto, foi utilizado um conjunto de 72 instâncias disponíveis na literatura referentes ao PRVCES. 
Os testes com as instâncias da literatura foram realizados utilizando-se o solver CPLEX 10. Cada 
execução foi limitada a um tempo máximo de duas horas. Os resultados mostram que as formulações 
de Dell’Amico et al. (2005) e Subramanian (2008) apresentam os melhores LBs. Ressalta-se a 
importância desses resultados, uma vez que podem servir como referência para avaliar o desempenho 
de procedimentos heurísticos propostos para o PRVCES. 
 
 
Palavras-chave: Formulações matemáticas. PRVCES. Lower bounds. 
 
 
 
 
 
ABSTRACT 
 
 
This monograph conducts a comparison between different mathematical formulations 
proposed for the Vehicle Routing Problem with Simultaneous Pickups and Deliveries (VRPSPD). The 
objective is to assess which formulations are able to obtain, on average, better lower bounds (LBs). To 
that end, was used a set of 72 instances available in the literature concerning the VRPSPD. Tests on 
the instances of literature were made using the solver CPLEX 10. Each execution was limited to a 
maximum time of two hours. The results show that the formulations of Dell'Amico et al. (2005) and 
Subramanian (2008) yield the best LBs. It is emphasized the importance of these results because it can 
serve as reference for assessing the performance of heuristic procedures proposed for VRPSPD. 
 
 
Keywords: Mathematical formulations. VRPSPD. Lower bounds. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
LISTA DE FIGURAS 
 
 
Figura 1 – Ilustração de um exemplo do PRV..........................................................................13 
Figura 2 – PRV com coleta e entrega simultânea.....................................................................14 
 
 
 
 
 
 
LISTA DE TABELAS 
 
 
Tabela 1 – Lower bounds encontrados para as instâncias de Dethloff.....................................26 
Tabela 2 – Lower bounds encontrados para as instâncias de Salhi e Nagy..............................27 
Tabela 3 – Lower bounds encontrados para as instâncias de Montané e Galvão.....................28 
Tabela 4 – Comparação entre os melhores LBs encontrados e os UBs para as instâncias de 
Dethloff.....................................................................................................................................29 
Tabela 5 – Comparação entre os melhores LBs encontrados e os UBs para as instâncias de 
Salhi e Nagy .............................................................................................................................30 
Tabela 6 – Comparação entre os melhores LBs encontrados e os UBs para as instâncias de 
Montané e Galvão.....................................................................................................................30 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 LISTA DE SIGLAS 
 
PRV Problema de Roteamento de Veículos 
PRVCES Problema de Roteamento de Veículos com Coleta e Entrega Simultânea 
PRVCE Problema de Roteamento de Veículos com Coleta e Entrega 
LB Lower bound 
UB Upper bound 
 
 
 
 
 
 
 
 
SUMÁRIO 
 
1 INTRODUÇÃO ................................................................................................................... 10 
1.1 DEFINIÇÃO DO TEMA ...................................................................................................10 
1.2 JUSTIFICATIVA ...............................................................................................................10 
1.3 OBJETIVOS.......................................................................................................................11 
1.3.1 Objetivo Geral .................................................................................................................11 
1.3.2 Objetivos Específicos ......................................................................................................11 
 
2 FUNDAMENTAÇÃO TEÓRICA...................................................................................... 12 
2.1 PRVCES .............................................................................................................................13 
2.2 FORMULAÇÕES MATEMÁTICAS ................................................................................14 
 
3 METODOLOGIA................................................................................................................233.1 INSTÂNCIAS ....................................................................................................................23 
3.2 CODIFICAÇÃO DOS MODELOS MATEMÁTICOS .....................................................23 
3.3 AVALIAÇÃO DO DESEMPENHO DOS MODELOS MATEMÁTICOS ......................24 
 
4 RESULTADOS E DISCUSSÕES ...................................................................................... 25 
 
5 CONCLUSÕES....................................................................................................................31 
 
REFERÊNCIAS .....................................................................................................................32 
10 
1 INTRODUÇÃO 
 
1.1 DEFINIÇÃO DO TEMA 
 
 O Problema de Roteamento de Veículos (PRV) consiste na construção de um conjunto 
ótimo de rotas para uma frota de veículos com o objetivo de atender demandas pré-
estabelecidas de entrega ou coleta associadas a clientes dispersos geograficamente. 
 Dentre as diversas variações existentes para o PRV, esta monografia aborda o PRV 
com coleta e entrega simultânea (PRVCES), variante pertencente à classe do PRV com coleta 
e entrega (PRVCE). Diferentemente do PRV, no PRVCES cada cliente possui também, além 
da demanda por entrega, uma demanda por coleta. Ambas as demandas devem ser atendidas 
simultaneamente durante a mesma visita do veículo. 
 Este trabalho busca investigar um conjunto de formulações matemáticas propostas na 
literatura para o PRVCES, ou seja: quais são os modelos que apresentam melhor 
desempenho quando testados em um conjunto de instâncias? 
 
1.2 JUSTIFICATIVA 
 
 O PRV é um problema de otimização combinatória amplamente estudado, sendo 
objeto da publicação de centenas de trabalhos abordando teoria e prática, além de possuir 
inúmeras variações com suas respectivas formulações e algoritmos de solução propostos. 
 A importância do problema pode ser percebida através da variedade de aplicações com 
as quais inúmeras empresas se deparam diariamente, tais como: distribuição de bebidas, 
serviços de entrega de jornais, transporte de equipes de vendedores, coleta de lixo, serviços de 
correios, entre outras. 
 Como diferencial em relação ao PRV clássico, o PRVCES engloba não apenas a 
Logística de Distribuição, mas também a Logística Reversa, que trata do fluxo de retorno de 
produtos de uma cadeia de suprimentos ao seu ponto de origem. 
 A aplicação de métodos computacionais em atividades de distribuição pode implicar, 
segundo Toth e Vigo (2002), em reduções da ordem de 5% a 20% nos custos de transporte. 
Vários estudos de caso são descritos por Golden et al. (2002) e Barker (2002) relatando a 
diminuição dos custos quando da aplicação de algoritmos ao PRV. 
11 
 
 Por ser classificado como NP-hard, as abordagens heurísticas são as mais 
freqüentemente utilizadas para solução do PRV, visto que resultam em soluções de boa 
qualidade com tempo de processamento computacional aceitável. Quando tratado de forma 
exata através das formulações matemáticas, a obtenção de solução em tempo computacional 
aceitável é viável apenas para instâncias de pequeno porte. 
 Apenas recentemente, nos últimos cinco anos, surgiram três trabalhos (BALDACCI et 
al., 2004; LETCHFORD e SALAZAR-GONZÁLEZ, 2006; BALDACCI et al., 2007) onde as 
formulações matemáticas para o PRV clássico são estudadas, relatando os recentes avanços 
nos métodos exatos de solução. Já para o PRVCES, não é de conhecimento a publicação de 
trabalhos semelhantes na investigação dos métodos exatos. Estas abordagens se tornaram 
mais factíveis através do desenvolvimento dos solvers comerciais que, na última década, se 
tornaram mais robustos. 
 O estudo das formulações propostas para o PRVCES pode contribuir substancialmente 
na avaliação da qualidade das soluções obtidas por procedimentos heurísticos propostos, já 
que os resultados decorrentes podem ser adotados como valores de referência sobre a solução 
ótima dos problemas. 
 
1.3 OBJETIVOS 
 
 Esta monografia possui os seguintes objetivos: 
 
1.3.1 Objetivo Geral 
 
 Avaliar a qualidade das relaxações lineares obtidas a partir das formulações 
matemáticas propostas para o PRVCES. 
 
1.3.2 Objetivos Específicos 
 
• Levantamento bibliográfico das principais formulações matemáticas propostas 
para o PRVCES; 
• Implementação das formulações matemáticas; 
• Comparar os desempenhos das formulações nas instâncias disponíveis na 
literatura. 
12 
 
2 FUNDAMENTAÇÃO TEÓRICA 
 
 O PRV foi proposto no final da década de 1950 e desde então uma grande quantidade 
de trabalhos relacionados ao tema se encontra disponível na literatura. A descrição do 
problema pode ser feita da seguinte maneira: dado um conjunto contendo clientes, cada um 
com sua demanda qi conhecida, e um depósito com veículos de capacidade Q, determinar 
quais os conjuntos de rotas capazes de minimizar os custos de transporte. 
 
 
 
Figura 1 – Ilustração de um exemplo do PRV 
 
 Toth e Vigo (2002) fornecem uma ampla revisão literária sobre o PRV onde também 
podem ser observadas metodologias para resolução e aplicações práticas. 
 Reconhecido como NP-hard, o PRV possui inúmeros algoritmos exatos propostos na 
literatura, contudo, por serem de complexidade exponencial, são geralmente viáveis apenas 
para pequenas instâncias. 
 Alguns complicadores podem ser adicionados, através da inserção de diferentes 
restrições, resultando assim em diversas variantes do PRV. As restrições encontradas com 
maior freqüência na literatura são as de capacidade dos veículos, janelas de tempo, 
componentes estocásticos, múltiplos depósitos, heterogeneidade da frota (frota mista), 
periodicidade, entrega dividida e coleta e entrega. 
 
 
 
13 
 
2.1 PRVCES 
 
 O PRVCE pode ser definido, de acordo com Subramanian (2008), da seguinte forma: 
seja G = (V, E) um grafo completo e direcionado com um conjunto de vértices V = {0, ..., n}, 
onde o vértice 0 representa o depósito (V0 = {0}) e os vértices restantes representam os 
clientes. Cada aresta ( , )i j E∈ possui um custo não-negativo cij que satisfaz a desigualdade 
triangular. Cada cliente 0i V V∈ − possui demanda Dqi ∈ por entrega e Ppi ∈ por coleta, 
onde D e P são os conjuntos contendo as quantidades de um determinado bem (ou pessoas) a 
serem distribuídos e recolhidos respectivamente e C = {1, ..., m} o conjunto de veículos 
disponíveis, cada qual com capacidade Q. 
 O PRVCE consiste em construir um conjunto de no máximo m rotas que satisfaçam 
aos seguintes requisitos: (i) todas as demandas por coleta e entrega devem ser atendidas; (ii) a 
capacidade do veículo não deve ser extrapolada; (iii) a soma dos custos deve ser minimizada. 
 A Figura 2 ilustra um exemplo do PRVCES com dois veículos. 
 
 
Figura 2 – PRV com Coleta e Entrega Simultânea 
Fonte: Subramanian (2008) 
 
 Em outras palavras, dado um conjunto de clientes, cada um com demanda pi por coleta 
e qi por entrega, e um depósito com veículos de capacidade Q, deve-se determinar quais os 
conjuntos de rotas capazes de minimizar os custos de transporte. 
 O PRVCES foi proposto inicialmente por Min (1989), onde o autor ilustra uma 
aplicação prática do problema através de um estudo de caso realizado no sistema de 
distribuição de uma biblioteca pública. 
 No PRVCES os veículos partem do depósito com os itens a serem entregues e 
retornam com itens coletados ao longo da rota. O que difere o PRVCES das demais variantes 
14 
 
de problemas pertencentes ao PRVCE é o fato dos serviços de coleta e entrega serem 
efetuados durante a mesma visita ao cliente. 
 Uma revisão bibliográfica acerca de trabalhos relacionados ao PRVCES pode ser 
encontrada em Subramanian (2008). 
 
2.2 FORMULAÇÕES MATEMÁTICAS 
 
 O PRVCES pode ser formulado como um problema de programação inteira mista, 
onde várias técnicas exatas podem ser aplicadas, tais como Relaxação Lagrangeana, branch-and-cut e branch-and-price. 
 Geoffrion (1974) define uma relaxação de um problema de minimização da maneira 
que segue: o problema ( ) ( ){ }min : min |RP g x x W∈ é uma relaxação do problema 
( ) ( ){ }min : min |P f x x V∈ , com a mesma variável de decisão x , se, e somente se: 
(i). O conjunto de soluções viáveis de ( )minRP contém o de ( )minP , ou seja, W V⊇ e 
(ii). Sobre o conjunto de soluções viáveis de ( )minP , o valor da função objetivo de ( )minRP 
é melhor que o da função objetivo de ( )minP , isto é, ( ) ( ),x V g x f x∀ ∈ ≤ . 
 
 Dessa forma tem-se que, no caso dos problemas de minimização, ( )g x é um lower 
bound (LB) para o problema original, implicando que o valor ( )f x da função objetivo deste 
será sempre maior que o valor do LB encontrado. 
 De acordo com Guignard (2003), as relaxações possuem dois papéis: fornecer bounds 
sobre o valor ótimo de problemas difíceis e suas “soluções”, mesmo que inviáveis para o 
problema original, podem ser usadas como ponto de partida no uso de procedimentos 
heurísticos. 
 Alguns modelos matemáticos foram propostos para representar o PRVCES. Dethloff 
(2001) propôs uma formulação baseada em outros dois trabalhos anteriores de sua própria 
autoria. Tal formulação é mostrada abaixo: 
 
Notação 
Conjuntos 
J Conjunto de todas as localizações dos clientes 
15 
 
0J Conjunto de todos os nós, ou seja, localizações dos clientes e o depósito, }0{0 ∪= JJ 
V Conjunto de todos os veículos 
 
Parâmetros 
C Capacidade dos veículos 
ijC Distância entre os nós jiJjJi ≠∈∈ ,, 00 ; ,,: JiMCii ∈= 0:00 =C 
jD Quantidade a ser entregue ao cliente Jj∈ 
n Número de nós, isto é, 0Jj = 
jP Quantidade a ser coletada do cliente Jj∈ 
M Número grande, ex: ( ){ }∑ ∑∑ ∈ ≠∈∈ += 0 0 ,,max Ji ijJj ijJj jj CPDM 
 
Variáveis de decisão 
'
vl Carga do veículo Vv∈ quando sai do depósito 
jl Carga do veículo depois de prestado serviço ao cliente .Jj∈ 
jπ Variável utilizada para proibir subrotas. Pode ser interpretada como sendo a posição do 
nó Jj∈ na rota. 
ijvx Variável binária que indica se o veículo Vv∈ transita diretamente do nó 0Ji∈ para o 
nó 0Jj∈ (xijv = 1) ou não (xijv = 0) 
 
Modelo 
 
 Minimizar∑∑∑
∈ ∈ ∈0 0Ji Jj Vv
ijvij xC (1) 
 
Sujeito a: 
∑∑
∈ ∈
=
0
1
Ji Vv
ijvx , )( Jj∈ (2) 
∑∑
∈∈
=
00 Jj
sjv
Ji
isv xx , ),( VvJs ∈∈ (3) 
∑∑
∈ ∈
=
0
'
Ji Jj
ijvjv xDl , )( Vv ∈ (4) 
)1( 0
'
jvjjvj xMPDll −−+−≥ , ),( VvJj ∈∈ (5) 
16 
 
⎟
⎠
⎞
⎜
⎝
⎛
−−+−≥ ∑
∈Vv
ijvjjij xMPDll 1 , ),,( ijJjJi ≠∈∈ (6) 
Clv ≤
' , )( Vv∈ (7) 
Cl j ≤ , )( Jj∈ (8) 
⎟
⎠
⎞
⎜
⎝
⎛
−−+≥ ∑
∈Vv
ijvij xn 11ππ , ),,( ijJjJi ≠∈∈ (9) 
0≥jπ , )( Jj∈ (10) 
{ }1,0∈ijvπ , ),,( 0 VvJjJi ∈∈∈ (11) 
 
 A função objetivo (1) indica que a distância total a ser percorrida pelos veículos deve 
ser minimizada. As restrições (2) garantem que o serviço deve ser prestado somente uma vez 
por cliente. As restrições (3) indicam que o veículo que chega e sai de cada cliente é o 
mesmo. As restrições (4) correspondem às cargas iniciais de cada veículo. As restrições (5) 
indicam a carga de cada veículo depois de ter visitado o primeiro cliente. As restrições (6) são 
relativas às cargas dos veículos em rota. As restrições (7) e (8) estão relacionadas à 
capacidade de cada veículo depois de ter visitado o primeiro cliente e em rota. As restrições 
(9) são responsáveis pela eliminação das subrotas. 
 Montané e Galvão (2006) construíram uma formulação pertencente a um conjunto de 
modelos que faz uso de variáveis de fluxo em rede para o problema de roteamento de 
veículos. Este modelo, obtido através da expansão do modelo proposto por Mosheiov (1998) 
para o PRVCE, é descrito a seguir: 
 
Notação 
Conjuntos 
V Conjunto de clientes 
0V Conjunto de clientes incluindo o depósito (cliente 0): { }00 ∪=VV 
 
Parâmetros 
n Número total de clientes: Vn = 
ijc Distância entre os clientes i e j 
jp Demanda por coleta do cliente j, j = 1, ..., n 
17 
 
jd Demanda por entrega do cliente j, j = 1, ..., n 
Q Capacidade do veículo 
MD Máxima distância permitida para qualquer rota k 
k Máximo número de veículos 
 
Variáveis de decisão 
=kijx
⎩
⎨
⎧
contrário caso 0,
 veículopelo operada rota apertencer ),arco( o se ,1 kji
 
ijy 
Demanda coletada nos clientes roteados até o nó i (incluindo o nó i) e transportados 
no arco (i, j) 
ijz Demanda a ser entregue para clientes roteados após o nó i e transportados no arco (i, j) 
 
Modelo 
 Minimizar kij
k
k
n
i
n
j
ij xc∑∑∑
= = =1 0 0
 (12) 
Sujeito a: 
∑∑
= =
=
n
i
k
k
k
ijx
0 1
1, ),...,1( nj = (13) 
0
00
=−∑∑
==
n
i
k
ji
n
i
k
ij xx , ),...,0( nj = , ),...,0( kk = (14) 
1
1
0 ≤∑
=
n
j
k
jx , ),...,0( kk = (15) 
∑∑
= =
≤
n
i
n
j
k
ijij MDxc
0 1
, ),...,0( kk = (16) 
j
n
i
ij
n
i
ji pyy =−∑∑
== 00
, 0≠∀j (17) 
j
n
j
ji
n
i
ij dzz =−∑∑
== 00
, 0≠∀j (18) 
∑
=
≤+
k
k
k
ijijij xQzy
1
, ),...,1( ni = , ),...,1( nj = (19) 
{ }1,0∈kijx , ),...,1( ni = , ),...,1( nj = (20) 
0≥ijy , ),...,1( ni = , ),...,1( nj = (21) 
18 
 
0≥ijz , ),...,1( ni = , ),...,1( nj = (22) 
 
 A expressão (12) representa a função objetivo que visa minimizar a soma das 
distâncias percorridas pelos veículos ao longo das rotas. As restrições (13) garantem que cada 
cliente é visitando uma vez. As restrições (14) indicam que o mesmo veículo deve chegar e 
partir de um mesmo cliente. As restrições (15) ilustram que podem ser utilizados até k 
veículos enquanto as expressões (16) são relativas à distância máxima permitida em cada rota. 
As restrições (17) e (18) são as equações de fluxo referentes à coleta e entrega 
respectivamente. As restrições (19) estabelecem que as coletas e entregas sejam efetuadas 
utilizando-se os arcos inclusos na solução, respeitando a capacidade do veículo. Finalmente, 
as restrições (20), (21) e (22) definem a natureza das variáveis de decisão. 
 Outra formulação matemática foi proposta por Dell’Amico et al. (2005), a qual 
também faz uso de variáveis de fluxo em rede. Apesar de guardar semelhanças com a 
formulação proposta por Montané e Galvão (2006), este modelo, descrito a seguir, se 
diferencia do anterior pelo uso de variáveis de decisão com apenas dois índices, ao invés de 
três. 
 
Notação 
Conjuntos 
V Conjunto de clientes 
0V Conjunto de clientes incluindo o depósito (cliente 0): { }00 ∪=VV 
A Conjunto das arestas (i, j), onde 0i V∈ e 0j V∈ 
Parâmetros 
n Número total de clientes: Vn = 
ijc Distância entre os clientes i e j 
jp Demanda por coleta do cliente j, j = 1, ..., n 
jd Demanda por entrega do cliente j, j = 1, ..., n 
Q Capacidade do veículo 
K Máximo número de veículos 
 
 
 
19 
 
Variáveis de decisão 
=kijx
⎩
⎨
⎧
contrário caso 0,
 veículopelo operada rota apertencer ),arco( o se ,1 kji
 
ijP 
Demanda coletada nos clientes roteados até o nó i (incluindo o nó i) e transportados 
no arco (i, j) 
ijD Demanda a ser entregue para clientes roteados após o nó i e transportados no arco (i, j) 
 
Modelo 
( , )
Min ij ij
i j A
c x
∈
∑ (23) 
Sujeito a: 
 
0
1ij
j V
x i V
∈
= ∀ ∈∑ (24) 
0 j
j V
x K
∈
≤∑ (25) 
0 0
0ij ji
j V j V
x x i V
∈ ∈
= ∀ ∈∑ ∑ (26) 
0 0
ij ji i
j V j V
P P p i V
∈ ∈
− = ∀ ∈∑ ∑ (27) 
0 0
ji ij i
j V j V
D D d i V
∈ ∈
− = ∀ ∈∑ ∑ (28) 
( ),ij ij ijP D Q x i j A+ ≤ ∀ ∈ (29) 
( ), 0 ,ij ijP D i j A≥ ∀ ∈ (30) 
{ } ( )0,1 ,ijx i j A∈ ∀ ∈ (31) 
 
 A expressão (23) busca minimizar a distância total percorrida pelo conjunto de 
veículos. As restrições (24) garantem que cada cliente seja visitado uma única vez. A restrição 
(25) faz com que não mais que K veículos sejam utilizados. As expressões (26), (27), e (28) 
sãorestrições de conservação do fluxo do número de veículos e das cargas de coleta e de 
entrega. As restrições (29) fazem com que a carga dos veículos não seja extrapolada. As 
expressões (30) e (31) se referem à natureza das variáveis de decisão. 
 Subramanian (2008) propõe uma formulação matemática para o PRVCES baseada no 
modelo de Baldacci et al. (2004) para o PRV clássico, onde é utilizada a abordagem de fluxo 
20 
 
com duas comodidades (two-commodity flow formulation). Este modelo leva em consideração 
três problemas: 
(i). PRV somente com entrega; 
(ii). PRV somente com coleta; 
(iii). PRV com coleta e entrega simultânea. 
 
 Esta formulação matemática encontra-se abaixo: 
 
Notação 
Conjuntos 
V Conjunto de todos os clientes e o depósito 
}1{ +∪= nVV Conjunto V agregado de uma cópia do depósito 
}1,0{\ +=′ nVV Conjunto de todos os clientes 
E Conjunto das arestas (i, j), onde Vi∈ e Vj∈ 
 
Parâmetros 
v Número de rotas 
iq Demanda por entrega do cliente Vi ′∈ 
ip Demanda por coleta do cliente Vi ′∈ 
ijc Custo entre os clientes Eji ∈),( 
Q Capacidade do veículo 
 
Variáveis de decisão 
ijx = 
⎩
⎨
⎧
contrário caso 0,
solução na inclusaestiver ),( aresta a se ,1 ji
 
=ijloadD carga do veículo, referente a entrega, na aresta Eji ∈),( 
=ijloadP carga do veículo, referente a coleta, na aresta Eji ∈),( 
=ijload carga do veículo, referente a coleta e entrega simultânea, na aresta Eji ∈),( 
 
 
 
 
21 
 
Modelo 
∑∑
∈ ∈Vi Vj
ijij xcMin (32) 
Sujeito a: 
 
∑
∈
′∈∀=−
Vj
iijji ViqloadDloadD 2)( (33) 
∑ ∑
′∈ ′∈
=
Vj Vi
ij qloadD )( 0 (34) 
∑ ∑
′∈ ′∈
−⋅=
Vj Vi
ij qQvloadD )( 0 (35) 
∑
∈
′∈∀=−
Vj
ijiij ViploadPloadP 2)( (36) 
∑ ∑
′∈ ′∈
+ =
Vj Vi
ijn ploadD )( 1 (37) 
∑ ∑
′∈ ′∈
+ −⋅=
Vj Vi
ijn pQvloadD )( 1 (38) 
∑
∈
′∈∀−=−
Vj
iiijji Vipqloadload )(2)( (39) 
VjloadDload jj ′∈∀= 00 (40) 
VjloadDload jj ′∈∀= 00 (41) 
VjloadPload jnjn ′∈∀= ++ 11 (42) 
VjloadPload jnjn ′∈∀= ++ 11 (43) 
EjixQloadDloadD ijjiij ∈∀⋅=+ ),( (44) 
EjixQloadPloadP ijjiij ∈∀⋅=+ ),( (45) 
EjixQloadload ijjiij ∈∀⋅=+ ),( (46) 
Vkxx
kj
Vj
kj
ki
Vj
ki ′∈∀=+∑∑
>
∈
<
∈
 2 (47) 
vx
Vj
j ≤∑
′∈
0 (48) 
vx
Vj
jn ≤∑
′∈
+1 (49) 
22 
 
}1,0{∈ijx , Eji ∈∀ ),( (50) 
,0≥ijloadD Eji ∈∀ ),( (51) 
0≥ijloadP , Eji ∈∀ ),( (52) 
0≥ijload , Eji ∈∀ ),( (53) 
 
 A função objetivo (32) minimiza o somatório das distâncias a serem percorridas. As 
restrições (33)-(35) estão relacionadas ao problema (i). As restrições (33) garantem que todas 
as demandas por entrega sejam atendidas. A restrição (34) faz com que a soma da carga que 
sai do depósito seja igual à soma das demandas de todos os clientes. A restrição (35) assegura 
que a soma das cargas dos veículos que chegam ao vértice 0 seja igual à soma da carga 
residual dos veículos ao sair do depósito. As restrições (36)-(38) são relativas ao problema (ii) 
e têm significado análogo às restrições (33)-(35). As restrições (39)-(43) correspondem ao 
problema (iii). As restrições (39) garantem que as demandas, por coleta e entrega, sejam 
atendidas simultaneamente. As restrições (40) e (41) indicam que as cargas que saem e 
chegam do vértice 0 devem ser respectivamente iguais às do problema (i). As restrições (42) e 
(43) asseguram que as cargas que entram e saem do vértice n + 1 sejam respectivamente 
iguais às do problema (ii). As restrições (44), (45) e (46) apontam que a soma das cargas que 
entram e saem de cada cliente, nos problemas (i), (ii) e (iii) respectivamente, deve ser igual à 
capacidade do veículo. As restrições (47) obrigam que toda solução viável contenha duas 
arestas incidentes em cada cliente. As restrições (48) e (49) correspondem ao limite superior 
de veículos. As restrições (50)-(53) estão relacionadas à natureza das variáveis de decisão. 
 
 
 
 
 
 
 
 
 
23 
 
3 METODOLOGIA 
 
 O procedimento metodológico utilizado é composto por três etapas: obtenção de dados 
de entrada através de instâncias de problemas teste, codificação de três dos quatro modelos 
matemáticos descritos na Seção 1, avaliação do comportamento dos três modelos quando 
testado em instâncias disponíveis na literatura. As etapas são descritas nas subseções a seguir: 
 
3.1 INSTÂNCIAS 
 
 Para o PRVCES, uma instância deve ter os seguintes dados de entrada: 
• Um conjunto { }1,...,V n= representando os clientes a serem visitados; 
• Um conjunto { }0 0V = representando o depósito dos veículos; 
• Um conjunto 0'V V V= ∪ contendo todos os clientes mais o depósito; 
• Um grafo completo e direcionado ( )',G V E= , onde E é o conjunto de arestas ( ),i j 
com custo não negativo ijc que satisfazem a desigualdade triangular; 
• Demandas não negativas ip por coleta associadas a cada cliente i V∈ ; 
• Demandas não negativas iq por entrega associadas a cada cliente i V∈ ; 
• Um número máximo de k veículos com capacidade Q. 
 
 Os testes computacionais realizados utilizam as instâncias propostas na literatura por 
Dethloff (2001), Salhi e Nagy (1999) e Montané e Galvão (2006). 
 
3.2. CODIFICAÇÃO DOS MODELOS MATEMÁTICOS 
 
 Para a realização dos testes comparativos entre as formulações de Dethloff (2001), 
Montané e Galvão (2006), Dell’Amico et al. (2005) e Subramanian (2008), as mesmas foram 
implementadas usando o compilador G++ fazendo uso das bibliotecas ILOG Concert 
Technology. 
 
 
 
24 
 
3.3 AVALIAÇÃO DO DESEMPENHO DOS MODELOS MATEMÁTICOS 
 
 Para avaliar o comportamento das formulações, cada uma destas foi testada em um 
conjunto de 72 instâncias. Os testes consistem de execuções utilizando o solver CPLEX 
versão 10.0 para as instâncias disponíveis na literatura. Para todas as execuções foram 
atribuídos os seguintes parâmetros comuns a todas as instâncias e modelos: 
• Tempo computacional limite de 2 horas; 
• Ênfase de busca do melhor LB. 
 
 A avaliação entre o desempenho das formulações é feita através da comparação dos 
LBs obtidos ao final das execuções de cada instância. Cada execução é finalizada quando o 
tempo limite é atingido. Caso contrário, a solução ótima foi encontrada. Dessa forma, tem-se 
que o valor do LB é o mesmo da solução ótima encontrada. 
 Além disso, também é verificado o gap entre o melhor LB encontrado e o melhor 
upper bound (UB) conhecido (melhor solução disponível na literatura). O gap é a diferença 
em percentual obtida pela seguinte expressão: 
 
100%UB LB
LB
−⎛ ⎞×⎜ ⎟
⎝ ⎠
, (54) 
 
onde UB corresponde ao valor da melhor solução encontrada na literatura e LB é o melhor 
lower bound encontrado entre as três formulações matemáticas. 
 
 
 
 
 
 
 
 
25 
 
4 RESULTADOS E DISCUSSÕES 
 
 Esta seção apresenta os resultados obtidos ao final das execuções para cada modelo da 
forma descrita na Seção 2.3. Dos quatro modelos apresentados, apenas o proposto por 
Dethloff (2001) não foi explorado, pois foi observado após testes preliminares que esta 
formulação não se mostrou capaz de produzir LBs significativos quando comparados com os 
fornecidos pelas outras três formulações estudadas. 
 Como mencionado anteriormente, os modelos matemáticos foram implementados em 
linguagem de programação C++, utilizando as bibliotecas ILOG Concert Technology. As 
execuções foram realizadas em um PC Intel Pentium D com 3,0 GHZ e 2048 MB de memória 
RAM, sistema operacional Linux com kernel versão 2.6.15. 
 Testes preliminares revelaram que o uso da Relaxação Lagrangeana fornecia 
resultados aquém do esperado. Dessa forma, optou-se por realizar as execuções no solver 
CPLEX versão 10.0 e guardar os LBs fornecidos pelo mesmo ao final de cada execução. 
 As Tabelas 1, 2 e 3 sumarizam os LBs de cada problema obtidos pelas formulações de 
Montané e Galvão (2006), Dell’Amico el al. (2005) e Subramanian(2008) para os conjuntos 
de problemas de Dethloff (2001), de Salhi e Nagy (1999) e Montané e Galvão (2006). Os 
valores destacados em negrito representam os melhores LBs obtidos para cada problema. 
 
Tabela 1: Lower bounds obtidos para as instâncias de Dethloff 
Problema Nº de Clientes Veículos
Montané e 
Galvão (2006) 
Dell'Amico et al. 
(2005) 
Subramanian 
(2008) 
SCA3-0 50 4 603,53 600,81 614,14 
SCA3-1 50 4 675,20 666,30 679,29 
SCA3-2 50 4 658,03 635,97 659,34 
SCA3-3 50 4 662,36 654,78 667,59 
SCA3-4 50 4 668,08 657,19 672,85 
SCA3-5 50 4 642,31 637,55 643,14 
SCA3-6 50 4 618,25 622,49 638,02 
SCA3-7 50 4 633,60 632,48 641,73 
SCA3-8 50 4 672,57 676,10 698,74 
SCA3-9 50 4 658,65 639,02 660,86 
SCA8-0 50 9 890,24 895,34 888,18 
SCA8-1 50 9 966,73 976,57 977,68 
SCA8-2 50 9 964,16 976,12 969,48 
SCA8-3 50 9 913,64 927,9 924,44 
SCA8-4 50 9 980,29 997,96 1000,74 
SCA8-5 50 9 960,63 956,68 959,67 
SCA8-6 50 9 896,45 905,54 917,45 
SCA8-7 50 9 960,83 974,51 961,72 
SCA8-8 50 9 994,70 997,81 1008,53 
26 
 
SCA8-9 50 9 982,00 986,68 986,27 
CON3-0 50 4 606,79 597,32 610,50 
CON3-1 50 4 544,24 544,72 543,87 
CON3-2 50 4 497,89 499,68 503,30 
CON3-3 50 4 582,61 574,90 583,95 
CON3-4 50 4 575,84 572,98 578,10 
CON3-5 50 4 541,60 542,63 550,38 
CON3-6 50 4 477,38 478,71 484,62 
CON3-7 50 4 553,52 557,81 563,54 
CON3-8 50 4 500,15 509,14 511,71 
CON3-9 50 4 561,34 561,81 569,64 
CON8-0 50 9 811,97 820,48 817,39 
CON8-1 50 9 697,07 703,9 701,48 
CON8-2 50 9 661,47 673,53 664,51 
CON8-3 50 10 758,33 768,81 775,12 
CON8-4 50 9 739,26 737,8 735,11 
CON8-5 50 9 715,78 719,08 710,95 
CON8-6 50 9 636,92 645 632,93 
CON8-7 50 9 769,01 770,8 769,36 
CON8-8 50 9 706,95 715,05 697,05 
CON8-9 50 9 751,91 765,4 750,33 
 
 Na Tabela 1, observa-se que dos 40 melhores LBs encontrados para as instâncias de 
Dethloff (2001), 24 foram fornecidos pela formulação de Subramanian (2008), 14 pelo 
modelo de Dell’Amico et al. (2005) e dois pelo de Montané e Galvão (2006). 
 É interessante notar que para as instâncias com maior número de veículos, totalizando 
20, o desempenho do modelo proposto por Dell’Amico et al. (2005) forneceu 13 dos 
melhores LBs. Para essas instâncias, os modelos de Montané e Galvão (2006) e Subramanian 
(2008) encontraram 2 e 5 melhores LBs, respectivamente. Já nas instâncias com menor 
número de veículos, o modelo de Subramanian (2008) se sobressai, fornecendo 19 dos 20 
melhores LBs. O LB restante foi fornecido pelo modelo de Dell’Amico et al. (2005) na 
instância CON3-1. 
 
Tabela 2: Lower bounds encontrados para as instâncias de Salhi e Nagy 
Problema Nº de Clientes Veículos
Montané e 
Galvão (2006) 
Dell'Amico et al. 
(2005) 
Subramanian 
(2008) 
CMT1X 50 3 460,27 458,23 463,27 
CMT1Y 50 3 458,62 460,29 461,94 
CMT2X 75 6 641,69 637,52 642,48 
CMT2Y 75 6 632,16 641,10 642,34 
CMT3X 100 5 686,35 689,11 699,41 
CMT3Y 100 5 690,74 689,63 697,83 
CMT12X 100 5 589,73 609,13 608,81 
CMT12Y 100 6 591,81 613,25 611,72 
CMT11X 120 4 690,58 690,20 685,00 
27 
 
CMT11Y 120 4 689,79 695,94 687,05 
CMT4X 150 7 783,26 782,54 806,57 
CMT4Y 150 7 779,53 777,54 805,66 
CMT5X 199 10 905,25 923,61 937,66 
CMT5Y 199 10 920,10 923,34 939,2 
 
 Na Tabela 2 estão os LBs para o conjunto de problemas de Salhi e Nagy (1999). Aqui, 
dos 14 melhores LBs encontrados, 10 foram obtidos através da formulação de Subramanian 
(2008), enquanto três foram fornecidos pelo modelo de Dell’Amico et al. (2005) e um pelo 
modelo de Montané e Galvão (2006). 
 
Tabela 3: Lower bounds encontrados para as instâncias de Montané e Galvão 
Problema Nº de Clientes Veículos
Montané e 
Galvão (2006) 
Dell'Amico et al. 
(2005) 
Subramanian 
(2008) 
r101 100 12 929,38 946,74 938,76 
r201 100 3 653,44 650,15 662,00 
c101 100 16 1081,93 1123,78 1110,75 
c201 100 5 637,45 629,40 644,62 
rc101 100 10 936,07 971,55 952,95 
rc201 100 3 669,27 659,29 659,11 
r1_2_1 200 23 2903,18 2951,85 2935,92 
r2_2_1 200 5 1567,49 1582,32 1599,66 
c1_2_1 200 28 3250,90 3306,84 3274,80 
c2_2_1 200 9 1551,01 1571,04 1572,49 
rc1_2_1 200 23 2926,93 2981,41 2952,99 
rc2_2_1 200 5 1484,17 1483,83 1501,93 
r1_4_1 400 54 - 8325,55 8343,67 
r2_4_1 400 10 - - - 
c1_4_1 400 63 - 10245,85 10287,32 
c2_4_1 400 15 - - - 
rc1_4_1 400 52 - 8407,16 8485,91 
rc2_4_1 400 11 - - - 
 
 A Tabela 3 contém os valores dos LBs encontrados pelas formulações quando testadas 
no conjunto de instâncias de Montané e Galvão (2006). Observa-se que em três instâncias não 
foi possível encontrar LBs por nenhuma das três formulações dentro do tempo de 
processamento estipulado para cada execução. Vale ressaltar que as instâncias em que não foi 
possível encontrar LBs são de grande porte, possuindo 400 clientes e apresentam números de 
veículos superiores a 50. Além das três instâncias em que não foi possível obter LBs, a 
formulação proposta por Montané e Galvão (2006) foi incapaz de fornecê-los em outros três 
problemas, também com 400 clientes, devido à quantidade insuficiente de memória. Já nas 
instâncias em que foram obtidos LBs, 8 foram encontrados pelo modelo de Subramanian 
(2008), 6 pelo modelo de Dell’Amico et al. (2005) e um pelo de Montané e Galvão (2006). 
28 
 
 Portanto, excluindo as instâncias em que não foi possível obter LBs, observa-se que a 
formulação de Subramanian (2008) conseguiu 42 dos 69 melhores LBs, enquanto as 
formulações de Dell’Amico et al. (2005) e Montané e Galvão (2006) forneceram, 
respectivamente, 23 e 4 desses melhores LBs. 
 As Tabelas de 4 a 6 mostram os gaps entre as melhores soluções disponíveis na 
literatura (UB) e os melhores LBs encontrados neste trabalho. Os valores de UB podem ser 
encontrados em Subramanian et al. (2008) e foram fornecidos por Ropke e Pisinger (2006), 
Zachariadis et al. (2007), Wassan et al. (2008), além dos próprios resultados encontrados pela 
heurística desenvolvida em tal trabalho. Estas diferenças foram calculadas de acordo com a 
equação (54) apresentada na Seção 2.3. 
 
Tabela 4: Comparação entre os melhores LBs encontrados e os UBs para as instâncias de Dethloff 
Problema Clientes Veículos LB UB gap (%) 
SCA3-0 50 4 614,14 635,62 3,50 
SCA3-1 50 4 679,29 697,84 2,73 
SCA3-2 50 4 659,34 659,34 0,00 
SCA3-3 50 4 667,59 680,04 1,86 
SCA3-4 50 4 672,85 690,50 2,62 
SCA3-5 50 4 643,14 659,90 2,61 
SCA3-6 50 4 638,02 651,09 2,05 
SCA3-7 50 4 641,73 659,17 2,72 
SCA3-8 50 4 698,74 719,47 2,97 
SCA3-9 50 4 660,86 681,00 3,05 
SCA8-0 50 9 895,34 961,50 7,39 
SCA8-1 50 9 977,68 1049,65 7,36 
SCA8-2 50 9 976,12 1039,64 6,51 
SCA8-3 50 9 927,90 983,34 5,97 
SCA8-4 50 9 1000,74 1065,49 6,47 
SCA8-5 50 9 960,63 1027,08 6,92 
SCA8-6 50 9 917,45 971,82 5,93 
SCA8-7 50 9 974,51 1051,28 7,88 
SCA8-8 50 9 1008,53 1071,18 6,21 
SCA8-9 50 9 986,68 1060,50 7,48 
CON3-0 50 4 610,50 616,52 0,99 
CON3-1 50 4 544,72 554,47 1,79 
CON3-2 50 4 503,30 518,00 2,92 
CON3-3 50 4 583,95 591,19 1,24 
CON3-4 50 4 578,10 588,79 1,85 
CON3-5 50 4 550,38 563,70 2,42 
CON3-6 50 4 484,62 499,05 2,98 
CON3-7 50 4 563,54 576,48 2,30 
CON3-8 50 4 511,71 523,05 2,22 
CON3-9 50 4 569,64 578,24 1,51 
CON8-0 50 9 820,48 857,17 4,47 
29 
 
CON8-1 50 9 703,90 740,85 5,25 
CON8-2 50 9 673,53 712,89 5,84 
CON8-3 50 9 775,12 811,07 4,64 
CON8-4 50 9 739,26 772,25 4,46 
CON8-5 50 9 719,08 754,88 4,98 
CON8-6 50 9 645,00 678,92 5,26 
CON8-7 50 9 770,80 811,96 5,34 
CON8-8 50 9 715,05 767,53 7,34 
CON8-9 50 9 765,40 809,00 5,70 
Média 4,14 
 
 Na Tabela 4 observa-se que foi possível encontrar a solução ótima para a instância 
SCA3-2. Este valor coincide com o melhor valor disponível na literatura. Este mesmo valor 
de solução foi obtido por Subramanian (2008), Ropke e Psinger (2006) e Zachariadis et al. 
(2007). Das três formulações estudadas, apenas a proposta por Subramanian (2008) foi capaz 
de encontrar a solução ótima para essa instância dentro do tempo limite. O maior percentual 
de diferença entre UB e LB verificado foi de 7,88% na instância SCA8-7, e o menor foi 
0,99%, excluindo o casoda instância SCA3-2 em que foi encontrada solução ótima. A média 
das diferenças entre UBs e os melhores LBs foi de 4,14%. 
 
Tabela 5: Comparação entre os melhores LBs encontrados e os UBs para as instâncias de Salhi e Nagy 
Problema Clientes Veículos LB UB gap (%) 
CMT1X 50 3 463,27 466,77 0,76 
CMT1Y 50 3 461,94 458,96 1,05 
CMT2X 75 7 642,48 668,77 4,09 
CMT2Y 75 7 642,34 663,25 3,26 
CMT3X 100 5 699,41 721,27 3,13 
CMT3Y 100 5 697,83 721,27 3,36 
CMT12X 100 6 609,13 662,22 8,72 
CMT12Y 100 6 613,25 662,22 7,99 
CMT11X 120 4 690,58 838,66 21,44 
CMT11Y 120 5 695,94 830,39 19,32 
CMT4X 150 7 806,57 852,46 5,69 
CMT4Y 150 7 805,66 852,46 5,81 
CMT5X 199 11 937,66 1030,55 9,91 
CMT5Y 199 10 939,20 1030,55 9,73 
Média 7,45 
 
 A Tabela 5 mostra os melhores LBs encontrados neste trabalho, as melhores soluções 
disponíveis na literatura e os gaps entre estes valores para as instâncias de Salhi e Nagy 
(1999). Essa diferença toma valores relativamente maiores que os encontrados para as 
instâncias de Dethloff (2001), tornando-se mais evidente à medida que o número de clientes 
30 
 
da instância aumenta. O menor valor encontrado entre os gaps foi de 0,76% e o maior foi 
21,44%, com média igual a 7,45%. Na instância CMT1Y, pode-se notar que o valor da 
melhor solução da literatura, encontrado por Wassan et al. (2007) está incorreto, já que este 
valor é menor que o melhor LB encontrado para esta instância, obtido através da formulação 
de Subramanian (2008), e também é menor que o LB fornecido pelo modelo de Dell’Amico et 
al. (2005). Este fato viola a condição de que o valor da função objetivo do problema original 
sempre será maior que o LB fornecido para o mesmo problema. Dessa forma, tem-se que o 
valor correto da melhor solução da literatura para esta instância é 466,77, encontrado por 
Subramanian (2008). 
 
Tabela 6: Comparação entre os melhores LBs encontrados e os UBs para as instâncias de Montané e Galvão 
Problema Clientes Veículos LB UB gap (%) 
r101 100 12 946,74 1010,90 6,78 
r201 100 3 662,00 666,20 0,63 
c101 100 17 1123,78 1220,26 8,59 
c201 100 5 644,62 662,07 2,71 
rc101 100 11 971,55 1059,32 9,03 
rc201 100 3 669,27 672,92 0,55 
r1_2_1 200 23 2951,85 3371,29 14,21 
r2_2_1 200 5 1599,66 1665,58 4,12 
c1_2_1 200 29 3306,84 3640,20 10,08 
c2_2_1 200 9 1572,49 1728,14 9,90 
rc1_2_1 200 25 2981,41 3327,98 11,62 
rc2_2_1 200 5 1501,93 1560,00 3,87 
r1_4_1 400 54 8343,67 9695,77 16,21 
r2_4_1 400 10 - 3574,86 - 
c1_4_1 400 65 10287,30 11124,30 8,14 
c2_4_1 400 15 - 3575,63 - 
rc1_4_1 400 52 8485,91 9602,53 13,16 
rc2_4_1 400 11 - 3416,61 - 
Média 7,97 
 
 A Tabela 8 contém as comparações entre melhores UBs e melhores LBs obtidos para o 
conjunto de instâncias de Montané e Galvão (2006). Aqui, o menor gap obtido ocorreu na 
instância rc201 no valor de 0,55% e o maior aparece na instância r1_4_1 com 16,21%. A 
média dos gaps foi de 7,97%. Vale ressaltar que, nesse caso, o cálculo da média só levou em 
consideração os valores para as 15 instâncias em que foi possível obter LBs, desconsiderando 
as três instâncias em que isso não foi possível. 
 
 
31 
 
5. CONCLUSÕES 
 
 Esta monografia tratou do Problema de Roteamento de Veículos com Coleta e Entrega 
Simultânea (PRVCES) através da avaliação de três formulações matemáticas propostas por 
Montané e Galvão (2006), Dell’Amico et al. (2005) e Subramanian (2008). 
 Através deste trabalho foi possível mostrar que a formulação proposta por 
Subramanian (2008) foi capaz de produzir a maioria dos melhores LBs, seguida pelo modelo 
de Dell’Amico et al. (2005). Como conseqüência desse estudo, foi possível melhorar o valor 
de 69 LBs para o PRVCES com relação aos valores encontrados por Montané e Galvão 
(2006) no único trabalho conhecido até então a fornecer LBs para este problema. Apenas em 
três instâncias não se obtiveram LBs, visto que através do método aqui utilizado não foi 
possível sequer encontrar um valor de relaxação linear para os problemas r2_4_1, c2_4_1, 
rc2_4_1 com as formulações estudadas. 
 A determinação de novos lower bounds é de grande importância para problemas de 
otimização combinatória como o PRVCES, já que estes serão tomados como valores de 
referência para avaliar o desempenho de algoritmos heurísticos propostos para resolvê-los. 
 Além disso, vale ressaltar que o trabalho forneceu ainda o valor da solução ótima para 
a instância SCA3-2 e ainda detectou que um resultado foi publicado equivocadamente na 
literatura para a instância CMT1Y. 
 Esse estudo pode contribuir para melhor selecionar uma formulação a ser explorada 
por técnicas mais sofisticadas como branch-and-cut, branch-and-price e branch-and-cut-and-
price na tentativa de conseguir resultados mais robustos. 
 
 
 
 
 
 
 
 
 
 
32 
 
REFERÊNCIAS 
 
BALDACCI, R.; HADJICONSTANTINOU, E. A.; MINGOZZI, A. An exact algorithm for 
the capacited vehicle routing problem based on a two-commodity network flow formulation. 
Operations Research, v. 52, n. 5, p. 723-738, 2004. 
 
 
BALDACCI, R.; TOTH, P; VIGO, D. Recent advances in vehicle routing exact algorithms. 
4OR: A Quarterly Journal of Operations Research, v. 5, n. 4, p. 269-298, 2007. 
 
 
BARKER, E. K. Evolution of Microcomputer-Based Vehicle Routing Software: Case Studies 
in United States. In: Paolo Toth e Daniele Vigo (eds.), The Vehicle Routing Problem, 
SIAM Monographs on Discrete Mathematics and Applications 9, Philadelphia, p. 353–362, 
2002. 
 
 
BERBEGLIA, G.; CORDEAU, J-F.; GRIBKOVSKAIA, I.; LAPORTE, G. Static Pickup 
and Delivery Problems: A Classification Scheme and Survey. Disponível em 
<http://neumann.hec.ca/chairedistributique/common/PDP-TOP.pdf.>, acesso em 31/01/2007. 
 
 
DE BRITO, M. P. Managing Reverse Logistics or Reversing Logistics Management?. 
Holanda, 2002. Tese (Doutorado), Erasmus University Rotterdam, Holanda, 2003. 
 
 
DETHLOFF, J. Vehicle routing and reverse logistics: the vehicle routing problem with 
simultaneous delivery and pick-up, OR Spektrum, v. 23, p. 79-96, 2001. 
 
 
GEOFFRION, A. M. Lagrangean relaxation for integer programming. Mathematical 
Programming Study, v. 2, p. 82-114, 1974. 
 
 
GOLDEN, B.L.; ASSAD, A. A.; WASIL, E. A. Routing vehicles in the real world: 
Applications in the solid waste, beverage, food, dairy, and newspaper industries. In: Paolo 
Toth e Daniele Vigo (eds.), The Vehicle Routing Problem, SIAM Monographs on Discrete 
Mathematics and Applications 9, Philadelphia, p. 245–286, 2002. 
 
 
GUIGNARD, M. Lagrangean Relaxation. TOP - Sociedad de Estadística e Investigación 
Operativa. v. 11, n. 2, p. 151-228, 2003. 
 
 
LETCHFORD, A. N.; SALAZAR-GONZÁLEZ, J.-J. Projection results for vehicle routing. 
Mathematical Programming, v. 105, n. 2-3, p. 251-274, 2006. 
 
 
33 
 
MIN, H. The multiple vehicle routing problem with simultaneous delivery and pick-up points, 
Transportation Research, v. 23, n. 5, p. 377-386, 1989. 
 
 
MONTANÉ, F. A. T.; GALVÃO, R. D. A tabu search algorithm for the vehicle routing 
problem with simultaneous pick-up and delivery service, Computers & Operations 
Research, v. 33, n. 3, p. 595-619, 2006. 
 
 
MOSHEIOV, G. Vehicle routing with pick-up and delivery: tour partitioning heuristics. 
Computers and Industrial Engineering, v. 34, p. 669-684, 1998. 
 
 
ROPKE, S.; PSINGER, D. A unified heuristic for a large class of vehicle routing problems 
with backhauls. European Journal of Operational Research, v. 171, n. 3, p. 750-775, 2006. 
 
 
SUBRAMANIAN, A. Metaheurística Iterated Local Search Aplicada ao Problema de 
Roteamento de Veículos com Coleta e Entrega Simultânea. 2008. Dissertação (Mestrado) - 
Programa de Pós-Graduação em Engenharia de Produção, Universidade Federal da Paraíba, 
João Pessoa, 2008. 
 
SUBRAMANIAN, A.; CABRAL, L. A. F.; OCHI, L. S. An efficient ILS heuristic for the 
vehicle routing problem with simultaneous pickup and delivery. Artigo submetido ao Journal 
of Heuristics, 2008. 
 
TOTH, P.; VIGO, D. Vehicle Routing Problem, SIAM Monographson Discrete 
Mathematics and Applications 9, Philadelphia, 2002. 
 
WASSAN, N. A.; WASSAN, A. H.; NAGY, G. A reactive tabu search algorithm for the 
vehicle routing problem with simultaneous pickups and deliveries. Journal of 
Combinatorial Optimization, v. 15, n. 4, p. 368-386, 2008. 
 
 
ZACHARIADIS, E. E.; TARANTILIS, C. D.; KIRANOUDIS, C. T. A hybrid metaheuristic 
algorithm for the vehicle routing problem with simultaneous delivery and pick-up service. 
Expert Systems with Applications, in press, 2007.