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

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

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



Изв. ИМИ УдГУ:
Год:
Том:
Выпуск:
Страница:
Найти






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


Изв. ИМИ УдГУ, 2019, том 54, страницы 102–121 (Mi iimi385)  

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

The routing problems with optimization of the starting point: dynamic programming

[Маршрутная задача с оптимизацией стартовой точки: динамическое программирование]

A. G. Chentsovab, P. A. Chentsovac

a N. N. Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, ul. S. Kovalevskoi, 16, Yekaterinburg, 620219, Russia
b Institute of Radioelectronics and Information Technologies, Ural Federal University, ul. Mira, 19, Yekaterinburg, 620002, Russia
c Mechanical Engineering Institute, Ural Federal University, ul. Mira, 19, Yekaterinburg, 620002, Russia

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

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

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 17-08-01385_а
Работа выполнена при финансовой поддержке Российского Фонда Фундаментальных Исследований (проект № 17–08–01385).


DOI: https://doi.org/10.20537/2226-3594-2019-54-08

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

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

Тип публикации: Статья
УДК: 519.6
MSC: 93C83
Поступила в редакцию: 30.07.2019
Язык публикации: английский

Образец цитирования: A. G. Chentsov, P. A. Chentsov, “The routing problems with optimization of the starting point: dynamic programming”, Изв. ИМИ УдГУ, 54 (2019), 102–121

Цитирование в формате AMSBIB
\RBibitem{CheChe19}
\by A.~G.~Chentsov, P.~A.~Chentsov
\paper The routing problems with optimization of the starting point: dynamic programming
\jour Изв. ИМИ УдГУ
\yr 2019
\vol 54
\pages 102--121
\mathnet{http://mi.mathnet.ru/iimi385}
\crossref{https://doi.org/10.20537/2226-3594-2019-54-08}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000512131100008}
\elib{https://elibrary.ru/item.asp?id=41435144}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/iimi385
  • http://mi.mathnet.ru/rus/iimi/v54/p102

    ОТПРАВИТЬ: 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. А. Г. Ченцов, А. А. Ченцов, А. Н. Сесекин, “О задаче последовательного обхода мегаполисов с условиями предшествования и функциями стоимости с зависимостью от списка заданий”, Тр. ИММ УрО РАН, 26, № 3, 2020, 219–234  mathnet  crossref  elib
  • Известия Института математики и информатики Удмуртского государственного университета
    Просмотров:
    Эта страница:93
    Полный текст:37
    Литература:5
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020