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
Lagrangean relaxation for the geographical partitioning problem
PDF (Español (España))

Keywords

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

How to Cite

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). Lagrangean relaxation for the geographical partitioning problem. Revista De Matemática: Teoría Y Aplicaciones, 19(2), 169–181. https://doi.org/10.15517/rmta.v19i2.1332

Abstract

Among methodologies used in territory clustering, stand location-allocation and set partitioning models, to group small geographic areas, usually called “basic units” into a given number of larger groups called “territories”. The territory clustering problem is modeled as a p-median problem. A Lagrangean relaxation is used to obtain lower bounds to the optimal solution of the problem and a procedure is used to obtain upper bounds. In order to evaluate the performance of the proposed procedure, instances of two Mexico cities are used. The results obtained with the proposed method are compared to partitioning methods from the literature. According to the obtained results for the considered instances using different number of groups, optimal or near optimal solution are obtained with a reasonable amount of computer effort.

 

https://doi.org/10.15517/rmta.v19i2.1332
PDF (Español (España))

References

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.

Comments

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Copyright (c) 2012 Revista de Matemática: Teoría y Aplicaciones

Downloads

Download data is not yet available.