Research On Fast Algorithms For Some Continuous Facility Location Models

Facility location problem is one of classical problems in the operational research, which is widelyused in the field of economic, management and transportation. The single-source facility locationproblem and multi-source facility location problem have been the hot topics of the facility locationproblem.The most common algorithms for the single-source facility location problem and multi-sourcefacility location problem are Weiszfeld algorithm and Cooper-Weiszfeld algorithm. In this paper, twonew algorithms called Weiszfeld-Newton algorithm and Cooper-Weiszfeld-Newton algorithm whichhave the characteristics of convergence and faster convergence rate are proposed for these twoproblems; Also, generalize the single-source facility location problem to be a generalizedsingle-source facility location problem. The details of this paper are as follows: The introductionpresents the background and current situation of the subject research. Chapter2introduces threecontinuous facility location problems: single-source facility location problem, multi-source facilitylocation problem and generalized single-source facility location problem. Five basic algorithmsinvolving in this paper are given in chapter3. They are Weiszfeld algorithm, improved Weiszfeldalgorithm, Newton algorithm, the Nearest Center Reclassification algorithm and Projection andContraction algorithm.In chapter4, because of limitations of the Weiszfeld algorithm in terms of global convergenceand convergence rate, a new algorithm combining the improved Weiszfeld algorithm and Newtonalgorithm, called Weiszfeld-Newton algorithm is proposed which can converge faster meanwhile has aglobal convergence. The new algorithm is superior to some other algorithms according to thenumerical experiments.The classical algorithm for multi-source facility location problem which is non-convex andNP-hard is Cooper-Weiszfeld algorithm (alternative location-allocation algorithm). Chapter5proposes a Cooper-Weiszfeld-Newton algorithm to solve multi-source facility location problem byusing Weiszfeld-Newton algorithm in the location phase. The numerical experiments demonstrate theavailability of the new algorithm in this chapter. Meanwhile, the improvement on theCooper-Weiszfeld-Newton algorithm, choosing the the optimal point of last iterate as the currentinitial iterate, can accelerate the convergence of Cooper-Weiszfeld-Newton algorithm greatly.Chapter6generalizes the single-source facility location problem via introducing asymmetricgauge to be the generalized single-source facility location problem, which is actually a non-convexoptimization problem. The differences between the generalized model and the classical single-sourcefacility location model are:1) distance measure gauge is asymmetric;2) the generalized model is constrained. The major difficulty for solving the generalized model is caused by confirming a crossingpoint on the boundary line which minimizes the distance between demand point and new facility ondifferent side of the boundary line. In this chapter, the generalized single-source facility locationproblem is transformed to the formulation of linear variational inequalities instead of looking for thecrossing point directly and solved by Projection and Contraction algorithm.Finally, summarize the whole paper and point out some possible research direction in the future.