THE MULTI–FACILITY LOCATION PROBLEM: A PROBABILISTIC DECOMPOSITION METHOD
Abstract: A generalized Weiszfeld method is proposed for the multi–facility location problem. The problem is relaxed using probabilistic assignments, and is decomposed into single facility location problems, that are coupled by these assignments, and can be solved in parallel. The probabilistic assignments are updated at each iteration, using the distances to the current centers. The method thus iterates between assignments and centers updates, with the probabilistic assignments gradually approaching the pure assignments to the computed centers. The method also provides intrinsic criteria for the quality of the solution, and for the optimal number of facilities to serve the given customers. A duality theorem allows verifying the optimality of the cluster centers by solving a dual problem. Numerical experience with several problems from the literature is presented.
Keywords: Facility location; clustering; Fermat–Weber problem; multi–facility location problem; Weiszfeld method; contour approximation; duality; Luce choice axiom; Kullback–Leibler divergence.
Category 1: Applications -- OR and Management Sciences (Other )
Entry Submitted: 08/03/2012
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|