A Model of 'Nonadditive' Routing Problem where the Costs Depend on the Set of Pending Tasks

Аннотация

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