Algorithms For Facility Location Models Based On Variational Inequalities

Facility location models are widely used in the field of life, economics, management,transportation and so on. It includes the discrete facility location model, network location modeland continuous facility location model. In this paper, several single-source facility locationproblems and multi-source location problems are investigated and the convergent algorithms areproposed for solving them. The details of this paper are as follows.The introduction of Chapter1presents the background and current situation of research field.Chapter2reviews three facility location problems: single-source facility location problem,multi-source facility location problem and multi-source facility location problem with interaction.Chapter3considers a generalized variation of Weber problem (GVWP) on the plane in whicha straight line divides the plane into two regions and different gauges are employed to measure thedistance among different regions. The differences between GVWP and facility location problem,mainly include:1) both the unconstrained and constrained problems are taken into considerationin GVWP;2) the more general distance measuring function, gauges, are employed instead of theusually used lp-norms to measure distances in GVWP. In this chapter, GVWP is divided into threesubproblems which are optimally solved as follows: two subproblems are first reformulated intomonotone linear variational inequalities (LVIs) and then a projection-contraction (PC) method isadopted to solve these LVIs; the third subproblem is further divided into some convexsubproblems and the golden section search is used to solve these convex subproblems. Bydividing the GVWP to three subproblems and solving these subproblems optimally, an algorithmwhich can obtain the optimal solution of GVWP is proposed. Preliminary numerical results arereported to verify the proposed algorithm.Chapter4considers the locations of multiple facilities with the regional customers, with theaim of minimizing the sum of weighted distances between facilities and regional customers, wherethe proximity between a facility and a regional customer is evaluated by the closest distance.Locational constraints are imposed to the facilities of our problem. In addition, the gauge isemployed in this paper instead of the frequently-used norms for measuring both the symmetric andasymmetric distances. In the spirit of Cooper algorithm, a new location-allocation heuristicalgorithm is proposed to solve this problem. In the location phase, the single-source subproblemwith regional demands is reformulated into an equivalent linear variational inequality (LVI) andthen a projection-contraction (PC) method is adopted to find the optimal locations of facilitieswhereas in the allocation phase, the regional customers are allocated to facilities according to thenearest center reclassification (NCR). The convergence of the proposed algorithm is proved under mild assumptions. Some preliminary numerical results are reported to show the effectiveness ofthe new algorithm.A constrained multi-source model is built in chapter5, considering the locational constraintson facilities and the transportation costs between facilities (interaction). The objective of the paperis to locate new facilities in some constrained areas such that the sum of the distances betweenfacilities and customers and the distance between these facilities is minimized. A variationalinequality alternative location-allocation heuristic algorithm is proposed to solve this constrainedlocation model: in the allocation phase, all customers are allocated to facilities by the nearestcenter reclassification algorithm; in the location phase, the subproblem is transformed into anequivalent linear variational inequality problem, then a projection-contraction method is adoptedto solve this LVI problem. Several properties about the proposed model and algorithm areanalyzed, and some preliminary numerical results are reported which verifies the effectiveness ofthis algorithm.Chapter6investigates the phenomenon of degeneracy in the multi-source facility locationproblem. The phenomenon relates to the existence of solutions in which one or more facilities areout of use, i.e., no demands(or customers) are allocated to these facilities. Three algorithms:greedy demand algorithm, greedy cluster algorithm and the mixed algorithm are proposed to solvethe phenomenon of degeneracy in the multi-source facility location problem. Numerical resultsverify the effectiveness of the algorithms.Finally, we summarize the whole paper and point out some possible research direction in thefuture.