The p-median problem under uncertainty

Consider the need to currently locate p facilities but it is possible that up to q additional facilities will have to be located in the future. There are known probabilities that 0 ⩽ r ⩽ q facilities will need to be located. The p-median problem under uncertainty is to find the location of p facilities such that the expected value of the objective function in the future is minimized. The problem is formulated on a graph, properties of it are proven, an integer programming formulation is constructed, and heuristic algorithms are suggested for its solution. The heuristic algorithms are modified to reduce the run time by about two orders of magnitude with minimal effect on the quality of the solution. Optimal solutions for many problems are found effectively by CPLEX. Computational results using the heuristic algorithms are presented.