Discrete Location Problems 
Benchmarks Library
Discrete Location Problems
| The (r|p)-centroid problem |
Instances with uniform distribution
|
In the competitive p-median problem, two decision makers, the leader and the follower, compete to attract clients from a given market. The leader opens his facilities, anticipating that the follower will react to the decision by opening own facilities. The leader and the follower try to maximize their own profits.
First, the leader opens p facilities. Later on, the follower opens r facilities. Each client chooses the closest open facility. We need to find p facilities for the leader to maximize his profit.
Mathematical model as a linear 0–1 bilevel programming problem
Efficient computational methods for this problem are still unknown. The first steps in this direction are made in [1] where a special case r = 1 is studied. The problem is reformulated as a mixed integer linear programming problem and solved by general purpose methods. A partial enumeration approach is suggested in [2] for general case r ≥ 1. The local search heuristics for the problem are studied in [3, 4, 7, 8, 11]. Upper bounds are described in [3, 5, 11]. Polynomially solvable cases and complexity results can be found in [9, 10].
REFERENCES
[1] F. Plastria, L. Vanhaverbeke. Discrete models for competitive location with foresight. Computers and Oper. Res. 2008. V. 35, N. 3. P. 683–700.
[2] C.M.C. Rodriguez, J.A.M. Perez. Multiple voting location problems. European J. Oper. Res. 2008. V. 191, N. 2. P. 437–453.
[3] E. Alekseeva, N. Kochetova. Upper and lower bounds for the competitive p-median problem. Proceedings of Baikal International school-seminar "Optimization methods and there applications". V 1. Mathematical programming, July, 2-8, 2008, Severobaikalsk. P. 563-569. (in Russian)
[4] E. Alekseeva, A. Orlov. Memetic algorithm for the competitive p-median problem. Proceedings of Baikal International school-seminar "Optimization methods and there applications". V 1. Mathematical programming, July, 2-8, 2008, Severobaikalsk. P. 563-569 (in Russian)
[5] Yu. Kochetov, A. Kononov, A. Plyasunov. Competitive facility location models. Computational Mathematics and Mathematical Physics, 2009. V 49, N 6. P. 1037-1054.
[6] S.L. Hakimi. On locating new facilities in a competitive environment. European J. Oper. Res. 1983. V. 12, P. 29–35.
[7] S. Benati, G. Laporte. Tabu search algorithms for the (r | Xp)-medianoid and (r|p)-centroid problems. Location
Science. 1994. V.2, N.2, P. 193-204.[8] J. Bhadury, H.A. Eiselt, J.H. Jaramillo. An alternating heuristic for medianoid and centroid problems in the plane. Computers and Oper. Res. 2003. V. 30. P. 553-565.
[9] H. Noltermeier, J. Spoerhose, H.C. Wirth. Muliple voting location and single voting location on trees. European J. Oper. Res. 2007. V. 181. P. 654-667.
[10] J. Spoerhose, H.C. Wirth. (r,p)-Centroid problems on paths and trees. Tech. Report 441, Inst. Comp. Science, University of Würzburg, 2008.
[11] E. Alekseeva, N. Kochetova, Y. Kochetov, A. Plyasunov. A Hybrid Memetic Algorithm for the Competitive p-Median Problem // Preprints of the 13th IFAC Symposium on Information Control Problems in Manufacturing, Moscow, Russia, June 3 - 5, 2009. P. 1516-1520 (pdf.file 216 Kb)