Маршрутизация транзитного узла - Transit node routing

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

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

Интуиция

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

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

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

Общие рамки

1. Маршрутизация транзитных узлов начинается с выбора транзитных узлов. ${ Displaystyle T substeq V}$ как подмножество всех узлов ${ displaystyle V}$ дорожной сети.
2. Для каждого узла ${ displaystyle v in V}$ выделенные наборы узлов прямого доступа ${ Displaystyle { overrightarrow {A}} (v) substeq T}$ и узлы обратного доступа ${ Displaystyle { overleftarrow {A}} (v) substeq 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 (синий)

Для каждой ячейки ${ displaystyle C}$, набор узлов доступа можно найти, посмотрев на внутреннюю область ${ displaystyle I}$ 5х5 ячеек и внешняя площадка ${ displaystyle O}$ 9x9 ячеек вокруг ${ 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}$. Аналогично можно найти узлы обратного доступа.

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

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

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

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

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

• Задача кратчайшего пути
• Ярлыки концентраторов
• Двунаправленный поиск

Рекомендации