К вопросу об оптимизации точки старта в задаче маршрутизации с ограничениями

Аннотация

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