IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v29y2017i1p152-169.html
   My bibliography  Save this article

Planar Maximum Coverage Location Problem with Partial Coverage and Rectangular Demand and Service Zones

Author

Listed:
  • Manish Bansal

    (Grado Department of Industrial and Systems Engineering, Virginia Tech, Blacksburg, Virginia 24061)

  • Kiavash Kianfar

    (Department of Industrial and Systems Engineering, Texas A&M University, College Station, Texas 77840)

Abstract

We study the planar maximum coverage location problem (MCLP) with rectilinear distance and rectangular demand zones in the case where “partial coverage” is allowed in its true sense, i.e., when covering part of a demand zone is allowed and the coverage accrued as a result of this is proportional to the demand of the covered part only. We pose the problem in a slightly more general form by allowing service zones to be rectangular instead of squares, thereby addressing applications in camera view-frame selection as well. More specifically, our problem, referred to as PMCLP-PCR (planar MCLP with partial coverage and rectangular demand and service zones), is to position a given number of rectangular service zones (SZs) on the two-dimensional plane to (partially) cover a set of existing (possibly overlapping) rectangular demand zones (DZs) such that the total covered demand is maximized. Previous studies on (planar) MCLP have assumed binary coverage, even when nonpoint objects such as lines or polygons have been used to represent demand. Under the binary coverage assumption, the problem can be readily formulated and solved as a binary linear program; whereas, partial coverage, although much more realistic, cannot be efficiently handled by binary linear programming, making PMCLP-PCR much more challenging to solve. In this paper, we first prove that PMCLP-PCR is NP-hard if the number of SZs is part of the input. We then present an improved algorithm for the single-SZ PMCLP-PCR, which is at least two times faster than the existing exact plateau vertex traversal algorithm. Next, we study multi-SZ PMCLP-PCR for the first time and prove theoretical properties that significantly reduce the search space for solving this problem, and we present a customized branch-and-bound exact algorithm to solve it. Our computational experiments show that this algorithm can solve relatively large instances of multi-SZ PMCLP-PCR in a short time. We also propose a fast polynomial time heuristic algorithm. Having optimal solutions from our exact algorithm, we benchmark the quality of solutions obtained from our heuristic algorithm. Our results show that for all the random instances solved to optimality by our exact algorithm, our heuristic algorithm finds a solution in a fraction of a second, where its objective value is at least 91% of the optimal objective in 90% of the instances (and at least 69% of the optimal objective in all the instances).

Suggested Citation

  • Manish Bansal & Kiavash Kianfar, 2017. "Planar Maximum Coverage Location Problem with Partial Coverage and Rectangular Demand and Service Zones," INFORMS Journal on Computing, INFORMS, vol. 29(1), pages 152-169, February.
    • Handle: RePEc:inm:orijoc:v:29:y:2017:i:1:p:152-169
    DOI: 10.1287/ijoc.2016.0722
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2016.0722
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2016.0722?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. Alan T. Murray & Morton E. O'Kelly, 2002. "Assessing representation error in point-based coverage modeling," Journal of Geographical Systems, Springer, vol. 4(2), pages 171-191, June.
    2. Drezner, Zvi, 1986. "The p-cover problem," European Journal of Operational Research, Elsevier, vol. 26(2), pages 312-313, August.
    3. Daoqin Tong & Alan T. Murray, 2009. "Maximising coverage of spatial demand for service," Papers in Regional Science, Wiley Blackwell, vol. 88(1), pages 85-97, March.
    4. Watson-Gandy, C. D. T., 1982. "Heuristic procedures for the m-partial cover problem on a plane," European Journal of Operational Research, Elsevier, vol. 11(2), pages 149-157, 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. Karatas, Mumtaz & Eriskin, Levent, 2023. "Linear and piecewise linear formulations for a hierarchical facility location and sizing problem," Omega, Elsevier, vol. 118(C).
    2. Pelegrín, Mercedes & Xu, Liding, 2023. "Continuous covering on networks: Improved mixed integer programming formulations," Omega, Elsevier, vol. 117(C).
    3. Baldomero-Naranjo, Marta & Kalcsics, Jörg & Marín, Alfredo & Rodríguez-Chía, Antonio M., 2022. "Upgrading edges in the maximal covering location problem," European Journal of Operational Research, Elsevier, vol. 303(1), pages 14-36.
    4. Chen, Liang & Chen, Sheng-Jie & Chen, Wei-Kun & Dai, Yu-Hong & Quan, Tao & Chen, Juan, 2023. "Efficient presolving methods for solving maximal covering and partial set covering location problems," European Journal of Operational Research, Elsevier, vol. 311(1), pages 73-87.
    5. Hu, Xiaoxuan & Zhu, Waiming & Ma, Huawei & An, Bo & Zhi, Yanling & Wu, Yi, 2021. "Orientational variable-length strip covering problem: A branch-and-price-based algorithm," European Journal of Operational Research, Elsevier, vol. 289(1), pages 254-269.
    6. Tedeschi, Danilo & Andretta, Marina, 2021. "New exact algorithms for planar maximum covering location by ellipses problems," European Journal of Operational Research, Elsevier, vol. 291(1), pages 114-127.

    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. Murray, Alan T. & Feng, Xin, 2016. "Public street lighting service standard assessment and achievement," Socio-Economic Planning Sciences, Elsevier, vol. 53(C), pages 14-22.
    2. Berman, Oded & Krass, Dmitry & Drezner, Zvi, 2003. "The gradual covering decay location problem on a network," European Journal of Operational Research, Elsevier, vol. 151(3), pages 474-480, December.
    3. Zhong, Qing & Tong, Daoqin, 2020. "Spatial layout optimization for solar photovoltaic (PV) panel installation," Renewable Energy, Elsevier, vol. 150(C), pages 1-11.
    4. Zvi Drezner & George Wesolowsky, 2014. "Covering Part of a Planar Network," Networks and Spatial Economics, Springer, vol. 14(3), pages 629-646, December.
    5. Ran Wei, 2016. "Coverage Location Models," International Regional Science Review, , vol. 39(1), pages 48-76, January.
    6. T Drezner & Z Drezner & P Kalczynski, 2011. "A cover-based competitive location model," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(1), pages 100-113, January.
    7. Berman, Oded & Drezner, Zvi & Krass, Dmitry & Wesolowsky, George O., 2009. "The variable radius covering problem," European Journal of Operational Research, Elsevier, vol. 196(2), pages 516-525, July.
    8. Alan T. Murray, 2016. "Maximal Coverage Location Problem," International Regional Science Review, , vol. 39(1), pages 5-27, January.
    9. Daoqin Tong & Alan T. Murray, 2009. "Maximising coverage of spatial demand for service," Papers in Regional Science, Wiley Blackwell, vol. 88(1), pages 85-97, March.
    10. Jiwon Baik & Alan T. Murray, 2022. "Locating a facility to simultaneously address access and coverage goals," Papers in Regional Science, Wiley Blackwell, vol. 101(5), pages 1199-1217, October.
    11. Chevalier, Philippe & Thomas, Isabelle & Geraets, David & Goetghebeur, Els & Janssens, Olivier & Peeters, Dominique & Plastria, Frank, 2012. "Locating fire stations: An integrated approach for Belgium," Socio-Economic Planning Sciences, Elsevier, vol. 46(2), pages 173-182.
    12. Kayode J. Samuel, 2010. "Infrastructure Location," Journal of Infrastructure Development, India Development Foundation, vol. 2(1), pages 71-90, June.
    13. Hammad, Ahmed W A & Akbarnezhad, Ali & Rey, David, 2017. "Sustainable urban facility location: Minimising noise pollution and network congestion," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 107(C), pages 38-59.
    14. Luke Shillington & Daoqin Tong, 2011. "Maximizing Wireless Mesh Network Coverage," International Regional Science Review, , vol. 34(4), pages 419-437, October.
    15. Murray, Alan T. & Wei, Ran, 2013. "A computational approach for eliminating error in the solution of the location set covering problem," European Journal of Operational Research, Elsevier, vol. 224(1), pages 52-64.
    16. Pludow, B. Amelia & Murray, Alan T. & Church, Richard L., 2022. "Service quality modeling to support optimizing facility location in a microscale environment," Socio-Economic Planning Sciences, Elsevier, vol. 82(PB).
    17. Karatas, Mumtaz & Eriskin, Levent, 2023. "Linear and piecewise linear formulations for a hierarchical facility location and sizing problem," Omega, Elsevier, vol. 118(C).
    18. Alan T. Murray & Daoqin Tong & Kamyoung Kim, 2010. "Enhancing Classic Coverage Location Models," International Regional Science Review, , vol. 33(2), pages 115-133, April.
    19. Alan T. Murray & Antonio Ortiz & Seonga Cho, 2022. "Enhancing strategic defensive positioning and performance in the outfield," Journal of Geographical Systems, Springer, vol. 24(2), pages 223-240, April.
    20. Wang, Wei & Wu, Shining & Wang, Shuaian & Zhen, Lu & Qu, Xiaobo, 2021. "Emergency facility location problems in logistics: Status and perspectives," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 154(C).

    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:orijoc:v:29:y:2017:i:1:p:152-169. 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.