IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v63y2015i3p445-460.html
   My bibliography  Save this article

An exact method for the discrete $$(r|p)$$ ( r | p ) -centroid problem

Author

Listed:
  • Ekaterina Alekseeva
  • Yury Kochetov
  • Alexandr Plyasunov

Abstract

This paper provides a new exact iterative method for the following problem. Two decision makers, a leader and a follower, compete to attract customers from a given market. The leader opens $$p$$ p facilities, anticipating that the follower will react to the decision by opening $$r$$ r facilities. Each customer patronizes the closest opened facility. The goal is to find $$p$$ p facilities for the leader to maximize his market share. It is known that this problem is $$\Sigma ^P_2$$ Σ 2 P -hard and can be presented as an integer linear program with a large number of constraints. Based on this representation, we design the new iterative exact method. A local search algorithm is used at each iteration to find a feasible solution for a system of constraints. Computational results and comparison with other exact methods show that the new method can be considered as one of the alternative approaches among the most advanced exact methods for the problem. Copyright Springer Science+Business Media New York 2015

Suggested Citation

  • Ekaterina Alekseeva & Yury Kochetov & Alexandr Plyasunov, 2015. "An exact method for the discrete $$(r|p)$$ ( r | p ) -centroid problem," Journal of Global Optimization, Springer, vol. 63(3), pages 445-460, November.
    • Handle: RePEc:spr:jglopt:v:63:y:2015:i:3:p:445-460
    DOI: 10.1007/s10898-013-0130-6
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10898-013-0130-6
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10898-013-0130-6?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Saidani, Nasreddine & Chu, Feng & Chen, Haoxun, 2012. "Competitive facility location and design with reactions of competitors already in the market," European Journal of Operational Research, Elsevier, vol. 219(1), pages 9-17.
    2. Resende, Mauricio G.C. & Werneck, Renato F., 2006. "A hybrid multistart heuristic for the uncapacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 174(1), pages 54-68, October.
    3. Nimrod Megiddo, 1981. "The Maximum Coverage Location Problem," Discussion Papers 490, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    4. Hansen, Pierre & Mladenovic, Nenad, 2001. "Variable neighborhood search: Principles and applications," European Journal of Operational Research, Elsevier, vol. 130(3), pages 449-467, May.
    5. Roboredo, Marcos Costa & Pessoa, Artur Alves, 2013. "A branch-and-cut algorithm for the discrete (r∣p)-centroid problem," European Journal of Operational Research, Elsevier, vol. 224(1), pages 101-109.
    6. Kress, Dominik & Pesch, Erwin, 2012. "Sequential competitive location on networks," European Journal of Operational Research, Elsevier, vol. 217(3), pages 483-499.
    7. Küçükaydin, Hande & Aras, Necati & Kuban AltInel, I., 2011. "Competitive facility location problem with attractiveness adjustment of the follower: A bilevel programming model and its solution," European Journal of Operational Research, Elsevier, vol. 208(3), pages 206-220, February.
    8. Noltemeier, H. & Spoerhase, J. & Wirth, H.-C., 2007. "Multiple voting location and single voting location on trees," European Journal of Operational Research, Elsevier, vol. 181(2), pages 654-667, September.
    9. Daniel Serra & Charles Revelle, 1993. "Market capture by two competitors: The pre-emptive location problem," Economics Working Papers 39, Department of Economics and Business, Universitat Pompeu Fabra.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Zhang, Ying & Snyder, Lawrence V. & Ralphs, Ted K. & Xue, Zhaojie, 2016. "The competitive facility location problem under disruption risks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 93(C), pages 453-473.
    2. Eligius M. T. Hendrix, 2016. "On competition in a Stackelberg location-design model with deterministic supplier choice," Annals of Operations Research, Springer, vol. 246(1), pages 19-30, November.
    3. Gentile, José & Alves Pessoa, Artur & Poss, Michael & Costa Roboredo, Marcos, 2018. "Integer programming formulations for three sequential discrete competitive location problems with foresight," European Journal of Operational Research, Elsevier, vol. 265(3), pages 872-881.
    4. Fernández, José & Hendrix, Eligius M.T., 2013. "Recent insights in Huff-like competitive facility location and design," European Journal of Operational Research, Elsevier, vol. 227(3), pages 581-584.
    5. Vladimir Marianov & H. A. Eiselt, 2016. "On agglomeration in competitive location models," Annals of Operations Research, Springer, vol. 246(1), pages 31-55, November.
    6. Xiang Li & Tianyu Zhang & Liang Wang & Hongguang Ma & Xiande Zhao, 2022. "A minimax regret model for the leader–follower facility location problem," Annals of Operations Research, Springer, vol. 309(2), pages 861-882, February.
    7. Boglárka G.-Tóth & Kristóf Kovács, 2016. "Solving a Huff-like Stackelberg location problem on networks," Journal of Global Optimization, Springer, vol. 64(2), pages 233-247, February.
    8. Dolores R. Santos-Peñate & Clara M. Campos-Rodríguez & José A. Moreno-Pérez, 2020. "A Kernel Search Matheuristic to Solve The Discrete Leader-Follower Location Problem," Networks and Spatial Economics, Springer, vol. 20(1), pages 73-98, March.
    9. Eiselt, H.A. & Marianov, Vladimir, 2020. "Maximizing political vote in multiple districts," Socio-Economic Planning Sciences, Elsevier, vol. 72(C).
    10. Tolga H. Seyhan & Lawrence V. Snyder & Ying Zhang, 2018. "A New Heuristic Formulation for a Competitive Maximal Covering Location Problem," Transportation Science, INFORMS, vol. 52(5), pages 1156-1173, October.
    11. Vladimir Marianov & H. A. Eiselt & Armin Lüer-Villagra, 2020. "The Follower Competitive Location Problem with Comparison-Shopping," Networks and Spatial Economics, Springer, vol. 20(2), pages 367-393, June.
    12. Tammy Drezner & Zvi Drezner & Dawit Zerom, 2020. "Facility Dependent Distance Decay in Competitive Location," Networks and Spatial Economics, Springer, vol. 20(4), pages 915-934, December.
    13. Florensa, Carlos & Garcia-Herreros, Pablo & Misra, Pratik & Arslan, Erdem & Mehta, Sanjay & Grossmann, Ignacio E., 2017. "Capacity planning with competitive decision-makers: Trilevel MILP formulation, degeneracy, and solution approaches," European Journal of Operational Research, Elsevier, vol. 262(2), pages 449-463.
    14. Campos Rodríguez, Clara M. & Santos Peñate, Dolores R. & Moreno Pérez, José Andrés, 2013. "Formulación lineal de extensiones del problema de localización competitiva del líder-seguidor/Linear Formulation for Extensions of the Leader-Follower Competitive Location Problem," Estudios de Economia Aplicada, Estudios de Economia Aplicada, vol. 31, pages 255(20)-255, Enero.
    15. Eiselt, H. A. & Laporte, Gilbert, 1997. "Sequential location problems," European Journal of Operational Research, Elsevier, vol. 96(2), pages 217-231, January.
    16. Roboredo, Marcos Costa & Pessoa, Artur Alves, 2013. "A branch-and-cut algorithm for the discrete (r∣p)-centroid problem," European Journal of Operational Research, Elsevier, vol. 224(1), pages 101-109.
    17. Diego Ruiz-Hernández & Javier Elizalde & David Delgado-Gómez, 2017. "Cournot–Stackelberg games in competitive delocation," Annals of Operations Research, Springer, vol. 256(1), pages 149-170, September.
    18. Shamekhi Amiri, A. & Torabi, S. Ali & Ghodsi, R., 2018. "An iterative approach for a bi-level competitive supply chain network design problem under foresight competition and variable coverage," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 99-114.
    19. Kress, Dominik & Pesch, Erwin, 2012. "Sequential competitive location on networks," European Journal of Operational Research, Elsevier, vol. 217(3), pages 483-499.
    20. Ivan Davydov & Yury Kochetov & Alexandr Plyasunov, 2014. "On the complexity of the (r|p)-centroid problem in the plane," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 22(2), pages 614-623, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jglopt:v:63:y:2015:i:3:p:445-460. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.