Оптимальная маршрутизация по ориентирам в нестационарных сетях

Рассмотрена задача Time-Dependent Shortest-Path (TDSP), которая является расширением задачи о кратчайшем пути в графе. Сеть представляется ориентированным графом $G=(V,E)$, в котором для каждой дуги $(x,y)\in E$ определены две функции: $w_{xy}(t)$ – время, необходимое для передвижения по дуге $(x,y)$, и $F_{xy}(t)$ – время прибытия в вершину $y$ при условии, что старт из вершины $x$ осуществлён в момент времени $t$. Такую сеть называют нестационарной, а наименьшее время передвижения из стартовой вершины в целевую интерпретируют как оптимальный маршрут или кратчайший путь между этими вершинами. В работе задача TDSP исследована для полиномиально разрешимого случая, когда функции прибытия являются монотонными. Двухфазный алгоритм ALT (A$^*$ with Landmarks & Triangle) – один из современных алгоритмов, способных быстро решать задачу TDSP на графах большой размерности. В работе определено и доказано достаточное условие корректности алгоритма ALT для задачи TDSP: сеть должна отвечать неравенству треугольника, заданного для промежутков времени передвижения по узлам сети. Особенность предложенного неравенства треугольника – его определение через “оптимистичные” веса дуг, когда возможно беспрепятственное движение по дугам. Показано, что это неравенство треугольника верно всегда, если веса дуг заданы отношениями длин дуг к скорости передвижения по ним и справедливо неравенство треугольника для расстояний между узлами сети.