Анализ стоимостного расстояния

Для более широкого освещения этой темы см. Анализ близости .

В пространственном анализе и географических информационных системах анализ стоимостного расстояния или анализ стоимостного пути — это метод определения одного или нескольких оптимальных маршрутов путешествия через неограниченное (двумерное) пространство. Оптимальным решением является то, которое минимизирует общую стоимость маршрута на основе поля плотности стоимости (стоимость за погонную единицу), которое меняется в пространстве из-за местных факторов. Таким образом, он основан на фундаментальном географическом принципе трения расстояния . Это задача оптимизации с множеством решений детерминированных алгоритмов , реализованных в большинстве программ ГИС.

Различные задачи, алгоритмы и инструменты анализа стоимостного расстояния работают в неограниченном двумерном пространстве, а это означает, что путь может иметь любую форму. Подобные проблемы оптимизации затрат также могут возникнуть в ограниченном пространстве, особенно в одномерной линейной сети, такой как дорога или телекоммуникационная сеть . Хотя в принципе они схожи, проблемы в сетевом пространстве требуют для решения совсем других (обычно более простых) алгоритмов, во многом заимствованных из теории графов . Совокупность ГИС-инструментов для решения этих задач называется сетевым анализом .

История

Кажется, у людей есть врожденное желание путешествовать с минимальными усилиями и временем. Исторические, даже древние дороги демонстрируют закономерности, аналогичные тем, которые генерируют современные вычислительные алгоритмы: они проходят прямо по ровным пространствам, но огибают горы, каньоны и густую растительность.

Однако только в 20 веке географы разработали теории, объясняющие эту оптимизацию маршрутов, и алгоритмы для ее воспроизведения. В 1957 году, во время количественной революции в географии, с ее склонностью перенимать принципы или математические формализмы из «точных» наук (известных как социальная физика ), Уильям Варнц использовал рефракцию как аналогию того, как минимизация транспортных расходов приведет к изменению направления транспортных маршрутов. на границе двух ландшафтов с очень разным расстоянием (например, выход из леса в прерию). Его принцип «экономного движения», меняющего направление для минимизации затрат, получил широкое признание, но аналогия с преломлением и математика ( закон Снелла ) не были приняты, главным образом потому, что они плохо масштабируются к обычно сложным географическим ситуациям.

Варнц и другие затем применили другую аналогию, которая оказалась гораздо более успешной в обычной ситуации, когда стоимость путешествия постоянно меняется в пространстве, путем сравнения ее с местностью. Они сравнили ставку затрат (т. е. стоимость на единицу расстояния, обратную скорости, если стоимость — это время) с наклоном поверхности местности (т. е. изменением высоты на единицу расстояния), причем оба показателя являются математическими производными накопленной функции или поля. : общая высота над вертикальной точкой отсчета (уровнем моря) в случае рельефа местности. Интеграция поля ставок затрат из заданной отправной точки создаст аналогичную поверхность общей накопленной стоимости поездки из этой точки. Точно так же, как поток движется вниз по пути наименьшего сопротивления, линия тока на поверхности накопления затрат от любой точки «вниз» к источнику будет путем с минимальными затратами. Дополнительные направления исследований 1960-х годов дополнительно развили природу поля ставок затрат как проявление концепции трения расстояния , изучая, как на него влияют различные географические особенности.

В то время это решение было только теоретическим, и для непрерывного решения не хватало данных и вычислительной мощности. Растровая ГИС предоставила первую реальную платформу для реализации теоретического решения путем преобразования непрерывной интеграции в процедуру дискретного суммирования. Дана Томлин реализовал анализ расстояния затрат в своем пакете анализа карт к 1986 году, а Рональд Истман добавил его в IDRISI к 1989 году с более эффективным алгоритмом накопления затрат «по принципу «метки». Дуглас (1994) дополнительно усовершенствовал алгоритм накопления, который, по сути, реализован в большинстве современных программ ГИС.

Стоимость растра

Блок-схема типичного анализа траектории затрат ГИС

См. Также: Трение расстояния

Основным набором данных, используемым при анализе стоимостного расстояния, является растр стоимости , иногда называемый поверхностью стоимости прохода. изображение трения, поле стоимости-ставки или поверхность стоимости. В большинстве реализаций это растровая сетка , в которой значение каждой ячейки представляет стоимость (т. е. затраченные ресурсы, такие как время, деньги или энергия) маршрута, пересекающего ячейку в горизонтальном или вертикальном направлении. это дискретизация поля Таким образом , нормы затрат (стоимость за линейную единицу), пространственно-интенсивного свойства. Эта стоимость является проявлением принципа трения расстояния .

В конкретной задаче маршрутизации могут иметь значение несколько различных типов затрат:

• Стоимость путешествия — затраты ресурсов, необходимые для перемещения по ячейке, обычно время или энергия/топливо.
• Стоимость строительства — ресурсы (обычно денежные), необходимые для создания инфраструктуры, позволяющей путешествовать, например дорог, труб и кабелей. В то время как некоторые затраты на строительство постоянны (например, материал для дорожного покрытия), другие являются пространственно изменчивыми, например, приобретение недвижимости и земляные работы.
• Воздействие на окружающую среду , негативное воздействие на природную или человеческую среду, вызванное инфраструктурой или перемещением по ней. Например, строительство скоростной автомагистрали через жилой район или заболоченную территорию повлечет за собой высокие политические издержки (в виде оценок воздействия на окружающую среду, протестов, судебных исков и т. д.).

Некоторые из этих затрат легко поддаются количественной оценке и измерению, например, время в пути, расход топлива и затраты на строительство, что естественным образом поддается вычислительным решениям. Тем не менее, может существовать значительная неопределенность в прогнозировании стоимости до реализации маршрута. Другие затраты гораздо сложнее измерить из-за их качественного или субъективного характера, например, политические протесты или экологические последствия; они обычно требуют практической реализации путем создания шкалы .

Во многих ситуациях одновременно могут иметь значение несколько типов затрат, а общая стоимость представляет собой их комбинацию. Поскольку разные затраты выражаются в разных единицах (или, в случае шкал, вообще без единиц), их обычно нельзя суммировать напрямую, а необходимо объединить путем создания индекса . Общий тип индекса создается путем масштабирования каждого фактора до согласованного диапазона (скажем, [0,1]), а затем их объединения с использованием взвешенной линейной комбинации . Важной частью создания такой индексной модели является Калибровка (статистика) , корректирующая параметры формулы(й) так, чтобы смоделированные относительные затраты соответствовали реальным затратам, с использованием таких методов, как процесс аналитической иерархии . Формула индексной модели обычно реализуется в растровой ГИС с использованием инструментов алгебры карт из растровых сеток, представляющих каждый фактор стоимости, в результате чего получается единая растровая сетка стоимости.

Направленная стоимость

Основная статья: Анизотропия

Одним из ограничений традиционного метода является то, что поле стоимости является изотропным или всенаправленным: стоимость в данном месте не зависит от направления обхода. Это уместно во многих ситуациях, но не в других. Например, если вы летите в ветреном месте, самолет, летящий по направлению ветра, несет гораздо меньшие затраты, чем самолет, летящий против него. Были проведены некоторые исследования по расширению алгоритмов анализа стоимостного расстояния для включения направленной стоимости, но они еще не получили широкого распространения в программном обеспечении ГИС. IDRISI имеет некоторую поддержку анизотропии.

Алгоритм пути наименьшей стоимости

Наиболее распространенной задачей определения стоимостного расстояния является определение единственного пути через пространство между заданным исходным местоположением и целевым местоположением, который имеет наименьшую общую накопленную стоимость. Типичный алгоритм решения представляет собой дискретную растровую реализацию стратегии интеграции затрат Варнца и Линдгрена, что является детерминированной ( NP-полной ) оптимизацией .

1. Входные данные: растр поля стоимости, местоположение источника, местоположение назначения (большинство реализаций могут учитывать несколько источников и мест назначения одновременно).
2. Накопление: начиная с исходного местоположения, вычислите наименьшую общую стоимость, необходимую для достижения каждой второй ячейки сетки. Хотя существует несколько алгоритмов, например, опубликованные Истманом и Дугласом, они обычно следуют одной и той же стратегии. В качестве важного побочного продукта этот процесс также создает вторую растровую сетку, обычно называемую сеткой обратных ссылок (Esri) или сеткой направления движения (GRASS), в которой каждая ячейка имеет код направления (0–7), представляющий, какой из ее восьми соседей самая низкая стоимость.
   1. Найдите ячейку, примыкающую хотя бы к одной ячейке, которой уже назначена накопленная стоимость (изначально это только исходная ячейка)
   2. Определите, какой сосед имеет наименьшую накопленную стоимость. Закодируйте направление от цели к соседу с наименьшей стоимостью в сетке обратных ссылок.
   3. Добавьте стоимость целевой ячейки (или среднее значение стоимости целевой и соседней ячеек) к накопленной стоимости соседа, чтобы создать накопленную стоимость целевой ячейки. Если сосед диагональный, локальная стоимость умножается на ${\sqrt {2}}$
   4. Алгоритм также должен учитывать, что непрямые маршруты могут иметь более низкую стоимость, часто используя хеш-таблицу для отслеживания временных значений стоимости вдоль расширяющейся границы вычислений, которые могут быть пересмотрены.
   5. Повторяйте процедуру, пока все ячейки не будут назначены.
3. Слив: следуя аналогии с местностью, проследите оптимальный маршрут от заданного пункта назначения обратно к источнику, как поток, стекающий из определенного места. По сути, это достигается путем начала с ячейки назначения, перемещения в направлении, указанном в сетке обратных ссылок, затем повторения для следующей ячейки и так далее, пока не будет достигнут источник. В последнее программное обеспечение добавлены некоторые улучшения, такие как просмотр трех или более ячеек для распознавания прямых линий под углами, отличными от восьми соседних направлений. Например, функция r.walk в GRASS может распознать «ход коня» (одну клетку прямо, затем одну клетку по диагонали) и нарисовать прямую линию в обход средней клетки.

Анализ коридора

Блок-схема процедуры анализа коридора затрат в ГИС, коридоры с низкими и умеренными затратами заштрихованы

Немного другая версия проблемы пути с наименьшей стоимостью, которую можно считать ее нечеткой версией, заключается в поиске коридоров шириной более одной ячейки, что обеспечивает некоторую гибкость в применении результатов. Коридоры обычно используются при транспортном планировании и управлении дикой природой.

Решение этой проблемы состоит в вычислении для каждой ячейки исследуемого пространства общей накопленной стоимости оптимального пути между заданным источником и пунктом назначения, который проходит через эту ячейку. Таким образом, каждая ячейка оптимального пути, полученного выше, будет иметь одно и то же минимальное значение. Ячейки, находящиеся рядом с этим путем, будут достигаться путями, лишь незначительно отклоняющимися от оптимального пути, поэтому они будут иметь относительно низкие значения стоимости, в совокупности образуя коридор с нечеткими краями, поскольку более удаленные ячейки имеют возрастающие значения стоимости.

Алгоритм получения этого поля коридора создается путем создания двух сеток накопления затрат: одна с использованием источника, как описано выше. Затем алгоритм повторяется, но в качестве источника используется пункт назначения. Затем эти две сетки добавляются с помощью алгебры карт . Это работает, потому что для каждой ячейки оптимальный путь источник-назначение, проходящий через эту ячейку, является оптимальным путем от этой ячейки к источнику, добавленным к оптимальному пути от этой ячейки к месту назначения. Это можно сделать с помощью инструмента накопления затрат, описанного выше, а также инструмента алгебры карты, хотя ArcGIS предоставляет инструмент «Коридор» , который автоматизирует этот процесс.

Распределение на основе затрат

Другое использование алгоритма накопления стоимости - это разделение пространства между несколькими источниками, при этом каждая ячейка назначается источнику, которого она может достичь с наименьшими затратами, создавая серию регионов, в которых каждый источник является «ближайшим». В аналогии с местностью они будут соответствовать водоразделам (таким образом можно было бы назвать их «потоками затрат», но этот термин не широко используется). Они напрямую связаны с диаграммой Вороного , которая по сути представляет собой распределение в пространстве с постоянной стоимостью. Они также концептуально (если не вычислительно) похожи на инструменты распределения местоположения для сетевого анализа.

Распределение на основе затрат можно создать двумя способами. Первый заключается в использовании модифицированной версии алгоритма накопления стоимости, который заменяет сетку обратных ссылок сеткой распределения, в которой каждой ячейке присваивается тот же идентификатор источника, что и ее сосед с наименьшей стоимостью, что приводит к постепенному росту домена каждого источника. пока они не встретятся друг с другом. Именно такой подход использован в ArcGIS Pro . Второе решение — сначала запустить базовый алгоритм накопления, а затем использовать сетку обратных ссылок для определения источника, в который «перетекает» каждая ячейка. GRASS GIS использует этот подход; фактически используется тот же инструмент, что и для расчета водоразделов по местности.

Реализации

Инструменты стоимостного расстояния доступны в большинстве программ растровых ГИС:

• GRASS GIS (часто входит в состав QGIS ) с отдельными накопления ( r.cost ) и стока ( r.walk ). функциями
• ArcGIS Desktop и ArcGIS Pro с отдельными инструментами геообработки накопления ( Cost Distance ) и дренажа ( Cost Path ), а также созданием коридоров . Недавно, начиная с версии ArcGIS Pro 2.5, был представлен новый набор инструментов стоимостного расстояния, использующий более совершенные алгоритмы с более гибкими опциями.
• TerrSet (ранее Idrisi) имеет несколько инструментов, реализующих различные алгоритмы для решения различных проблем стоимостного расстояния, включая анизотропную (направленную) стоимость.

Приложения

Анализ стоимостного расстояния нашел применение в широком спектре географических дисциплин, включая археологию. и ландшафтная экология .

См. также

• Распад расстояния
• Первый закон географии Тоблера
• Второй закон географии Тоблера
• Функция похода Тоблера
• Задача коммивояжера
  • Проблема канадского путешественника
  • Проблема путешествующего покупателя
  • Проблема с маршрутом автомобиля

Внешние ссылки

• Документация по набору инструментов Distance для Esri ArcGIS Pro
• Инструменты Cost Surface в GRASS GIS