Динамическое программирование и декомпозиция в задачах маршрутизации с ограничениями

Рассматриваются задачи последовательного обхода мегаполисов (непустых конечных множеств) при ограничениях в виде условий предшествования и функциях стоимости, допускающих зависимость от списка заданий. Исследуется постановка с аддитивным агрегированием затрат и постановка, ориентированная на использование минимаксного критерия (задача на узкие места). Предполагается, что все множество заданий разбито в сумму двух подмножеств (кластеров). Задания из первого кластера должны быть выполнены раньше, чем начнется выполнение заданий из второго кластера. На этой основе возникает естественная декомпозиция совокупной задачи с выделением предваряющей и финальной задач. Возможные применения могут быть связаны с задачей последовательного демонтажа радиационно опасных объектов, задачей управления инструментом при фигурной листовой резке деталей на машинах с ЧПУ, транспортными задачами (в частности, имеются в виду вопросы логистики в малой авиации, связанные с ограничением на дальность беспосадочного перелета).Предложен и обоснован подход к решению проблемы построения оптимального композиционного решения, построен алгоритм, реализованный на ПЭВМ и позволяющий решать задачи ощутимой размерности за приемлемое время; проведен вычислительный эксперимент.