Discrete Location Problems  Benchmarks Library

---

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.

We are given a set I = {1, … , m} of facilities and a set J = {1, …, n} of clients. A matrix (g_ij) defines the distances between clients and facilities. If client j is serviced from a facility, he gives a profit w_j > 0.

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 client j by the follower:

Note that we consider conservative clients. 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)
	xiÎ{0,1},  iÎI,	(3)
where  zj*(x),  jÎJ   is the optimal solution of the follower problem:
		(4)
		(5)
		(6)
	yi + xi £ 1,  iÎI,	(7)
	yi, zj Î{0,1},  iÎI, jÎJ.	(8)

The objective function (1) defines the total profit of the leader. Equation (2) guarantees that the leader  opens exactly p facilities. The objective function (4) defines the total profit of the follower.  Equation (5) guarantees that the follower opens exactly r facilities. Constraint (6) determines the values of z by the decision variables y of 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 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 | X_p)-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, 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

 

Home Benchmarks Library