Área de agregación en el mapa de generalización de la programación entera mixta

...

La programación entera-mixta ha sido aplicada con frecuencia a problemas de asignación espacial, por ejemplo, territorio de ventas (alineación Zoltners y Sinha, 1983). En muchos de estos problemas, el tamaño compacto y la contigüidad de las regiones de salida son criterios importantes. Dado que estos criterios también son importantes para el mapa de generalización, podemos reutilizar algunas de las formulaciones de programación entera mixta existentes. Por otro lado, algunas de las innovaciones que presentamos pueden ser interesantes no sólo en el contexto de la generalización del mapa, sino también en el contexto general de problemas de asignación espacial. En particular, presentamos un programa entero mixto (MIP) basado en el flujo que nos permite agrupar un conjunto de unidades de asignación mínima en distritos compactos y contiguos de forma óptima que satisfagan las restricciones de tamaño. Este MIP se las arregla con una serie lineal de variables y limitaciones, sin requerir un conjunto de centros de distrito predefinidos. Además, la heurística que presentamos puede ser exitosa para muchos problemas de asignación espacial.

El esbozo del artículo es como sigue. Debemos revisar primero los enfoques existentes para la agregación en la generalización del mapa y esbozar nuestra noción de los indicadores de calidad de relevancia. A continuación, nos dan una rápida introducción a los conceptos básicos de la optimización técnica y aplicamos las diferencias fundamentales entre esta técnica y el imperante método iterativo. Presentamos una definición formal del problema, una prueba de nuestras formulaciones NPhardness, MIP, y heurística que abordaran con éxito la gran complejidad del problema.

Ofrecemos tres apéndices como complementación del material on-line. Apéndice A bocetos los conceptos básicos de programación entero mixto. El apéndice B presenta nuestro MIP basado en el flujo que nos permite resolver los pequeños problemas de instancias con la prueba de optimalidad. El apéndice C presenta una gran muestra procesada con nuestra heurística.

- Agregación en la generalización del mapa.

Según Timpf (1998), la agregación más común es la jerarquía que existe entre objetos de diferentes escalas: como parte de la abstracción de datos, un grupo de objetos, por ejemplo, pequeñas áreas de bosques, se sustituye por un único objeto en menor escala. La definición de tales grupos es una tarea clave de la generalización del mapa que ha sido investigada por diferentes tipos de objetos, por ejemplo, edificios e islas. La agrupación se hace a menudo de acuerdo con los principios de la percepción humana, que en las primeras obras de psicología, eran subsumidas por leyes de la denominada teoría de la Gestalt. Por ejemplo, la agrupación de objetos se realiza según su proximidad. En nuestro enfoque consideramos este criterio midiendo la compacidad de las formas, es decir, partes del mismo agregado debe estar cerca de un centro común.

Varios investigadores han propuesto sencillos algoritmos iterativos para la agregación de áreas en una partición planar. Un enfoque común es seleccionar de forma iterativa un área de la conjunto de datos y para combinar a uno de sus vecinos. Este vecino es seleccionado de acuerdo a una medida de compatibilidad local, por ejemplo, una función de clase similitudes y longitudes de frontera común. Algoritmo 1 formaliza el enfoque iterativo de forma bastante general.

El algoritmo termina cuando todas las zonas tienen el tamaño suficiente para la escala de destino.

Para algoritmos similares, Podrenek (2002) y van Smaalen (2003) definen criterios que son evaluado en cada paso, con el fin de seleccionar las áreas que van a ser agregadas. Jaakkola (1997) aplica un algoritmo de agregación iterativo similar dentro de un sistema para la generalización de mapas de cobertura terrestre basada en raster. Asimismo, Cheng y Li (2006) combinación de áreas que son demasiado pequeñas, con vecinos. Comparan dos ajustes diferentes de este método. En la primera configuración, el vecino es seleccionado de acuerdo a su tamaño; en la segunda opción, se selecciona de acuerdo con la longitud de la frontera común. Con la primera opción, Cheng y Li (2006) observan para un dataset que 12,3% del total del área del mapa cambia su clase. Se refieren a esta medida como "coherencia semántica'. Por supuesto, estos valores dependen de las características del conjunto de datos y los umbrales definidos para la escala de destino. En cualquier caso, los experimentos muestran que la cantidad de cambio de clase puede ser considerable.

Elaboramos un conjunto de datos desde la base de datos topográficos oficial alemana ATKIS a escala 1:50.000 (DLM 50) con 1 Algoritmo para satisfacer el área que los umbrales de las especificaciones existentes para la escala 1:250.000 de destino. La figura 1 muestra la entrada para la agregación de algoritmo y el resultado que se obtiene seleccionando el prójimo de acuerdo a la clase de valores de similitud. Aunque el algoritmo produce un conjunto de datos claramente menos desordenados, observamos una cierta deficiencia: cada una de las zonas de asentamiento rojos en la muestra son demasiado pequeñas para la escala objetivo 1: 250.000. Sin embargo, un cartógrafo crearía probablemente una solución de tamaño suficiente como su volumen. Desde Algoritmo 1 es codicioso y sólo toma en cuenta los vecinos directos, es poco probable que los rendimientos den soluciones de tan alta calidad. Como consecuencia de ello, la solución está perdida y relativamente grandes partes de la muestra cambian sus clases. Ejemplos como este nos motivan a enfocar el problema de optimización global.

- La coherencia lógica, la exhaustividad y la precisión semántica.

Consideramos tres elementos diferentes de calidad de los datos espaciales en nuestro enfoque, a saber, la coherencia lógica, la exhaustividad y la precisión semántica. Una introducción a los aspectos de la calidad está dado por Morrison (1995).

La coherencia lógica implica el cumplimiento de las especificaciones de la base de datos, es decir, necesitamos asegurar las características estructurales del modelo de datos y satisfacer las restricciones sobre sus características. En nuestro caso el dataset generalizado debe ser una partición planar. Las especificaciones suelen definir criterios de selección de las zonas en función de su tamaño, por ejemplo, un bosque en el DLM ATKIS 250 no debe ser inferior a 400.000 m2. Vemos criterios tales como las restricciones, que deben cumplirse en cualquier caso.

Además, podemos tomar un