Сетевое планирование: стохастические задачи о кратчайшем пути на графах (SSP)

Математическая архитектура SSP радикально переосмысливает понятие «кратчайший». Если время в пути — это функция распределения вероятностей, то аналитик должен четко определить целевую функцию для лица, принимающего решение (ЛПР). Простая минимизация ожидаемого времени в пути (Expected Travel Time) сводится к классическому алгоритму Дейкстры, запущенному на средних весах, и игнорирует риски. Более сложной и реалистичной целью является максимизация вероятности прибытия вовремя (Maximizing On-Time Arrival Probability). То есть, курьер должен выбрать маршрут, на котором вероятность доехать до пункта назначения строго менее чем за 45 минут (дедлайн) является абсолютным максимумом среди всех возможных путей в графе.

Для решения задачи максимизации вероятности прибытия вовремя алгоритм Беллмана-Форда подвергается сложнейшей функциональной модификации (Stochastic Dynamic Programming). Вместо того чтобы передавать по графу одно скалярное число (расстояние), каждая вершина графа накапливает и передает функцию распределения вероятностей (PDF). Операция сложения длин двух последовательных ребер заменяется операцией математической свертки (Convolution) двух функций плотности вероятности. Поскольку свертка непрерывных распределений является интегральной операцией, точное аналитическое решение возможно лишь в редких случаях (например, когда все ребра графа имеют нормальное распределение). На практике распределения дискретизируются, превращая алгоритм в гигантский матричный калькулятор.

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

Особую вычислительную трудность представляют задачи маршрутизации на сетях с пространственно-временной корреляцией (когда пробка на улице А с высокой вероятностью означает пробку на соседней улице Б). Игнорирование матриц ковариации приводит к ложному занижению дисперсии времени в пути (иллюзия надежности). Интеграция методов Монте-Карло с генетическими алгоритмами позволяет современным логистическим системам рассчитывать надежные маршруты, выстраивая оптимальные буферы времени для курьеров и гарантируя, что 95 процентов пицц будут доставлены горячими, несмотря на стохастический хаос уличного трафика.