Discrete Location Problems ballred.gif (861 bytes) Benchmarks Library
line.jpg (1129 bytes)

The (r|p)-centroid problem

ballred.gif (861 bytes)  Home Benchmarks Library  

ballred.gif (861 bytes)  Benchmarks

Instances on Euclidean plane

Instances with uniform distribution

 

ballred.gif (861 bytes)  Russian page


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)



 


ballred.gif (861 bytes) Home Benchmarks Library ballred.gif (861 bytes)