Utilização de Algoritmos Genéticos para Resolução de Problemas de Localização de Concentradores

Resumo

Redes hub-and-spoke são amplamente utilizadas nas áreas de transporte e comunicações, onde estão envolvidos fluxos de pessoas ou informações. São compostas por diversos pontos origem-destino, com demandas e custos de transporte associados a eles. O problema de localização de concentradores (hub location) é uma extensão relativamente nova dos clássicos problemas de localização de instalações [2]. Concentradores (hubs) são pontos que funcionam como consolidação ou troca de informações, pessoas ou objetos entre os pontos de origem e os destinos estipulados. O objetivo é encontrar os melhores pontos para tais instalações de forma a minimizar o custo operacional total, dado pela soma entre o custo de instalação dos hubs e o custo de transporte entre os nós hub e os nós não-hub. Existem várias formulações para o problema de localização de concentradores. O objetivo deste trabalho é apresentar um algoritmo genético para resolver o problema do p-hub capacitado com alocação única [4]. Nesta formulação considera-se que cada hub tem uma capacidade e que cada nó não-hub deve estar associado a apenas um hub. Além disso, a quantidade p de hubs é escolhida pelo usuário. Um Algoritmo Genético (AG) é uma técnica evolucionária, isto é, utiliza analogias aos processos deevolução dos seres vivos para gerar e melhorar soluções para um determi- nado problema [3]. O AG é um método iterativo e adaptativo de busca global, com boa capacidade para fugir de ótimos locais. Trabalha com uma população de indivı́duos, onde cada indivı́duo representa uma possı́vel solução para o problema e, a cada iteração, gera uma nova população através de operações genéticas com cruzamento, mutação e seleção natural, buscando gerar filhos melhores que as soluções-pai. Cada indivı́duo é avaliado conforme uma função de aptidão (fitness), que mede a qualidade da solução que este in- divı́duo representa, e os que têm melhor fitness têm mais chances de serem passados para a próxima população. O método é probabilı́stico, de forma que os indivı́duos melhores avaliados tenham maior probabilidade tanto de serem submetidos às operações genéticas quanto de sobreviverem para a próxima população [3]. O algoritmo apresentado neste trabalho foi implementado em linguagem de programação JAVA versão 6 e IDE Eclipse. Para os experimentos foram utilizadas instâncias.[...]