Research output: Contribution to journal › Article › peer-review
Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - К ВОПРОСУ ОБ ОПТИМИЗАЦИИ ТОЧКИ СТАРТА В ЗАДАЧЕ МАРШРУТИЗАЦИИ С ОГРАНИЧЕНИЯМИ
AU - Ченцов, Александр Георгиевич
AU - Ченцов, Павел Александрович
PY - 2020
Y1 - 2020
N2 - Рассматривается экстремальная задача маршрутизации перемещений с аддитивным критерием, терминальная компонента которого зависит от точки старта. Данная зависимость может, в частности, быть связана с требованием возврата в район точки старта после выполнения конечной системы заданий, которые требуется упорядочить. В работе предполагается, что задания, подлежащие выполнению, связаны с посещением непустых конечных множеств - мегаполисов. С упомянутыми посещениями связано, в свою очередь, выполнение работ, стоимость которых участвует в формировании критерия. Наконец, стоимость внешних перемещений (между мегаполисами) дополняет формирование аддитивного критерия, подлежащего минимизации. Требуется найти глобальный экстремум и решение, включающее точку старта, очередность посещения мегаполисов и конкретную траекторию процесса. Для решения используется широко понимаемое динамическое программирование (ДП). Существенно то, что процедуры на основе ДП «привязаны» к точке старта. Поэтому требуется перебор упомянутых точек. В статье предлагается подход к решению проблемы сокращения данного перебора за счет применения вспомогательных вариантов ДП, которые универсальны по отношению к выбору точки старта. Построен и реализован на ПЭВМ оптимальный алгоритм с использованием упомянутого подхода.
AB - Рассматривается экстремальная задача маршрутизации перемещений с аддитивным критерием, терминальная компонента которого зависит от точки старта. Данная зависимость может, в частности, быть связана с требованием возврата в район точки старта после выполнения конечной системы заданий, которые требуется упорядочить. В работе предполагается, что задания, подлежащие выполнению, связаны с посещением непустых конечных множеств - мегаполисов. С упомянутыми посещениями связано, в свою очередь, выполнение работ, стоимость которых участвует в формировании критерия. Наконец, стоимость внешних перемещений (между мегаполисами) дополняет формирование аддитивного критерия, подлежащего минимизации. Требуется найти глобальный экстремум и решение, включающее точку старта, очередность посещения мегаполисов и конкретную траекторию процесса. Для решения используется широко понимаемое динамическое программирование (ДП). Существенно то, что процедуры на основе ДП «привязаны» к точке старта. Поэтому требуется перебор упомянутых точек. В статье предлагается подход к решению проблемы сокращения данного перебора за счет применения вспомогательных вариантов ДП, которые универсальны по отношению к выбору точки старта. Построен и реализован на ПЭВМ оптимальный алгоритм с использованием упомянутого подхода.
KW - dynamic programming
KW - route
KW - precedence conditions
KW - TRAVELING SALESMAN PROBLEM
UR - https://www.elibrary.ru/item.asp?id=42949305
UR - https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=tsmetrics&SrcApp=tsm_test&DestApp=WOS_CPL&DestLinkType=FullRecord&KeyUT=000547994700009
UR - http://www.scopus.com/inward/record.url?scp=85093889670&partnerID=8YFLogxK
U2 - 10.35634/2226-3594-2020-55-09
DO - 10.35634/2226-3594-2020-55-09
M3 - Статья
VL - 55
SP - 135
EP - 154
JO - Известия Института математики и информатики Удмуртского государственного университета
JF - Известия Института математики и информатики Удмуртского государственного университета
SN - 2226-3594
ER -
ID: 13200321