A model of “nonadditive” routing problem where the costs depend on the set of pending tasks

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