General information
Latest issue
Impact factor
Guidelines for authors
Submit a manuscript

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Avtomat. i Telemekh.:

Personal entry:
Save password
Forgotten password?

Avtomat. i Telemekh., 2014, Issue 4, Pages 106–119 (Mi at7535)  

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

Two-level programming problems

Fast metaheuristics for the discrete $(r|p)$-centroid problem

I. A. Davydovab, Yu. A. Kochetovab, N. Mladenovicc, D. Urosevicc

a Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia
c Mathematical Institute of the Serbian Academy of Sciences and Arts, Belgrade, Serbia

Abstract: Two players, the leader and his competitor, open facilities, striving to capture the largest market share. The leader opens $p$ facilities, then the follower opens $r$ facilities. Each client chooses the nearest facility as his supplier. We need to choose $p$ facilities of the leader in such a way as to maximize his market share. This problem can be represented as a bilevel programming problem. Based on this representation, in this work we propose two numerical approaches: local search with variable neighborhoods and stochastic tabu search. We pay the most attention to improving the methods' efficiency at no loss to the quality of the resulting solutions. Results of numerical experiments support the possibility to quickly find an exact solution for the problem and solutions with small error.

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

English version:
Automation and Remote Control, 2014, 75:4, 677–687

Bibliographic databases:

Presented by the member of Editorial Board: . . 

Received: 14.11.2013

Citation: I. A. Davydov, Yu. A. Kochetov, N. Mladenovic, D. Urosevic, “Fast metaheuristics for the discrete $(r|p)$-centroid problem”, Avtomat. i Telemekh., 2014, no. 4, 106–119; Autom. Remote Control, 75:4 (2014), 677–687

Citation in format AMSBIB
\by I.~A.~Davydov, Yu.~A.~Kochetov, N.~Mladenovic, D.~Urosevic
\paper Fast metaheuristics for the discrete $(r|p)$-centroid problem
\jour Avtomat. i Telemekh.
\yr 2014
\issue 4
\pages 106--119
\jour Autom. Remote Control
\yr 2014
\vol 75
\issue 4
\pages 677--687

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. 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
    2. I. A. Davydov, P. A. Kononova, Yu. A. Kochetov, “Local search with exponential neighborhood for the servers load balancing problem”, J. Appl. Industr. Math., 9:1 (2015), 27–35  mathnet  crossref  mathscinet
    3. Yu. A. Kochetov, A. A. Panin, A. V. Plyasunov, “Comparison of metaheuristics for the bilevel facility location and mill pricing problem”, J. Appl. Industr. Math., 9:3 (2015), 392–401  mathnet  crossref  crossref  mathscinet  elib
    4. Yu. A. Kochetov, A. V. Khmelev, “Hybrid local search for the heterogenous fixed fleet vehicle routing problem”, J. Appl. Industr. Math., 9:4 (2015), 503–518  mathnet  crossref  crossref  mathscinet  elib
    5. S. M. Lavlinskii, A. A. Panin, A. V. Plyasunov, “A bilevel planning model for public-private partnership”, Autom. Remote Control, 76:11 (2015), 1976–1987  mathnet  crossref  isi  elib  elib
    6. B. Biesinger, B. Hu, G. Raidl, “A hybrid genetic algorithm with solution archive for the discrete -centroid problem”, J. Heuristics, 21:3 (2015), 391–431  crossref  zmath  isi  elib  scopus
    7. Yu. Kochetov, I. Sokolova, S. Amirgaliyeva, Zh. Amirgaliyeva, “Alternating heuristic and exact method for the leader-follower facility location and design problem”, 2015 Twelve International Conference on Electronics Computer and Computation (Icecco), eds. S. Guvercin, M. Zhaparov, A. Sagandykova, IEEE, 2015, 87–89  isi
    8. A. Karakitsiou, “Discrete competitive facility location: modeling and optimization approaches”, Optimization, Control, and Applications in the Information Age: in Honor of Panos M. Pardalos'S 60Th Birthday, Springer Proceedings in Mathematics & Statistics, 130, ed. A. Migdalas, A. Karakitsiou, Springer, 2015, 153–169  crossref  mathscinet  zmath  isi  scopus
    9. Y. Zhang, L. V. Snyder, T. K. Ralphs, Zh. Xue, “The competitive facility location problem under disruption risks”, Transp. Res. Pt. e-Logist. Transp. Rev., 93 (2016), 453–473  crossref  isi  scopus
    10. Yu. Kochetov, E. Alekseeva, M. Mezmaz, “Local search heuristic for the discrete leader-follower problem with multiple follower objectives”, Proceedings of the 2nd International Conference “Numerical Computations: Theory and Algorithms”, NUMTA 2016 (Pizzo Calabro, Italy, 19–25 June 2016), AIP Conf. Proc., 1776, eds. Y. Sergeyev, D. Kvasov, F. DellAccio, M. Mukhametzhanov, Amer. Inst. Phys., 2016, 050007  crossref  mathscinet  isi  scopus
    11. V. Beresnev, A. Melnikov, “Facility location in unfair competition”, Discrete Optimization and Operations Research, Lecture Notes in Computer Science, 9869, ed. Y. Kochetov, M. Khachay, V. Beresnev, E. Nurminski, P. Pardalos, Springer Int Publishing Ag, 2016, 325–335  crossref  mathscinet  zmath  isi  scopus
    12. I. Davydov, M. Coupechoux, S. Iellamo, “Tabu search approach for the bi-level competitive base station location problem”, Discrete Optimization and Operations Research, Lecture Notes in Computer Science, 9869, eds. Y. Kochetov, M. Khachay, V. Beresnev, E. Nurminski, P. Pardalos, Springer Int Publishing Ag, 2016, 364–372  crossref  mathscinet  zmath  isi  scopus
    13. A. Karakitsiou, A. Migdalas, “Locating facilities in a competitive environment”, Optim. Lett., 11:5 (2017), 929–945  crossref  mathscinet  zmath  isi  scopus
    14. G. G. Zabudskii, T. I. Keiner, “Optimal placement of rectangles on a plane with fixed objects”, Autom. Remote Control, 78:9 (2017), 1651–1661  mathnet  crossref  isi  elib
    15. N. Aras, H. Kucukaydin, “Bilevel models on the competitive facility location problem”, Spatial Interaction Models: Facility Location Using Game Theory, Springer Optimization and Its Applications, 118, eds. L. Mallozzi, E. Amato, P. Pardalos, Springer, 2017, 1–19  crossref  mathscinet  zmath  isi  scopus
    16. E. Alekseeva, Yu. Kochetov, E.-G. Talbi, “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
    17. A. Konak, S. Kulturel-Konak, L. Snyder, “A multi-objective approach to the competitive facility location problem”, International Conference on Computational Science (ICCS 2017), Procedia Computer Science, 108, eds. P. Koumoutsakos, M. Lees, V. Krzhizhanovskaya, J. Dongarra, P. Sloot, Elsevier Science BV, 2017, 1434–1442  crossref  isi  scopus
    18. T. H. Seyhan, V L. Snyder, Y. Zhang, “A new heuristic formulation for a competitive maximal covering location problem”, Transp. Sci., 52:5 (2018), 1156–1173  crossref  isi  scopus
    19. Santos-Penate D.R., Campos-Rodriguez C.M., Moreno-Perez J.A., “The Generalized Discrete (R Vertical Bar P)-Centroid Problem”, Int. Trans. Oper. Res., 26:1 (2019), 340–363  crossref  isi  scopus
    20. A. V. Kononov, A. A. Panin, A. V. Plyasunov, “A bilevel competitive location and pricing model with nonuniform split of demand”, J. Appl. Industr. Math., 13:3 (2019), 500–510  mathnet  crossref  crossref
  • Avtomatika i Telemekhanika
    Number of views:
    This page:245
    Full text:40
    First page:25

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