# Evolutionary Algorithms for Optimization Sequence of Cut in the Laser Cutting Path Problem
## 4 Overview of Application of ABRKGA to LCPP
### An Eulerian Heuristic to Generate Improved Individuals for LCPP  
Consider an LCPP context. Examine the provided layout (Figure 6) and note that it can commence from a single point and traverse every edge precisely once without changing the device mode (always cutting). The term traversable describes graphs in which it is possible to begin at a vertex and trace all the edges without lifting the pen off the page or retracing any edge. There are two categories of traversable graphs:  
* A graph is called Eulerian if it possesses a closed trail, known as an Eulerian trail or an Eulerian circuit, which starts and ends at the same vertex while traversing every edge. * A graph with an open trail, where the trail begins and ends at distinct vertices while traversing every edge, is called semi-Eulerian. Alternatively, it can be denoted as having a semi-Eulerian trail. Figure 5: Example of the quality value computed between \(i\) and \(i+1\) indexes of individual vector representation. It is feasible to ascertain whether an undirected graph is Eulerian or semi-Eulerian without the need to identify the trail explicitly: if a graph exhibits precisely two vertices with an odd degree, it is classified as semi-Eulerian (Figure 6a). These two vertices serve as the start and end points of the open semi-Eulerian trail. If a graph consists entirely of even-degree vertices, it is categorized as Eulerian (Figure 6b). The closed Eulerian trail can commence from any vertex within the graph. In this context, we consider the concept, as mentioned earlier, to improve individual fitness, whereas solutions tend to have fewer unnecessary air moves. In [9], the authors construct the initial population with a random order of edges. This fact impacts several air movements. Our idea is to consider four specific cases on the generation of initial solutions:  
1. We assume the input layout is connected and contains all nodes with even degrees (Eulerian graph). Then, the heuristic can find an Eulerian circuit and needs to use one air movement (source to nearest node) and another (nearest node back to origin). In this case, we have the minimum time required to cut all items. **Note**: To return the sequence of edges at the Eulerian circuit, we apply a linear time implementation adapted from [38] with _NetworkX_ (Python library). 2. We assume the input layout is connected and contains precisely two vertices that have odd degrees (semi-Eulerian graph). In this way, the initial population comprises solutions with path routes that necessarily pass through both odd-degree vertices. The idea is that the metaheuristic finds the combination that minimizes the end-cut time in the LCPP, assuming that a good solution must pass through the starting and ending points. 3. We assume the input layout is connected and contains more than two nodes with odd degrees. In this case, the heuristic seeks to transform the graph's vertices that have odd degrees into even degrees, adding new edges between them until only two odd edges remain in the semi-Eulerian graph (2). 4. We consider the possibility that the input layouts present items without contact between them. This situation occurs when the cut needs to maintain a safe area for the edges. In this procedure, edges between odd vertices enter the solution and are counted as displacement. Algorithm 1 shows the pseudocode for applying the heuristic to the graph. First, the edges are divided into two sets with even and odd degrees, then the code checks if the graph is semi-Eulerian. Otherwise, the displacements are added between them until only two even vertices remain.