Research On The Location Of Facilities With Bandwidth Limitations

Facility location problem is a kind of optimization problem that is widely studied and used in Internet,distributed computing and data mining.Generally,facility location problem is to select a number of objects from a collection of objects to serve other objects as facility,and the goal is to minimize the cost of service.In this paper,the facility location problem studied is the combination of traditional facility location problem and network flow problem,each edge in the graph contains bandwidth limitation,so that the process of transmit flow from facility point to customer point is limited by the bandwidth of edge,which is called Bandwidth Limited Facility Location problem.In this paper,the following research is carried out:When facility set is determined,Bandwidth Limited Facility Location problem is converted into minimum cost flow problem.As it's slow to solve the minimum cost flow problem,the approximate minimum cost flow algorithm,called parallel cost flow algorithm,is proposed.Parallel cost flow algorithm improves a dozens of times than traditional minimum cost flow algorithm,while the cost is quite close to minimal cost.In addition,in this paper,aiming at the neighborhood search of the current facility set,the algorithms for adding facility and removing facilities are proposed respectively.To the current the current facility set,the facility addition algorithm is based on increasing its maximum flow as well as the contribution of facility point;the facility removal algorithm is based on an estimate of the added cost after removing each facility point.The facility addition algorithm and facility removal algorithm are used as heuristic information combined with genetic algorithm and simulated annealing algorithm,which greatly improves the performance of these two heuristic algorithms.In addition,this paper presents the idea of generalized customer point,which considers the facility point as a customer point and transmits flow between the facility points,so that the feasible cost flow of neighborhood can be gotten via that of current facility set,and the feasibility of generalized customer point is proved.Based on this,a fast algorithm of calculating neighborhood's minimum cost flow through current facility set's one is given by proof.Then a heuristic algorithm based on the idea of generalized customer point is proposed.Experiments show that Generalized Customer Heuristic Algorithm can get a solution that is more approximate to the optimal solution if the calculation time is more comfortable.According to this algorithm,this paper implements a system solving bandwidth limited facility location problem.As the facility location problem is inputted,this system can preprocess and calculate the problem,and finally gives a facility deployment plan.