НОВЫЙ АЛГОРИТМ ПОСТРОЕНИЯ КРАТЧАЙШЕГО ПУТИ ОБХОДА КОНЕЧНОГО МНОЖЕСТВА НЕПЕРЕСЕКАЮЩИХСЯ КОНТУРОВ НА ПЛОСКОСТИ

  • А. А. Петунин Уральский Федеральный университет
  • Е.Г. Полищук Уральский Федеральный университет
  • С. С. Уколов Уральский Федеральный университет
Ключевые слова: Задача резки, непрерывная резка, оптимизация, достаточные условия, эвристика, GTSP, метод переменных окрестностей

Аннотация

Рассматривается проблема маршрутизации режущего инструмента машин листо-
вой резки с ЧПУ для случая, когда точки врезки расположены на границах деталей, ограни-
ченных отрезками прямых и дугами окружностей, при этом используется техника непрерывной резки (CCP), т.е. каждый контур вырезается целиком, но не используется предва-
рительная дискретизация, то есть резка может начинаться с любой точки контура. Об-
щая задача поиска оптимального маршрута в этом случае сводится к минимизации длины
холостого хода. Показано, что она эквивалентна поиску кратчайшей ломаной с вершинами,
расположенными на контурах. Предложен новый эвристический алгоритм построения
такой ломаной для заранее заданного порядка обхода контуров. Показано, что получаю-
щееся решение представляет собой локальный минимум. Описаны некоторые достаточ-
ные условия, того, что решение является также глобальным минимумом, которые легко
проверяются численно, а некоторые даже визуально. Описана методика автоматического
учёта ограничений предшествования для практически важного случая наличия вложенных
контуров, возникающих как за счёт отверстий в деталях, так и за счёт расположения
мелких деталей в отверстиях крупных. При этом происходит также уменьшение размер-
ности задачи, что положительно сказывается на времени оптимизации, особенно дис-
кретной. Предложен эвристический алгоритм выбора порядка обхода контуров на основе
метода переменных окрестностей (VNS). Описаны альтернативные подходы применения
других методов дискретной оптимизации совместно с предложенным алгоритмом по-
строения кратчайшей ломаной для решения полной задачи непрерывной резки и возникаю-
щие при этом сложности как теоретического, так и практического характера. Описано
обобщение задачи непрерывной резки до более широкого класс задач сегментной резки и
обобщённой сегментной резки, что позволяет продвинуться в решении общей задачи пре-
рывистой резки. Описана схема применения предложенного алгоритма для решения задач
сегментной и обобщённой сегментной резки. Приведены некоторые результаты численных
экспериментов в сравнении с точным решением задачи для дискретной модели GTSP.

Литература

1. Hoeft J., Palekar U. S. Heuristics for the plate-cutting traveling salesman problem, IIE Transactions,
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.
Опубликован
2021-04-04
Выпуск
Раздел
РАЗДЕЛ II. СИСТЕМЫ УПРАВЛЕНИЯ И МОДЕЛИРОВАНИЯ