Динамическое программирование в задаче маршрутизации: схема независимых вычислений
Аннотация
Рассматривается реализация схемы независимых вычислений для решения маршрутной задачи с условиями предшествования и (в теоретической части) с функциями стоимости, зависящими от списка заданий. Используется метод динамического программирования. Отдельно рассматривается параллельный алгоритм определения значения задачи (глобальный экстремум) и алгоритм "полного" решения, включающего построение оптимального маршрута. Последний алгоритм реализован на супервычислителе 'Уран" при использовании (конечной) системы узлов, каждый из которых является совокупностью нескольких процессоров. В свою очередь, вся совокупность узлов образует вычислительный кластер. Допускается возможность вычисления некоторых значений функции Беллмана разными процессорами.
Ключевые слова
динамическое программирование,
маршрут,
условия предшествования,
существенные списки (заданий),
слои пространства позиций,
независимые вычисления,
функция Беллмана,
dynamic programming,
route,
precedence constraints,
feasible sets (of tasks),
state space layers,
independent computations,
Bellman function
Об авторах
А. Г. Ченцов
Институт математики и механики имени Н. Н. Красовского УрО РАН; Уральский Федеральный Университет
Россия
Россия
А. М. Григорьев
Институт математики и механики имени Н. Н. Красовского УрО РАН
Россия
Россия
Список литературы
1. Ченцов А. Г., Кошелева М. С. Динамическое программирование в задаче курьера со стоимостями, зависящими от списка заданий // Мехатроника, автоматизация, управление. 2015. Т. 16, № 4. С. 232-244.
2. Ченцов А. Г. Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами // АиТ. 2012. № 3. С. 134-149.
3. Ченцов А. Г. Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами // Вестник ЮУрГУ. Сер. Мат. моделирование и программирование. 2012. № 18. Вып. 12. С. 53-76.
4. Ташлыков О. Л. Методы оценки и снижения дозовых нагрузок при ремонте АЭС. Екатеринбург: УГТУ-УПИ, 2009.
5. с.
6. Ташлыков О. Л. Дозовые затраты персонала в атомной энергетике. Анализ. Пути снижения. Оптимизация. Saar-1511^0^ Germany: LAP LAMBERT Academic Publishing GmbH & Co. RG, 2011. 232 c.
7. Коробкин В. В., Сесекин А. Н., Ташлыков О. Л., Чен-цов А. Г. Методы маршрутизации и их приложения в задачах повышения безопасности и эффективности эксплуатации атомных станций. М.: Новые технологии, 2012. 234 с.
8. Петунин А. А. О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала // Вестник УГАТУ. Серия: Управление, вычислительная техника и информатика. 2009. Т. 13. № 2 (35). С. 280-286.
9. Фроловский В. Д. Автоматизация проектирования управляющих программ тепловой резки металла на оборудовании с ЧПУ // Информационные технологии в проектировании и производстве. 2005. № 4. С. 63-66.
10. Петунин А. А., Ченцов А. Г., Ченцов П. А. К вопросу о маршрутизации движения инструмента в машинах листовой резки с числовым программным управлением // Науч.-техн. ведомости СПбГПУ. Сер. Информатика. Телекоммуникации. Управление. 2013. № 2 (169). С. 103-111.
11. Меламед И. И., Сергеев С. И., Сигал И. Х. Задача коммивояжера. I. Вопросы теории; II. Точные алгоритмы; III. Приближенные алгоритмы // АиТ. 1989. № 9. C. 3-34; № 10. C. 3-29; № 11. C. 3-26.
12. Gutin G., Punnen A. P. The Traveling Salesman Problem and Its Variations // Kluwer. 2002. 830 p.
13. William J. Cook. In pursuit of the traveling salesman. Mathematics at the limits of computation. Princeton University Press, NJ. 2012. P. 248.
14. Литл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи о коммивояжере // Экономика и математические методы. 1965. Т. 1 (Вып. 1). С. 94-107.
15. Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернет. сборник. Т. 9. М.: Мир, 1964. С. 219-228.
16. Хелд М., Карп Р. М. Применение динамического программирования к задачам упорядочения // Кибернет. сборник. 1964. Т. 9. С. 202-218.
17. Ченцов А. Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. М., Ижевск: НИЦ "Регулярная и хаотическая динамика", 2008. 240 с.
18. Куратовский К., Мостовский А. Теория множеств. М.: Мир. 1970. 416 c.
19. Дьедонне Ж. Основы современного анализа. М.: Мир, 1964. 430 с.
20. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1990. 960 с.
21. Ченцов А. А., Ченцов А. Г., Ченцов П. А. Элементы динамического программирования в экстремальных задачах маршрутизации // Проблемы управления. 2013. № 5. С. 12-21.
22. Ченцов А. Г. Задача последовательного обхода мегаполисов с условиями предшествования // АиТ. 2014. № 4. С. 170-190.
23. Ченцов А. Г. К вопросу о маршрутизации комплексов работ // Вестник Удм. ун-та. Математика. Механика. Комп. науки. 2013. № 1. С. 59-82.
24. Ченцов А. Г., Ченцов А. А. К вопросу о нахождении значения маршрутной задачи с ограничениями // Проблемы управления и информатики. 2016. № 1. С. 41-54.
Рецензия
Для цитирования:
Ченцов А.Г., Григорьев А.М. Динамическое программирование в задаче маршрутизации: схема независимых вычислений. Мехатроника, автоматизация, управление. 2016;17(12):834-846. https://doi.org/10.17587/mau.17.834-846
For citation:
Chentsov A.G., Grigoryev A.M. Dynamic Programming Method in a Routing Problem: a Scheme of Independent Computations. Mekhatronika, Avtomatizatsiya, Upravlenie. 2016;17(12):834-846. (In Russ.) https://doi.org/10.17587/mau.17.834-846
Просмотров: 564
.png)
Послать статью по эл. почте 