Apresentações
Algoritmos meméticos para o problema do carteiro rural
Ana Maria Moreira Rodrigues
— ISCAP, INESC Porto
José Soeiro Ferreira
— FEUP, INESC Porto
O Problema do Carteiro Rural (PCR) consiste em determinar o caminho de custo mínimo que atravessa um dado conjunto de arcos de um grafo com a particularidade de apenas uma parte desse conjunto ser de passagem obrigatória. Trata-se de um problema com enorme aplicabilidade. Pode ser encontrado em situações como distribuição de correio, recolha de lixo, remoção de neve e muitas mais. Sendo o PCR um problema de difícil resolução, tem sido abordado recorrendo a heurísticas havendo, no entanto, importantes estudos suportados numa formulação em programação matemática e em algorítmos exactos.
Nesta apresentação será dada a conhecer uma nova abordagem ao PCR através de Algoritmos Meméticos (AM). Em poucas palavras pode dizer-se que os AM são Algoritmos Genéticos aos quais é aplicada pesquisa local com o objectivo de agregar informação proveniente de alguma transmissão cultural.
No final desta comunicação serão dados a conhecer alguns dos resultados computacionais obtidos bem como uma aplicação industrial real interessante que consiste na determinação de caminhos de corte óptimos em operações de corte de componentes.