Heuristic methods for the location problem / Métodos heurísticos para o problema de localização de concentradores

AUTOR(ES)

Wesley Gomes de Almeida

DATA DE PUBLICAÇÃO

2009

RESUMO

O problema de localização de concentradores (hubs) é comumente encontrado em redes de transporte e de telecomunicação. Trata-se de problema de Otimização Combinatória NP-difícil e que ocorre em diversas situações práticas, tais como: no transporte aéreo, nos serviços de entregas postais, nos serviços de atendimento de emergência, no abastecimento de supermercados e de redes de lojas, na localização de antenas de comunicação, dentre muitas outras. A decisão sobre a localização de concentradores e quais os nós da rede serão alocados a cada um destes, depende do número de concentradores necessários, da demanda de cada um dos nós, da capacidade de atendimento dos concentradores, dentre outros fatores. Metaheurísticas têm sido usadas com sucesso para obter soluções em diversos problemas de Otimização Combinatória. No entanto, a construção de algoritmos heurísticos eficientes requer bons mecanismos de intensificação de busca. Neste trabalho estuda-se o problema de localização de concentradores e propõem-se métodos heurísticos que utilizam a busca por agrupamentos, uma técnica de intensificação de busca capaz de identificar as regiões do espaço de busca mais promissoras para a obtenção de boas soluções. São propostos um algoritmo genético (AG) e um algoritmo simulated annealing com lista tabu (SATL). Testes computacionais foram realizados com os algoritmos propostos e com estes algoritmos combinados com a busca por agrupamentos (clustering search). Os testes demonstram que a aplicação da busca por agrupamentos a estes algoritmos permite obter soluções de melhor qualidade e em menor tempo computacional, em relação às soluções obtidas pelos algoritmos AG e SATL isoladamente.

ASSUNTO(S)

algoritmo genético simulated genetic algorithm clustering search tabu list annealing metaheurística problema de localização de concentradores metauristic recozimento simulado busca por agrupamentos hub location problem lista tabu

Documentos Relacionados

• Métodos heurísticos para o problema de localização de concentradores
• Heuristic location-allocation for facilities location problems
• Heurística de localizacão-alocacão para problemas de localizacão de facilidades
• HIBRIDIZAÇÃO DE MÉTODOS EXATOS E HEURÍSTICOS PARA RESOLUÇÃO DE PROBLEMAS DE OTIMIZAÇÃO COMBINA
• Condução de Experimentos Computacionais com Métodos Heurísticos