Finite Dominating Set for the p-Facility Cent-Dian Network Location Problem

  1. Dionisio Pérez Brito 1
  2. José Andrés Moreno Pérez 1
  3. Inmaculada Rodríguez Marín 1
  1. 1 Universidad de La Laguna
    info

    Universidad de La Laguna

    San Cristobal de La Laguna, España

    ROR https://ror.org/01r9z8p25

Revista:
Studies in Locational Analysis

ISSN: 1105-5162

Año de publicación: 1997

Volumen: 11

Páginas: 27-40

Tipo: Artículo

GOOGLE SCHOLAR

Otras publicaciones en: Studies in Locational Analysis

Resumen

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.

Referencias bibliográficas

  • [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.