Solving a Routing Problem with the Aid of an Independent Computations Scheme

Статья посвящена вопросам построения и реализации параллельных алгоритмов для решения прикладных задач. Рассматривается задача маршрутизации перемещений с ограничениями и усложненными функциями стоимости. Предполагается, что объекты посещения - суть мегаполисы (непустые конечные множества), при посещении которых должны выполнятся некоторые работы, именуемые далее внутренними. По постановке задачи имеются ограничения в виде условий предшествования. Стоимости перемещений зависят от списка заданий, которые не выполнены на момент перемещения. Ситуация такого рода возникает, в частности, при аварийных ситуациях, связанных с работой АЭС и подобных происходящим в Чернобыле и Фукусиме. Речь идет об утилизации источников радиоактивного излучения, осуществляемой последовательно во времени; в этом случае исполнитель находится под воздействием источников, которые не были демонтированы на момент соответствующего перемещения. За счет этого в функциях стоимости, оценивающих воздействие радиации на исполнителя, возникает зависимость от списка невыполненных заданий. Последние состоят в том или ином варианте ' выключения' соответствующего источника. В настоящем исследовании излагается подход к решению данной задачи параллельным алгоритмом, реализуемым на суперкомпьютере УРАН. Приведены результаты вычислительного эксперимента.

Ключевые слова

динамическое программирование; маршрут; условия предшествования; параллельный алгоритм.

Литература

1. Garey, M.R. Computers and Intractability: A Guide to the Theory of NP-Completeness / M.R. Garey, D.S. Johnson. - N.Y., W.H. Freeman, 1979.
2. Gutin, G. The Traveling Salesman Problem and Its Variations / G. Gutin, A.P. Punnen. - N.Y., Springer, 2002.
3. Cook, W.J. In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation / W.J. Cook. - New Jersey, Princeton University Press, 2012.
4. Меламед, И.И. Задача коммивояжера. Вопросы теории / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - T. 50, № 9. - C. 3-34.
5. Меламед, И.И. Задача коммивояжера. Точные алгоритмы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - T. 50, № 10. - C. 3-29.
6. Меламед, И.И. Задача коммивояжера. Приближенные алгоритмы / И.И. Меламед, С.И. Сергеев, И.Х. Сигал // Автоматика и телемеханика. - 1989. - T. 50, № 11. - C. 3-26.
7. Литл, Дж. Алгоритм для решения задачи о коммивояжере / Дж. Литл, К. Мурти, Д. Суини, К. Кэрел // Экономика и математические методы. - 1965. - Т. 1, вып. 1. - C. 94-107.
8. Беллман, Р. Применение динамического программирования к задаче о коммивояжере / Р. Беллман // Кибернетический сборник. - Т. 9.- М.: Мир, 1964. - C. 219-228.
9. Хелд, М. Применение динамического программирования к задачам упорядочения / М. Хелд, Р.М. Карп // Кибернетический сборник. - Т. 9. - М.: Мир, 1964. - C. 202-218.
10. Leon, V.J. Replanning and Analysis of Partial Setup Strategies in Printed Circuit Board Assembly Systems / V.J. Leon, B.A. Peters // International Journal of Flexible Manufacturing Systems. - 1996. - V. 8. - P. 389-411.
11. Alkaya, A.F. A New Generalization of the Traveling Salesman Problem / A.F. Alkaya, E. Duman // Applied and Computational Mathematics. - 2010. - V. 9, № 2. - P. 162-175.
12. Kinable, J. Hybrid Optimization Methods for Time-Dependent Sequencing Problems / J. Kinable, A. Cire, W.J. van Hoeve // European Journal of Operational Research. - 2017. - V. 259, № 3. - P. 887-897.
13. Ченцов, А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории / А.Г. Ченцов. - Ижевск: НИЦ 'Регулярная и хаотическая динамика', Ижевский институт компьютерных исследований, 2008.
14. Коробкин, В.В. Методы маршрутизации и их приложения в задачах повышения безопасности и эффективности эксплуатации атомных станций / В.В. Коробкин, А.Н. Сесекин, О.Л. Ташлыков, А.Г. Ченцов. - М.: Новые технологии, 2012.
15. Ташлыков, О.Л. Дозовые затраты персонала в атомной энергетике. Анализ. Пути снижения. Оптимизация: монография / О.Л. Ташлыков. - Saarbruke: LAP LAMBERT Academic Publishing GmbH & Co. RG., 2011.
16. Петунин, А.А. О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала / А.А. Петунин // Вестник УГАТУ. Серия: Управление, вычислительная техника и информатика. - 2009. - Т. 13, № 2 (35). - C. 280-286.
17. Петунин, А.А. К вопросу о маршрутизации движения инструмента в машинах листовой резки с числовым программным управлением / А.А. Петунин, А.Г. Ченцов, П.А. Ченцов // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. - 2013. - № 2 (169). - С. 103-111.
18. Фроловский, В.Д. Автоматизация проектирования управляющих программ тепловой резки металла на оборудовании с ЧПУ / В.Д. Фроловский // Информационные технологии в проектировании и производстве. - 2005. - № 4. - С. 63-66.
19. Wang, G.G. Optimal Process Planning for a Combined Punch-and-Laser Cutting Machine Using and Colony Optimization / G.G. Wang, S.Q. Xie // International Journal of Production Research. - 2005. - V. 43, № 11. - P. 2195-2216.
20. Dewil, R. Construction Heuristics for Generating Tool Paths for Laser Cutters / R. Dewil, P. Vansteenwegen, D. Cattrysse // International Journal of Production Research. - 2014. - P. 1-20.
21. Ченцов, А.Г. Маршрутизация в условиях ограничений: задача о посещении мегаполисов / А.Г. Ченцов, П.А. Ченцов // Автоматика и телемеханика. - 2016. - № 11. - C. 96-117.
22. Dieudonne, J. Foundations of Modern Analysis / J. Dieudonne. - N.Y.: Academic, 1960.
23. Cormen, T.H. Introduction to Algorithms / T.H. Cormen, C.E. Leizerson, R.L. Rivest. - Cambridge: MIT Press, 1990.
24. Ченцов, А.Г. К вопросу о маршрутизации комплексов работ / А.Г. Ченцов // Вестник Удмуртского ун-та. Математика. Механика. Компьютерные науки. - 2013. - № 1. - С. 59-82.
25. Ченцов, А.Г. Задача маршрутизации с ограничениями, зависящими от списка заданий / А.Г. Ченцов, А.А. Ченцов // Доклады Академии наук. - 2015. - Т. 465, № 2. - C. 154-158.
26. Ченцов, А.А. К вопросу о нахождении значения маршрутной задачи с ограничениями / А.А. Ченцов, А.Г. Ченцов // Проблемы управления и информатики. - 2016. - № 1. - C. 41-54.
27. Lawler, E.L. Efficient Implementation of Dynamic Programming Algorithms for Sequencing Problems / E.L. Lawler // CWI Technical report. Stichting Mathematisch Centrum. Mathematische Besliskunde-BW. - 1979. - V. 106, № 79. - P. 1-16.
28. Ченцов, А.Г. Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами / А.Г. Ченцов // Автоматика и телемеханика. - 2012. - № 3. - С. 134-149.
29. Ченцов, А.Г. Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами / А.Г. Ченцов // Вестник ЮУрГУ. Серия: Математическое моделирование и программирование. - 2012. - № 18 (277), вып. 12. - С. 44-52.
30. Ченцов, А.Г. Динамическое программирование в задаче маршрутизации: схема независимых вычислений / А.Г. Ченцов, А.М. Григорьев // Мехатроника, автоматизация, управление. - 2016 - Т. 17, № 12. - C. 834-846.
31. Schmidt, G. Relations and Graphs: Discrete Mathematics for Computer Scientists / G. Schmidt, T. Strohlein // EATCS Monographs on Theoretical Computer Science. - N.Y.: Springer-Verlag, 1993.
32. Steiner, G. On the Сomplexity of Dynamic Programming for Sequencing Problems with Precedence Constraints / G. Steiner // Annals of Operations Research. - 1990. - V. 26, № 1. - P. 103-123.