Об одной нестационарной задаче маршрутизации с ограничениями

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