Сетевой анализ: где ГИСы встречаются с математикой

Введение

Дороги и реки, инженерные коммуникации и линии электропередач – многое из того, что нас окружает, можно представить в виде сетей.

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

Основываясь на теории графов, сетевой анализ рассматривает объекты как модели, состоящие из узлов и связей между ними.

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

В статье я рассказала, почему геоаналитикам полезно знать о математических методах для изучения геопространственных сетей и привела распространённые примеры их применения в ГИС.

Сети в геопространственном анализе

Сеть — это структура, состоящая из узлов (вершин), связанных рёбрами (дугами).

Сети могут представлять разнообразные системы, например, социальные, где узлы представляют собой людей, и рёбра — их отношения, или технологические, где узлы — это компьютеры, а рёбра — каналы передачи данных.

Геопространственные сети

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

Как правило, узлы в геопространственных сетях представляют собой физические объекты, размещённые в географических локациях, а рёбра — реальные пути или связи, подчиняющиеся географическим и физическим ограничениям (например, дороги или реки).

Изучение таких моделей позволяет учитывать пространственные характеристики и географические зависимости.

Примеры:

• Транспорт. Структуры, соединяющие городские и региональные пункты для удобства перемещения людей и грузов. Узлами часто выступают пересечения дорог, вокзалы и аэропорты, связанные автомобильными дорогами, железнодорожными путями и воздушными коридорами.
• Водоснабжение. Системы, соединяющая источники воды, водоочистные станции и потребителей через водопроводы. Узлами здесь выступают резервуары, насосные станции и гидранты, а рёбрами – водопроводы различного диаметра и назначения.
• Инженерные коммуникации. Электрические, газовые и тепловые и другие системы, обеспечивающие функционирование зданий и промышленных объектов. Узлами могут быть подстанции, трансформаторы и тепловые узлы, соединенные кабелями, трубопроводами и линиями электропередач.

Применение сетевого анализа в геоаналитике

Сетевой анализ — это метод моделирования и изучения систем, представленных в виде сетей.

Аналитика пространственной сети предполагают изучение важных пространственных параметров (таких как расстояние, площадь и ориентация), а также применяется для выявления закономерностей во взаимодействии между географически определёнными объектами и определения «зон охвата» географических локаций.

Геоаналитика сетей востребована во многих отраслях, где важным является местоположение активов или инфраструктуры.

Эти отрасли активно используют геопространственные данные для анализа, планирования, прогнозирования и оптимизации различных процессов. Вот некоторые из них:

• Транспорт и логистика. Оптимизация маршрутов, планирование транспортных потоков, а также прогнозирование и решение проблем пробок на дорогах.
• Урбанистика. Городское планирование, размещение инфраструктуры, изучение пешеходных потоков и определение оптимальных мест для создания общественных пространств.
• Экология и охрана окружающей среды. Изучение миграции животных, потоков воды или загрязнения в экосистемах.
• Энергетика. Планирование и мониторинг систем передачи электроэнергии, оптимизация местоположения источников возобновляемой энергии.
• Телекоммуникации. Планирование и оптимизация распределения телекоммуникационных сетей, поиск оптимальных локаций для башен сотовой связи и базовых станций.
• Здравоохранение. Распределение и изучение распространения болезней, планирование размещения медицинских учреждений.
• Розничная торговля. Изучение потоков покупателей, планирование размещения магазинов или оптимизация доставки товаров.
• Безопасность и чрезвычайные ситуации. Прогнозирование и реагирование на чрезвычайные ситуации, планирование мероприятий по предотвращению катастроф, оптимизация маршрутов для служб спасения.
• Сельское хозяйство. Оптимизация систем орошения, планирование участков для посева с учетом геопространственных данных.

Для чего нужны сетевые геоаналитические сервисы?

Представьте себе: вы планируете новую дорожную развязку или хотите оптимизировать логистику доставки.

Цифровая модель сети позволит вам «поиграть» с различными вариантами, прежде чем применить их на практике.

В сетевом анализе используется теория графов

Проектирование и расчёт параметров сетей выполняется путём построения их моделей, и использования различных математических методов с учетом имеющихся ресурсов, условий и ограничений.

Для моделирования сетей используется теория графов. Графы представляют собой множества вершин (или узлов), соединенных рёбрами.

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

Для этого можно использовать многие хорошо известные эффективные математические методы.

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

Что важно знать о графах

• У вершин есть степень (количество рёбер вершины).

• У рёбер есть направление и вес. Вес может представлять собой стоимость, расстояние, время в пути или другую метрику.

Графы могут быть направленными (перемещение по рёбрам возможно только в определенных направлениях) или ненаправленными (перемещение возможно в любом направлении), а также взвешенными или нет.

• У вершин и рёбер есть атрибуты.
• Связность  — это свойство графа, характеризующее возможность достижимости из одной вершины любой другой вершины, следуя по рёбрам.

• Для описания графа используются матрицы.
  Матрица смежности — это двумерная квадратная матрица, которая показывает, есть ли ребро между двумя вершинами графа. Если вершина i связана с вершиной j, то в ячейке на пересечении строки i и столбца j стоит 1 (или вес ребра, если граф взвешенный). Если ребра между этими вершинами нет, то в соответствующей ячейке стоит 0.
  В случае направленного графа при построении матрицы смежности учитывается направление ребра.

Матрицы смежности для ненаправленного и направленного графов отличаются: для ненаправленного графа матрица смежности всегда симметричная, а для ненаправленного — нет, так как наличие ребра из вершины I в вершину j не гарантирует наличие ребра из вершины j в вершину i.

Матрица инцидентности — это матрица, где строки соответствуют вершинам графа, а столбцы — рёбрам. Если вершина принадлежит ребру (то есть ребро «приходит» или «уходит» из вершины), то в соответствующей ячейке стоит -1 (для начальной вершины) или 1 (для конечной вершины). Если вершина к ребру не относится, то стоит 0.

Матричное описание свойств графа даёт возможность использовать методы линейной алгебры и линейного программирования для поиска оптимального решения.

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

От графов к искусственному интеллекту

Методы машинного обучения на графах стали популярными в последние годы, особенно с ростом интереса к графовым нейронным сетям (Graph Neural Networks, GNNs).

GNN — это класс моделей машинного обучения, которые были разработаны специально для обработки данных, структурированных в виде графов.

Все перечисленные выше свойства вершин и рёбер, а также самого графа отлично подходят для решения задач прогнозирования.

Структура графа даёт возможность делать три основных типа прогнозов:

• Прогнозирование на уровне отдельных вершин. Цель этого метода — предсказать свойства отдельных вершин. Например, прогнозирование типа здания (жилое, коммерческое, промышленное) на основе его географического положения и связей с соседними объектами (например, дороги, парки, объекты городской инфраструктуры).

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

Применение этих методов требует интеграции информации из разных частей графа.
Для этого часто используются GNN, которые агрегируют и анализируют данные, включая структуру графа и свойства его вершин и рёбер.

• Прогнозирование времени в пути (или откуда навигатор знает, сколько придётся ехать). Транспортная сеть может быть представлена в виде графа, где вершины представляют собой местоположения (например, остановки или станции или сегменты дорог), а рёбра — пути между ними.
  У рёбер могут быть заданы атрибуты, такие как протяжённость пути, пропускная способность, состояние дороги и другие.
  GNN могут учитывать плотность движения, скорость движения, погодные условия и другие данные. Это делается путём обновления атрибутов вершин и рёбер в реальном времени или с использованием актуальных данных.
  GNN обучаются на основе исторических данных о времени в пути между различными парами вершин. Целью является обучение модели таким образом, чтобы она могла предсказать время в пути между произвольной парой вершин.
  После обучения GNN можно использовать для прогнозирования времени в пути между различными вершинами на графе.
  Модель может также учитывать различные внешние факторы, такие как погодные условия, время суток, день недели, чтобы уточнить прогнозы времени в пути.
• Изучение транспортных сетей. GNN могут обучаться на данных о дорогах, предсказывая, например, возможные места пробок или определяя оптимальные пути движения. Путем агрегации данных из различных источников (датчики движения, данные о погоде, камеры наблюдения и т. д.), GNN могут динамически адаптировать и оптимизировать транспортные потоки.
• Прогнозирование трафика. В таких моделях узлы представляют сегменты дорожной сети, а рёбра обозначают связи между сегментами. Каждый сегмент дороги содержит информацию о его состоянии в разные периоды времени (атрибуты вершин): например, скорость движения, плотность трафика, наличие аварий или дорожных работ. GNN обучается на этих данных, учитывая не только текущую ситуацию на конкретном участке дороги, но и особенности движения на соседних участках, а также на всём пути от начальной до конечной локации.
• Оценка состояния сетей электроснабжения. GNN могут использоваться для прогнозирования и обнаружения возможных точек отказа, основываясь на различных входных данных, таких как погодные условия, нагрузка и состояние оборудования.

Типовые задачи сетевого анализа в ГИС

Оптимизация маршрута (OPP — Optimal Path Problem)

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

Например, когда Вы выбираете маршрут доставки товаров из пункта А в пункт Б, минимизируя затраты на бензин и платные дороги, вы решаете задачу сетевого анализа.

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

1. Географический контекст. Физическую географию местности, включая естественные или искусственные препятствия (реки, горы, здания, или закрытые территории и участки дорог).
2. Атрибуты, которые влияют на выбор маршрута. Каждый узел и ребро на графе могут иметь атрибуты, такие как максимальная скорость, типы дорог, стоимость проезда и другие.
3. Изменение ситуации на дороге. На маршрут могут повлиять пробки, дорожные работы, аварии или погодные условия.
4. Многокритериальность. Задачи оптимизации часто включают в себя несколько критериев, которые могут конфликтовать друг с другом. Например, при планировании маршрута часто нужно минимизировать и время пути, и стоимость. Однако самый быстрый путь может быть более дорогим, и наоборот, самый дешевый путь может занять больше времени.
5. Мультимодальный способ перевозки. Например, при расчёте оптимального маршрута на общественном транспорте сервис может учитывать разные виды транспорта, — для части маршрута можно использовать метро, а затем пересесть на автобус. В этом случае оптимальный маршрут будет определяться с учётом расписания движения общественного транспорта, текущей загруженности дорог и других условий.

Задача OPP является базовой для многих других задач оптимизации маршрутов, таких как Shortest Path Problem (SPP), Traveling Salesman Problem (TSP), Vehicle Routing Problem (VRP) и Multi-Constrained Optimal Path Problem (MCOP), каждая из которых имеет свои уникальные особенности и требования.

Поиск кратчайшего пути (SPP- Shortest Path Problem)

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

В математическом контексте эти дома становятся вершинами графа, дороги – рёбрами графа, а длина дороги может обозначать вес ребра. Таким образом, логистическая задача «Найти самый короткий путь от дома А до дома Б» трансформируется в математическую задачу определения кратчайшего пути между двумя вершинами графа.

Для решения этой задачи есть несколько известных алгоритмов (Дейкстры, Беллмана-Форда и другие).

Такие задачи легко решают семиклассники на кружках по математике. Это задача «Поиск кратчайшего пути», и она лежит в основе геосервисов, связанных с маршрутизацией.

Классика жанра — задача коммивояжера (TSP — Traveling Salesman Problem)

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

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

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

Выбор подходящего алгоритма зависит от условий конкретной задачи: размера входных данных, особенности графа, требований к скорости вычислений и точности результата, доступных времени и ресурсов. Для ускорения вычислений и повышения точности маршрутов может использоваться комбинация методов.

Решение проблемы коммивояжера — самая известная задача оптимизации маршрутов и одна из самых распространённых задач в логистике.

Задача выбора маршрута транспорта (VRP — Vehicle Routing Problem)

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

Анализируются локации начала и завершения рабочего дня, затраты, ёмкость транспортных средств и объём перевозимого груза, временные окна, перерывы, зоны охвата.

Оценка пропускной способности и потока

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

Значение потока на конкретном ребре не может превышать его пропускную способность.

Эти понятия являются ключевыми при моделировании и оптимизации различных сетевых систем и применяются во многих отраслях, например:

• Транспорт: развитие дорожной инфраструктуры, оптимизация движения транспорта и распределение пассажиропотоков.
• Телекоммуникации: проектирование сетевой инфраструктуры и расчёт загрузки каналов.
• Энергетика: моделирование потоков электроэнергии и оптимизация систем газо- и нефтепроводов.
• Гидрология: моделирование потоков воды и планирование использования водных ресурсов.
• Городское планирование: оценка пешеходных потоков и планирование городской инфраструктуры.

Поиск оптимального маршрута в интерактивном режиме

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

Сервисы моделируют различные сценарии движения и прокладывают оптимальные маршруты в реальном времени, учитывая даже непредвиденные обстоятельства и «запасные» маршруты.

Ключевым моментом является выбор оптимального пути, минимизирующего «стоимость» передвижения. «Стоимость» пути может быть измерена во времени в пути или в длине пути.

Определение зоны охвата

Какие конкуренты находятся в радиусе 500 метров от магазина? Или какие дома находятся на расстоянии 5 минут пешком от метро?

Зоны используются для оценки транспортной и пешей доступности исследуемой локации.

Зоны охвата моделируются обычно двумя способами: в виде окружности или изохроны.

1. Построение буферной зоны в виде окружности

Буферные зоны — это равноудаленные области вокруг объекта на карте. Они создаются вокруг точек, линий или площадей.

Примером может служить карта возле входа в метро, где центральная точка указывает «Вы здесь», а окружность включает в себя объекты в пределах пяти минутах пешком.

Буферная зона даёт понимание о доступности объектов, но не учитывает препятствия (например, показать, что за пять минут можно добраться до другого берега реки по воде пешком).

Для более точных расчётов требуется учет реальной инфраструктуры.

2. Изохроны

При использовании сетевого анализа для определения зоны охвата строятся не окружности, а более сложные фигуры – изохроны.

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

Время в пути зависит от того, идти ли пешком, использовать автомобиль или общественный транспорт.

Зоны охвата могут различаться по размеру в зависимости от транспортной инфраструктуры, а также меняться в соответствии с изменениями трафика в течение дня и на выходных.

В зависимости от задачи учитываются различные данные, влияющие на точность изохрон:

• Автомобильные дорожные пути, включая информацию о характеристиках участков дорог (качество покрытия, платные участки, светофоры и т.д.)
• Пешеходные пути и тропы (тротуары, переходы, тропы, лестницы, мосты и т.д.)
• Инфраструктура общественного транспорта: автобусные остановки и метро, железнодорожные платформы, а также информация о маршрутах и расписании.
• Ограничения на дорогах: односторонние участки, зоны с ограниченной скоростью, запреты для определенных видов транспорта, ограничения для грузовиков и др.
• Географические особенности: водные препятствия и др.
• Временные факторы: пробки, ремонтные работы или временные ограничения.

Поиск ближайшей точки

Поиск близлежащих точек интереса (аптек, банкоматов, вестибюлей метро, заправок, школ и т.д.) рядом.

Этот механизм расчета использует алгоритм с несколькими источниками и несколькими назначениями на основе алгоритмов поиска кратчайшего пути в графе.

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

Поиск оптимальной локации

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

Моделирование и сценарное планирование

Представьте, что вы решаете задачу расширения городской инфраструктуры.

Применение сетевого анализа дает возможность добавлять, удалять или модифицировать узлы и связи, позволяя просчитывать различные варианты развития.

Методы оптимизации в геоаналитике

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

Модель оптимизации включает в себя следующие элементы:

• Переменные, определяющие оптимальное решение задачи. Например, нужно ли открывать новый распределительный центр в определенной локации, или выбор оптимального способа и времени доставки посылок.
• Целевая функция. Значение, по которому оценивается эффективность решения. Это может быть минимизация затрат на логистику или максимизация количества доставок.
• Условия, которые должны быть выполнены. Например, автомобиль не может перевозить товары весом более своей грузоподъёмности, разгрузка в каждой точке должна быть выполнена в течение определённого временного окна и так далее.
• Поиск решения. Для поиска оптимального решения алгоритмы анализируют различные комбинации переменных, исходя из целевой функции и ограничений.

«Здесь вам не равнина — здесь климат иной» или геопространственные дополнения к методам сетевого анализа

Геопространственные системы представлять собой сложную сеть взаимосвязанных объектов и явлений. В разных проектах приходится принимать во внимание свой набор критериев и атрибутов вершин и рёбер графов. Например,

• Рельеф. Графы могут быть использованы для представления географических объектов, в которых вершины соответствуют определенным точкам, а рёбра — путям между ними. Рельеф может влиять на сложность и стоимость передвижения между этими точками. При оптимизации маршрутов можно учитывать высотные различия, склоны и другие аспекты рельефа для выбора наилучшего пути.
• Ветер и другие метеорологические условия. Eсли задачей является оптимизация маршрутов для авиаперевозок или морских путей, то силу и направление ветра следует учитывать как важный критерий. Графы могут быть адаптированы для учета этих условий, где вес рёбер будет изменяться в зависимости от метеорологических данных.
• Другие геопространственные характеристики. Тип почвы, наличие водных преград, охранные зоны и т.д. Эти атрибуты могут быть включены в модель как дополнительные параметры или ограничения.

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

Для стандартных расчётов зон охвата и оптимальных маршрутов необходимо учесть ряд особенностей.

• Сложный рельеф. Горные тропы и дороги могут быть крутыми, извилистыми и узкими, что затрудняет доступ тяжелой пожарной техники к месту пожара, влияет на время в пути.
• Ограниченный доступ к воде. В горных районах может не быть достаточно естественных исходников воды, что делает ее перевозку и хранение критически важными.
• Ветер. В горах ветер может быстро менять направление и скорость, что усугубляет распространение пожара.
• Сухость. Горные районы, особенно на высотах, могут быть сухими, что увеличивает риск возгорания и распространения пожара.
• Изолированность. Некоторые горные районы могут быть удалены от основных населенных пунктов, что затрудняет быстрый доступ спасательных служб.
• Ограниченные ресурсы. Пожарные службы могут располагать ограниченными ресурсами по сравнению с городскими подразделениями.
• Эвакуация. Эвакуация жителей из горных районов может быть сложной из-за ограниченных путей выхода и удаленности от основных дорог.

В следующих статьях будем делиться интересными кейсами реализации подобных проектов.

Вместо заключения (или математика в географии)

Математики знают, что всё в мире можно описать с использованием математических понятий.

Первый закон географии Тоблера утверждает, что «Всё связано со всем, но близкие объекты связаны больше, чем далекие». Первый закон географии затрагивает струны души не только географов, но и математиков, ведь он может быть описан математическими терминами, с использованием структуры графа и взаимодействие между вершинами (объектами) и рёбрами (связями).

Это даёт возможность использовать весь мощный математический инструментарий для изучения пространственных взаимодействий и зависимостей, что я считаю удачей как для современных геоаналитиков, так и для тех математиков и инженеров, которые занимаются геоаналитикой.

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