maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State Universitymais-1068Research ArticleОригинальные статьиArticlesДинамическое программирование в обобщенной задаче курьера с внутренними работами: элементы параллельной структурыDynamic Programming in a Generalized Courier Problem with Inner Tasks: Elements of a Parallel StructureГригорьевАлексей МихайловичGrigorievA. M.noemail@neicon.ruИванкоЕвгений ЕвгеньевичIvankoE. E.noemail@neicon.ruЧенцовАлександр ГеоргиевичChentsovA. G.chentsov@imm.uran.ruИнститут математики и механики УрО РАНRussian Federation201120092011183101124Copyright © Григорьев А.М., Иванко Е.Е., Ченцов А.Г., 20112011Григорьев А.М., Иванко Е.Е., Ченцов А.Г.Grigoriev A.M., Ivanko E.E., Chentsov A.G.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1068

Рассматриваются вопросы, связанные с реализацией динамического программирования в задачах последовательного обхода мегаполисов, осложненной условиями предшествования и внутренними работами, осуществляемыми в пределах мегаполисов. Предложена схема построения усеченного (неполного) массива значений функции Беллмана, использующая параллельные вычисления и не проигрывающая в качестве. Предлагаемая процедура реализована на многопроцессорной вычислительной системе; распараллеливание реализуется на этапе построения слоев функции Беллмана.

In the article we concern the questions connected with the realization of a dynamic programming method in problems of consequent visiting of megapolises. The realization is complicated by precedence conditions and works inside the megapolises. The scheme for constructing a reduced (partial) array of Bellman function values using parallel computing without loss in accuracy is suggested. This procedure is realized on a multiprocessor computing system; parallelizing is performed at the stage of Bellman function layers construction.

маршруттрассаусловия предшествованияroutetraceprecedence conditionReferencesМеламед И.И., Сергеев С.И., Сигал И.X. Задача коммивояжера. Вопросы теории // Автоматика и телемеханика, 1989. №9. С. 3-34.Меламед И.И., Сергеев С.И., Сигал И.X. Задача коммивояжера. Вопросы теории // Автоматика и телемеханика, 1989. №9. С. 3-34.Меламед И.И., Сергеев С.И., Сигал И.X. Задача коммивояжера. Точные алгоритмы // Автоматика и телемеханика, 1989. №10. С. 3-29.Меламед И.И., Сергеев С.И., Сигал И.X. Задача коммивояжера. Точные алгоритмы // Автоматика и телемеханика, 1989. №10. С. 3-29.Меламед И.И., Сергеев С.И., Сигал И.X. Задача коммивояжера. Приближенные алгоритмы // Автоматика и телемеханика, 1989. №11. С. 3-26.Меламед И.И., Сергеев С.И., Сигал И.X. Задача коммивояжера. Приближенные алгоритмы // Автоматика и телемеханика, 1989. №11. С. 3-26.Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернетический сборник. М.: Мир, 1964. Т. 9. С, 219-228.Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернетический сборник. М.: Мир, 1964. Т. 9. С, 219-228.Хелд М., Карп P.M. Применение динамического программирования к задачам упорядочения // Кибернетический сборник, М.: Мир, 1964. Т. 9. С. 202-218.Хелд М., Карп P.M. Применение динамического программирования к задачам упорядочения // Кибернетический сборник, М.: Мир, 1964. Т. 9. С. 202-218.Сергеев С.И. Гибридные системы управления и динамическая задача коммивояжера // Автоматика и телемеханика, 2008. №1. С. 45-54.Сергеев С.И. Гибридные системы управления и динамическая задача коммивояжера // Автоматика и телемеханика, 2008. №1. С. 45-54.Сигал И.X., Иванова A.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. М.: Наука, 2007. С. 304.Сигал И.X., Иванова A.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. М.: Наука, 2007. С. 304.Ченцов А.А., Чепцов А.Г., Чепцов П.A. Экстремальная задача маршрутизации с внутренними потерями / / Труды Института математики и механики УрО РАН. 2008. Т.14, №3. С. 183-200.Ченцов А.А., Чепцов А.Г., Чепцов П.A. Экстремальная задача маршрутизации с внутренними потерями / / Труды Института математики и механики УрО РАН. 2008. Т.14, №3. С. 183-200.Ченцов А.Г. Об оптимальной маршрутизации в условиях ограничений // Доклады Академии Наук. 2008. Т.423, №3. С. 303-307.Ченцов А.Г. Об оптимальной маршрутизации в условиях ограничений // Доклады Академии Наук. 2008. Т.423, №3. С. 303-307.Ченцов А.Г. Метод динамического программирования в экстремальных задачах маршрутизации с ограничениями // Известия РАН. Теория и системы управления. 2010. №3. С. 52-66.Ченцов А.Г. Метод динамического программирования в экстремальных задачах маршрутизации с ограничениями // Известия РАН. Теория и системы управления. 2010. №3. С. 52-66.Ченцов А.А., Ченцов А.Г., Ченцов П.А. Экстремальная задача маршрутизации перемещений с ограничениями и внутренними потерями // Известия вузов. Математика. 2010. № 6. С. 64-81.Ченцов А.А., Ченцов А.Г., Ченцов П.А. Экстремальная задача маршрутизации перемещений с ограничениями и внутренними потерями // Известия вузов. Математика. 2010. № 6. С. 64-81.Ченцов А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. М.; Ижевск: НИЦ "Регулярная и хаотическая динамика", Ижевский институт компьютерных исследований, 2008. 240 с.Ченцов А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. М.; Ижевск: НИЦ "Регулярная и хаотическая динамика", Ижевский институт компьютерных исследований, 2008. 240 с.Коротаева Л.П., Сесекин А.П., Ченцов А.Г. Об одной модификации метода динамического программирования в задаче последовательного сближения // Журн. вычисл. математики и мат, физики, 1989. Т. 29, № 8. С. 1107-1113.Коротаева Л.П., Сесекин А.П., Ченцов А.Г. Об одной модификации метода динамического программирования в задаче последовательного сближения // Журн. вычисл. математики и мат, физики, 1989. Т. 29, № 8. С. 1107-1113.Коротаева Л.Н., Назаров Э.М., Ченцов А.Г. Об одной задаче о назначениях // Журн. вычисл. математики и мат. физики, 1993. Т. 33, № 4. С. 483-494.Коротаева Л.Н., Назаров Э.М., Ченцов А.Г. Об одной задаче о назначениях // Журн. вычисл. математики и мат. физики, 1993. Т. 33, № 4. С. 483-494.Ченцов А.А., Ченцов А.Г. О решении задачи маршрутной оптимизации методом динамического программирования / / Автоматика и телемеханика. 1998. № 9. С. 117-129.Ченцов А.А., Ченцов А.Г. О решении задачи маршрутной оптимизации методом динамического программирования / / Автоматика и телемеханика. 1998. № 9. С. 117-129.Ченцов А.Г., Ченцов П.А. Маршрутизация с условиями предшествования (задача курьера): метод динамического программирования // Вестник УГТУ- УПИ. Екатеринбург, 2004. Ч. 1. №15 (45). С. 148-152.Ченцов А.Г., Ченцов П.А. Маршрутизация с условиями предшествования (задача курьера): метод динамического программирования // Вестник УГТУ- УПИ. Екатеринбург, 2004. Ч. 1. №15 (45). С. 148-152.Куратовский К., Мостовский А. Теория множеств. М.: Мир. 1970. 416 с.Куратовский К., Мостовский А. Теория множеств. М.: Мир. 1970. 416 с.Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. 960 с.Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. 960 с.Сесекин А.Н., Ташлыков О.Л., Щеклеин С.Е., Куклин М.Ю., Ченцов А.Г., Кадников А. А. Использование метода динамического программирования для оптимизации траектории перемещения работников в радиационно опасных зонах с целью минимизации облучения // Известия вузов. Ядерная энергетика. 2006. № 2. С. 41-48.Сесекин А.Н., Ташлыков О.Л., Щеклеин С.Е., Куклин М.Ю., Ченцов А.Г., Кадников А. А. Использование метода динамического программирования для оптимизации траектории перемещения работников в радиационно опасных зонах с целью минимизации облучения // Известия вузов. Ядерная энергетика. 2006. № 2. С. 41-48.Ташлыков О. Л., Сесекин А.Н., Ченцов А. Г., Щеклеин С. К., Балушкин Ф. А., Хомяков А. П. Возможности математических методов моделирования в решении проблемы облучаемости персонала // Вопросы радиационной безопасности. 2009. № 4. С. 39-49.Ташлыков О. Л., Сесекин А.Н., Ченцов А. Г., Щеклеин С. К., Балушкин Ф. А., Хомяков А. П. Возможности математических методов моделирования в решении проблемы облучаемости персонала // Вопросы радиационной безопасности. 2009. № 4. С. 39-49.Ташлыков О.Л., Сесекин А.Н.. Щеклеин С.Е., Ченцов А.Г. Разработка оптимальных алгоритмов вывода АЭС из эксплуатации с использованием методов математического моделирования // Известия вузов. Ядерная энергетика. 2009. № 2. С. 115-120.Ташлыков О.Л., Сесекин А.Н.. Щеклеин С.Е., Ченцов А.Г. Разработка оптимальных алгоритмов вывода АЭС из эксплуатации с использованием методов математического моделирования // Известия вузов. Ядерная энергетика. 2009. № 2. С. 115-120.

The authors declare that there are no conflicts of interest present.