# Metaheuristics for the Minimum Time Cut Path Problem with Different Cutting and Sliding Speeds
## 3 Evolutionary Metaheuristics for MTCP
### A GA-Based Approach  
As mentioned previously, the MTCP with different moving and cutting speeds can be seen as a generalization of the CPD problem [5; 15]. The input data for the MTCP problem is a packing layout, i.e., a set of non-overlapping polygons, which are defined as a set of two-dimensional points and edges, as illustrated in Figure 3. It also includes, in our approach, the moving (\(\mu\)) and cutting speeds (\(\pi\)), which are numerical parameters that vary according to the machinery and the raw material. Let \(d(A,B)\) be the distance between the points \(A\) and \(B\) using a metric that respects the triangle inequality. This study adopted the Chebyshev metric (see Figure 4) since it abstracts aspects that are ignored: deceleration, acceleration, and effects from the cutting process, such as surface bending. The solution for the MTCP problem is a sequence of actions (being either moving or cutting) for the cutting head device. The first step is to build an equivalent undirected graph \(G=(V,E)\) containing the union of all the polygons' vertices and edges in the layout (see Figure 3). We applied the same strategy suggested by [PERSON] et al. (2015). Figure 5 illustrates two possible paths in which cutting moves are represented as black edges, and simple moves are shown in red. The nodes and edges of the resultant graph portray the polygon points in surface space and the lines resulting from the meeting of two faces, respectively. In the final step, the solution is associated with a sequence of (cut or move) instructions processed by the cutting machine until the separation of the entire layout of pieces is finished. Figure 4: Distance metrics: Euclidean (**a**), Manhattan (**b**), and Chebyshev (**c**). The continuous lines represents the layout, and the points in red and blue represent the two points considered in our example of the three distances used. The dashed lines represent the value of the distance between these two points. The Euclidean distance is the usual shortest line that connect both points; the Manhattan distance is the horizontal euclidean distance plus the vertical Euclidean distance between them; and, finally, the Chebyshev distance is the maximum value between horizontal and vertical Euclidean distances. Figure 5: Examples of cut path for the layout in Figure 3. (**a**) A example of possible paths with 11 simple moves. (**b**) A example of possible paths with 14 simple moves. Figure 3: Example of the layout conversion to a set of points in the plane. In addition, this section presents a packing approach that uses a traditional genetic algorithm (GA) to tackle practical instances that exact models cannot address in a reasonable time. GAs are computational algorithms based on the principle of natural selection and survival through the fittest individuals in a similar way to the evolutionary processes in nature [37]. GA-based methods are among the prevalent approaches to cutting and packing problems [38; 39] and cutting path problems [16; 40]. The GA starts by generating a random group of individuals, which are represented by chromosomes or typically binary arrays. These structures are evaluated using a fitness function that measures the candidate solution's quality. A small percentage of the individuals with the highest fitness is copied into the next generation (elitism). The selection operator then chooses two individuals of the current generation to be combined with probability \(txCross\) (crossover rate). Similarly, the mutation operator is applied to the offspring with probability \(txMut\) (mutation rate) [41]. After the new population is generated, the stop condition (e.g., number of generations or genetic convergence) of the algorithm is tested. If it is not satisfied, the process is repeated. In the proposed GA implementation, each individual is encoded by a chromosome represented by a vector \(chrom(i)=(i=1,2,\ldots,n,n+1,\ldots,2n)\), where \(n\) corresponds to the number of edges that must be cut from the input layout.