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

Ключевые слова и синонимы

Поиск кратчайших путей

Постановка задачи

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

Классический алгоритм Дейкстры для решения этой задачи [ ] итеративно посещает все вершины по порядку расстояния от источника до тех пор, пока не будет достигнута целевая вершина. При обработке очень больших графов алгоритм начинает работать слишком медленно для многих приложений, из-за чего возникает необходимость в применении более специфичных техник, использующих особые свойства конкретного графа. Крайне важным на практике случаем является маршрутизация в дорожных сетях, в которых слияния и пересечения дорог трактуются как узлы, а участки дорог – как ребра, вес которых определяется некоторой весовой функцией, например, от ожидаемого времени в пути, расстояни и потребления топлива. Дорожные сети обычно являются разреженными (т. е. |E| = O(|V|)), почти планарными (т. е. в них очень небольшое число переездов) и иерархическими (т. е. можно выделить более или менее «важные» дороги). Обзор различных технологий ускорения для этой конкретной задачи приведен в работе [7].

Основные результаты

Маршрутизация при помощи транзитных узлов [2, 3] основывается на простом наблюдении, интуитивно используемом людьми: Если вы начинаете движение из исходного узла s и движетесь куда-то «далеко», вы покинете свое текущее местоположение через одну из нескольких «важных» точек пересечений дорог, называемых (прямыми) узлами доступа [math]\displaystyle{ \overrightarrow{A}(s) }[/math]. Аналогичное рассуждение применяется и к целевому узлу, в который можно попасть только из одного из нескольких обратных узлов доступа [math]\displaystyle{ \overleftarrow{A}(t) }[/math]. Более того, объединение всех прямых и обратных узлов доступа всех узлов, называемое множеством транзитных вершин [math]\displaystyle{ \mathcal{T} }[/math], весьма невелико. Из этого следуют два наблюдения, заключающиеся в том, что для каждого узла можно хранить расстояния до и из его прямых и обратных узлов доступа, а для каждой пары транзитных узлов (u, v) – расстояние между u и v. Для заданных исходного и целевого узлов s и t длина кратчайшего путь, проходящего как минимум через один транзитный узел, задается соотношением [math]\displaystyle{ d_{\mathcal{T}} (s, t) = min \{ d(s, u) + d(u, v) + d(v, t) | u \in \overrightarrow{A}(s), v \in \overleftarrow{A}(t) \} }[/math].

Заметим, что все входящие в него расстояния d(s, u), d(u, v) и d(v, t) могут быть непосредственно получены из предварительно вычисленных структур данных. Наконец, необходим также фильтр локальности [math]\displaystyle{ L: V \times V \to \{ true, false \} }[/math], определяющий, не находятся ли узлы s и t слишком близко друг к другу для того, чтобы перемещаться между ними через транзитный узел. Значение [math]\displaystyle{ L }[/math] должно удовлетворять свойству, заключающемуся в том, что из [math]\displaystyle{ \lnot{L}(s, t) }[/math] следует [math]\displaystyle{ d(s, t) = d_{\mathcal{T}}(s, t) }[/math]. Заметим, что в общем случае обратное не обязательно должно быть справедливо, поскольку это может стать препятствием для эффективной реализации фильтра локальности. Таким образом, могут встречаться ложноположительные значения, т. е. "[math]\displaystyle{ L(s, t) \and d(s, t) = d_{\mathcal{T}} (s, t) }[/math]".

Следующий алгоритм может использоваться для вычисления d(s, t):

  Если [math]\displaystyle{ \lnot{L}(s, t) }[/math], то вычислить и вернуть [math]\displaystyle{ d_{\mathcal{T}} (s, t) }[/math];
  в противном случае использовать любой другой алгоритм маршрутизации.

Рисунок 1. Поиск оптимального времени поездки между двумя точками (отмеченными флажками) где-то между Саарбрюккеном и Карлсруэ сводится к получению 2x4 узлов доступа (отмеченных ромбами), выполнению 16 поисков по таблице между всеми парами узлов доступа и проверке, не перекрываются ли два диска, определяющие фильтр локальности. Транзитные узлы, не принадлежащие к множествам узлов доступа выбранных исходного и целевого узлов, изображены в виде маленьких квадратиков. Уровни иерархии дорог обозначены цветом: серым, красным, синим и зеленым для уровней 0-1, 2, 3 и 4, соответственно

Пример приведен на рис. 1. Зная длину кратчайшего пути, можно эффективно вывести его полное описание при помощи итеративных поисков по таблице и заранее вычисленных представлений путей между транзитными вершинами. При условии, что вышеупомянутые наблюдения справедливы, а процент ложноположительных срабатываний мал, данный алгоритм работает очень эффективно, поскольку значительная часть всех запросов может быть обработана в строке 1, [math]\displaystyle{ d_{\mathcal{T}} (s, t) }[/math] может быть вычислено при помощи нескольких поисков в таблице, а источник и цельоставшихся запросов в строке 2 оказываются достаточно близки. И в самом деле, поиск ответов на оставшиеся запросы может быть ускорен за счет введения вторичного уровня маршрутизации транзитных узлов, основанного на множестве вторичных транзитных узлов [math]\displaystyle{ {\mathcal{T}}_2 \supset {\mathcal{T}} }[/math]. В данном случае нет необходимости в вычислении и хранении полной таблицы расстояний [math]\displaystyle{ {\mathcal{T}}_2 \times {\mathcal{T}}_2 }[/math], достаточно хранить только расстояния [math]\displaystyle{ \{d(u, v) | u, v \in {\mathcal{T}}_2 \and d(u, v) \ne d_{{\mathcal{T}}}(s, t) \} }[/math], т. е. расстояния, которые не могут быть получены при помощи первичного уровня. Аналогичным образом можно добавить и более глубокие уровни.

Существуют две разных реализации: одна из них основана на простой геометрической решетке, а другая – на иерархии дорог, самом быстром из предыдущих подходов [5, 6]. Иерархия дорог состоит из последовательности уровней (рис. 1), где уровень i + 1 строится из уровня i путем обхода узлов низкой степени и удаления ребер, которые никогда не встречаются вдали от источника или цели кратчайшего пути. Любопытно, что эти уровни постепенно становятся геометрическим меньшими по размеру, во всех прочих отношениях они похожи друг на друга. Наивысший уровень содержит самые «важные» узлы и становится множеством первичных транзитных узлов. Узлы более низких уровней используются для формирования множеств транзитных узлов подчиненных уровней.

Применение

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