О структуре одной экстремальной задачи маршрутизации с ограничениями в виде условий предшествования

Рассматривается задача последовательного обхода сечений многозначных отображений, осложненная ограничениями. Последние связаны с реализацией конечного набора адресных перемещений для заданных пар «отправитель – получатель» (по ходу этих перемещений могут посещаться сечения других многозначных отображений). В качестве решения рассматривается пара маршрут – трасса; маршрут определяется в виде перестановки индексов многозначных отображений и имеет смысл дискретной компоненты (полного) решения, а трасса («непрерывная» компонента) понимается как кортеж точек в сечениях многозначных отображений, индексированных в соответствии с маршрутом. Последний должен удовлетворять вышеупомянутым условиям адресных перемещений. Перемещения же между множествами характеризуются затратами, которые аггрегируются посредством суммирования, порождая аддитивный критерий, который и должен минимизироваться в классе всех допустимых пар маршрут – трасса. В работе построена модификация метода динамического программирования (МДП) на основе эквивалентного преобразования исходной задачи к задаче с ограничениями на реализацию (текущих) переходов с множества на очередное (следующее по списку) множество. Для частного случая «метрической» задачи на плоскости проведены расчеты на основе алгоритма с использованием МДП.