Revista de Matemática: Teoría y Aplicaciones ISSN Impreso: 1409-2433 ISSN electrónico: 2215-3373

OAI: https://revistas.ucr.ac.cr/index.php/matematica/oai
Relajacion lagrangeana para el problema de particionamiento de áreas geográficas
PDF

Palabras clave

partitioning
Lagrangean relaxation
heuristics
particionamiento
relajación Lagrangena
heurísticas

Cómo citar

Díaz García, J. A., Bernábe Loranca, M. B., Luna Reyes, D. E., Olivares Benítez, E., & Martínez Flores, J. L. (2012). Relajacion lagrangeana para el problema de particionamiento de áreas geográficas. Revista De Matemática: Teoría Y Aplicaciones, 19(2), 169–181. https://doi.org/10.15517/rmta.v19i2.1332

Resumen

Entre las metodologías utilizadas en el particionamiento territorial, destacan los modelos de localización-asignación (“location-allocation”) y los de particionamiento de conjuntos ("set partitioning”), que agrupan pequeñas áreas geográficas llamadas unidades básicas en un número dado de grupos geográficos más grandes, denominados territorios. El problema de particionamiento territorial se modela como un problema de la p-mediana. Se utiliza un enfoque derelajación Lagrangeana para obtener cotas inferiores de la solución óptima y un procedimiento para la obtención de cotas superiores. Para evaluar el desempeño de la metología propuesta, se utilizan instancias de dos ciudades de México. Los resultados obtenidos se comparan con otros métodos de particionamiento de la literatura. De acuerdo con los resultados obtenidos para estas instancias, utilizando distintos números de grupos, se observa que se pueden obtener soluciones factibles de muy buena calidad con un esfuerzo computacional razonable.

 

https://doi.org/10.15517/rmta.v19i2.1332
PDF

Citas

Avella, P.; Sassanol, A.; Vasil’ev, I. (2007) ‘Computational study of large-scale p-Median problems”, Mathematical Programming 109: 89–114.

Bernábe, M.B.; Espinosa, J.E.; Ramı́rez, J.; Osorio, M.A. (2011) “A statistical comparative analysis of simulated annealing and variable neighborhood search for the geographic clustering problem”, Computación y Sistemas 14(3): 295–308.

Christofides, N.; Beasley, J.E. (1982) “A tree search algorithm for the p-median problem”, European Journal of Operational Research 10: 196–204. Floyd, R.W. (1962) “Algorithm, 97 - shortest path”, Communications of the ACM 5: 345.

Guignard, M. (2003) “Lagrangean Relaxation”, TOP 11(2): 151–228.

Hess, S.W.; Samuels, S.A. (1971) “Experiences with a sales districting model: criteria and implementation”, Management Science 18(4): 41–54.

Kalcsics, J.; Nikel, S.; Schröder, M. (2005) “Toward a unified territory design approach - applications, algorithms, and GIS integration”, TOP 13(1): 1–74.

Kariv O.; Hakimi, S.L. (1979) “An algorithmic approach to network location problems. II: the p-medians”. SIAM Journal of Applied Mathematics 37(3): 539–560.

Kaufman, L.; Rousseeuw, P.J. (2008) Finding Groups in Data: An Introduction to Cluster Analysis, John Wiley Online.

Reese, J. (2006) “Solution methods for the p-median problem: An annotated bibliography”, Nerworks 48(3): 125–142.

Zamora, E. (2006) Implementación de un Algoritmo Compacto y Homogéneo para la Clasificación de AGEBs bajo una Intefaz Gráfica. Tesis de Ingeniería en Ciencias de la Computación, Benemerita Universidad Autónoma de Puebla, Puebla, México.

Zoltners, A.; Sinha, P. (2005) Sales territory design: thirty years of modeling and implementation. Marketing Science 24(3): 313–331.

Comentarios

Descargas

Los datos de descargas todavía no están disponibles.

Métricas

Cargando métricas ...