RODRIGO ROMAISr.romais@gmail.com

ALGORITMOS GENÉTICOSAPLICADOS AO PROBLEMA DE ROTEAMENTO DE VEÍCULOS

INTRODUÇÃO A METAHEURÍSTICA

“A utilização e elegância da matemática reside na sua capacidade de explorar as ligações formais entre

problemas aparentemente distintos”.

Richard Parris

Dados do Artigo

Universidade do Vale do Rio dos Sinos (UNISINOS)Computação Aplicada . PIPCA

CEP 93022-000. São Leopoldo - RS - Brasil

Download:http://

revistaseletronicas.pucrs.br/ojs/index.php/hifen/article/viewFile/3781/2893

Fernando Santos Osóriofosorio@unisinos.br

Milton Roberto Heinenmheinen@turing.unisinos.br

1. Introdução2. Algoritmos Genéticos3. Roteamento de Veículos

3.1 Heurísticas de aproximação4. Heurísticas de Clark e Wright

4.1 Heurística de Mole e Jameson4.2 Roteamento Genético

5. Resultados6. Conclusões

Estrutura do Artigo

• Considerado um problema dos mais estudados da otimização combinatória;

• É um problema presente na maioria das empresas de transporte, logística e distribuição;

• Não possui uma solução exata em tempo polinomial.

• É um caso especial do problema do “Caixeiro Viajante”;

Problema de Roteamento de Veículos (PRV)

Problema de Roteamento de Veículos (PRV)

• Calcular todas as propostas de soluções possíveis e escolher a melhor delas, a que apresentar menor custo.

• Dependendo da dimensão do problema, este processo torna-se inviável.

Inicialmente, como tentar resolver um PRV?

Propostas

Apresentar 3 heurísticas para o PRV:

Heurística de Clark e Wright;Heurística de Mole e Jameson;Algoritmos Genéticos.

Em trabalhos anteriores foram abordadas apenas comparações com as heurísticas de Clark e Wright e Mole e Jameson, em específico neste, acrescentado Algoritmos Genéticos para novas comparações de resultados.

Heurística de Clark e Wright

Foi o primeiro algoritmo direcionado para este tipo de problemas.

O Algoritmo apresenta as seguintes características:

Principal Vantagem:Resolve este problema em tempo polinomial, é rápido.

Principal Desvantagem:A partir de um grafo inicial, incrementa apenas os pontos extremos na função objetivo.

Inicialmente construída uma matriz de distâncias:

Em seguida, construídas caminhos iniciais, cada uma deles ligando um dos clientes ao depósito, ondeé o número de nós do grafo.

Calculada a combinação 2 a 2 termos.

Heurística de Clark e Wright

Fundamentação do algoritmo:

Em que: Função custo a ser minimizada; Custo do depósito até a cidade Custo do depósito até a cidade Custo entre as cidades e .

Heurística de Clark e Wright

Heurística de Mole e Jameson

O Algoritmo apresenta as seguintes características:

Principal Vantagem:Reduz a fragilidade do algoritmo anterior, analisa

todos os nós possíveis.

Principal Desvantagem:Aumenta-se a complexidade computacional.

Utiliza os seguintes critérios:

Critério de proximidade:seleciona o nó que está mais próximo da rota atual

Critério de economia:visa selecionar qual o melhor local para se inserir o nó selecionado

Adotado no problema

Heurística de Mole e Jameson

Inicialmente, para cada indivíduo é inicializado com rotas aleatórias, mas que passam apenas uma vez em cada cliente.

Cada indivíduo da população (genoma) é uma lista de inteiros, onde cada elemento desta lista corresponde a um elemento do grafo, ou seja, um cliente que deve ser visitado:

Roteamento Genético

Para a implementação dos Algoritmos Genéticos, foi selecionada a biblioteca de software Galib(Criado por Matthew Wall - MIT), O tipo de Algoritmo Genético utilizado foi o GASteadyStateGA

Roteamento Genético

Todos os experimentos foram realizados na linguagem C++, com processamento de 1.54Ghz, 512 de memória ram, e sistema operacional Linux:

Resultados

Críticas ao ArtigoPontos Positivos:

Linguagem clara e objetiva, texto bem estruturado;O autor consegue transmitir a ideia principal do

artigo;Abordagem o tema é bem atrativa;Título atrativo.

Pontos Negativos:

Não apresenta códigos e/ou pseudocódigo dos algoritmos;

Estrutura não adequada.

Proposta de estrutura:

1. Introdução2. Algoritmos Genéticos3. Problema Modelo: Roteamento de Veículos4. Heurísticas de aproximação

1. Heurísticas de Clark e Wright2. Heurística de Mole e Jameso3. Roteamento Genético

5. Resultados6. Conclusão

Críticas ao Artigo

Referências Clark, G. and Wright, J. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Opns. Res., (12):568.581. Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2002). Algoritmos - Teoria e Prática. Campus, Rio de Janeiro, RJ, Brazil, 2 edition. Darwin, C. (1859). Origin of Species. John Murray, London, UK. De Jong, K. A. (1975). An Analysis of the Bahavior of a Class of Genetic Adaptative Systems. Doctoral thesis, Univ. Michigan, Ann Arbor, MI. Fisher, M. and Jaikumar, R. (1981). The lagrangean relaxation method for solving integer programming problem. Mam. Sci., (27):01.18. Goldbarg, M. C. and Luna, H. P. (2000). Otimização Combinatória e Programação Linear - Modelos e Algoritmos. Campus, Rio de Janeiro, Brazil. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA. Heinen, M. R. (2005). Análise e implementação de algoritmos para o roteamento de veículos. In Anais do IV Simpósio de Informática da Região Centro do RS (SIRC/RS), pages 1.8, Santa Maria, RS, Brazil. UNIFRA Editora. Holland, J. H. (1975). Adaptation in Natural and Articial Systems. Univ. Michigan Press, Ann Arbor, MI. Karp, R. M. (1975). On the computational complexity of combinatorial problems. Neworks, (5):45.68. Mitchell, M. (1996). An Introduction to Genetic Algorithms. MIT Press, Cambridge, MA. Mole, R. H. and Jameson, R. S. (1976). A sequencial routing-building algorithm employing a generalised savings criterion. Opl. Res Q, (27).

Obrigado pela atenção de todos e todas.