Finite Dominating Set for the p-Facility Cent-Dian Network Location Problem
-
1
Universidad de La Laguna
info
ISSN: 1105-5162
Year of publication: 1997
Volume: 11
Pages: 27-40
Type: Article
More publications in: Studies in Locational Analysis
Abstract
A dominating set for a location problem is a set of points that contains an optimal solution for all instances of the problem. The p-facility location problems on a network appear when the possible selections for locating the facilities are the sets of p points of the network. Hooker, Gar¯nkel and Chen [4] consider a theoretical result to extend the dominating set for the 1-facility problems to the corresponding p-facility problems, and apply this result to propose a ¯nite dominating set for the p-facility cent-dian problem on a network. The optimal solutions of the cent-dian problems are those minimizing a linear combination of the center and median objective functions. Since it is known that the set of vertices and local centers is a dominating set for the single facility cent-dian problem, they claim that it is also a dominating set for the p-facility cent-dian problem. We show a counterexample for p = 2 and give an alternative ¯nite dominating set for the p-facility cent-dian.We also provide a solution method that avoids the exhaustive search in all the sets of p points of this dominating set.
Bibliographic References
- [1] Hakimi, S.L., \Optimum Locations of Switching Center and the absolute Center and Medians of a Graph", Operations Research 12 (1964) 450-459.
- [2] Halpern, J., \The location of a cent-dian convex combination on an undirected tree", Journal of Regional Science 16 (1976) 237-245.
- [3] Halpern, J., \Finding Minimal Center Median Convex Combination (Cent-Dian) of a Graph", Management Science 24 (1978) 535-544.
- [4] Hooker, J.N., Gar¯nkel, R.S., and Chen, C.K., \Finite Dominating Sets For Network Location Problems", Operation Research 39 (1991) 100-118.
- [5] Moreno, J.A., \A Correction to the de¯nition of Local Center", European Journal of Operational Research 20 (1985) 382-385.