|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
МАТЕМАТИКА
К вопросу об оптимизации точки старта в задаче маршрутизации с ограничениями
А. Г. Ченцов, П. А. Ченцов Институт математики и механики им. Н. Н. Красовского УрО РАН, 620219, Россия, г. Екатеринбург, ул. С. Ковалевской, 16
Аннотация:
Рассматривается экстремальная задача маршрутизации перемещений с аддитивным критерием, терминальная компонента которого зависит от точки старта.
Данная зависимость может, в частности, быть связана с требованием возврата в район точки старта после выполнения конечной системы заданий, которые требуется упорядочить.
В работе предполагается, что задания, подлежащие выполнению, связаны с посещением непустых конечных множеств — мегаполисов.
С упомянутыми посещениями связано, в свою очередь, выполнение работ, стоимость которых участвует в формировании критерия.
Наконец, стоимость внешних перемещений (между мегаполисами) дополняет формирование аддитивного критерия, подлежащего минимизации.
Требуется найти глобальный экстремум и решение, включающее точку старта, очередность посещения мегаполисов и конкретную траекторию процесса.
Для решения используется широко понимаемое динамическое программирование (ДП).
Существенно то, что процедуры на основе ДП «привязаны» к точке старта.
Поэтому требуется перебор упомянутых точек.
В статье предлагается подход к решению проблемы сокращения данного перебора за счет применения вспомогательных вариантов ДП, которые универсальны по отношению к выбору точки старта.
Построен и реализован на ПЭВМ оптимальный алгоритм с использованием упомянутого подхода.
Ключевые слова:
динамическое программирование, маршрут, условия предшествования.
Поступила в редакцию: 12.01.2020
Образец цитирования:
А. Г. Ченцов, П. А. Ченцов, “К вопросу об оптимизации точки старта в задаче маршрутизации с ограничениями”, Изв. ИМИ УдГУ, 55 (2020), 135–154
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/iimi395 https://www.mathnet.ru/rus/iimi/v55/p135
|
Статистика просмотров: |
Страница аннотации: | 231 | PDF полного текста: | 48 | Список литературы: | 18 |
|