Using PCGTSPAlgorithm for Solving Generalized Segment Continuous Cutting Problem
Электронный научный архив УРФУ
Информация об архиве | Просмотр оригинала| Поле | Значение | |
| Заглавие |
Using PCGTSPAlgorithm for Solving Generalized Segment Continuous Cutting Problem
|
|
| Автор |
Petunin, A.
Khachay, M. Ukolov, S. Chentsov, P. |
|
| Тематика |
BRANCH-AND-BOUND
CUTTING PATH PROBLEM DYNAMIC PROGRAMMING GENERALIZED TRAVELING SALESMAN PROBLEM OPTIMIZATION PRECEDENCE CONSTRAINTS BRANCH AND BOUND METHOD HEURISTIC ALGORITHMS OPTIMAL SYSTEMS TRAVELING SALESMAN PROBLEM BRANCH AND BOUNDS CUTTING PATH PROBLEM CUTTING PATHS CUTTING PROBLEMS GENERALIZED TRAVELING SALESMAN PROBLEM OPTIMAL SOLUTIONS OPTIMISATIONS PATH PROBLEMS PRECEDENCE CONSTRAINTS ROUTINGS DYNAMIC PROGRAMMING |
|
| Описание |
The problem of optimal tool routing for CNC sheet cutting machines (referred to as Cutting Path Problem or Tool Path Problem) is considered. The general formulation is used - Generalized Segment Continuous Cutting Problem (GSCCP). The new algorithm developed by the authors to solve generalized traveling salesman problem with precedence constraints (PCGTSP) is shown to effectively tackle this problem. This branch-and-bound algorithm, combined with the use of dynamic programming and a specialized heuristic solver, makes it possible to get optimal solutions for problems of small dimension in a relatively short time compared to known exact algorithms, as well as to find effective lower and upper bounds for the optimal solutions for large-scale problems. The conclusions are illustrated by solving several model examples. © 2022 The Authors. This is an open access article under the CC BY-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/4.0/)
Ministry of Education and Science of the Russian Federation, Minobrnauka, (075 -02-2022-874) The work was performed as part of research conducted in the Ural Mathematical Center with the financial support of the Ministry of Science and Higher Education of the Russian Federation (Agreement number 075 -02-2022-874). |
|
| Дата |
2024-04-22T15:52:58Z
2024-04-22T15:52:58Z 2022 |
|
| Тип |
Conference paper
Conference object (info:eu-repo/semantics/conferenceObject) Published version (info:eu-repo/semantics/publishedVersion) |
|
| Идентификатор |
Petunin, A, Khachay, M, Ukolov, S & Chentsov, P 2022, 'Using PCGTSP Algorithm for Solving Generalized Segment Continuous Cutting Problem', IFAC-PapersOnLine, Том. 55, № 10, стр. 578-583. https://doi.org/10.1016/j.ifacol.2022.09.456
Petunin, A., Khachay, M., Ukolov, S., & Chentsov, P. (2022). Using PCGTSP Algorithm for Solving Generalized Segment Continuous Cutting Problem. IFAC-PapersOnLine, 55(10), 578-583. https://doi.org/10.1016/j.ifacol.2022.09.456 2405-8963 Final All Open Access; Bronze Open Access https://doi.org/10.1016/j.ifacol.2022.09.456 https://doi.org/10.1016/j.ifacol.2022.09.456 http://elar.urfu.ru/handle/10995/132377 10.1016/j.ifacol.2022.09.456 85144544073 881681700098 |
|
| Язык |
en
|
|
| Права |
Open access (info:eu-repo/semantics/openAccess)
|
|
| Формат |
application/pdf
|
|
| Издатель |
Elsevier B.V.
|
|
| Источник |
IFAC-PapersOnLine
IFAC-PapersOnLine |
|