Задача последовательного обхода мегаполисов с условиями предшествования

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

Статья представлена к публикации членом редколлегии: А. И. Кибзун