A NEW ALGORITHM FOR CONSTRUCTING THE SHORTEST TOUR OF A FINITE SET OF DISJOINT CONTOURS ON A PLANE
Abstract
The problem of tool path routing for the CNC thermal cutting machines is considered.
Pierce points are located at the parts bounding contours, consisting of straight-line segments and
circular arcs. Continuous cutting technique is used, each contour is cut out entirely, and no presampling
occurs, so cutting can start from any point on the contour. General problem of minimizing
the route length is reduced to minimizing the air move length. It is shown to be equivalent to
finding the shortest polyline with vertices on the contours. New algorithm for constructing such a
broken line for fixed order of contour traversing is proposed. The resulting solution is shown to be
a local minimum. Some sufficient conditions are described for the it to be also a global minimum,
which can be easily verified numerically, and some even visually. A technique is described for
automatically taking into account precedence constraints for the practically important case of
nested contours. This also decreases the size of the problem, which has a positive effect on the
optimization time. A heuristic routing algorithm based on the variable neighborhood search (VNS)
is proposed. Alternative approaches to the use of other discrete optimization methods along with
the proposed algorithm for constructing the shortest polyline for solving the complete problem of
continuous cutting, and the resulting difficulties of both theoretical and practical nature are described.
The generalization of the problem of continuous cutting to a wider class of problems of
(generalized) segment cutting is described, which makes it possible to advance in solving the problem
of intermittent cutting. The scheme of application of the proposed algorithm for solving problems
of generalized segment cutting is described. The results of numerical experiments are considered
in comparison with the exact solution of the GTSP problem.
References
1997, Vol. 29, No. 9, pp. 719-731. ISSN 1573-9724. Doi: 10.1023/A:1018582320737.
2. Dewil R., Vansteenwegen P., Cattrysse D. A review of cutting path algorithms for laser
cutters, International Journal of Advanced Manufacturing Technology, 2016, Vol. 87,
No. 5, pp. 1865-1884. ISSN 1433-3015. Doi: 10.1007/s00170-016-8609-1.
3. Petunin A.A., Stylios C. Optimization Models of Tool Path Problem for CNC Sheet Metal Cutting
Machines, IFAC-PapersOnLine, 2016, Vol. 49, No. 12, pp. 23-28.
4. Dewil R., Vansteenwegen P., Cattrysse D. Construction heuristics for generating tool paths for laser
cutters, International Journal of Production Research, 2014, Vol. 52, No. 20, pp. 5965-5984.
5. Sherif S.U., Jawahar N., Balamurali M. Sequential optimization approach for nesting and cutting
sequence in laser cutting, Journal of Manufacturing Systems, 2014, Vol. 33, No. 4, pp. 624-638.
6. Imahori S. [et al.]. Generation of cutter paths for hard material in wire EDM, Journal of Materials
Processing Technology, 2008, Vol. 206, No. 1, pp. 453-461. ISSN 0924-0136.
Doi: 10.1016/j.jmatprotec. 2007.12.039.
7. Chentsov A. G., Chentsov A. A. A Discrete–Continuous Routing Problem with Precedence Constraints,
Proceedings of the Steklov Institute of Mathematics, 2018, Vol. 300, No. 1, pp. 56-71.
ISSN 1531- 8605. Doi: 10.1134/S0081543818020074.
8. Petunin A.A. [et al.]. Elements of dynamic programming in local improvement constructions
for heuristic solutions of routing problems with constraints, Automation and Remote Control,
2017, Vol. 78, No. 4, pp. 666-681. ISSN 1608-3032. Doi: 10.1134 / S0005117917040087.
9. Ye J., Chen Z.G. An Optimized Algorithm of Numerical Cutting-Path Control in Garment
Manufacturing, Advanced Materials Research, 2013, Vol. 796, pp. 454-457. ISSN 1662-8985.
Doi: 10.4028/ www.scientific.net/AMR.796.454.
10. Yu W., Lu L. A route planning strategy for the automatic garment cutter based on genetic algorithm,
2014 IEEE Congress on Evolutionary Computation (CEC), 2014, pp. 379-386. ISSN
1941-0026. Doi: 10.1109/CEC.2014.6900425.
11. Chentsov A.G. [et al.]. Model of megalopolises in the tool path optimisation for CNC plate
cutting machines, International Journal of Production Research, 2018, Vol. 56, No. 14,
pp. 4819-4830. ISSN 0020-7543. Doi: 10.1080/00207543.2017.1421784.
12. Arkin E.M., Hassin R. Approximation algorithms for the geometric covering salesman problem,
Discrete Applied Mathematics, 1994, Vol. 55, No. 3, pp. 197-218. ISSN 0166-218X. Doi:
10.1016/0166- 218X(94)90008-6.
13. Vicencio K., Davis B., Gentilini I. Multi-goal path planning based on the generalized Traveling
Salesman Problem with neighborhoods, 2014 IEEE/RSJ International Conference on Intelligent
Robots and Systems, 2014, pp. 2985-2990. ISSN 2153-0866. Doi: 10.1109/IROS.2014.6942974.
14. Dror M. [et al.]. Touring a sequence of polygons, Proceedings of the thirty-fifth annual ACM
symposium on Theory of computing, ACM, 2003, pp. 473-482.
15. Petunin A.A., Polishchuk E.G., Ukolov S.S. On the new Algorithm for Solving Continuous
Cutting Problem, IFAC-PapersOnLine, 2019, Vol. 52, No. 13, pp. 2320-2325. ISSN 2405-
8963. Doi: 10.1016/j.ifacol.2019.11.552.
16. Hansen P., Mladenovic´ N., Moreno Pe´rez J. A. Variable neighbourhood search: methods and
applications, Annals of Operations Research, 2010, Vol. 175, No. 1, pp. 367-407. ISSN 1572-
9338. Doi: 10.1007/s10479-009-0657-6.
17. Petunin A. A., Chentsov A. G., Chentsov P. A. About routing in the sheet cutting, Bulletin of the
South Ural State University, Series: Mathematical Modelling, Programming and Computer
Software, 2017, Vol . 10, No. 3, pp. 25-39. ISSN 2071-0216. DOI: 10.14529/mmp170303.
18. Smith S. L., Imeson F. GLNS: An effective large neighborhood search heuristic for the Generalized
Traveling Salesman Problem, Computers & Operations Research, 2017, Vol. 87,
pp. 1-19. ISSN 0305-0548. Doi: 10.1016/j.cor.2017.05.010.
19. Papadimitriou C H. Euclidean TSP is NP-complete, Theoretical Computer Science, 1977,
Vol. 4, pp. 237-244.
20. Chentsov A.G., Grigoryev A.M. A Scheme of Independent Calculations in a Precedence Constrained
Routing Problem,, SpringerLink, 2016, pp. 121-135. DOI: 10.1007/978-3-319-44914-2\_10.
21. Saliy Y. V. Influence of predestination conditions on the computational complexity of solution
of route problems by the dynamic programming method, Bulletin of the Udmurt University.
Maths. Mechanics. Computer Science, 2014, No. 1, pp. 76-86. ISSN 1994-9197.
22. Balas E. New classes of efficiently solvable generalized Traveling Salesman Problems, Annals of Operations
Research, 1999, Vol. 86, pp. 529-558. ISSN 1572-9338. Doi: 10.1023/A:1018939709890.
23. Chentsov A.G., Khachai M.Y., Khachai D.M. An exact algorithm with linear complexity for a
problem of visiting megalopolises, Proceedings of the Steklov Institute of Mathematics, 2016,
Vol. 295, No. 1, pp. 38-46. ISSN 1531-8605. Doi: 10.1134/S0081543816090054.
24. Chentsov A., Khachay M., Khachay D. Linear time algorithm for Precedence Constrained
Asymmetric Generalized Traveling Salesman Problem, IFAC-PapersOnLine, 2016, Vol. 49,
No. 12, pp. 651- 655. ISSN 2405-8963. Doi: 10.1016/j.ifacol.2016.07.767.
25. Khachai M.Y., Neznakhina E.D. Approximation Schemes for the Generalized Traveling Salesman
Problem, Proceedings of the Steklov Institute of Mathematics, 2017, Vol. 299, No. 1,
pp. 97-105. ISSN 1531-8605. Doi: 10.1134/S0081543817090127.
26. Khachay M., Neznakhina K. Complexity and approximability of the Euclidean generalized traveling
salesman problem in grid clusters, Annals of Mathematics and Artificial Intelligence, 2020,
Vol. 88, No. 1, pp. 53-69. ISSN 1573-7470. Doi: 10.1007/s10472-019- 09626-w.
27. Gurobi Optimization. Gurobi optimizer reference manual, 2020. Available at: http://www.gurobi.com.
