Из Википедии, бесплатной энциклопедии
  (Перенаправлено из транспортной сети )
Перейти к навигации Перейти к поиску
Для математической теории графов транспортной сети см. Потоковая сеть .
Сетевая наука
Internet_map_1024.jpg
Теория
Типы сетей
Графики
Функции
Типы
  • Двудольный
  • Полный
  • Режиссер
  • Гипер
  • Мульти
  • Случайный
  • Взвешенный
МетрикиАлгоритмы
  • Центральность
  • Степень
  • Мотив
  • Кластеризация
  • Распределение степеней
  • Ассортативность
  • Расстояние
  • Модульность
  • Эффективность
Модели
Топология
  • Случайный график
  • Эрдеш – Реньи
  • Барабаши – Альберт
  • Фитнес-модель
  • Уоттс-Строгац
  • Экспоненциальный случайный (ERGM)
  • Случайный геометрический (RGG)
  • Гиперболический (HGN)
  • Иерархический
  • Стохастический блок
  • Максимальная энтропия
  • Мягкая конфигурация
  • Тест LFR
Динамика
  • Логическая сеть
  • агент на основе
  • Эпидемия / SIR
СпискиКатегории
  • Темы
  • Программное обеспечение
  • Сетевые ученые
  • Категория: Теория сетей
  • Категория: Теория графов
  • v
  • т
  • е

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

История [ править ]

Применимость теории графов к географическим явлениям была признана рано. Фактически, многие из ранних проблем и теорий, предпринятых теоретиками графов, были вдохновлены географическими ситуациями, такими как проблема семи мостов Кенигсберга , которая была одной из первоначальных основ теории графов, когда она была решена Леонардом Эйлером в 1736 году. [ 2]

В 1970-х годах связь была восстановлена ​​первыми разработчиками географических информационных систем , которые использовали ее в топологических структурах данных полигонов (что здесь не имеет значения) и анализе транспортных сетей. Ранние работы, такие как Tinkler (1977), были сосредоточены в основном на простых схематических сетях, вероятно, из-за отсутствия значительных объемов линейных данных и вычислительной сложности многих алгоритмов. [3] Полная реализация алгоритмов сетевого анализа в программном обеспечении ГИС не появлялась до 1990-х годов, [4] [5], но довольно продвинутые инструменты, как правило, доступны сегодня.

Сетевые данные [ править ]

Сетевой анализ требует подробных данных, представляющих элементы сети и ее свойства. [6] Ядром набора сетевых данных является векторный слой из полилиний, представляющих пути движения, точные географические маршруты или схематические изображения, известные как края . Кроме того, необходима информация о топологии сети , представляющей соединения между линиями, что позволяет моделировать транспорт от одной линии к другой. Обычно эти точки подключения или узлы включаются в качестве дополнительного набора данных. [7]

И ребрам, и нотам приписываются свойства, связанные с движением или потоком:

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

Методы анализа [ править ]

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

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

Основные статьи: проблема кратчайшего пути и алгоритм Дейкстры

Одна из самых простых и распространенных задач в сети - найти оптимальный маршрут, соединяющий две точки в сети, при этом оптимальный определяется как минимизация некоторых форм затрат, таких как расстояние, затраты энергии или время. [9] Типичный пример - поиск направлений в уличной сети, функция практически любого веб-приложения для картографии улиц, такого как карты Google . Самым популярным методом решения этой задачи, реализованным в большинстве программ ГИС и картографии, является алгоритм Дейкстры . [10]

В дополнение к базовой двухточечной маршрутизации также распространены проблемы составной маршрутизации . Задача коммивояжера требует оптимального (наименьшее расстояние / стоимость) заказа и маршрута для достижения ряда пунктов назначения; это NP-сложная проблема, но ее несколько легче решить в сетевом пространстве, чем в неограниченном, из-за меньшего набора решений. [11] Проблема маршрутизации транспортных средств является обобщением этого, позволяя использовать несколько одновременных маршрутов для достижения пункта назначения. Осмотр маршрутаили задача "китайский почтальон" требует оптимального (наименьшего расстояния / стоимости) пути, который проходит через каждое ребро; обычное приложение - это маршрут для мусоровозов. Оказывается, эту задачу гораздо проще решить с помощью алгоритмов с полиномиальным временем .

Анализ местоположения [ править ]

Основные статьи: проблема размещения объекта и размещение-размещение

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

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

Зоны обслуживания [ править ]

Зона обслуживания сети аналогична буферу в неограниченном пространстве, изображению области, которая может быть достигнута из точки (обычно объекта обслуживания) на меньшем, чем указанное расстояние или с другими накопленными затратами. [13] Например, предпочтительной зоной обслуживания пожарного депо будет набор сегментов улицы, который он может достичь за небольшой промежуток времени. Когда имеется несколько предприятий, каждое ребро будет назначено ближайшему предприятию, что даст результат, аналогичный диаграмме Вороного . [14]

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

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

Транспортная инженерия [ править ]

Основные статьи: Транспортное машиностроение и Транспортные потоки

Движение широко изучено с использованием методов статистической физики. [15] [16] [17] Недавно реальная транспортная сеть Пекина была изучена с использованием сетевого подхода и теории перколяции. Исследование показало, что можно охарактеризовать качество глобального трафика в городе в любое время дня, используя порог перколяции, см. Рис. 1. В недавних статьях теория перколяции применялась для изучения загруженности дорог в городе. Качество глобального трафика в городе в данный момент времени определяется одним параметром - критическим порогом перколяции. Критический порог представляет собой скорость, ниже которой можно двигаться в значительной части городской сети. Этот метод позволяет выявить повторяющиеся узкие места трафика. [18] Критические показатели, характеризующие распределение хорошего трафика по размеру кластера, аналогичны показателям теории перколяции. [19] Также обнаружено, что в часы пик транспортная сеть может иметь несколько метастабильных состояний разных размеров сети и чередоваться между этими состояниями. [20]

Эмпирическое исследование распределения размеров пробок было недавно проведено Zhang et al. [21] Они нашли приблизительный универсальный степенной закон для распределения размеров затора.

Серок и др. Разработали метод определения функциональных кластеров пространственно-временных улиц, которые представляют свободный транспортный поток в городе. [22] G. Li et al. [23] разработали метод проектирования оптимальной двухуровневой транспортной сети в городе.

Рис. 1: Распространение транспортных сетей в типичный день в Пекине. A Показывает высокоскоростные кластеры. В B можно увидеть кластеры на критическом пороге, где гигантский компонент разрушается. C Показывает случай низкой скорости, когда можно добраться до всего города. В D можно увидеть перколяционное поведение самого большого (зеленый) и второго по величине (оранжевый) компонентов в зависимости от относительной скорости. E Показывает критический порог q в течение дня для рабочих и выходных дней. Высокое q означает хороший глобальный трафик, а низкое q - плохой трафик - в час пик.

Схемы движения трафика [ править ]

Речные модели транспортных потоков в городских районах больших городов в часы пик и не в часы пик были изучены Yohei Shida et al. [24]

См. Также [ править ]

  • Парадокс брасса
  • Поточная сеть
  • Эвристическая маршрутизация
  • Межпланетная транспортная сеть
  • Сетевая наука
  • Теория перколяции
  • Уличная сеть
  • Железнодорожная сеть
  • Мультимодальные перевозки

Ссылки [ править ]

  1. Перейти ↑ Barthelemy, Marc (2010). «Пространственные сети». Отчеты по физике . 499 (1–3): 1–101. arXiv : 1010.0302 . Bibcode : 2011PhR ... 499 .... 1B . DOI : 10.1016 / j.physrep.2010.11.002 . S2CID  4627021 .
  2. ^ Эйлер, Леонард (1736). "Solutio problematis ad geometriam situs pertinentis". Комментарий. Акад. Sci. У. Петроп 8, 128–40.
  3. ^ Тинклер, KJ (1977). "Введение в теоретические методы графов в географии" (PDF) . КАТМОГ (14).
  4. ^ Ахуджа Р.К., Магнанти Т.Л., Орлин Дж.Б. (1993) Сетевые потоки: теория, алгоритмы и приложения . Прентис Холл, Энглвуд Клиффс, Нью-Джерси, США
  5. ^ Даскин М.С. (1995) Сеть и дискретное местоположение - модели, алгоритмы и приложения . Уайли, штат Нью-Джерси, США
  6. ^ "Что такое набор сетевых данных?" . Документация ArcGIS Pro . Esri.
  7. ^ «Сетевые элементы» . Документация ArcGIS Pro . Esri . Проверено 17 марта 2021 года .
  8. ^ деСмит, Майкл Дж .; Гудчайлд, Майкл Ф .; Лонгли, Пол А. (2021). «7.2.1 Обзор - сетевой и локационный анализ» . Геопространственный анализ: всеобъемлющее руководство по принципам, методам и программным средствам (6-е пересмотренное издание).
  9. ^ Worboys, Майкл; Дакхэм, Мэтт (2004). «5.7 Сетевое представление и алгоритмы». ГИС: вычислительная перспектива (2-е изд.). CRC Press. С. 211–218.
  10. Перейти ↑ Dijkstra, EW (1959). «Заметка о двух проблемах, связанных с графиками» (PDF) . Numerische Mathematik . 1 : 269–271. DOI : 10.1007 / BF01386390 . S2CID 123284777 .  
  11. ^ "v.net.salesman команда" . Руководство GRASS GIS . ОСГЕО . Проверено 17 марта 2021 года .
  12. ^ деСмит, Майкл Дж .; Гудчайлд, Майкл Ф .; Лонгли, Пол А. (2021). «7.4.2 Большие проблемы p-медианы и p-центра» . Геопространственный анализ: всеобъемлющее руководство по принципам, методам и программным средствам (6-е пересмотренное издание).
  13. ^ деСмит, Майкл Дж .; Гудчайлд, Майкл Ф .; Лонгли, Пол А. (2021). «7.4.3 Зоны обслуживания» . Геопространственный анализ: всеобъемлющее руководство по принципам, методам и программным средствам (6-е пересмотренное издание).
  14. ^ "команда v.net.alloc" . Документация GRASS GIS . ОСГЕО . Проверено 17 марта 2021 года .
  15. ^ Хелбинг D (2001). «Трафик и связанные с ним самоуправляемые системы многих частиц». Обзоры современной физики . 73 (4): 1067–1141. arXiv : cond-mat / 0012229 . Bibcode : 2001RvMP ... 73.1067H . DOI : 10.1103 / RevModPhys.73.1067 . S2CID 119330488 . 
  16. ^ С., Кернер, Борис (2004). Физика движения: эмпирические особенности схемы автострад, инженерные приложения и теория . Берлин, Гейдельберг: Springer Berlin Heidelberg. ISBN 9783540409861. OCLC  840291446 .
  17. ^ Вольф, Германия; Schreckenberg, M; Бахем, А (июнь 1996 г.). Трафик и гранулярный поток . Трафик и гранулярный поток . МИРОВАЯ НАУЧНАЯ. С. 1–394. DOI : 10,1142 / 9789814531276 . ISBN 9789810226350.
  18. ^ Ли, Дацин; Фу, Боуэн; Ван, Юньпэн; Лу, Гуанцюань; Березин, Йехиель; Стэнли, Х. Юджин; Хавлин, Шломо (2015-01-20). «Перколяционный переход в динамической сети трафика с развивающимися критическими узкими местами» . Труды Национальной академии наук . 112 (3): 669–672. Bibcode : 2015PNAS..112..669L . DOI : 10.1073 / pnas.1419185112 . ISSN 0027-8424 . PMC 4311803 . PMID 25552558 .   
  19. ^ Переключение между критическими режимами перколяции в динамике городского движения, G Zeng, D Li, S Guo, L Gao, Z Gao, HE Stanley, S Havlin, Proceedings of the National Academy of Sciences 116 (1), 23-28 (2019)
  20. ^ Г. Цзэн, Дж. Гао, Л. Шехтман, С. Го, В. Львов, Дж. Ву, Х. Лю, О. Леви, Д. Ли, ... (2020). «Множественные метастабильные состояния сети в городском трафике» . Труды Национальной академии наук . 117 (30): 17528–17534. DOI : 10.1073 / pnas.1907493117 . PMC 7395445 . PMID 32661171 .  CS1 maint: несколько имен: список авторов ( ссылка )
  21. ^ Устойчивость к реальным пробкам без масштабов, Лимиао Чжан, Гуаньвэнь Цзэн, Дацин Ли, Хай-Цзюнь Хуанг, Х. Юджин Стэнли, Шломо Хавлин, Труды Национальной академии наук 116 (18), 8673-8678 (2019)
  22. ^ Нимрод Serok, Орр Леви, Шломо Хавлин, Эфрат Блюменфельд-Lieberthal (2019). «Выявление взаимосвязей между сетью городских улиц и их динамическими транспортными потоками: значение для планирования». Публикации SAGE . 46 (7): 1362.CS1 maint: несколько имен: список авторов ( ссылка )
  23. ^ Г. Ли, SDS Reis, А.А. Морейра, С. Хавлин, Стенли, JS Андраде младший (2010). «К принципам проектирования оптимальных транспортных сетей». Phys. Rev. Lett . 104 (1): 018701. arXiv : 0908.3869 . Bibcode : 2010PhRvL.104a8701L . DOI : 10.1103 / PhysRevLett.104.018701 . PMID 20366398 . S2CID 119177807 .  CS1 maint: несколько имен: список авторов ( ссылка )
  24. ^ Ю. Шида, Х. Такаясу, С. Хавлин, М. Такаясу (2020). «Универсальные законы масштабирования моделей коллективных потоков людей в городских регионах» . Научные отчеты . 10 (1): 21405. DOI : 10.1038 / s41598-020-77163-2 . PMC 7722863 . PMID 33293581 .  CS1 maint: несколько имен: список авторов ( ссылка )