# Metaheuristics for the Minimum Time Cut Path Problem with Different Cutting and Sliding Speeds
## 3 Evolutionary Metaheuristics for MTCP
### A GA-Based Approach
The \(n\)'s first positions represent the cutting order of each edge, and the remaining elements have binary values (0 or 1) expressing the direction of the process. Figure 6a illustrates an input layout. We emphasize that the entire cutting process tends to start from the original system of each device (Source) and return with the movement head at the end (Regress). In this work, we considered the point (0,0), because the machine where we applied the tests follows the same idea. Note that in Figure 6b, the coding process for each individual describes that the input layout has four edges and, therefore, the individuals' representation vector contains eight positions. Moreover, the order (\(i=1,2,3,4\)) and direction (\(i=5,6,7,8\)) determine the plan of the complete cut. Therefore, when treating each element of the representation vector, we applied an offset assuming the shortest distance (Chebyshev) possible for cases in which the target node of one edge \(i\) does not match the origin node of the next \(i+1\). We assumed that 0 represents \"left-to-right\" or \"bottom-to-up,\" in other words, for edge \((u,v)\), we considered the initial point to visit \(u\) and the final point \(v\), and 1 depicts the directions back. Figure 6: Example of an individual representation for input layout. (**a**) illustrates an input layout. (**b**) the coding process for each individual describes that the input layout has four edges and, therefore, the individuals’ representation vector contains eight positions. The initial population was generated by shuffling a list of each cutting edge, while the rest of the positions with values 0s or 1s were drawn randomly under equal probabilities. The fitness of each individual was calculated by adding the time needed to cut, i.e., the time to cut the required edges (\(T_{cut}\)) and the motion of the head from the origin to the initial node of the layout and back from the head to the end of the complete cut (\(t_{offset}\)). It was necessary to consider the speed \(\pi\) (cutting) and the other times \(\mu\) (without cutting) to calculate the value of \(T_{cut}\). Figure 7 illustrates the (\(i\), \(i+1\))-step of the fitness function. Note that (\(i\)) typifies each position of _chrom_, and the two squares represent the required cut edges (\(n\)), in other words, the input layout. Figure 7a illustrates the \(i\)-step to compute the fitness value for each individual. The \(chrom(i)\) is (\(x\),\(y\)) edge and its position in the second part of the chromosome (\(chrom(2n+i)\)) contained value 0. The movement occured from node \(x\) to \(y\) (direction represented by 0), and, in this case, the edge (\(x\),\(y\)) belonged to the set of required cutting edges. Thereby, to compute the time, \(t(i)\) was divided by the Chebyshev distance for (\(x\),\(y\)) to \(\pi\) (cut speed). The next stage, (\(i+1\)-step), supposed that the \(chrom(i+1)\) was the edge (\(z\),\(w\)) and that its direction position (\(chrom(2n+(i+1))\)) had value 1--see Figure 7b. In this condition, to account for the time \(t(i+1)\), we needed to add the displacement time of the cutting device head from node \(y\) to \(z\); for this, we applied the displacement speed (1) with the cutting time of the edge (\(z\),\(w\)), and we used the cutting speed (2). Therefore, Equation (1) formalizes the fitness function. \[fitness(chrom)=\sum_{i=1}^{n}t(chrom(i))+t_{offset} \tag{1}\]  
The method for individual selection applied was \(q\)-Tournament [42]. In this procedure, a group of \(q\) individuals was randomly selected with population replacement. This group became part of a dispute in which the winner was determined according to the best fitness. The crossover operator, in general, recombines aspects of chromosomes and benefits the search for the solution space, directing the evolution process. The method applied to the proposed GA was partially matched crossover (PMX) [43]. The goal is to generate two children by combining pairs of values in a given range of the two parents and exchanging these indexes' values.