Um Algoritmo GRASP Híbrido para o Problema de Localização Capacitada de Custo Fixo
Autores
|
4361 |
47,1953
|
|
|
4362 |
47,1953
|
Informações:
Publicações do PESC
Apresentamos o desenvolvimento de um algoritmo para o Problema de Localização Capacitada de Custo Fixo (PLC). No PLC a questão central é localizar um conjunto de facilidades (uma ou mais), minimizando o custo global de localizá-las. O algoritmo implementa uma meta-heurística gulosa, o GRASP, para chegar a um conjunto solução de facilidades localizadas e no final, com o objetivo de tentar melhorar a solução, são realizadas trocas entre os elementos do conjunto solução e as facilidades candidatas que não fazem parte da solução final. Avaliamos duas estratégias GRASP, usando Alfa Fixo e Alfa Variado. Esta última estratégia, a denominamos de GRASP Adaptativo (o mesmo que reativo). Para testar os resultados foi utilizada a biblioteca de problemas teste do PCL a OR-Library, onde obtivemos resultados que se com GAP em média abaixo de 0,5% da solução ótima.
In this work a hybrid algorithm for the Fixed Cost Capacitated Location Problem (FCCLP), whose objective is to locate a number of capacitated facilities that cover the total demand of the customers in a geographical region. We use a hybrid algorithm based on the transportation problem and a meta-heuristic GRASP to encompass the solution, in order to identify a solution set for the facilities on addition, exchanges among facilities belonging to the solution set and others non candidate solution are made in the search for the final solution. We evaluate two strategies of GRASP, using fixed alpha and a range of alpha (reactive GRASP). To evaluate the results the OR-Library was used for the instances of the FCCLP, where as result we found an average gap from the optimum solution below 0,5% using our method.