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