| Summary: | O problema básico da distribuição e/ou recolha de produtos é um problema de Optimização Combinatória que consiste em determinar o conjunto de rotas que partem de um depósito central, cuja localização é conhecida, servem um conjunto de clientes com procuras e localizações pré - definidas, minimizando a distância total percorrida. Este é um problema NP-difícil, para o qual poucos métodos exactos foram desenvolvidos, sendo demasiado demorados e não sendo sequer exequíveis para a generalidade dos problemas de dimensão média. Assim, as abordagens mais comuns e eficientes baseiam-se em métodos heurísticos. Numa classificação superficial podem-se considerar duas classes de métodos heurísticos: os “clássicos” e os “modernos”. Os primeiros incluem, entre outros, os métodos construtivos de rota, os métodos de duas fases e os de melhoramento de rotas. Estes métodos foram basicamente desenvolvidos nos anos 60 e 70, embora continuem a ser utilizados e melhorados. Por outro lado, os métodos “modernos” têm como característica comum o recurso à pesquisa local utilizando técnicas de intensificação e diversificação dessa pesquisa. Entre outras, têm aparecido recentemente heurísticas baseadas em: Simulação de Têmpera; algoritmos Genéticos; Pesquisa Tabu; Algoritmos Difusos e Redes Neuronais. Combinações destas técnicas têm conduzido a algoritmos híbridos e a meta-heurísticas. Neste trabalho é feita a apresentação de um Algoritmo Genético para o Problema de Optimização de Rotas de Veículos. Apresenta-se a sua implementação e um estudo computacional comparativo com duas heurísticas “clássicas” num conjunto de problemas - teste conhecidos da literatura.
|
|---|