Маршрутизация в дорожных сетях с транзитными узлами: различия между версиями

Пусть дан ориентированный граф G = (V, E) с неотрицательными весами ребер. Необходимо вычислить кратчайший путь по графу G из вершины-источника s в целевую вершину t для заданных s и t. Предполагая, что граф G остается неизменными и что будет много запросов с указанием источника и цели, имеет смысл потратить некоторое время на этап предварительной обработки, который позволит очень быстро отвечать на запросы. На выходе, в зависимости от приложения, ожидается либо полное описание кратчайшего пути, либо только его длина d(s, t).

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

Эксперименты проводились на дорожных сетях Западной Европы и США с использованием целевой функции, учитывающей только ожидаемое время в пути. Результаты отражают различные компромиссы между средним временем выполнения запроса (от 5 до 63 микросекунд для США), продолжительностью предварительной обработки (от 59 до 1200 минут) и затратами на хранение (от 21 до 244 байт на узел). Для варианта, использующего три уровня и настроенного для минимального времени выполнения запроса, в таблицах 1 и 2 показана статистика для продолжительности предварительной обработки и эффективности запросов, соответственно. Среднее время выполнения запроса, около 5 микросекунд, на шесть порядков величины меньше, чем у алгоритма Дейкстры. На рис. 2 для каждого ранга r на оси x приведено распределение для 1000 запросов со случайной исходной точкой s и целевым узлом t, для нахождения ответа на которые алгоритму Дейкстры требуется r итераций. Можно различить три уровня маршрутизации при помощи транзитных узлов с небольшими транзитными зонами между ними: для больших рангов достаточно обращения только к первичному уровню, что дает время выполнения запроса около 5 микросекунд, для меньших рангов требуются дополнительные уровни и медианное время выполнения запроса возрастает до 20 микросекунд.

! colspan="2" | Слой 1

! colspan="3" | Слой 2

! colspan="2" | Слой 3

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

! слой 1

! слой 2

! слой 3

Таблица 2. Эффективность алгоритма маршрутизации при помощи транзитных узлов на 10 000 000 случайных запросов. Столбец для уровня i показывает, на какую часть запросов был дан точный ответ с использованием только информации, доступной на уровнях < i. Каждый «ящик» простирается от нижнего до верхнего квартиля и содержит медианное значение, «усы» простираются до минимального и максимального значений, исключая выбросы, изображенные отдельно

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