Probabilistic formulations of some facility location problems in discrete space

TR Number



Journal Title

Journal ISSN

Volume Title


Virginia Tech


The first formulation to be examined is a probabilistic version of the set covering problem. The problem can be stated as follows: determine the locations of the minimum number of facilities among a discrete set of feasible location sites in order to assure that the probability each customer is covered by some facility is no less than a specified value. The second problem treated involves the location of a given number of facilities among a discrete set of feasible location sites in order to maximize the minimum probability that a customer is covered by some facility. This problem is a probabilistic formulation of a special case of the discrete space, minimax location problem known as the p-center problem. Thus, the first and second problems can be considered to be complementary problems.

Frequently, several measures of overall system effectiveness must be considered simultaneously. This is particularly the case in many public sector location problems. Thus, the third problem treated in the dissertation considers the case in which several objectives are to be optimized collectively. The problem is formulated as a goal programming problem in which the objectives are ranked ordinally.

The problems discussed above are formulated probabilistically under the assumption of a discrete solution space. This approach was taken in order to account explicitly for the random variation inherent in the systems of inte~est. Example problems are employed throughout the research to assist in the explanation of each formulation. The emphasis in the research is placed upon a sound formulation of each problem, reduction of the problem to an equivalent but computationally more efficient formulation, and the application of an appropriate procedure in solving each problem. Sensitivity analyses are conducted in order to provide further insight into the specific cause-effect relationships.



facility layout