Dynamic Programming Method in a Routing Problem: a Scheme of Independent Computations

The article is devoted to an implementation of the scheme of independent computations for solving the routing problem with precedence constraints and (in the theoretical part) with the cost functions depending on the list of tasks. The prototype of the considered statement is the well-known intractable traveling salesman problem, however, the considered statement is distinguished by the above-mentioned qualitative features. The problem is solved by the dynamic programming method. It is not necessary to construct the whole array of the values of the Bellman function, which is motivated by a desire to decrease the computational complexity. The parallel algorithm for determining the value of the problem value (the global extremum) and the "complete" solution algorithm, which includes the construction of an optimal route, are treated separately. The latter algorithm was realized on the Uran supercomputer; it made use of the (finite) nodes system. Every node had multiple processors, and the totality of the nodes formed the computational cluster. It was possible for certain values of the Bellman function to be (independently) computed by different processors. The developed methods may be applied to certain problems of the nuclear power generation, including the problem of minimization of the radiation exposure of the staff during the emergency situations, similar to Chernobyl and Fukushima. Another possible application may be connected with machine engineering problems, such as routing of a cutting tool of CNC cutting machines. And the last but not the least, this statement may be used to model many problems in the sea and air transportation, and also certain problems in the airborne wildfire detection.

динамическое программирование, маршрут, условия предшествования, существенные списки (заданий), слои пространства позиций, независимые вычисления, функция Беллмана, 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.