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

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

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

Интуиция

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

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

Общие рамки

Маршрутизация транзитных узлов начинается с выбора транзитных узлов. $T\subseteq V$ как подмножество всех узлов $V$ дорожной сети.
Для каждого узла $v\in V$ выделенные наборы узлов прямого доступа ${\overrightarrow {A}}(v)\subseteq T$ и узлы обратного доступа ${\overleftarrow {A}}(v)\subseteq T$ выбираются из всех транзитных узлов.
Теперь попарные расстояния между транзитными узлами $D_{T}$ и расстояния между узлами $v$ и соответствующие им узлы доступа $d_{A}$ рассчитываются и сохраняются.
Расстояние между двумя узлами теперь можно рассчитать как $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$ ячеек 5x5 и внешней области $O$ ячеек 9x9 вокруг $C$ . Сосредоточение внимания на пересекающихся узлах (концах ребер, пересекающих границу $C$ , $I$ или $O$ ), узлы доступа для $C$ это те узлы $I$ которые являются частью кратчайшего пути от некоторого узла в $C$ к узлу в $O$ . В качестве узлов доступа для произвольного узла $v\in C$ все узлы доступа $C$ выбраны (красные точки на изображении справа).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

^ Перейти обратно: ^а ^б Баст, Х.; Функе, С.; Сандерс, П.; Шультес, Д. (27 апреля 2007 г.). «Быстрая маршрутизация в дорожных сетях с транзитными узлами». Наука . 316 (5824): 566. Бибкод : 2007Sci...316..566B . дои : 10.1126/science.1137521 . ISSN 0036-8075 . ПМИД 17463281 . S2CID 16559205 .
^ Перейти обратно: ^а ^б Баст, Хольгер; Функе, Стефан; Матиевич, Домагой; Сандерс, Питер; Шультес, Доминик (06 января 2007 г.), «На пути к запросам кратчайшего пути в постоянном времени в дорожных сетях», 2007 г., Материалы девятого семинара по разработке алгоритмов и экспериментам (ALENEX) , Общество промышленной и прикладной математики, стр. 46–59, номер домена : 10.1137/1.9781611972870.5 , ISBN. 9781611972870
^ Перейти обратно: ^а ^б Арз, Джулиан; Люксен, Деннис; Сандерс, Питер (2013), «Пересмотр маршрутизации транзитных узлов», Экспериментальные алгоритмы , Springer Berlin Heidelberg, стр. 55–66, arXiv : 1302.5611 , Bibcode : 2013arXiv1302.5611A , doi : 10.1007/978-3-642-38527-8_ 7 , ISBN 9783642385261 , S2CID 14371800
^ Шультес, Доминик; Сандерс, Питер (2007), «Динамическая маршрутизация узлов шоссе», Экспериментальные алгоритмы , Конспекты лекций по информатике, том. 4525, Springer Berlin Heidelberg, стр. 66–79, doi : 10.1007/978-3-540-72845-0_6 , ISBN 9783540728443
^ «Девятая задача по внедрению DIMACS: кратчайшие пути» . users.diag.uniroma1.it . Проверено 15 июля 2019 г.

[:0-1] Перейти обратно: ^а ^б Баст, Х.; Функе, С.; Сандерс, П.; Шультес, Д. (27 апреля 2007 г.). «Быстрая маршрутизация в дорожных сетях с транзитными узлами». Наука . 316 (5824): 566. Бибкод : 2007Sci...316..566B . дои : 10.1126/science.1137521 . ISSN 0036-8075 . ПМИД 17463281 . S2CID 16559205 .

[:1-2] Перейти обратно: ^а ^б Баст, Хольгер; Функе, Стефан; Матиевич, Домагой; Сандерс, Питер; Шультес, Доминик (06 января 2007 г.), «На пути к запросам кратчайшего пути в постоянном времени в дорожных сетях», 2007 г., Материалы девятого семинара по разработке алгоритмов и экспериментам (ALENEX) , Общество промышленной и прикладной математики, стр. 46–59, номер домена : 10.1137/1.9781611972870.5 , ISBN. 9781611972870

[:2-3] Перейти обратно: ^а ^б Арз, Джулиан; Люксен, Деннис; Сандерс, Питер (2013), «Пересмотр маршрутизации транзитных узлов», Экспериментальные алгоритмы , 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] «Девятая задача по внедрению DIMACS: кратчайшие пути» . users.diag.uniroma1.it . Проверено 15 июля 2019 г.

[1]

[2]

[3]

[4]

[5]