Study On Continuous Approximation Algorithm For Median Facility Location Discrete Problems

Nowadays,researchers pay much attention to the discreteness of median facility location problems.They find the optimal possibility in a large number of combinations,usually including allocation layer and location layer of the problem.Solving the discrete facility location problems by a continuous method is a less studied direction.In this paper,a continuous approximation algorithm for the discrete facility location problems is proposed.Firstly,location range of the discrete problem is extended to the whole continuous plane,and then the optimal location is obtained through the approximation algorithm.Finally,the discrete solution is returned.Generally,the optimal location of discrete problems is near the one of continuous problems.Because in this way,the total transportation cost can be avoided to increase too much.In this paper,by analyzing the network structure and mathematical model of the K-Median Facility Location Problem(KMFLP)and the Multiple Facilities Weber Location Problem(MFWLP),the framework of continuous approximation algorithm is designed.It is essentially a kind of Extended Cooper Algorithm(ECA),which divides the solution of continuous location problems into two layers.The first layer is allocation optimization,determining which nodes are connected to the same facility.The second layer is location optimization,calculating the best facilities location on continuous plane by differential iterative formula.Compared with other discrete algorithms,ECA can avoid searching for possible combinations of facilities.In order to verify the feasibility of framework,this paper selects three kinds of discrete facility location problem as the test object: Single-Source Capacitated Facility Location Problem(SSCFLP),Uncapacitated Single Allocation Hub Location Problem(USAHLP),and Multi-Level Facility Location Problem(MLFLP).These three problems are similar in structure,from simplest to more complex.ECA needs to pay attention to the facility capacity limits when optimizing SSCFLP,the flow between when optimizing USAHLP,and the multi-layer structure when optimizing MLFLP.Experiments show that ECA can obtain the facility locations of discrete problem on the continuous plane in a relatively short time,and quickly return the discrete solution through the search strategy.Compared with the linear programming solver,the quality of solution obtained by ECA is similar.However,an approximate solution on the continuous plane can point out the areas where the best facility nodes may exist,allowing the decision maker to select facility locations based on the comprehensive consideration of realistic factors.When be used to solve the simplified and approximated discrete models,ECA makes the final solution more flexible and reliable.