Relajacion lagrangeana para el problema de particionamiento de áreas geográficas

• Díaz García, Juan Antonio ^[1] ; Bernabé Loranca, María Beatriz ^[2] ; Luna Reyes, Dolores Edwiges ^[1] ; Olivares Benítez, Elías ^[3] ; José Luis Martínez Flores ^[3]
  1. [1] Universidad de las Américas

     Universidad de las Américas

     México

     
  2. [2] Benemérita Universidad Autónoma de Puebla

     Benemérita Universidad Autónoma de Puebla

     México

     
  3. [3] Universidad Popular Autónoma del Estado de Puebla

     Universidad Popular Autónoma del Estado de Puebla

     México

     

  Mostrar afiliaciones +
• Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 19, Nº. 2, 2012
• Idioma: español
• DOI: 10.15517/rmta.v19i2.1332
• Títulos paralelos:
  • Lagrangean relaxation for the geographical partitioning problem
• Enlaces
  • Texto completo
• Resumen
  • español

    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.Palabras clave: particionamiento, relajación Lagrangena, heurísticas.Mathematics Subject Classification: 90C59, 62H30, 91C20.

  • English

    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.Keywords: partitioning, Lagrangean relaxation, heuristics.Mathematics Subject Classification: 90C59, 62H30, 91C20.

• Referencias bibliográficas
  • 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...
  • Christofides, N.; Beasley, J.E. (1982) “A tree search algorithm for the p-median problem”, European Journal of Operational Research 10: 196–204....
  • 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”,...
  • Kariv O.; Hakimi, S.L. (1979) “An algorithmic approach to network location problems. II: the p-medians”. SIAM Journal of Applied Mathematics...
  • 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...
  • Zoltners, A.; Sinha, P. (2005) Sales territory design: thirty years of modeling and implementation. Marketing Science 24(3): 313–331.