THE ALGORITHMS FOR CONSTRUCTING OF CUTTER OPTIMAL PATH

Article Sidebar

PDF
Published: Jul 6, 2015
Keywords:
Plane graph Effective algorithm Cutting process Ordered enclosing Path.

Main Article Content

T. A. Makarovskikh
South Ural State University

Abstract

This paper considers methods of automatic cutter path choice for laser equipment. Graphs are often used as mathematical models for different control problems or automated design. Particularly, for automated system of cutting process preparation the mathematical model of a cutting plan should be a topological plane graph. Nowadays a branch of graph theory dealing with constructing some paths and trails with different restrictions is rapidly developing. This research considers the following cutting problem formulated in the terms of graph theory. We need define a shortest cutter trajectory so that part cut out a sheet does not require further cuttings. If one considers the cutter trajectory to be a trail of a plane graph, the requirement of eliminating the necessity of cutting of a piece separated from the sheet can be formalized as the condition that internal faces of any initial part of the given trail does not intersect the graph edges.  The polynomial algorithms presented in the paper allow to solve the routing problem either for connected or disconnected plane graph.

Article Details

Issue
Vol. 1 No. 2 (2014): JOURNAL OF COMPUTATIONAL AND ENGINEERING MATHEMATICS
Section
Survey Articles

References

Kantorovich L.V., Zalgaller V.A. Rational Cutting of Industrial Materials. St. Peterburg, Nevskij Dialekt publ., 2012. (in Russian)

Verkhoturov M.A., Tarasenko P.Yu. Mathematical Support for a Path Optimization Problem of a Plane Figure Circuit Cutting. Vestnik UGATU. Seriya "Upravlenie, Vychislitelnaya Tekhnika i Informatika" - Bulletin of USATU. Series "Control, Computing and Informatics", 2008, vol. 10, no. 2(27), pp. 123-130. (in Russian)

Petunin A.A. About Some Heuristic Strategies Forming a Cutter Path in Development of Control Programs for Thermal Cutting Machines. Vestnik UGATU. Seriya "Upravlenie, Vychislitelnaya Tekhnika i Informatika" - Bulletin of USATU. Series "Control, Computing and Informatics", 2008, vol. 13, no. 2(35), pp. 280-286. (in Russian)

Pisanski T., Tucker T.W., Zitnik A. Straight-ahead walks in Eulerian graphs. Discrete Mathematics, 2004, no. 81, pp. 237-246. DOI:10.1016/j.disc.2003.09.011

Fleischner H. Eulerian Graphs and Related Topics: Part 1, Volume 2. Series "Annals of Discrete Mathematics", vol. 50. Amsterdam, North Holland Publ., 1991. DOI:10.1016/S0167-5060(08)70153-5

Fleischner H. Eulerian Graphs and Related Topics: Part 1, Volume 1. Series "Annals of Discrete Mathematics", vol. 45. Amsterdam, North Holland Publ., 1990. DOI:10.1016/S0167-5060(08)70942-7

Fleischner H., Beineke L.W., Wilson R.J. Eulerian Graphs, Selected Topics in Graph Theory 2. London, New-York, Academic Press, 1983.

Kotzig A., Moves Without Forbidden Transitions in a Graph. Mat.-Fiz. Casopis, 1968, vol. 18 , no. 1, pp. 76-80.

Panyukov A.V., Panioukova T.A. The Algorithm for Tracing of Flat Euler Cycles with Ordered Enclosing. Proceedings of Chelyabinsk Scientific Center, 2000, no. 4(9), pp. 18-22.

Panyukova T. Cover with Ordered Enclosing for Flat Graphs. Electronic Notes in Discrete Mathematics, 2007, no. 28, pp. 17-24. DOI: 10.1016/j.endm.2007.01.004

Panyukova T. Ordered Enclosing Covers with Minimal Length of Additional Edges. Abstracts of 8th French Combinatorial Conference: Orsay, France (June 28 - July 2, 2010). Orsay, France, 2010, abstract no. 18.

Panioukova T.A., Panyukov A.V. Algorithms for Construction of Ordered Enclosing Traces in Planar Eulerian Graphs. The International Workshop on Computer Science and Information Technologies' 2003, Proceedings of Workshop, Ufa, September 16-18, Ufa, USATU, 2003, vol. 1, pp. 134-138.

Panyukova T. The special routes in plane graphs. Special Issue: Sixth International Congress on Industrial Applied Mathematics (ICIAM07) and GAMM Annual Meeting, 2007. Zurich, 2008, vol. 7, issue 1, pp. 2070015-2070016. DOI:10.1002/pamm.200701066.

Panyukova T. Covering with Ordered Enclosing for a Multiconneted Graph. Abstracts of Seventh Czech-Slovak Symposium on Graph Theory, Combinatorics and Applications: Koshice, Slovakia (July 7-13, 2013), Koshice, 2013, p. 65.

Panyukova T.A. Optimal Eulerian Covers for Plane Graphs Discrete Analysis and Operation Research, 2010, vol. 18, no. 2, pp. 64-74. (in Russian)

Panyukova T., Savitsky E. Allowed Eulerian Covers with Ordered Enclosing for Multiconnected Graph. Statistika. Modelirovanie. Optimizatsiya. Vserossijskaya nauchno-prakticheskaya konferentsiya. CHelyabinsk. YUzhno-Ural'skij gosudarstvennyj universitet Statistics. Modelling. Optimization. Proceedings of All-Russian conference, Chelyabinsk, South Ural State University, Chelyabinsk, SUSU, 2011, pp. 154-159. (in Russian).

Panyukova T., Savitskiy E. Optimization of Resources Usage for Technological Support of Cutting Processes. Proceedings of the Workshop on Computer Science and Information Technologies (CSIT'2010), Russia, Moscow - St.Petersburg, September 13-19, 2010, Ufa, USATU, 2010, vol. 1, pp. 66-70.