Двухфазный алгоритм маршрутизации в нестационарных сетях

Рассмотрена задача Time-Dependent Shortest-Path (TDSP), которая является расширением известной задачи о кратчайшем пути в ориентированном графе, когда вес каждой дуги $(x,y)$ этого графа – функция от времени отправления из вершины $x$. Предложено задачу TDSP решать с помощью двухфазного алгоритма ALT, который осуществляет целенаправленный поиск по ориентирам от стартовой вершины $s$ до целевой вершины $d$. На первой фазе выполняется расстановка ориентиров в узлах сети и вычисляются потенциальные функции, на второй фазе находится точное значение $(s, d)$-пути с учётом вычисленных потенциальных функций. Предложены формулы вычисления потенциальных функций и способ задания неравенства треугольника, обеспечивающие корректность алгоритма ALT, и полиномиальная по времени адаптивная эвристика для расстановки ориентиров, которая использует историю обработки запросов при многократном решении задачи TDSP.