|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Робототехника, автоматизация и системы управления
Метод определения надежного кратчайшего пути в стохастической сети с использованием параметрически заданных устойчивых распределений вероятностей
А. А. Агафоновa, В. В. Мясниковab a Самарский национальный исследовательский университет имени академика С.П. Королёва (Самарский университет)
b Институт систем обработки изображений РАН – филиал
ФНИЦ «Кристаллография и фотоника» РАН
Аннотация:
Тенденция к увеличению количества транспортных средств, особенно в крупных городах, а также неспособность существующей дорожно-транспортной инфраструктуры распределять транспортные потоки, ведут к чрезмерной загрузке транспортных сетей и образованию дорожных заторов. Нерешенность данных проблем подчеркивает актуальность навигационных задач нахождения кратчайшего пути или оптимального маршрута движения. Несмотря на популярность этих задач, многие существующие коммерческие системы строят маршрут движения в детерминированных сетях, не учитывая зависящие от времени и стохастические свойства транспортных потоков. В работе рассматривается задача нахождения надежного маршрута движения в стохастической транспортной сети, максимизирующего вероятность прибытия в пункт назначения в течение заданного интервала времени. Надежный кратчайший путь учитывает дисперсию времени прохождения сегментов дорожной сети, что делает его более применимым для решения задач маршрутизации в транспортных сетях по сравнению со стандартными алгоритмами поиска кратчайшего пути, учитывающими только среднее время прохождения дорожных сегментов. Для описания времени прохождения сегментов дорожной сети предлагается использовать параметрически заданные устойчивые распределения вероятностей Леви. Использование устойчивых распределений позволяет перейти от операции вычисления свертки для определения надежности пути к пересчету параметров плотности распределения, что значительно сокращает время исполнения алгоритма. В работе решается задача нахождения адаптивного маршрута движения. Адаптивность подразумевает зависимость выбора следующего используемого дорожного сегмента от времени прибытия в вершину графа и определяется реальным состоянием дорожной сети. Экспериментальный анализ алгоритма, проведенный на крупномасштабной транспортной сети города Самара, показал, что представленный алгоритм позволяет значительно сократить время решения задачи нахождения надежного маршрута движения при незначительном увеличении времени проезда.
Ключевые слова:
надежный кратчайший путь, стохастическая транспортная сеть, устойчивые распределения, распределение Леви.
Поступила в редакцию: 18.03.2019
Образец цитирования:
А. А. Агафонов, В. В. Мясников, “Метод определения надежного кратчайшего пути в стохастической сети с использованием параметрически заданных устойчивых распределений вероятностей”, Тр. СПИИРАН, 18:3 (2019), 558–582
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/trspy1056 https://www.mathnet.ru/rus/trspy/v18/i3/p558
|
Статистика просмотров: |
Страница аннотации: | 200 | PDF полного текста: | 301 |
|