Uso de Búsqueda Dispersa para problemas de localizaciónaplicación a recursos sanitarios en la provincia de Burgos

  1. Joaquín A. Pacheco
  2. Silvia Casado
Revista:
Rect@: Revista Electrónica de Comunicaciones y Trabajos de ASEPUMA

ISSN: 1575-605X

Año de publicación: 2004

Volumen: 5

Número: 1

Páginas: 83-107

Tipo: Artículo

DIALNET GOOGLE SCHOLAR lock_openDialnet editor

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

Resumen

En este trabajo se propone un algoritmo para dos problemas de localización de facilidades. Este algoritmo está basado en la estrategia denominada búsqueda dispersa (scatter search, SS). El primer problema de localización es el conocido problema del pcentro. El segundo es el problema del Maximum Set Covering (MSC). El algoritmo scatter search propuesto incorpora diferentes estrategias, como búsqueda local, GRASP y path relinking. En principio se desarrolla el algoritmo para el problema del p-centro y después se adapta para el problema del MSC. El objetivo es obtener soluciones de calidad para un número bajo de facilidades. Se realizan una serie de experiencias computacionales que muestran que nuestro algoritmo para el problema del p-centro da resultados similares a otras recientes estrategias en un tiempo de computación menor . En el caso del problema del MSC alcanza soluciones de muy buena calidad (la desviación media con respecto a cotas inferiores menor a un 1%). Se muestran además aplicaciones con datos reales a la localización de recursos sanitarios en la provincia de Burgos (España).

Referencias bibliográficas

  • BEASLEY, J. E., (1990). “OR-Library: Distributing Test Problems by Electronic Mail” Journal of the Operational Research Society, 41, 1069-1072.
  • CAMPOS, V., GLOVER, F., LAGUNA, M. y MARTÍ, R. (2001). “An Experimental Evaluation of a Scatter Search for the Linear Ordering Problem,” Journal of Global Optimization, vol. 21, pp. 397-414.
  • DONGARRA, J.J. (2003). “Performance of various computers using standard linear equations software”. Technical Report CS-89-85, University of Tennessee Computer Science Department.
  • FEO, T.A. y RESENDE, M.G.C., (1989). “A Probabilistic heuristic for a computationally difficult Set Covering Problem”. Operations Research Letters, 8, 67-71.
  • FEO, T.A. y RESENDE, M.G.C., (1995). “Greedy Randomized Adaptive Search Procedures”. Journal of Global Optimization, vol. 2, pp 1-27.
  • GLOVER, F. (1998). “A Template for Scatter Search and Path Relinking,” in Artificial Evolution, Lecture Notes in Computer Science, 1363, J.-K. Hao, E. Lutton, E. Ronald, M. Schoenauer and D. Snyers (Eds.) Springer, pp. 13-54.
  • GLOVER, F. y LAGUNA, M. (1997). “Tabu Search”. Kluwer Academic Publishers.
  • GLOVER, F., LAGUNA, M. y MARTÍ, R. (2000). “Fundamentals of Scatter Search and Path Relinking,” Control and Cybernetics, vol. 39, no. 3, pp. 653-684.
  • HANSEN, P. y MLADENOVIC, N. (1997). “Variable neigborhhod search for the pMedian”. Location Science, 5, pp. 207-226.
  • INSALUD (2001) Memoria de Castilla y León. Insalud. CD-ROM. D.L. VA-532/2001.
  • KARIV, O. y HAKAMI, S.L. (1979). “And algorithmic approach to network location problems. Part I: The P-center Problem”. SIAM J. Appl. Math., 37, pp. 513-538.
  • LAGUNA, M. (2002). “Scatter Search,” in Handbook of Applied Optimization, P. M. Pardalos and M. G. C. Resende (Eds.), Oxford University Press, New York, pp. 183- 193.
  • LAGUNA, M. y MARTÍ, R. (1999). “GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization”. INFORMS Journal on Computing, vol. 11, no. 1, pp. 44-52.
  • LAGUNA, M. y MARTÍ, R (2003). "Scatter Search. Methodology and Implementations" in C. Kluwer Academic Publishers.
  • LOVE, R.F., MORRIS, J.G. y WESOLOWSKY, G.O. (1988). Facilities Location: Models and Methods. North Holland.
  • MLADENOVIC_, N., LABBE, M. y HANSEN, P. (2001). “Solving the p-Center Problem with Tabu Search and Variable Neigborhood Search”. Les Cahiers du GERAD, G-2000-35.
  • MLADENOVIC, N., MORENO, J.P. y MORENO-VEGA, J. (1995). “Tabu search in solving the p-facility location-allocation problems”. Les Cahiers du GERAD, G-95- 38.
  • MLADENOVIC, N., MORENO, J.P. y MORENO-VEGA, J. (1996). “A ChainInterchange Heuristic Method”. Yugoslav. Journal Operations Research, 6 (1), pp. 41-54.
  • MULVEY J.M. y BECK M.P. (1984). "Solving Capacitated Clustering Problems". European Journal Operations Research, 18 (3), pp. 339- 348.
  • PITSOULIS, L.S. y RESENDE, M.G.C., (2002). “Greedy Randomized Adaptive Search Procedures” in Handbook of Applied Optimizaton, P. M. Pardalos and M. G. C. Resende (Eds.), Oxford University Press, pp. 168-182.
  • RESENDE, M. G. C. (1998). "Computing Approximate Solutions of the Maximum Covering Problem using GRASP". J. of Heuristics, vol. 4, pp. 161-171.
  • RESENDE, M. G. C. y RIBEIRO, C.C. (2003). “A GRASP with path-relinking for private virtual circuit routing”, Networks, vol. 41, pp. 104-114.
  • RIBEIRO C.C., UCHOA E. y WERNEK R.F. (2002). "A Hybrid GRASP with Perturbations for the Steiner Problem in Graphs". INFORMS Journal on Computing, vol. 14(3), pp.228-246.
  • WHITAKER, R. (1983) “A fast algorithm for the greedy interchange for large-scale clustering and median location problems”. INFOR 21, pp. 95-108.
Fuente de los datos: Dialnet