Транспортная сеть или транспортная сеть — это сеть или граф в географическом пространстве, описывающий инфраструктуру, которая разрешает и ограничивает движение или поток. [1] Примеры включают, помимо прочего, дорожные сети , железные дороги , воздушные трассы , трубопроводы , акведуки и линии электропередач . Цифровое представление этих сетей и методы их анализа являются основной частью пространственного анализа , географических информационных систем , коммунального хозяйства и транспортного машиностроения . Сетевой анализ — это применение теорий и алгоритмов теории графов и форма анализа близости .
Применимость теории графов к географическим явлениям была признана довольно рано. Многие из ранних задач и теорий, разработанных теоретиками графов, были вдохновлены географическими ситуациями, такими как проблема семи мостов Кенигсберга , которая была одной из первоначальных основ теории графов, когда она была решена Леонардом Эйлером в 1736 году. [2]
В 1970-х годах связь была восстановлена первыми разработчиками географических информационных систем , которые использовали ее в топологических структурах данных полигонов (что здесь не имеет значения) и анализе транспортных сетей. Ранние работы, такие как Тинклер (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)