Técnicas da Pesquisa Operacional aplicadas a um Problema de Cobertura de Arcos

Abstract

Neste trabalho, é proposta uma metodologia para a obtenção de uma solução otimizada de um problema de cobertura de arcos utilizando algumas técnicas da Pesquisa Operacional. A metodologia aqui apresentada consta de duas fases. Na 1a fase utiliza-se um algoritmo genético aplicado ao problema das p-medianas cuja resposta pode ser melhorada com a heurística clássica de Teitz e Bart. A partir da definição das medianas necessárias para o problema, determina-se os grupos (clusters) de pontos de demanda a serem designados a cada mediana através do algoritmo de Gillett e Johnson Adaptado. Na 2a fase, a partir da definição dos clusters de atendimento, é feito o roteamento em cada cluster para ter-se a seq¨uência de pontos a serem transpassados, utilizando o modelo matemático do Problema Carteiro Chinês. A validação da metodologia foi obtida através da aplicação da mesma a um estudo de caso comparando-se a solução otimizada com a solução adotada por ocasião a coleta de dados.