The P-Center Problem under Uncertainty

Document Type: Research Paper


Dept. of Industrial Engineering, Sharif University of Technology, Tehran, Iran


Facility location decisions play a prominent role in strategic planning of many firms, companies and governmental organizations. Since in many real-world facility location problems, the data are subject to uncertainty, in this paper, we consider the P-center problem under uncertainty of demands. Using Bertsimas and Sim approach, we develop a robust model of the problem as an integer programming model. Furthermore, we develop a tabu search algorithm for solving the problem. Finally we use design of experiments (DOE) to adjust the parameters of tabu search algorithm. The numerical results of algorithm are presented accordingly.


Main Subjects

[1] Arostegui M., Kadipasaoglu N., Khumawala M. (2006), An empirical comparison of Tabu Search,
Simulated Annealing, and Genetic Algorithms for facilities location problems; International Journal of
Production Economics103; 742-754.
[2] Ben-Tal A., Nemirovski A. (1998), Robust convex optimization, Math. Operations Research 23; 769-
[3] Bertsimas D., Sim M. (2003), Robust discrete optimization and networkflows;Mathematical
Programming Series B; 98, 49–71.
[4] El-Ghaoui, Lebret H. (1997), Robust solutions to least-square problems to uncertain data matrices;SIAM
Journal on Matrix Analysis and Applications 18; 1035-1064.
[5] Glover F. (1989), Tabu Search Part I;ORSA Journal on Computing 1; 190-206.
[6] Glover, F (1990), Tabu Search Part II;ORSA Journal on Computing 2; 4-32.
[7] Jia H. Fernando, Dessouki G. (2007), A modeling framework for facility location of medical services for
large-scale emergencies;IIE Transactions 39; 41–55.
[8] Soyster A.L. (1973), Convex programming with set-inclusive constraints and applications to inexact
linear programming; Operations Research 21; 1154-1157.