Resumo

Рассматривается экстремальная задача маршрутизации перемещений с аддитивным критерием, терминальная компонента которого зависит от точки старта. Данная зависимость может, в частности, быть связана с требованием возврата в район точки старта после выполнения конечной системы заданий, которые требуется упорядочить. В работе предполагается, что задания, подлежащие выполнению, связаны с посещением непустых конечных множеств - мегаполисов. С упомянутыми посещениями связано, в свою очередь, выполнение работ, стоимость которых участвует в формировании критерия. Наконец, стоимость внешних перемещений (между мегаполисами) дополняет формирование аддитивного критерия, подлежащего минимизации. Требуется найти глобальный экстремум и решение, включающее точку старта, очередность посещения мегаполисов и конкретную траекторию процесса. Для решения используется широко понимаемое динамическое программирование (ДП). Существенно то, что процедуры на основе ДП «привязаны» к точке старта. Поэтому требуется перебор упомянутых точек. В статье предлагается подход к решению проблемы сокращения данного перебора за счет применения вспомогательных вариантов ДП, которые универсальны по отношению к выбору точки старта. Построен и реализован на ПЭВМ оптимальный алгоритм с использованием упомянутого подхода.
Título traduzido da contribuiçãoTO THE QUESTION OF OPTIMIZATION OF THE STARTING POINT IN THE ROUTING PROBLEM WITH RESTRICTIONS
Idioma originalRussian
Páginas (de-até)135-154
Número de páginas20
RevistaИзвестия Института математики и информатики Удмуртского государственного университета
Volume55
DOIs
Estado da publicaçãoPublished - 2020

ASJC Scopus subject areas

  • Mathematics(all)
  • Computational Theory and Mathematics

WoS ResearchAreas Categories

  • Mathematics

GRNTI

  • 27.00.00 MATHEMATICS

Level of Research Output

  • VAK List

Impressão digital Mergulhe nos tópicos de investigação de “К ВОПРОСУ ОБ ОПТИМИЗАЦИИ ТОЧКИ СТАРТА В ЗАДАЧЕ МАРШРУТИЗАЦИИ С ОГРАНИЧЕНИЯМИ“. Em conjunto formam uma impressão digital única.

Citar isto