Транспортная сеть , или транспортная сеть , представляет собой сеть или граф в географическом пространстве, описывающую инфраструктуру, которая допускает и ограничивает движение или поток. [1] Примеры включают, но не ограничиваются, дорожными сетями , железными дорогами , воздушными маршрутами , трубопроводами , акведуками и линиями электропередач . Цифровое представление этих сетей и методы их анализа являются основной частью пространственного анализа , географических информационных систем , коммунальных служб и транспортной инженерии . Сетевой анализ является приложением теорий и алгоритмов теории графов и является формой анализа близости .
Применимость теории графов к географическим явлениям была признана на раннем этапе. Многие из ранних проблем и теорий, разработанных теоретиками графов, были вдохновлены географическими ситуациями, такими как задача о семи мостах Кенигсберга , которая была одним из первоначальных оснований теории графов, когда ее решил Леонард Эйлер в 1736 году. [2]
В 1970-х годах эта связь была восстановлена ранними разработчиками географических информационных систем , которые использовали ее в топологических структурах данных полигонов (что здесь не имеет значения) и анализе транспортных сетей. Ранние работы, такие как Tinkler (1977), были сосредоточены в основном на простых схематических сетях, вероятно, из-за отсутствия значительных объемов линейных данных и вычислительной сложности многих алгоритмов. [3] Полная реализация алгоритмов сетевого анализа в программном обеспечении ГИС появилась только в 1990-х годах, [4] [5] но сегодня доступны довольно продвинутые инструменты.
Сетевой анализ требует подробных данных, представляющих элементы сети и ее свойства. [6] Ядром сетевого набора данных является векторный слой полилиний, представляющих пути перемещения, либо точные географические маршруты, либо схематические диаграммы, известные как ребра . Кроме того, необходима информация о топологии сети , представляющая соединения между линиями, что позволяет моделировать транспортировку с одной линии на другую. Обычно эти точки соединения, или узлы , включаются в качестве дополнительного набора данных. [7]
Как рёбрам, так и узлам приписываются свойства, связанные с движением или потоком:
Для решения проблем и задач, связанных с сетевым потоком, был разработан широкий спектр методов, алгоритмов и методик. Некоторые из них являются общими для всех типов транспортных сетей, в то время как другие специфичны для конкретных областей применения. [8] Многие из этих алгоритмов реализованы в коммерческом и открытом программном обеспечении ГИС, таком как GRASS GIS и расширение Network Analyst для Esri ArcGIS .
Одной из самых простых и распространенных задач в сети является поиск оптимального маршрута, соединяющего две точки вдоль сети, при этом оптимальный определяется как минимизация некоторой формы затрат, такой как расстояние, затраты энергии или время. [9] Распространенным примером является поиск направлений в уличной сети, функция почти любого веб-приложения для картографирования улиц, такого как Google Maps . Наиболее популярным методом решения этой задачи, реализованным в большинстве ГИС и картографического программного обеспечения, является алгоритм Дейкстры . [10]
В дополнение к базовой маршрутизации «точка-точка» распространены также задачи составной маршрутизации . Задача коммивояжера требует оптимального (наименьшее расстояние/стоимость) упорядочения и маршрута для достижения ряда пунктов назначения; это NP-трудная задача, но ее несколько легче решить в сетевом пространстве, чем в неограниченном пространстве из-за меньшего набора решений. [11] Задача маршрутизации транспортных средств является обобщением этой задачи, допускающим несколько одновременных маршрутов для достижения пунктов назначения. Задача проверки маршрута или «китайский почтальон» требует оптимального (наименьшее расстояние/стоимость) пути, который пересекает каждое ребро; распространенным приложением является маршрутизация мусоровозов. Это оказывается гораздо более простой задачей для решения с помощью алгоритмов полиномиального времени .
Этот класс задач направлен на поиск оптимального местоположения для одного или нескольких объектов вдоль сети, при этом оптимальное определяется как минимизация совокупной или средней стоимости поездки в (или из) другой набор точек в сети. Распространенным примером является определение местоположения склада для минимизации стоимости доставки в набор розничных точек или местоположения розничной точки для минимизации времени поездки от мест проживания ее потенциальных клиентов. В неограниченном (декартовы координаты) пространстве это NP-трудная задача, требующая эвристических решений, таких как алгоритм Ллойда , но в сетевом пространстве ее можно решить детерминированно. [12]
Конкретные приложения часто добавляют дополнительные ограничения к проблеме, такие как местоположение уже существующих или конкурирующих объектов, мощности объектов или максимальная стоимость.
Зона обслуживания сети аналогична буферу в неограниченном пространстве, изображению области, которая может быть достигнута из точки (обычно объекта обслуживания) менее чем за указанное расстояние или другие накопленные затраты. [13] Например, предпочтительная зона обслуживания для пожарной станции будет набором сегментов улицы, которые она может достичь за небольшое время. Когда есть несколько объектов, каждое ребро будет назначено ближайшему объекту, создавая результат, аналогичный диаграмме Вороного . [14]
Распространенным применением в коммунальных сетях является определение возможных мест неисправностей или разрывов в сети (которые часто скрыты или иным образом трудно поддаются непосредственному наблюдению) на основе отчетов, которые можно легко найти, например, жалоб клиентов.
Дорожное движение широко изучалось с использованием методов статистической физики. [15] [16] [17]
Чтобы обеспечить максимальную эффективность железнодорожной системы, необходимо также провести анализ сложности/вертикали. Этот анализ поможет в анализе будущих и существующих систем, что имеет решающее значение для обеспечения устойчивости системы (Беднар, 2022, стр. 75–76). Вертикальный анализ будет состоять из знания операционной деятельности (повседневных операций) системы, предотвращения проблем, контроля деятельности, разработки деятельности и координации деятельности. [18]
{{cite book}}: CS1 maint: multiple names: authors list (link)