The Facility Location Problem under Demand Uncertainty

The facility location problem is one of the well-studied combinatorial optimization problems, and a number of algorithms which could find the optimal solution efficiently have been proposed. The facility location problem which considers the parametrjc analysis on demands has been studied, and this problem can handle the demand uncertainty to some extent. This paper deals with the facility location problem in which the customer's demands are given by the probability distribution functions. This model can provide more realistic information than the parametric analysis.Firstly, the facility location problem under demand uncertainty is formulated as a mixed integer programming problem. The objective function to be minimized is the expected value of the total cost. To prevent the algorithm from finding such solutions that are very unlikely to satisfy the demand, a constraint is imposed so as to satisfy the total demand with more than a given probability. A branch-and-bound algorithm is proposed to find the exact solution. To find the optimal solution efficiently, a procedure for calculating the lower bound is presented. Moreover, to strengthen the lower bound, the Lagrangean relaxation is applied for the constraints on demand. Lastly, to illustrate the efficiency of the proposed method, the computational experience is given.