# Metaheuristics for the Minimum Time Cut Path Problem with Different Cutting and Sliding Speeds
## 2 Literature Review  
As mentioned previously, MTCP problems consider the minimization of the total cutting time to extract the pieces from the input layout, and it is often called cutting path determination (CPD) [18]. CPD aims to determine the sequence of moves for the cutting head necessary to separate all the smaller pieces from the surface (also referred to as the stage in an industrial setting). This section focuses on approaches for CPD problems. For comprehensive surveys on C&P problems, we refer to [13; 19]. [PERSON] and [PERSON] [20] categorized CPD problems according to the flexibility to choose an initial contour entry and whether a piece is only partially cut before the head  
Figure 1: Example of a two-dimensional C&P problem with irregular items and a single open-dimensional surface of fixed width and variable length. This is a \(2|Si|Oo\) problem according to [PERSON] et al.’s taxonomy [4]. device moves to another object. The first category, according to [20], contains problems with _continuous cutting_, i.e., the cut is allowed to start at any point of the perimeter of pieces [21; 22]. In such problems, the entry point should be the same for both entry and departure. The second category is called _endpoint cutting_, which contains problems in which the cut starts and ends at predefined vertices of the polygons [5; 6]. The last category is _intermittent cutting_, in which there are no restrictions on the points that can be used for entry or exit of the cutting [23; 24]. The literature contains several examples of algorithmic approaches for CPD. [PERSON] et al. [25] proposed grouping these methods according to the technique for traversing the vertices of the polygons. Three categories (here presented with examples of studies that employ such an approach) were identified by the authors: the touring polygons problem [26; 27]), the traveling salesman problem (TSP) [28; 29], the generalized TSP [30; 31], and the TSP with neighborhoods [21]. Figure 2 presents a classification for CPD and the degree of generalization for this problem. The generalization level grows considering the flexibility of starting a path at any point of an item's layout. Besides, it is possible to cut only segments of a part, not necessarily starting and ending the cutting contour in the same item. Laser cutting, as the designation suggests, applies a laser origin to cut the material. A benefit of laser cutting is that both the expanse of the cut and the heat-affected areas are tiny. Additionally, it is similar to both flame cutting and plasma cutting [32], and it is essential to highlight that the enclosed area detaches from the raw material after the cut of a complete piece contour. Depending on the supporting grid and air of the laser nozzle, it can shift its position, or if there is no supporting grid, it simply falls through. In both cases, it will be impracticable to continue cutting in this area. The CPD problem aims to plan a path that minimizes the time required to cut all pieces regarding precedence constraints and is described in [PERSON] et al. [17]. Additional objectives include minimizing the cut across contours' path lengths and the effect of heat on the cutting path sequence [33]. A possible additional constraint is the requirement for a predefined cutting sequence for the items, which are to be cut without sliding movements [16]. [PERSON] and [PERSON] [6] tackled the problem of sequencing a torch (flame cutter machine) for cutting regular and irregular parts arranged on a surface. The main objective was to minimize the number of piercings, i.e., small holes made near each piece to improve the cutting process. One of the approaches for CPD problems is the use of linear integer models to determine the sequence of moves that minimizes the overall time required to cut the demand of pieces [34]. [PERSON] et al.