IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v43y1996i3p435-461.html
   My bibliography  Save this article

An exact algorithm for the maximal covering problem

Author

Listed:
  • Brian T. Downs
  • Jeffrey D. Camm

Abstract

This article develops a robust, exact algorithm for the maximal covering problem (MCP) using dual‐based solution methods and greedy heuristics in branch and bound. Based on tests using randomly generated problems with problem parameters similar to those in the existing literature, the hybrid approach developed in this work appears to be effective over a wide range of MCP model parameters. The method is further validated on problems constructed from three real‐world data sets. The extensive computational study compares the new method with other existing exact methods using problems that are as big, or larger than, those used in previous work on MCP. The results show that the proposed method is effective in most instances of MCP. In particular, it is shown that bounding schemes using Lagrangian relaxation are effective on MCP as a method of obtaining both exact and heuristic solutions. © 1996 John Wiley & Sons, Inc.

Suggested Citation

  • Brian T. Downs & Jeffrey D. Camm, 1996. "An exact algorithm for the maximal covering problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(3), pages 435-461, April.
    • Handle: RePEc:wly:navres:v:43:y:1996:i:3:p:435-461
    DOI: 10.1002/(SICI)1520-6750(199604)43:33.0.CO;2-A
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/(SICI)1520-6750(199604)43:33.0.CO;2-A
    Download Restriction: no
    File URL: https://libkey.io/10.1002/(SICI)1520-6750(199604)43:33.0.CO;2-A?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. Hasan Pirkul & David A. Schilling, 1991. "The Maximal Covering Location Problem with Capacities on Total Workload," Management Science, INFORMS, vol. 37(2), pages 233-248, February.
    2. Marshall L. Fisher, 1981. "The Lagrangian Relaxation Method for Solving Integer Programming Problems," Management Science, INFORMS, vol. 27(1), pages 1-18, January.
    3. Hasan Pirkul & David A. Schilling, 1988. "The Siting of Emergency Service Facilities with Workload Capacities and Backup Service," Management Science, INFORMS, vol. 34(7), pages 896-908, July.
    4. Mark Daskin & Philip C. Jones & Timothy J. Lowe, 1990. "Rationalizing Tool Selection in a Flexible Manufacturing System for Sheet-Metal Products," Operations Research, INFORMS, vol. 38(6), pages 1104-1115, December.
    5. F. Robert Dwyer & James R. Evans, 1981. "A Branch and Bound Algorithm for the List Selection Problem in Direct Mail Advertising," Management Science, INFORMS, vol. 27(6), pages 658-667, June.
    6. Richard Church & Charles R. Velle, 1974. "The Maximal Covering Location Problem," Papers in Regional Science, Wiley Blackwell, vol. 32(1), pages 101-118, January.
    7. Bennett, Vivienne L. & Eaton, David J. & Church, Richard L., 1982. "Selecting sites for rural health workers," Social Science & Medicine, Elsevier, vol. 16(1), pages 63-72, January.
    8. David J. Eaton & Mark S. Daskin & Dennis Simmons & Bill Bulloch & Glen Jansma, 1985. "Determining Emergency Medical Service Vehicle Deployment in Austin, Texas," Interfaces, INFORMS, vol. 15(1), pages 96-108, February.
    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. Alan T. Murray, 2016. "Maximal Coverage Location Problem," International Regional Science Review, , vol. 39(1), pages 5-27, January.
    2. 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.
    3. Galvao, Roberto D. & Gonzalo Acosta Espejo, Luis & Boffey, Brian, 2000. "A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem," European Journal of Operational Research, Elsevier, vol. 124(2), pages 377-389, July.
    4. Cordeau, Jean-François & Furini, Fabio & Ljubić, Ivana, 2019. "Benders decomposition for very large scale partial set covering and maximal covering location problems," European Journal of Operational Research, Elsevier, vol. 275(3), pages 882-896.
    5. He, Zhou & Fan, Bo & Cheng, T.C.E. & Wang, Shou-Yang & Tan, Chin-Hon, 2016. "A mean-shift algorithm for large-scale planar maximal covering location problems," European Journal of Operational Research, Elsevier, vol. 250(1), pages 65-76.
    6. Jeffrey D. Camm & James J. Cochran & David J. Curry & Sriram Kannan, 2006. "Conjoint Optimization: An Exact Branch-and-Bound Algorithm for the Share-of-Choice Problem," Management Science, INFORMS, vol. 52(3), pages 435-447, March.
    7. Jeffrey D. Camm & Jeremy Christman & A. Narayanan, 2022. "Total Unduplicated Reach and Frequency Optimization at Procter & Gamble," Interfaces, INFORMS, vol. 52(2), pages 149-157, March.
    8. James J. Cochran & Martin S. Levy & Jeffrey D. Camm, 2010. "Bayesian coverage optimization models," Journal of Combinatorial Optimization, Springer, vol. 19(2), pages 158-173, February.

    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. Alan T. Murray, 2016. "Maximal Coverage Location Problem," International Regional Science Review, , vol. 39(1), pages 5-27, January.
    2. James J. Cochran & Martin S. Levy & Jeffrey D. Camm, 2010. "Bayesian coverage optimization models," Journal of Combinatorial Optimization, Springer, vol. 19(2), pages 158-173, February.
    3. 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).
    4. Hasan Pirkul & David A. Schilling, 1998. "An Efficient Procedure for Designing Single Allocation Hub and Spoke Systems," Management Science, INFORMS, vol. 44(12-Part-2), pages 235-242, December.
    5. 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.
    6. P. Daniel Wright & Matthew J. Liberatore & Robert L. Nydick, 2006. "A Survey of Operations Research Models and Applications in Homeland Security," Interfaces, INFORMS, vol. 36(6), pages 514-529, December.
    7. Tiwari, Richa & Jayaswal, Sachin & Sinha, Ankur, 2021. "Alternate solution approaches for competitive hub location problems," European Journal of Operational Research, Elsevier, vol. 290(1), pages 68-80.
    8. 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.
    9. 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.
    10. Huizhu Wang & Jianqin Zhou & Ling Zhou, 2024. "A Lattice Boltzmann Method-like Algorithm for the Maximal Covering Location Problem on the Complex Network: Application to Location of Railway Emergency-Rescue Spot," Mathematics, MDPI, vol. 12(2), pages 1-20, January.
    11. Boffey, Brian & Galvao, Roberto & Espejo, Luis, 2007. "A review of congestion models in the location of facilities with immobile servers," European Journal of Operational Research, Elsevier, vol. 178(3), pages 643-662, May.
    12. Wajid, Shayesta & Nezamuddin, N., 2023. "Capturing delays in response of emergency services in Delhi," Socio-Economic Planning Sciences, Elsevier, vol. 87(PA).
    13. Afsaneh Amiri & Majid Salari, 2019. "Time-constrained maximal covering routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(2), pages 415-468, June.
    14. Galvao, Roberto D. & Gonzalo Acosta Espejo, Luis & Boffey, Brian, 2000. "A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem," European Journal of Operational Research, Elsevier, vol. 124(2), pages 377-389, July.
    15. Wajid, Shayesta & Nezamuddin, N., 2022. "A robust survival model for emergency medical services in Delhi, India," Socio-Economic Planning Sciences, Elsevier, vol. 83(C).
    16. Kevin Curtin & Karen Hayslett-McCall & Fang Qiu, 2010. "Determining Optimal Police Patrol Areas with Maximal Covering and Backup Covering Location Models," Networks and Spatial Economics, Springer, vol. 10(1), pages 125-145, March.
    17. Jeffrey D. Camm & Jeremy Christman & A. Narayanan, 2022. "Total Unduplicated Reach and Frequency Optimization at Procter & Gamble," Interfaces, INFORMS, vol. 52(2), pages 149-157, March.
    18. Jing Yao & Alan T. Murray, 2014. "Locational Effectiveness of Clinics Providing Sexual and Reproductive Health Services to Women in Rural Mozambique," International Regional Science Review, , vol. 37(2), pages 172-193, April.
    19. Muren, & Li, Hao & Mukhopadhyay, Samar K. & Wu, Jian-jun & Zhou, Li & Du, Zhiping, 2020. "Balanced maximal covering location problem and its application in bike-sharing," International Journal of Production Economics, Elsevier, vol. 223(C).
    20. Sunarin Chanta & Maria Mayorga & Laura McLay, 2014. "Improving emergency service in rural areas: a bi-objective covering location model for EMS systems," Annals of Operations Research, Springer, vol. 221(1), pages 133-159, October.

    More about this item

    Statistics

    Access and download statistics

    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:wly:navres:v:43:y:1996:i:3:p:435-461. 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.