General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Diskretn. Anal. Issled. Oper.:

Personal entry:
Save password
Forgotten password?

Diskretn. Anal. Issled. Oper., 2010, Volume 17, Number 6, Pages 3–19 (Mi da627)  

This article is cited in 14 scientific papers (total in 14 papers)

Approximation algorithms for the competitive facility location problem

V. L. Beresnevab, A. A. Melnikovb

a S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia

Abstract: 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.

Full text: PDF file (297 kB)
References: PDF file   HTML file

Bibliographic databases:
UDC: 519.725
Received: 10.05.2010

Citation: V. L. Beresnev, A. A. Melnikov, “Approximation algorithms for the competitive facility location problem”, Diskretn. Anal. Issled. Oper., 17:6 (2010), 3–19

Citation in format AMSBIB
\by V.~L.~Beresnev, A.~A.~Melnikov
\paper Approximation algorithms for the competitive facility location problem
\jour Diskretn. Anal. Issled. Oper.
\yr 2010
\vol 17
\issue 6
\pages 3--19

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. V. L. Beresnev, E. N. Goncharov, A. A. Mel'nikov, “Local search over generalized neighborhood for an optimization problem of pseudo-Boolean functions”, J. Appl. Industr. Math., 6:1 (2012), 22–30  mathnet  crossref  mathscinet  zmath
    2. V. L. Beresnev, “Local search algorithms for the problem of competitive location of enterprises”, Autom. Remote Control, 73:3 (2012), 425–439  mathnet  crossref  isi
    3. Beresnev V., “Branch-and-Bound Algorithm for a Competitive Facility Location Problem”, Comput. Oper. Res., 40:8 (2013), 2062–2070  crossref  mathscinet  zmath  isi  elib  scopus
    4. V. L. Beresnev, A. A. Melnikov, “Branch-and-bound method for the competitive facility location problem with prescribed choice of suppliers”, J. Appl. Industr. Math., 8:2 (2014), 177–189  mathnet  crossref  mathscinet
    5. V. L. Beresnev, “On the competitive facility location problem with a free choice of suppliers”, Autom. Remote Control, 75:4 (2014), 668–676  mathnet  crossref  isi
    6. A. A. Panin, M. G. Pashchenko, A. V. Plyasunov, “Bilevel competitive facility location and pricing problems”, Autom. Remote Control, 75:4 (2014), 715–727  mathnet  crossref  isi
    7. A. A. Mel'nikov, “Computational complexity of the discrete competitive facility location problem”, J. Appl. Industr. Math., 8:4 (2014), 557–567  mathnet  crossref  mathscinet
    8. V. L. Beresnev, A. A. Melnikov, “A capacitated competitive facility location problem”, J. Appl. Industr. Math., 10:1 (2016), 61–68  mathnet  crossref  crossref  mathscinet  elib
    9. S. V. Ivanov, M. V. Morozova, “Stochastic problem of competitive location of facilities with quantile criterion”, Autom. Remote Control, 77:3 (2016), 451–461  mathnet  crossref  isi  elib
    10. Alekseeva E., Kochetov Yu., Talbi E.-G., “A Matheuristic For the Discrete Bilevel Problem With Multiple Objectives At the Lower Level”, Int. Trans. Oper. Res., 24:5 (2017), 959–981  crossref  mathscinet  zmath  isi  scopus
    11. Karakitsiou A., Migdalas A., “Locating Facilities in a Competitive Environment”, Optim. Lett., 11:5 (2017), 929–945  crossref  mathscinet  zmath  isi  scopus
    12. Aras N., Kucukaydin H., “Bilevel Models on the Competitive Facility Location Problem”, Spatial Interaction Models: Facility Location Using Game Theory, Springer Optimization and Its Applications, 118, eds. Mallozzi L., DAmato E., Pardalos P., Springer, 2017, 1–19  crossref  mathscinet  zmath  isi  scopus
    13. Luan J., Pan K., “Research on Location of Cold Chain Logistics Distribution Center Based on "Internet Plus "”, Proceedings of the 2017 International Conference on Education Science and Economic Management (Icesem 2017), Advances in Social Science Education and Humanities Research, 106, eds. Lin X., Li B., Lamba J., Atlantis Press, 2017, 541–544  isi
    14. Nasiri M.M. Mahmoodian V. Rahbari A. Farahmand Sh., “A Modified Genetic Algorithm For the Capacitated Competitive Facility Location Problem With the Partial Demand Satisfaction”, Comput. Ind. Eng., 124 (2018), 435–448  crossref  isi  scopus
  • Дискретный анализ и исследование операций
    Number of views:
    This page:585
    Full text:130
    First page:6

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020