Модель «неаддитивной» задачи маршрутизации с функциями стоимости, зависящими от списка заданий

Рассматривается следующий (усложненный) вариант маршрутной задачи “на узкие места”: исследуется задача последовательного обхода мегаполисов, осложненная условиями предшествования и тем, что функции стоимости (перемещений и внутренних работ) могут явным образом зависеть от списка заданий, которые не выполнены на данный момент. Процесс перемещений рассматривается в виде совокупности этапов, включающих внешнее перемещение к соответствующему мегаполису и последующее выполнение (внутренних по смыслу) работ, связанных с данным мегаполисом. Качество совокупного процесса оценивается максимумом стоимостей составляющих его этапов; рассматривается  задача на минимум упомянутого критерия (получается задача на минимакс, обычно именуемая задачей “на узкие места”). Для построения оптимального решения в виде пары маршрут-трасса (трасса, или траектория, соответствует конкретному варианту прохождения мегаполисов, нумеруемых в соответствии с маршрутом, определяемым в виде перестановки индексов) построен “нестандартный” вариант метода динамического программирования, при реализации которого не используется, в случае ограничений в виде условий предшествования, построение всего массива значений функции Беллмана.