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 -