RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 2018, том 28, выпуск 4, страницы 513–530 (Mi vuu654)  

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

МАТЕМАТИКА

Оптимизирующие мультивставки в задачах маршрутизации с ограничениями

А. Г. Ченцовab, А. М. Григорьевa

a Институт математики и механики им. Н.Н. Красовского УрО РАН, 620219, Россия, г. Екатеринбург, ул. С. Ковалевской, 16
b Уральский федеральный университет, 620002, Россия, г. Екатеринбург, ул. Мира, 19

Аннотация: Рассматривается задача последовательного обхода мегаполисов (непустых конечных множеств) с условиями предшествования и функциями стоимости, зависящими от списка заданий. Постановка ориентирована на инженерные задачи, возникающие в атомной энергетике и связанные со снижением облучаемости работников, а также в машиностроении (маршрутизация движения инструмента при листовой резке на машинах с ЧПУ). Предполагается, что исследуемая задача дискретной оптимизации имеет ощутимую размерность, что вынуждает к использованию эвристик. Обсуждается процедура локального улучшения качества последних посредством применения оптимизирующих мультивставок, определяемых всякий раз в виде конечного дизъюнктного набора вставок. Предполагается, что в каждой вставке используется процедура оптимизации на основе широко понимаемого динамического программирования. Показано, что в «аддитивной» маршрутной задаче вышеупомянутого типа (с ограничениями и усложненными функциями стоимости) улучшения достигаемого результата также агрегируются аддитивно. Предлагаемая конструкция допускает реализацию в виде параллельной процедуры с использованием МВС; при этом отдельные вставки выделяются вычислительным узлам и формируются независимо.

Ключевые слова: динамическое программирование, мультивставки, параллельный алгоритм.

Финансовая поддержка Номер гранта
Российский научный фонд 14-11-00109
Работа выполнена при финансовой поддержке РНФ (грант 14-11-00109).


DOI: https://doi.org/10.20537/vm180406

Полный текст: PDF файл (427 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.6
MSC: 49L20, 90C39
Поступила в редакцию: 17.09.2018

Образец цитирования: А. Г. Ченцов, А. М. Григорьев, “Оптимизирующие мультивставки в задачах маршрутизации с ограничениями”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 28:4 (2018), 513–530

Цитирование в формате AMSBIB
\RBibitem{CheGri18}
\by А.~Г.~Ченцов, А.~М.~Григорьев
\paper Оптимизирующие мультивставки в задачах маршрутизации с~ограничениями
\jour Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки
\yr 2018
\vol 28
\issue 4
\pages 513--530
\mathnet{http://mi.mathnet.ru/vuu654}
\crossref{https://doi.org/10.20537/vm180406}
\elib{http://elibrary.ru/item.asp?id=36873367}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/vuu654
  • http://mi.mathnet.ru/rus/vuu/v28/i4/p513

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. А. Г. Ченцов, А. А. Ченцов, “К вопросу о маршрутизации перемещений в задаче с динамическими ограничениями”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 29:3 (2019), 363–381  mathnet  crossref
  • Вестник Удмуртского университета. Математика. Механика. Компьютерные науки
    Просмотров:
    Эта страница:145
    Полный текст:166
    Литература:16
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020