Un algoritmo para el calculo del conjunto dominante finito del problema generalizado de la p-centdiana

  1. Canós Darós, Lourdes
  2. Martínez Romero, María Luisa
  3. Mocholi Arce, Manuel
Revista:
Rect@: Revista Electrónica de Comunicaciones y Trabajos de ASEPUMA

ISSN: 1575-605X

Año de publicación: 2005

Volumen: 6

Número: 1

Páginas: 87-112

Tipo: Artículo

DIALNET GOOGLE SCHOLAR lock_openDialnet editor

Otras publicaciones en: Rect@: Revista Electrónica de Comunicaciones y Trabajos de ASEPUMA

Resumen

Los problemas de localización tratan de averiguar la ubicación de las instalaciones de una empresa de modo que se minimicen los costes o se maximicen los beneficios. Dos de los modelos más utilizados en localización en redes son el problema de la p-mediana y el problema del p-centro. El primero consiste en minimizar la suma total de las distancias ponderadas, mientras que el segundo trata de minimizar la máxima distancia ponderada desde un centro de servicio hasta sus usuarios asignados. El objetivo del problema de la p-mediana hace que sea eficiente pero no equitativo, mientras que la cota implícita en el problema del p-centro lo convierte en equitativo pero no eficiente. Para combinar ambos aspectos, aparece en la década de los 70 un nuevo problema, el de la p-centdiana, cuya función objetivo es una mezcla de las dos anteriores. En este trabajo consideramos el problema generalizado de la p-centdiana sobre una red en la que los pesos asociados al p-centro y a la p-mediana no son necesariamente iguales. Mientras que los conjuntos dominantes finitos de los dos primeros problemas son relativamente sencillos de calcular, esto no es así para la p-centdiana generalizada. Proponemos un algoritmo que nos permitirá calcular este conjunto

Referencias bibliográficas

  • BERMAN, O y YANG, E,K (1991), Medi-centre location problems, Journal of the Operational Research Society, vol, 42, pp, 313-322,
  • BERMAN, O; EINAV, D, y HANDLER, G, (1991), The zone-constrained location problem on a network, European Journal of Operational Research, vol, 53, pp, 14-24,
  • ERKUT, E y BOZKAYA, B, (1999), Analysis of aggregation errors for the p-median problem, Computers & Operations Research, vol, 26, pp, 1075-1096,
  • FRANCIS, R.L.; LOWE, T.J. y TAMIR, A. (2002), Demand point aggregation for location models en: DREZNER, Z. y HAMACHER, H.W. (Ed.) Facility Location. Applications and theory, Springer, Berlin-Heidelberg.
  • GAREY, M,R, y JOHNSON, D,S, (1979), Computers and intractability: a guide to the theory of NP-completeness, Freeman, Nueva York,
  • HAKIMI, S,L, (1964), Optimum locations of switching centers and the absolute centers and medians of a graph, Operations Research, vol, 12, pp, 450-459,
  • HAKIMI, S,L, (1965), Optimum distribution of switching centers in a communication network and some related graph theoretic problems, Operations Research, vol, 13, pp, 462-475,
  • HALPERN, J, (1976), The location of a center-median convex combination on an undirected tree, Journal of Regional Science, vol, 16, pp, 237-245,
  • HALPERN, J, (1978), Finding minimal center-median convex combination (cent-dian) of a graph, Management Science, vol, 24, pp, 535-544,
  • HALPERN, J, (1980), Duality in the cent-dian of a graph, Operations Research, vol, 28, pp, 722-735,
  • HANDLER, G,Y, (1985), Medi-centers of a tree, Transportation Science, vol, 19, pp, 246-260,
  • HANSEN, P,; LABBÉ, M, y THISSE, J,F, (1991), From the median to the generalized center, RAIRO, vol, 25, pp, 73-86,
  • HOOKER, J,N,; GARFINKEL, R,S, y CHEN, C,K, (1991), Finite dominating sets for network location problems, Operations Research, vol, 39, pp, 100-118,
  • MLADENOVIC, N,; LABBÉ, M, y HANSEN, P, (2000), Solving the p-center problem with tabu search and variable neighborhood search, documento de trabajo, disponible en <smg,ulb,ac,be>
  • OGRYCZAK, W, (1997), On cent-dians of general networks, Location Science, vol, 5, pp, 15-28,
  • PÉREZ BRITO, D, y MORENO PÉREZ, J,A, (2000), The generalized p-centdian on network, TOP, vol, 8, pp, 265-285,
  • PÉREZ BRITO, D,; MORENO PÉREZ, J,A, y RODRÍGUEZ MARTÍN, I, (1997), Finite dominating set for the p-facility cent-dian network location problem, Studies in Locational Analysis, vol, 11, pp, 27-40,
  • TAMIR, A,; PÉREZ BRITO, D, y MORENO PÉREZ, J,A, (1998), A polynomial algorithm for the p-centdian on a tree, Networks, vol, 32, pp, 255-262,
Fuente de los datos: Dialnet