Abstract
The problem considered in this paper is to find p locations for p facilities such that the weights attracted to each facility will be as close as possible to one another. We model this problem as minimizing the maximum among all the total weights attracted to the various facilities. We propose solution procedures for the problem on a network, and for the special cases of the problem on a tree or on a path. The complexity of the problem is analyzed, O(n) algorithms and an O(pn 3) dynamic programming algorithm are proposed for the problem on a path respectively for p=2 and p>2 facilities. Heuristic algorithms (two types of a steepest descent approach and tabu search) are proposed for its solution. Extensive computational results are presented.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Alp, O., Drezner, Z., & Erkut, E. (2003). An efficient genetic algorithm for the p-median problem. Annals of Operations Research, 122, 21–42.
Azar, Y., Epstein, L., Richter, Y., & Woeginger, G. (2004). All-norm approximation algorithms. Journal of Algorithms, 52, 120–133.
Baron, O., Berman, O., Krass, D., & Wang, Q. (2007). The equitable location problem on the plane. European Journal of Operational Research, 183, 578–590.
Baron, O., Berman, O., & Krass, D. (2008, accepted). Facility location with stochastic demand and constraints on waiting time. Manufacturing and Service Operations Management.
Beasley, J. E. (1990). OR-library—distributing test problems by electronic mail. Journal of the Operational Research Society, 41, 1069–1072. Also available at http://mscmga.ms.ic.ac.uk/jeb/orlib/pmedinfo.html.
Berman, O., & Larson, R. C. (1985). Optimal 2-facility network districting in the presence of queuing. Transportation Science, 19, 261–277.
Berman, O., & Drezner, Z. (2007). The multiple server location problem. Journal of the Operational Research Society, 58, 91–99.
Berman, O., Larson, R. C., & Parkan, C. (1987). The stochastic queue p-median problem. Transportation Science, 21, 207–216.
Chiyoshi, F., & Galvao, R. D. (2000). A statistical analysis of simulated annealing applied to the p-median problem. Annals of Operations Research, 96, 61–74.
Dear, R., & Drezner, Z. (2000). Applying combinatorial optimization metaheuristics to the golf scramble problem. International Transactions of Operations Research, 7, 331–347.
Drezner, Z. (Ed.). (1995). Facility location: a survey of applications and methods. New York: Springer.
Drezner, T., & Drezner, Z. (2001). A note on applying the gravity rule to the airline hub problem. Journal of Regional Science, 41, 67–73.
Drezner, T., & Drezner, Z. (2006). Multiple facilities location in the plane using the gravity model. Geographical Analysis, 38, 391–406.
Frederickson, G. N., & Johnson, D. B. (1984). Generalized selection and ranking: sorted matrices. SIAM Journal on Computing, 13, 14–30.
Gallo, G., Grigoriadis, M., & Tarjan, R. E. (1989). A fast parametric network flow problem. SIAM Journal on Computing, 18, 30–55.
Garey, M. R., & Johnson, D. (1979). Computers and intractability: a guide to the theory of NP-completeness. New York: Freeman.
Garfinkel, R. S., & Nemhauser, G. L. (1970). Optimal political districting by implicit enumeration techniques. Management Science, 16(8), B-495–B-508.
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, 13, 533–549.
Glover, F., & Laguna, M. (1997). Tabu search. Boston: Kluwer Academic.
Goldman, A. J. (1971). Optimal center location in simple networks. Transportation Science, 5, 212–221.
Hansen, P., & Mladenovic, N. (1997). Variable neighborhood search for the p-median. Location Science, 5, 207–226.
Hess, S., Weaver, J., Siegfeldt, H., Whelan, J., & Zitlau, P. (1965). Non-partisan political redistricting by computer. Operations Research, 13, 993–1006.
Horowitz, E., & Sahni, S. (1976). Exact and approximate algorithms for scheduling nonidentical processors. Journal of the ACM, 23, 317–327.
Kalcsics, J., Melo, T., & Nickel, S. (2002). Planning sales territories—a facility location approach. In ISOLDE IX Conference, Fredericton, New Brunswick, Canada, June 2002.
Kariv, O., & Hakimi, L. S. (1979). An algorithmic approach to network location problems. Part 2. The p-medians. SIAM Journal on Applied Mathematics, 37, 539–560.
Kirpatrick, S., Gelat, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220, 671–680.
Lenstra, J. K., Shmoys, D. B., & Tardos, E. (1990). Approximation algorithms for scheduling unrelated machines. Mathematical Programming, 46, 259–271.
Meholtra, A. A., Johnson, E. L., & Nemhauser, G. L. (1998). An optimization based heuristic for political districting. Management Science, 44, 1100–1114.
Mirchandani, P. B., & Francis, R. L. (Eds.). (1990). Discrete location theory. New York: Wiley.
Mladenovic, N., Labbe, M., & Hansen, P. (2003). Solving the p-center problem with tabu search and variable neighborhood search. Networks, 42, 48–64.
Mladenovic, N., Brimberg, J., Hansen, P., & Moreno-Perez, J. A. (2007). The p-median problem: a survey of metaheuristic approaches. European Journal of Operational Research, 179, 927–939.
Murray, A. T., & Church, R. L. (1996). Applying simulated annealing to location-planning models. Journal of Heuristics, 2, 31–53.
Rolland, E., Schilling, D. A., & Current, J. R. (1997). An efficient tabu search procedure for the p-median problem. European Journal of Operational Research, 96, 329–342.
Suzuki, A., & Drezner, Z. (2008, in press). The minimum equitable radius location problem with continuous demand. European Journal of Operational Research.
Teitz, M. B., & Bart, P. (1968). Heuristic methods for estimating the generalized vertex median of a weighted graph. Operations Research, 16, 955–961.
van Roy, T. J. (1986). A cross decomposition algorithm for capacitated facility location. Operations Research, 34, 145–163.
Wang, Q., Batta, R., & Rump, C. M. (2002). Algorithms for a facility location problems with stochastic customer demand and immobile servers. In O. Berman & D. Krass (Eds.), Annals of operations research : Vol. 111. Recent developments in the theory and applications of location models part II (pp. 17–34). Dordrecht: Kluwer Academic.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Berman, O., Drezner, Z., Tamir, A. et al. Optimal location with equitable loads. Ann Oper Res 167, 307–325 (2009). https://doi.org/10.1007/s10479-008-0339-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-008-0339-9