IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v52y2018i5p1156-1173.html
   My bibliography  Save this article

A New Heuristic Formulation for a Competitive Maximal Covering Location Problem

Author

Listed:
  • Tolga H. Seyhan

    (Amazon.com, Seattle, Washington 98109)

  • Lawrence V. Snyder

    (Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, Pennsylvania 18015)

  • Ying Zhang

    (Zhejiang Cainiao Supply Chain Management Co., Ltd., Hangzhou 311122, China)

Abstract

We consider a competitive facility location problem in which two firms engage in a leader–follower game. Both firms would like to maximize the customer demand that they capture. Given the other player’s decision, each player’s problem is the classical maximal covering location problem. That is, the leader has to solve a bi-level problem in which the second-level problem is NP-hard. To overcome this, we use the greedy add algorithm as an approximation for the follower’s response and formulate a mixed-integer programming model that embeds the follower’s heuristic response into the leader’s constraints and solve it as a single-level problem. The resulting formulation is tractable and provides near-optimal solutions for the leader’s decision. We analyze the performance of the heuristic both theoretically and computationally. We also provide alternate formulations for the same problem and compare them.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:ortrsc:v:52:y:2018:i:5:p:1156-1173
    DOI: 10.1287/trsc.2017.0769
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/trsc.2017.0769
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2017.0769?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
    ---><---

    References listed on IDEAS

    as
    1. Hakimi, S. Louis, 1983. "On locating new facilities in a competitive environment," European Journal of Operational Research, Elsevier, vol. 12(1), pages 29-35, January.
    2. Alfred A. Kuehn & Michael J. Hamburger, 1963. "A Heuristic Program for Locating Warehouses," Management Science, INFORMS, vol. 9(4), pages 643-666, July.
    3. D Serra & S Ratick & C ReVelle, 1996. "The Maximum Capture Problem with Uncertainty," Environment and Planning B, , vol. 23(1), pages 49-59, February.
    4. Benoît Colson & Patrice Marcotte & Gilles Savard, 2007. "An overview of bilevel optimization," Annals of Operations Research, Springer, vol. 153(1), pages 235-256, September.
    5. Richard Church & Charles R. Velle, 1974. "The Maximal Covering Location Problem," Papers in Regional Science, Wiley Blackwell, vol. 32(1), pages 101-118, January.
    6. Jonathan F. Bard & James T. Moore, 1992. "An algorithm for the discrete bilevel programming problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(3), pages 419-435, April.
    7. Nimrod Megiddo, 1981. "The Maximum Coverage Location Problem," Discussion Papers 490, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    8. Gerard Cornuejols & Marshall L. Fisher & George L. Nemhauser, 1977. "Exceptional Paper--Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms," Management Science, INFORMS, vol. 23(8), pages 789-810, April.
    9. Kress, Dominik & Pesch, Erwin, 2012. "Sequential competitive location on networks," European Journal of Operational Research, Elsevier, vol. 217(3), pages 483-499.
    10. CORNUEJOLS, Gérard & FISHER, Marshall L. & NEMHAUSER, George L., 1977. "Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms," LIDAM Reprints CORE 292, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    11. James T. Moore & Jonathan F. Bard, 1990. "The Mixed Integer Linear Bilevel Programming Problem," Operations Research, INFORMS, vol. 38(5), pages 911-921, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Fu, Chenyi & Ma, Shoufeng & Zhu, Ning & He, Qiao-Chu & Yang, Hai, 2022. "Bike-sharing inventory management for market expansion," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 28-54.

    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. 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.
    2. 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.
    3. 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.
    4. Ortiz-Astorquiza, Camilo & Contreras, Ivan & Laporte, Gilbert, 2018. "Multi-level facility location problems," European Journal of Operational Research, Elsevier, vol. 267(3), pages 791-805.
    5. Klaus Büdenbender & Tore Grünert & Hans-Jürgen Sebastian, 2000. "A Hybrid Tabu Search/Branch-and-Bound Algorithm for the Direct Flight Network Design Problem," Transportation Science, INFORMS, vol. 34(4), pages 364-380, November.
    6. Camilo Ortiz-Astorquiza & Ivan Contreras & Gilbert Laporte, 2019. "An Exact Algorithm for Multilevel Uncapacitated Facility Location," Transportation Science, INFORMS, vol. 53(4), pages 1085-1106, July.
    7. Pierre Hansen & Jack Brimberg & Dragan Urošević & Nenad Mladenović, 2007. "Primal-Dual Variable Neighborhood Search for the Simple Plant-Location Problem," INFORMS Journal on Computing, INFORMS, vol. 19(4), pages 552-564, November.
    8. Michael Brusco & Douglas Steinley, 2015. "Affinity Propagation and Uncapacitated Facility Location Problems," Journal of Classification, Springer;The Classification Society, vol. 32(3), pages 443-480, October.
    9. Sharma, R.R.K. & Berry, V., 2007. "Developing new formulations and relaxations of single stage capacitated warehouse location problem (SSCWLP): Empirical investigation for assessing relative strengths and computational effort," European Journal of Operational Research, Elsevier, vol. 177(2), pages 803-812, March.
    10. 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.
    11. Camilo Ortiz-Astorquiza & Ivan Contreras & Gilbert Laporte, 2017. "Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 767-779, November.
    12. Drexl, Andreas & Klose, Andreas, 2001. "Facility location models for distribution system design," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 546, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    13. Mladenovic, Nenad & Brimberg, Jack & Hansen, Pierre & Moreno-Perez, Jose A., 2007. "The p-median problem: A survey of metaheuristic approaches," European Journal of Operational Research, Elsevier, vol. 179(3), pages 927-939, June.
    14. Martha-Selene Casas-Ramírez & José-Fernando Camacho-Vallejo & Juan A. Díaz & Dolores E. Luna, 2020. "A bi-level maximal covering location problem," Operational Research, Springer, vol. 20(2), pages 827-855, June.
    15. Jesica Armas & Angel A. Juan & Joan M. Marquès & João Pedro Pedroso, 2017. "Solving the deterministic and stochastic uncapacitated facility location problem: from a heuristic to a simheuristic," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(10), pages 1161-1176, October.
    16. Daniel Serra & Charles Revelle, 1992. "The PQ-Median problem: Location and districting of hierarchical facilities. Part II: Heuristic solution methods," Economics Working Papers 13, Department of Economics and Business, Universitat Pompeu Fabra.
    17. 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.
    18. Michael Brusco & Hans-Friedrich Köhn, 2009. "Exemplar-Based Clustering via Simulated Annealing," Psychometrika, Springer;The Psychometric Society, vol. 74(3), pages 457-475, September.
    19. Klose, Andreas & Drexl, Andreas, 2005. "Facility location models for distribution system design," European Journal of Operational Research, Elsevier, vol. 162(1), pages 4-29, April.
    20. Sergei Pashko & Anton Molyboha & Michael Zabarankin & Sergei Gorovyy, 2008. "Optimal sensor placement for underwater threat detection," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(7), pages 684-699, October.

    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:inm:ortrsc:v:52:y:2018:i:5:p:1156-1173. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.