Анализ транспортной сети
| Часть серии о | ||||
| Сетевая наука | ||||
|---|---|---|---|---|
| Типы сетей | ||||
| Графики | ||||
| ||||
| Модели | ||||
| ||||
| ||||
или Транспортная сеть транспортная сеть — это сеть или граф в географическом пространстве, описывающий инфраструктуру, которая разрешает и ограничивает движение или поток. [1] Примеры включают, помимо прочего, дорожные сети , железные дороги , воздушные трассы , трубопроводы , акведуки и линии электропередачи . Цифровое представление этих сетей и методы их анализа являются основной частью пространственного анализа , географических информационных систем , коммунального хозяйства и транспортного машиностроения . Сетевой анализ — это применение теорий и алгоритмов теории графов и форма анализа близости .
История [ править ]
Применимость теории графов к географическим явлениям была признана довольно рано. Многие из ранних задач и теорий, разработанных теоретиками графов, были вдохновлены географическими ситуациями, такими как проблема семи мостов Кенигсберга , которая была одной из первоначальных основ теории графов, когда она была решена Леонардом Эйлером в 1736 году. [2]
В 1970-х годах связь была восстановлена первыми разработчиками географических информационных систем , которые использовали ее в топологических структурах данных полигонов (что здесь не имеет значения) и анализе транспортных сетей. Ранние работы, такие как Тинклер (1977), были сосредоточены в основном на простых схематических сетях, вероятно, из-за отсутствия значительных объемов линейных данных и вычислительной сложности многих алгоритмов. [3] Полная реализация алгоритмов сетевого анализа в программном обеспечении ГИС появилась только в 1990-х годах. [4] [5] но сегодня, как правило, доступны довольно продвинутые инструменты.
Сетевые данные [ править ]
Сетевой анализ требует подробных данных, представляющих элементы сети и ее свойства. [6] Ядром набора сетевых данных является векторный слой полилиний, представляющих пути перемещения, либо точные географические маршруты, либо схематические диаграммы, известные как ребра . Кроме того, необходима информация о топологии сети , представляющая соединения между линиями, что позволяет моделировать транспортировку с одной линии на другую. Обычно эти точки подключения или узлы включаются в качестве дополнительного набора данных. [7]
И краям, и узлам приписываются свойства, связанные с движением или потоком:
- Пропускная способность — измерение любых ограничений допустимого объема потока, таких как количество полос на дороге, полоса пропускания телекоммуникаций или диаметр трубы.
- Импеданс , измерение любого сопротивления потоку или скорости потока, например, ограничение скорости или запрещенное направление поворота на перекрестке улиц.
- Стоимость, накопленная в результате индивидуального путешествия по краю или через узел, обычно затраченное время, в соответствии с принципом трения расстояния . Например, узлу уличной сети может потребоваться разное количество времени для совершения определенного поворота налево или направо. Такие затраты могут меняться со временем, например, время в пути по городской улице зависит от суточных циклов интенсивности движения.
- Объем потока , измерения фактического происходящего движения. Это могут быть конкретные закодированные во времени измерения, собранные с использованием сенсорных сетей , таких как счетчики трафика , или общие тенденции за определенный период времени, такие как среднегодовой дневной трафик (AADT).
Методы анализа [ править ]
Для решения проблем и задач, связанных с сетевым потоком, разработан широкий спектр методов, алгоритмов и приемов. Некоторые из них являются общими для всех типов транспортных сетей, тогда как другие специфичны для конкретных областей приложений. [8] Многие из этих алгоритмов реализованы в коммерческом программном обеспечении ГИС с открытым исходным кодом, таком как GRASS GIS и расширении Network Analyst для Esri ArcGIS .
Оптимальная маршрутизация [ править ]
Одной из самых простых и распространенных задач в сети является поиск оптимального маршрута, соединяющего две точки сети, причем оптимальный определяется как минимизация некоторой формы затрат, таких как расстояние, затраты энергии или время. [9] Типичным примером является поиск направлений в уличной сети, функция практически любого веб-приложения для картографирования улиц, такого как Google Maps . Самым популярным методом решения этой задачи, реализованным в большинстве ГИС и картографических программ, является алгоритм Дейкстры . [10]
Помимо базовой маршрутизации «точка-точка», проблемы составной маршрутизации также распространены . Задача коммивояжера требует оптимального (наименьшее расстояние/стоимость) заказа и маршрута для достижения нескольких пунктов назначения; это NP-сложная задача, но ее несколько легче решить в сетевом пространстве, чем в неограниченном пространстве, из-за меньшего набора решений. [11] Задача маршрутизации транспортных средств является ее обобщением, позволяющим использовать несколько одновременных маршрутов для достижения пунктов назначения. или Проверка маршрута задача «Китайский почтальон» требует поиска оптимального (наименьшего расстояния/стоимости) пути, пересекающего каждое ребро; Распространенным применением является маршрутизация мусоровозов. Оказывается, эту задачу гораздо проще решить с помощью алгоритмов с полиномиальным временем .
Анализ местоположения [ править ]
Этот класс задач направлен на поиск оптимального местоположения для одного или нескольких объектов в сети, причем оптимальное определяется как минимизация совокупной или средней стоимости поездки в (или из) другого набора точек в сети. Типичным примером является определение местоположения склада, чтобы минимизировать затраты на доставку до ряда торговых точек, или расположение торговой точки, чтобы минимизировать время в пути от мест проживания потенциальных клиентов. В неограниченном (декартовых координатах) пространстве это NP-сложная задача, требующая эвристических решений, таких как алгоритм Ллойда , но в сетевом пространстве ее можно решить детерминированно. [12]
Конкретные приложения часто добавляют дополнительные ограничения к проблеме, такие как расположение уже существующих или конкурирующих объектов, мощность объекта или максимальная стоимость.
Зоны обслуживания [ править ]
Зона обслуживания сети аналогична буферу в неограниченном пространстве, изображению области, до которой можно добраться из точки (обычно из пункта обслуживания) на расстоянии, меньшем указанного, или за счет других накопленных затрат. [13] Например, предпочтительной зоной обслуживания пожарной части будет набор участков улицы, до которых она может добраться за небольшой промежуток времени. При наличии нескольких объектов каждое ребро будет присвоено ближайшему объекту, что даст результат, аналогичный диаграмме Вороного . [14]
Анализ неисправностей [ править ]
Распространенным применением в коммунальных сетях общего пользования является идентификация возможных мест неисправностей или разрывов в сети (которые часто скрыты или иным образом трудно наблюдать напрямую), выведенная из отчетов, которые можно легко найти, например, жалоб клиентов.
Транспортное машиностроение [ править ]
Движение транспорта широко изучалось с использованием методов статистической физики. [15] [16] [17]
Вертикальный анализ [ править ]
Чтобы обеспечить максимальную эффективность железнодорожной системы, необходимо также провести комплексный/вертикальный анализ. Этот анализ поможет в анализе будущих и существующих систем, что имеет решающее значение для обеспечения устойчивости системы (Беднар, 2022, стр. 75–76). Вертикальный анализ будет состоять из знания операционной деятельности (повседневных операций) системы, предотвращения проблем, действий по контролю, разработки действий и координации действий. [18]
См. также [ править ]
- Парадокс Брасса
- Проточная сеть
- Эвристическая маршрутизация
- Межпланетная транспортная сеть
- Сетевая наука
- Теория перколяции
- Уличная сеть
- Железнодорожная сеть
- Размер шоссе
- Мультимодальные перевозки
- Цепочка поставок
- Логистика
Ссылки [ править ]
- ^ Бартелеми, Марк (2010). «Пространственные сети». Отчеты по физике . 499 (1–3): 1–101. arXiv : 1010.0302 . Бибкод : 2011ФР...499....1Б . дои : 10.1016/j.physrep.2010.11.002 . S2CID 4627021 .
- ^ Эйлер, Леонард (1736). «Решение задачи, касающейся геометрии площадки». Комментарий. акад. Знать У. Петроп. 8, 128–40.
- ^ Тинклер, К.Дж. (1977). «Введение в методы теории графов в географии» (PDF) . КАТМОГ (14).
- ^ Ахуджа Р.К., Маньянти Т.Л., Орлин Дж.Б. (1993) Сетевые потоки: теория, алгоритмы и приложения . Прентис Холл, Энглвуд Клиффс, Нью-Джерси, США
- ^ Даскин М.С. (1995) Сеть и дискретное местоположение — модели, алгоритмы и приложения . Уайли, Нью-Джерси, США
- ^ «Что такое набор сетевых данных?» . Документация ArcGIS Pro . Эсри.
- ^ «Элементы сети» . Документация ArcGIS Pro . Эсри . Проверено 17 марта 2021 г.
- ^ деСмит, Майкл Дж.; Гудчайлд, Майкл Ф.; Лонгли, Пол А. (2021). «7.2.1 Обзор – сетевой и локальный анализ» . Геопространственный анализ: всеобъемлющее руководство по принципам, методам и программным инструментам (6-е исправленное изд.).
- ^ Уорбойс, Майкл; Дакэм, Мэтт (2004). «5.7 Сетевое представление и алгоритмы». ГИС: вычислительная перспектива (2-е изд.). ЦРК Пресс. стр. 211–218.
- ^ Дейкстра, EW (1959). «Заметка о двух проблемах, связанных с графами» (PDF) . Нумерическая математика . 1 : 269–271. дои : 10.1007/BF01386390 . S2CID 123284777 .
- ^ «команда v.net.salesman» . Руководство по GRASS ГИС . ОСГЕО . Проверено 17 марта 2021 г.
- ^ деСмит, Майкл Дж.; Гудчайлд, Майкл Ф.; Лонгли, Пол А. (2021). «7.4.2 Более крупные проблемы с p-медианой и p-центром» . Геопространственный анализ: всеобъемлющее руководство по принципам, методам и программным инструментам (6-е исправленное изд.).
- ^ деСмит, Майкл Дж.; Гудчайлд, Майкл Ф.; Лонгли, Пол А. (2021). «7.4.3 Зоны обслуживания» . Геопространственный анализ: всеобъемлющее руководство по принципам, методам и программным инструментам (6-е исправленное изд.).
- ^ «команда v.net.alloc» . ГИС-документация GRASS . ОСГЕО . Проверено 17 марта 2021 г.
- ^ Хелбинг, Д. (2001). «Трафик и связанные с ним автономные многочастичные системы». Обзоры современной физики . 73 (4): 1067–1141. arXiv : cond-mat/0012229 . Бибкод : 2001RvMP...73.1067H . дои : 10.1103/RevModPhys.73.1067 . S2CID 119330488 .
- ^ С., Кернер, Борис (2004). Физика дорожного движения: эмпирические особенности схемы автомагистралей, инженерные приложения и теория . Берлин, Гейдельберг: Springer Berlin Heidelberg. ISBN 9783540409861 . OCLC 840291446 .
{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Вольф, Делавэр; Шрекенберг, М; Бахем, А. (июнь 1996 г.). Трафик и гранулированный поток . МИРОВАЯ НАУЧНАЯ. стр. 1–394. дои : 10.1142/9789814531276 . ISBN 9789810226350 .
- ^ Беднар, 2022, стр. 75–76.
| Базы данных органов управления : Национальные |
|---|
