ОПТИМИЗИРУЮЩИЕ МУЛЬТИВСТАВКИ В ЗАДАЧАХ МАРШРУТИЗАЦИИ С ОГРАНИЧЕНИЯМИ

Александр Георгиевич Ченцов, Алексей Михайлович Григорьев

Результат исследований: Вклад в журналСтатья

2 Цитирования (Scopus)

Аннотация

Рассматривается задача последовательного обхода мегаполисов (непустых конечных множеств) с условиями предшествования и функциями стоимости, зависящими от списка заданий. Постановка ориентирована на инженерные задачи, возникающие в атомной энергетике и связанные со снижением облучаемости работников, а также в машиностроении (маршрутизация движения инструмента при листовой резке на машинах с ЧПУ). Предполагается, что исследуемая задача дискретной оптимизации имеет ощутимую размерность, что вынуждает к использованию эвристик. Обсуждается процедура локального улучшения качества последних посредством применения оптимизирующих мультивставок, определяемых всякий раз в виде конечного дизъюнктного набора вставок. Предполагается, что в каждой вставке используется процедура оптимизации на основе широко понимаемого динамического программирования. Показано, что в «аддитивной» маршрутной задаче вышеупомянутого типа (с ограничениями и усложненными функциями стоимости) улучшения достигаемого результата также агрегируются аддитивно. Предлагаемая конструкция допускает реализацию в виде параллельной процедуры с использованием МВС; при этом отдельные вставки выделяются вычислительным узлам и формируются независимо.
Переведенное названиеOptimizing multi-inserts in routing problems with constraints
Язык оригиналаРусский
Страницы (с-по)513-530
ЖурналВестник Удмуртского университета. Математика. Механика. Компьютерные науки
DOI
СостояниеОпубликовано - 2018

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

  • Computer Science(all)
  • Mathematics(all)
  • Fluid Flow and Transfer Processes

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

  • Математика

ГРНТИ

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

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

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

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

Цитировать