Modelo para la representación de redes y búsqueda de caminos óptimos en Sistemas de Información Geográfica

Model for network representation and optimal path search in Geographic Information Systems

Una de las funcionalidades presente en los sistemas de información geográfica es la búsqueda de caminosóptimos. En la actualidad, este tipo de funcionalidad se implementa sobre modelos que no garantizanescalabilidad y eficiencia cuando las redes son grandes.En este artículo se propone un modelo de representación de redes en Sistemas de Información Geográficabasado en el concepto de grafos reducidos. Este modelo permite realizar búsquedas de caminos óptimosen redes grandes de forma eficiente y escalable. Una característica relevante del modelo propuesto es laposibilidad de realizar análisis a escala en la red.

INTRODUCCIÓN

Desde un punto de vista práctico un Sistema de Información Geográfica (SIG) es un sistema informático capaz de gestionar datos geográficos georreferenciados. Por georreferenciados se entiende que estos datos tienen asociadas coordenadas geográficas (longitud, latitud). También deben facilitar la relación de datos de diversa índole (densidad de población, información financiera, etc.) con datos geográficos.

Un SIG está formado por cuatro componentes: hardware, software, datos y recursos humanos [1].

Como parte de los datos los mapas tienen vital importancia. De forma intuitiva se puede decir que un mapa es un modelo que representa el "mundo real" y se almacena utilizando varios formatos, por ejemplo: Shape [2], TAB [3], entre otros. Por otra parte, existen proyectos que utilizan el modelo relacional extendido con soporte de tipos de datos espaciales (punto, línea, polígono, etc.) para almacenar los mapas; tal es el caso del proyecto OpenStreetMap [4].

Existen dos tipos de datos en el ámbito de los SIG: el vectorial y el raster. En el primer caso se utilizan puntos, líneas (definidas por una serie de puntos) y polígonos (delimitados por líneas) para representar los objetos geográficos. En el segundo caso los datos consisten en filas de celdas; a cada celda se pueden asociar datos de diversos tipos (medida, nombre, etc.) [5].

Para realizar análisis de redes se utilizan los SIG vectoriales, o sea, aquellos que usan el tipo de datos vectorial para representar la información geográfica; por lo que en el marco de este trabajo solo se hará referencia a este tipo de sistema.

Varios SIG cuentan con funcionalidades para el análisis de redes; entre estas se pueden mencionar las siguientes:

•     ¿Cuál es el camino óptimo entre x e y?

•     ¿Cuál es el camino de costo mínimo entre x e y según un determinado criterio?