Research output: Contribution to journal › Article › peer-review
Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - Using PCGTSP Algorithm for Solving Generalized Segment Continuous Cutting Problem
AU - Petunin, Alexander
AU - Khachay, Michael
AU - Ukolov, Stanislav
AU - Chentsov, Pavel
N1 - 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).
PY - 2022/1/1
Y1 - 2022/1/1
N2 - 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.
AB - 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.
UR - https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=tsmetrics&SrcApp=tsm_test&DestApp=WOS_CPL&DestLinkType=FullRecord&KeyUT=000881681700098
UR - http://www.scopus.com/inward/record.url?partnerID=8YFLogxK&scp=85144544073
U2 - 10.1016/j.ifacol.2022.09.456
DO - 10.1016/j.ifacol.2022.09.456
M3 - Article
VL - 55
SP - 578
EP - 583
JO - IFAC-PapersOnLine
JF - IFAC-PapersOnLine
SN - 2405-8963
IS - 10
ER -
ID: 32804666