RODRIGO [email protected]
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ó[email protected]
Milton Roberto [email protected]
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.