A Scatter Search Algorithm using Biological Evolution Strategies to Solve Multilevel Uncapacitated Facility Location Problem

Multi-Level Uncapacitated Facility Location Problem is a problem branched by Uncapacitated Facility Location Problem consists a set of facility portioned into several level. This problem discusses the placement of a facility to be built and serving customers in order to minimize the total cost of constructions and services. Every customer will be served by exactly one facility in each level. This research studies how to solve Multi-Level Uncapacitated Facility Location Problem using Modified Scatter Search Algorithm. The Modified Scatter Search Algorithm is a modified algorithm from Scatter Search adopted by biological evolution strategies of genetic algorithm which can be classified as evolution algorithm because the individual in this algorithm act as parents who does the reproduce to produce offspring. This algorithm uses references set as the population. The processes which carried out by Modified Scatter Search to solve Multi-Level Uncapacitated Facility Location Problem includes data input, parameter initialization, generate the initial solution, calculate the value of the objective function, create the Reference Set, create the subset of Reference Set, solution combination method, and applying the selection, crossover and mutation to a good individual as a form of modification. To validate its performance, the proposed algorithm is implemented in data using 2 levels of facilities and 3 levels of facilities. The result of running program implemented in two types of data shows that the greater the number of Reference Set, the greater the number of good individuals and the greater the number of iterations, the solution obtained tends to be better with a smaller total cost.