Аннотация

Рассматривается экстремальная задача маршрутизации перемещений с аддитивным критерием, терминальная компонента которого зависит от точки старта. Данная зависимость может, в частности, быть связана с требованием возврата в район точки старта после выполнения конечной системы заданий, которые требуется упорядочить. В работе предполагается, что задания, подлежащие выполнению, связаны с посещением непустых конечных множеств - мегаполисов. С упомянутыми посещениями связано, в свою очередь, выполнение работ, стоимость которых участвует в формировании критерия. Наконец, стоимость внешних перемещений (между мегаполисами) дополняет формирование аддитивного критерия, подлежащего минимизации. Требуется найти глобальный экстремум и решение, включающее точку старта, очередность посещения мегаполисов и конкретную траекторию процесса. Для решения используется широко понимаемое динамическое программирование (ДП). Существенно то, что процедуры на основе ДП «привязаны» к точке старта. Поэтому требуется перебор упомянутых точек. В статье предлагается подход к решению проблемы сокращения данного перебора за счет применения вспомогательных вариантов ДП, которые универсальны по отношению к выбору точки старта. Построен и реализован на ПЭВМ оптимальный алгоритм с использованием упомянутого подхода.
Переведенное названиеTO THE QUESTION OF OPTIMIZATION OF THE STARTING POINT IN THE ROUTING PROBLEM WITH RESTRICTIONS
Язык оригиналаРусский
Страницы (с-по)135-154
Число страниц20
ЖурналИзвестия Института математики и информатики Удмуртского государственного университета
Том55
DOI
СостояниеОпубликовано - 2020

Предметные области ASJC Scopus

  • Mathematics(all)
  • Computational Theory and Mathematics

Предметные области WoS

  • Математика

ГРНТИ

  • 27.00.00 МАТЕМАТИКА

Уровень публикации

  • Перечень ВАК

Fingerprint Подробные сведения о темах исследования «К ВОПРОСУ ОБ ОПТИМИЗАЦИИ ТОЧКИ СТАРТА В ЗАДАЧЕ МАРШРУТИЗАЦИИ С ОГРАНИЧЕНИЯМИ». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать