Dynamic Programming in a Generalized Courier Problem with Inner Tasks: Elements of a Parallel Structure
Abstract
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.
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.
About the Authors
A. M. Grigoriev
Институт математики и механики УрО РАН
Russian Federation
Russian Federation
E. E. Ivanko
Институт математики и механики УрО РАН
Russian Federation
Russian Federation
A. G. Chentsov
Институт математики и механики УрО РАН
Russian Federation
Russian Federation
References
1. Меламед И.И., Сергеев С.И., Сигал И.X. Задача коммивояжера. Вопросы теории // Автоматика и телемеханика, 1989. №9. С. 3-34.
2. Меламед И.И., Сергеев С.И., Сигал И.X. Задача коммивояжера. Точные алгоритмы // Автоматика и телемеханика, 1989. №10. С. 3-29.
3. Меламед И.И., Сергеев С.И., Сигал И.X. Задача коммивояжера. Приближенные алгоритмы // Автоматика и телемеханика, 1989. №11. С. 3-26.
4. Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернетический сборник. М.: Мир, 1964. Т. 9. С, 219-228.
5. Хелд М., Карп P.M. Применение динамического программирования к задачам упорядочения // Кибернетический сборник, М.: Мир, 1964. Т. 9. С. 202-218.
6. Сергеев С.И. Гибридные системы управления и динамическая задача коммивояжера // Автоматика и телемеханика, 2008. №1. С. 45-54.
7. Сигал И.X., Иванова A.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. М.: Наука, 2007. С. 304.
8. Ченцов А.А., Чепцов А.Г., Чепцов П.A. Экстремальная задача маршрутизации с внутренними потерями / / Труды Института математики и механики УрО РАН. 2008. Т.14, №3. С. 183-200.
9. Ченцов А.Г. Об оптимальной маршрутизации в условиях ограничений // Доклады Академии Наук. 2008. Т.423, №3. С. 303-307.
10. Ченцов А.Г. Метод динамического программирования в экстремальных задачах маршрутизации с ограничениями // Известия РАН. Теория и системы управления. 2010. №3. С. 52-66.
11. Ченцов А.А., Ченцов А.Г., Ченцов П.А. Экстремальная задача маршрутизации перемещений с ограничениями и внутренними потерями // Известия вузов. Математика. 2010. № 6. С. 64-81.
12. Ченцов А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. М.; Ижевск: НИЦ "Регулярная и хаотическая динамика", Ижевский институт компьютерных исследований, 2008. 240 с.
13. Коротаева Л.П., Сесекин А.П., Ченцов А.Г. Об одной модификации метода динамического программирования в задаче последовательного сближения // Журн. вычисл. математики и мат, физики, 1989. Т. 29, № 8. С. 1107-1113.
14. Коротаева Л.Н., Назаров Э.М., Ченцов А.Г. Об одной задаче о назначениях // Журн. вычисл. математики и мат. физики, 1993. Т. 33, № 4. С. 483-494.
15. Ченцов А.А., Ченцов А.Г. О решении задачи маршрутной оптимизации методом динамического программирования / / Автоматика и телемеханика. 1998. № 9. С. 117-129.
16. Ченцов А.Г., Ченцов П.А. Маршрутизация с условиями предшествования (задача курьера): метод динамического программирования // Вестник УГТУ- УПИ. Екатеринбург, 2004. Ч. 1. №15 (45). С. 148-152.
17. Куратовский К., Мостовский А. Теория множеств. М.: Мир. 1970. 416 с.
18. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. 960 с.
19. Сесекин А.Н., Ташлыков О.Л., Щеклеин С.Е., Куклин М.Ю., Ченцов А.Г., Кадников А. А. Использование метода динамического программирования для оптимизации траектории перемещения работников в радиационно опасных зонах с целью минимизации облучения // Известия вузов. Ядерная энергетика. 2006. № 2. С. 41-48.
20. Ташлыков О. Л., Сесекин А.Н., Ченцов А. Г., Щеклеин С. К., Балушкин Ф. А., Хомяков А. П. Возможности математических методов моделирования в решении проблемы облучаемости персонала // Вопросы радиационной безопасности. 2009. № 4. С. 39-49.
21. Ташлыков О.Л., Сесекин А.Н.. Щеклеин С.Е., Ченцов А.Г. Разработка оптимальных алгоритмов вывода АЭС из эксплуатации с использованием методов математического моделирования // Известия вузов. Ядерная энергетика. 2009. № 2. С. 115-120.
Review
For citations:
Grigoriev A.M., Ivanko E.E., Chentsov A.G. Dynamic Programming in a Generalized Courier Problem with Inner Tasks: Elements of a Parallel Structure. Modeling and Analysis of Information Systems. 2011;18(3):101-124. (In Russ.)
Views:
508
Email this article 