Программное обеспечение для построения a-цепей с упорядоченным охватыванием в плоском связном 4-регулярном графе
Автор: Макаровских Татьяна Анатольевна
Статья в выпуске: 1 т.8, 2019 года.
Бесплатный доступ
В CAD/CAM-системах технологической подготовки процессов раскроя встает задача построения маршрута движения режущего инструмента, при котором отрезанная от листа часть не требует дополнительных разрезаний и запрещены пересечения траектории резки (касания допускаются). Формально такая задача может быть сформулирована как задача построения самонепересекающейся цепи в плоском эйлеровом графе, представляющим гомеоморфный образ раскройного плана. В конечном счете задачи построения маршрутов, удовлетворяющих технологическим ограничениям, сводятся к нахождению A-цепи с упорядоченным охватыванием в плоском связном 4-регулярном графе. В статье предложен алгоритм нахождения такой цепи. Выполнение алгоритма состоит из двух этапов. На первом этапе выявляются и расщепляются точки сочленения ранга k. На втором этапе построение цепи начинается из произвольной вершины, инцидентной внешней грани; первым ребром цепи выбирается инцидентное данной вершине ребро максимального ранга; далее организуется итерационный процесс, где в качестве следующего ребра выбирается непройденное ребро максимального ранга, являющееся левым либо правым соседом текущего ребра. Показано, что для плоского связного 4-регулярного графа алгоритм строит маршрут с указанными свойствами за линейное время. Представленные алгоритмы реализованы в виде компьютерной программы. Приведены примеры решения ряда тестовых задач.
Плоский граф, маршрут, раскройный план, полиномиальный алгоритм
Короткий адрес: https://sciup.org/147233189
IDR: 147233189 | УДК: 512.5, | DOI: 10.14529/cmse190103
Software for constructing of a-chains with ordered enclosing for a plane connected 4-regular graph
The task of constructing the cutting path of the tool when the part cut off from the sheet does not require additional cuts and the trajectories of cuts intersections are forbidden (the touches are allowed) may arise in CAD/CAM-systems of technological preparation of cutting processes. Formally, such a task can be formulated as the problem of constructing a self-non-intersecting chain in a plane Euler graph representing a homeomorphic image of a cutting plan. Finally, the tasks of constructing routes satisfying the technological constraints are reduced to defining an A-chain with ordered enclosing for a plane connected 4-regular graph. This article is devoted to the algorithm for finding such a chain. The execution of this algorithm consists of two stages. At the first stage, cut-vertices of rank k are identified and splitted. At the second stage, the construction of the chain starts from an arbitrary vertex incident to the outer face; the first edge of the chain is chosen to be an edge of maximal rank incident to a given vertex; next, an iterative process is organized where, as the next edge, an unpassed edge of maximum rank is chosen, which is the left or right neighbour of the current one. It is shown that the algorithm constructs a route with the indicated properties in linear time for a plane connected 4-regular graph. The considered algorithms are realized as a computer program. The examples of some test problems are given in this paper.
Список литературы Программное обеспечение для построения a-цепей с упорядоченным охватыванием в плоском связном 4-регулярном графе
- Dewil R., Vansteenwegen P., Cattrysse D. A Review of Cutting Path Algorithms for Laser Cutters // International Journal Adv Manuf. Technol. 2016. Vol. 87. P. 1865-1884. DOI: 10.1007/s00170-016-8609-1
- Makarovskikh Т.А., Panyukov А.V., Savitsky E.A. Mathematical Models and Routing Algorithms for CAD Technological Preparation of Cutting Processes // Automation and Remote Control. 2017. Vol. 78, No. 4. P. 868-882.
- Dewil R., Vansteenwegen P., Cattrysse D., Laguna M., Vossen T. An Improvement Heuristic Framework for the Laser Cutting Tool Path Problem // International Journal of Production Research. 2015. Vol. 53, Issue 6. P. 1761-1776. DOI: 10.1080/00207543.2014.959268
- Hoeft J., Palekar U. Heuristics for the Plate-cutting Travelling Salesman Problem. // IIE Transactions. 1997. Vol. 29(9). P. 719-731.
- Dewil R., Vansteenwegen P., Cattrysse D. Construction Heuristics for Generating Tool Paths for Laser Cutters. // International Journal of Production Research. 2014. Vol. 52(20). P. 5965-5984.
- Петунин А.А., Ченцов А.Г., Ченцов П.А. К вопросу о маршрутизации перемещений при листовой резке деталей // Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование. 2017. Т. 10, № 3. С. 25-39.
- DOI: 10.14529/mmp170303
- Chentsov A.G., Grigoryev A.M., Chentsov A.A. Solving a Routing Problem with the Aid of an Independent Computations Scheme // Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование. 2018. Т. 11, № 1. С. 60-74.
- DOI: 10.14529/mmp180106
- Petunin A., Stylios C. Optimization Models of Tool Path Problem for CNC Sheet Metal Cutting Machines. // 8th IFAC Conference on Manufacturing Modelling, Management and Control MIM 2016 Troyes, France, June 28-30, 2016. IFAC-PapersOnLine, 2016. Vol. 49. P. 23-28.
- Chentsov A., Khachay M., Khachay D. Linear Time Algorithm for Precedence Constrained Asymmetric Generalized Traveling Salesman Problem // 8th IFAC Conference on Manufacturing Modelling, Management and Control MIM 2016, Troyes, France, June 28-30, 2016. IFAC-PapersOnLine, 2016. Vol. 49. P. 651-655.
- Khachay M., Neznakhina K. Towards Tractability of the Euclidean Generalized Travelling Salesman Problem in Grid Clusters Defined by a Grid of Bounded Height // Communications in Computer and Information Science. 2018. Vol. 871. P. 68-77.
- Manber U., Israni S. Pierce Point Minimization and Optimal Torch Path Determination in Flame Cutting // J. Manuf. Syst. Vol 3(1). 1984. P. 81-89.
- DOI: 10.1016/0278-6125(84)90024-4
- Panyukova T.A. Constructing of OE-postman Path for a Planar Graph // Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование. 2014. Т. 7, № 4. С. 90-101.
- DOI: 10.14529/mmp140407
- Garfinkel R.S., Webb I.R. On Crossings, the Crossing Postman Problem, and the Rural Postman Problem. // Networks. 1999. Vol. 34(3). P. 173-180.
- Manber U., Bent S.W. On Non-intersecting Eulerian Circuits // Discrete Applied Mathematics. 1987. Vol. 18. P. 87-94.
- DOI: 10.1016/0166-218X(87)90045-X
- Fleischner H. Eulerian Graphs and Related Topics. Part 1, Vol. 1.: Ann. Discrete Mathematics, 1990. № 45.
- Филиппов А.Ф. Элементарное доказательство теоремы Жордана // Успехи математических наук. 1950. Т. 5, Вып. 5(39). C. 173-176.
- Makarovskikh T., Panyukov A. The Cutter Trajectory Avoiding Intersections of Cuts // IFAC-PapersOnLine. 2017. Vol. 50, Issue 1. P. 2284-2289.
- Makarovskikh T., Panyukov A. Development of Routing Methods for Cutting out Details // CEUR Workshop Proceedings. 2018. Vol. 2098. P. 249-263. URL: htpp://ceur-ws.org/ Vol-2098 (дата обращения: 20.07.2018).
- Зыков А.А. Основы теории графов. М.: Вузовская книга, 2004. 664 с.
- Makarovskikh Т.А., Panyukov А.V., Savitsky E.A. Mathematical Models and Routing Algorithms for CAM of Technological Support of Cutting Processes // ScienceDirect IFAC-PapersOnLine 49-12. 2016. P. 821-826.
- DOI: 10.1016/j.ifacol.2016.07.876
- Szeider S. Finding Paths in Graphs Avoiding Forbidden Transitions // Discrete Applied Mathematics. 2003. No. 126. P. 261-273.
- DOI: 10.1016/S0166-218X(02)00251-2
- Panyukova T. Chain Sequences with Ordered Enclosing // Journal of Computer and System Sciences International. 2007. Vol. 46, No. 1(10). P. 83-92.
- DOI: 10.1134/S1064230707010108
- Савицкий Е.А. Использование алгоритма поиска в ширину для определения уровней вложенности ребер плоского графа // Информационные технологии и системы: Труды Третьей междунар. науч. конф. Челябинск: Изд-во ЧелГУ, 2014. C. 43-45.
- Панюкова Т.А. Цепи с упорядоченным охватыванием в плоских графах // Дискретный анализ и исследование операций. Часть 2. 2006. Т. 13, № 2. С. 31-43.
