New Numerical Methods For Facility Location Based On Alternating Direction Method Of Multipliers

Facility location problem is widely used in our daily life,such as economy,transportation,management,communication,medical treatment and so on.Therefore,researching facility location problem has a profound influence on economic and social development.In this paper we consider Weber problem and multi-facility location problem and generalize it underl_p-norm,then we develop a unified algorithm framework based on alternating direction method of multipliers?ADMM?and a new numerical algorithm for Weber problem and multi-facility location problem under l₁,l₂,l_?-norm.The details of this paper are as follows:The introduction of Chapter 1 presents the background and current situation of the subject research.Chapter 2 introduces three kinds of classic continuous facility location problems:Weber problem?WP?,multi-source Weber problem?MSWP?and multi-facility location problem?MFLP?.Chapter 3 gives ADMM-based iteration and its application when solving linear constrained convex optimization problem with two separable operators.We also give a brief analysis about the convergence of ADMM-based method.In chapter 4,we have a deep research on both Weber problem and Weber problem underl_p-norm and give a unified algorithm framework for Weber problem based on ADMM.We also propose new ADMM-based methods for Weber problem underl₁,l₂,l_?-norm.Weiszfeld algorithm is the well-used numerical method for solving Weber problem,two disadvantages of Weiszfeld algorithm are as follows.Firstly,when the singular case happens,the global convergence of Weiszfeld algorithm is not guaranteed.Secondly,as the steepest descent method,the efficiency of Weiszfeld algorithm is not high enough.The new ADMM-based method for Weber problem can guarantee the global convergence even in singular case and has faster convergence efficiency than Weiszfeld algorithm.The numerical results verify the efficiency of the proposed ADMM-based methods for Weber problem.Chapter 5 uses ADMM to solve multi-facility location problem underl_p-norm.Considering that multi-facility location problem is a convex problem,the separable properties can be fully utilized when ADMM is used to solve this problem.Basing on the single facility in chapter 4,we combine multiple facilities into a quadratic programming problem and solve it.Introducing the variable to get y-subproblem and z-subproblem,y-subproblem and z-subproblem are parallel so that we can solve each subproblem independently.When the iterate happens to coincide with one customer,the ADMM-based methods can guarantee the global convergence and have faster convergence efficiency.The numerical results verify the efficiency of the proposed ADMM-based methods for multi-facility location problem.Finally,we summarize the whole paper and point out some possible research direction in the future.