Metaheurística para o Problema de Carregamento e Roteamento de Veículos

Olinto César Bassi de AraújoUFSM

Vinícius Amaral ArmentanoUNICAMP

São Carlos, abril de 2009.

Sumário

Apresentação do problema

Busca Tabu para resolução do 3L-CVRP

Variações na definição do problema

Função objetivo

Restrições de carregamento (LIFO)

Resultados preliminares para 3L-VRPTW

Conclusões

Apresentação do problema

• 3L-CVRP

• Rotamento

Cada cliente é servido por exatamente um veículo

O limite da capacidade de peso do veículos deve ser respeitada

Para cada veículo existe um carregamento 3D factível

• Empacotamento 3D

orientação vertical fixa

fragilidade

projeção da área de apoio

múltiplos destinos

Apresentação do problema

Exemplo de empacotamento

30 35 40 45 50 5520

25

30

35

40

45

50

5

10

9

2

11

Depósito

Apresentação do problema

Exemplo de empacotamento e roteamento

Busca Tabu para o 3L-CVRP

Busca Tabu

Gendreau et al. (2006) O algoritmo aceita movimentos que produz soluções infactíveis (excesso

de peso ou excesso de comprimento do carregamento)

Solução inicial : heurística construtiva de Clarke e Wright (1964)

Vizinhança : Troca + Inserção

avalição = (dist. total)+(excesso peso)+(excesso comp.)+f(i,j)

Busca Tabu para o 3L-CVRP

Instância # caixas # v GILM1 GILM2 # v AAcr % d1 % d2

E016-03m 32 5 316,32 316,32 4 304,13 -4,01 -4,01

E016-05m 26 5 350,58 350,58 5 334,96 -4,66 -4,66

E021-04m 37 5 447,73 447,73 5 391,65 -14,32 -14,32

E021-06m 36 6 448,48 448,48 6 447,98 -0,11 -0,11

E022-04g 45 7 464,24 464,24 6 454,14 -2,22 -2,22

E022-06m 40 6 504,46 504,46 6 499,07 -1,08 -1,08

E023-03g 46 6 831,66 831,66 6 865,77 4,10 4,10

E023-05s 43 8 871,77 873,14 6 823,21 -5,90 -6,07

E026-08m 50 8 666,10 676,60 8 645,14 -3,25 -4,88

Tabela 1. Resultados para instâncias de Gendreau et al. (2006) – n 25

Busca Tabu para o 3L-CVRP

Instâncias # caixas # v GILM1 GILM2 # v AAcr % d1 % d2

E030-03g 62 10 911,16 893,61 8 849,33 -7,28 -5,21

E030-04s 58 9 819,36 818,65 8 822,17 0,34 0,43

E031-09h 63 9 651,58 717,74 9 625,92 -4,10 -14,6

E033-03n 61 9 2.928,34 2.816,93 7 2.807,56 -4,30 -0,33

E033-04g 72 11 1.559,64 1.548,41 8 1.494,67 -4,35 -3,60

E033-05s 68 10 1.452,34 1.488,79 8 1.467,70 1,06 -1,44

E036-11h 63 11 707,85 714,37 11 702,70 -0,73 -1,66

E041-14h 79 14 920,87 909,99 14 879,57 -4,70 -3,46

E045-04f 94 14 1.400,52 1.452,02 11 1.316,12 -6,41 -10,3

Tabela 2. Resultados para instâncias de Gendreau et al. (2006) – 25 < n < 50

Busca Tabu para o 3L-CVRP

Tabela 3. Resultados para instâncias de Gendreau et al. (2006) – n 50

Instâncias # caixas # v GILM1 GILM2 # v AAcr % d1 % d2

E051-05e 99 13 871,29 827,99 11 823,48 -5,81 -0,55

E072-04f 147 20 732,12 732,12 17 623,35 -17,45

-17,45

E076-07s 155 18 1.275,20 1.226,20 17 1,168,79 -9,10 -4,91

E076-08s 146 19 1.277,94 1.291,53 19 1,252,62 -2,02 -3,11

E076-10e 150 18 1.258,16 1.271,40 17 1,216,21 -3,45 -4,54

E076-14s 143 18 1.307,09 1.317,86 16 1,193,12 -9,55 -10,45

E101-08e 193 24 1.570,72 1.616,39 22 1,499,02 -4,78 -7,83

E101-10c 199 28 1.847,95 1.839,12 26 1,782,83 -3,65 -3,16

E101-14s 198 25 1.747,52 1.773,50 25 1,675,28 -4,31 -5,86

Busca Tabu para o 3L-CVRP

  # veículos

%d1 %d2  GILM AAcr

Média     -4,52 -4,87

Total 336 306    

Tabela 4. Resumo dos resultados para todos os grupo de instâncias

Variações na definição do problema

Função objetivo

O bin packing problem associado ao CVRP é NP-hard, no entanto, para as instâncias disponíveis não é de difícil resolução;

Para problemas de roteamento de veículos com janela de tempo e/ou restrição de distância, encontrar o número mínimo de veículos não é um cálculo trivial;

Variações na definição do problema

Função objetivo

Nestes casos, geralmente o número de veículos é considerado como um objetivo a ser minimizado e o custo fixo é incorporado à função objetivo.

No 3L-CVRP o cálculo do número mínimo de veículos leva a resolução de um Bin Packing tridimensional com restrições do tipo LIFO para o carregamento das demandas.

Variações na definição do problema

Função objetivo

Bin Packing tridimensional com restrições de múltiplos destinos

demand n

demand 1

?

Variações na definição do problema

Função objetivo

Resultados detalhados para 2L-CVRP divulgados por Fuellerer et al. (2009) utilizam diferentes números de veículos para uma mesma instância.

Variações na definição do problema

20 veículos

Variações na definição do problema

19 veículos

Variações na definição do problema

Instância#v

FDHI AA

07-02 5 4

07-03 5 4

10-02 6 5

11-02 6 5

18-02 8 719-03 11 10

20-04 15 14

20-05 13 12

21-04 14 13

23-04 16 15

27-04 20 19

30-04 30 29

32-05 32 31

33-03 39 38

34-04 49 4835-02 44 43

36-05 42 41

Tabela 5. Resultados para instâncias Iori (2004)

AA reduz 1 bin em 17 instâncias e obtémo mesmo número de binnas demais instâncias

Variações na definição do problema

Função objetivo

Com um número menor de veículos aumenta a dificuldade de encontrar um empacotamento tridimensional factível para as rotas.

Estimar a ocupação dos veículos:

Aprile, Egeblad, Garavelli, Lisi, Pisinger, 2007. Logistics Optimization: Vehicle Routing with Loading Constraints, 19th International Conference on Production Research.

Representação do empacotamento tridimensional Matriz de superfície Graph-theoretical characterization

Variações na definição do problema

Conjunto de instâncias

X

Variações na definição do problema

Restrições de múltiplos destinos

Lin and Yu, 2006. A Heuristic Algorithm for the Three-Dimensional Container Packing Problem with Zero Unloading Cost Constraint,IEEE International Conference on Systems, Man, and Cybernetics October 8-11, 2006, Taipei, Taiwan.

Resultados preliminares para 3L-VRPTW

AM DSC VS

Instâncias # veículos distância # veículos distância # veículos distância

GI/I1-01 9 762,59 8 635,85 8 625,87

GI/I1-02 8 675,24 8 610,96 7 595,78

GI/I1-03 6 1.250,86 6 548,22 6 504,48

GI/I1-04 6 605,72 6 493,03 5 472,85

GI/I1-05 9 1.398,47 7 580,31 6 570,33

GI/I2-01 5 2.668,55 5 572,32 4 731,671

GI/I2-02 5 2.555,26 5 526,13 4 731,631

I/I2-03 5 2.526,11 5 509,87 4 598,299

GI/I2-04 5 1.953,67 5 479,19 5 453,179

GI/I2-05 5 635,96 5 504,79 4 678,582

Tabela 6. Resultados para instancias Moura e Oliveira (2008)

Conclusões

Propor novos modelos para o problema 3L-CVRP

Considerar redução da vizinhança da busca tabu baseada em estimativa do carregamento tridimensional.

Gerar conjuntos de instâncias para o 3L-CVRP e 3L-VRPTW.