Some Facility Location Models And Algorithms

In this article, we use some Meta-heuristic algorithms to solve classical facility location problems and their extension problems.Firstly, this article describes the development and current research state of facilities locat-ion, and some of classical facility location problems, including weber problem, set cover pro-blem etc. Location problems are common optimization problems, many of which are NP-hard.There have been many algorithms to solve facility location problems. This article describes s-ome traditional methods and Meta-heuristic algorithms. Traditional methods include Weiszfeld procedure, Branch and Bound algorithm, Lagrangean relaxation algorithm etc. Meta-heuristic a-lgorithms have Variable Neighborhood Search algorithm, genetic algorithm etc.Secondly, an extended k-cardinality tree problem is considered whose edges and vertex a-re both weighted. This extended model unifies vertex-weights and edge-weights problem. We apply a variable neighborhood search method to solve it. We divide neighborhood according to the model characteristics. It chooses the initial solution by greedy algorithm. In the process of changing neighborhood, we use a simple algorithm of the exchange of ideas leaves to si-mplify the algorithm. These greatly improve computational efficiency for solving the extended problem.Thirdly, for the classic p-median model, this paper applies a new variable neighborhood search algorithm which uses the nested neighborhood transform ideas in neighborhood search and a cobweb search in finding out a local optimal solution. The computational results show that the new variable neighborhood search algorithm for solving the median problem is effective.Fourthly, we apply a simple heuristic algorithm, a variable neighborhood search algorithm and an improved genetic algorithm to solve a new p-median problem with unknown p. We apply the probability to select neighborhood in the new variable neighborhood search algorithm and the population improvement strategy, local search strategy and the optimal preservation strategy in the improved genetic algorithm. The computational results show that the improved genetic algorithm for solving the median problem is more effective than the other two algorithms.Finally, we summarize and point out some possible directions of future research.