» Download Article

Authors
Kochetov, Yuri; Plyasunov, Alexandr; Kochetova, Nina; Alekseeva, Ekaterina

Identifier
10.3182/20090603-3-RU-2001.00254

Index Terms
Heuristic and Metaheuristics; Integer Linear Programming; Discrete Applied Mathematics

Abstract
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. This is the Stackelberg game. We present it as a linear bilevel 0-1 problem. It is known that the problem is NP-hard. We develop a hybrid memetic algorithm for it where the follower problem is solved by commercial software. To obtain an upper bound for this maximization problem, we reformulate the bilevel problem as a single level mixed integer programming problem with exponential number of constraints and variables. Removing some of them, we get the desired upper bound. For finding an appropriate family of constraints and variables, we use metaheuristics again. As a result, we get near optimal solutions for the bilevel problem with a posterior bound for deviation from the global optimum. Computational results for Euclidian test instances are discussed.

References

REFERENCES
E. Alekseeva, N. Kochetova (2008) Upper and lower
bounds for the competitive p-median problem. Pro-
ceedings of XIV Baikal International School{Seminar
Optimization Methods and Their Applications, 1, 563{
569 (in Russian).
E. Alekseeva, A. Orlov (2008) Memetic algorithm for
the competitive p-median problem. Proceedings of
XIV Baikal International School{Seminar Optimization
Methods and Their Applications, 1, 570{576 (in Rus-
sian).
S. Benati, G. Laporte (1994) Tabu search algorithms
for the (rjXp){medianoid and (rjp){centroid problems.
Location Science, 2(4), 193{204.
A. Caprara, P. Toth, M. Fischetti (2000) Algorithms
for the Set Covering Problem. Annals of Operations
Research, 98(1{4), 353{371.
Z. Drenzer, H.A. Eiselt (2004) Consumers in competitve
location models. In: Z. Drenzer, H. Hamacher (Eds.) Fa-
cility Location. Applicatios and Theory, Springer, 151{
178.
E. Goncharov and Y. Kochetov (2002) Probabilistic
tabu search for the unconstrained discrete optimization
problems. Discrete Analysis and Operations Research,
9(2), 13{30 (in Russian).
F. Glover, M. Laguna. Tabu Search. Kluwer Acad. Publ,
Boston, 1997.
S. L. Hakimi (1990) Locations with spatial interactions:
competitive locations and games. In: P. B. Mirchandani,
R. L. Francis (Eds.) Discrete Location Theory. Wiley
& Sons. 439{478.
H. Noltemeier, J. Spoerhase, H.-C. Wirth (2007) Multiple
voting location and single voting location on trees.
European Journal of Operational Research, 181, 654{
667.
Y. Kochetov, A. Kononov, A. Plyasunov (2009) Competi-
tive facility location models. Computational Mathemat-
ics and Mathematical Physics, (in press).
N. Mladenovi¶c, J. Brimberg, P. Hansen and J. Moreno{
Perez (2007) The p-median problem: A survey of meta-
heuristic approaches. European Journal of Operational
Research, 179(3), 927{939.
C. M. C. Rodriguez, J. A. M. Perez (2008) Multiple voting
location problems. European Journal of Operational
Research, 191(2), 437{453.
K. Sastry, D. Goldberg, G. Kendall (2005) Genetic
algorithms. In: E.K. Burke, G. Kendall (Eds.) Search
Methodologies. Introductory Tutorials in Optimization
and Decision Support Techniques. Springer, 97{126.
I. Vasil'ev, K. Klimentova, Y. Kochetov (2009) New lower
bounds for the facility location problem with user pref-
erences. Computational Mathematics and Mathematical
Physics, (in press).