Алгоритм оптимального движения в транспортной сети

Модель транспортной сети Транспортная сеть (рис. 4) представляется топологической моделью в виде взвешенного графа G. Ребра графа соответствуют однородным сегментам транспортной сети, а узлы — точкам ветвления или иным точкам интереса (стартовым точкам, конечным точкам, точкам сети, ближайшим к заданному объекту и т. д.). Каждому ребру графа поставлено в соответствие значение временных затрат на преодоление сегмента. Сегментные затраты определяются геометрической длиной сегмента и средней скоростью движения объекта вдоль сегмента.

Постановка задачи по прокладке маршрута в транспортной сети не отличается от задачи маршрутизации по пересеченной местности.

Описание алгоритма Обозначим через S множество стартовых точек и через E множество конечных точек. Для каждого узла сети введем понятие накопленных затрат. Накопленные затраты определяются минимальными суммарными затратами на перемещение из ближайшей стартовой точки в данную точку.

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