Análisis de distancia de costos

En el análisis espacial y los sistemas de información geográfica , el análisis de costo-distancia o el análisis de costo-ruta es un método para determinar una o más rutas óptimas de viaje a través de un espacio bidimensional no restringido. ^{[ 1 ]} La solución óptima es aquella que minimiza el costo total de la ruta, basándose 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 la fricción de la distancia . Es un problema de optimización con múltiples soluciones algorítmicas deterministas , implementadas en la mayoría del software SIG.

Los diversos problemas, algoritmos y herramientas del análisis de distancia de costos operan en un espacio bidimensional sin restricciones, lo que significa que un camino puede tener cualquier forma. Problemas similares de optimización de costos también pueden surgir en un espacio restringido, especialmente en una red lineal unidimensional como una red vial o de telecomunicaciones . Si bien son similares en principio, los problemas en el espacio de red requieren algoritmos muy diferentes (generalmente más simples) para su resolución, en gran medida adoptados de la teoría de grafos . El conjunto de herramientas SIG para resolver estos problemas se denomina análisis de redes .

Los seres humanos parecen tener un deseo innato de viajar con el mínimo esfuerzo y tiempo. Los caminos históricos, incluso los más antiguos, muestran patrones similares a los que generarían los algoritmos computacionales modernos: discurren en línea recta por terrenos llanos, pero se curvan alrededor de montañas, cañones y vegetación densa.

Sin embargo, no fue hasta el siglo XX que los geógrafos desarrollaron teorías para explicar esta optimización de rutas 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" (conocida como física social ), William Warntz utilizó la refracción como analogía de cómo la minimización del costo del viaje hará que las rutas de transporte cambien de dirección en el límite entre dos paisajes con fricción de distancia muy diferente (por ejemplo, al salir de un bosque hacia 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 se adaptan bien a situaciones geográficas normalmente complejas. ^{[ 3 ]}

Warntz y otros adoptaron entonces otra analogía que resultó mucho más exitosa en la situación común donde el costo del viaje varía continuamente en el espacio, comparándolo con el terreno. ^{[ 4 ]} Compararon la tasa de costo (es decir, costo por unidad de distancia, el inverso de la velocidad si el costo es tiempo) con la pendiente de una superficie de terreno (es decir, cambio de elevación por unidad de distancia), siendo ambos derivados matemáticos de una función o campo acumulado: elevación total sobre un datum vertical (nivel del mar) en el caso del terreno. Integrar el campo de la tasa de costo desde un punto de partida dado crearía una superficie análoga del costo total acumulado del viaje desde ese punto. De la misma manera que un arroyo sigue el camino 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á el camino de costo mínimo. ^{[ 5 ] [ 6 ]} Otras líneas 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ía afectado por diversas características geográficas. ^{[ 7 ]}

En aquel momento, esta solución era solo teórica, careciendo de los datos y la capacidad de cálculo necesarios para la solución continua. El SIG ráster proporcionó la primera plataforma viable para implementar la solución teórica al convertir la integración continua en un procedimiento de suma discreta. Dana Tomlin implementó el análisis de distancia de costos en su Paquete de Análisis de Mapas en 1986, y Ronald Eastman lo añadió a IDRISI en 1989, con un algoritmo de acumulación de costos de "barrido" 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 SIG actual. ^{[ 9 ]}

El conjunto de datos principal utilizado en el análisis de distancia de costo es el ráster de costo , a veces llamado superficie de costo de paso, ^{[ 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, los recursos gastados, como tiempo, dinero o energía) de una ruta que cruza la celda en dirección horizontal o vertical. ^{[ 10 ]} Es, por lo tanto, una discretización de un campo de tasa de costo (costo por unidad lineal), una propiedad espacialmente intensiva . Este costo es una manifestación del principio de fricción de la distancia .

En un problema de enrutamiento determinado, pueden ser relevantes varios tipos de costes diferentes:

• Coste de desplazamiento , el gasto de recursos necesario para moverse a través de la celda, normalmente tiempo o energía/combustible.
• Costo de construcción : los recursos (generalmente monetarios) necesarios para construir la infraestructura que posibilita el transporte, como carreteras, tuberías y cables. Si bien algunos costos de construcción son constantes (por ejemplo, el material de pavimentación), otros varían según la ubicación, como la adquisición de terrenos y la excavación.
• Impactos ambientales : los efectos negativos sobre el medio ambiente natural o humano causados ​​por la infraestructura o el tránsito a lo largo de ella. Por ejemplo, la construcción de una autopista que atraviese un barrio residencial o un humedal conllevaría un alto costo político (en forma de evaluaciones de impacto ambiental, protestas, demandas, 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, lo que facilita su aplicación a soluciones computacionales. Sin embargo, puede existir una incertidumbre significativa al predecir el costo antes de implementar la ruta. Otros costos son mucho más difíciles de medir debido a su naturaleza cualitativa o subjetiva, como las protestas políticas o el impacto ecológico; estos generalmente requieren operacionalización mediante la creación de una 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 distintas unidades (o, en el caso de las escalas, sin unidades), generalmente 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 (por ejemplo, [0,1]), y luego combinándolos mediante una combinación lineal ponderada . Una parte importante de la creación de un modelo de índice como este es la calibración (estadística) , que consiste en ajustar los parámetros de la(s) fórmula(s) para 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 típicamente en un SIG ráster utilizando herramientas de álgebra de mapas a partir de cuadrículas ráster que representan cada factor de costo, lo que da como resultado una única cuadrícula ráster de costos.

La tarea más común de cálculo de distancia de costos consiste en determinar la única ruta a través del espacio entre una ubicación de origen y una ubicación de destino que tenga el menor costo total acumulado. El algoritmo de solución típico es una implementación raster discreta de la estrategia de integración de costos de Warntz y Lindgren, ^{[ 5 ]} que es una optimización determinista ( NP-completa ) . ^{[ 10 ]}

1. Entradas: ráster de campo de costos, ubicación de origen, ubicación de destino (la mayoría de las implementaciones pueden resolver múltiples orígenes y destinos simultáneamente).
2. Acumulación: Partiendo de la ubicación de origen, se calcula 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 importante subproducto, una segunda cuadrícula ráster, generalmente llamada cuadrícula de enlace inverso (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 tuvo el costo más bajo.
   1. Encuentra 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).
   2. Determina qué vecino tiene el menor coste acumulado. Codifica la dirección desde el objetivo hacia el vecino de menor coste en la cuadrícula de enlace inverso.
   3. Sume el costo de la celda objetivo (o un promedio de los costos de la celda objetivo y las celdas vecinas) al costo acumulado de la celda vecina, para crear el costo acumulado de la celda objetivo. Si la celda vecina es diagonal, el costo local se multiplica por${\displaystyle {\sqrt {2}}}$
   4. El algoritmo también debe tener en cuenta que las rutas indirectas pueden tener un coste menor, utilizando a menudo una tabla hash para realizar un seguimiento de los valores de coste temporales a lo largo del margen de cálculo en expansión que se puede reconsiderar.
   5. Repita el procedimiento hasta que se hayan asignado todas las celdas.
3. Drenaje: Siguiendo la analogía del terreno, se traza la ruta óptima desde el destino dado hasta el origen, como un arroyo que drena desde un punto. 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 enlaces inversos, repitiendo el proceso para la siguiente celda, y así sucesivamente hasta llegar al origen. El software reciente incorpora algunas mejoras, como la capacidad de analizar tres o más celdas para reconocer líneas rectas en ángulos distintos a las ocho direcciones vecinas. Por ejemplo, la función r.walk en GRASS puede reconocer el "movimiento del caballo" (una celda en línea recta, luego una en diagonal) y trazar una línea recta que evite la celda central.

Una versión ligeramente distinta del problema de la ruta de menor coste, que podría considerarse una versión difusa del mismo, consiste en 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 habitualmente en la planificación del transporte y en la gestión de la fauna silvestre.

La solución a este problema consiste en calcular, para cada celda del espacio de estudio, el coste total acumulado de la ruta óptima entre un origen y un destino determinados que pasa por dicha celda. De este modo, cada celda de la ruta óptima obtenida tendría el mismo valor mínimo. Las celdas cercanas a esta ruta serían alcanzadas por caminos que se desvían solo ligeramente de la ruta óptima, por lo que tendrían costes relativamente bajos, formando colectivamente un corredor con bordes difusos, ya que las celdas más distantes presentan costes crecientes.

El algoritmo para derivar este campo de corredor se crea generando dos cuadrículas de acumulación de costos: una usando el origen como se describió anteriormente. Luego, el algoritmo se repite, pero usando el destino como origen. Posteriormente, estas dos cuadrículas se suman mediante álgebra de mapas . Esto funciona porque, para cada celda, la ruta óptima origen-destino que pasa por esa celda es la ruta óptima desde esa celda hasta el origen, sumada a la ruta óptima desde esa celda hasta el destino. Esto se puede lograr usando la herramienta de acumulación de costos mencionada anteriormente, junto con una herramienta de álgebra de mapas, aunque ArcGIS proporciona una herramienta de corredor que automatiza el proceso.

Otro uso del algoritmo de acumulación de costos consiste en particionar el espacio entre múltiples fuentes, asignando a cada celda la fuente a la que puede llegar con el menor costo, creando así una serie de regiones en las que cada fuente es la más cercana. En la analogía del terreno, estas regiones corresponderían a cuencas hidrográficas (por lo que podrían denominarse "cuencas de costos", aunque este término no es de uso común). Están directamente relacionadas con un diagrama de Voronoi , que es esencialmente una asignación en un espacio con costo constante. También son conceptualmente (si no computacionalmente) similares a las herramientas de localización y asignación para el análisis de redes.

Se puede crear una asignación basada en costos mediante dos métodos. El primero consiste en utilizar una versión modificada del algoritmo de acumulación de costos, que sustituye la cuadrícula de enlaces inversos por una cuadrícula de asignación. En esta cuadrícula, a cada celda se le asigna el mismo identificador de origen que a su vecino de menor costo, lo que provoca que el dominio de cada origen crezca gradualmente hasta que se encuentren. Este es el enfoque utilizado en ArcGIS Pro . ^{[ 14 ]} La segunda solución consiste en ejecutar primero el algoritmo de acumulación básico y, a continuación, utilizar la cuadrícula de enlaces inversos para determinar el origen al que "fluye" cada celda. GRASS GIS utiliza este enfoque; de ​​hecho, se utiliza la misma herramienta que para calcular cuencas hidrográficas a partir del terreno. ^{[ 15 ]}

Las herramientas de cálculo de distancia de costes están disponibles en la mayoría de los programas SIG basados ​​en ráster:

• 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 separadas para acumulación ( Distancia de Costo ) y drenaje ( Ruta de Costo ), así como generación de corredores . Recientemente, a partir de la versión 2.5 de ArcGIS Pro, se introdujo un nuevo conjunto de herramientas de distancia de costo, que utiliza algoritmos más avanzados con opciones más flexibles. ^{[ 16 ]}
• TerrSet (anteriormente Idrisi) cuenta con varias herramientas que implementan diversos algoritmos para resolver distintos tipos de problemas de distancia de costo, incluido el costo anisotrópico (direccional). ^{[ 17 ]}

El análisis de distancia de costos ha encontrado aplicaciones en una amplia gama de disciplinas relacionadas con la geografía, incluyendo la arqueología ^{[ 18 ]} y la ecología del paisaje . ^{[ 19 ]}

• Documentación del conjunto de herramientas de distancia para Esri ArcGIS Pro
• Herramientas de superficie de costes en GRASS GIS