# Evolutionary Algorithms for Optimization Sequence of Cut in the Laser Cutting Path Problem
## 3 Literature Review
[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]. This mapping allows for using mathematical models to optimize CPD [6; 32]. 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, [PERSON] et al. [25] 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. [PERSON] et al. [33] 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 [PERSON] et al. [33] 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. [PERSON] [34] 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, [PERSON]'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. It is worth noting that mathematical formulations have proven to be impractical for more real-world examples. A practicable technique is using metaheuristics that employ a graph-based representation similar to the traditional CPD problem. However, we incorporate the air and cut speeds as additional considerations.