En el análisis espacial y los sistemas de información geográfica , el análisis de costo-distancia o el análisis de ruta de costo es un método para determinar una o más rutas óptimas de viaje a través del espacio no restringido (bidimensional). [1] La solución óptima es aquella que minimiza el costo total de la ruta, basada en un campo de densidad de costo (costo por unidad lineal) que varía en el espacio debido a factores locales. Por lo tanto, se basa en el principio geográfico fundamental de fricción de la distancia . Es un problema de optimización con múltiples soluciones de algoritmos deterministas , implementadas en la mayoría del software GIS.
Los diversos problemas, algoritmos y herramientas del análisis de costo-distancia operan en un espacio bidimensional sin restricciones, lo que significa que una ruta puede tener cualquier forma. También pueden surgir problemas similares de optimización de costes en un espacio limitado, especialmente una red lineal unidimensional , como una red de carreteras o de telecomunicaciones . Aunque son similares en principio, los problemas en el espacio de la red requieren algoritmos muy diferentes (generalmente más simples) para resolver, adoptados en gran parte de la teoría de grafos . La colección de herramientas SIG para resolver estos problemas se denomina análisis de redes .
Historia
Los seres humanos parecen tener un deseo innato de viajar con un mínimo de esfuerzo y tiempo. Las carreteras históricas, incluso antiguas, muestran patrones similares a los que generarían los algoritmos computacionales modernos, viajando directamente a través de espacios planos, pero curvándose alrededor de montañas, cañones y vegetación espesa.
Sin embargo, no fue hasta el siglo XX que los geógrafos desarrollaron teorías para explicar la optimización de esta ruta y algoritmos para reproducirla. En 1957, durante la revolución cuantitativa en geografía, con su propensión a adoptar principios o formalismos matemáticos de las ciencias "duras" (conocidas como física social ), William Warntz usó la refracción como una analogía de cómo minimizar el costo de viaje hará que las rutas de transporte cambien de dirección. en el límite entre dos paisajes con una fricción de distancia muy diferente (por ejemplo, emergiendo de un bosque a una pradera). [2] Su principio de "movimiento parsimonioso", cambiar de dirección para minimizar el costo, fue ampliamente aceptado, pero la analogía de la refracción y las matemáticas ( ley de Snell ) no lo fueron, en gran parte porque no escala bien en situaciones geográficas normalmente complejas. [3]
Warntz y otros adoptaron luego otra analogía que resultó mucho más exitosa en la situación común en la que el costo de viaje varía continuamente en el espacio, comparándolo con el terreno. [4] Compararon la tasa de costo (es decir, el costo por unidad de distancia, el inverso de la velocidad si el costo es el tiempo) con la pendiente de la superficie del terreno (es decir, el cambio de elevación por unidad de distancia), siendo ambos derivados matemáticos de un acumulado función o campo: elevación total sobre un datum vertical (nivel del mar) en el caso del terreno. La integración del campo de la tasa de costo desde un punto de partida dado crearía una superficie análoga del costo total acumulado de viaje desde ese punto. De la misma manera que una corriente sigue la ruta de menor resistencia cuesta abajo, la línea de corriente en la superficie de acumulación de costos desde cualquier punto "hacia abajo" hasta la fuente será la ruta de costo mínimo. [5] [6] Líneas adicionales de investigación en la década de 1960 desarrollaron aún más la naturaleza del campo de la tasa de costo como una manifestación del concepto de fricción de la distancia , estudiando cómo se ve afectado por diversas características geográficas. [7]
En ese momento, esta solución era solo teórica, carecía de los datos y la potencia informática para la solución continua. Raster GIS proporcionó la primera plataforma factible para implementar la solución teórica al convertir la integración continua en un procedimiento de suma discreto. Dana Tomlin implementó el análisis de costo-distancia en su Paquete de Análisis de Mapas en 1986, y Ronald Eastman lo agregó a IDRISI en 1989, con un algoritmo de acumulación de costos "pushbroom" más eficiente. [8] Douglas (1994) perfeccionó aún más el algoritmo de acumulación, que es básicamente lo que se implementa en la mayoría del software GIS actual. [9]
Ráster de costo
El conjunto de datos principal utilizado en el análisis de costo-distancia es el ráster de costo , a veces llamado superficie de costo de pasaje, [9] la imagen de fricción, [8] el campo de tasa de costo o superficie de costo. En la mayoría de las implementaciones, se trata de una cuadrícula ráster , en la que el valor de cada celda representa el costo (es decir, recursos gastados, como tiempo, dinero o energía) de una ruta que cruza la celda en dirección horizontal o vertical. [10] Es, pues, una discretización de un campo de tasa de coste (coste por unidad lineal), una propiedad espacialmente intensiva . Este costo es una manifestación del principio de fricción de la distancia .
Varios tipos diferentes de costos pueden ser relevantes en un problema de enrutamiento dado:
- Costo de viaje , el gasto de recursos necesarios para moverse a través de la celda, generalmente tiempo o energía / combustible.
- Costo de construcción , los recursos (generalmente monetarios) necesarios para construir la infraestructura que hace posible los viajes, como carreteras, tuberías y cables. Si bien algunos costos de construcción son constantes (por ejemplo, material de pavimentación), otros varían espacialmente, como la adquisición de propiedades y la excavación.
- Impactos ambientales , los efectos negativos sobre el medio ambiente natural o humano provocados por la infraestructura o los desplazamientos por ella. Por ejemplo, la construcción de una autopista a través de un vecindario residencial o un humedal incurriría en un alto costo político (en forma de evaluaciones de impacto ambiental, protestas, juicios, etc.).
Algunos de estos costos son fácilmente cuantificables y medibles, como el tiempo de tránsito, el consumo de combustible y los costos de construcción, por lo que, naturalmente, se prestan a soluciones computacionales. Dicho esto, puede haber una gran incertidumbre al predecir el costo antes de implementar la ruta. Otros costos son mucho más difíciles de medir por su carácter cualitativo o subjetivo, como la protesta política o el impacto ecológico; estos normalmente requieren operacionalización mediante la creación de una [Escala (ciencias sociales) | escala]]. [11]
En muchas situaciones, varios tipos de costos pueden ser relevantes simultáneamente y el costo total es una combinación de ellos. Debido a que los diferentes costos se expresan en diferentes unidades (o, en el caso de las escalas, ninguna unidad), por lo general no se pueden sumar directamente, sino que deben combinarse creando un índice . Un tipo común de índice se crea escalando cada factor a un rango consistente (digamos, [0,1]), luego combinándolos usando una combinación lineal ponderada . Una parte importante de la creación de un modelo de índice como este es la Calibración (estadísticas) , ajustando los parámetros de la (s) fórmula (s) para hacer que el costo relativo modelado coincida con los costos del mundo real, utilizando métodos como el proceso de jerarquía analítica . La fórmula del modelo de índice se implementa normalmente en un SIG ráster utilizando herramientas de álgebra de mapas de cuadrículas ráster que representan cada factor de costo, lo que da como resultado una cuadrícula ráster de costo único.
Costo direccional
Una limitación del método tradicional es que el campo de costos es isotrópico u omnidireccional: el costo en una ubicación determinada no depende de la dirección de recorrido. Esto es apropiado en muchas situaciones, pero no en otras. Por ejemplo, si uno está volando en un lugar con viento, un avión que vuela en la dirección del viento incurre en un costo mucho menor que un avión que vuela en contra. Se han realizado algunas investigaciones sobre la extensión de los algoritmos de análisis de costos y distancias para incorporar costos direccionales, pero aún no se han implementado ampliamente en el software SIG. [12] IDRISI tiene cierto soporte para la anisotropía. [1]
Algoritmo de ruta de menor costo
La tarea de distancia de costo más común es determinar la ruta única a través del espacio entre una ubicación de origen determinada y una ubicación de destino que tiene el menor costo total acumulado. El algoritmo de solución típico es una implementación de ráster discreto de la estrategia de integración de costos de Warntz y Lindgren, [5] que es una optimización determinista ( NP-completa ) . [10]
- Entradas: ráster de campo de costo, ubicación de origen, ubicación de destino (la mayoría de las implementaciones pueden resolver múltiples fuentes y destinos simultáneamente)
- Acumulación: comenzando en la ubicación de origen, calcule el costo total más bajo necesario para llegar a todas las demás celdas de la cuadrícula. Aunque existen varios algoritmos, como los publicados por Eastman y Douglas, [8] [9] generalmente siguen una estrategia similar. [13] Este proceso también crea, como un subproducto importante, una segunda cuadrícula ráster generalmente llamada cuadrícula de vínculo de retroceso (Esri) o cuadrícula de dirección de movimiento (GRASS), en la que cada celda tiene un código de dirección (0-7) que representa cuál de sus ocho vecinos tuvieron el costo más bajo.
- Encuentre una celda que sea adyacente a al menos una celda que ya tenga un costo acumulado asignado (inicialmente, esta es solo la celda de origen)
- Determine qué vecino tiene el costo acumulado más bajo. Codifique la dirección desde el objetivo hasta el vecino de menor costo en la cuadrícula de backlinks.
- Agregue el costo de la celda de destino (o un promedio de los costos de las celdas de destino y vecinas) al costo acumulado del vecino, para crear el costo acumulado de la celda de destino. Si el vecino es diagonal, el costo local se multiplica por √ 2
- El algoritmo también debe tener en cuenta que las rutas indirectas pueden tener un costo más bajo, a menudo utilizando una tabla hash para realizar un seguimiento de los valores de costos temporales a lo largo de la franja de cálculo en expansión que se puede reconsiderar.
- Repita el procedimiento hasta que se asignen todas las celdas.
- Drenaje: de acuerdo con la analogía del terreno, trace la ruta óptima desde el destino dado hasta la fuente como un arroyo que se aleja de una ubicación. En su forma más básica, esto se logra comenzando en la celda de destino, moviéndose en la dirección indicada en la cuadrícula de backlinks, luego repitiendo para la siguiente celda, y así sucesivamente hasta que se alcanza la fuente. El software reciente agrega algunas mejoras, como mirar a través de tres o más celdas para reconocer líneas rectas en ángulos distintos de las ocho direcciones vecinas. Por ejemplo, la función r.walk en GRASS puede reconocer el "movimiento del caballo " (una celda recta, luego una celda en diagonal) y dibujar una línea recta sin pasar por la celda del medio.
Análisis de corredor
Una versión ligeramente diferente del problema de la ruta de menor costo, que podría considerarse una versión difusa, es buscar corredores de más de una celda de ancho, lo que proporciona cierta flexibilidad en la aplicación de los resultados. Los corredores se utilizan comúnmente en la planificación del transporte y en el manejo de la vida silvestre.
La solución a este problema es calcular, para cada celda del espacio de estudio, el costo total acumulado de la ruta óptima entre un origen y un destino determinados que pasa por esa celda. Por lo tanto, cada celda en la ruta óptima derivada anteriormente tendría el mismo valor mínimo. Las celdas cercanas a esta ruta serían alcanzadas por rutas que se desvían solo ligeramente de la ruta óptima, por lo que tendrían valores de costo relativamente bajos, formando colectivamente un corredor con bordes difusos ya que las celdas más distantes tienen valores de costo crecientes.
El algoritmo para derivar este campo de corredor se crea generando dos cuadrículas de acumulación de costos: una usando la fuente como se describe arriba. Luego se repite el algoritmo, pero utilizando el destino como origen. Luego, estas dos cuadrículas se agregan usando álgebra de mapas . Esto funciona porque para cada celda, la ruta de origen-destino óptima que pasa a través de esa celda es la ruta óptima de esa celda a la fuente, sumada a la ruta óptima de esa celda al destino. Esto se puede lograr utilizando la herramienta de acumulación de costos anterior, junto con una herramienta de álgebra de mapas, aunque ArcGIS proporciona una herramienta Corridor que automatiza el proceso.
Asignación basada en costos
Otro uso del algoritmo de acumulación de costos es dividir el espacio entre múltiples fuentes, con cada celda asignada a la fuente a la que puede llegar con el menor costo, creando una serie de regiones en las que cada fuente es la "más cercana". En la analogía del terreno, estos corresponderían a cuencas hidrográficas (por lo tanto, se podrían llamar "coberturas de costos", pero este término no es de uso común). Están directamente relacionados con un diagrama de voronoi , que es esencialmente una asignación sobre un espacio con un costo constante. También son conceptualmente (si no computacionalmente) similares a las herramientas de ubicación y asignación para el análisis de redes.
Se puede crear una asignación basada en costos utilizando dos métodos. La primera es utilizar una versión modificada del algoritmo de acumulación de costos, que sustituye la cuadrícula de backlinks por una cuadrícula de asignación, en la que a cada celda se le asigna el mismo identificador de fuente de su vecino de menor costo, lo que hace que el dominio de cada fuente crezca gradualmente. hasta que se conozcan. Este es el enfoque adoptado en ArcGIS Pro . [14] La segunda solución es ejecutar primero el algoritmo de acumulación básico, luego usar la cuadrícula de backlinks para determinar la fuente a la que "fluye" cada celda. GRASS GIS utiliza este enfoque; de hecho, se utiliza la misma herramienta que para calcular las cuencas hidrográficas a partir del terreno. [15]
Implementaciones
Las herramientas de coste-distancia están disponibles en la mayoría de los programas de SIG de trama:
- GRASS GIS (a menudo incluido en QGIS ), con funciones separadas de acumulación ( r.cost ) y drenaje ( r.walk )
- ArcGIS Desktop y ArcGIS Pro , con herramientas de geoprocesamiento independientes de acumulación ( costo de distancia ) y drenaje ( ruta de costo ), así como generación de corredor . Recientemente, a partir de la versión 2.5 de ArcGIS Pro, se introdujo un nuevo conjunto de herramientas de costo-distancia, utilizando algoritmos más avanzados con opciones más flexibles. [dieciséis]
- TerrSet (anteriormente Idrisi) tiene varias herramientas, implementando una variedad de algoritmos para resolver diferentes tipos de problemas de distancia de costo, incluido el costo anisotrópico (direccional). [17]
Referencias
- ^ a b de Smith, Michael, Paul Longley, Michael Goodchild (2018) Coste distancia , análisis geoespacial , sexta edición
- ^ Warntz, William (1957). "Transporte, Física Social y Ley de Refracción". El geógrafo profesional . 9 (4): 2–7. doi : 10.1111 / j.0033-0124.1957.094_2.x .
- ^ Bunge, William (1966). Geografía teórica . Lund, Suecia: Berlingsta Botryckeriet. pag. 128.
- ^ Warntz, William (1965) " Una nota sobre superficies y caminos y aplicaciones a problemas geográficos , IMaGe Discussion Paper # 6 , Ann Arbor: Comunidad Interuniversitaria de Geógrafos Matemáticos de Michigan
- ^ a b Lindgren, Ernesto S. (1967). "Propuesta de solución al problema del recorrido mínimo". Serie de artículos de Harvard sobre geografía teórica, geografía y las propiedades de la superficie . 4 .
- ^ Lindgren, Ernesto S. (1967). "Un problema de recorrido mínimo reconsiderado". Serie de artículos de Harvard sobre geografía teórica, geografía y las propiedades de la superficie . 28 .
- ^ Huff, David L .; Jenks, George F. (1968). "Interpretación gráfica de la fricción de la distancia en modelos de gravedad". Anales de la Asociación de Geógrafos Estadounidenses . 58 (4): 814. doi : 10.1111 / j.1467-8306.1968.tb01670.x .
- ^ a b c Eastman JR (1989) Algoritmos Pushbroom para calcular distancias en cuadrículas ráster . Actas, AutoCarto 9 , págs. 288-97
- ^ a b c Douglas, David H. (1994). "Ruta de menor costo en SIG utilizando una superficie de costo acumulado y pendientes". Cartographica . 31 (3): 37–51. doi : 10.3138 / D327-0323-2JUT-016M .
- ^ a b Bolstad, Paul (2008). Fundamentos de SIG: Un primer texto sobre sistemas de información geográfica (3ª ed.). Eider Press. págs. 404–408. ISBN 978-0-9717647-2-9.
- ^ GH Pirie (2009) Distancia , en Rob Kitchin, Nigel Thrift (eds.) Enciclopedia internacional de geografía humana , Elsevier, páginas 242-251. doi: 10.1016 / B978-008044910-4.00265-0
- ^ Collischonn, Walter; Pilar, Jorge Víctor (2000). "Un algoritmo de ruta de menor costo dependiente de la dirección para carreteras y canales". Revista Internacional de Ciencias de la Información Geográfica . 14 (4): 397–407. doi : 10.1080 / 13658810050024304 . S2CID 37823291 .
- ^ "Cómo funcionan las herramientas de coste a distancia" . Documentación de ArcGIS Pro . Esri . Consultado el 29 de diciembre de 2020 .
- ^ "Asignación de costos (analista espacial)" . Documentación de ArcGIS Pro . Esri . Consultado el 30 de diciembre de 2020 .
- ^ "cuenca r . " . Documentación de GRASS GIS . Consultado el 30 de diciembre de 2020 .
- ^ "Una descripción general del conjunto de herramientas Distancia" . Documentación de ArcGIS Pro . Esri . Consultado el 29 de diciembre de 2020 .
- ^ Eastman, J. Ronald, Manual TerrSet, p.115, 227, 356
enlaces externos
- Documentación del conjunto de herramientas de distancia para Esri ArcGIS Pro
- Herramientas de superficie de coste en GRASS GIS