The Applications Of Meta-heuristic Algorithms In Discrete Location

This paper mainly discusses the applications of meta-heuristic algorithms in facility location field.Firstly, we introduce the background, development and research status of facility location, and some classical facility location problems, including p-midian problem, p-center problem, set covering problem. Two competitive facility location problems are also presented. One is the maximal market capture model and the other is the preemptive capture location model. The competitive facility location problem is not only a typical facility location problem, but also a common optimization problem in real lives, which mainly consider two or more providers providering congeneric products or service, or the provider providering multi-products or services. Many facility location problems including competitive facility location problems are NP-hard, and therefore for this type of problems it is difficult to find out their optimal solutions. Now, many scholastics are aimed at improving the algorithm according to the characteristics of the models so that an efficient solution can be obtained. There are plenty of algorithms solving facility location problems, and in this paper we simply discuss several kinds of metaheuristic algorithms, which include tabu search, simulated annealing, genetic algorithm and ant colony optimization etc.Secondly, we consider three facility location models in this paper. The first one is the maximal market capture model with the constraint of total budget cost. We discuss the influences of the distance and the scale of facility to the policymakers. Meanwhile, a hybrid method of maximin ant colony algorithm and tabu search is proposed for this model. The second model is p-median problem with p uncertain where the construting cost of facilities are considered and a new formula for the cost is used. This paper proposes a heuristic, a tabu search algorithm and a genetic algorithm for solving this model. The third model is the classic p-median problem and a new variable neighborhood search algorithm is proposed which uses the nested neighborhood transform ideas in the neighborhood search and a cobweb search in finding out a local optimal solution.