Построение оптимального маршрута

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

Эффективный подход к решению этой задачи вытекает из теории графов. Модель дорожной сети для решения задач поиска "оптимальных" путей принято представлять в виде графа (graph) в котором:

• узлы - это пересечение двух или более дорожных сегментов
• ребра(arcs, edges) - направленная дуга в графе
• в простейшей модели каждому ребру назначается вес, как время необходимое для проезда по дуге

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

1. Алгоритм Дейкстры (Dijkstra's algorithm)

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

2. Алгоритм A*

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

3. Алгоритм A* with Landmarks (ALT)

Является усовершенствованным алгоритмом A*, использует набор узлов в качестве ориентиров для вычисления эвристики. Позволяет ускорить A* в 2 раза, но требует много дополнительного пространства для предвычисленных расстояний.

4. Arc flags (помеченные ребра)

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

5. Highway & Contraction Hierarchies

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

6. TNR (Transit Node Routing)

Построен на вычислении наборов Transit Nodes и Access Nodes.

• TN - узлы, через которые проходит большинство кратчайших путей
• AN - узлы доступа в транспортную сеть

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

• учет стоимости маневров (левый, правый повороты и т.п.)
• учет дорожных событий
• учет запрещенных маневров для разных видов транспортных средств