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

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