IDEAS home Printed from https://ideas.repec.org/a/sae/envira/v28y1996i9p1699-1708.html
   My bibliography  Save this article

Analysis and Computational Schemes for p-Median Heuristics

Author

Listed:
  • M Horn

    (CSIRO Division of Information Technology, GPO Box 664, Canberra, ACT 2601, Australia)

Abstract

This paper is concerned with solution procedures for the p -median problem: the well-established heuristic of Teitz and Bart, and the GRIA (Global/Regional Interchange Algorithm) technique developed more recently by Densham and Rushton. A computational scheme is presented which facilitates efficient implementations in both cases. The mathematical basis for the computational scheme is explained concisely by means of set-theory notation, and implementation of the Teitz—Bart heuristic is discussed with particular reference to search and storage considerations in large networks and in trees. In addition, it is shown that the two procedures in general do not terminate at solutions of equivalent local optimality.

Suggested Citation

  • M Horn, 1996. "Analysis and Computational Schemes for p-Median Heuristics," Environment and Planning A, , vol. 28(9), pages 1699-1708, September.
    • Handle: RePEc:sae:envira:v:28:y:1996:i:9:p:1699-1708
    DOI: 10.1068/a281699
    as

    Download full text from publisher

    File URL: https://journals.sagepub.com/doi/10.1068/a281699
    Download Restriction: no
    File URL: https://libkey.io/10.1068/a281699?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. S. L. Hakimi, 1964. "Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph," Operations Research, INFORMS, vol. 12(3), pages 450-459, June.
    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. Rosing, K. E. & ReVelle, C. S. & Schilling, D. A., 1999. "A gamma heuristic for the p-median problem," European Journal of Operational Research, Elsevier, vol. 117(3), pages 522-532, September.

    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. Alfandari, Laurent, 2004. "Choice Rules with Size Constraints for Multiple Criteria Decision Making," ESSEC Working Papers DR 04002, ESSEC Research Center, ESSEC Business School.
    2. S Salhi & A Al-Khedhairi, 2010. "Integrating heuristic information into exact methods: The case of the vertex p-centre problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(11), pages 1619-1631, November.
    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. Schnepper, Teresa & Klamroth, Kathrin & Stiglmayr, Michael & Puerto, Justo, 2019. "Exact algorithms for handling outliers in center location problems on networks using k-max functions," European Journal of Operational Research, Elsevier, vol. 273(2), pages 441-451.
    5. Davood Shishebori & Lawrence Snyder & Mohammad Jabalameli, 2014. "A Reliable Budget-Constrained FL/ND Problem with Unreliable Facilities," Networks and Spatial Economics, Springer, vol. 14(3), pages 549-580, December.
    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. Behrens, Kristian, 2007. "On the location and lock-in of cities: Geography vs transportation technology," Regional Science and Urban Economics, Elsevier, vol. 37(1), pages 22-45, January.
    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. Csiszár, Csaba & Csonka, Bálint & Földes, Dávid & Wirth, Ervin & Lovas, Tamás, 2020. "Location optimisation method for fast-charging stations along national roads," Journal of Transport Geography, Elsevier, vol. 88(C).
    10. Ashraf Abd El Karim & Mohsen M. Awawdeh, 2020. "Integrating GIS Accessibility and Location-Allocation Models with Multicriteria Decision Analysis for Evaluating Quality of Life in Buraidah City, KSA," Sustainability, MDPI, vol. 12(4), pages 1-28, February.
    11. Zvi Drezner & G. O. Wesolowsky, 1991. "Facility location when demand is time dependent," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(5), pages 763-777, October.
    12. Zhizhu Lai & Qun Yue & Zheng Wang & Dongmei Ge & Yulong Chen & Zhihong Zhou, 2022. "The min-p robust optimization approach for facility location problem under uncertainty," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1134-1160, September.
    13. Stephanie A. Snyder & Robert G. Haight, 2016. "Application of the Maximal Covering Location Problem to Habitat Reserve Site Selection," International Regional Science Review, , vol. 39(1), pages 28-47, January.
    14. Robichet, Antoine & Nierat, Patrick, 2021. "Consequences of logistics sprawl: Order or chaos? - the case of a parcel service company in Paris metropolitan area," Journal of Transport Geography, Elsevier, vol. 90(C).
    15. Höhn, J. & Lehtonen, E. & Rasi, S. & Rintala, J., 2014. "A Geographical Information System (GIS) based methodology for determination of potential biomasses and sites for biogas plants in southern Finland," Applied Energy, Elsevier, vol. 113(C), pages 1-10.
    16. Averbakh, Igor & Berman, Oded, 1996. "Locating flow-capturing units on a network with multi-counting and diminishing returns to scale," European Journal of Operational Research, Elsevier, vol. 91(3), pages 495-506, June.
    17. Zhang, Tong & Zeng, Zhe & Jia, Tao & Li, Jing, 2016. "Examining the amenability of urban street networks for locating facilities," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 457(C), pages 469-479.
    18. Berman, Oded & Krass, Dmitry & Menezes, Mozart B.C., 2016. "Directed assignment vs. customer choice in location inventory models," International Journal of Production Economics, Elsevier, vol. 179(C), pages 179-191.
    19. Shulin Wang & Shanhua Wu, 2023. "Optimizing the Location of Virtual-Shopping-Experience Stores Based on the Minimum Impact on Urban Traffic," Sustainability, MDPI, vol. 15(13), pages 1-25, June.
    20. D Bigman & C ReVelle, 1979. "An Operational Approach to Welfare Considerations in Applied Public-Facility-Location Models," Environment and Planning A, , vol. 11(1), pages 83-95, January.

    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:sae:envira:v:28:y:1996:i:9:p:1699-1708. 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: SAGE Publications (email available below). General contact details of provider: .

    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.