Программное обеспечение для построения A-цепей с упорядоченным охватыванием в плоском связном 4-регулярном графе

Татьяна Анатольевна Макаровских

Аннотация


В CAD/CAM-системах технологической подготовки процессов раскроя встает задача построения маршрута движения режущего инструмента, при котором отрезанная от листа часть не требует дополнительных разрезаний и запрещены пересечения траектории резки (касания допускаются). Формально такая задача может быть сформулирована как задача построения самонепересекающейся цепи в плоском эйлеровом графе, представляющим гомеоморфный образ раскройного плана. В конечном счете задачи построения маршрутов, удовлетворяющих технологическим ограничениям, сводятся к нахождению A-цепи с упорядоченным охватыванием в плоском связном 4-регулярном графе. В статье предложен алгоритм нахождения такой цепи. Выполнение алгоритма состоит из двух этапов. На первом этапе выявляются и расщепляются точки сочленения ранга k. На втором этапе построение цепи начинается из произвольной вершины, инцидентной внешней грани; первым ребром цепи выбирается инцидентное данной вершине ребро максимального ранга; далее организуется итерационный процесс, где в качестве следующего ребра выбирается непройденное ребро максимального ранга, являющееся левым либо правым соседом текущего ребра. Показано, что для плоского связного 4-регулярного графа алгоритм строит маршрут с указанными свойствами за линейное время. Представленные алгоритмы реализованы в виде компьютерной программы. Приведены примеры решения ряда тестовых задач.

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


плоский граф; маршрут; раскройный план; полиномиальный алгоритм; CAD/CAM

Полный текст:

PDF

Литература


Dewil R., Vansteenwegen P., Cattrysse D. A Review of Cutting Path Algorithms for Laser Cutters. International Journal Adv Manuf. Technol. 2016. vol. 87. pp. 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. pp. 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, iss. 6. pp. 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). pp. 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). pp. 5965–5984.

Petunin A.A., Chentsov A.G., Chentsov P.A. On the Issue of Routing Movements in Sheet Cutting of Parts. Vestnik Yuzhno-Ural’skogo gosudarstvennogo universiteta. Seriya: Matematicheskoe modelirovanie i programmirovanie [Bulletin of the South Ural State University, Series: Mathematical Modelling and Programming]. 2017. vol. 10, no. 3. pp. 25–39. DOI: 10.14529/mmp170303 (in Russian)

Chentsov A.G., Grigoryev A.M., Chentsov A.A. Solving a Routing Problem with the Aid of an Independent Computations Scheme. Vestnik Yuzhno-Ural’skogo gosudarstvennogo universiteta. Seriya: Matematicheskoe modelirovanie i programmirovanie [Bulletin of the South Ural State University, Series: Mathematical Modelling and Programming]. 2018. vol. 11, no. 1. pp. 60–74. DOI: 10.14529/mmp180106 (in Russian)

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. pp. 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. pp. 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. pp. 68–77.

Manber U., Israni S. Pierce Point Minimization and Optimal Torch Path Determination in Flame Cutting. J. Manuf. Syst. 1984. vol. 3(1). pp. 81–89. DOI: 10.1016/0278-6125(84)90024-4

Panyukova T.A. Constructing of OE-postman Path for a Planar Graph. Bulletin of the South Ural State University, Series: Mathematical Modelling, Programming and Computer Software. 2014. vol. 7, no. 4. pp. 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). pp. 173–180.

Manber U., Bent S.W. On Non-intersecting Eulerian Circuits. Discrete Applied Mathematics. 1987. vol. 18. pp. 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. no. 45.

Filippov A.F. The Elementary Proof of Jordan Theorem Uspekhi matematicheskikh nauk [Successes of Mathematical Sciences]. 1950. vol. 5, no. 5(39). pp. 173–176. (in Russian)

Makarovskikh T., Panyukov A. The Cutter Trajectory Avoiding Intersections of Cuts. IFAC-PapersOnLine. 2017. vol. 50, issue 1. pp. 2284-2289.

Makarovskikh T., Panyukov A. Development of Routing Methods for Cutting out Details. CEUR Workshop Proceedings. 2018. vol. 2098. pp. 249–263. Available at: htpp://ceur-ws.org/Vol-2098 (accessed: 20.07.2018).

Zykov A.A. Osnovy teorii grafov [The Basics of Graph Theory]. Moscow, High School Book, 2004. 664 p. (in Russian)

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. pp. 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. pp. 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). pp. 83–92. DOI: 10.1134/S1064230707010108

Savitskiy E.A. Using of Wide-with Search Algorithm for Ranking of Edges of a Plane Graph. Informacionnye tekhnologii i sistemy: tr. Tret’ej mezhdunar. nauch. konf. [Information technologies and systems: Proceedings of the Third International conference]. Chelyabinsk, Publishing of Chelyabinsk State University. 2014. pp. 43–45. (in Russian)

Panyukova T.A. Chains with Ordered Enclosing for Plane Graphs. Diskretnyj analiz i issledovanie operacij. Chast’ 2. [Discrete analysis and operation research. Part 2]. 2006. vol. 13, no. 2. pp. 31–43. (in Russian)




DOI: http://dx.doi.org/10.14529/cmse190103