Skip to main content
SpringerLink
Log in

Algorithms for a Facility Location Problem with Stochastic Customer Demand and Immobile Servers

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

This paper studies a facility location problem with stochastic customer demand and immobile servers. Motivated by applications to locating bank automated teller machines (ATMs) or Internet mirror sites, these models are developed for situations in which immobile service facilities are congested by stochastic demand originating from nearby customer locations. Customers are assumed to visit the closest open facility. The objective of this problem is to minimize customers' total traveling cost and waiting cost. In addition, there is a restriction on the number of facilities that may be opened and an upper bound on the allowable expected waiting time at a facility. Three heuristic algorithms are developed, including a greedy-dropping procedure, a tabu search approach and an ε-optimal branch-and-bound method. These methods are compared computationally on a bank location data set from Amherst, New York.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. I. Averbakh and O. Berman, Locating flow-capturing units on a network with multicounting and diminishing returns to scale, European Journal of Operational Research 91 (1996) 495-506.

    Google Scholar 

  2. O. Berman, The maximizing market-size discretionary facility location problem with congestion, Socio-Economic Planning Sciences 29(1) (1995) 39-46.

    Google Scholar 

  3. O. Berman, M.J. Hodgson and D. Krass, Flow-interception problems, in: Facility Location: A Survey of Applications and Methods, ed. Z. Drezner, Springer Series in Operations Research (Springer, New York, 1995).

    Google Scholar 

  4. O. Berman, R.C. Larson and S.S. Chiu, Optimal server location on a network operating as an M/G/1 queue, Operations Research 33 (1985) 746-771.

    Google Scholar 

  5. O. Berman, R.C. Larson and N. Fouska, Optimal location of discretionary service facilities, Transportation Science 26 (1992) 201-211.

    Google Scholar 

  6. O. Boxma, J. Kan, A. Rinnooy and M. van Vliet, Machine allocation problems in manufacturing networks, European Journal of Operational Research 45 (1990) 47-54.

    Google Scholar 

  7. M.L. Brandeau and S.S. Chiu, A unified family of single-server queueing location models, Operations Research 38 (1990) 1034-1044.

    Google Scholar 

  8. M.S. Daskin, Network and Discrete Location: Models, Algorithms, and Applications (Wiley, New York, 1995).

    Google Scholar 

  9. M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979).

    Google Scholar 

  10. L. Green and D. Guha, Note: On the efficiency of imbalance in multi-facility multi-server service systems, Management Science 41 (1995) 179-187.

    Google Scholar 

  11. D. Gross and C.M. Harris, Fundamentals of Queueing Theory (Wiley, New York, 1998).

    Google Scholar 

  12. M.J. Hodgson, A flow-capturing location-allocation model, Geographical Analysis 22 (1990) 270-279.

    Google Scholar 

  13. M.J. Hodgson and O. Berman, A billboard location model, Geographical and Environmental Modeling 1 (1997) 25-43.

    Google Scholar 

  14. B. Li, M.J. Golin, G.F. Italiano, X. Deng and K. Sohraby, On the optimal placement of web proxies in the Internet, in: Proceedings of the INFOCOM '99 (1999) pp. 1282-1290.

  15. V. Marianov and C. ReVelle, The queueuing probabilistic location set covering problem and some extensions, Socio-Economic Planning Sciences 28 (1994) 167-178.

    Google Scholar 

  16. V. Marianov and C. ReVelle, Siting emergency services, in: Facility Location: A Survey of Applications and Methods, ed. Z. Drezner, Springer Series in Operations Research (Springer, New York, 1995).

    Google Scholar 

  17. P.B. Mirchandani and R.L. Francis, Discrete Location Theory (Wiley, New York, 1990).

    Google Scholar 

  18. S.Y. Prasad and R. Batta, Efficient facility locations on a tree network operating as a FIFO M/G/1 queue, Networks 23 (1993) 597-603.

    Google Scholar 

  19. C. ReVelle and K. Hogan, The maximum reliability location problem and ?-reliable p-center Problem: Derivatives of the probabilistic location set covering problem, Annals of Operations Research (1989) 155-174.

  20. J.G. Shanthikumar and D.D. Yao, Optimal server allocation in a system of multi-server stations, Management Science 33 (1987) 1173-1191.

    Google Scholar 

  21. Q. Wang, Discrete facility location design with stochastic customer demand and immobile servers, Ph.D. dissertation, University at Buffalo, State University of New York (2000).

Download references

Author information

Authors and Affiliations

  1. Department of Industrial Engineering, University at Buffalo, State University of New York, 342 Lawrence D. Bell Hall, Buffalo, NY, 14260-2050, USA

    Qian Wang, Rajan Batta & Christopher M. Rump

Authors
  1. Qian Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rajan Batta
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Christopher M. Rump
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wang, Q., Batta, R. & Rump, C.M. Algorithms for a Facility Location Problem with Stochastic Customer Demand and Immobile Servers. Annals of Operations Research 111, 17–34 (2002). https://doi.org/10.1023/A:1020961732667

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1020961732667

Search

Navigation