Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

История [ править ]

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

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

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

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

Растр стоимости [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

Анализ коридора [ править ]

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

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

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

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

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

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

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

Реализации [ править ]

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

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

Ссылки [ править ]

  1. ^ а б де Смит, Майкл, Пол Лонгли, Майкл Гудчайлд (2018) Стоимость Расстояние , Геопространственный анализ , 6-е издание
  2. ^ Warntz, Уильям (1957). «Транспорт, социальная физика и закон преломления». Профессиональный географ . 9 (4): 2–7. DOI : 10.1111 / j.0033-0124.1957.094_2.x .
  3. ^ Бунге, Уильям (1966). Теоретическая география . Лунд, Швеция: Berlingsta Botryckeriet. п. 128.
  4. ^ Warntz, Уильям (1965) " Заметка о поверхностях, путях и приложениях к географическим проблемам , IMaGe Discussion Paper # 6 , Анн-Арбор: Мичиганское межуниверситетское сообщество математических географов"
  5. ^ a b Линдгрен, Эрнесто С. (1967). «Предлагаемое решение проблемы минимального пути». Гарвардские документы по теоретической географии, географии и свойствам поверхностных рядов . 4 .
  6. ^ Линдгрен, Эрнесто С. (1967). «Проблема минимального пути пересмотрена». Гарвардские документы по теоретической географии, географии и свойствам поверхностных рядов . 28 .
  7. ^ Хафф, Дэвид Л .; Дженкс, Джордж Ф. (1968). «Графическая интерпретация трения расстояния в гравитационных моделях». Летопись Ассоциации американских географов . 58 (4): 814. DOI : 10.1111 / j.1467-8306.1968.tb01670.x .
  8. ^ a b c Eastman JR (1989) Алгоритмы Pushbroom для вычисления расстояний в растровых сетках . Труды, AutoCarto 9 , стр. 288-97
  9. ^ a b c Дуглас, Дэвид Х. (1994). «Путь с наименьшей стоимостью в ГИС с использованием поверхности суммарной стоимости и уклонов». Cartographica . 31 (3): 37–51. DOI : 10,3138 / D327-0323-2JUT-016M .
  10. ^ a b Болстад, Пол (2008). Основы ГИС: первый текст по географическим информационным системам (3-е изд.). Eider Press. С. 404–408. ISBN 978-0-9717647-2-9.
  11. ^ GH Пири (2009) Расстояние в Rob Китчина, Найджел бережливость (ред.) Международной энциклопедии человеческой географии , Elsevier, Страницы 242-251. DOI: 10.1016 / B978-008044910-4.00265-0
  12. ^ Коллишонн, Вальтер; Пилар, Хорхе Виктор (2000). "Зависящий от направления алгоритм наименьшей стоимости пути для дорог и каналов". Международный журнал географической информатики . 14 (4): 397–407. DOI : 10.1080 / 13658810050024304 . S2CID 37823291 . 
  13. ^ "Как работают инструменты определения расстояния" . Документация ArcGIS Pro . Esri . Проверено 29 декабря 2020 года .
  14. ^ «Распределение затрат (пространственный аналитик)» . Документация ArcGIS Pro . Esri . Проверено 30 декабря 2020 .
  15. ^ "r.watershed" . Документация GRASS GIS . Проверено 30 декабря 2020 .
  16. ^ «Обзор группы инструментов Distance» . Документация ArcGIS Pro . Esri . Проверено 29 декабря 2020 года .
  17. ^ Истман, Дж. Рональд, Руководство TerrSet, стр.115, 227, 356

Внешние ссылки [ править ]

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