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

The p-median problem under uncertainty

Author

Listed:
  • Berman, Oded
  • Drezner, Zvi

Abstract

Consider the need to currently locate p facilities but it is possible that up to q additional facilities will have to be located in the future. There are known probabilities that 0 [less-than-or-equals, slant] r [less-than-or-equals, slant] q facilities will need to be located. The p-median problem under uncertainty is to find the location of p facilities such that the expected value of the objective function in the future is minimized. The problem is formulated on a graph, properties of it are proven, an integer programming formulation is constructed, and heuristic algorithms are suggested for its solution. The heuristic algorithms are modified to reduce the run time by about two orders of magnitude with minimal effect on the quality of the solution. Optimal solutions for many problems are found effectively by CPLEX. Computational results using the heuristic algorithms are presented.

Suggested Citation

  • Berman, Oded & Drezner, Zvi, 2008. "The p-median problem under uncertainty," European Journal of Operational Research, Elsevier, vol. 189(1), pages 19-30, August.
    • Handle: RePEc:eee:ejores:v:189:y:2008:i:1:p:19-30
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(07)00498-5
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Z. Drezner & G. O. Wesolowsky, 1981. "Optimum Location Probabilities in the l p Distance Weber Problem," Transportation Science, INFORMS, vol. 15(2), pages 85-97, May.
    2. Hakimi, S. Louis, 1983. "On locating new facilities in a competitive environment," European Journal of Operational Research, Elsevier, vol. 12(1), pages 29-35, January.
    3. Michael B. Teitz & Polly Bart, 1968. "Heuristic Methods for Estimating the Generalized Vertex Median of a Weighted Graph," Operations Research, INFORMS, vol. 16(5), pages 955-961, October.
    4. Drezner, Zvi, 1982. "Competitive location strategies for two facilities," Regional Science and Urban Economics, Elsevier, vol. 12(4), pages 485-493, November.
    5. Current, John & Ratick, Samuel & ReVelle, Charles, 1998. "Dynamic facility location when the total number of facilities is uncertain: A decision analysis approach," European Journal of Operational Research, Elsevier, vol. 110(3), pages 597-609, November.
    6. Tammy Drezner & Zvi Drezner & Shogo Shiode, 2002. "A Threshold‐Satisfying Competitive Location Model," Journal of Regional Science, Wiley Blackwell, vol. 42(2), pages 287-299, May.
    7. George O. Wesolowsky, 1977. "Probabilistic Weights in the One-Dimensional Facility Location Problem," Management Science, INFORMS, vol. 24(2), pages 224-229, October.
    8. Drezner, Zvi & Shiode, Shogo, 2007. "A distribution map for the one-median location problem on a network," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1266-1273, 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. Murali, Pavankumar & Ordóñez, Fernando & Dessouky, Maged M., 2012. "Facility location under demand uncertainty: Response to a large-scale bio-terror attack," Socio-Economic Planning Sciences, Elsevier, vol. 46(1), pages 78-87.
    2. Amir Hossein Sadeghi & Ziyuan Sun & Amirreza Sahebi-Fakhrabad & Hamid Arzani & Robert Handfield, 2023. "A Mixed-Integer Linear Formulation for a Dynamic Modified Stochastic p-Median Problem in a Competitive Supply Chain Network Design," Logistics, MDPI, vol. 7(1), pages 1-24, March.
    3. Qianli Zhang & Haijun Mao, 2022. "An Integrated Method for Locating Logistic Centers in a Rural Area," Sustainability, MDPI, vol. 14(9), pages 1-19, May.
    4. Chen, Xudong & Fujita, Tsuyoshi & Hayashi, Yoshitsugu & Kato, Hirokazu & Geng, Yong, 2014. "Determining optimal resource recycling boundary at regional level: A case study on Tokyo Metropolitan Area in Japan," European Journal of Operational Research, Elsevier, vol. 233(2), pages 337-348.
    5. Guerriero, Francesca & Miglionico, Giovanna & Olivito, Filomena, 2016. "Location and reorganization problems: The Calabrian health care system case," European Journal of Operational Research, Elsevier, vol. 250(3), pages 939-954.
    6. 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).
    7. Simon Blanchard & Daniel Aloise & Wayne DeSarbo, 2012. "The Heterogeneous P-Median Problem for Categorization Based Clustering," Psychometrika, Springer;The Psychometric Society, vol. 77(4), pages 741-762, October.
    8. N Görmez & M Köksalan & F S Salman, 2011. "Locating disaster response facilities in Istanbul," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(7), pages 1239-1252, July.
    9. 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.
    10. Shahzad Bhatti & Michael Lim & Ho-Yin Mak, 2015. "Alternative fuel station location model with demand learning," Annals of Operations Research, Springer, vol. 230(1), pages 105-127, July.
    11. Sonmez, Ayse Durukan & Lim, Gino J., 2012. "A decomposition approach for facility location and relocation problem with uncertain number of future facilities," European Journal of Operational Research, Elsevier, vol. 218(2), pages 327-338.

    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. Shiode, Shogo & Drezner, Zvi, 2003. "A competitive facility location problem on a tree network with stochastic weights," European Journal of Operational Research, Elsevier, vol. 149(1), pages 47-52, August.
    2. Zvi Drezner & Mozart B. C. Menezes, 2016. "The wisdom of voters: evaluating the Weber objective in the plane at the Condorcet solution," Annals of Operations Research, Springer, vol. 246(1), pages 205-226, November.
    3. Mahmutogullari, Ali Irfan & Kara, Bahar Y., 2016. "Hub location under competition," European Journal of Operational Research, Elsevier, vol. 250(1), pages 214-225.
    4. 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.
    5. Drezner, Zvi & Eiselt, H.A., 2024. "Competitive location models: A review," European Journal of Operational Research, Elsevier, vol. 316(1), pages 5-18.
    6. Thomas Byrne & Sándor P. Fekete & Jörg Kalcsics & Linda Kleist, 2023. "Competitive location problems: balanced facility location and the One-Round Manhattan Voronoi Game," Annals of Operations Research, Springer, vol. 321(1), pages 79-101, February.
    7. Drezner, Tammy & Drezner, Zvi & Salhi, Said, 2002. "Solving the multiple competitive facilities location problem," European Journal of Operational Research, Elsevier, vol. 142(1), pages 138-151, October.
    8. O Berman & Z Drezner, 2003. "A probabilistic one-centre location problem on a network," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(8), pages 871-877, August.
    9. 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.
    10. Tammy Drezner & Zvi Drezner & Pawel Kalczynski, 2020. "Gradual cover competitive facility location," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(2), pages 333-354, June.
    11. Eiselt, H.A. & Marianov, Vladimir, 2020. "Maximizing political vote in multiple districts," Socio-Economic Planning Sciences, Elsevier, vol. 72(C).
    12. Granot, Daniel & Granot, Frieda & Raviv, Tal, 2010. "On competitive sequential location in a network with a decreasing demand intensity," European Journal of Operational Research, Elsevier, vol. 205(2), pages 301-312, September.
    13. Vladimir Marianov & H. A. Eiselt & Armin Lüer-Villagra, 2020. "The Follower Competitive Location Problem with Comparison-Shopping," Networks and Spatial Economics, Springer, vol. 20(2), pages 367-393, June.
    14. Tammy Drezner & Zvi Drezner & Atsuo Suzuki, 2019. "A cover based competitive facility location model with continuous demand," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(7), pages 565-581, October.
    15. Uno, Takeshi & Katagiri, Hideki, 2008. "Single- and multi-objective defensive location problems on a network," European Journal of Operational Research, Elsevier, vol. 188(1), pages 76-84, July.
    16. Tammy Drezner & Zvi Drezner & Dawit Zerom, 2020. "Facility Dependent Distance Decay in Competitive Location," Networks and Spatial Economics, Springer, vol. 20(4), pages 915-934, December.
    17. Loree, Nick & Aros-Vera, Felipe, 2018. "Points of distribution location and inventory management model for Post-Disaster Humanitarian Logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 116(C), pages 1-24.
    18. Daniel Serra & Charles Revelle, 1994. "Competitive location in discrete space," Economics Working Papers 96, Department of Economics and Business, Universitat Pompeu Fabra.
    19. Menezes, Mozart B.C. & da Silveira, Giovani J.C. & Drezner, Zvi, 2016. "Democratic elections and centralized decisions: Condorcet and Approval Voting compared with Median and Coverage locations," European Journal of Operational Research, Elsevier, vol. 253(1), pages 195-203.
    20. Saidani, Nasreddine & Chu, Feng & Chen, Haoxun, 2012. "Competitive facility location and design with reactions of competitors already in the market," European Journal of Operational Research, Elsevier, vol. 219(1), pages 9-17.

    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:eee:ejores:v:189:y:2008:i:1:p:19-30. 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.