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

Maximal covering tree problems

Author

Listed:
  • Richard Church
  • John Current

Abstract

Hutson and ReVelle [8] define the maximal direct covering tree problem as a bicriterion problem to identify a subtree of a given tree. The two criteria are to maximize demand covered by the subtree and to minimize the cost of the subtree. Demand at a node on the underlying tree is considered covered if it is within some prespecified covering distance S of the subtree. In the direct covering version of the problem. S = 0. In this article we present a new bicriterion formulation of the maximal direct covering tree problem and present O(n2) algorithms for solving both this problem and the special case where one must add to an existing subtree. The new formulation is extremely concise; consequently, additional constraints may be added where appropriate. This is demonstrated with the addition of a budget constraint. In addition, we demonstrate that the new formulation and algorithm can be readily extended to incorporate indirect covering (i.e., S > 0) as defined by Kim et al. [9]. © 1993 John Wiley & Sons. Inc.

Suggested Citation

  • Richard Church & John Current, 1993. "Maximal covering tree problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(1), pages 129-142, February.
    • Handle: RePEc:wly:navres:v:40:y:1993:i:1:p:129-142
    DOI: 10.1002/1520-6750(199302)40:13.0.CO;2-T
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/1520-6750(199302)40:13.0.CO;2-T
    Download Restriction: no
    File URL: https://libkey.io/10.1002/1520-6750(199302)40:13.0.CO;2-T?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. R. K. Ahuja & V. V. S. Murty, 1987. "Exact and Heuristic Algorithms for the Optimum Communication Spanning Tree Problem," Transportation Science, INFORMS, vol. 21(3), pages 163-170, August.
    2. Current, J. R. & Re Velle, C. S. & Cohon, J. L., 1985. "The maximum covering/shortest path problem: A multiobjective network design and routing formulation," European Journal of Operational Research, Elsevier, vol. 21(2), pages 189-199, August.
    3. Richard Church & Charles R. Velle, 1974. "The Maximal Covering Location Problem," Papers in Regional Science, Wiley Blackwell, vol. 32(1), pages 101-118, January.
    4. Current, John & Min, HoKey, 1986. "Multiobjective design of transportation networks: Taxonomy and annotation," European Journal of Operational Research, Elsevier, vol. 26(2), pages 187-201, August.
    5. CONSTANTINE TOREGAS & CHARLES ReVELLE, 1972. "Optimal Location Under Time Or Distance Constraints," Papers in Regional Science, Wiley Blackwell, vol. 28(1), pages 133-144, January.
    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. T. Boffey, 1998. "Efficient solution methods for covering tree problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 6(2), pages 205-221, December.
    2. Mesa, Juan A. & Brian Boffey, T., 1996. "A review of extensive facility location in networks," European Journal of Operational Research, Elsevier, vol. 95(3), pages 592-603, December.

    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. Ospina, Juan P. & Duque, Juan C. & Botero-Fernández, Verónica & Montoya, Alejandro, 2022. "The maximal covering bicycle network design problem," Transportation Research Part A: Policy and Practice, Elsevier, vol. 159(C), pages 222-236.
    2. Arana-Jiménez, Manuel & Blanco, Víctor & Fernández, Elena, 2020. "On the fuzzy maximal covering location problem," European Journal of Operational Research, Elsevier, vol. 283(2), pages 692-705.
    3. Theophilus Dhyankumar Chellappa & Ramasubramaniam Muthurathinasapathy & V. G. Venkatesh & Yangyan Shi & Samsul Islam, 2023. "Location of organ procurement and distribution organisation decisions and their impact on kidney allocations: a developing country perspective," Annals of Operations Research, Springer, vol. 321(1), pages 755-781, February.
    4. Jenkins, Phillip R. & Lunday, Brian J. & Robbins, Matthew J., 2020. "Robust, multi-objective optimization for the military medical evacuation location-allocation problem," Omega, Elsevier, vol. 97(C).
    5. Alan T. Murray & Daoqin Tong & Kamyoung Kim, 2010. "Enhancing Classic Coverage Location Models," International Regional Science Review, , vol. 33(2), pages 115-133, April.
    6. Marianov, Vladimir & Eiselt, H.A., 2024. "Fifty Years of Location Theory - A Selective Review," European Journal of Operational Research, Elsevier, vol. 318(3), pages 701-718.
    7. Alan T. Murray, 2016. "Maximal Coverage Location Problem," International Regional Science Review, , vol. 39(1), pages 5-27, January.
    8. Sam Ratick & Jeffrey Osleeb & Kangping Si, 2016. "The Maximal Cover Location Model with Hedging," International Regional Science Review, , vol. 39(1), pages 77-107, January.
    9. Curtin, Kevin M. & Biba, Steve, 2011. "The Transit Route Arc-Node Service Maximization problem," European Journal of Operational Research, Elsevier, vol. 208(1), pages 46-56, January.
    10. Michael J. Brusco, 2022. "Solving Classic Discrete Facility Location Problems Using Excel Spreadsheets," INFORMS Transactions on Education, INFORMS, vol. 22(3), pages 160-171, May.
    11. Mesa, Juan A. & Brian Boffey, T., 1996. "A review of extensive facility location in networks," European Journal of Operational Research, Elsevier, vol. 95(3), pages 592-603, December.
    12. Tammy Drezner & Zvi Drezner, 2019. "Cooperative Cover of Uniform Demand," Networks and Spatial Economics, Springer, vol. 19(3), pages 819-831, September.
    13. Minghe Sun, 2005. "Warm-Start Routines for Solving Augmented Weighted Tchebycheff Network Programs in Multiple-Objective Network Programming," INFORMS Journal on Computing, INFORMS, vol. 17(4), pages 422-437, November.
    14. Huizhu Wang & Jianqin Zhou, 2023. "Location of Railway Emergency Rescue Spots Based on a Near-Full Covering Problem: From a Perspective of Diverse Scenarios," Sustainability, MDPI, vol. 15(8), pages 1-16, April.
    15. Zanakis, Stelios H. & Mandakovic, Tomislav & Gupta, Sushil K. & Sahay, Sundeep & Hong, Sungwan, 1995. "A review of program evaluation and fund allocation methods within the service and government sectors," Socio-Economic Planning Sciences, Elsevier, vol. 29(1), pages 59-79, March.
    16. Li, Xin & Pan, Yanchun & Jiang, Shiqiang & Huang, Qiang & Chen, Zhimin & Zhang, Mingxia & Zhang, Zuoyao, 2021. "Locate vaccination stations considering travel distance, operational cost, and work schedule," Omega, Elsevier, vol. 101(C).
    17. Murawski, Lisa & Church, Richard L., 2009. "Improving accessibility to rural health services: The maximal covering network improvement problem," Socio-Economic Planning Sciences, Elsevier, vol. 43(2), pages 102-110, June.
    18. 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.
    19. Fadda, Edoardo & Manerba, Daniele & Cabodi, Gianpiero & Camurati, Paolo Enrico & Tadei, Roberto, 2021. "Comparative analysis of models and performance indicators for optimal service facility location," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    20. Erhan Erkut & Armann Ingolfsson & Güneş Erdoğan, 2008. "Ambulance location for maximum survival," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(1), pages 42-58, February.

    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:40:y:1993:i:1:p:129-142. 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.