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

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

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



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






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


Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 2014, выпуск 2, страницы 56–75 (Mi vuu427)  

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

МАТЕМАТИКА

Локальные вставки на основе динамического программирования в задаче маршрутизации с ограничениями

А. А. Петунинa, А. Г. Ченцовb, П. А. Ченцовb

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

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

Ключевые слова: маршрутная задача, условия предшествования.

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

Тип публикации: Статья
УДК: 519.6
MSC: 93CXX, 93С15
Поступила в редакцию: 01.03.2014

Образец цитирования: А. А. Петунин, А. Г. Ченцов, П. А. Ченцов, “Локальные вставки на основе динамического программирования в задаче маршрутизации с ограничениями”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 2014, № 2, 56–75

Цитирование в формате AMSBIB
\RBibitem{PetCheChe14}
\by А.~А.~Петунин, А.~Г.~Ченцов, П.~А.~Ченцов
\paper Локальные вставки на основе динамического программирования в задаче маршрутизации с ограничениями
\jour Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки
\yr 2014
\issue 2
\pages 56--75
\mathnet{http://mi.mathnet.ru/vuu427}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/vuu427
  • http://mi.mathnet.ru/rus/vuu/y2014/i2/p56

    ОТПРАВИТЬ: 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. А. Г. Ченцов, “Беллмановские вставки в задаче маршрутизации с ограничениями и усложненными функциями стоимости”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 2014, № 4, 122–141  mathnet
    2. А. Г. Ченцов, “Оптимизирующие вставки в задачах маршрутизации и их реализация на основе динамического программирования”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 26:4 (2016), 565–578  mathnet  crossref  mathscinet  elib
    3. А. А. Петунин, А. А. Ченцов, А. Г. Ченцов, П. А. Ченцов, “Элементы динамического программирования в конструкциях локального улучшения эвристических решений задач маршрутизации с ограничениями”, Автомат. и телемех., 2017, № 4, 106–125  mathnet  elib; A. A. Petunin, A. A. Chentsov, A. G. Chentsov, P. A. Chentsov, “Elements of dynamic programming in local improvement constructions for heuristic solutions of routing problems with constraints”, Autom. Remote Control, 78:4 (2017), 666–681  crossref  isi
    4. А. Г. Ченцов, А. М. Григорьев, “Оптимизирующие мультивставки в задачах маршрутизации с ограничениями”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 28:4 (2018), 513–530  mathnet  crossref  elib
  • Вестник Удмуртского университета. Математика. Механика. Компьютерные науки
    Просмотров:
    Эта страница:211
    Полный текст:63
    Литература:17

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019