A Probabilistic Analysis of the Capacitated Facility Location Problem

The solution value $$Z_n^*$$ of a stochastic version of the capacitated facility location problem is studied. It is shown that, for large numbers of customers n, the value of $$\tfrac{1}{n}Z_n^*$$ can be closely approximated by θ, where the constant θ is identified as a function of the parameters of the underlying stochastic model. Furthermore, an extensive probabilistic analysis is performed on the difference $$\tfrac{1}{n}Z_n - \theta$$ that includes an exponential inequality on the tail distribution, a classification of the speed of convergence and a central limit theorem.