Geodesic
Software for constructing of A-chains with ordered enclosing for a plane connected 4-regular graph
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 8 (2019) no. 1, pp. 36-53 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: CAD/CAM, plane graph, path, cutting plan, CAD/CAM.
Mots-clés : polynomial-time algorithm 
@article{VYURV_2019_8_1_a2,
     author = {T. A. Makarovskikh},
     title = {Software for constructing of {A-chains} with ordered enclosing for a plane connected 4-regular graph},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {36--53},
     year = {2019},
     volume = {8},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2019_8_1_a2/}
}
TY  - JOUR
AU  - T. A. Makarovskikh
TI  - Software for constructing of A-chains with ordered enclosing for a plane connected 4-regular graph
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2019
SP  - 36
EP  - 53
VL  - 8
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VYURV_2019_8_1_a2/
LA  - ru
ID  - VYURV_2019_8_1_a2
ER  - 
%0 Journal Article
%A T. A. Makarovskikh
%T Software for constructing of A-chains with ordered enclosing for a plane connected 4-regular graph
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2019
%P 36-53
%V 8
%N 1
%U http://geodesic.mathdoc.fr/item/VYURV_2019_8_1_a2/
%G ru
%F VYURV_2019_8_1_a2
T. A. Makarovskikh. Software for constructing of A-chains with ordered enclosing for a plane connected 4-regular graph. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 8 (2019) no. 1, pp. 36-53. http://geodesic.mathdoc.fr/item/VYURV_2019_8_1_a2/

[1] R. Dewil, P. Vansteenwegen, D. Cattrysse, “A Review of Cutting Path Algorithms for Laser Cutters”, International Journal Adv Manuf. Technol, 87 (2016), 1865–1884 | DOI

[2] T. A. Makarovskikh, A. V. Panyukov, E. A. Savitsky, “Mathematical Models and Routing Algorithms for CAD Technological Preparation of Cutting Processes”, Automation and Remote Control, 78:4 (2017), 868–882 | DOI | MR

[3] R. Dewil, P. Vansteenwegen, D. Cattrysse, M. Laguna, T. Vossen, “An Improvement Heuristic Framework for the Laser Cutting Tool Path Problem”, International Journal of Production Research, 53:6 (2015), 1761–1776 | DOI

[4] J. Hoeft, U. Palekar, “Heuristics for the Plate-cutting Travelling Salesman Problem”, IIE Transactions, 29(9) (1997), 719–731

[5] R. Dewil, P. Vansteenwegen, D. Cattrysse, “Construction Heuristics for Generating Tool Paths for Laser Cutters.”, International Journal of Production Research, 52(20) (2014), 5965–5984 | DOI

[6] A. A. Petunin, A. G. Chentsov, P. A. Chentsov, “On the Issue of Routing Movements in Sheet Cutting of Parts”, Bulletin of the South Ural State University, Series: Mathematical Modelling and Programming, 10:3 (2017), 25–39 | DOI | MR | Zbl

[7] A. G. Chentsov, A. M. Grigoryev, A. A. Chentsov, “Solving a Routing Problem with the Aid of an Independent Computations Scheme”, Bulletin of the South Ural State University, Series: Mathematical Modelling and Programming, 11:1 (2018), 60–74 | DOI | MR | Zbl

[8] A. Petunin, C. Stylios, “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.), v. 49, IFAC-PapersOnLine, 2016, 23–28

[9] A. Chentsov, M. Khachay, D. Khachay, “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), v. 49, IFAC-PapersOnLine, 2016, 651–655 | MR

[10] M. Khachay, K. Neznakhina, “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, 871 (2018), 68–77 | DOI | MR

[11] U. Manber, S. Israni, “Pierce Point Minimization and Optimal Torch Path Determination in Flame Cutting”, J. Manuf. Syst, 3(1) (1984), 81–89 | DOI

[12] T. A. Panyukova, “Constructing of OE-postman Path for a Planar Graph”, Bulletin of the South Ural State University, Series: Mathematical Modelling, Programming and Computer Software, 7:4 (2014), 90–101 | DOI | Zbl

[13] R. S. Garfinkel, I. R. Webb, “On Crossings, the Crossing Postman Problem, and the Rural Postman Problem.”, Networks, 34 (1999), 173–180 | 3.0.CO;2-W class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[14] U. Manber, S. W. Bent, “On Non-intersecting Eulerian Circuits”, Discrete Applied Mathematics, 18 (1987), 87–94 | DOI | MR | Zbl

[15] H. Fleischner, Eulerian Graphs and Related Topics, part 1, v. 1, Ann. Discrete Mathematics, 45, 1990 | MR | Zbl

[16] A. F. Filippov, “The Elementary Proof of Jordan Theorem”, Successes of Mathematical Sciences, 5:5(39) (1950), 173–176 | MR | Zbl

[17] T. Makarovskikh, A. Panyukov, “The Cutter Trajectory Avoiding Intersections of Cuts”, IFAC-PapersOnLine, 50:1 (2017), 2284–2289 | DOI

[18] T. Makarovskikh, A. Panyukov, “Development of Routing Methods for Cutting out Details”, CEUR Workshop Proceedings, 2098 (2018), 249–263 htpp://ceur-ws.org/Vol-2098

[19] A. A. Zykov, The Basics of Graph Theory, High School Book, Moscow, 2004, 664 pp.

[20] T. A. Makarovskikh, A. V. Panyukov, E. A. Savitsky, “Mathematical Models and Routing Algorithms for CAM of Technological Support of Cutting Processes”, ScienceDirect IFAC-PapersOnLine 49–12, 2016, 821–826 | DOI | MR

[21] S. Szeider, “Finding Paths in Graphs Avoiding Forbidden Transitions”, Discrete Applied Mathematics, 2003, no. 126, 261–273 | DOI | MR | Zbl

[22] T. Panyukova, “Chain Sequences with Ordered Enclosing”, Journal of Computer and System Sciences International, 46:1(10) (2007), 83–92 | DOI | MR | Zbl

[23] E. A. Savitskiy, “Using of Wide-with Search Algorithm for Ranking of Edges of a Plane Graph”, Information technologies and systems: Proceedings of the Third International conference, Publishing of Chelyabinsk State University, Chelyabinsk, 2014, 43–45

[24] T. A. Panyukova, “Chains with Ordered Enclosing for Plane Graphs”, Discrete analysis and operation research. Part 2, 13:2 (2006), 31–43 | MR | Zbl