Исследование ускорения метода определения надёжного кратчайшего пути в зависящей от времени стохастической транспортной сети

Abstract

Целью работы является модификация и исследование алгоритма нахождения надежного кратчайшего пути в зависящей от времени стохастической транспортной сети. Под надёжностью понимается максимизация вероятности прибытия в пункт назначения в заданный заранее интервал времени. Модификация базового алгоритма нахождения надежного кратчайшего пути проводится с целью повышения скорости работы алгоритма и заключается в выборе определенного подмножества вершин и ребер графа, которые доступны для построения кратчайшего пути. Предложены два метода выбора подмножества вершин и ребер графа: на основе ограничивающего прямоугольника и на основе алгоритма k кратчайших путей. Проведены экспериментальные исследования эффективности базового и модифицированного алгоритмов на примере транспортной сети города Самары.