Algoritmos genéticos e busca tabu aplicados ao problema das p-medianas

Abstract

Resumo: Os problemas de localização de instalações (facility location) possuem várias aplicações como em telecomunicações, distribuição e transporte industrial. Um dos problemas de localização de instalações mais conhecido é o problema das p-medianas (HAKIMI, 1965) e (REVELLE, 1970). Neste trabalho é apresentada uma aplicação do problema das p-medianas capacitado a um problema real. É proposto um algoritmo que otimiza a designação de candidatos ao vestibular para os locais de provas mais próximos de suas residências. Para resolver o problema das p-medianas capacitado são propostas duas heurísticas modernas adaptadas ao problema. A primeira é baseada em um algoritmo genético simples que utiliza os operadores genéticos usuais e um operador heurístico chamado "hipermutação direcionada". A segunda heurística proposta é baseada em busca tabu e usa memória de curto e de longo prazo para controlar a busca. Também utiliza uma estratégia de oscilação e tempo tabu aleatório para tentar evitar a repetição de soluções. As duas heurísticas propostas são utilizadas para resolver o problema real mencionado anteriormente, caracterizado como das p- medianas capacitado. Palavras-chave: localização de instalações, p-medianas, designação, algoritmos genéticos, busca tabu

Abstract: Facility location problems have several applications in telecommunications, distribution and industrial transportation. One of the most well known facility location problems is the p-median problem (HAKIMI, 1965), (REVELLE, 1970). This work presents an application of the capacitated p-median problem to a real- world problem. This work proposes an algorithm that optimizes the designation of candidate students (who have to pass a university admission exam) to exam facilities closer to their residences. In order to solve the capacitated p-median problem we propose two modem heuristics adapted to the problem. The first one is based on a simple genetic algorithm that uses both conventional genetic operators and a new heuristic operator called "directed hipermutatiori\ The second one is based on tabu search and uses both short-term and long-term memory to control the search. It also uses an oscillation strategy and random tabu tenure in an attempt to avoid the generation of repeated Solutions. The two proposed heuristics are used to solve the above-mentioned real-world problem, cast as a capacitated p-median problem