Researchers frequently aspire to reduce production costs by considering the context of cutting materials. Integrating CAD (computer-aided design) and CAM (computer-aided manufacturing) systems has significantly enhanced the production capacity of device tools for generating NC (numerical control) programs. Consequently, developers have created numerous commercial computer system packages to automate the NC programming process for diverse cutting applications. This advancement has resulted in the extensive adoption of automated devices across manufacturing industries, enabling the precise cutting of various materials such as clothes, papers, glasses, and sheet metals.

For example, cutting clothes involves working with polygon-shaped pieces that must be carefully positioned on a “strip” to minimize waste. This process, known as cutting and packing (C&P), is classified as an optimization problem. It aims to efficiently arrange items within a given space, maintaining the same dimension [1,2]^[1][2]. Employing heuristics and exact techniques for C&P can provide a significant commercial advantage ^[3]. For comprehensive surveys on C&P problems, refer to [4,5]^[4][5].

In the nesting process, which is the initial stage, the objective is to minimize the amount of raw material required. This process can also involve additional constraints specific to the application at hand. Laser cutting, for instance, is a widely used technique for separating sheet metal items, making it one of the primary methods employed once an optimal layout has been determined.

Once a suitable arrangement of polygons (layout) has been found, the next step is to compute the optimal cutting path the cutting device should follow to minimize the processing time. This problem is known as the cutting path determination problem (CPDP) ^[6]. The CPDP focuses on determining the most efficient cutting path for a tool or machine to manufacture a specific part or product.

Cutting can be categorized into two main categories: complete cutting, where each polygon is cut entirely before moving on to the next polygon, and partial cutting, where an item can be cut in portions, allowing for switching between partially cut pieces during the cutting process. The CPDP plays a crucial role in the manufacturing industry, and extensive research has been conducted to develop efficient algorithms and approaches to solve this problem across various manufacturing processes. The aim is to optimize the cutting path and minimize processing time, leading to improved efficiency and productivity in the manufacturing industry.

LCPP is an extension of the well-known traveling salesman problem (TSP), a typical NP-hard problem ^[7]. Consequently, algorithms that aim to provide optimal solutions for LCPP face exponentially increasing computational time as the number of layout pieces grows. Hence, heuristic methods that offer approximate solutions are justified and necessary for solving industrial-scale problems. Metaheuristic methods have gained popularity among researchers as they can discover approximate solutions often close to optimal. On the other hand, approaches based on mathematical formulations have proven impractical for real-world examples, but they can serve as valuable guides for potential methods. 

2. Laser Cutting Path Problem

Researchers have attempted to apply metaheuristics to various processing methods to minimize the inefficient “airtime” during the operation of cutting devices [12]^[8]. GA (genetic algorithm) and BRKGA (biased random-key genetic algorithm) have been used to determine the optimal arrangement of edges for a set of operations located in asymmetrical positions and diverse classes [9,13]^[9][10]. The ant colony optimization (ACO) algorithm has been employed to minimize tool switching time and tool airtime in hole-making operations [14]^[11], as well as to discover the optimal travel path by determining the best ordering for hole-cutting operations [15]^[12]. The literature encompasses various research studies on algorithmic techniques for CPD. Dewil et al. ^[7] presented and classified these methods based on the approach used to traverse the vertices of the polygons. They identified three categories: the touring polygons problem [16^[13][14],17], traveling salesman problem (TSP) [18^[15][16],19], generalized TSP (GTPS) [20^[17][18],21], and TSP with neighborhoods (TSP-N) [22]^[19]. Derwil et al. [10]^[20] classified CPD problems based on the flexibility of selecting an initial contour entry point and whether a piece is partially cut before the cutting head device moves to another object. The first category includes situations with continuous cutting, where the cut can start from any point along the perimeter of the pieces [22,23]^[19][21]. In such cases, the entry point should be the same for both entry and exit. The second category is referred to as endpoint cutting, which pertains to problems where the cut starts and ends at predefined vertices of the polygons [24,25]^[22][23]. The final category is intermittent cutting, which imposes no constraints on the points that can be used to enter or exit the cutting [26,27]^[24][25]. Additional objectives in CPD include minimizing the path length of the cutting trajectory across contours and considering the impact of heat on the cutting path sequence [28]^[26]. Another potential constraint is the requirement for a predefined cutting sequence of items without any sliding movements [29]^[27]. Manber and Israni [24]^[22] addressed the sequencing problem of a torch (flame cutter machine) for cutting regular and irregular parts placed on a surface. Their approach aimed to improve the cutting process by minimizing the number of piercings, which refers to small holes made near each piece. One approach for solving CPD problems is to use linear integer models to determine the optimal sequence of actions that minimizes the overall cutting time for a given set of parts [30]^[28]. Building on this, Dewil et al. [10]^[20] further extended the work presented in [30]^[28] by incorporating additional constraints that reflect real-world conditions. For instance, the relationships between inner and outer contours arise from holes in parts, pieces positioned within holes, or elements nested within enclosed waste areas. Considering the inner–outer contour relationship means an inner contour must be cut entirely before the outer shape is cut. In summary, the cutting sequence requires all pieces of an inner contour to be cut before the final element of its outer contour is cut. Additionally, imposing a set of constraints on primary cuts is feasible. In specific layouts, each regular cut is enclosed by a contour formed by its two surrounding contours. Therefore, it is not permitted for a regular cut to connect both of its surrounding contours. Another set of significant constraints arises from the observation that when a regular cut intersects the contour of two surrounding contours, the disconnected contour can slide, rendering the remaining cutting process infeasible. The laser must move into the cut kerf to achieve precise cutting of the remaining contour objects. This event is not permissible if high part quality is required, and a pre-cut should have been made earlier. Similarly, when cutting a part, a small pre-cut can be created in a neighboring element if the laser head needs to start cutting from that location later on. Dewil et al. ^[7] also consider several non-trivial extensions, such as collisions, bridges, and thermal effects, which further add to the practical complexities of the problem. An alternative approach involves mapping CPD to graph-based problems, such as the capacitated node routing problem (NRP), also known as the vehicle routing or dispatch problem [31]^[29]. This mapping allows for using mathematical models to optimize CPD [6,32]^[6][30]. These techniques handle CPD by manipulating a mathematical formulation based on the NRP problem and a derived model for the traveling salesman problem (TSP). This strategy is particularly effective in obtaining optimal solutions for instances with approximately 2000 edges within a reasonable time frame. The formulation presented in ^[6] achieved optimal results for more significant instances, with up to 712 edges and a maximum of 560 nodes. It is important to note that using mathematical models in practical instances with tens of thousands of edges and nodes has proven impractical. A viable approach is to employ heuristics and metaheuristics to solve graph-based problems equivalent to the original CPD problem. For instance, Moreira et al. [25]^[23] adopted this technique by considering the surface as having an elevation (height) and allowing objects to fall as they are being cut. This approach qualifies for exploring alternative strategies that efficiently handle more extensive and complex instances. Similarly, the empty path problems in laser cutting can be seen as an extension of the traveling salesman problem (TSP), a well-known NP-hard problem. Hajad et al. [33]^[31] propose an approach for addressing the laser cutting path problem, formulated as a generalized traveling salesman problem (GTSP). Their study combines population-based simulated annealing (SA) with adaptive large neighborhood search (ALNS). Recombination techniques, such as swap, reversion, insertion, and removal–insertion, are applied alternately using a fitness proportionate sampling mechanism. In each iteration, the cultural algorithm selection method manages 35% of the population to reduce computational execution time while maintaining solution quality. The results indicate that this method can solve problems of various sizes with a reasonable error percentage compared to the best-known solutions. The study by Hajad et al. [33]^[31] demonstrates a promising approach for tackling the laser cutting path problem, utilizing a combination of population-based simulated annealing and adaptive extensive neighborhood search techniques. Their method effectively solves problems of different scales and provides satisfactory accuracy compared to the best-known solutions. Skinderowicza [34]^[32] introduced a modified version of the ant colony optimization (ACO) algorithm called focused ACO (FACO). This approach incorporates a mechanism to manage potential differences between newly generated and previously selected solutions. The main objective is to create a more focused search procedure that allows for the discovery of improvements while maintaining the quality of the existing solution. A computational study using various traveling salesman problem (TSP) datasets was conducted to evaluate the performance of FACO. The results showed that FACO outperforms state-of-the-art ACO algorithms significantly when solving large TSP instances. FACO could find high-quality solutions within less than an hour using an eight-core commodity CPU. Overall, Skinderowicza’s FACO algorithm presents a promising enhancement to the traditional ACO approach, demonstrating improved performance in solving large-scale TSP instances. The efficient computational performance of FACO makes it a valuable tool for tackling optimization problems with practical significance.