Portal de Eventos Científicos da UTFPR (EVIN), XXIII Seminário de Iniciação Científica e Tecnológica da UTFPR

Tamanho da fonte: 
Operador de cruzamento baseado em partições aplicado no problema do roteamento de veículos
Elcio Cezario Sanches Junior, Danilo Sipoli Sanches

Última alteração: 2019-02-04

Resumo


OBJETIVO: Desenvolver um método de aplicação do Operador de Cruzamento de Partição 2 sobre o Problema do Roteamento de Veículos Capacitado em um Algoritmo Genético.MÉTODOS: Será desenvolvido o Operador juntamente com um algoritmo genético para utilização do mesmo, com isso seria implementado a proposta de transformação do grafo do Problema do Roteamento de Veículos Capacitado em um grafo que o operador possa realizar a cruzamento, no caso, um Ciclo Hamiltoniano. Para validar o funcionamento será realizado testes de quatro instâncias do problema, onde os resultados serão comparados com o operador Cruzamento de Ordem variando os métodos de população inicial do algoritmo genético. RESULTADOS: Em todos os testes o Operador de Cruzamento de Partição 2 se saiu melhor que o Cruzamento de Ordem, tanto em porcentagem de alcance do ótimo global quanto de porcentagem de convergência dos testes, estando sempre com uma ótima taxa de próximidade. CONCLUSÕES: Pode-se perceber que o Operador de Cruzamento de Partição 2 é funcional sobre o problema, dentro da forma de aplicação proposta, e que seus resultados são bons, assim como é possível considerar o método de aplicação funcional.


Palavras-chave


Problema do Roteamento de Veículos; Algoritmo Genético; Operador de Cruzamento de Partição Generalizado

Texto completo: PDF