Algorítimos Genéticos

Algoritmos Genéticos Aplicados ao Problema de

Roteamento de Veículos

Milton Roberto Heinen1 e Fernando Santos Osório1

1Universidade do Vale do Rio dos Sinos (UNISINOS)

Computação Aplicada – PIPCA

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

[e-mail], [e-mail]

Resumo. Este artigo trata do problema de roteamento de veículos, que é uma

tarefa muito importante na maioria dos sistemas de transporte e logística. Embora

o problema de roteamento de veículos ainda não possua uma solução exata

em tempo polinomial, existem algumas soluções em tempo polinomial que podem

aproximar o valor ótimo. Neste artigo serão descritas três heurísticas de

aproximação para este problema: a Heurística de Clark e Wright, a Heurística

de Mole e Jameson e os Algoritmos Genéticos. Diversos experimentos foram realizados

com cada uma das heurísticas, e foram realizas comparações relativas

ao tempo de execução e a qualidade das soluções encontradas.

1. Introdução

O roteamento de veículos é um problema presente na maioria das empresas de transporte,

logística e distribuição. Seu objetivo é determinar, dentre todas as possíveis rotas

alternativas, qual é a que representa o menor custo, ou seja, qual é a solução ótima

[Goldbarg and Luna 2000]. Aparentemente, é fácil descobrir qual a melhor solução, basta

calcular o custo de todas as possíveis combinações e selecionar a que apresentar o menor

custo. Para um pequeno conjunto de locais a serem visitados (nodos), isto é perfeitamente

viável, mas a medida que este conjunto cresce, a solução vai se tornando cada vez mais

difícil do ponto de vista computacional. Isto ocorre porque o número de combinações

possíveis se torna muito grande, fazendo com que o cálculo possa demorar até vários

séculos dependendo do número de nodos.

Em termos de complexidade computacional, os Problemas de Roteamento de Veí-

culos (PRV), assim como a maioria dos problemas combinatoriais, são classicados como

sendo NP-Completos [Cormen et al. 2002], ou seja, a complexidade de tempo é não polinomial.

Até o momento, não foi possível encontrar nenhuma solução de tempo polinomial

para problemas da classe NP-Completo, assim sendo, atualmente não existe nenhuma solu

ção