Введение

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

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

История

Применимость теории графов к географическим явлениям была признана на раннем этапе. Многие из первых задач и теорий, разработанных теоретиками графов, были вдохновлены географическими ситуациями, например, проблемой о семи мостах Кёнигсберга, которая стала одним из основополагающих моментов теории графов, когда она была решена Леонардом Эйлером в 1736 году. В 1970-х годах эта связь была восстановлена первыми разработчиками географических информационных систем, которые использовали теорию графов в топологических структурах данных для полигонов (что не имеет отношения к данной работе), а также при анализе транспортных сетей. Ранние работы, такие как работа Тинклера (1977), в основном фокусировались на простых схематических сетях, вероятно, из-за недостатка значительных объемов линейных данных и вычислительной сложности многих алгоритмов. Полная реализация алгоритмов сетевого анализа в программном обеспечении ГИС появилась лишь в 1990-х годах, но в настоящее время доступны гораздо более продвинутые инструменты.

Методы анализа

Для решения широкого круга задач и проблем, связанных с сетевыми потоками, разработаны разнообразные методы, алгоритмы и техники. Некоторые из них применимы ко всем типам транспортных сетей, а другие – специфичны для отдельных областей применения. Многие из этих алгоритмов реализованы в коммерческом и открытом программном обеспечении ГИС, например, в GRASS GIS и расширении Network Analyst для Esri ArcGIS.

Оптимальная маршрутизация

Одной из самых простых и распространенных задач в сети является поиск оптимального маршрута, соединяющего две точки, при этом оптимальность определяется как минимизация определенных затрат, таких как расстояние, энергозатраты или время. Типичным примером является поиск маршрута в дорожной сети, функция, реализованная практически в любом веб-приложении для картографирования дорог, например, в Google Maps. Наиболее популярным методом решения этой задачи, используемым в большинстве ГИС и картографических программ, является алгоритм Дейкстры. Помимо базовой маршрутизации между двумя точками, часто встречаются и составные задачи маршрутизации. Задача коммивояжера требует определения оптимальной (минимальной по расстоянию/стоимости) последовательности посещения и маршрута для достижения нескольких пунктов назначения; это NP-трудная задача, но ее несколько легче решить в сетевом пространстве, чем в неограниченном, благодаря меньшему множеству возможных решений. Задача маршрутизации транспортных средств является ее обобщением, позволяющим использовать несколько маршрутов одновременно для достижения пунктов назначения. Задача обхода маршрута, или "Задача китайского почтальона", требует найти оптимальный (минимальный по расстоянию/стоимости) путь, проходящий по всем ребрам сети; типичным применением является маршрутизация мусоровозов. Оказывается, эту задачу гораздо проще решить, используя алгоритмы с полиномиальной сложностью.

Анализ местоположения

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

Области обслуживания

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

Анализ неисправностей

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

Транспортная техника

Дорожное движение широко исследовалось с применением методов статистической физики.

Вертикальный анализ

Для обеспечения максимальной эффективности железнодорожной системы также следует провести анализ сложности и вертикальный анализ. Этот анализ поможет в анализе как будущих, так и существующих систем, что крайне важно для обеспечения устойчивости системы (Bednar, 2022, pp. 75–76). Вертикальный анализ будет включать в себя знание операционной деятельности (повседневной работы) системы, предотвращение возникновения проблем, контрольные мероприятия, развитие деятельности и координацию действий.