Hybrid Ant Colony Algorithm For Facility Location Problem

The general form of facility location problem is to select a number of location points from a location set to establish the facility in order to service the corresponding demand.The solution goal is to satisfy all the requirements while minimizing the service cost.In this paper,discrete facility location problem are researched,including uncapacitated facility location problem,capacitated facility location problem,p-median problem,and so on.This kind of facility location problem is a classical combinatorial optimization problem.It belongs to NP-hard and has wide application in Internet,distributed computing,data mining,logistics transportation and operational planning.So,it has important practical significance for researching discrete facility location problem and the algorithms of solving this kind of facility location problem.This paper briefly introduces the development and research status of facility location problem,and presents four basic mathematical models for the discrete facility location problem.Furthermore,according to the classification of algorithms for solving facility location problem,divided into three categories: approximate algorithm,precise algorithm and intelligent optimization algorithm,several common related algorithms are presented.The basic principle,basic flow and main characteristics of basic ant colony algorithm are briefly described.When solving large scale discrete facility location problem by basic ant colony algorithm,there are two defects,slow convergence rate and local optimum.In order to improve the performance of basic ant colony algorithm in solving large scale discrete facility location problem,three methods are proposed.In this paper,uncapacitated facility location problem model is introduced,and its characteristics are analyzed,and the basic characteristics of its optimal solution are obtained.Then,two local search strategies are designed for uncapacitated facility location problem.Finally,combining basic ant colony algorithm and two local search strategies,a hybrid ant colony algorithm is proposed for the uncapacitated facility location problem.The investment constraint is introduced into the classical constrained p-median problem,and the constrained p-median problem with investment is proposed,which makes the model more suitable for facility location problem in transportation and logistics.Based on the analysis of the mathematical model of the p-median problem with investment constraints,a local search strategy is proposed for the problem.Combining basic ant colony algorithm,the local search strategy and lagrangian heuristic algorithm,a lagrangian hybrid ant colony algorithm is designed to solve the problem.