Software for Constructing of A-chains with Ordered Enclosing for a Plane Connected 4-regular Graph
DOI:
https://doi.org/10.14529/cmse190103Keywords:
plane graph, path, cutting plan, polynomial-time algorithm, CAD/CAMAbstract
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.
References
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)
