Discrete Location Problems Benchmarks Library

The competitive
-median
problemp |

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

pfacilities. Later on, the follower opensrfacilities. Each client chooses the closest open facility. We need to findpfacilities for the leader to maximize his profit.We are given a set

I= {1, … ,m} of facilities and a setJ= {1, …,n} of clients. A matrix (g) defines the distances between clients and facilities. If client_{ij}jis serviced from a facility, he gives a profitw> 0._{j}Let us present this Stackelberg game as a linear 0–1 bilevel programming problem. Define the decision variables:

For a given solution

x, we can define the set of facilities which allow to capture clientjby the follower:

Note that we consider

conservativeclients. If a client has the same distances to the closest leader and the closest follower facilities, he prefers the leader facility. So, the follower never opens a facility at a site where the leader has opened a facility.Now the model can be written as a linear 0–1 bilevel programming problem:

(1)

s.t

(2)

xÎ{0,1},_{i}iÎI,(3)

where

z_{j}^{*}(x),jÎJis the optimal solution of the follower problem:

(4)

(5)

(6)

y_{i}_{ }+x_{i}_{ }£ 1,iÎI,(7)

y,_{i}zÎ{0,1},_{j}iÎI,jÎJ.(8)

The objective function (1) defines the total profit of the leader. Equation (2) guarantees that the leader opens exactly

pfacilities. The objective function (4) defines the total profit of the follower. Equation (5) guarantees that the follower opens exactlyrfacilities. Constraint (6) determines the values ofzby the decision variablesyof the follower. Constraint (7) admits to open a facility by at most one decision maker. Note that the sum of the leader and the follower profits is a constant. So, we deal with the (r|p)–centroid problem [6] which is - complete.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 caser³ 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|X)-medianoid and (_{p}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, Yu. Kochetov, A. Plyasunov. A hybrid memetic algorithm for the competitive

p-median problem. Proc. of XIII IFAC Symposium on Information Control Problems in Manufacturing (INCOM '09). Moscow. 2009. pdf.file 143 Kb