Skip to main content
Log in

Stochastic analysis of ordered median problems

Journal of the Operational Research Society

Abstract

Many location problems can be expressed as ordered median objective. In this paper, we investigate the ordered median objective when the demand points are generated in a circle. We find the mean and variance of the kth distance from the centre of the circle and the correlation matrix between all pairs of ordered distances. By applying these values, we calculate the mean and variance of any ordered median objective and the correlation coefficient between two ordered median objectives. The usefulness of the results is demonstrated by calculating various probabilities such as: What is the probability that the mean distance is greater than the truncated mean distance? What is the probability that the maximum distance is greater than 0.9? What is the probability that the range of distances is greater than 0.8? An analysis of an illustrative example also demonstrates the usefulness of the analysis.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1

References

  • Abramowitz M and Stegun IA (1972). Handbook of Mathematical Functions. Dover Publications: New York, NY.

    Google Scholar 

  • Altınel IK, Durmaz E, Aras N and Özkısacık KC (2009). A location-allocation heuristic for the capacitated multi-facility Weber problem with probabilistic customer locations. European Journal of Operational Research 198: 790–799.

    Article  Google Scholar 

  • Arnold BC, Balakrishnan N and Nagaraja HN (1992). A First Course in Order Statistics. John Wiley & Sons: New York, NY.

    Google Scholar 

  • Averbakh I and Bereg S (2005). Facility location problems with uncertainty on the plane. Discrete Optimizatiion 2: 3–34.

    Article  Google Scholar 

  • Berman O, Drezner Z and Wesolowsky GO (2003). The expropriation location problem. Journal of the Operational Research Society 54: 769–776.

    Article  Google Scholar 

  • Beyer HW (1981). Standard Mathematical Tables. CRC Press: Boca Raton, Florida.

    Google Scholar 

  • Cooper L (1974). A random location equilibrium problem. Journal of Regional Science 14: 47–54.

    Article  Google Scholar 

  • Drezner T, Drezner Z and Guyse J (2009). Equitable service by a facility: Minimizing the Gini coefficient. Computers and Operational Research 36: 3240–3246.

    Article  Google Scholar 

  • Drezner Z (1992). Computation of the multivariate normal integral. ACM Transactions on Mathematical Software 18: 470–480.

    Article  Google Scholar 

  • Drezner Z (1994). Computation of the trivariate normal integral. Mathematics of Computation 62: 289–294.

    Article  Google Scholar 

  • Drezner Z (2007). A general global optimization approach for solving location problems in the plane. Journal of Global Optimization 37: 305–319.

    Article  Google Scholar 

  • Drezner Z and Nickel S (2009a). Solving the ordered one-median problem in the plane. European Journal of Operational Research 195: 46–61.

    Article  Google Scholar 

  • Drezner Z and Nickel S (2009b). Constructing a DC decomposition for ordered median problems. Journal of Global Optimization 45: 187–201.

    Article  Google Scholar 

  • Drezner Z and Simchi-Levi D (1992). Asymptotic behavior of the Weber location problem on the plane. Annals of Operations Research 40: 163–172.

    Article  Google Scholar 

  • Drezner Z and Suzuki A (2004). The big triangle small triangle method for the solution of non-convex facility location problems. Operations Research 52: 128–135.

    Article  Google Scholar 

  • Drezner Z and Wesolowsky GO (1981). Optimum location probabilities in the l p distance Weber problem. Transportation Science 15: 85–97.

    Article  Google Scholar 

  • Drezner Z and Wesolowsky GO (1990). On the computation of the bivariate normal integral. Journal of Statistical Computation and Simulation 35: 101–107.

    Article  Google Scholar 

  • Drezner Z, Klamroth K, Schöbel A and Wesolowsky GO (2002). The weber problem. In: Drezner Z and Hamacher HW (eds) Facility Location: Applications and Theory. Springer: Berlin, pp 1–36.

    Chapter  Google Scholar 

  • Durmaz E, Aras N and Altınel IK (2009). Discrete approximation heuristics for the capacitated continuous location-allocation problem with probabilistic customer locations. Computers and Operations Research 36: 2139–2148.

    Article  Google Scholar 

  • Frank H (1966). Optimum locations on a graph with probabilistic demands. Operations Research 14: 409–421.

    Article  Google Scholar 

  • Frank H (1967). Optimum locations on graphs with correlated normal demands. Operations Research 15: 552–557.

    Article  Google Scholar 

  • Gradshteyn LS, Ryzhik IM and Jeffrey A (1994). Tables of Integrals, Series, and Products. 5th edn, Academic Press: San Diego, CA.

    Google Scholar 

  • Horst R and Thoai NV (1999). DC programming: Overview. Journal of Optimization Theory and Applications 103: 1–43.

    Article  Google Scholar 

  • Johnson NL and Kotz S (1972). Distributions in Statistics: Continuous Multivariate Distributions. Wiley: New York.

    Google Scholar 

  • Kalcsics J, Nickel S, Puerto J and Tamir A (2002). Algorithmic results for ordered median problems. Operations Research Letters 30: 149–158.

    Article  Google Scholar 

  • Love RF, Morris JG and Wesolowsky GO (1988). Facilities Location: Models & Methods. Elsevier Science, North Holland: New York, NY.

    Google Scholar 

  • Melo MT, Nickel S and Saldanha-da-Gama F (2009). Facility location and supply chain management—A review. European Journal of Operational Research 196: 401–412.

    Article  Google Scholar 

  • Murat A, Verter V and Laporte G (2010). A continuous analysis framework for the solution of location-allocation problems with dense demand. Computers and Operations Research 37: 123–136.

    Article  Google Scholar 

  • Nickel S and Puerto J (2005). Facility Location—A Unified Approach. Springer: Berlin Heidelberg.

    Google Scholar 

  • Rodríguez-Chía AM, Nickel S, Puerto J and Fernandez FR (2000). A flexible approach to location problems. Mathematical Methods of Operations Research 51: 69–89.

    Article  Google Scholar 

  • Snyder LV (2006). Facility location under uncertainty: A review. IIE Transactions 38: 547–564.

    Article  Google Scholar 

  • Weber A (1929). Über den Standort der Industrien, 1. Teil: Reine Theorie des Standortes. English Translation: On the Location of Industries. University of Chicago Press: Chicago, IL, Originally published in Tuobingen, Germany in 1909.

    Google Scholar 

  • Wesolowsky GO (1977a). The Weber problem with rectangular distances and randomly distributed destinations. Journal of Regional Science 17: 53–60.

    Article  Google Scholar 

  • Wesolowsky GO (1977b). Probabilistic weights in the one-dimensional facility location problem. Management Science 24: 224–229.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Appendix

Appendix

Proofs

Proof of Theorem 1

Substituting m=j−1 in the first sum and recalling that leads to:

All the terms, except the first one in the first sum, cancel out proving the Theorem.

Proof of Lemma 3

For simplicity of presentation, let . By Formula (5.2.3) in Arnold et al (1992).

Equation (15) is therefore by isolating all the terms that include p and applying Lemma 2:

Similarly to the derivation of Lemma 2, . Hence,

Yielding,

In obtaining Equation (16), we assume that j>i. However, the formula is correct also for j=i: μ ii =i/(n+1), which is the same as E i 2 by the proof of Theorem 4.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Drezner, Z., Nickel, S. & Ziegler, HP. Stochastic analysis of ordered median problems. J Oper Res Soc 63, 1578–1588 (2012). https://doi.org/10.1057/jors.2012.2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2012.2

Keywords

Navigation