( PDF ) Algoritmos para problemas de roteamento de veículos com entrega e coleta

Download PDF

ads:

IVAN XAVIER ARA

UJO DE LIMA

NITER

2009

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

IVAN XAVIER ARA

UJO DE LIMA

Disserta¸c˜ao de Mestrado submetida ao Pro-

grama de P´os-Gradua¸c˜ao em Computa¸c˜ao da

Universidade Federal Fluminense como re-

quisito parcial para a obten¸c˜ao do t´ıtulo de

Mestre.

Area de concentra¸c˜ao: Otimiza¸c˜ao

Combinat´oria e Inteligˆencia Artiﬁcial.

Orientador:

Prof. Luiz Satoru Ochi, D. Sc.

Co-orientador:

Prof. Eduardo Uchoa Barboza, D. Sc.

Universidade Federal Fluminense

NITER

2009

ads:

Algoritmos para problemas de roteamento de ve´ıculos com entrega e

coleta

Ivan Xavier Ara´ujo de Lima

Disserta¸c˜ao de Mestrado submetida ao Pro-

grama de P´os-Gradua¸c˜ao em Computa¸c˜ao da

Universidade Federal Fluminense como re-

quisito parcial para a obten¸c˜ao do t´ıtulo de

Mestre.

Area de concentra¸c˜ao: Otimiza¸c˜ao

Combinat´oria e Inteligˆencia Artiﬁcial.

Aprovada por:

Prof. Luiz Satoru Ochi, D.Sc. / IC-UFF (Presidente)

Prof. Eduardo Uchoa Barboza, D.Sc. / TEP-UFF

Profa. Adriana C. F. Alvim, D.Sc. / DIA-UNIRIO

Prof. Artur Alves Pessoa, D.Sc. / TEP-UFF

Prof. Marcus V. S. Poggi de Arag˜ao, D.Sc. / DI-PUC-Rio

Niter´oi, 17 de Abril de 2009.

“...

E melhor tentar e falhar, que preocupar-se e ver a vida passar.

E melhor tentar,

ainda em v˜ao, que sentar-se fazendo nada at´e o ﬁnal.”

Martin Luther King

Dedico esse trabalho a Deus. A minha esposa, meus familiares, ao Uchoa e demais

amigos, por todo apoio, amor e carinho.

Acima de tudo agrade¸co a Deus que conhece o futuro desde o presente, pois toda a

sabedoria do mundo pertence a Ele, e tamb´em, por ter me enviado as pessoas certas para

poder ajudar nessa grande batalha.

Um agradecimento super especial `a minha esposa Danielly quem com muito amor

me incentiva e concede for¸cas me lembrando que: “Tudo posso naquEle que me fortalece”

(Filipenses 4:13). Meus pais e familiares que mesmo distante, nunca estiveram longe de

mim.

Ao meu orientador Prof. Dr. Satoru por dar-me o voto de conﬁan¸ca para a realiza¸c˜ao

deste trabalho. Ao meu coorientador Prof. Dr. Uchoa o qual com carinho, aten¸c˜ao e

dedica¸c˜ao me encaminhou para o rumo certo.

A meus amigos de longo e curto prazo que no dia-a-dia, atrav´es de suas amizades,

foram me moldando e auxiliando, a ser quem eu sou e estar onde estou. N˜ao citarei

nomes, mas, `a todos do IC, principalmente aos que ﬁzeram mat´eria comigo pois tivemos

a oportunidade de nos conhecer melhor e compartilhar experiˆencias, e aos amigos do

trabalho (Automatos e Gapso), pois tornaram agrad´avel esta forma que consegui de me

manter no rio, um grande abra¸co.

Agrade¸co `a Maria e `a

Angela por serem atenciosas, prestativas e colaboradoras, indo

al´em de suas obriga¸c˜oes para na medida do poss´ıvel facilita nossas vidas.

Agrade¸co aos membros da banca (Uchoa, Satoru, Artur Pessoa, Marcus Poggi e Adri-

ana Alvim) que dedicaram um tempo com certeza escasso a colaborar com este trabalho

realizando cr´ıticas e sugest˜oes que vem a enriquece-lo.

Neste trabalho s˜ao abordados problemas de roteamento de ve´ıculo com coleta e en-

trega. Dentre eles trabalhou-se, o problema de roteamento de ve´ıculo com coleta e en-

trega, especiﬁcamente, o Roteamento de Ve´ıculo com Coleta e Entrega e Janelas de Tempo

(VRPPDTW - Vehicle Route Problem Pickup Delivery with Time Windows) e o Problema

do Caixeiro Viajante com Coleta e Entrega (TSPPD - Traveling Salesman Problem with

Pickup and Delivery). O primeiro foi trabalho com uma abordagem heur´ıstica, busca

local interativa com movimento randˆomico de descida (ILS-MRD), e o segundo atrav´es

por programa¸c˜ao inteira, com algoritmo de branch-and-cut.

Palavras-chave: Roteamento de Ve´ıculo, Caixeiro Viajante, Coleta e Entrega, Janelas

de Tempo, Programa¸c˜ao inteira, Gera¸c˜ao de cortes, Busca Local Iterativa.

In this work are discussed problems with the routing of vehicle pickup and delivery.

Among them worked up, the vehicle routing problem with pickup and delivery, speciﬁcally,

the Vehicle Routing Problem Pickup and Delivery with Time Window (VRPPDTW) and

Traveling Salesman Problem with Pickup and Delivery (TSPPD). The the ﬁrst was wor-

king with a heuristic approach, iterated local search, and second through integer program

with cuts generation, branch-and-cut.

Keywords: Vehicle Route Problem, Traveling Salesman Problem, Pickup and Delivery,

Time Window, Integer Programming, Cut Generation, Iterated Local Search.

xii

xiii

1.1 Motiva¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Principais Contribui¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Organiza¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.1 Vis˜ao Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.2 Classiﬁca¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2.1 Deﬁni¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2.2 Revis˜ao da Literatura . . . . . . . . . . . . . . . . . . . . . . . . 8

2.2.2.1 Problema com Coleta e Entrega . . . . . . . . . . . . . . 8

2.2.2.2 Problema de Entrega Expressa . . . . . . . . . . . . . . 9

2.2.2.3 Problema com Contens˜ao de Via . . . . . . . . . . . . . 9

2.2.2.4 Problema “Pe¸ca por uma carona” . . . . . . . . . . . . . 10

2.2.2.5 TSP com Coleta de Retorno e VRP com Coleta de Retorno 10

2.3 Problema de Roteamento de Ve´ıculos com Coleta e Entrega e Janelas de

Tempo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.3.1 Revis˜ao de Literatura . . . . . . . . . . . . . . . . . . . . . . . . . 12

Sum´ario viii

2.3.2 Deﬁni¸c˜ao e Formula¸c˜ao Matem´atica . . . . . . . . . . . . . . . . . 14

2.4 Problema do Caixeiro Viajante com Coleta e Entrega . . . . . . . . . . . 16

2.4.1 Revis˜ao de Literatura . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.4.2 Deﬁni¸c˜ao Formal do Problema . . . . . . . . . . . . . . . . . . . . 17

3.1 Metaheuristica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.1.1 Busca Local Iterada (ILS) . . . . . . . . . . . . . . . . . . . . . . 18

3.1.2 M´etodo Randˆomico de Descida (MRD) . . . . . . . . . . . . . . . 19

3.1.3 Objetivo e custos . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.2 Solu¸c˜ao Inicial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.2.1 Vizinhan¸ca mais pr´oxima - C1 . . . . . . . . . . . . . . . . . . . . 21

3.2.2 Flex´ıvel - C2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.3 Estrutura de Vizinhan¸cas . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.3.1 Opera¸c˜ao PD-Shift . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.3.2 Opera¸c˜ao PD-Exchange . . . . . . . . . . . . . . . . . . . . . . . 24

3.3.3 Opera¸c˜ao PD-Rearrange . . . . . . . . . . . . . . . . . . . . . . . 24

3.3.4 Opera¸c˜ao PD-Eliminate . . . . . . . . . . . . . . . . . . . . . . . 25

3.3.5 Viabiliza Rota . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.4 Perturba¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.5 Resultados computacionais . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.1 Formula¸c˜ao N˜ao Orientada . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4.1.1 Desigualdades v´alidas . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.1.1.1 GOC - Generalized Order Constraints . . . . . . . . . . 38

4.1.1.2 Outras Desigualdades . . . . . . . . . . . . . . . . . . . 38

Sum´ario ix

4.2 Formula¸c˜ao Orientada . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.2.1 Modelo Matem´atico . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.2.2 Desigualdade Fortalecida e Separa¸c˜ao por Programa¸c˜ao Inteira . . 41

4.3 Formula¸c˜ao Estendida . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.3.1 Corte do dep´osito `a duas coletas . . . . . . . . . . . . . . . . . . . 47

4.3.2 Formula¸c˜ao por Fluxos Equivalente . . . . . . . . . . . . . . . . . 48

4.4 Testes e resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.4.1 Descrevendo as Instˆancias . . . . . . . . . . . . . . . . . . . . . . 52

4.4.2 Resultados Computacionais . . . . . . . . . . . . . . . . . . . . . 53

5.1 Conclus˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.2 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

1 Problemas de Coleta e Entrega (segundo Parragh, Doerner e Hartl (2008a,

2008b)) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Algoritmo ILS-MRD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3 Algoritmo MRD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4 Perturba¸c˜ao - ILS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

5 Vizinhan¸ca mais pr´oxima - C1 . . . . . . . . . . . . . . . . . . . . . . . . 22

6 Opera¸c˜ao PD-Shift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

7 Opera¸c˜ao PD-Exchange . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

8 Opera¸c˜ao PD-Rearrange . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

9 Restri¸c˜ao (4.5) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

10 GOC com m = 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

11 Desigualdades da formula¸c˜ao orientada . . . . . . . . . . . . . . . . . . . 41

12 Desigualdades do Corte - Formula¸c˜ao Inteira . . . . . . . . . . . . . . . . 42

13 Solu¸c˜ao para uma instˆancia com 3 pares de clientes representada como

um caminho em G



. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

14 Grafo G

- Coleta para entrega (em w) . . . . . . . . . . . . . . . . . . . 47

15 Grafo G

- Dep´osito para coleta (em w) . . . . . . . . . . . . . . . . . . . 47

16 Grafo G

- Entrega para dep´osito (em w) . . . . . . . . . . . . . . . . . . 48

17 Solu¸c˜ao Fracion´aria da Instˆancia prob10a . . . . . . . . . . . . . . . . . . 49

18 Decomposi¸c˜ao em rotas da solu¸c˜ao fracion´aria da instˆancia prob10a . . . 50

19 Retirando as entregas 15 e 17, (restri¸c˜ao (4.32) com F = 0, 5) . . . . . . 50

20 Retirando a entrega 15 (restri¸c˜ao (4.32) com F = 1) . . . . . . . . . . . . 50

Lista de Figuras xi

21 Retirando a entrega 17 (restri¸c˜ao (4.32) com F = 1) . . . . . . . . . . . . 50

1 Resultados das Instˆancias de 100 pares - LC . . . . . . . . . . . . . . . . 27

2 Resultados das Instˆancias de 100 pares - LR . . . . . . . . . . . . . . . . 28

3 Resultados das Instˆancias de 100 pares - LRC . . . . . . . . . . . . . . . 28

4 Resultados das Instˆancias de 200 pares - LC . . . . . . . . . . . . . . . . 29

5 Resultados das Instˆancias de 200 pares - LR . . . . . . . . . . . . . . . . 29

6 Resultados das Instˆancias de 200 pares - LRC . . . . . . . . . . . . . . . 30

7 Resultados das Instˆancias de 100 pares - LC . . . . . . . . . . . . . . . . 31

8 Resultados das Instˆancias de 100 pares - LR . . . . . . . . . . . . . . . . 32

9 Resultados das Instˆancias de 100 pares - LRC . . . . . . . . . . . . . . . 33

10 Resultados das Instˆancias de 200 pares - LC . . . . . . . . . . . . . . . . 34

11 Resultados das Instˆancias de 200 pares - LR . . . . . . . . . . . . . . . . 34

12 Resultados das Instˆancias de 200 pares - LRC . . . . . . . . . . . . . . . 35

13 Relaxa¸c˜ao Linear da Formula¸c˜ao Orientada (4.9-4.14) × N˜ao-orientada

(4.2-4.6): sem cortes adicionais . . . . . . . . . . . . . . . . . . . . . . . 54

14 Relaxa¸c˜ao Linear da Formula¸c˜ao orientada (4.9-4.14) + (4.15) + cortes

CPLEX × N˜ao-orientada (4.2-4.6) + todos os cortes da se¸c˜ao 4.1.1 +

cortes CPLEX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

15 Relaxa¸c˜ao Linear da Formula¸c˜ao Estendida (4.24-4.33) + cortes de 2

coletas × N˜ao-orientada (4.2-4.6) + todos os cortes da se¸c˜ao 4.1.1 . . . . 56

16 Relaxa¸c˜ao Linear da Formula¸c˜ao de Fluxo (4.35-4.47) × N˜ao-orientada

(4.2-4.6) + todos os cortes da se¸c˜ao 4.1.1 . . . . . . . . . . . . . . . . . . 56

COPPEAD : Instituto de Pesquisa e P´os-Gradua¸c˜ao em Administra¸c˜ao de

Empresas da Universidade Federal do Rio de Janeiro (UFRJ)

DARP : do inglˆes: Dial-a-Ride Problem - Problema de Dar uma Volta

EDP : do inglˆes: Express Delivery Problem - Problema de Entrega

Expressa

GGA : do inglˆes: Grouping Genetic Algorithm - Algoritmo Gen´etico

Agrupado

ILS : do inglˆes: Iterated Local Search - Busca Local Iterada

IPEA : Instituto de Pesquisa Econˆomica Aplicada

FGV : Funda¸c˜ao Get´ulio Vargas

GPDP : do inglˆes: General Pickup and Delivery Problem - Problema

Geral de Coleta e Entrega

MDARP : do inglˆes: M-Dial-a-Ride Problem - Sem tradu¸c˜ao, disp˜oe de

servi¸cos de transporte em domic´ılio

MRD : M´etodo Randˆomico de Descida

PAC : Programa de Acelera¸c˜ao do Crescimento

PIB : Produto Interno Bruto

PDP : do inglˆes: Problem Pickup and Delivery - Problem Problema

de Coleta e Entrega

PDPTW : do inglˆes: Problem Pickup and Delivery with Time Windows -

Problem Problema de Coleta e Entrega com Janelas de Tempo

RTS : do inglˆes: Reactive Tabu Search - Busca Tabu Reativa

SA : Simulated Annealing

TS : do inglˆes, Tabu Search - Buscas Tabu

TSP : do inglˆes: Traveling Salesman Problem - Problema do Cai-

xeiro Viajante

TSPB : do inglˆes: Traveling Salesman Problem with Backhauls - Pro-

blema do Caixeiro Viajante com Coleta de retorno

Siglas e Abrevia¸c˜oes xiv

TSPPDL : do inglˆes: The Pickup and Delivery Traveling Salesman Pro-

blem with LIFO Loading - Problema do Caixeiro Viajante com

Coleta e Entrega em Forma de Fila

TSPPDF : do inglˆes: Traveling Salesman Problem First-In-First-Out Lo-

ading - Problema do Caixeiro Viajante com Coleta e Entrega

em Forma de Pilha

TSPPD : do inglˆes: Traveling Salesman Problem with Pickup and Deli-

very - Problema do Caixeiro Viajante com Coleta e Entrega

TSPSPD : do inglˆes: Traveling Salesman Problem With Simultaneous

Pickup and Delivery - Problema do Caixeiro Viajante com

Coleta e Entrega Simultˆaneas

VRP : do inglˆes: Vehicle Route Problem - Problema de Roteamento

de Ve´ıculo

VRPB : do inglˆes: Vehicle Routing Problem Problema with Backhauls

- Roteamento de Ve´ıculos com Coleta de Retorno

VRPPDTW : do inglˆes: Vehicle Route Problem Pickup Delivery with Time

Windows - Roteamento de Ve´ıculo com Coleta e Entrega e

Janelas de Tempo

VRPTW : do inglˆes: Vehicle Routing Problem With Time Windows -

Problema de Roteamento de Ve´ıculos com Janelas de Tempo

VNS : do inglˆes: Variable Neighborhood Search - Busca por Vizi-

nhan¸ca Vari´avel

A expans˜ao do com´ercio mundial levou a um crescimento signiﬁcativo da demanda

por transporte. Nas ´ultimas d´ecadas, observou-se pronunciada intensiﬁca¸c˜ao dos ﬂuxos

comerciais, exigindo a moderniza¸c˜ao/expans˜ao dos meios de transporte e, conseq

uente-

mente, o aumento dos investimentos no sistema log´ıstico.

O processo de globaliza¸c˜ao que integrou as economias nacionais trouxe benef´ıcios,

mas passou a exigir que a infra-estrutura n˜ao apenas atendesse `as necessidades b´asicas

da popula¸c˜ao, mas que tamb´em servisse como suporte `a competitividade das empresas.

Os custos envolvidos no processo de produ¸c˜ao, tanto os anteriores `a fabrica¸c˜ao (como

custo de energia) quanto os posteriores (como o de transporte), tˆem grandes implica¸c˜oes

sobre o pre¸co ﬁnal dos produtos, vinculando fortemente a competitividade das empresas

`a infra-estrutura nacional.

Entre 2005 e 2007 foram aplicados na recupera¸c˜ao das rodovias cerca de R$ 4,9 bilh˜oes

de reais. Percentual baixo se comparado aos R$ 25 bilh˜oes gastos com pagamento de

indeniza¸c˜oes, perdas de cargas, tempo durante o qual o ve´ıculo permanece parado, reparos

e/ou substitui¸c˜oes causadas pela m´a conserva¸c˜ao das rodovias brasileiras. Em raz˜ao desse

conjunto de deﬁciˆencias, o custo log´ıstico no Brasil atinge 12,63% do PIB, contra 8,19% nos

EUA. Deve-se considerar que o transporte responde pela maior parcela do custo log´ıstico.

“Segundo a COPPEAD, os custos com transporte chegam a 60% dos custos log´ısticos e a

redu¸c˜ao de custos nessa ´area ´e muito importante, pois correspondem, em m´edia, 20% do

custo total das empresas.” (DIAS; LIMA, 2008)

Os problemas de roteamento de ve´ıculo com coleta e entrega est˜ao diretamente relaci-

onados aos esfor¸cos para a redu¸c˜ao dos custos de transportes, estes problemas se resumem

ao atendimento de uma demanda, que pode se apresentar na forma de coleta e/ou entrega

de pessoas ou mercadorias em uma determinada regi˜ao geogr´aﬁca ou espacial. A maio-

1.2 Principais Contribui¸c˜oes 2

ria das aplica¸c˜oes para estes problemas s˜ao geogr´aﬁcas e representadas por consumidores

distribu´ıdos em uma ´area de atendimento. Desta forma, o objetivo ´e desenvolver metodo-

logias para atender as demandas de forma otimizada, visando `a redu¸c˜ao dos gastos com

ve´ıculos e com o deslocamento dos mesmos.

Esta disserta¸c˜ao tem o interesse em dois casos de problemas de roteamento de ve´ıculos

envolvendo coleta e entrega: com janelas de tempo e o problema do caixeiro viajante

(roteamento de um ´unico ve´ıculo).

No primeiro caso, aplicou-se a heur´ıstica de busca local iterada com o m´etodo randˆo-

mico de descida. Esse algoritmo, apesar de simples, mostrou-se capaz de encontrar boas

solu¸c˜oes para o problema, comparado a outros algoritmos encontrados na literatura.

No segundo caso, foram propostas novas formula¸c˜oes lineares inteiras e t´ecnicas para

gera¸c˜ao de cortes, levando ao desenvolvimento de algoritmos do tipo branch-and-cut. As

formula¸c˜oes estendidas, apesar de n˜ao serem capazes de resolver instˆancias de maior porte

em tempo razo´avel, mostraram-se satisfat´orias ao obter limites inferiores bastante fortes

para o problema.

O Cap´ıtulo 2 descreve o problema de roteamento de ve´ıculos de maneira geral e

algumas de suas variantes. A seguir, no Cap´ıtulo 3, uma abordagem heur´ıstica para

o Problema de Roteamento de Ve´ıculo com Coleta e Entrega com Janelas de Tempo ser´a

apresentada, como tamb´em compara¸c˜oes dos resultados com os obtidos na literatura. O

Cap´ıtulo 4, dedica-se ao problema do Caixeiro Viajante com Coleta e Entrega um caso

particular de roteamento onde se prop˜oem algumas formula¸c˜oes e algoritmos para esse

problema. Finalmente, no Cap´ıtulo 5, tem-se as considera¸c˜oes ﬁnais e trabalhos futuros.

Problema de roteamento de ve´ıculo (VRP - Vehicle Routing Problem) ´e um nome

gen´erico para uma s´erie de problemas que tem as seguintes caracter´ısticas: estabelecer

e organizar rotas ou itiner´arios eﬁcientes para ve´ıculos realizarem coletas/entregas de

mercadorias, dispondo de uma frota de ve´ıculos idˆenticos ou n˜ao, atendendo a um conjunto

de clientes, cada um com uma demanda espec´ıﬁca. Na literatura, Dantzig e Ramser (1959)

foram os primeiros a formular o VRP quando estudaram a aplica¸c˜ao real na distribui¸c˜ao

de gasolina para postos de venda de combust´ıvel.

H´a muitas variantes para esse problema, algumas com janelas de tempo, outras com

coleta e entrega, com capacidade, com m´ultiplos dep´ositos, peri´odicas, simultˆaneas, etc.

Nesta se¸c˜ao s˜ao apresentados os conceitos b´asicos e os principais parˆametros que

caracterizam as variantes desse problema com coleta e entrega. A partir do problema

b´asico, s˜ao apresentadas suas extens˜oes e nos problemas relacionados a este trabalho

haver´a uma ˆenfase em sua explana¸c˜ao.

O VRP introduzido por Dantzig e Ramser (1959), ´e deﬁnido como um grafo n˜ao

orientado, G = (V, E), onde V = {0, 1, . . . , N} ´e o conjunto de v´ertices e E = {(i, j) :

i, j ∈ V, i < j} o conjunto de arestas. O v´ertice 0 representa o dep´osito de onde partem os

m ve´ıculos e os demais v´ertices s˜ao cidades ou clientes. Um custo n˜ao negativo, distˆancia

ou tempo de viagem ´e dado por c

deﬁnido em E. Cada v´ertice i tem uma demanda q

um tempo de servi¸co s

. O VRP tem como objetivo deﬁnir rotas entre um dep´osito e um

conjunto de pontos de entrega que minimize o n´umero de ve´ıculos, a distˆancia percorrida

ou o tempo. As restri¸c˜oes b´asicas do problema consistem em: cada cidade ´e visitada uma

´unica vez por um ´unico ve´ıculo; cada rota ´e iniciada num dep´osito e ﬁnalizada no mesmo

2.1 Vis˜ao Geral 4

dep´osito; todas as demandas de todos os consumidores devem ser satisfeitas, respeitando

a capacidade Q do ve´ıculo.

Outras restri¸c˜oes que podem ser acrescentadas ao problema s˜ao: restri¸c˜ao no n´umero

de pontos de entrega em cada rota; restri¸c˜ao de tempo ou distˆancia de uma rota; restri¸c˜ao

de janelas de tempo: cada ponto deve ser visitado em um per´ıodo de tempo espec´ıﬁco;

restri¸c˜ao de precedˆencia entre cidades: o ponto de entrega i deve ser visitado antes do

ponto j; tipo de frota: ve´ıculos dispon´ıveis para execu¸c˜ao das rotas s˜ao homogˆeneos ou

heterogˆeneos; quantidade de ve´ıculos contidos na frota: quantidade limitada ou ilimitada;

capacidade dos ve´ıculos: ve´ıculos com capacidade limitada ou ilimitada; quantidade de

dep´ositos: ´unico dep´osito ou v´arios dep´ositos, etc.

Encontram-se na literatura v´arios trabalhos publicados que tratam diversos proble-

mas de roteamento de ve´ıculos com diferentes abordagens: com um ´unico dep´osito (BE-

ASLEY, 1983; HO; GENDREAU, 2006; CAMPOS; MOTA, 2000; BR

aYSY; GENDREAU; DUL-

LAERT, 2004); ou v´arios dep´ositos (SALHI; NAGY, 1999; FAN; WANG; CHEN, 2007); com

ve´ıculos homogˆeneos (CAMPOS; MOTA, 2000; CHIN; KIT; LIM, 1999; BR

aYSY; GENDREAU;

DULLAERT, 2004) ou heterogˆeneos (BELFIORE; Y.YOSHIZAKI, 2006; CHOI; TCHA, 2007);

modelo est´atico (HO; GENDREAU, 2006; CHIN; KIT; LIM, 1999) ou dinˆamico (ALVARENGA

et al., 2005; MONTEMANNI et al., 2002); com servi¸cos de coleta e/ou entrega (MIN, 1989)

com restri¸c˜ao de janelas de tempo (REIMANN; DOERNER; HARTL, 2002; OMBUKI; ROSS;

HANSHAR, 2006; ROUSSEAU; GENDREAU; PESANT, 2002; BR

aYSY; GENDREAU; DULLAERT,

2004; DUMITRESCU et al., 2008) entre outros.

Um problema bastante abordado na literatura ´e o Problema de Roteamento de Ve´ı-

culos com Janelas de Tempo (VRPTW, do inglˆes Vehicle Routing Problem With Time

Windows) que inclui um intervalo de tempo para come¸car e terminar o atendimento no

consumidor e ainda um intervalo para sa´ıda e retorno ao dep´osito (ALVARENGA et al.,

2005).

Este trabalho apresenta uma abordagem heur´ıstica (Cap´ıtulo 3) para um caso particu-

lar do Roteamento de Ve´ıculos com Coleta e Entrega e Janelas de Tempo (VRPPDTW,

do inglˆes Vehicle Routing Problem Pickup Delivery With Time Windows) descrita na

Se¸c˜ao 2.3.

Outro problema bastante abordado na literatura, o Problema do Caixeiro Viajante,

consiste em encontrar um trajeto que visite N cidades diferentes, sem repeti¸c˜ao, retor-

nando `a origem e utilizando a menor rota poss´ıvel, pode ser considerado um problema

de roteamento de ve´ıculos quando esse possui apenas um ´unico ve´ıculo com capacidade

2.2 Classiﬁca¸c˜ao 5

ilimitada. Este trabalho apresenta um algoritmo de branch-and-cut (Cap´ıtulo 4) para

o Problema do Caixeiro Viajante com Coleta e Entrega (TSPPD, do inglˆes Traveling

Salesman Problem with Pickup and Delivery) descrito na Se¸c˜ao 2.4.

V´arios problemas de roteamento de ve´ıculos com coleta e entrega tˆem sido estudados

para tratar as diferentes situa¸c˜oes reais. Todos eles se concentram em um ´unico objetivo:

uso eﬁciente de uma frota de ve´ıculos que deve satisfazer demandas de entrega e/ou coleta

de um conjunto de consumidores ou clientes. As demandas de cada consumidor devem

ser satisfeitas por um ´unico ve´ıculo (XU et al., 2003).

Tendo em vista essa semelhan¸ca, Savelsbergh e Sol (1995) apresentam o Problema

Geral de Coleta e Entrega (GPDP, do inglˆes General Pickup and Delivery Problem)

que combina v´arias caracter´ısticas encontradas entre esses problemas pr´aticos de coleta

e entrega. O GPDP consiste em deﬁnir um conjunto de rotas a ﬁm de satisfazer um

conjunto de demandas de transporte. Recentemente Berbeglia et al. (2007), Parragh,

Doerner e Hartl (2008a) e Parragh, Doerner e Hartl (2008b), ﬁzeram uma classiﬁca¸c˜ao

mais detalhada desse tipo de problema.

Cada consumidor possui demandas de coleta e entrega. As demandas de coleta pos-

suem informa¸c˜oes sobre a carga total a ser coletada pelo ve´ıculo e em quais consumidores

essa carga deve ser entregue posteriormente. As demandas de entrega possuem informa-

¸c˜oes sobre a carga total a ser entregue e em quais consumidores elas devem terem sido

coletadas anteriormente. Portanto, existe uma regra de precedˆencia entre consumidores,

pois para satisfazer uma demanda de entrega o ve´ıculo dever´a satisfazer anteriormente a

respectiva demanda de coleta.

A posi¸c˜ao inicial e a posi¸c˜ao ﬁnal dos ve´ıculos tamb´em s˜ao informadas. Assim, o

objetivo ´e deﬁnir rotas otimizadas que tenham como ponto de partida e ponto de chegada

`aqueles deﬁnidos para os ve´ıculos e que satisfa¸cam todas as demandas dos consumidores

sem extrapolar a capacidade dos ve´ıculos.

Parragh, Doerner e Hartl (2008a, 2008b) dividem o Problema Geral de Coleta e En-

trega em dois grupos:

• Grupo 1: transporte de cargas do dep´osito para os consumidores e dos consumidores

para o dep´osito

2.2 Classiﬁca¸c˜ao 6

• Grupo 2: transporte de carga entre consumidores

No primeiro grupo todos os ve´ıculos partem do dep´osito contendo a carga necess´aria

para satisfazer as demandas de entrega dos consumidores. As cargas recolhidas pelo

ve´ıculo nos consumidores devem ser entregues no dep´osito. Para o segundo grupo, os

ve´ıculos partem de um ponto inicial sem qualquer carga e percorrem v´arios pontos de

coleta e/ou entrega de itens e ent˜ao retornam a um ponto ﬁnal. Neste caso demandas de

entrega s˜ao sempre satisfeitas por itens coletados anteriormente pelo ve´ıculo. (veja Figura

Figura 1: Problemas de Coleta e Entrega (segundo Parragh, Doerner e Hartl (2008a,

2008b))

Outra classiﬁca¸c˜ao foi feita por Berbeglia et al. (2007) onde divide o Problema Geral

de Coleta e Entrega em trˆes grupos, de acordo com elementos: estrutura, visitas e ve´ıculos.

Estrutura refere-se `a quantidade de origens e destinos de uma mercadoria, sendo o elemento

chave dessa divis˜ao. Este ´e subdividido em trˆes partes:

– muito-para-muitos (M-M), qualquer v´ertice pode servir como uma fonte ou

como um destino para qualquer mercadoria.

– um-para-muitos-para-um (1-M-1), as mercadorias est˜ao inicialmente dispon´ı-

veis num armaz´em e se destinam aos v´ertices (clientes), al´em disso muitas

mercadorias dos clientes est˜ao destinadas ao dep´osito. Os conjuntos de pares

coleta-entrega dos clientes n˜ao s˜ao necessariamente disjuntos (ROPKE; PISIN-

GER, 2006b) e, muitas vezes, coincidem como na distribui¸c˜ao de bebidas e a

coleta de suas garrafas vazias (PRIV´e et al., 2006).

– um-para-um (1-1), cada produto tem uma origem e destino determinado. Pro-

blemas desse tipo, surgiram, por exemplo, nas opera¸c˜oes dos correios e nos

servi¸cos de porta-em-porta (CORDEAU; LAPORTE, 2003a).

2.2 Classiﬁca¸c˜ao 7

Visitas fornece informa¸c˜oes sobre a forma como as opera¸c˜oes de coletas e entregas s˜ao re-

alizadas nos clientes. Usa-se a nota¸c˜ao PD para indicar que o cliente ´e visitado

somente uma vez na opera¸c˜ao de coleta e entrega (PD, se estas opera¸c˜oes s˜ao rea-

lizadas juntas, e P/D se cada v´ertice ´e uma coleta ou entrega independente). Al´em

disso usa-se a letra T quando alguns v´ertices podem ser utilizados como um ponto

intermedi´ario de transbordo.

Ve´ıculos indica o n´umero de ve´ıculos utilizados, na solu¸c˜ao. Sempre que um elemento ´e

indeﬁnido, usa-se a nota¸c˜ao “-”.

Claramente, est´a classiﬁca¸c˜ao n˜ao contempla todos os tipos de PDPs, com todas suas

restri¸c˜oes, objetivos alternativos, n´umero de mercadorias, etc., mas consegue-se abranger

os casos de forma geral.

Os Problema de Coleta e Entrega (PDP, do inglˆes Pickup and Delivery Problem)

constituem uma importante classe dos problemas de roteamento de ve´ıculos em que as

mercadorias ou pessoas tˆem que ser transportados entre origens e destinos. O PDP ´e

um problema do grupo onde o transporte de cargas ´e feito entre consumidores (Grupo

2, segundo Parragh, Doerner e Hartl (2008a)). Estes problemas vˆem sendo estudados a

mais de 30 anos e aplicam-se a diversos contextos, como o da log´ıstica, servi¸cos e rob´otica.

No PDP cada demanda de coleta possui informa¸c˜oes sobre a carga total a ser coletada

pelo ve´ıculo e o destino dessa carga. As demandas de entrega possuem informa¸c˜oes sobre

a carga total a ser entregue e a origem da carga. Todos os ve´ıculos, ent˜ao, partem de

um dep´osito para satisfazer as demandas e retornam novamente ao dep´osito ﬁnalizando o

trajeto (SAVELSBERGH; SOL, 1995).

A maioria dos atuais PDPs podem ser deﬁnidos dentro do seguinte quadro. Dado G =

(V, A) um grafo completo e n˜ao orientado com o conjunto de v´ertices V = {0, 1, . . . , N},

onde o v´ertice 0 representa o dep´osito e cada um dos v´ertices restantes (1, . . . , N), um

cliente. Arcos s˜ao deﬁnidos como A = {(i, j) : i, j ∈ V, i = j}. Cada arco (i, j) ∈ A tem

um custo c

n˜ao-negativo associado a ele que satisfaz a desigualdade triangular, o custo

corresponde `a dura¸c˜ao da viagem. H = {1, . . . , p} ´e o conjunto de mercadorias a serem

transportadas. Cada v´ertice, incluindo o dep´osito, pode necessitar/gerar uma demanda

para cada tipo de mercadoria. D = (d

) representa a matriz de tipos de mercadoria.

Assim, d

, positivo, refere-se `a quantidade de mercadoria h que sai para o v´ertice i, e −d

2.2 Classiﬁca¸c˜ao 8

negativo, ´e a quantidade de mercadoria h requerida pelo v´ertice i. No caso de transporte

de passageiros ´e mais comum falar em pedido em vez de mercadoria, mas do ponto de vista

de modelagem matem´atica n˜ao h´a diferen¸ca. Assume-se que



i∈V

= 0 : h ∈ H, ou

seja, deve haver um equil´ıbrio entre coleta e entrega de cada mercadoria. K = {1, . . . , m}

´e o conjunto de ve´ıculos dispon´ıveis com capacidade Q. Uma rota ´e um circuito com alguns

v´ertices, come¸cando e terminando no dep´osito. PDPs consistem em construir rotas com

m ve´ıculos tais que:

• Todos as coletas e entregas sejam satisfeitas;

• A carga de um ve´ıculo n˜ao exceda a sua capacidade;

• A soma dos custos das rotas seja minimizada.

• Em uma rota v´alida um ve´ıculo come¸ca e termina seu trajeto no dep´osito.

O Problema de Roteamento de Ve´ıculos com Coleta e Entrega (VRPPD, do inglˆes

Vehicle Routing Problem with Pickup and Delivery) ´e uma extens˜ao do Problema de

Coleta e Entrega. Em ambos, as cargas s˜ao transportadas entre pontos de coleta e en-

trega (Grupo 2, segundo (PARRAGH; DOERNER; HARTL, 2008a)), mas no VRPPD uma

carga coletada pode ser utilizada para satisfazer qualquer demanda de entrega (PARRAGH;

DOERNER; HARTL, 2008b).

Dumas, Desrosiers e Soumis (1991) propuseram um m´etodo branch-and-bound que ´e

capaz de resolver problemas com at´e 55 pedidos. Outro algoritmo exato foi proposto por

Ruland e Rodin (1997), usando o m´etodo branch-and-cut. Ele mostra formula¸c˜oes para

o PDP como um problema de programa¸c˜ao inteira. Os testes foram feitos com base em

campos a´ereos dos Estados Unidos, gerando redes com 7 a 15 n´os de demanda e coleta.

O tempo de resposta varia de 3 a 1246 segundos.

Outros trabalhos da literatura como Mosheiov (1998), Salhi e Nagy (1999), Montan´e e

Galv˜ao (2006) trabalham com o transporte de cargas do dep´osito para os consumidores e

dos consumidores para o dep´osito (Grupo 1). Nestes casos os ve´ıculos partem do dep´osito

com as cargas a serem entregues nos consumidores e retornam ao dep´osito com as cargas

coletadas pelos consumidores. Um exemplo simples ´e a entrega de engradados, botij˜oes

2.2 Classiﬁca¸c˜ao 9

de g´as, e outros, onde o ve´ıculo parte do dep´osito com vasilhames cheios, os quais s˜ao

trocados por vazios, e retornam ao dep´osito.

O Problema de Entrega Expressa (EDP, do inglˆes Express Delivery Problem) foi

proposto por Montan´e, Ferreira e Galv˜ao (1997), a ﬁm de resolver problemas de entrega

a´erea expressa. Ele ´e outro problema com demandas de coleta e entrega em cada n´o.

Neste caso, o atendimento da demanda ´e composto por duas fases. A primeira ´e a de

coleta e a segunda de entrega.

Deve-se notar que as fases de coleta e entrega n˜ao necessariamente coincidem. Uma

rota ´e deﬁnida entre as cidades onde existem demandas de coleta. Todas as demandas

de uma mesma cidade s˜ao agrupadas em um carregador (demanda de coleta). Depois

de efetuadas todas as coletas, o carregamento ´e encaminhado a um distribuidor (ponto

intermedi´ario que pode ser visto como o dep´osito deﬁnido no Problema de Roteamento de

Ve´ıculos). No distribuidor os carregamentos s˜ao desfeitos e as demandas de entrega s˜ao

organizadas conforme a cidade destino. Uma nova rota ´e deﬁnida partindo do distribuidor

at´e as cidades (pontos de demanda de entrega).

O Problema de Entrega Expressa pode ser considerado um misto entre o Grupo 1 e

o Grupo 2, as requisi¸c˜oes de transporte especiﬁcam uma origem e um destino para cada

item o que demonstra uma caracter´ıstica do Grupo 2. No entanto, em uma mesma rota o

ve´ıculo n˜ao efetua coletas e entregas permitindo que todas as demandas a serem entregues

e coletadas partam do ´unico ponto, o distribuidor.

Montan´e, Ferreira e Galv˜ao (1997) mostram algumas heur´ısticas para resolu¸c˜ao do

problema e executa testes com 20 cidades comparando-as com resultados exatos e com

at´e 100 cidades comparado-as entre as heur´ısticas abordadas. Os resultados foram satis-

fat´orios retornando solu¸c˜oes bem pr´oximas da ´otima.

Caricato et al. (2003) abordam o problema de coleta e entrega com contens˜ao de via.

Neste contexto, a rede de transporte ´e composta por vias, sendo que, cada uma possui

uma capacidade unit´aria, ou seja, em cada via pode trafegar um ´unico ve´ıculo. Quando

dois ou mais ve´ıculos tentam entrar na via ao mesmo tempo, uma contens˜ao ´e aplicada

e o ´ultimo deles ´e removido ou roteado novamente. O autor apresenta duas heur´ısticas

2.2 Classiﬁca¸c˜ao 10

seq

uenciais e uma heur´ıstica baseada na metaheur´ıstica busca tabu paralela.

O Problema “Pe¸ca por uma carona” (DARP, do inglˆes Dial-a-Ride Problem) ´e um

Problema de Coleta e Entrega onde a carga s˜ao pessoas, chamadas de clientes ou con-

sumidores, e o tamanho das cargas s˜ao todas iguais a 1. Os clientes s˜ao recolhidos em

locais pr´e-deﬁnidos e transportados para pontos conhecidos. O objetivo ´e minimizar o

n´umero de ve´ıculos, se o problema ´e composto por m´ultiplos ve´ıculos (m-dial-a-ride ou

MDARP), ou distˆancia trafegada, ou ambos. O problema deve considerar o tempo gasto

no embarque e desembarque de passageiros.

Este problema foi proposto por Psaraﬁs (1980) que desenvolveu um algoritmo de pro-

grama¸c˜ao dinˆamica para casos com um ´unico ve´ıculo. Existem na literatura algumas

referˆencias apresentando heur´ısticas para resolu¸c˜ao do trabalho. Ho e Gendreau (2006)

implementaram um algoritmo busca tabu e um algoritmo h´ıbrido utilizando GRASP e

busca tabu. Ele comprovou que os resultados do primeiro algoritmo foram melhores que

o segundo, apesar da maior robustez do segundo. Cordeau e Laporte (2003b) tamb´em

propuseram uma heur´ıstica de busca tabu para o problema com m´ultiplos ve´ıculos. Berg-

vinsdottir (2004) apresenta um algoritmo gen´etico que utiliza a cl´assica estrat´egia “dividir

e rotear”, assim, a fase de divis˜ao dos n´os ´e feita com um algoritmo gen´etico.

O trabalho apresentado por Cordeau (2006) compara a solu¸c˜ao obtida em um al-

goritmo branch-and-cut utilizando o CPLEX. Os testes foram feitos com redes de, no

m´aximo, 32 consumidores, mostrando um maior desempenho do m´etodo branch-and-cut.

O problema dial-a-ride pode ser associado ao Grupo 2, pois considera as requisi¸c˜oes

de transporte associadas a uma origem e um destino.

O Problema do Caixeiro Viajante com Coleta de Retorno (TSPB, do inglˆes Traveling

Salesman Problem with Backhauls) e o Problema de Roteamento de Ve´ıculos com Coleta

de Retorno s˜ao extens˜oes do TSP e VRP, respectivamente. A diferen¸ca ´e que ambos

trabalham com coleta e entrega, sendo que todas as entregas devem ser conclu´ıdas antes

que as coletas possam ser efetuadas. Ambos os problemas consideram o transporte de

carga entre dep´osito e consumidor e vice-versa, tornando-o um problema do Grupo 1.

Goetschalckx e Jacobs-Blecha (1993) apresentam uma heur´ıstica baseada no problema

2.3 Problema de Roteamento de Ve´ıculos com Coleta e Entrega e Janelas de Tempo 11

de assinalamento generalizado. Gelogullari (2004) mostra um algoritmo exato para reso-

lu¸c˜ao do VRPB e Reimann, Doerner e Hartl (2002) aplicam a metaheur´ıstica “Colˆonia de

Formigas”.

Potvin, Duhamel e Guertin (1996) mostram uma heur´ıstica construtiva para o VRPB.

Ela insere cada consumidor na rota usando uma ordem de prioridade. Posteriormente, os

autores prop˜oem um algoritmo gen´etico para melhorar a qualidade das solu¸c˜oes.

Ghaziri e Osman (2003) prop˜oem uma rede neural para resolu¸c˜ao do TSPB. Os re-

sultados obtidos mostram que a abordagem proposta ´e compar´avel com as heur´ısticas

encontradas na literatura em termos de qualidade da solu¸c˜ao e recursos computacionais.

Os testes foram aplicados em grandes instˆancias, superiores a 1000 consumidores.

Nessa variante, o Problema com Coleta e Entrega com Janelas de Tempo (PDPTW)

pretende atender a um n´umero de pedidos e de ve´ıculos. O pedido consiste em pegar

mercadorias num local e entreg´a-las noutro. Duas janelas temporais s˜ao atribu´ıdas a

cada pedido: uma janela de coleta, tempo que especiﬁca quando as mercadorias podem

ser apanhadas e um prazo de entrega, janela que avisa quando a mercadoria pode ser

entregue. Al´em disso, um tempo de servi¸co est´a associado a cada coleta e entrega. O

tempo de servi¸co indica quanto tempo levar´a para a coleta ou a entrega ser realizada.

permitido um ve´ıculo chegar a um local antes da in´ıcio da janela de tempo, mas ent˜ao

o ve´ıculo deve esperar at´e o in´ıcio da janela do tempo antes de iniciar a opera¸c˜ao. Um

ve´ıculo n˜ao pode nunca chegar a um local ap´os o t´ermino do tempo da janela local. A

cada pedido ´e atribu´ıdo um conjunto de ve´ıculos vi´avel. Isto pode, por exemplo, ser usado

para modelar situa¸c˜oes onde alguns ve´ıculos n˜ao podem entrar num determinado local por

causa das dimens˜oes do ve´ıculo.

Cada ve´ıculo tem capacidade limitada e deve sair e retornar ao dep´osito sem que

no meio do trajeto passe pelo dep´osito novamente. Dois ve´ıculos podem ter dep´ositos

de origens e destinos diferentes. A hora de chegada do ve´ıculo ao dep´osito pode variar,

no entanto, o hor´ario de partida do mesmo ´e sempre no instante inicial, se preciso ﬁca

esperando o in´ıcio da janela de tempo do primeiro cliente.

Devem-se construir rotas v´alidas para os ve´ıculos. A rota ´e v´alida se o intervalo das

janelas de tempo e a capacidade dos ve´ıculos s˜ao obedecidos ao longo do percurso, cada

2.3 Problema de Roteamento de Ve´ıculos com Coleta e Entrega e Janelas de Tempo 12

coleta ´e feita antes da entrega, cada coleta e entrega s˜ao realizadas pelo mesmo ve´ıculo e

deve-se analisar se o cliente pode ser atendido pelo ve´ıculo em quest˜ao. As rotas devem

ser constru´ıdas de tal ordem que minimizem seus custos.

Como a quantidade de ve´ıculos ´e limitada, podemos encontrar situa¸c˜oes em que alguns

pedidos n˜ao podem ser atribu´ıdos para nenhum ve´ıculo. Estes pedidos s˜ao colocados em

um banco virtual. Em uma situa¸c˜ao real, um operador humano deve decidir o que fazer

com esses pedidos. O operador pode decidir, por exemplo, pagar hora extra a ﬁm de

servir os pedidos restantes.

O objetivo do problema ´e minimizar a quantidade de ve´ıculos, o custo total da viagem,

tempo total de viagem, tempo total de espera. Sendo que na literatura encontramos

diferentes formas de calcular o custo. Alguns enfocam somente no custo total da viagens

enquanto outros fazem a soma ponderada de cada sub objetivo onde os pesos de cada

parcela da soma indicam sua importˆancia.

Este problema ´e NP-Dif´ıcil sendo um caso especial do problema do caixeiro viajante.

O objetivo deste trabalho ´e desenvolver um m´etodo exato para encontrar boas solu¸c˜oes. O

m´etodo desenvolvido deve ser razoavelmente r´apido, robusto e capaz de lidar com grandes

problemas.

Na literatura encontram-se v´arios trabalho para PDPTW. Destes trabalhos tem-se

tanto m´etodos heur´ısticos como m´etodos exatos.

Gendreau, Laporte e Vigo (1999), Lu e Dessouky (2006) apresentam uma heur´ıstica

baseada em inser¸c˜ao aplicada ao Problema de Coleta e Entrega com Janelas de Tempo

(PDPTW, do inglˆes Pickup and Delivery Problem with Time Windows). O procedimento

consiste em inserir novos n´os em rotas j´a existentes at´e que isso n˜ao seja mais poss´ıvel.

Quando isso ocorre, uma nova rota ´e criada e o processo continua. Para decidir qual o

pr´oximo n´o a ser inserido e onde ele deve ser inserido, a maioria das heur´ısticas de inser¸c˜ao

usam como crit´erio o aumento do custo ou distˆancia da rota com a inser¸c˜ao de um novo

n´o. Dessa forma, o autor prop˜oe uma alternativa para melhorar os resultados inserindo

mais um crit´erio de veriﬁca¸c˜ao. Esse novo crit´erio avalia o grau de liberdade para futuras

inser¸c˜oes de acordo com as janelas de tempo.

Outro aspecto que difere a heur´ıstica proposta por Lu e Dessouky (2006) das demais

´e o fato de considerar solu¸c˜oes visualmente melhores. O autor desenvolve um m´etodo

2.3 Problema de Roteamento de Ve´ıculos com Coleta e Entrega e Janelas de Tempo 13

para avaliar solu¸c˜oes visivelmente mais atrativas chamado Crossing Length Percentage

(CLP) para incorporar na heur´ıstica de inser¸c˜ao. Os resultados obtidos com a heur´ıstica

construtiva baseada em inser¸c˜ao proposta pelo autor foram bons, inclusive, melhores que

a heur´ıstica Simulated Annealing com Busca Tabu proposta por Li e Lim (2001) aplicada

ao mesmo problema (PDPTW).

Nanry e Barnes (2000) apresentaram uma Busca Tabu Reativa (RTS, do inglˆes Re-

active Tabu Search) para resolver o problema de coleta e entrega com janelas de tempo.

Na abordagem feita os autores consideraram os ve´ıculos homogˆeneos localizados em um

´unico dep´osito. O transporte requer a coleta da mercadoria num lugar predeterminado

durante um tempo especiﬁcado (janela de tempo) e esta entregue no seu destino. Esse tra-

balho marca a primeira aplica¸c˜ao da Busca Tabu Reativa para resolu¸c˜ao deste problema

apresentando bons resultados. Os testes foram feitos em redes com 25, 50 e 100 clientes.

No primeiro caso, os testes foram feitos em 29 instˆancias e em todos a solu¸c˜ao ´otima foi

encontrada. J´a no segundo caso, dos 15 testes aplicados, 14 retornaram a solu¸c˜ao ´otima.

E no terceiro, 9 testes foram feitos obtendo 8 solu¸c˜oes ´otimas. Li e Lim (2001) utilizam

uma metaheur´ıstica h´ıbrida para resolver o problema. A heur´ıstica combina Simulated

Annealing e Tabu Search. Lim, Lim e Rodrigues (2002) aplicam otimiza¸c˜ao de “Squeaky

wheel” e busca local para o PDPTW. Sua heur´ıstica ´e testada sobre o conjunto de pro-

blemas propostos por Li e Lim (2001). O trabalho de Lau e Liang (2001) tamb´em aplica

uma Busca Tabu para o PDPTW e eles descrevem v´arias heur´ısticas construtivas para

o problema. Especial aten¸c˜ao ´e dada `a forma de como testar os problemas podem ser

constru´ıdos a partir instˆancias do VRPTW.

William e Barnes (2001) propuseram, para o problema de roteamento de ve´ıculos

com m´ultiplas coletas e entregas e janelas de tempo, uma abordagem de uma busca tabu

reativa para minimizar o custo das viagem, utilizando uma penalidade na fun¸c˜ao objetivo

ao tempo de viagem, penalidade por violar as restri¸c˜oes de tempo de carga e das janelas

de tempo. O abordagem foi testada em instˆancias de 25, 50 e 100 clientes. Estes testes

foram constru´ıdos a partir de instˆancias de Solomon (1987).

Xu et al. (2003) consideram um PDPTW com v´arias restri¸c˜oes da vida real, incluindo

m´ultiplas janelas temporais, compatibilidade e restri¸c˜oes de tempo m´aximo de condu-

¸c˜ao. O problema ´e resolvido usando uma heur´ıstica de gera¸c˜ao de colunas. Seu artigo

consideram instˆancias com at´e 500 pedidos.

Sigurd, Pisinger e Sig (2004) resolveram o PDPTW relacionado ao transporte de gado.

Para este problema foram introduzidas algumas restri¸c˜oes extras, tais como a prioridade

2.3 Problema de Roteamento de Ve´ıculos com Coleta e Entrega e Janelas de Tempo 14

entre os pedidos, o que signiﬁca que alguns pedidos devem ser servidos antes de outros,

a ﬁm de evitar a propaga¸c˜ao de doen¸cas. O problema ´e resolvido `a otimalidade usando

gera¸c˜ao de colunas. Os maiores problemas resolvidos continham mais de 200 pedidos.

Outra heur´ıstica encontrada na literatura para o PDPTW ´e um Algoritmo Gen´etico.

Pankratz (2005) prop˜oe um algoritmo em que cada gene representa um grupo de deman-

das. Os resultados apresentados mostraram que a proposta do GGA (do inglˆes Grouping

Genetic Algorithm) foi boa e bastante competitiva em rela¸c˜ao aos demais m´etodos apre-

sentados na literatura para solucionar o PDPTW.

Outro trabalho encontrado na literatura ´e o de Bent e Hentenryck (2006), Ropke e

Pisinger (2006a) tratam o PDPTW utilizando a heur´ıstica “Large Neighborhood Search”.

Nessa abordagem, Ropke e Pisinger (2006a) limitam a quantidade de ve´ıculos. Esse

m´etodo mostrou bons resultados em um tempo computacional razo´avel em testes feitos

em 350 redes distintas, com um n´umero superior a 500 clientes. O m´etodo, em 50% dos

problemas, provˆe melhores solu¸c˜oes em rela¸c˜ao aos melhores resultados conhecidos na

literatura. A heur´ıstica implementada por Bent e Hentenryck (2006) foi testada sobre os

problemas propostos por Li e Lim (2001).

O PDPTW ´e deﬁnido num grafo orientado G = (N, A) com um conjunto de v´ertices

N = {0, . . . , 2n + 1} e o conjunto de arcos A. O v´ertice 0 e 2n + 1 representam o dep´o-

sito de origem e destino (que podem ser a mesma localidade) enquanto os subconjuntos

P = {1, . . . , n} e D = {n + 1, . . . , 2n} representam os v´ertices de coleta e entrega, respec-

tivamente. Cada demanda i est´a associada com o v´ertice de coleta i e sua entrega i + n.

Para cada i ∈ N est´a associado uma carga q

e uma dura¸c˜ao de servi¸co n˜ao-negativa d

que satisfa¸ca: d

= d

2n+1

= 0, q

= q

2n+1

= 0, e para i = 1, . . . , n, q

≥ 0 e q

i+n

= −q

Uma quantidade ilimitada de ve´ıculos com capacidade Q para servir as demandas. Com

cada arco (i, j) ∈ A est´a associado o custo da rota c

e um tempo de viajem t

. Uma

janela de tempo [e

, l

] ´e ent˜ao associada a cada v´ertice i ∈ P ∪D, onde e

e l

representam

o tempo m´ınimo e m´aximo, respectivamente, para come¸car o servi¸co em i. O dep´osito

tem ent˜ao duas janelas [e

, l

] e [e

2n+1

, l

2n+1

], correspondendo ao tempo que o ve´ıculo pode

partir e chagar ao dep´osito, respectivamente. Assume-se que a desigualdade triangular

´e v´alida tanto para custo quanto para o tempo da rota. Finalmente, para restri¸c˜ao de

grau e precedˆencia, convencionou-se S como sendo o conjunto de todos os subconjuntos

S ⊆ N, tais que, 0 ∈ S, 2n + 1 /∈ S e se i /∈ S ent˜ao i + n ∈ S.

2.3 Problema de Roteamento de Ve´ıculos com Coleta e Entrega e Janelas de Tempo 15

Para qualquer subconjunto de S ⊆ N, deﬁne-se complementar como S = N \ S.

Assim, δ(S) = δ

(S) ∪ δ

−

(S), onde δ

(S) = {(i, j) ∈ A|i ∈ S, j /∈ S} e δ

−

(S) = {(i, j) ∈

A|i /∈ S, j ∈ S}. Por ﬁm, deﬁne-se x(S) =



i,j∈S

e x(S : T ) =



i∈S



j∈T

, onde

S, T ⊆ N.

Para cada arco (i, j) ∈ A est´a associado uma vari´avel bin´aria igual a 1 se e apenas

se o ve´ıculo est´a partindo de i com destino a j. Para cada i ∈ P ∪ D, temos B

como o

instante de tempo a partir do qual o servi¸co pode ser come¸cado, e Q

, como sendo a carga

atual do ve´ıculo.

O Problema do Caixeiro Viajante com Coleta e Entrega e Janelas de Tempo (TSPPDTW)

pode ser formulado como programa¸c˜ao linear inteira mista, como se segue:

Min



i∈N



j∈N

(2.1)

Sujeito a:



i∈N

= 1 ∀j ∈ P ∪ D (2.2)



j∈N

= 1 ∀i ∈ P ∪ D (2.3)



i∈N

≤ |S| − 2 ∀j ∈ P ∪ D (2.4)

≥ (B

+ d

+ t

∀i, j ∈ N (2.5)

≥ (Q

+ q

∀i, j ∈ N (2.6)

≤ B

≤ l

∀i ∈ N (2.7)

max{0, q

} ≤ Q

≤ min{Q, Q + q

} ∀i, j ∈ N (2.8)

∈ {0, 1} ∀i, j ∈ N (2.9)

A fun¸c˜ao objetivo (2.1) minimiza o custo total da rota. As restri¸c˜oes (2.2) e (2.3)

requerem que cada v´ertice seja visitado somente uma vez. As inequa¸c˜oes (2.4) representam

a precedˆencia, onde cada v´ertice i precisa ser visitado antes de i + n, |S| representa a

quantidades de v´ertices neste conjunto. Estas restri¸c˜oes foram originalmente propostas por

Ruland e Rodin (1997) para uma frota homogˆenea mas podem ser aplicadas diretamente

em frotas heterogˆeneas, as condi¸c˜oes s˜ao vi´aveis em ambos os casos. A coerˆencia do

2.4 Problema do Caixeiro Viajante com Coleta e Entrega 16

tempo e da carga s˜ao asseguradas pelas restri¸c˜oes (2.5) e (2.6). As janelas de tempo e da

capacidade do ve´ıculo s˜ao validadas pelas restri¸c˜oes (2.7) e (2.8).

O Problema do Caixeiro Viajante com Coleta e Entrega (TSPPD, do inglˆes Traveling

Salesman Problem with Pickup and Delivery) ´e uma extens˜ao do TSP, sendo que, em

cada ponto ou cada cidade, existe demanda de coleta ou entrega de mercadoria. Se ambas

as demandas (entrega e coleta) puderem ocorrer em um mesmo ponto, o problema ´e

denominado Problema do Caixeiro Viajante com Coleta e Entrega Simultˆaneas (TSPSPD,

do inglˆes Traveling Salesman Problem With Simultaneous Pickup and Delivery). Ambos

os problemas consideram o transporte de cargas do dep´osito para os consumidores e dos

consumidores para o dep´osito. Portanto, eles est˜ao inclu´ıdos no Grupo 1.

O Problema do Caixeiro Viajante com Coleta e Entrega foi proposto por Mosheiov

(1994). O autor apresenta uma abordagem heur´ıstica para o problema e prop˜oe algumas

aplica¸c˜oes.

Balas, Fischetti e Pulleyblank (1995), Ruland e Rodin (1997) trabalham com restri¸c˜oes

de precedˆencia para o TSP e TSPPD que servem de base para v´arios outros trabalhos

com algoritmos exatos.

Gendreau, Laporte e Vigo (1999) apresentam heur´ısticas para TSPPD, a primeira

baseada numa solu¸c˜ao exata de um grupo especial e outra com base em uma busca tabu.

Um algoritmo exato (Branch-and-Cut) ´e descrito por Hern´andez-P´erez e Gonz´alez (2004).

Este ´ultimo mostrou bons resultados em problemas com at´e 75 consumidores.

Sete heur´ısticas de perturba¸c˜ao s˜ao descritas e comparadas por Renaud, Boctor e

Laporte (2002) para o TSPPD. Um estudo probabil´ıstico realizado por Beraldi et al.

(2005) sobre o TSPPD onde apresenta procedimentos com complexidade computacional

de O(n

) na busca de vizinhan¸cas e algumas aproxima¸c˜oes com complexidade O(n

Hern´andez-P´erez e Gonz´alez (2004) estudaram uma generaliza¸c˜ao do conhecido pro-

blema do caixeiro viajante e apresentam um modelo de programa¸c˜ao linear inteira para

este problema e utilizam um algoritmo branch-and-cut para encontrar solu¸c˜oes ´otimas.

2.4 Problema do Caixeiro Viajante com Coleta e Entrega 17

O modelo e os algoritmos s˜ao facilmente adaptados para resolver os casos do TSP com

Coleta e Entrega.

O objetivo do trabalho de Erdogan, Cordeau e Laporte (2009) ´e introduzir uma nova

variante do TSPPD denominado: TSPPD em Forma de Fila (TSPPDF, do inglˆes The

pickup and delivery traveling salesman problem with ﬁrst-in-ﬁrst-out loading) que ´e se-

melhante `a TSPPD, com a diferen¸ca de que as opera¸c˜oes de coleta e entrega devem ser

executadas em forma de ﬁla, o primeiro a entrar deve ser o primeiro a sair. Ele tamb´em

descreve cinco m´etodos para melhorar uma solu¸c˜ao vi´avel, e heur´ısticas que utilizam dois

destes: um algoritmo probabil´ıstico de busca tabu e um algoritmo de busca local iterada.

As instˆancias das heur´ısticas foram adaptadas a partir das instˆancias da TSPLIB. Simi-

larmente Carrabs, Cordeau e Laporte (2007) prop˜oem uma nova variante para o TSPPD

chamada TSPPD em Forma de Pilha (TSPPDL, do inglˆes The pickup and delivery tra-

veling salesman problem with LIFO loading).

Seja G = (V, E), um grafo completo n˜ao orientado, onde V ´e o conjunto de v´ertices e E

o conjunto de arestas. O conjunto V ´e constitu´ıdo pelos v´ertices de coleta e entrega, al´em

de dois v´ertices que correspondem ao dep´osito, `a sa´ıda e ahegada a ele. Um par de v´ertices

de coleta e entrega formam uma requisi¸c˜ao. A quantidade de requisi¸c˜oes ´e indicada por

n. Seja P = {1, . . . , n} o conjunto de v´ertices de coleta e D = {n + 1, . . . , 2n} o conjuntos

dos v´ertices de entrega. O v´ertice de entrega correspondente ao v´ertice de coleta i ∈ P

´e i + n ∈ D. Desta forma, V = P ∪ D ∪ {0, 2n + 1}, onde 0 corresponde a partida do

dep´osito e 2n + 1 a chegada a ele. Para dois v´ertices i e j, i < j, a aresta associada a esse

par ´e denotada como (i, j). Um custo n˜ao-negativo c

´e associado com a aresta (i, j) ∈ E.

O TSPPD consiste em encontrar um caminho hamiltoniano sobre G que deve come¸car

em (0) e terminar em (2n + 1), passando por uma coleta i antes de sua entrega i + n.

Juntando-se a esse caminho a aresta (0, 2n + 1), que n˜ao possui custo, temos um circuito

hamiltoniano sobre G. Maiores detalhes ser˜ao apresentados no Cap´ıtulo 4.

Este cap´ıtulo apresenta detalhes da implementa¸c˜ao do m´etodo heur´ıstico proposto

para o problema de roteamento de ve´ıculos com coleta e entrega e janelas de tempo, ba-

seado em uma Busca Local Iterada (Iterated Local Search - ILS) conjugado a um M´etodo

Randˆomico de Descida (MRD). Tamb´em s˜ao apresentados os resultados computacionais

obtidos e compara¸c˜oes com outros m´etodos da literatura.

Muitas vezes, com uma boa heur´ıstica construtiva e busca local, o ´otimo local obtido ´e

suﬁcientemente bom. No entanto, em otimiza¸c˜ao combinat´oria, pode-se encontrar solu¸c˜oes

ainda distantes de um ´otimo global. Neste contexto ´e incentivado o uso de heur´ısticas que

gerem muitos ´otimos locais, como ´e o caso das metaheur´ısticas. Dentre elas podemos citar

a Busca Local Iterada (do inglˆes, Iterated Local Search - ILS), Busca Tabu (do inglˆes,

Tabu Search - TS), Simulated Annealing, VNS, etc.

Nesse trabalho foi escolhido o m´etodo de busca ILS e sua maior vantagem consiste na

sua facilidade de implementa¸c˜ao. Mas muitas vezes, a sua vers˜ao original n˜ao consegue

solu¸c˜oes suﬁcientemente boas num tempo razo´avel, o que leva `a utiliza¸c˜ao de variantes

mais soﬁsticados.

O ILS, proposto por St

utzle e Hoos (1999), ´e um m´etodo de busca local que procura

focar a busca n˜ao no espa¸co completo de solu¸c˜oes, mas num subespa¸co contendo solu¸c˜oes

3.1 Metaheuristica 19

que representam ´otimos locais. De acordo com Louren¸co, Martin e St

utzle (2003), o

sucesso do ILS ´e centrado no conjunto de amostragem de ´otimos locais, juntamente com

a escolha da busca local, das perturba¸c˜oes e do crit´erio de aceita¸c˜ao.

Juntamente com a busca local do ILS ser´a utilizado o MRD (M´etodo Randˆomico

de Descida) que ´e uma heur´ıstica de reﬁnamento que consiste em analisar um vizinho

qualquer e o aceitar somente se ele for estritamente melhor que a solu¸c˜ao corrente. Caso

esse vizinho n˜ao seja melhor, a solu¸c˜ao corrente permanece inalterada e outro vizinho

´e gerado. O m´etodo ´e ﬁnalizado quando se atinge um n´umero m´aximo de itera¸c˜oes

(maxIter) sem que haja a produ¸c˜ao de melhorias na solu¸c˜ao corrente. O algoritmo da

Figura 2 explica o funcionamento do ILS-MRD.

Sa´ıda: Uma solu¸c˜ao S

← solucaoInicial1



← MRD(s

, maxIter)2

kp ← 03

iter ← 04

enquanto kp < kp

max

fa¸ca5

iter ← melhorIter6

enquanto iter < iter

max

fa¸ca7

iter ← iter + 18



← perturbacao(s



, historico)9



← MRD(s



, maxIter)10

se (s



< s



) ent˜ao11



← s



melhorIter ← iter13

kp ← 014

kp ← kp + delta15

retorna s



Figura 2: Algoritmo ILS-MRD

O algoritmo MRD ´e descrito na Figura 3 onde recebe como entrada a quantidade

m´axima de itera¸c˜oes e a solu¸c˜ao corrente. Na linha 1 inicia-se a contagem das itera¸c˜oes,

3.1 Metaheuristica 20

enquanto n˜ao atingir o m´aximo de itera¸c˜oes (linha 2), incrementa-se o contador (linha 3)

e gera-se uma nova solu¸c˜ao atrav´es da escolha aleat´oria de um vizinho (linha 4). Caso

encontre melhora ent˜ao a solu¸c˜ao corrente passa a ser a melhor (linha 5), zerando o

contador (linha 6) e o loop ´e retomado.

Input: S,maxIter

Sa´ıda: Uma solu¸c˜ao S

iter ← 01

enquanto iter < maxIter fa¸ca2

iter ← iter + 13

Gere aleatoriamente um vizinho S



∈ N(S)4

se f(S



) < f(S) ent˜ao5

S ← S



iter ← 07

retorna S8

Figura 3: Algoritmo MRD

A Figura 4 representa o objetivo da perturba¸c˜ao que ´e tentar escapar de um ´otimo

local, S

∗

, a seguir obt´em-se S



perturbando S

∗

. A partir de S



efetua-se uma busca local

ao seu redor obtendo S

∗



, que pode ser melhor que a solu¸c˜ao anterior.

Figura 4: Perturba¸c˜ao - ILS

Na literatura h´a v´arias propostas para se calcular a fun¸c˜ao objetivo no VRPPDTW.

Mas basicamente obedecem as seguintes ordens:

3.2 Solu¸c˜ao Inicial 21

1. minimizar o n´umero de ve´ıculos, logo o n´umero de rotas, uma vez que h´a um ve´ıculo

por rota.

2. minimizar o custo total das viagens.

3. minimizar o tempo total de cada rota.

4. minimizar o tempo de espera.

Li e Lim (2001), Tam e Tseng (2003), Dumitrescu et al. (2008), por exemplo, adap-

taram seus algoritmos para obedecerem a essa ordem. No entanto, Pankratz (2005) tinha

como ´unico objetivo minimizar o custo da rota, ignorando assim a quantidade de ve´ıculos.

Neste trabalho, o objetivo do problema VRPPDTW foi usado a seq

uˆencia de prioridades

descrita inicialmente nesta se¸c˜ao.

Neste trabalho os pares de atividades associados aos cliente (coleta e entrega), ser˜ao

denotados apenas de “par”. Deste modo, o princ´ıpio b´asico dos algoritmos descritos nesta

se¸c˜ao ´e dado por: pega-se aleatoriamente um par, que n˜ao esteja em nenhuma rota, o qual

ir´a forma uma rota trivial “dep´osito-entrega-coleta-dep´osito” ({v

, v

} ∴ i ∈ P, j ∈

D) e vai-se inserindo outros pares, ainda n˜ao inseridos na rota atual at´e chegar ao ponto

que n˜ao possa mais ser colocado nenhum elemento sem que este viole as restri¸c˜oes. Ent˜ao

se cria uma nova rota e tenta-se fazer o mesmo processo acima, at´e que n˜ao haja mais

pares, sem rota, para serem colocados.

A inser¸c˜ao de um novo par `a rota ´e feita analisando todas as poss´ıveis posi¸c˜oes para

um par ser encaixado entre os v´ertices da rota e escolhendo a melhor das posi¸c˜oes a qual

obedece a ordem relatada anteriormente.

Partindo do princ´ıpio b´asico (descrino em 3.2) esse algoritmo ´e um algoritmo n˜ao-

determin´ıstico de Vizinhan¸ca mais Pr´oxima. O C1 para o VRPPDTW ´e descrito no

pseudo-algoritmo da Figura 5. O seu objetivo ´e construir uma solu¸c˜ao que consiste de

v´arias rotas onde cada uma dela ´e constru´ıda iterativamente escolhendo-se os vizinhos

mais pr´oximos para form´a-la.

3.2 Solu¸c˜ao Inicial 22

Primeiramente, pega-se a lista de v´ertices de coleta ou entrega, nesse caso ser˜ao os de

coleta (linha 1), pois sempre ser˜ao colocados em pares na rota (linha 7). Depois, inicia-se

um la¸co para garantir que todos os v´ertices ser˜ao inseridos. Cria-se uma rota (linha 3)

e tenta-se inserir a maior quantidade de elementos que esta ela suportar (linha 7), ou

seja, inserir todos os elementos que n˜ao violem nenhuma restri¸c˜ao. A escolha do primeiro

elemento da rota ´e feita de forma aleat´oria (linha 4), o que torna esse algoritmo n˜ao-

determin´ıstico, no entanto, os demais s˜ao escolhidos baseados num crit´erio de distˆancia,

onde ser˜ao o pr´oximo elemento escolhido ser´a sempre o vizinho mais pr´oximo v´alido (linha

10). Na linha 6 tem-se um la¸co para percorrer todos os poss´ıveis candidatos sem rota.

Caso a inser¸c˜ao seja bem sucedida ent˜ao esse o v´ertice ´e removido da lista de candidatos

(linha 9). A linha 10 refere-se `a procura do vizinho mais pr´oximo ao atual inserido e

que ainda n˜ao foi descartado (linha 8). Finalmente n˜ao conseguindo inserir mais nenhum

elemento nessa rota, a mesma ´e adicionada a solu¸c˜ao (linha 12) e cria-se outra nova rota

vazia para ser preenchida at´e que n˜ao haja mais pares a serem inseridos (linha 2).

Sa´ıda: Uma solu¸c˜ao S

vect ← pickups1

enquanto vect tiver elementos fa¸ca2

cria-se uma nova rota: route3

id ← elemento aleat´orio de vect4

i ← 05

enquanto i < quantidades de elementos atuais de vect fa¸ca6

sucess ← insere id e id + n a route7

se sucess ent˜ao8

remove id de vect9

id ← escolhe um novo vizinho ainda n˜ao escolhido10

i ← i + 111

Adiciona route a solu¸c˜ao parcial S12

retorna S13

Figura 5: Vizinhan¸ca mais pr´oxima - C1

O principal objetivo deste algoritmo n˜ao ´e criar rotas v´alidas. Como este trabalho

prop˜oe um ILS o qual tem uma fase de perturba¸c˜ao. Este algoritmo obriga a ter uma

busca local de valida¸c˜ao da solu¸c˜ao como sendo o primeiro passo da busca local.

Esse algoritmo nem sempre cria rotas v´alidas, pois depende da folga que ´e acrescentada

a cada janela de tempo, proporcionando assim rotas com maiores quantidade de pares,

3.3 Estrutura de Vizinhan¸cas 23

por´em rotas possivelmente violadas.

Sua estrutura ´e semelhante ao C1, com uma diferen¸ca que na linha 7 deve ser acres-

centado uma folga. A folga refere-se ao acr´escimo que ´e dado no ﬁnal de cada janela

de tempo possibilitando momentaneamente que um v´ertice que antes era violado ﬁque

v´alido. O valor da folga n˜ao ´e ﬁxo, deste modo, de ver pensado um valor que n˜ao seja

irrelevante e que tamb´em n˜ao seja exagerado, perturbando demais a solu¸c˜ao.

H´a v´arias formas de se fazer a busca de vizinhan¸cas (N(S)) a ﬁm de encontrar uma

melhor solu¸c˜ao. As opera¸c˜oes N(S) s˜ao: PD-Shift, PD-Exchange, PD-Rearrange (LI;

LIM, 2001), PD-Eliminate e Viabiliza Rota. As duas primeiras opera¸c˜oes tem o objetivo

de tenta fugir de ´otimos locais ainda distantes de um ´otimo global, a terceira ´e usada

como uma p´os-otimiza¸c˜ao, para melhorar o arranjo dos elementos que comp˜oes a rota. A

quarta ´e tentar reduzir a quantidade de rotas da solu¸c˜ao e a ´ultima tem o objetivo de

tentar de forma mais r´apida diminuir a quantidade de rotas totais da solu¸c˜ao.

As opera¸c˜oes PD-Shift, PD-Exchange e PD-Rearrange descrita em Li e Lim (2001)

e implementadas neste trabalho tem o seguinte aspecto: sempre haver´a duas maneiras

para escolher a vizinhan¸ca a ser modiﬁcada. Ou de forma aleat´oria ou na escolha de um

elemento da lista de vizinhos. Possivelmente em v´arias itera¸c˜oes a escolha do vizinho seria

repetitiva, diminuindo assim a eﬁciˆencia da busca, e para evitar isso usam-se 2 m´etodos

trabalhados ao mesmo tempo. O primeiro ´e que a escolha do vizinho ´e a partir de uma

busca aleat´oria de vizinhos e a outra ´e criando uma estrutura de mem´oria para evitar

movimentos c´ıclicos.

Esta opera¸c˜ao consiste em pegar um par de uma rota e transferir este para outra e

vice-versa. Essa opera¸c˜ao ´e denotada por N

P DS

(S). Para cada par de rotas selecionadas,

no exemplo da Figura 6, temos as rotas: Rota 1 e Rota 2. A opera¸c˜ao ser´a a remo¸c˜ao

primeiramente de um par da Rota 1 e a inser¸c˜ao deste na Rota 2, e o contr´ario.

A Figura 6 mostra somente o envio do par P e D retirado da Rota 1 e sendo colocado

na Rota 2, ou seja, somente metade do algoritmo. A posi¸c˜ao escolhida para ser colocado

esse novo par ´e exatamente como descrito na Se¸c˜ao 3.2.

3.3 Estrutura de Vizinhan¸cas 24

Figura 6: Opera¸c˜ao PD-Shift

Nesta opera¸c˜ao a troca ´e simultˆanea de pares entre duas rotas, sujeitos a todas as

restri¸c˜oes impostas pelo VRPPDTW. A opera¸c˜ao ´e denotada por N

P DE

(S). Na Figura

7, os clientes P1 e D1 est˜ao inicialmente na Rota 1, enquanto os clientes P2 e D2 est˜ao

na Rota 2. A opera¸c˜ao PD-Exchange remove dois pares, um de cada rota, depois tenta-se

inserir o par P1-D1 na Rota 2 na melhor posi¸c˜ao vi´avel, enquanto o par P2-D2 ´e inserido

na rota Rota 1.

Figura 7: Opera¸c˜ao PD-Exchange

A opera¸c˜ao PD-Rearrange consiste em rearranjar uma determinada rota. Este pro-

cesso ter´a a seguinte nomenclatura: N

P DR

(S). A Figura 8 ilustra a opera¸c˜ao onde um par

da rota ´e removido e depois inserido na mesma rota por´em tenta-se a melhor posi¸c˜ao para

este.

E bastante r´apido e com bons resultados. Sempre que ocorrer v´arias perturba¸c˜oes

3.3 Estrutura de Vizinhan¸cas 25

na solu¸c˜ao inicial esta opera¸c˜ao deve ser aplicada.

Figura 8: Opera¸c˜ao PD-Rearrange

Esta opera¸c˜ao ´e muito semelhante `a opera¸c˜ao PD-Shift e a chamaremos de N

P DX

(S).

Para isso escolhe-se uma rota e tenta-se retirar os pares de uma delas e colocar nas outras

rotas. A rota a qual cada par vai ser realocado ´e analisado de acordo com as rotas mais

pr´oximas deste par. Caso a primeira mais pr´oxima n˜ao suporte o par, ent˜ao tenta-se

na segunda mais pr´oxima e assim por diante. No entanto a proximidade ´e relativa, pois

analisando a rota mais pr´oxima do par-coleta teremos uma rota e analisando o par-entrega

pode ter outra rota. Assim caso as a rota mais pr´oxima do dois seja a mesma, com certeza

est´a ser´a a escolhida, caso contr´ario, escolhe-se a rota mais com menor distˆancia do par.

Como nem sempre s˜ao criadas rotas v´alidas, pois h´a tanto o algoritmo (Se¸c˜ao 3.2.2)

quanto a fase de perturba¸c˜ao (veja 3.4) podem gerar rotas violadas. Fez-se necess´ario a

cria¸c˜ao desse processo de viabilizar as rotas. O algoritmo C2 (Se¸c˜ao 3.2.2), por exemplo,

na maioria das vezes cria rotas inv´alidas. Para tornar v´alida uma rota procede-se de duas

formas: a primeira tenta-se retirar elementos desta rota e colocar em outras existentes at´e

que se torne v´alida, ou seja, remove-se um par da rota violada e tenta-se introduzi-lo em

outra rota, o processo p´ara quando todas as rotas estiverem v´alidas. Caso na inser¸c˜ao a

inicial se torne v´alida e a rota que ganhou o par se torne violada a inser¸c˜ao ´e desfeita e

procura-se outra rota para esse par. Caso n˜ao se ache nenhuma rota em que ele se encaixe,

escolhe-se outro par e o ciclo ´e reiniciado.

A outra forma, corresponde a criar uma nova rota. Esta ser´a realizada somente caso

n˜ao se consiga solu¸c˜ao v´alida na primeira etapa. Pois acrescentar uma nova rota ´e um

passo contra a fun¸c˜ao objetivo que tenta diminuir quantidade de ve´ıculos utilizados.

3.4 Perturba¸c˜ao 26

A ﬁm de fugir de ´otimos locais, a perturba¸c˜ao tenta encontrar novas solu¸c˜oes que

n˜ao seriam poss´ıveis somente com a busca local. A perturba¸c˜ao da solu¸c˜ao n˜ao pode ser

muito fraca de forma que volte rapidamente a solu¸c˜ao corrente. Nem muito grande o que

provavelmente causar´a uma grande perda em rela¸c˜ao a quanlidade de solu¸c˜oes corrente.

Tento todas as rotas j´a formadas de uma solu¸c˜ao S a perturba¸c˜ao ocorre quando deixa-

se de validar algumas restri¸c˜oes como por exemplo as janelas de tempo, a capacidade

do ve´ıculo, etc. Assim, a perturba¸c˜ao utilizada nesse trabalho foi a retirada de alguns

pares de uma rota e inseri-los em outra ignorando algumas restri¸c˜oes. Neste trabalho as

restri¸c˜oes violadas foram as das janelas de tempo. Tendo em conta o equil´ıbrio, a remo¸c˜ao

e inser¸c˜ao de um par n˜ao ´e feita de forma aleat´oria, e sim ap´os um varredura na rota e

em sua vizinhan¸ca para descobrir qual seria o melhor par a ser retirado e tamb´em qual a

melhor rota que este se encaixaria.

Geralmente a perturba¸c˜ao gera rotas violadas o que torna obrigat´oria uma busca local

para poder validar a rota. Na se¸c˜ao 3.3.5 foi descrito como esse processo de valida¸c˜ao ´e

realizado.

Os testes foram realizados numa m´aquina com o Sistema Operacional Windows Vista,

core 2 due E7300, 2,66GHz e 4Gb de mem´oria RAM. Algoritmos codiﬁcados em C++

com Standard Template Library. As instˆancias foram baseadas em Solomon (1987).

As instˆancias podem ser encontradas em

<http://www.sintef.no/static/am/opti/projects/top/vrp/benchmarks.html>,

onde tamb´em est˜ao os melhores resultados encontrados na literatura. Para resolver

tais instˆancias este trabalho utilizou as seguintes constantes para o ISL-MRD: maxInter =

100; kpmax = 10; delta = 2;. Com rela¸c˜ao aos m´etodos de solu¸c˜ao inicial foi testado C1 e

C2 com uma folga de 100, 500e1000. Foram rodadas 116 instˆancias com aproximadamente

100 e 200 clientes.

As Tabelas apresentam os seguintes valores: na primeira coluna tem-se o nome da

instˆancia, na segunda a quantidade de ve´ıculos (V). T representa o tempo (custo) total

de viagem, na seguinte, relativos a literatura. Estes tem siglas que referem-se a: Li & Lim

3.5 Resultados computacionais 27

Instˆancia Melhor Resultado ILS-MRD

V T Pub V T Tempo (s)

lc101 10 828,94 Li & Lim 10 828,94 0,50

lc102 10 828,94 Li & Lim 10 828,94 0,44

lc103 9 1.035,35 BVH 10 827,87 0,47

lc104 9 860,01 SAM::OPT 9 876,93 2,98

lc105 10 828,94 Li & Lim 10 828,94 0,48

lc106 10 828,94 Li & Lim 10 828,94 0,48

lc107 10 828,94 Li & Lim 10 828,94 0,53

lc108 10 826,44 Li & Lim 10 826,44 0,62

lc109 9 1.000,60 BVH 10 827,82 1,64

lc201 3 591,56 Li & Lim 3 591,56 1,29

lc202 3 591,56 Li & Lim 3 591,56 1,98

lc203 3 585,56 Li & Lim 3 591,17 3,58

lc204 3 590,60 SAM::OPT 3 596,76 4,49

lc205 3 588,88 Li & Lim 3 588,88 1,76

lc206 3 588,49 Li & Lim 3 588,49 2,95

lc207 3 588,29 Li & Lim 3 588,29 4,74

lc208 3 588,32 Li & Lim 3 588,32 2,92

Tabela 1: Resultados das Instˆancias de 100 pares - LC

Li e Lim (2001); BVH - Bent e Hentenryck (2006); RP - Ropke e Pisinger (2006a); TS -

TetraSoft (2003); SAM::OPT - Mathematics (Em processo). Depois o V, T e o Tempo de

CPU em segundos encontrados no ILS-MRD. Os resultados apresentados foram realizados

a seguir s˜ao apenas de C1, pois C2 se mostrou pior que C1.

Os testes mostraram que o ILS-MRD consegue boas solu¸c˜oes em tempos razo´aveis.

Para as instˆancias de 100 clientes, representadas nas Tabelas 1, 2 e 3, das 56 conseguiu-se

encontrar o melhor valor da literatura em 35 dos 56 casos. N˜ao foi calculado GAP pois os

valores seriam duvidosos uma vez que o objetivo ´e diminuir a quantidade de rota assim

existem instˆancias com maior quantidade de rotas e custo menor. O tempo m´edio dessas

instˆancias foram de 3,55s. Para as instˆancias de 200 clientes, conseguiu-se chegar aos

valores da literatura em 26 dos 60 casos. Os tempos foram um pouco maiores comparados

aos anteriores com m´edia de 20,82s.

3.5 Resultados computacionais 28

Instˆancia Melhor Resultado ILS-MRD

V T Pub V T Tempo (s)

lr101 19 1.650,80 Li & Lim 19 1.650,80 0,22

lr102 17 1.487,57 Li & Lim 17 1.487,57 0,22

lr103 13 1.292,68 Li & Lim 13 1.292,68 0,20

lr104 9 1.013,39 Li & Lim 9 1.013,39 0,28

lr105 14 1.377,11 Li & Lim 14 1.377,11 0,33

lr106 12 1.252,62 Li & Lim 12 1.252,62 0,36

lr107 10 1.111,31 Li & Lim 10 1.111,31 3,28

lr108 9 968,97 Li & Lim 9 968,97 0,50

lr109 11 1.208,96 SAM::OPT 11 1.239,96 3,33

lr110 10 1.159,35 Li & Lim 11 1.165,83 2,39

lr111 10 1.108,90 Li & Lim 10 1.108,90 0,42

lr112 9 1.003,77 Li & Lim 9 1.003,77 0,47

lr201 4 1.253,23 SAM::OPT 4 1.256,72 4,69

lr202 3 1.197,67 Li & Lim 3 1.197,67 2,45

lr203 3 949,40 Li & Lim 3 949,40 6,24

lr204 2 849,05 Li & Lim 2 849,05 9,84

lr205 3 1.054,02 Li & Lim 3 1.054,02 1,79

lr206 3 931,63 Li & Lim 3 931,63 2,98

lr207 2 903,06 Li & Lim 2 903,06 13,31

lr208 2 734,85 Li & Lim 2 736,00 17,74

lr209 3 930,59 SAM::OPT 3 937,05 8,51

lr210 3 964,22 Li & Lim 3 964,22 6,00

lr211 2 911,52 SAM::OPT 3 896,76 5,94

Tabela 2: Resultados das Instˆancias de 100 pares - LR

Instˆancia Melhor Resultado ILS-MRD

V T Pub V T Tempo (s)

lrc101 14 1.708,80 Li & Lim 14 1.708,80 0,25

lrc102 12 1.558,07 SAM::OPT 12 1.558,07 4,23

lrc103 11 1.258,74 Li & Lim 11 1.258,74 0,33

lrc104 10 1.128,40 Li & Lim 10 1.129,95 1,47

lrc105 13 1.637,62 Li & Lim 13 1.643,88 7,33

lrc106 11 1.424,73 SAM::OPT 11 1.424,73 4,30

lrc107 11 1.230,15 Li & Lim 11 1.230,14 5,31

lrc108 10 1.147,43 SAM::OPT 10 1.152,87 3,39

lrc201 4 1.406,94 SAM::OPT 4 1.439,67 6,00

lrc202 3 1.374,27 Li & Lim 4 1.385,25 6,45

lrc203 3 1.089,07 Li & Lim 3 1.089,07 6,89

lrc204 3 818,66 SAM::OPT 3 820,66 10,55

lrc205 4 1.302,20 Li & Lim 4 1.305,91 0,78

lrc206 3 1.159,03 SAM::OPT 3 1.164,35 5,42

lrc207 3 1.062,05 SAM::OPT 3 1.064,40 9,58

lrc208 3 852,76 Li & Lim 3 861,31 3,00

Tabela 3: Resultados das Instˆancias de 100 pares - LRC

3.5 Resultados computacionais 29

Instˆancia Melhor Resultado ILS-MRD

V T Pub V T Tempo (s)

LC1 2 1 20 2.704,57 Li & Lim 20 2.704,57 0,95

LC1 2 2 19 2.764,56 Li & Lim 19 2.764,56 0,53

LC1 2 3 17 3.128,61 RP 18 2.773,91 10,76

LC1 2 4 17 2.693,41 BVH 18 2.673,57 10,90

LC1 2 5 20 2.702,05 Li & Lim 20 2.702,50 0,78

LC1 2 6 20 2.701,04 Li & Lim 20 2.701,04 0,90

LC1 2 7 20 2.701,04 Li & Lim 20 2.701,04 0,94

LC1 2 8 20 2.689,83 Li & Lim 20 2.689,83 0,73

LC1 2 9 18 2.724,24 Li & Lim 18 2.724,24 0,87

LC1 2 10 17 2.943,49 RP 18 2.741,56 0,69

LC2 2 1 6 1.931,44 Li & Lim 6 1.931,44 2,42

LC2 2 2 6 1.881,40 Li & Lim 6 1.881,40 3,96

LC2 2 3 6 1.844,33 SAM::OPT 6 1.844,33 4,46

LC2 2 4 6 1.767,12 Li & Lim 6 1.778,54 10,50

LC2 2 5 6 1.891,21 Li & Lim 6 1.891,21 1,73

LC2 2 6 6 1.857,78 SAM::OPT 6 1.858,25 3,67

LC2 2 7 6 1.850,13 SAM::OPT 6 1.850,13 3,34

LC2 2 8 6 1.824,34 Li & Lim 6 1.824,34 2,46

LC2 2 9 6 1.854,21 SAM::OPT 6 1.854,21 6,15

LC2 2 10 6 1.817,45 Li & Lim 6 1.817,45 3,73

Tabela 4: Resultados das Instˆancias de 200 pares - LC

Instˆancia Melhor Resultado ILS-MRD

V T Pub V T Tempo (s)

LR1 2 1 20 4.819,12 Li & Lim 20 4.819,12 4,49

LR1 2 2 17 4.621,21 RP 19 4.205,50 5,21

LR1 2 3 15 3.612,64 TS 15 3.657,19 29,73

LR1 2 4 10 3.037,38 RP 10 3.089,86 11,89

LR1 2 5 16 4.760,18 BVH 16 4.760,18 5,23

LR1 2 6 14 4.175,16 BVH 14 4.201,82 5,96

LR1 2 7 12 3.550,61 RP 12 3.851,36 7,78

LR1 2 8 9 2.784,53 RP 9 2.828,09 25,85

LR1 2 9 14 4.354,66 RP 14 4.411,54 11,45

LR1 2 10 11 3.714,16 RP 11 3.744,95 9,16

LR2 2 1 5 4.073,10 SAM::OPT 5 4.073,10 16,88

LR2 2 2 4 3.796,00 SAM::OPT 4 3.796,00 7,85

LR2 2 3 4 3.098,36 RP 4 3.098,36 98,97

LR2 2 4 3 2.486,14 RP 3 2.737,22 78,41

LR2 2 5 4 3.438,39 SAM::OPT 4 3.438,39 80,61

LR2 2 6 4 3.201,54 Li & Lim 4 3.208,53 14,74

LR2 2 7 3 3.135,05 RP 3 3.337,28 67,11

LR2 2 8 2 2.555,40 RP 3 2.736,35 107,60

LR2 2 9 3 3.930,49 RP 4 3.198,44 49,66

LR2 2 10 3 3.323,37 SAM::OPT 3 3.478,67 26,47

Tabela 5: Resultados das Instˆancias de 200 pares - LR

3.5 Resultados computacionais 30

Instˆancia Melhor Resultado ILS-MRD

V T Pub V T Tempo (s)

LRC1 2 1 19 3.606,06 SAM::OPT 19 3.606,06 4,52

LRC1 2 2 15 3.673,19 BVH 16 3.681,36 16,44

LRC1 2 3 13 3.161,75 BVH 13 3.251,38 11,78

LRC1 2 4 10 2.631,82 RP 10 2.655,27 16,60

LRC1 2 5 16 3.715,81 BVH 16 3.715,81 15,24

LRC1 2 6 17 3.368,66 SAM::OPT 17 3.368,66 14,96

LRC1 2 7 14 3.668,39 RP 15 3.417,16 25,54

LRC1 2 8 13 3.226,72 RP 14 3.087,62 10,55

LRC1 2 9 13 3.174,55 RP 13 3.226,72 36,79

LRC1 2 10 12 2.951,29 RP 13 2.833,85 48,34

LRC2 2 1 6 3.605,40 RP 6 3.690,10 12,90

LRC2 2 2 5 3.327,18 RP 6 2.666,01 12,15

LRC2 2 3 4 2.938,28 RP 4 3.249,36 53,70

LRC2 2 4 3 2.887,97 RP 4 2.795,70 42,26

LRC2 2 5 5 2.776,93 BVH 5 2.776,93 32,56

LRC2 2 6 5 2.707,96 SAM::OPT 5 2.707,96 22,26

LRC2 2 7 4 3.050,03 BVH 5 2.816,41 25,76

LRC2 2 8 4 2.399,95 RP 4 3.050,03 46,36

LRC2 2 9 4 2.208,49 RP 4 2.750,30 37,61

LRC2 2 10 3 2.550,56 RP 3 2.699,55 27,32

Tabela 6: Resultados das Instˆancias de 200 pares - LRC

3.5 Resultados computacionais 31

Tabela 7: Resultados das Instˆancias de 100 pares - LC

Li01 Pankratz05 Bent06 Derigs06 Ropke06 ILS-MRD

V T V T V T V T V T V T

1 10 828,94 10 828,94 10 828,94 10 828,94 10 828,94 10 828,94

2 10 828,94 10 828,94 10 828,94 10 828,94 10 828,94 10 828,94

3 10 827,86 10 827,86 9 1.035,35 10 827,86 9 1.035,35 10 827,87

4 9 861,95 10 818,60 9 860,01 9 860,01 9 860,01 9 876,93

5 10 828,94 10 828,94 10 828,94 10 828,94 10 828,94 10 828,94

6 10 828,94 10 828,94 10 828,94 10 828,94 10 828,94 10 828,94

7 10 828,94 10 828,94 10 828,94 10 828,94 10 828,94 10 828,94

8 10 826,44 10 826,44 10 826,44 10 826,44 10 826,44 10 826,44

9 10 827,82 10 827,82 9 1.000,60 10 827,82 9 1.000,60 10 827,82

1 3 591,56 3 591,56 3 591,56 3 591,56 3 591,56 3 591,56

2 3 591,56 3 591,56 3 591,56 3 591,56 3 591,56 3 591,56

3 3 585,56 3 591,17 3 591,17 3 591,17 3 591,17 3 591,17

4 3 591,17 3 590,60 3 590,60 3 590,60 3 590,60 3 596,76

5 3 588,88 3 588,88 3 588,88 3 588,88 3 588,88 3 588,88

6 3 588,49 3 588,49 3 588,49 3 588,49 3 588,49 3 588,49

7 3 588,29 3 588,29 3 588,29 3 588,29 3 588,29 3 588,29

8 3 588,32 3 588,32 3 588,32 3 588,32 3 588,32 3 588,32

3.5 Resultados computacionais 32

Tabela 8: Resultados das Instˆancias de 100 pares - LR

Li01 Pankratz05 Bent06 Derigs06 Ropke06 ILS-MRD

V T V T V T V T V T V T

1 19 1.650,78 19 1.650,80 19 1.650,80 19 1.650,80 19 1.650,80 19 1.650,80

2 17 1.487,57 17 1.487,57 17 1.487,57 17 1.487,57 17 1.487,57 17 1.487,57

3 13 1.292,68 13 1.292,68 13 1.292,68 13 1.292,68 13 1.292,68 13 1.292,68

4 9 1.013,39 9 1.013,99 9 1.013,39 9 1.013,99 9 1.013,39 9 1.013,39

5 14 1.377,11 14 1.377,11 14 1.377,11 14 1.377,11 14 1.377,11 14 1.377,11

6 12 1.252,62 12 1.252,62 12 1.252,62 12 1.252,62 12 1.252,62 12 1.252,62

7 10 1.111,31 10 1.111,31 10 1.111,31 10 1.111,31 10 1.111,31 10 1.111,31

8 9 968,97 9 968,97 9 968,97 9 968,97 9 968,97 9 968,97

9 11 1.239,96 11 1.208,96 11 1.208,96 11 1.208,96 11 1.208,96 11 1.239,96

10 10 1.159,35 11 1.165,83 10 1.159,35 10 1.159,35 10 1.159,35 11 1.165,83

11 10 1.108,90 10 1.108,90 10 1.108,90 10 1.108,90 10 1.108,90 10 1.108,90

12 9 1.003,77 9 1.003,77 9 1.003,77 9 1.003,77 9 1.003,77 9 1.003,77

1 4 1.263,84 4 1.253,23 4 1.253,23 4 1.253,23 4 1.253,23 4 1.256,72

2 3 1.197,67 3 1.197,67 3 1.197,67 3 1.197,67 3 1.197,67 3 1.197,67

3 3 949,40 3 952,29 3 949,40 3 949,40 3 949,40 3 949,40

4 2 849,05 2 849,05 2 849,05 2 849,05 2 849,05 2 849,05

5 3 1.054,02 3 1.054,02 3 1.054,02 3 1.054,02 3 1.054,02 3 1.054,02

6 3 931,63 3 931,63 3 931,63 3 931,63 3 931,63 3 931,63

7 2 903,06 2 903,60 2 903,06 2 903,06 2 903,06 2 903,06

8 2 734,85 2 736,00 2 734,85 2 734,85 2 734,85 2 736,00

9 3 937,05 3 932,43 3 930,59 3 930,59 3 930,59 3 937,05

10 3 964,22 3 964,22 3 964,22 3 964,22 3 964,22 3 964,22

11 2 927,80 3 888,15 2 913,84 3 896,76 2 911,52 3 896,76

3.5 Resultados computacionais 33

Tabela 9: Resultados das Instˆancias de 100 pares - LRC

Li01 Pankratz05 Bent06 Derigs06 Ropke06 ILS-MRD

V T V T V T V T V T V T

1 14 1.708,80 15 1.703,21 14 1.708,80 14 1.708,80 14 1.708,80 14 1.708,80

2 13 1.563,55 12 1.558,07 12 1.558,07 12 1.558,07 12 1.558,07 12 1.558,07

3 11 1.258,74 11 1.258,74 11 1.258,74 11 1.258,74 11 1.258,74 11 1.258,74

4 10 1.128,40 10 1.128,40 10 1.128,40 10 1.128,40 10 1.128,40 10 1.129,95

5 13 1.637,62 13 1.637,62 13 1.637,62 13 1.637,62 13 1.637,62 13 1.643,88

6 11 1.425,53 11 1.424,73 11 1.424,73 11 1.424,73 11 1.424,73 11 1.424,73

7 11 1.230,14 11 1.230,14 11 1.230,14 11 1.230,14 11 1.230,14 11 1.230,14

8 10 1.147,97 10 1.147,43 10 1.147,43 10 1.147,96 10 1.147,43 10 1.152,87

1 4 1.468,96 4 1.407,21 4 1.406,94 4 1.406,94 4 1.406,94 4 1.439,67

2 3 1.374,27 4 1.385,25 3 1.374,27 3 1.374,27 3 1.374,27 4 1.385,25

3 3 1.089,07 4 1.093,89 3 1.089,07 3 1.089,07 3 1.089,07 3 1.089,07

4 3 827,78 3 818,66 3 818,66 3 818,66 3 818,66 3 820,66

5 4 1.302,20 4 1.302,20 4 1.302,20 4 1.302,20 4 1.302,20 4 1.305,91

6 3 1.162,91 3 1.159,03 3 1.159,03 3 1.159,03 3 1.159,03 3 1.164,35

7 3 1.424,60 3 1.062,05 3 1.062,05 3 1.062,05 3 1.062,05 3 1.064,40

8 3 852,76 3 852,76 3 852,76 3 865,51 3 852,76 3 861,31

3.5 Resultados computacionais 34

Tabela 10: Resultados das Instˆancias de 200 pares - LC

Bent06 Ropke06 ILS-MRD

V T V T V T

1 20 2.704,57 20 2.704,57 20 2.704,57

2 19 2.764,56 19 2.764,56 19 2.764,56

3 17 3.134,08 17 3.128,61 18 2.773,91

4 17 2.693,41 17 2.693,41 18 2.673,57

5 20 2.702,05 20 2.702,05 20 2.702,05

6 20 2.701,04 20 2.701,04 20 2.701,04

7 20 2.701,04 20 2.701,04 20 2.701,04

8 20 2.689,83 20 2.689,83 20 2.689,83

9 18 2.724,24 18 2.724,24 18 2.724,24

10 17 2.741,56 17 2.943,49 17 2.943,49

1 6 1.931,44 6 1.931,44 6 1.931,44

2 6 1.881,40 6 1.881,40 6 1.881,40

3 6 1.844,33 6 1.844,33 6 1.844,33

4 6 1.778,54 6 1.767,12 6 1.778,54

5 6 1.891,21 6 1.891,21 6 1.891,21

6 6 1.857,78 6 1.857,78 6 1.858,25

7 6 1.850,13 6 1.850,13 6 1.850,13

8 6 1.824,34 6 1.824,34 6 1.824,34

9 6 1.854,21 6 1.854,21 6 1.854,21

10 6 1.817,45 6 1.817,45 6 1.817,45

Tabela 11: Resultados das Instˆancias de 200 pares - LR

Bent06 Ropke06 ILS-MRD

V T V T V T

1 20 4.819,12 20 4.819,12 20 4.819,12

2 17 4.666,09 17 4.621,21 19 4.205,50

3 15 3.657,19 15 3.612,64 15 3.657,19

4 10 3.146,06 10 3.037,38 10 3.089,89

5 16 4.760,18 16 4.760,18 16 4.760,18

6 14 4.178,24 14 4.178,24 14 4.201,82

7 12 3.851,36 12 3.550,61 12 3.851,36

8 9 2.784,53 9 2.784,53 9 2.828,09

9 14 4.411,54 14 4.354,66 14 4.411,54

10 11 3.744,95 11 3.714,16 11 3.744,95

1 5 4.073,10 5 4.073,10 5 4.073,10

2 4 3.796,00 4 3.796,00 4 3.796,00

3 4 3.100,38 4 3.098,36 4 3.098,36

4 3 2.956,15 3 2.486,14 3 2.737,22

5 4 3.438,39 4 3.438,39 4 3.438,39

6 4 3.208,53 4 3.201,54 4 3.208,53

7 3 3.337,28 3 3.135,05 3 3.337,28

8 3 2.407,66 2 2.555,40 3 2.736,35

9 4 3.198,44 3 3.930,49 4 3.198,44

10 3 3.478,67 3 3.344,08 3 3.478,67

3.5 Resultados computacionais 35

Tabela 12: Resultados das Instˆancias de 200 pares - LRC

Bent06 Ropke06 ILS-MRD

V T V T V T

1 19 3.606,06 19 3.606,06 19 3.606,06

2 16 3.681,36 15 3.674,80 16 3.681,36

3 13 3.161,75 13 3.178,17 13 3.251,38

4 10 2.655,27 10 2.631,82 10 2.655,27

5 16 3.715,81 16 3.715,81 16 3.715,81

6 17 3.368,66 17 3.368,66 17 3.368,66

7 15 3.417,16 14 3.668,39 15 3.417,16

8 14 3.087,62 13 3.174,55 14 3.087,62

9 14 3.129,65 13 3.226,72 13 3.226,72

10 13 2.833,85 12 2.951,29 13 2.833,85

1 6 3.690,10 6 3.605,40 6 3.690,10

2 6 2.666,01 5 3.327,18 6 2.666,01

3 5 2.523,59 4 2.938,28 4 3.249,36

4 4 2.795,70 3 2.887,97 4 2.795,70

5 5 2.776,93 5 2.776,93 5 2.776,93

6 5 2.707,96 5 2.707,96 5 2.707,96

7 4 3.056,09 4 3.056,09 5 2.816,41

8 4 3.050,03 4 2.399,95 4 3.050,03

9 4 2.750,30 4 2.208,49 4 2.750,30

10 3 2.699,55 3 2.550,56 3 2.699,55

O problema do caixeiro viajante ´e um dos mais cl´assicos problemas da ´area de otimi-

za¸c˜ao. Por´em esta variante com coleta e entrega vem sendo estudada h´a menos tempo

(veja Se¸c˜ao 2.4). Este cap´ıtulo pretende comparar diferentes formula¸c˜oes matem´aticas.

A formula¸c˜ao n˜ao-orientada (veja Se¸c˜ao 4.1), sobre as arestas do grafo, foi proposta ini-

cialmente por Ruland e Rodin (1997) e aprofundada por Dumitrescu et al. (2008). Neste

trabalho s˜ao propostas uma formula¸c˜ao orientada (veja Se¸c˜ao 4.2), sobre os arcos de um

grafo orientado, e tamb´em uma formula¸c˜ao estendida, sobre vari´aveis de arco e posi¸c˜ao.

Dumitrescu et al. (2008) ﬁzeram um estudo sobre a estrutura poliedral do TSPPD e

aplicaram as desigualdades encontradas em um algoritmo de branch-and-cut. Esse estudo

foi feito sobre a formula¸c˜ao n˜ao orientada proposta por Ruland e Rodin (1997) e que ser´a

apresentada a seguir.

Seja G = (V, E), um grafo completo n˜ao orientado, onde V ´e o conjunto de v´ertices e E

o conjunto de arestas. O conjunto V ´e constitu´ıdo pelos v´ertices de coleta e entrega, al´em

de dois v´ertices que correspondem ao dep´osito, a sa´ıda e chegada a ele. Um par de v´ertices

de coleta e entrega formam uma requisi¸c˜ao. A quantidade de requisi¸c˜oes ´e indicada por

n. Seja P = {1, . . . , n} o conjunto de v´ertices de coleta e D = {n + 1, . . . , 2n} o conjunto

dos v´ertices de entrega. O v´ertice de entrega correspondente ao v´ertice de coleta i ∈ P

´e i + n ∈ D. Desta forma, V = P ∪ D ∪ {0, 2n + 1}, onde 0 corresponde a partida do

dep´osito e 2n + 1 a volta a ele. Para dois v´ertices i e j, i < j, a aresta associada a esse par

´e denotada como (i, j). Um custo n˜ao-negativo c

i,j

´e associado com a aresta (i, j) ∈ E.

O TSPPD consiste em encontrar um caminho hamiltoniano sobre G que deve come¸car

em {0} e terminar em {2n + 1}, passando por uma coleta i antes de sua entrega i + n.

4.1 Formula¸c˜ao N˜ao Orientada 37

Juntando-se a esse caminho a aresta (0, 2n + 1), que n˜ao possui custo, temos um circuito

hamiltoniano sobre G.

Em adi¸c˜ao a esta nota¸c˜ao, deﬁne-se δ(S) = {(i, j) ∈ E : i ∈ S, j /∈ S ou i /∈ S, j ∈ S}

para todo conjunto S ⊆ V . Se S = {i}, escreve-se δ(i) em vez de δ({i}). O TSPPD foi

formulado primeiramente como programa¸c˜ao linear inteira por Ruland (1995), associando

a vari´avel bin´aria x

`a aresta (i, j) ∈ E. Usamos a nota¸c˜ao x(E



) para



(i,j)∈E



, onde



⊆ E:

Minimize:



(i,j)∈E

(4.1)

sujeito a:

0,2n+1

= 1 (4.2)

x(δ(i)) = 2 ∀i ∈ V (4.3)

x(δ(S)) ≥ 2 ∀S ⊆ V, 3 ≤ |S| ≤ |V |/2 (4.4)

x(δ(S)) ≥ 4 ∀S ∈ U (4.5)

∈ {0, 1} ∀(i, j) ∈ E (4.6)

onde U ´e uma cole¸c˜ao de subconjuntos de S ⊂ V que satisfaz S ⊆ V, 3 ≤ |S| ≤ |V |/2

com 0 ∈ S, 2n + 1 /∈ S e que exista i ∈ P tal que, i /∈ S e i + n ∈ S. O objetivo ´e

minimizar a soma dos custos das arestas na solu¸c˜ao, restri¸c˜ao (4.1). A aresta (0, 2n + 1)

tem seu valor ﬁxado em 1 como mostra a restri¸c˜ao (4.2). A restri¸c˜ao (4.3) obriga a todo

v´ertice a ter grau 2. A restri¸c˜ao (4.4) ´e a cl´assica restri¸c˜ao de elimina¸c˜ao de sub ciclos.

Finalmente, a restri¸c˜ao (4.5) obriga um v´ertice i a ser visitado antes do v´ertice i + n para

todo i ∈ P . Conforme ilustrado na Figura 9, qualquer solu¸c˜ao vi´avel para o TSPPD cruza

um conjunto S ∈ U pelo menos 4 vezes (em particular, a aresta (0, 2n + 1) sempre cruza

esses conjuntos). As restri¸c˜oes (4.5) podem ser separadas em tempo polinomial usando o

algoritmo do corte m´ınimo.

Para explicar uma das desigualdades v´alidas usadas como cortes por Dumitrescu et

al. (2008) apresentamos mais algumas nota¸c˜oes:

Para o conjunto de v´ertices S ⊆ V , π(S) refere-se ao conjunto dos v´ertices de coleta

de S, ou seja, π(S) = {i ∈ P : n + i ∈ S}. Similarmente σ(S) ´e o conjunto dos v´ertices

4.1 Formula¸c˜ao N˜ao Orientada 38

Figura 9: Restri¸c˜ao (4.5)

de entrega de S, σ(S) = {n + i ∈ D : i ∈ S}. Ent˜ao, para S ⊆ V , deﬁne-se S = V \S e

E(S) = {(i, j) ∈ E : i ∈ S, j ∈ S}. Ser´a escrito x(S) em vez de x(E(S)).

Sejam S

, . . . , S

⊂ P ∪ D conjuntos mutuamente disjuntos, tal que, m ≥ 2, S

∩

π(S

i+1

) = ∅, ∀i = 1, . . . , m, onde S

m+1

= S

. Ent˜ao a inequa¸c˜ao



i=1

x(S

) ≤



i=1

| − m − 1 (4.7)

´e v´alida.

Exemplo: Considere o subconjunto S

= {i, n + k}, S

= {j, n + i}, S

= {k, n + j}.

Claramente S

∩ π(S

i+1

) = ∅, ∀i = 1, 2, 3. O GOC para esse conjunto ´e: x

i,n+k

+ x

j,n+i

k,n+j

≤ 2. Como mostra a Figura 10.

Uma classe semelhante de desigualdades foi proposta por Balas, Fischetti e Pul-

leyblank (1995) para o precedence-constrained asymmetric traveling salesman problem

(PCATSP). Foi mostrado em (DUMITRESCU et al., 2008) que em geral as GOCs n˜ao deﬁ-

nem facetas do poliedro TSPPD. Apesar disso elas s˜ao cortes muito efetivos no algoritmo

de branch-and-cut. A separa¸c˜ao das GOCs ´e feita de forma exata (atrav´es do algoritmo

de corte m´ınimo) para o caso m = 2 e de forma heur´ıstica para os casos em que m > 2.

N˜ao existe algoritmo de separa¸c˜ao polinomial conhecido para m qualquer.

V´arias outras fam´ılias de desigualdade v´alidas s˜ao apresentadas em Dumitrescu et al.

(2008) e utilizadas como cortes no algoritmo de branch-and-cut. Elas s˜ao as OMC (Order

Matching Constraints), DGOMCs (Doubly Generalized Order Matching Constraints), PC

4.2 Formula¸c˜ao Orientada 39

Figura 10: GOC com m = 3

(Precedence Constraints), LSEC (Lifted subtour elimination constraints), GLSEC (Gene-

ralized lifted subtour elimination constraints), DC (Depot constraints), StEnC (Start-End

Constraints), entre outras.

E interessante notar que, apesar de v´arias dessas desigualdades deﬁnirem facetas do

TSPPD, o efeito conjunto de todos esses cortes em termos de redu¸c˜ao do gap de integra-

lidade ´e menor do que apenas as GOCs.

Nesta sess˜ao apresenta-se uma nova formula¸c˜ao linear inteira para o TSPPD sobre

um grafo orientado completo G = (V, A). O dep´osito ser´a denotado apenas por 0 (n˜ao

h´a duplica¸c˜ao do dep´osito). Temos V = {0, 1, . . . , 2n} como sendo o conjunto de v´ertices.

Novamente as coletas s˜ao dadas por P = {1, . . . , n} e as entregas por D = {n+1, . . . , 2n}.

O arco a ∈ A com origem em i e destino em j ´e denotado por (i, j). Seja c

o custo do

arco a, esse custo ´e sim´etrico (c

= c

) e ´e o mesmo custo da aresta (i, j) na formula¸c˜ao

n˜ao orientada. Para cada conjunto S ⊂ V , temos δ

(S) = {(i, j) ∈ A : i ∈ S, j /∈ S},

−

(S) = {(i, j) ∈ A : i /∈ S, j ∈ S}, V

= V \ {0}, V

= V \ {i}, V

i+n

= V \ {i + n}.

A(S

: S

) representa o conjunto de arcos (i, j) ∈ A onde i ∈ S

e j ∈ S

. O conjunto de

arcos A n˜ao precisa conter os arcos do dep´osito para a entrega (0 : D) nem os arcos de

coleta para o dep´osito (P : 0), pois nunca uma entrega ser´a o primeiro v´ertice a ser visitado

ao sair do dep´osito, nem h´a a possibilidade de partir de uma coleta e ir diretamente ao

dep´osito.

4.2 Formula¸c˜ao Orientada 40

O modelo matem´atico para TSPPD tem-se:

Vari´avel de decis˜ao:



1 se o arco pertence a rota

0 caso contr´ario

Formula¸c˜ao:

Minimize:



(i,j)∈A

(4.8)



a∈δ

−

(i)

= 1 ∀i ∈ V (4.9)



a∈δ

(i)

= 1 ∀i ∈ V (4.10)



a∈δ

(S)\A(S:{0})

≥ 1 ∀S ⊂ V

|i ∈ S e i + n /∈ S (4.11)



a∈δ

(S)\A(S:{i+n})

≥ 1 ∀S ⊂ V

i+n

|0 ∈ S e i /∈ S (4.12)



a∈δ

(S)\A(S:{i})

≥ 1 ∀S ⊂ V

|i + n ∈ S e 0 /∈ S (4.13)

∈ {0, 1} ∀a ∈ A (4.14)

A fun¸c˜ao objetivo (4.8) ´e minimizar a soma dos custos dos arcos. As restri¸c˜oes (4.9)

e (4.10) dizem que exatamente um arco entra e um arco sai de cada v´ertice i. As trˆes

pr´oximas restri¸c˜oes servem tanto para eliminar sub ciclos para garantir a seq

uˆencia correta

de coletas e entregas. A restri¸c˜ao (4.11) indica que deve haver um caminho orientado de

i para i + n sem passar pelo dep´osito (veja Figura 11(a)). A restri¸c˜ao (4.12) indica que

deve haver um caminho orientado de 0 at´e i sem passar por i + n (veja Figura 11(b)).

Finalmente, a restri¸c˜ao (4.13) indica que deve existir um caminho orientado de i + n at´e

0 sem passar por i (veja Figura 11(c)).

Em um algoritmo de branch-and-cut sobre essa formula¸c˜ao, cria-se o problema apenas

com as restri¸c˜oes (4.9) e (4.10). As demais restri¸c˜oes v˜ao sendo separadas ao longo do

algoritmo. Como essas restri¸c˜oes s˜ao essenciais para a viabilidade da solu¸c˜ao, elas devem

ser separadas em todos os n´os da ´arvore de enumera¸c˜ao. Essa separa¸c˜ao ´e feita atrav´es

do algoritmo do ﬂuxo m´aximo - corte m´ınimo nos 3 casos, conforme mostrado a seguir:

4.2 Formula¸c˜ao Orientada 41

(a) Coleta para entrega (b) Dep´osito para coleta (c) Entrega para dep´osito

Figura 11: Desigualdades da formula¸c˜ao orientada

Coleta para entrega : Cria-se um grafo contendo apenas os arcos com valor positivo

na solu¸c˜ao do problema linear do corrente. A capacidade desses arcos ´e deﬁnida

como sendo igual a esse valor. Elimina-se os arcos adjacentes ao dep´osito. Ent˜ao

aplica-se o algoritmo de ﬂuxo m´aximo nesse grafo, tendo como origem i e destino

i + n, para cada i ∈ P . Caso o valor do ﬂuxo seja menor que 1 em algum desses

casos, existe um corte violado.

Dep´osito para coleta : Os grafos s˜ao criados de forma similar, por´em para cada i ∈ P ,

elimina-se os arcos adjacentes ao v´ertice i+n. Aplica-se o algoritmo de ﬂuxo m´aximo

em cada um desses grafos, tendo como origem 0 e destino i. Caso o valor do ﬂuxo

seja menor que 1, signiﬁca que temos um corte violado.

Entrega para o dep´osito : Procede-se de forma similar ao item anterior, cada grafo

elimina os arcos adjacentes ao v´ertice i. O algoritmo de ﬂuxo m´aximo ´e aplicado

tendo como origem i + n e como destino 0.

Seja S um subconjunto de V

. A formula¸c˜ao orientada j´a implica que em qualquer

solu¸c˜ao pelo menos um arco dever´a entrar em S. Entretanto, analisando-se com mais

cuidado quais v´ertices pertencem a S, ´e poss´ıvel obter uma nova desigualdade que domina

(4.11):



a∈S

≥ 1 ∀S ⊆ V

(4.15)

4.2 Formula¸c˜ao Orientada 42

onde, S ´e o subconjunto dos arcos de δ

−

(S) deﬁnido da seguinte forma.

1. Se (i, j) ∈ δ

−

(S), i, j ∈ P , ent˜ao (i, j) ∈ S.

2. Se (i + n, j) ∈ δ

−

(S), i + n ∈ D, j ∈ P . Caso i /∈ S ent˜ao (i + n, j) ∈ S, caso

contr´ario (i + n, j) /∈ S.

3. Se (i, j + n) ∈ δ

−

(S), i ∈ P , j + n ∈ D. Caso j /∈ S ent˜ao (i, j + n) ∈ S, caso

contr´ario (i, j + n) /∈ S.

4. Se (i + n, j + n) ∈ δ

−

(S), i + n, j + n ∈ D. Caso i ou j /∈ S ent˜ao (i + n, j + n) ∈ S,

caso contr´ario (i + n, j + n) /∈ S.

A condi¸c˜ao 1 ´e ilustrada na Figura 12(a), nessa condi¸c˜ao (i, j) pode ser o ´unico arco

entrando em S, logo ele deve pertencer a S. Por outro lado, um arco (i+n, j) na condi¸c˜ao

da Figura 12(b) s´o pode estar em uma rota, se esta rota j´a entrou anteriormente em S

antes de passar pelo v´ertice i. Logo esse arco n˜ao pertence a S. Similarmente na condi¸c˜ao

da Figura 12(c), o arco (i, j + n) entrou em S depois da rota j´a ter entrado anteriormente

em S, passando por j, assim o arco n˜ao pertence a S. Finalmente, na condi¸c˜ao da Figura

12(d), um arco (i + n, j + n) s´o pode estar na rota, se esta rota j´a entrou em S antes,

passando por i e/ou j.

(a) Restri¸c˜ao (4.17) (b) Restri¸c˜ao (4.18) (c) Restri¸c˜ao (4.19) (d) Restri¸c˜ao (4.20)

Figura 12: Desigualdades do Corte - Formula¸c˜ao Inteira

Ao contr´ario da desigualdades (4.11)-(4.13), que podem ser facilmente separadas pelo

algoritmo do corte m´ınimo, n˜ao parece ser poss´ıvel separar (4.15) em tempo polinomial.

Entretanto, ´e poss´ıvel separar esse corte utilizando-se a seguinte formula¸c˜ao de programa-

¸c˜ao inteira. Seja G = (V, A

∗

) o grafo onde V = {0, 1, . . . , 2n} e A

∗

´e o conjunto de arcos

com valor positivo na solu¸c˜ao do problema linear corrente:

Dados:

i,j

valor fracion´ario da vari´avel associada ao arco (i, j)

4.3 Formula¸c˜ao Estendida 43

Vari´aveis:



1 se o v´ertice i ∈ S

0 caso contr´ario

i,j



1 se o arco (i, j) ∈ S

0 caso contr´ario

Formula¸c˜ao:

Minimize:



(i,j)∈A

i,j

(4.16)

Sujeito a:

i,j

≥ y

− y

∀(i, j) ∈ A : i ≤ n e j ≤ n (4.17)

i+n,j

≥ y

− y

i+n

− y

∀(i, j) ∈ A : i ≤ n e j ≤ n (4.18)

i,j+n

≥ y

j+n

− y

∀(i, j) ∈ A : i ≤ n e j ≤ n (4.19)

i+n,j+n

≥ y

j+n

− y

i+n

− y

∀(i, j) ∈ A : i ≤ n e j ≤ n (4.20)



i=1

≥ 2 (4.21)

= 0 (4.22)

O objetivo, (4.16), dessa formula¸c˜ao ´e minimizar o valor fracion´ario dos arcos em S.

As restri¸c˜oes (4.17),(4.18),(4.19) e (4.20) correspondem as quatro condi¸c˜oes para que um

arco perten¸ca a S. A restri¸c˜ao (4.21) ´e colocada porque a restri¸c˜ao (4.15) s´o pode estar

violada para conjuntos S de tamanho pelo menos 2, enquanto (4.22) indica que o v´ertice

0 n˜ao deve pertencer a S.

Seja N = {1, . . . , 2n} e N

= N ∪ {0}. Para o conjunto de v´ertices S, K(S) ´e o

d´ıgrafo completo de S, ou seja, o conjunto de arcos {(u, v) : u, v ∈ S, u = v}. Existe uma

correspondˆencia de um-para-um entre os ciclos hamiltonianos de K(N

) e os caminhos

hamiltonianos de K(N).

O TSPPD no grafo completo K(N

) pode ser modelado como um problema de pro-

grama¸c˜ao inteira deﬁnido no grafo de camadas G



= (V, A), onde V consiste no v´ertice 0,

uma c´opia desse v´ertice T , e n´os intermedi´arios (i, k) para i, k ∈ N. O primeiro ´ındice

4.3 Formula¸c˜ao Estendida 44

corresponde ao identiﬁcador do v´ertice i do grafo K(N) enquanto o segundo refere-se ao

n´ıvel do caminho hamiltoniano. O conjunto de arcos A ´e composto por trˆes tipos de arcos.

Primeiro os que partem do dep´osito 0 para os v´ertices (i, 1), os quais s˜ao denotados por

(0, i, 0) para i ∈ N . O segundo tipo, (i, T, 2n), s˜ao os que chegam ao dep´osito, partindo

dos v´ertices do ´ultimo n´ıvel (i, 2n) com destino a T . Por ﬁm, para i, j ∈ N tal que i = j

e 1 ≤ k ≤ 2n − 1, ser˜ao denotados como (i, j, k) os arcos que partem do v´ertice (i, k) at´e

o (j, k + 1). Assim, o grafo G



, ter´a (2n + 1) n´ıveis.

Para melhor explicar a formula¸c˜ao ser˜ao deﬁnidos os seguintes conjuntos: N(j) =

N \ {j}; V

= {(i, 1), (i, 2), . . . , (i, 2n)} ; V

= V \ {0, T }; V

= V \ V

´e o conjunto de

v´ertices que n˜ao cont´em o v´ertice i em nenhum dos n´ıveis k e V

i+n

= V \ V

i+n

Figura 13: Solu¸c˜ao para uma instˆancia com 3 pares de clientes representada como um

caminho em G



Como exemplo, a Figura 13 representa uma solu¸c˜ao para uma instˆancia de seis v´ertices

(3 coletas, v´ertices de 1 a 3, e 3 entregas, v´ertices de 4 a 6) sobre o grafo G



. A formula¸c˜ao

estendida ´e apresentada a seguir.

Dados:

n ´e a quantidade de pares (coleta-entrega)

i,j

o custo da aresta (i, j)

Vari´aveis:

i,j



1 se o arco (i, j) pertence ao caminho no n´ıvel k

0 caso contr´ario

4.3 Formula¸c˜ao Estendida 45

•



1 se o arco (i, j) pertence ao caminho em qualquer n´ıvel

0 caso contr´ario

Formula¸c˜ao:

Minimize



j∈N

0,j

2n−1



k=1



i∈N



j∈N (i)

i,j

× w

i,j



i∈N

i,T

(4.23)



j∈N

0,j

= 1 (4.24)

0,j



i∈N(j)

j,i

∀j = 1 . . . 2n (4.25)



i∈N(j)

i,j



l∈N (j)

k+1

j,l

∀j = 1 . . . 2n e

∀k = 1 . . . 2n − 2 (4.26)

0,i

= w

0,i

∀i = 1 . . . 2n (4.27)

i,j



k∈N

i,j

∀i = 1 . . . 2n,

∀j = 1 . . . 2n (4.28)

i,0

= w

i,T

∀i = 1 . . . 2n (4.29)



j∈N

(j)

i,j

= 1 ∀i = 1 . . . 2n (4.30)



(i,j,k)∈δ

(S)\A(S:{0})

i,j

≥ 1 ∀S ⊂ V

|S ⊃ V

S ∩ V

i1+n

= ∅ (4.31)



(i,j,k)∈δ

(S)\A(S:{i1+n})

i,j

≥ 1 ∀S ⊂ V

i1+n

|S ⊃ {0} e

S ∩ V

= ∅ (4.32)



(i,j,k)∈δ

(S)\A(S:{i1})

i,j

≥ 1 ∀S ⊂ V

|S ⊃ V

i1+n

S ∩ V

= ∅ (4.33)

O objetivo dessa formula¸c˜ao ´e minimizar a soma dos custos das arestas utilizadas,

dada por (4.23). A formula¸c˜ao tem 3 partes com foi explicado anteriormente. A restri¸c˜ao

4.3 Formula¸c˜ao Estendida 46

(4.24) obriga a ter ﬂuxo partindo do dep´osito com valor 1, como a vari´avel w

i,j

´e bin´aria,

ser´a escolhida somente um arco. A restri¸c˜ao (4.25) representa a sa´ıda do ﬂuxo, a partir

do deposito, no n´ıvel 0 com valor unit´ario o este ﬂuxo precisa chegar, novamente ao

dep´osito, no n´ıvel 2n. Analogamente na restri¸c˜ao (4.26) constr´oi-se o ﬂuxo que passa pelos

n´ıveis intermedi´arios e ﬁnal. As restri¸c˜oes (4.27-4.29) correspondem ao mapeamento das

vari´aveis w nas vari´aveis x. A restri¸c˜ao (4.30) obriga o ﬂuxo a passar exatamente uma

vez em cada v´ertice (em algum n´ıvel). As pr´oximas restri¸c˜oes (4.31-4.33) s˜ao semelhantes

`as explicadas na se¸c˜ao 4.2, aplicadas `a vari´avel x (restri¸c˜oes (4.11-4.13), respectivamente)

modiﬁcadas para a vari´avel w.

Em um algoritmo de branch-and-cut sobre essa formula¸c˜ao, cria-se o problema apenas

com as restri¸c˜oes (4.24-4.30). Enquanto as demais ser˜ao criadas ao longo do algoritmo.

Como essas restri¸c˜oes s˜ao essenciais para a viabilidade do problema, estas devem ser

separadas em todos os n´os da ´arvore de enumera¸c˜ao. As restri¸c˜oes aplicadas a vari´avel

x, descritas na se¸c˜ao anterior, continuam valendo para esta formula¸c˜ao e ser˜ao aplicadas

da mesma forma e como a vari´avel w tem rela¸c˜ao com x tamb´em podem-se aplicar as

separa¸c˜oes com algumas mudan¸cas, que ser˜ao descritas a seguir:

Coleta para entrega (em w) Cria-se um grafo G

a partir de G



, por´em sem conter

os arcos adjacentes ao dep´osito 0 e T , para i ≤ n. Deve-se calcular, usando o

algoritmo de ﬂuxo m´aximo/corte m´ınimo, o ﬂuxo entre os pontos V

e V

i+n

. Para

tanto, ´e necess´ario adicionar dois super v´ertices s e t, al´em disso criar arcos com

capacidade inﬁnita A(s : V

) e A(V

i+n

: t). Os demais arcos tem como capacidade

o seu valor na solu¸c˜ao fracion´aria corrente. Calcula-se o corte m´ınimo entre s e t.

Se o valor desse corte for menor do que 1, uma desigualdade (4.31) est´a violada. O

grafo G

´e ilustrado na Figura 14.

Dep´osito para coleta (em w) Cria-se um grafo G

a partir de G



, que n˜ao contenha

os v´ertices adjacentes aos v´ertices V

i+n

, para i ≤ n. Deve-se calcular, usando o

algoritmo de ﬂuxo m´aximo/corte m´ınimo, o ﬂuxo entre os pontos 0 e V

. Para

tanto, ´e necess´ario adicionar um super v´ertice t, al´em disso criar arcos A(V

: t) com

capacidade inﬁnita. O dep´osito ser´a o ponto de partida. Os demais arcos tem como

capacidade o seu valor na solu¸c˜ao fracion´aria corrente. Calcula-se o corte m´ınimo

entre 0 e t. Se o valor desse corte for menor que 1, uma desigualdade (4.32) est´a

violada. O grafo G

´e ilustrado na Figura 15.

Entrega para dep´osito (em w) Cria-se um grafo G

a partir de G



, que n˜ao conte-

nha os v´ertices V

, para i ≤ n. Deve-se calcular, usando o algoritmo de ﬂuxo m´a-

4.3 Formula¸c˜ao Estendida 47

Figura 14: Grafo G

- Coleta para entrega (em w)

Figura 15: Grafo G

- Dep´osito para coleta (em w)

ximo/corte m´ınimo, o ﬂuxo deve ser entre os pontos V

i+n

e T. Para isso, ´e necess´ario

adicionar um superv´ertice s, que representar´a o ponto de partida, al´em disso criar

arcos A(s : V

i+n

) com capacidade inﬁnita. Os demais arcos tem como capacidade o

seu valo na solu¸c˜ao fracion´aria corrente. Calcula-se o corte m´ınimo entre s e T . Se

o valor desse corte for menor que 1, uma desigualdade (4.33) est´a violada. O grafo

´e ilustrado na Figura 16

Ao analisar uma solu¸c˜ao fracion´aria, ap´os a adi¸c˜ao de todos os cortes acima relatados,

veriﬁcou-se que ainda poderia ser criado mais um corte. Ser´a usado um exemplo para

4.3 Formula¸c˜ao Estendida 48

Figura 16: Grafo G

- Entrega para dep´osito (em w)

explicar esse corte. Na Figura 17 mostra-se a solu¸c˜ao fracion´aria da instˆancia prob10a na

formula¸c˜ao estendida.

Essa solu¸c˜ao fracion´aria pode ser decomposta em duas rotas fracion´arias (com valor

0,5), representadas esquematicamente na Figura 17. Pode-se notar que essa decomposi¸c˜ao

n˜ao ´e ´unica, outras trˆes decomposi¸c˜oes seriam poss´ıveis dependendo de como se escolhe a

seq

uˆencia das rotas a partir dos pontos de bifurca¸c˜ao nos v´ertices 4 e 14.

Pode-se notar que esta solu¸c˜ao fracion´aria satisfaz todas as restri¸c˜oes at´e agora ex-

plicadas. Por´em ao aplicar a restri¸c˜ao (4.32) a dois pares de coleta ao mesmo tempo,

encontra-se mais uma desigualdade (4.32) violada. O Exemplo abaixo removeu os v´erti-

ces de entrega (15 e 17) dos v´ertices 5 e 7.

O ﬂuxo m´aximo (F ) encontrado entre 0 e 5 e entre 0 e 7 tem capacidade de F = 0, 5.

Isto ´e facilmente observado na Figura 19, pois o segundo 7 da Rota1 e o primeiro 5 da

Rota2 n˜ao tem mais nenhuma liga¸c˜ao com dep´osito 0.

O mesmo n˜ao ocorre se for eliminado somente um desses arcos, como ´e mostrado nas

Figuras 20 e 21.

Outra formula¸c˜ao estendida para o problema do TSPPD ´e a que usa ﬂuxos ao inv´es

de restri¸c˜oes de corte para garantir a existˆencia de certos caminhos no grafo estendido.

Esta formula¸c˜ao ´e equivalente `a formula¸c˜ao estendida j´a apresentada. A diferen¸ca ´e que

a formula¸c˜ao por ﬂuxos possui uma quantidade polinomial de vari´aveis e restri¸c˜oes, en-

quanto a anterior possui uma quantidade exponencial de restri¸c˜oes. Para substituir as

4.3 Formula¸c˜ao Estendida 49

Figura 17: Solu¸c˜ao Fracion´aria da Instˆancia prob10a

4.3 Formula¸c˜ao Estendida 50

Rota 1: 0- 5- 7- 3- 2- 6- 4- 9- 8- 6- 2-15- 3- 7-19-14-12-15-11-17-13-T

Rota 2: 0-10- 1-11- 8- 9- 4-13-17-10- 1-18- 5-20-16-14-19-12-16-20-18-T

Figura 18: Decomposi¸c˜ao em rotas da solu¸c˜ao fracion´aria da instˆancia prob10a

Rota 1: 0- 5- 7- 3- 2- 6- 4- 9- 8- 6- 2- - 3- 7-19-14-12- -11- -13-T

Rota 2: 0-10- 1-11- 8- 9- 4-13- -10- 1-18- 5-20-16-14-19-12-16-20-18-T

Figura 19: Retirando as entregas 15 e 17, (restri¸c˜ao (4.32) com F = 0, 5)

Rota 1: 0- 5- 7- 3- 2- 6- 4- 9- 8- 6- 2- - 3- 7-19-14-12- -11-17-13-T

Rota 2: 0-10- 1-11- 8- 9- 4-13-17-10- 1-18- 5-20-16-14-19-12-16-20-18-T

Figura 20: Retirando a entrega 15 (restri¸c˜ao (4.32) com F = 1)

Rota 1: 0- 5- 7- 3- 2- 6- 4- 9- 8- 6- 2-15- 3- 7-19-14-12-15-11- -13-T

Rota 2: 0-10- 1-11- 8- 9- 4-13- -10- 1-18- 5-20-16-14-19-12-16-20-18-T

Figura 21: Retirando a entrega 17 (restri¸c˜ao (4.32) com F = 1)

restri¸c˜oes (4.31), para cada d, 1 ≤ d ≤ n, deﬁnimos que dever´a existir no grafo estendido

um ﬂuxo entre os v´ertices V

e V

i+d

. De modo similar, para cada d, 1 ≤ d ≤ n, deﬁnimos

no grafo estendido um ﬂuxo entre 0 e V

que n˜ao passe por V

i+d

. A formula¸c˜ao ´e descrita

a seguir:

Dados:

n ´e a quantidade de pares (coleta-entrega)

i,j

o custo da aresta (i, j)

Vari´aveis:

i,j

(Bin´aria):



1 se a aresta (i, j) pertence ao caminho no n´ıvel k

0 caso contr´ario

i,j

(Cont´ınua): quantidade de ﬂuxo que passa pelos arcos (i, j) em todos os n´ıveis

k,d

i,j

(Cont´ınua): quantidade de ﬂuxo que passa pelos arcos (i, j) que parte de i at´e

d no n´ıvel k, sem passar pelo dep´osito, 0.

k,d

i,j

(Cont´ınua): quantidade de ﬂuxo que passa pelos arcos (i, j) que parte de 0 at´e

d no n´ıvel k, sem passar por i + n.

4.3 Formula¸c˜ao Estendida 51

Formula¸c˜ao:

Minimize



j∈N

0,j

× w

0,j

2n−1



k=1



i∈N



j∈N (i)

i,j

× w

i,j



i∈N

i,0

× w

i,0

(4.34)



j∈N

0,j

= 1 (4.35)



i∈N(j)

i,j



l∈N (j)

k+1

j,l

∀j = 1 . . . 2n e

∀k = 1 . . . 2n − 2 (4.36)

0,i

= w

0,i

∀i = 1 . . . 2n (4.37)

i,j



k∈N

i,j

∀i = 1 . . . 2n,

∀j = 1 . . . 2n (4.38)

i,0

= w

i,T

∀i = 1 . . . 2n (4.39)



j∈N

(j)

i,j

= 1 ∀i = 1 . . . 2n (4.40)

k,d

i,j

≤ w

j,i

∀i = 0 . . . 2n, ∀j = 0 . . . 2n,

∀k = 0 . . . 2n, ∀d = 1 . . . n (4.41)



j=1



k=1

k,d

d,j

= 1 ∀d = 1 . . . n (4.42)



i∈N({j,k})

k,d

i,j



i∈N({j,k+p})

k−1,d

j,i

∀j, d, k = 1 . . . 2n (4.43)

4.4 Testes e resultados 52

k,d

i,j

≤ w

j,i

∀i = 1 . . . 2n, ∀j = 1 . . . 2n,

∀k = 1 . . . 2n, ∀d = 1 . . . n (4.44)



j=1

0,d

0,j

= 1 ∀d = 1 . . . n (4.45)

0,d

0,j



i=1

1,d

j,i

∀j = 1 . . . n, ∀d = 1 . . . n (4.46)



i=1

k,d

i,j



i=1

k+1,d

i,j

∀d = 1 . . . n,

∀j = 1 . . . n, ∀k = 1 . . . 2n (4.47)

As restri¸c˜oes (4.35) at´e (4.40) s˜ao as mesmas da formula¸c˜ao estendida. As demais

s˜ao as restri¸c˜oes que diferenciam as duas formula¸c˜oes. As restri¸c˜oes de (4.41) at´e (4.43),

garantem que deve haver um ﬂuxo entre a coleta e entrega sem passar pelo dep´osito,

onde (4.41) faz o mapeamento das vari´aveis w para as f. A restri¸c˜ao (4.42) obriga existir

um ﬂuxo com valor unit´ario entre cada par de coleta-entrega. Na restri¸c˜ao (4.43) ´e a

conserva¸c˜ao do ﬂuxo. As vari´aveis g, por sua vez, garantem que haja um ﬂuxo entre o

dep´osito, 0, e o v´ertice de coleta, sem passar pela entrega. Dessa forma deve-se mapear

as vari´aveis w para g, restri¸c˜ao (4.44). Depois precisa sair do dep´osito um ﬂuxo para

cada coleta (4.45), depois deve-se conservar esse ﬂuxo at´e o seu destino, restri¸c˜oes (4.46)

e (4.47).

O algoritmo de branch-and-cut foi implementado usando o CPLEX 10.2. As ramiﬁ-

ca¸c˜oes na ´arvore de enumera¸c˜ao foram feitas na vari´avel x

na formula¸c˜ao orientada e na

vari´avel w

no caso da formula¸c˜ao estendida.

O conjunto de instˆancias testes utilizado foi criado por Ruland e Rodin (1997) atrav´es

da gera¸c˜ao 2n + 1 pontos aleatoriamente no quadrado [0, 1000] × [0, 1000]. O primeiro

ponto ´e utilizado como o dep´osito, enquanto os restantes pontos s˜ao pedidos para formar

pares (ponto i est´a emparelhado com ponto n+i). O custo de viagem (c

) foi estabelecido

pelo arredondamento das distˆancias euclidianas. Instˆancias com n em {5, 10, . . . , 30, 35}

foram criadas, cinco para cada tamanho. As instˆancias s˜ao nomeadas probnx, em que

4.4 Testes e resultados 53

x ´e uma das letras {a, b, c, d, e} usadas para distinguir entre as instˆancias com o mesmo

tamanho.

Os algoritmos foram implementados em C++ e rodados numa m´aquina Core 2 Duo

E7300, com 4GB de RAM e CPLEX 10.2. Foram realizados v´arios testes comparativos

entre as formula¸c˜oes implementadas e as da literatura.

As tabelas que ser˜ao apresentadas cont´em os seguintes dados. A primeira coluna

indica o nome da instˆancia. Na coluna seguinte o melhor valor da literatura, n´umeros em

it´alico representam valores que n˜ao foram provados serem ´otimos. As 4 pr´oximas colunas

apresentam resultados obtidos neste trabalho atrav´es das novas formula¸c˜oes (orientada e

estendida), e as outras 4 resultados da formula¸c˜ao n˜ao-orientada obtidas por Dumitrescu

et al. (2008). S˜ao 4 os elementos comparativos: custo - valor do limite inferior obtido;

GAP - porcentagem que falta para chegar ao melhor; tempo - tempo total em segundos

para se obter o limite; cortes - total de cortes adicionados.

Os resultados descritos na Tabela 13, comparam a formula¸c˜ao orientada somente com

as restri¸c˜oes (4.9-4.14) (sem cortes adicionais) com a formula¸c˜ao n˜ao orientada com apenas

as restri¸c˜oes (4.2-4.6) (tamb´em sem cortes adicionais). A formula¸c˜ao orientada consegue

limites consistentemente melhores que a n˜ao orientada o que sugere que aquela ´e mais

forte que esta. Enquanto o GAP m´edio da orientada ﬁcou em 9, 44% o da n˜ao orientada

foi 11, 38%. N˜ao foi indicado em Dumitrescu et al. (2008) a quantidade de cortes (4.2-4.6)

usados.

A Tabela 14 mostra resultados da formula¸c˜ao orientada fortalecida com o corte mos-

trado na Se¸c˜ao 4.2.2, o corte do dep´osito `a duas coletas (veja a Se¸c˜ao 4.3.1) e os cortes do

CPLEX. A compara¸c˜ao ´e com os resultados obtidos em Dumitrescu et al. (2008) usando

todos os cortes mencionados na Se¸c˜ao 4.1.1, bem como os cortes do CPLEX. Pode-se ver

que os cortes da formula¸c˜ao n˜ao-orientada foram bem mais efetivos. Enquanto o GAP

m´edio da orientada caiu de 9, 45% para 8, 21%, a formula¸c˜ao orientada obteve um ganho

muito mais signiﬁcativo,passando de 11, 38% para 3, 32%.

Os cortes da formula¸c˜ao n˜ao-orientada mencionados na Se¸c˜ao 4.1.1 tamb´em poderiam

ser inseridos na formula¸c˜ao orientada, obtendo resultados potencialmente melhores. En-

tretanto isso dependeria de uma implementa¸c˜ao de complexas heur´ısticas de separa¸c˜ao

(nenhum desses cortes possui separa¸c˜ao conhecida em tempo polinomial). A id´eia de se

4.4 Testes e resultados 54

Orientada N˜ao Orientada Dumitrescu et al. (2008)

Instˆancia Melhor Custo GAP Tempo Cortes Custo GAP Tempo Cortes

prob5a 3.585,00 3.585,00 0,00% 0,0 18 3.495,38 2,50% -

prob5b 2.565,00 2.565,00 0,00% 0,0 19 2.565,00 0,00% -

prob5c 3.787,00 3.787,00 0,00% 0,0 25 3.787,00 0,00% 0,0 -

prob5d 3.128,00 3.128,00 0,00% 0,0 19 3.128,00 0,00% -

prob5e 3.123,00 3.046,57 2,45% 0,0 31 2.966,85 5,00% -

prob10a 4.896,00 4.473,83 8,62% 0,1 112 4.288,90 12,40% -

prob10b 4.490,00 3.994,60 11,03% 0,1 260 3.767,11 16,10% -

prob10c 4.070,00 3.979,80 2,22% 0,0 152 3.903,13 4,10% 0,0 -

prob10d 4.551,00 4.380,00 3,76% 0,1 141 4.323,45 5,00% -

prob10e 4.874,00 4.711,75 3,33% 0,1 138 4.688,79 3,80% -

prob15a 5.150,00 4.703,00 8,68% 0,3 329 4.583,50 11,00% -

prob15b 5.391,00 4.649,28 13,76% 0,5 673 4.323,58 19,80% -

prob15c 5.008,00 4.798,13 4,19% 0,3 375 4.697,50 6,20% 0,0 -

prob15d 5.566,00 4.987,00 10,40% 0,5 579 4.881,38 12,30% -

prob15e 5.229,00 5.049,82 3,43% 0,4 395 4.957,09 5,20% -

prob20a 5.698,00 5.173,74 9,20% 1,0 879 5.054,13 11,30% -

prob20b 6.213,00 5.502,25 11,44% 0,9 679 5.392,88 13,20% -

prob20c 6.200,00 5.605,52 9,59% 0,5 461 5.449,80 12,10% 0,1 -

prob20d 6.106,00 5.657,58 7,34% 0,7 621 5.574,78 8,70% -

prob20e 6.465,00 5.751,60 11,03% 0,8 544 5.676,27 12,20% -

prob25a 7.332,00 6.177,56 15,75% 1,1 686 6.085,56 17,00% -

prob25b 6.665,00 5.873,17 11,88% 1,2 657 5.685,25 14,70% -

prob25c 7.095,00 6.213,86 12,42% 1,2 699 6.087,51 14,20% 0,2 -

prob25d 7.069,00 6.095,42 13,77% 1,1 709 6.015,72 14,90% -

prob25e 6.754,00 6.069,17 10,14% 1,0 622 5.930,01 12,20% -

prob30a 7.309,00 6.115,71 16,33% 2,0 900 5.964,14 18,40% -

prob30b 6.857,00 5.979,53 12,80% 1,8 844 5.732,45 16,40% -

prob30c 7.723,00 6.668,25 13,66% 1,5 686 6.587,72 14,70% 0,3 -

prob30d 7.310,00 6.457,99 11,66% 2,6 1.159 6.396,25 12,50% -

prob30e 7.213,00 6.108,50 15,31% 1,4 705 6.022,86 16,50% -

prob35a 7.746,00 6.739,50 12,99% 3,5 1.221 6.591,85 14,90% -

prob35b 7.904,00 6.566,80 16,92% 4,2 1.297 6.299,49 20,30% -

prob35c 7.949,00 6.800,47 14,45% 3,9 1.287 6.629,47 16,60% 0,3 -

prob35d 7.905,00 6.704,63 15,19% 2,3 730 6.600,68 16,50% -

prob35e 8.530,00 7.115,46 16,58% 2,7 879 7.037,25 17,50% -

M´edia 5.927,31 5.291,87 9,44% 1,1 558 5.176,31 11,38% 0,1 -

Tabela 13: Relaxa¸c˜ao Linear da Formula¸c˜ao Orientada (4.9-4.14) × N˜ao-orientada (4.2-

4.6): sem cortes adicionais

4.4 Testes e resultados 55

orientada N˜ao-orientada Dumitrescu et al. (2008)

Instˆancia Melhor Custo GAP Tempo Cortes Custo GAP Tempo Cortes

prob5a 3.585,00 3.585,00 0,00% 0,0 41 3.585,00 0,00% 19

prob5b 2.565,00 2.565,00 0,00% 0,0 19 2.565,00 0,00% 6

prob5c 3.787,00 3.787,00 0,00% 0,0 25 3.787,00 0,00% 0,0 6

prob5d 3.128,00 3.128,00 0,00% 0,0 19 3.128,00 0,00% 6

prob5e 3.123,00 3.123,00 0,00% 0,0 63 3.123,00 0,00% 45

prob10a 4.896,00 4.494,00 8,21% 0,3 182 4.857,75 0,78% 134

prob10b 4.490,00 4.075,75 9,23% 0,4 180 4.490,00 0,00% 135

prob10c 4.070,00 4.070,00 0,00% 0,2 136 4.070,00 0,00% 3,1 93

prob10d 4.551,00 4.451,65 2,18% 0,2 124 4.551,00 0,00% 93

prob10e 4.874,00 4.731,77 2,92% 0,3 121 4.874,00 0,00% 97

prob15a 5.150,00 4.743,13 7,90% 1,1 328 5.063,33 1,68% 268

prob15b 5.391,00 4.756,69 11,77% 1,9 374 5.141,22 4,63% 580

prob15c 5.008,00 4.863,96 2,88% 1,4 252 5.008,00 0,00% 12,9 165

prob15d 5.566,00 5.112,37 8,15% 1,4 232 5.435,24 2,35% 390

prob15e 5.229,00 5.123,85 2,01% 1,3 281 5.229,00 0,00% 140

prob20a 5.698,00 5.247,34 7,91% 2,4 383 5.695,42 0,05% 438

prob20b 6.213,00 5.629,02 9,40% 4,6 515 6.144,93 1,10% 473

prob20c 6.200,00 5.658,56 8,73% 4,3 390 6.050,71 2,41% 16,8 444

prob20d 6.106,00 5.671,79 7,11% 1,8 405 6.001,88 1,71% 369

prob20e 6.465,00 5.878,76 9,07% 3,8 388 6.199,20 4,11% 962

prob25a 7.332,00 6.220,85 15,15% 6,8 496 6.670,14 9,03% 3.244

prob25b 6.665,00 5.939,32 10,89% 14,1 498 6.267,22 5,97% 2.266

prob25c 7.095,00 6.300,83 11,19% 9,0 695 6.770,59 4,57% 44,8 1.255

prob25d 7.069,00 6.191,44 12,41% 6,7 620 6.526,56 7,67% 3.873

prob25e 6.754,00 6.220,07 7,91% 11,1 585 6.539,76 3,17% 704

prob30a 7.309,00 6.231,05 14,75% 21,0 698 6.776,44 7,29% 3.238

prob30b 6.857,00 6.053,02 11,72% 13,2 612 6.475,78 5,56% 2.262

prob30c 7.723,00 6.766,18 12,39% 20,9 572 7.281,38 5,72% 73,2 2.019

prob30d 7.310,00 6.486,98 11,26% 10,4 753 7.043,19 3,65% 1.372

prob30e 7.213,00 6.279,94 12,94% 28,2 837 6.716,71 6,88% 3.412

prob35a 7.746,00 6.873,30 11,27% 39,3 1141 7.354,74 5,05% 1.649

prob35b 7.904,00 6.678,19 15,51% 23,5 931 7.104,95 10,11% 2.764

prob35c 7.949,00 6.850,60 13,82% 16,5 672 7.514,87 5,46% 100,3 3.194

prob35d 7.905,00 6.866,00 13,14% 28,2 898 7.324,58 7,34% 2.944

prob35e 8.530,00 7.217,68 15,38% 33,0 760 7.698,54 9,75% 3.562

M´edia 5.927,31 5.367,77 8,21% 8,8 435 5.687,57 3,32% 35,9 1.218

Tabela 14: Relaxa¸c˜ao Linear da Formula¸c˜ao orientada (4.9-4.14) + (4.15) + cortes CPLEX

× N˜ao-orientada (4.2-4.6) + todos os cortes da se¸c˜ao 4.1.1 + cortes CPLEX

partir para a formula¸c˜ao estendida foi obter limites compar´aveis (e at´e melhores) usando

apenas cortes conceitualmente simples e que podem ser separados em tempo polinomial

pelo algoritmo do corte m´ınimo.

A Tabela 15 apresenta os valores obtidos com formula¸c˜ao estendida, comparando-a

com a formula¸c˜ao n˜ao-orientada melhorada com todos os cortes mencionados na Se¸c˜ao

4.1.1 (mas n˜ao os do CPLEX). Os resultados em termos de limites foram muito bons.

Em nove das dez instˆancias com n ≤ 10 a formula¸c˜ao estendida obteve a solu¸c˜ao ´otima

inteira, sendo melhor do que a n˜ao-orientada com todos os cortes em 4 casos. No entanto,

s´o foi poss´ıvel realizar esses testes nessas instˆancias menores, pois a gera¸c˜ao de cortes

na formula¸c˜ao estendida est´a demorando excessivamente para convergir. Pode-se notar

a quantidade de cortes gerados nas instˆancias prob5a e prob10a, que pula da casa das

centenas para a dezena de milhar, apenas dobrando a quantidade de clientes.

Para evitar a necessidade da separa¸c˜ao de um grande n´umero de restri¸c˜oes na for-

4.4 Testes e resultados 56

Estendida N˜ao-orientada Dumitrescu et al. (2008)

Instˆancia Melhor Custo GAP Tempo Cortes Custo GAP Tempo Cortes

prob5a 3.585,00 3.585,00 0,00% 0,4 70 3.585,00 0,00% 19

prob5b 2.565,00 2.565,00 0,00% 0,0 29 2.565,00 0,00% 6

prob5c 3.787,00 3.787,00 0,00% 0,0 21 3.787,00 0,00% 0,0 6

prob5d 3.128,00 3.128,00 0,00% 0,0 34 3.128,00 0,00% 6

prob5e 3.123,00 3.123,00 0,00% 0,3 184 3.123,00 0,00% 45

prob10a 4.896,00 4.842,45 1,09% 3.240,0 14.966 4.806,15 1,84% 134

prob10b 4.490,00 4.490,00 0,00% 3.682,8 13.569 4.458,19 0,71% 135

prob10c 4.070,00 4.070,00 0,00% 20,4 11.458 4.070,00 0,00% 3,1 93

prob10d 4.551,00 4.551,00 0,00% 434,1 5.562 4.538,03 0,29% 93

prob10e 4.874,00 4.874,00 0,00% 807,7 6.463 4.840,66 0,68% 97

M´edia 3.906,90 3.901,55 0,11% 818,6 5.236 3.890,10 0,35% 1,6 63

Tabela 15: Relaxa¸c˜ao Linear da Formula¸c˜ao Estendida (4.24-4.33) + cortes de 2 coletas

× N˜ao-orientada (4.2-4.6) + todos os cortes da se¸c˜ao 4.1.1

Formula¸c˜ao por Fluxos Equivalente N˜ao-orientada Dumitrescu et al. (2008)

Instˆancia Melhor Custo GAP Tempo Cortes Custo GAP Tempo Cortes

prob5a 3.585,00 3.585,00 0,00% 0 - 3.585,00 0,00% 19

prob5b 2.565,00 2.565,00 0,00% 0 - 2.565,00 0,00% 6

prob5c 3.787,00 3.787,00 0,00% 0 - 3.787,00 0,00% 0,0 6

prob5d 3.128,00 3.128,00 0,00% 0 - 3.128,00 0,00% 6

prob5e 3.123,00 3.123,00 0,00% 0 - 3.123,00 0,00% 45

prob10a 4.896,00 4.827,00 1,41% 103 - 4.806,15 1,84% 134

prob10b 4.490,00 4.490,00 0,00% 110 - 4.458,19 0,71% 135

prob10c 4.070,00 4.070,00 0,00% 107 - 4.070,00 0,00% 3,1 93

prob10d 4.551,00 4.551,00 0,00% 105 - 4.538,03 0,29% 93

prob10e 4.874,00 4.874,00 0,00% 88 - 4.840,66 0,68% 97

prob15a 5.150,00 5.087,61 1,21% 955 - 4.999,31 2,93% 268

prob15b 5.391,00 5.120,26 5,02% 1.421 - 5.055,83 6,22% 580

prob15c 5.008,00 5.008,00 0,00% 733 - 5.008,00 0,00% 6,9 165

prob15d 5.566,00 5.545,66 0,37% 1.352 - 5.396,90 3,04% 390

prob15e 5.229,00 5.229,00 0,00% 929 - 5.229,00 0,00% 140

M´edia 4.360,87 4.332,70 0,53% 394 - 4.306,00 1,05% 3,3 145

Tabela 16: Relaxa¸c˜ao Linear da Formula¸c˜ao de Fluxo (4.35-4.47) × N˜ao-orientada (4.2-

4.6) + todos os cortes da se¸c˜ao 4.1.1

mula¸c˜ao estendida, criou-se a formula¸c˜ao por ﬂuxo equivalente que substitui um n´umero

exponencial de restri¸c˜oes por uma quantidade polinomial de vari´aveis, o que deixa o pro-

blema grande, usando muita mem´oria, mesmo assim mais f´acil de ser resolvido diretamente

pelo CPLEX usando um algoritmo de pontos interiores (m´etodo barreira). A Tabela 16

apresenta os resultados com as instˆancias de 5 a 15 pares encontrados atrav´es da formu-

la¸c˜ao de ﬂuxo equivalente. Nesses testes n˜ao foram separados os cortes de duas coletas,

o que causa uma pequena redu¸c˜ao na qualidade dos limites inferiores em rela¸c˜ao a tabela

anterior. Esses limites continuam sendo consistentemente melhores dos que os obtidos por

(DUMITRESCU et al., 2008) com a formula¸c˜ao n˜ao orientada.

Apesar da formula¸c˜ao por ﬂuxo equivalente ter permitido avaliar melhor o potencial

do uso das vari´aveis estendidas no TSPPD, seu uso j´a se torna invi´avel para n = 20.

Espera-se que com o uso de t´ecnicas mais avan¸cadas de programa¸c˜ao matem´atica (t´ecnicas

lagrangeanas, algoritmos de dual ascent ou de gera¸c˜ao de colunas) seja poss´ıvel no futuro

obter tais limites de forma eﬁciente.

Neste trabalho foram atacados dois problemas relacionados ao roteamento de ve´ı-

culo com coleta e entrega. O primeiro, o VRPPDTW, apresentou um problema com

muitas restri¸c˜oes e grande complexidade computacional, assim, decidiu-se que a melhor

abordagem a ﬁm de encontrar solu¸c˜oes boas em tempos razo´aveis foi uma metaheur´ıs-

tica. Para o segundo, como foram propostas formula¸c˜oes inteira utilizando o algoritmo de

branch-and-cut e o uma formula¸c˜ao linear resolvida pelo m´etodo de barreiras. Escolher

um problema com menos restri¸c˜oes n˜ao signiﬁca que seja mais simples de solu¸c˜ao, uma

vez que, o TSPPD continua pertencendo a classe NP-dif´ıcil e sim que tem menos detalhes

para serem observados.

A heur´ıstica ILS-MRD, utilizada para resolver o VRPPDTW, apresentou bons re-

sultados comparados `a literatura. Apesar de n˜ao encontrado novos valores melhores,

conseguiu encontrar, em sua grande maioria, os ´ultimos resultados da literatura. Esta

se mostrou uma heur´ıstica que demanda de pouco tempo computacional para conseguir

bons resultados.

Para o problema de caixeiro viajante com coleta e entrega foram propostas 3 formu-

la¸c˜oes para serem comparadas com as da literatura. A formula¸c˜ao orientada se apresen-

tou bastante r´apida, no entanto, n˜ao conseguiu bons limites inferiores para o problema,

pois comparada a formula¸c˜ao n˜ao-orientada sem cortes foi superior, mas ao se adicionar

cortes a formula¸c˜ao n˜ao orientada, a formula¸c˜ao orientada se mostrou mais fraca. En-

t˜ao resolveu-se estender a formula¸c˜ao orientada, esta se mostrou bem mais forte que a

anterior com bons limites inferiores, em contrapartida tornou-se lenta, devido a grade

quantidade de restri¸c˜oes (um n´umero exponencial). Assim, para amenizar esse problema

tentou-se a formula¸c˜ao de ﬂuxo que ﬁcou como intermedi´aria, pois n˜ao tem muitas res-

tri¸c˜oes, em contra-partida em um n´umero polinomial de vari´aveis, que apesar de muitas

(utiliza grande quantidade de mem´oria), ´e ainda menor que a quantidade de restri¸c˜oes

5.2 Trabalhos Futuros 58

(cortes) necess´arias para encontrar uma solu¸c˜ao na formula¸c˜ao estendida.

A grande vantagem da formula¸c˜ao de estendida/ﬂuxo do modelo exato, para o TSPPD,

mostrou-se bastante satisfat´orio no que se refere aos valores dos limites inferiores. Em sua

totalidade 8 das 15 instˆancias foram encontrados o ´otimo na raiz, da ´arvore de branch-and-

bound. O que demonstra que a formula¸c˜ao ´e forte. Conseguindo superar em 7 instˆancias

os valores anteriormente encontrados na literatura.

Para o VRPPDTW, h´a dois trabalhos na literatura que apresentaram bons resulta-

dos. Bent e Hentenryck (2006) propuseram uma heur´ıstica h´ıbrida onde num primeiro

est´agio tentaram reduzir a quantidade de rotas e num segundo est´agio, a custo de cada

rota. O outro trabalho foi o de Ropke e Pisinger (2006a) os quais apresentaram uma

heur´ıstica adaptativa baseada em inser¸c˜oes e remo¸c˜oes, mas para dispondo de uma boa

estrutura e algoritmos para tentar escolher os melhores elementos a serem alterados. Com

isso percebe-se que para se melhorar uma heur´ıstica, tem-se cada vez mais unido v´arias

t´ecnicas, heur´ısticas h´ıbridas, pois tem-se conseguido bons resultados com elas. Assim,

um path relink poderia ser usado no lugar da perturba¸c˜ao em algumas itera¸c˜oes. A fase

inicial poderia conter 2 etapas: uma para reduzir a quantidade de rotas e outra para

reduzir o custo total da viagem.

Outra proposta para o VRPPDTW seria utilizar a solu¸c˜ao heur´ıstica como passo

inicial para o algoritmo exato de gera¸c˜ao de coluna. Foi desenvolvido por Ropke (2007)

um branch-and-cut-and-price, e testado com 3 formula¸c˜oes diferentes. O mais importante

nesse tipo de algoritmo ´e conseguir descrever bons crit´erios de dominˆancia para assim

reduzir ao m´aximo o espa¸co de busca.

Apenar do TSPPD ter encontrado bons valores, o tempo n˜ao foi razo´avel, assim uma

das op¸c˜oes para melhorar o tempo e, conseq

uentemente, agilizar a convergˆencia seria a

adi¸c˜ao dos cortes propostos por (DUMITRESCU et al., 2008) `a formula¸c˜ao estendida (Se¸c˜ao

4.3). Outra proposta seria usar a formula¸c˜ao orientada at´e ela ﬁnalizar seus cortes na raiz,

depois pegar essa solu¸c˜ao e transform´a-la em ponto de partida da formula¸c˜ao estendida,

assim, esta come¸caria com bons cortes e um limite inferior bem melhor. Logo, juntando

as 2 propostas acima acredita-se que os tempos computacionais reduziriam.

ALVARENGA, A. V. et al. Classiﬁcation of breast tumours on ultrasound images using

morphometric parameters. In: Proc. IEEE International Workshop on Intelligent Signal

Processing. [S.l.: s.n.], 2005. p. 206–210.

BALAS, E.; FISCHETTI, M.; PULLEYBLANK, W. R. The precedence-constrained

asymmetric traveling salesman polytope. Mathematical Programming, v. 68, p. 241–265,

1995.

BEASLEY, J. Route ﬁrst-cluster second methods for vehicle routing. Omega, v. 11, p.

403–408, 1983.

BELFIORE, P. P.; Y.YOSHIZAKI, H. T. Scatter Search para Problemas de Roteiriza¸c˜ao

de Ve´ıculos com Frota Heterogˆenea, Janelas de Tempo e Entregas Fracionadas. Tese

(Doutorado) — Universidade de S˜ao Paulo, 2006.

BENT, R.; HENTENRYCK, P. V. A two-stage hybrid algorithm for pickup and delivery

vehicle routing problems with time windows. Comput. Oper. Res., Elsevier Science Ltd.,

Oxford, UK, UK, v. 33, n. 4, p. 875–893, 2006. ISSN 0305-0548.

BERALDI, P. et al. Eﬃcient neighborhood search for the probabilistic pickup and

delivery travelling salesman problem. Networks, v. 45, p. 195 – 198, 2005.

BERBEGLIA, G. et al. Static pickup and delivery problems: a classiﬁcation scheme and

survey. Spanish Society of Statistics and Operations Research, v. 15, p. 32–44, 2007.

BERGVINSDOTTIR, K. B. The genetic algorithm for solving the dial-a-ride problem.

Disserta¸c˜ao (Mestrado) — Technical University of Denmark, 2004.

aYSY, O.; GENDREAU, M.; DULLAERT, W. Evolutionary algorithms for the

vehicle routing problem with time windows. Journal of Heuristics, v. 11, p. 587–611,

2004.

CAMPOS, V.; MOTA, E. Heuristic procedures for the capacitated vehicle routing

problem. Comput. Optim. Appl., Kluwer Academic Publishers, Norwell, MA, USA, v. 16,

n. 3, p. 265–277, 2000. ISSN 0926-6003.

CARICATO, P. et al. Parallel tabu search for a pickup and delivery problem under

track contention. Parallel Comput., Elsevier Science Publishers B. V., Amsterdam, The

Netherlands, The Netherlands, v. 29, n. 5, p. 631–639, 2003. ISSN 0167-8191.

CARRABS, F.; CORDEAU, J.-F.; LAPORTE, G. Variable neighborhood search

for the pickup and delivery traveling salesman problem with LIFO loading.

INFORMS Journal on Computing, v. 19, n. 4, p. 618–632, 2007. Dispon´ıvel em:

<http://joc.journal.informs.org/cgi/content/short/19/4/618>.

Referˆencias 60

CHIN, A. J.; KIT, H. W.; LIM, A. A new ga approach for the vehicle routing problem.

In: ICTAI ’99: Proceedings of the 11th IEEE International Conference on Tools with

Artiﬁcial Intelligence. Washington, DC, USA: IEEE Computer Society, 1999. p. 307.

ISBN 0-7695-0456-6.

CHOI, E.; TCHA, D.-W. A column generation approach to the heterogeneous ﬂeet

vehicle routing problem. Comput. Oper. Res., Elsevier Science Ltd., Oxford, UK, UK,

v. 34, n. 7, p. 2080–2095, 2007. ISSN 0305-0548.

CORDEAU, J. F. A branch-and-cut algorithm for the dial-a-ride problem. Operations

Research, v. 54(6), p. 573–586, 2006.

CORDEAU, J.-F.; LAPORTE, G. The dial-a-ride problem (darp): Variants, modeling

issues and algorithms. 4OR, v. 1, p. 89–101, 2003.

CORDEAU, J. F.; LAPORTE, G. A tabu search heuristic for the static multi-vehicle

dial-a-ride problem. Transportation Research, Part B: Methodological 37(6), p. 579–594,

2003.

DANTZIG, G. B.; RAMSER, J. H. The truck dispatching problem. Ma-

nagement Science, v. 6, n. 1, p. 80–91, Outubro 1959. Dispon´ıvel em:

<http://mansci.journal.informs.org/cgi/content/abstract/6/1/80>.

DIAS, A. d. C.; LIMA, F. R. F. de. A importˆancia dos estudos sobre infra-estrutura e

log´ıstica. An´alise Conjuntural, v. 30, p. 15–16, 2008.

DUMAS, Y.; DESROSIERS, J.; SOUMIS, F. The pickup and delivery problem with

time windows. European Journal of Operational Research, v. 54, n. 1, p. 7–22, September

1991. Dispon´ıvel em: <http://ideas.repec.org/a/eee/ejores/v54y1991i1p7-22.html>.

DUMITRESCU, I. et al. The travelling salesman problem with pickup and delivery:

Polyhedral results and a branch-and-cut algorithm. Mathematical Programming, Ser. A,

p. 37, 2008.

ERDOGAN, G.; CORDEAU, J.-F.; LAPORTE, G. The pickup and delivery traveling

salesman problem with ﬁrst-in-ﬁrst-out loading. Comput. Oper. Res., Elsevier Science

Ltd., Oxford, UK, UK, v. 36, n. 6, p. 1800–1808, 2009. ISSN 0305-0548.

FAN, J.; WANG, X.; CHEN, Q. A heuristic algorithm for multiple depots vehicle

routing problem with backhauls. In: FSKD ’07: Proceedings of the Fourth International

Conference on Fuzzy Systems and Knowledge Discovery (FSKD 2007) Vol.3. Washington,

DC, USA: IEEE Computer Society, 2007. p. 421–425. ISBN 0-7695-2874-0.

GELOGULLARI, C. A. An exact algorithm for the vehicle routing problem with

backhauls. Computers and Operations Research, v. 33, p. 595–619, 2004.

GENDREAU, M.; LAPORTE, G.; VIGO, D. Heuristics for the traveling salesman

problem with pickup and delivery. Comput. Oper. Res., Elsevier Science Ltd., Oxford,

UK, UK, v. 26, n. 7, p. 699–714, 1999. ISSN 0305-0548.

GHAZIRI, H.; OSMAN, I. H. A neural network algorithm for the traveling salesman

problem with backhauls. Computers and Industrial Engineering, v. 44(2), p. 267–281,

2003.

Referˆencias 61

GOETSCHALCKX, M.; JACOBS-BLECHA, C. The vehicle routing problem with

backhauls: Properties and solution algorithms. [S.l.], 1993.

HERN

ANDEZ-P

EREZ, H.; GONZ

ALEZ, J. J. S. A branch-and-cut algorithm for a tra-

veling salesman problem with pickup and delivery. Discrete Applied Mathematics, v. 145,

n. 1, p. 126–139, 2004. Dispon´ıvel em: <http://dx.doi.org/10.1016/j.dam.2003.09.013>.

HO, S. C.; GENDREAU, M. Path relinking for the vehicle routing

problem. Journal of Heuristics, v. 12, p. 55–72, 2006. Dispon´ıvel em:

<http://www.springerlink.com/content/5075744n65023367/>.

LAU, H. C.; LIANG, Z. Pickup and delivery with time windows: Algorithms and test

case generation. IEEE Computer Society, Washington, DC, USA, p. 333, 2001.

LI, H.; LIM, A. A metaheuristic for the pickup and deli-

very problem with time windows. p. 160, 2001. Dispon´ıvel em:

<http://computer.org/proceedings/ictai/1417/14170160abs.htm>.

LIM, H.; LIM, A.; RODRIGUES, B. Solving the Pick up and Delivery Problem with

Time Windows using “Squeaky Wheel” Optimization with Local Search. [S.l.], 2002.

LOUREN¸cO, H. R.; MARTIN, O.; ST

uTZLE, T. Handbook of metaheuristics. In:

. [S.l.]: Kluwer Academic Publishers, 2003. cap. Iterated Local Search, p. 251–285.

LU, Q.; DESSOUKY, M. M. A new insertion-based construction heuristic for solving the

pickup and delivery problem with hard time windows. European Journal of Operational

Research, v. 175, p. 672–687, 2006.

MATHEMATICS, S. A. Department of optimisation, technical report in progress. Em

processo.

MIN, H. The multiple vehicle routing problem with simultaneous delivery and pickup

points. Transportation Research-A, v. 23, p. 377–86, 1989.

MONTAN´e, F. A. T.; FERREIRA, V. J. M. F.; GALV˜aO, R. D. Determina¸c˜ao de rotas

para empresa de entrega expressa. Pesquisa Operacional, v. 17, p. 107–135, 1997.

MONTAN´e, F. A. T.; GALV˜aO, R. D. A tabu search algorithm for the vehicle routing

problem with simultaneous pick-up and delivery service. Computers and Operations

Research, v. 33(3), p. 595–619., 2006.

MONTEMANNI, R. et al. A new algorithm for a Dynamic Vehicle Routing Problem

based on Ant Colony System. [S.l.]: Istituto Dalle Molle Di Studi Sull Intelligenza

Artiﬁciale, 2002.

MOSHEIOV, G. The travelling salesman problem with pick-up and delivery. European

Journal of Operational Research, v. 79, n. 2, p. 299–310, December 1994. Dispon´ıvel em:

<http://ideas.repec.org/a/eee/ejores/v79y1994i2p299-310.html>.

MOSHEIOV, G. Vehicle routing with pick-up and delivery: Tour-partition heuristics.

Computer and Industrial Engineering, v. 34(3), p. 669–684, 1998.

Referˆencias 62

NANRY, W. P.; BARNES, W. J. Solving the pickup and delivery problem with time

windows using reactive tabu search. Transportation Research, Part B: Methodological

34(2), p. 107–121, 2000.

OMBUKI, B.; ROSS, B. J.; HANSHAR, F. Multi-objective genetic algorithms for vehicle

routing problem with time windows. Applied Intelligence, Kluwer Academic Publishers,

Hingham, MA, USA, v. 24, n. 1, p. 17–30, 2006. ISSN 0924-669X.

PANKRATZ, G. A grouping genetic algorithm for the pickup and delivery problem with

time windows. OR Spectrum, v. 27(1), p. 21–41, 2005.

PARRAGH, S. N.; DOERNER, K. F.; HARTL, R. F. Part i: Transportation between

customers and depot. Journal f

ur Betriebswirtschaft, v. 51, p. 21–51, 2008.

PARRAGH, S. N.; DOERNER, K. F.; HARTL, R. F. Part ii: Transportation between

pickup and delivery locations. Journal f

ur Betriebswirtschaft, v. 51, p. 81–117, 2008.

POTVIN, J.-Y.; DUHAMEL, C.; GUERTIN, F. A genetic algorithm for vehicle routing

with backhauling. Applied Intelligence, v. 6(4), p. 345–355, 1996.

PRIV´e, J. et al. Solving a vehicle routing problem arising in soft drink distribution.

Journal of the Operational Research Society, v. 57, p. 1045–1052, 2006.

PSARAFIS, H. A dyanmic programming solution to the single vehicle many-to-many

immediate request dial-a-ride problem. Transportation Science, v. 14, p. 130–154, 1980.

REIMANN, M.; DOERNER, K.; HARTL, R. F. Insertion based ants for vehicle routing

problems with backhauls and time windows. In: ANTS ’02: Proceedings of the Third

International Workshop on Ant Algorithms. London, UK: Springer-Verlag, 2002. p.

135–148. ISBN 3-540-44146-8.

RENAUD, J.; BOCTOR, F. F.; LAPORTE, G. Perturbation heuristics for the pickup

and delivery traveling salesman problem. Computers & OR, v. 29, n. 9, p. 1129–1141,

2002. Dispon´ıvel em: <http://dx.doi.org/10.1016/S0305-0548(00)00109-X>.

ROPKE, S. Branch-and-Cut-and-Price for the Pickup and Delivery Problem with Time

Windows. Universitetsparken 1, 2100 Copenhagen, Denmark, Novembro 2007.

ROPKE, S.; PISINGER, D. An adaptive large neighborhood search heuristic for the

pickup and delivery problem with time windows. Transportation Science, INFORMS,

Institute for Operations Research and the Management Sciences (INFORMS), Linthicum,

Maryland, USA, v. 40, n. 4, p. 455–472, 2006. ISSN 1526-5447.

ROPKE, S.; PISINGER, D. A uniﬁed heuristic for a large class of vehicle routing problems

with backhauls. European Journal of Operational Research, v. 171, n. 3, p. 750–775, June

2006. Dispon´ıvel em: <http://ideas.repec.org/a/eee/ejores/v171y2006i3p750-775.html>.

ROUSSEAU, L.-M.; GENDREAU, M.; PESANT, G. Using constraint-based operators

to solve the vehicle routing problem with time windows. Journal of Heuristics, Kluwer

Academic Publishers, Hingham, MA, USA, v. 8, n. 1, p. 43–58, 2002. ISSN 1381-1231.

RULAND, K. Polyhedral solution to the pickup and delivery problem. Tese (Doutorado)

— Washington University, St. Louis, MO, 1995.

Referˆencias 63

RULAND, K. S.; RODIN, E. Y. The pickup and delivery problem: Faces and

branch-and-cut algorithm. Computers & Mathematics with Applications, v. 33, p. 1–13,

Junho 1997.

SALHI, S.; NAGY, G. A cluster insertion heuristic for single and multiple depot vehicle

routing problems with backhauling. Journal of the Operational Research Society, v. 50,

p. 1034–42, 1999.

SAVELSBERGH, M.; SOL, M. The general pickup and delivery problem. Transportation

Science, v. 29, p. 17–29, 1995.

SIGURD, M.; PISINGER, D.; SIG, M. The pickup and delivery problem with time

windows and precedences,. Transportation Science, v. 38, p. 197–209, 2004.

SOLOMON, M. M. Algorithms for the vehicle routing and scheduling problems with

time window constrains. Massachusetts Institute of Technology, Operations Research

Center, v. 35, p. 254–264, 1987.

uTZLE, T.; HOOS, H. H. Analysing the run-time behaviour of iterated local search

for the travelling salesman problem. In: Third Metaheuristics International Conference.

[S.l.: s.n.], 1999.

TAM, V.; TSENG, L. C. Y. Eﬀective heuristics to solve pickup and delivery problems

with time windows. In: ICTAI ’03: Proceedings of the 15th IEEE International

Conference on Tools with Artiﬁcial Intelligence. Washington, DC, USA: IEEE Computer

Society, 2003. p. 184. ISBN 0-7695-2038-3.

TETRASOFT, A. Mapbooking algoritm for pickupand de-

livery solutions with time windows and capacity restraints.

Http://www.sintef.no/static/am/opti/projects/top/vrp/benchmarks. 2003.

WILLIAM, P. N.; BARNES, J. W. Solving the pickup and delivery problem with time

windows using tabu search. Transportation Research, v. 34, p. 107–121, 2001.

XU, H. et al. Solving a practical pickup and delivery problem. Transportation Science,

v. 37, p. 347–364, 2003.

Livros Grátis
( http://www.livrosgratis.com.br )
 
Milhares de Livros para Download:
 
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas

Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
 
 