IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v224y2013i3p477-485.html
   My bibliography  Save this article

New variations of the maximum coverage facility location problem

Author

Listed:
  • Bhattacharya, Bhaswar B.
  • Nandy, Subhas C.

Abstract

Consider a competitive facility location scenario where, given a set U of n users and a set F of m facilities in the plane, the objective is to place a new facility in an appropriate place such that the number of users served by the new facility is maximized. Here users and facilities are considered as points in the plane, and each user takes service from its nearest facility, where the distance between a pair of points is measured in either L1 or L2 or L∞ metric. This problem is also known as the maximum coverage (MaxCov) problem. In this paper, we will consider the k-MaxCov problem, where the objective is to place k (⩾1) new facilities such that the total number of users served by these k new facilities is maximized. We begin by proposing an O(nlogn) time algorithm for the k-MaxCov problem, when the existing facilities are all located on a single straight line and the new facilities are also restricted to lie on the same line. We then study the 2-MaxCov problem in the plane, and propose an O(n2) time and space algorithm in the L1 and L∞ metrics. In the L2 metric, we solve the 2-MaxCov problem in the plane in O(n3logn) time and O(n2logn) space. Finally, we consider the 2-Farthest-MaxCov problem, where a user is served by its farthest facility, and propose an algorithm that runs in O(nlogn) time, in all the three metrics.

Suggested Citation

  • Bhattacharya, Bhaswar B. & Nandy, Subhas C., 2013. "New variations of the maximum coverage facility location problem," European Journal of Operational Research, Elsevier, vol. 224(3), pages 477-485.
    • Handle: RePEc:eee:ejores:v:224:y:2013:i:3:p:477-485
    DOI: 10.1016/j.ejor.2012.08.009
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221712006091
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2012.08.009?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. Abellanas, Manuel & López, M Dolores & Rodrigo, Javier, 2010. "Searching for equilibrium positions in a game of political competition with restrictions," European Journal of Operational Research, Elsevier, vol. 201(3), pages 892-896, March.
    2. Plastria, Frank, 2001. "Static competitive facility location: An overview of optimisation approaches," European Journal of Operational Research, Elsevier, vol. 129(3), pages 461-470, March.
    3. H. A. Eiselt & Gilbert Laporte & Jacques-François Thisse, 1993. "Competitive Location Models: A Framework and Bibliography," Transportation Science, INFORMS, vol. 27(1), pages 44-54, February.
    4. Abellanas, Manuel & Lillo, Isabel & Lopez, M Dolores & Rodrigo, Javier, 2006. "Electoral strategies in a dynamical democratic system. Geometric models," European Journal of Operational Research, Elsevier, vol. 175(2), pages 870-878, December.
    5. Qian Wang & Rajan Batta & Christopher Rump, 2002. "Algorithms for a Facility Location Problem with Stochastic Customer Demand and Immobile Servers," Annals of Operations Research, Springer, vol. 111(1), pages 17-34, March.
    6. Eiselt, H. A. & Laporte, G., 1989. "Competitive spatial models," European Journal of Operational Research, Elsevier, vol. 39(3), pages 231-242, April.
    7. Cabello, S. & Díaz-Báñez, J.M. & Langerman, S. & Seara, C. & Ventura, I., 2010. "Facility location problems in the plane based on reverse nearest neighbor queries," European Journal of Operational Research, Elsevier, vol. 202(1), pages 99-106, April.
    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. Ross, Anthony & Khajehnezhad, Milad & Otieno, Wilkistar & Aydas, Osman, 2017. "Integrated location-inventory modelling under forward and reverse product flows in the used merchandise retail sector: A multi-echelon formulation," European Journal of Operational Research, Elsevier, vol. 259(2), pages 664-676.

    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. Díaz-Báñez, J.M. & Heredia, M. & Pelegrín, B. & Pérez-Lantero, P. & Ventura, I., 2011. "Finding all pure strategy Nash equilibria in a planar location game," European Journal of Operational Research, Elsevier, vol. 214(1), pages 91-98, October.
    2. Cabello, S. & Díaz-Báñez, J.M. & Langerman, S. & Seara, C. & Ventura, I., 2010. "Facility location problems in the plane based on reverse nearest neighbor queries," European Journal of Operational Research, Elsevier, vol. 202(1), pages 99-106, April.
    3. Haase, Knut & Hoppe, Mirko, 2008. "Standortplanung unter Wettbewerb - Teil 1: Grundlagen," Discussion Papers 2/2008, Technische Universität Dresden, "Friedrich List" Faculty of Transport and Traffic Sciences, Institute of Transport and Economics.
    4. Aritra Banik & Bhaswar B. Bhattacharya & Sandip Das, 2013. "Optimal strategies for the one-round discrete Voronoi game on a line," Journal of Combinatorial Optimization, Springer, vol. 26(4), pages 655-669, November.
    5. Wenxuan Shan & Qianqian Yan & Chao Chen & Mengjie Zhang & Baozhen Yao & Xuemei Fu, 2019. "Optimization of competitive facility location for chain stores," Annals of Operations Research, Springer, vol. 273(1), pages 187-205, February.
    6. Rafael Suárez‐Vega & Dolores R. Santos‐Peñate & Pablo Dorta‐González, 2004. "Competitive Multifacility Location on Networks: the (r∣Xp)‐Medianoid Problem," Journal of Regional Science, Wiley Blackwell, vol. 44(3), pages 569-588, August.
    7. Kress, Dominik & Pesch, Erwin, 2012. "Sequential competitive location on networks," European Journal of Operational Research, Elsevier, vol. 217(3), pages 483-499.
    8. 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.
    9. Avella, P. & Benati, S. & Canovas Martinez, L. & Dalby, K. & Di Girolamo, D. & Dimitrijevic, B. & Ghiani, G. & Giannikos, I. & Guttmann, N. & Hultberg, T. H. & Fliege, J. & Marin, A. & Munoz Marquez, , 1998. "Some personal views on the current state and the future of locational analysis," European Journal of Operational Research, Elsevier, vol. 104(2), pages 269-287, January.
    10. 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.
    11. Buechel, Berno & Roehl, Nils, 2015. "Robust equilibria in location games," European Journal of Operational Research, Elsevier, vol. 240(2), pages 505-517.
    12. Rhim, Hosun & Ho, Teck H. & Karmarkar, Uday S., 2003. "Competitive location, production, and market selection," European Journal of Operational Research, Elsevier, vol. 149(1), pages 211-228, August.
    13. Fernandez, Jose & Pelegri'n, Blas & Plastria, Frank & Toth, Boglarka, 2007. "Solving a Huff-like competitive location and design model for profit maximization in the plane," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1274-1287, June.
    14. Konur, Dinçer & Geunes, Joseph, 2012. "Competitive multi-facility location games with non-identical firms and convex traffic congestion costs," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 373-385.
    15. Papathanasiou, Jason & Manos, Basil D., 2007. "An approximation algorithm for the location of dairy enterprises under time constraints," European Journal of Operational Research, Elsevier, vol. 182(3), pages 1479-1487, November.
    16. Sven Müller & Knut Haase & Sascha Kless, 2009. "A Multiperiod School Location Planning Approach with Free School Choice," Environment and Planning A, , vol. 41(12), pages 2929-2945, December.
    17. Redondo, Juana L. & Fernández, José & Arrondo, Aránzazu G. & García, Inmaculada & Ortigosa, Pilar M., 2012. "Fixed or variable demand? Does it matter when locating a facility?," Omega, Elsevier, vol. 40(1), pages 9-20, January.
    18. Daniel Serra & Charles Revelle, 1994. "Competitive location in discrete space," Economics Working Papers 96, Department of Economics and Business, Universitat Pompeu Fabra.
    19. Gunhak Lee & Morton E. O'Kelly, 2009. "Exploring Locational Equilibria In A Competitive Broadband Access Market: Theoretical Modeling Approach," Journal of Regional Science, Wiley Blackwell, vol. 49(5), pages 953-975, December.
    20. Casas-Ramírez, Martha-Selene & Camacho-Vallejo, José-Fernando & Martínez-Salazar, Iris-Abril, 2018. "Approximating solutions to a bilevel capacitated facility location problem with customer's patronization toward a list of preferences," Applied Mathematics and Computation, Elsevier, vol. 319(C), pages 369-386.

    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:eee:ejores:v:224:y:2013:i:3:p:477-485. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.