Loading...
Publication
Estudo computacional de um algoritmo genético para o problema de optimização de rotas de veículos
Authors
Advisor(s)
Abstract(s)
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.
Description
Keywords
Optimização de Rotas de Veículos Métodos Heurísticos Algoritmos Genéticos
Citation
Schutz, G.; Pires, F. M.; Ruano, A. E. Estudo computacional de um algoritmo genético para o problema de optimização de rotas de veículos, Trabalho apresentado em 8º Congresso da APDIO, In 8º Congresso da APDIO, Faro, 1998.