Маршрутизация транзитного узла

В прикладной математике маршрутизация транзитных узлов может использоваться для ускорения кратчайшего маршрута путем предварительного вычисления соединений между общими узлами доступа к подсети, соответствующей дальним поездкам. ^[1]

Маршрутизация транзитных узлов как фреймворк была создана в 2007 году ^[1], и в последующие годы появилось много конкретных реализаций, таких как подходы с использованием сеток, иерархий автомагистралей ^[2] и иерархий сжатия . ^[3] Маршрутизация транзитных узлов — это статический подход, требующий предварительной обработки попарных расстояний между важными узлами в графе (см. ниже, как выбираются эти узлы). Динамический подход не был опубликован. ^[4]

Интуиция

Несколько маршрутов, использующих одни и те же узлы доступа к междугородней дорожной сети.

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

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

Общая структура

1. Маршрутизация транзитных узлов начинается с выбора транзитных узлов как подмножества всех узлов дорожной сети. ${\displaystyle T\subseteq V}$ ${\displaystyle V}$
2. Для каждого узла выбираются выделенные наборы узлов прямого доступа и узлов обратного доступа из всех транзитных узлов. ${\displaystyle v\in V}$ ${\displaystyle {\overrightarrow {A}}(v)\subseteq T}$ ${\displaystyle {\overleftarrow {A}}(v)\subseteq T}$
3. Теперь рассчитываются и сохраняются попарные расстояния между транзитными узлами и расстояния между узлами и соответствующими им узлами доступа . ${\displaystyle D_{T}}$ ${\displaystyle v}$ ${\displaystyle d_{A}}$
4. Расстояние между двумя узлами теперь можно рассчитать как ${\displaystyle d(s,t)=\min _{u\in {\overrightarrow {A}}(s),v\in {\overleftarrow {A}}(t)}d_{A}(s,u)+D_{T}(u,v)+d_{A}(v,t)}$

Фильтр по местоположению

Короткие маршруты между близкими точками старта и назначения могут не требовать транзитных узлов. В этом случае указанная выше структура приводит к неверным расстояниям, поскольку она заставляет маршруты посещать по крайней мере один транзитный узел.

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

Конкретные примеры

Маршрутизация транзитного узла — это не алгоритм, а просто фреймворк для ускорения планирования маршрута. Общий фреймворк оставляет открытыми несколько вопросов, на которые нужно ответить для его реализации:

• Как выбираются транзитные узлы?
• Как выбираются узлы доступа?
• Какой фильтр по местоположению следует использовать?
• Как следует обрабатывать локальные запросы?

Следующие примеры реализации этой структуры отвечают на эти вопросы, используя различные базовые методы, такие как группировка узлов в ячейки сетки наложения ^[2] и более сложную реализацию, основанную на иерархиях сжатия . ^[3]

Геометрический подход с использованием сеток

При сеточном подходе ограничивающий квадрат всех узлов равномерно подразделяется на квадратные ячейки.

Как выбираются узлы доступа?

Узлы доступа (красные точки) для ячейки C (красная) с внутренней областью I (оранжевая) и внешней областью O (синяя)

Для каждой ячейки набор узлов доступа можно найти, посмотрев на внутреннюю область 5x5 ячеек и внешнюю область 9x9 ячеек вокруг . Сосредоточившись на узлах пересечения (концах ребер, пересекающих границу , или ), узлы доступа для являются теми узлами , которые являются частью кратчайшего пути от некоторого узла в к узлу в . В качестве узлов доступа для произвольного узла выбираются все узлы доступа из (красные точки на изображении справа). ${\displaystyle C}$ ${\displaystyle I}$ ${\displaystyle O}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle I}$ ${\displaystyle O}$ ${\displaystyle C}$ ${\displaystyle I}$ ${\displaystyle C}$ ${\displaystyle O}$ ${\displaystyle v\in C}$ ${\displaystyle C}$

Как выбираются транзитные узлы?

Набор транзитных узлов представляет собой в точности объединение всех наборов узлов доступа.

Какой фильтр по местоположению следует использовать?

Способ выбора узлов доступа подразумевает, что если источник и цель находятся на расстоянии более четырех ячеек сетки друг от друга, транзитный узел должен быть пройден по кратчайшему пути, и расстояние может быть рассчитано, как описано выше. Если они находятся ближе друг к другу, для получения расстояния используется резервный алгоритм.

Как следует обрабатывать локальные запросы?

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

Требования к пространству

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

В реализации на основе сетки, описанной выше, это приводит к 16 байтам памяти, которые требуются для каждого узла дорожного графа. Полный граф дорожной сети США имеет 23 947 347 узлов. ^[5] Таким образом, для хранения таблиц расстояний потребуется около 383 МБ памяти.

Использование иерархий сокращения

Как выбираются транзитные узлы?

По определению, иерархия сжатия перемещает важные узлы (т. е. узлы, которые являются частью многих кратчайших путей) на вершину иерархии. Таким образом, набор транзитных узлов может быть выбран в качестве самых высоких узлов иерархии сжатия. ${\displaystyle k}$

Как выбираются узлы доступа?

Узлы прямого доступа узла могут быть найдены путем запуска восходящего поиска иерархии сжатия, начинающейся с . Во время восходящего поиска ребра, покидающие ранее найденные транзитные узлы, не ослабляются. Когда в поиске больше не остается восходящих узлов для урегулирования, те транзитные узлы, которые были урегулированы, являются узлами доступа . Узлы обратного доступа могут быть найдены аналогично. ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$

Какой фильтр по местоположению следует использовать?

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

Как следует обрабатывать локальные запросы?

Локальные запросы используют обычный алгоритм запросов иерархии сжатия.

Смотрите также

• Задача о кратчайшем пути
• Метки концентраторов
• Двунаправленный поиск
• Размеры шоссе

Ссылки

1. Bast, H.; Funke, S.; Sanders, P.; Schultes, D. (2007-04-27). "Быстрая маршрутизация в дорожных сетях с транзитными узлами". Science . 316 (5824): 566. Bibcode :2007Sci...316..566B. doi :10.1126/science.1137521. ISSN  0036-8075. PMID  17463281. S2CID  16559205.
2. Баст, Хольгер; Функе, Стефан; Матиевич, Домагой; Сандерс, Питер; Шультес, Доминик (2007-01-06), "В переходе к запросам на кратчайший путь за постоянное время в дорожных сетях", Труды Девятого семинара по разработке алгоритмов и экспериментам (ALENEX) 2007 г. , Общество промышленной и прикладной математики, стр. 46–59, doi : 10.1137/1.9781611972870.5 , ISBN 9781611972870
3. Arz, Julian; Luxen, Dennis; Sanders, Peter (2013), «Пересмотр маршрутизации транзитных узлов», Experimental Algorithms , Springer Berlin Heidelberg, стр. 55–66, arXiv : 1302.5611 , Bibcode : 2013arXiv1302.5611A, doi : 10.1007/978-3-642-38527-8_7, ISBN 9783642385261, S2CID  14371800
4. Шультес, Доминик; Сандерс, Питер (2007), «Динамическая маршрутизация магистралей и узлов», Экспериментальные алгоритмы , Конспект лекций по информатике, т. 4525, Springer Berlin Heidelberg, стр. 66–79, doi :10.1007/978-3-540-72845-0_6, ISBN 9783540728443
5. "9-я задача по внедрению DIMACS: кратчайшие пути". users.diag.uniroma1.it . Получено 15 июля 2019 г.