Geodesic
Approximation algorithms for the competitive facility location problem
Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 6, pp. 3-19.

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper deals with the competitive facility location problem, where two players, the leader and the follower, sequentially establish their facilities and every consumer chooses one of the established facilities in accordance with his own preference. The problem consists in placing the leader's facilities so as to acquire the maximal profit, taking the follower's facilities placing into account, who seeks to maximize his profit as well. The problem is formulated in terms of bi-level integer programming. The paper offers a method for calculating the upper bound for the leader's maximum profit value. The corresponding algorithm consists in designing the classical maximization facility location problem and finding its optimal solution. Along with the calculation of the upper bound, an initial approximate solution for the problem of competitive facility location is generated. The paper offers local search algorithms for improving the initial approximate solution and gives the results of a computational experiment employing the proposed algorithms. The experiment makes it possible to estimate the precision of the obtained approximate solutions and a comparative evaluation of the quality of the algorithms under examination for designing approximate solutions of the examined problem. Tab. 1, bibliogr. 13.
Keywords: bi-level programming problem, optimal uncooperative solution, upper bound, approximate solution, local search. 
@article{DA_2010_17_6_a0,
     author = {V. L. Beresnev and A. A. Melnikov},
     title = {Approximation algorithms for the competitive facility location problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--19},
     publisher = {mathdoc},
     volume = {17},
     number = {6},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2010_17_6_a0/}
}
TY  - JOUR
AU  - V. L. Beresnev
AU  - A. A. Melnikov
TI  - Approximation algorithms for the competitive facility location problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2010
SP  - 3
EP  - 19
VL  - 17
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2010_17_6_a0/
LA  - ru
ID  - DA_2010_17_6_a0
ER  - 
%0 Journal Article
%A V. L. Beresnev
%A A. A. Melnikov
%T Approximation algorithms for the competitive facility location problem
%J Diskretnyj analiz i issledovanie operacij
%D 2010
%P 3-19
%V 17
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2010_17_6_a0/
%G ru
%F DA_2010_17_6_a0
V. L. Beresnev; A. A. Melnikov. Approximation algorithms for the competitive facility location problem. Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 6, pp. 3-19. http://geodesic.mathdoc.fr/item/DA_2010_17_6_a0/

[1] Beresnev V. L., Diskretnye zadachi razmescheniya i polinomy ot bulevykh peremennykh, Izd-vo In-ta matematiki, Novosibirsk, 2005, 408 pp.

[2] Beresnev V. L., “Verkhnie otsenki dlya tselevykh funktsii diskretnykh zadach konkurentnogo razmescheniya predpriyatii”, Diskret. analiz i issled. operatsii, 15:4 (2008), 3–24 | MR

[3] Campos C., Moreno J. A., “Multiple voting location problems”, Europ. J. Oper. Res., 191:2 (2008), 436–452 | MR

[4] Dempe S., Foundations of bilevel programming, Kluwer Acad. Publ., Dordrecht, 2002, 332 pp. | MR | Zbl

[5] Eiselt H. A., Laporte G., “Sequential location problems”, Europ. J. Oper. Res., 96 (1996), 217–231 | DOI

[6] Mirchandani P. B., Francis R. L. (Eds.), Discrete location theory, John Wiley and sons, New York, 1990, 555 pp. | MR | Zbl

[7] Dobson G., Karmarkar U., “Competitive location on network”, Oper. Res., 35 (1987), 565–574 | DOI | MR | Zbl

[8] Drezner Z., Hamacher H. W. (Eds.), Facility location: applications and theory, Springer-Verl., Berlin, 2002, 457 pp. | MR

[9] Aarts E. H. L., Lensrta J. K. (Eds.), Local search in combinatorial optimization, John Wiley and sons, Chichester, 1997, 512 pp. | MR

[10] Plastria F., “Static competitive facility location: an overview of optimization approaches”, Europ. J. Oper. Res., 129 (2001), 461–470 | DOI | MR | Zbl

[11] Plastria F., Vanhaverbeke L., “Discrete models for competitive location with foresight”, Comput. Oper. Res., 35 (2008), 683–700 | DOI | MR | Zbl

[12] Santos-Penãte D. R., Suárez-Vega R., Dorta-Gonzáles P., “The leader-follower location model”, NETS, 7 (2007), 45–61 | MR | Zbl

[13] Von Stackelberg H., The theory of the market economy, Oxford Univ. Press, Oxford, 1952, 289 pp.