The p‐Compact‐regions Problem. Issue 3 (July 2014)

• Record Type: Journal Article
• Authors: Li, Wenwen; Church, Richard L.; Goodchild, Michael F.
• Is Part Of: Geographical analysis. Volume 46:Issue 3(2014)
• Page Start: 250
• Page End: 273
• Publication Date: 2014-07
• Subjects: Geography -- Methodology -- Periodicals; Electronic journals; 910.00182
• DOI: 10.1111/gean.12038
• Languages: English
• ISSNs: 0016-7363

Abstract

<abstract abstract-type="main"> <title> <x xml:space="preserve">Abstract</x> </title> <p>The p‐compact‐regions problem involves the search for an aggregation of <italic>n</italic> atomic spatial units into p‐compact, contiguous regions. This article reports our efforts in designing a heuristic framework—MERGE (memory‐based randomized greedy and edge reassignment)—to solve this problem through phases of dealing, randomized greedy, and edge reassignment. This MERGE heuristic is able to memorize (ME of MERGE) the potential best moves toward an optimal solution at each phase of the procedure such that the search efficiency can be greatly improved. A dealing phase grows seeded regions into a viable size. A randomized greedy (RG of MERGE) approach completes the regions' growth and generates a feasible set of p‐regions. The edge‐reassigning local search (E of MERGE) fine‐tunes the results toward better objectives. In addition, a normalized moment of inertia (NMI) is introduced as the method of choice in computing the compactness of each region. We discuss in detail how MERGE works and how this new compactness measure can be seamlessly integrated into different phases of the proposed regionalization procedure. The performance of MERGE is evaluated through the use of both a small and a large p‐compact‐regions problem motivated by modeling the regional economy of Southern California. We expect this work to contribute to the regionalization theory and practice literature. Theoretically, we formulate a new model for the family of p‐compact‐regions problems. The novel NMI introduced in the model provides an accurate, robust, and efficient measure of compactness, which is a key objective for p‐compact‐regions problems. Practically, we developed the MERGE heuristic, proven to be effective and efficient in solving this nonlinear optimization problem to near optimality.</p> <p>El problema de regiones compactas tipo p (<italic>p‐compact regions</italic>) consiste en la búsqueda de la agregación de n unidades espaciales atómicas que produzca regiones contiguas de tipo p‐compacto. Este artículo reporta los esfuerzos de los autores en el diseño de un marco heurístico MERGE (<italic>memory‐based randomized greedy and edge‐reassignment)</italic> el cual resuelve este problema a través de las fases de la negociación <italic>(dealing)</italic>, codicia aleatorizada <italic>(randomized greedy)</italic>, y la reasignación de bordes (<italic>edge reassignment</italic>). El heurístico MERGE es capaz de memorizar ( ME de MERGE) los mejo)res desplazamientos posibles hacia una solución óptima en cada fase del procedimiento de tal manera que la eficiencia de la búsqueda puede ser mejorada en gran medida. La fase de negociación crea regiones "sembradas" aleatoriamente y las hace crecer en diferentes tamaños . El componente de codicia aleatorio (RG de MERGE) completa la fase de crecimiento de las regiones y genera un conjunto factible de regiones tipo p. La reasignación de bordes se realiza vía una búsqueda local (E de MERGE) que afina los resultados con el fin the alcanzar los objetivos. Además, el enfoque propuesto aquí utiliza el momento de inercia normalizado (<italic>normalized momento of inertia</italic>‐NMI) como método para el cálculo de la compacidad de cada región. El artículo discute en detalle el funcionamiento de MERGE y cómo esta nueva medida compacidad puede integrarse perfectamente en las diferentes fases del procedimiento de regionalización propuesto. Para ilustrar y evaluar el desempeño de MERGE, el metodo es aplicado a dos problemas de <italic>p‐compact regions</italic>, uno grande y uno pequeño, basados en el modelado de la economía regional del sur de California. Los autores esperan que este trabajo contribuya a la literatura teórica y práctica de la regionalización. En términos teóricos, se formula un nuevo modelo de la familia de problemas de <italic>p‐compact regions</italic>. El NMI equipa al modelo con una novedosa forma de obtener una medida exacta, robusta y eficiente de compacidad, que es un objetivo clave para los problemas región compacta tipo p. En términos prácticos, se desarrolla MERGE, un procedimiento heurístico que ha demostrado ser eficaz y eficiente en la solución de este problema de optimización no lineal de manera casi óptima.</p> <p>p紧凑区域问题包含寻找一种聚集方法，将n个不可分割的空间单元集合成p紧凑的邻近区域。本文阐述了一种启发式架构MERGE(基于记忆的随机贪婪和边界再赋值算法)，通过处理、随机贪婪和边界再分配这几个阶段解决p紧凑问题。MERGE启发式框架能存储 处理过程每个阶段中，向一个最优解的潜在最佳移动方式，从而可极大地提升搜索效率。一个处理阶段可将种子区域生长到可行大小。而一个随机贪婪阶段能完成区域增长并生成p区域的可行集。在边界再分配的局部搜索阶段对结果进行微调以达到更好的目标。此外，引入标准化的惯性矩作为每个区域紧凑度计算的选择方法。本文详细讨论了MERGE的工作原理，以及这种新的紧凑度测算方法如何能无缝地整合到所提出的区域化流程的不同阶段。通过在南部加州区域经济建模中一小一大两个p紧凑区域问题的应用，对MERGE的性能进行评估，期望该工作能够对区域化理论和实践作出贡献。理论上，提出了可解决p紧凑区域这类问题的新模型。在模型中引入新颖的标准化惯性矩这一精确的、鲁棒的和有效的紧凑度度量方法，是解决p紧凑区域问题的关键目标；实践上，本文发展了MERGE启发式框架，并证明了它在解决这种非线性优化问题近优性的有效性和高效性。</p> </abstract>