The zone-constrained location problem on a network. (English) Zbl 0732.90048
Summary: We consider the m-median and m-center problems on a network, subject to zone-type constraints. These constraints require that at least one server be located in each one of several perspecified zones that may overlap. The zones may be municipal districts, geographical zones, equity-type zones and so on. Special cases of the problem include the m-medi-center problem and the m-center (or m-median) problem with user-dependent distance constraints. The paper includes a relaxation algorithm where in each step of the algorithm a relaxed problem is solved. For the m-center problem with user-dependent distance constraints the relaxation algorithm can be refined by taking advantage of an available method to solve the relaxed problem. Computational experience suggests that the algorithm performs well for large problems.
MSC:
| 90B80 | Discrete location and assignment |
| 90C35 | Programming involving graphs or networks |
| 90-08 | Computational methods for problems pertaining to operations research and mathematical programming |
References:
| [1] | Berman, O.; Yang, E., Medi-center location problems, (Working Paper 89-003 (1989), College of Management, University of Massachusetts: College of Management, University of Massachusetts Boston, MA), to appear in Journal of the Operational Research Society · Zbl 0733.90041 |
| [2] | Chen, R.; Handler, G. Y., The conditional \(p\)-center problem in the plane, (Working Paper 889/86 (1986), Faculty of Management, Tel-Aviv University: Faculty of Management, Tel-Aviv University Tel-Aviv, Israel) · Zbl 0769.90061 |
| [3] | Church, R. L., Absolute median of a graph and a \(p\)-median problem with the maximum distance constraints (1976), Department of Civil Engineering, University of Tennessee: Department of Civil Engineering, University of Tennessee Knoxville, TN |
| [4] | Church, R. L., The regionally constrained \(p\)-median problem, (presented in the North American Meeting of Regional Sciences. presented in the North American Meeting of Regional Sciences, Geographical Analysis (January 1990)), to appear in |
| [5] | Einav, D., Multi objective problems on networks, (M.S. Thesis (August 1986), Faculty of Management, Tel-Aviv University: Faculty of Management, Tel-Aviv University Tel-Aviv, Israel) |
| [6] | Erlenkotter, D., A dual-based procedure for uncapacitated facility location, Operations Research, 26, 992-1009 (1978) · Zbl 0422.90053 |
| [7] | Hakimi, S. L., Optimal locations of switching centers and the absolute centers and medians of a graph, Operations Research, 12, 450-459 (1964) · Zbl 0123.00305 |
| [8] | Halpern, J., The location of a center-median convex combination on an undirected tree, Journal of Regional Science, 16, 237-245 (1976) |
| [9] | Handler, G. Y., Medi-centers of a tree, Transportation Science, 19, 247-260 (1985) · Zbl 0618.90029 |
| [10] | Handler, G. Y., Complexity and efficiency in minimax network location, (Christofides, N.; etal., Combinatorial Optimization (1979), Wiley: Wiley New York), 281-314 · Zbl 0427.90082 |
| [11] | Handler, G. Y.; Mirchandani, P. B., Location on Networks: Theory and Algorithms (1979), MIT Press: MIT Press Cambridge, MA · Zbl 0533.90026 |
| [12] | Hillsman, E. L.; Rushton, G., The \(p\)-median problem with maximum distance constraints: A comment, Geographical Analysis, 5, 85-89 (1975) |
| [13] | Khumawala, B. M., An efficient algorithm for the \(p\)-median problem with maximum distance constraints, Geographical Analysis, 5, 309-321 (1973) |
| [14] | Minieka, E., The \(m\)-center problem, SIAM Review, 12, 138-139 (1970) · Zbl 0193.24204 |
| [15] | Minieka, E., Conditional centers and medians on a graph, Networks, 10, 265-272 (1980) |
| [16] | Narula, S. C.; Ogbu, U. I.; Samuelson, H. M., An algorithm for the \(p\)-median problem, Operations Research, 25, 709-713 (1977) · Zbl 0372.90096 |
| [17] | Tansel, B. C.; Francis, R. L.; Lowe, J., Location on networks: A survey. Part I: The \(p\)-centers and \(p\)-median problems, Management Science, 29, 482-497 (1983) · Zbl 0513.90022 |
| [18] | Toregas, C. R.; ReVelle, C., Optimal location under time or distance constraints, Papers of the Regional Science association, 28, 133-144 (1972) |
| [19] | Weaver, J. R.; Church, R. L., A location model based on multiple metrics and multiple facility assignment, Transportation Research, 20B, 283-296 (1986) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
