Алгоритмическое обеспечение оптимальной маршрутизации
В. Г. Стэмпковский
Институт прикладной астрономии РАН, г. Санкт-Петербург, Россия
Аннотация:
Построение маршрута транспортного средства, управляемого автоматически или
с участием оператора, во многих случаях является одним из этапов всего
комплекса работ по координатно-временному и навигационному обеспечению.
Алгоритмы построения маршрута в значительной степени определяются моделью
транспортной системы, но, как правило, трансформируются в алгоритмы поиска
пути на графе. В работе рассмотрен алгоритм поиска пути на ориентированном
графе, учитывающий наличие координат у вершин графа, унаследованных из модели
транспортной системы. При выполнении определенных ограничений
на вид целевой функции предложенный алгоритм эффективнее традиционно используемого алгоритма Э. Дейкстры.
Ключевые слова:
транспортная система, дорожный элемент, координатная информация, целевая функция, оптимальный маршрут, многошаговое прогнозирование, ориентированный граф, дерево путей на графе.
Algorithmic Support of Optimal Routing
V. G. Stempkovsky
Abstract
In this paper the algorithm for finding ways to directed graph, taking into account the availability of the coordinates of the vertices of the graph, inherited from the model of the transport system is proposed. Under certain restrictions on the type of objective function, the proposed algorithm is more efficient than traditionally used algorithm E. Dijkstra.
Keywords:
transport, road element, coordinate information, objective function, optimal route, multi-step prediction, directed graph, tvertices of the graph.