Placing vector objects on a plane is a common challenge in various industries, such as cutting shapes from paper, metal, wood, and other substrates [1,21]. The optimal arrangement becomes essential when cutting many pieces, as it helps conserve material and handle non-standard plane shapes efficiently. Optimizing the placement of vector objects on a plane is a complex problem due to the vast number of possible configurations and the need to consider multiple parameters for each object. For example, the rotation of objects can significantly influence the overall efficiency of the placement. Furthermore, maintaining sufficient spacing between objects is vital to prevent material damage or other production defects.
This optimization challenge belongs to the category of NP-hard problems, making exact methods impractical for large datasets. Therefore, it is more suitable to use heuristic optimization methods that can provide acceptable solutions within a reasonable time frame. This paper explores three optimization methods: the genetic algorithm, simulated annealing, and simulation modeling. A software application was developed to evaluate the effectiveness of these algorithms by processing simplified input data, which consisted of rectangular objects placed on planes of various sizes. The findings of this research may contribute to the creation of more efficient algorithms for optimization tasks across various industrial and applied fields, enabling resource savings and improving productivity.
Due to its importance and complexity, the problem of finding optimal solutions is actively studied in various scientific and applied fields. A variety of methods developed to tackle this problem, with the most widely used being genetic algorithms, simulated annealing, and simulation modeling. Each of these methods offers unique approaches to finding optimal solutions. Simulated Annealing -is an optimization algorithm miming the physical process of annealing metals [2,[13][14][15]. In this method, the system is "heated" to explore various possibilities and then "cooled" to avoid getting trapped in local minima. This algorithm is effective for optimizing complex spaces with many local optima. It offers several key advantages, including simplicity of implementation and the ability to find optimal solutions for various problems. However, it may require significant time and parameter tuning. Due to its flexibility and ability to find optimal solutions in challenging environments, simulated annealing is widely applied to optimization tasks such as the traveling salesperson problem, scheduling, and task allocation.
Simulation modeling is a powerful tool in applied systems analysis that allows the exploration of complex systems and processes, mainly when decision-making is linked to uncertainty [3,[18][19][20]. Compared to other methods, it enables consideration of many alternatives, improves the quality of management decisions, and forecasts their consequences. However, using simulation modeling in practical management is relatively common due to the complexity of the mathematical framework and the processing of large datasets. The method is based on replicating the functioning process of a system, including its interaction with the external environment, and its model can be represented as functionally implemented blocks, either in software or hardware. Simulation modeling allows include of a wide range of factors in decision-making. It is one of the most powerful tools for analyzing complex systems and processes, particularly under conditions of subjectivity and uncertainty, where reliable analytical tools are required.
Genetic algorithm stands apart from traditional optimization methods and offers several key advantages [4,[15][16][17]. It operates on encoded values and searches within a population, enabling efficient solution space exploration. This method does not require objective function derivatives, employs probabilistic selection rules to avoid getting stuck in local optima, and features inherent parallelism to explore multiple search directions simultaneously. It excels in complex search domains, can manage numerous parameters concurrently, and requires no additional problemspecific information while delivering solutions quickly. However, a significant limitation is the inability to create a universal code for describing functions and optimization criteria due to varying initial conditions. Genetic algorithms are widely applied across scientific and technical fields, including neural network design, production management, economics, medicine, mathematics, etc [5,6,22].
Analyze and compare the effectiveness of simulated annealing, simulation modeling, and the genetic algorithm for efficiently placing vector graphic objects on a plane.
A software application was developed to demonstrate the performance of the algorithms and compare their efficiency in optimizing the placement of vector objects on a given plane. This application was implemented using the Java Swing library [5,7,23] and written in Kotlin. The application's input data includes the board's size and the number of objects to be placed on it. To simplify the problem, only rectangular shapes were used, ranging in size from 1 to 40 cells in height and width, with randomly generated dimensions. The goal of the application is to place the shapes on the plane while occupying the least available space. The shapes are arranged row by row, starting from the top left corner of the plane. The application evaluates the quality of the solution based on the number of empty cells remaining from the bottom-right corner.
In the software application (Figure 1), three planes are displayed simultaneously, each using identical input data but applying different algorithms: simulated annealing, simulation modeling, and the genetic algorithm. The quality of the resulting solution is displayed above each plane. Naturally, the higher the quality score, the better the result.
The simulated annealing method has several variations that differ in the temperature change laws [6,[10][11][12]. Each variation has advantages and disadvantages, such as speed, the guarantee of finding the global minimum, and implementation complexity. A modification of the algorithm called "Very Fast Annealing" was selected for this task. To better understand how the algorithm works in the problem of optimal object placement on a plane, it can be represented as the following sequence of steps:
1. Two values are defined: the initial temperature T0 and the final temperature Tend. 2. A valid initial solution x0 is generated, its quality is measured, and the resulting evaluation is saved as r0. 3. The initial temperature is assigned to the current temperature, T = T0. 4. A new iteration is initiated. In each iteration, two shapes selected by a random number generator are swapped. New shape indices are recalculated if the chosen shapes cannot be placed in the new positions. The swap is performed once the new indices are determined, resulting in a new solution x. 5. The new solution is evaluated using the function r=f(x). If r < r0, the solution has improved, and the new solution is stored as the current one x0=x, r0=r. Otherwise, if r > r0, the new solution is accepted as the current one only with the probability:
∆E = r0 -r. Thus, the probability of accepting a worse solution as the current one decreases as the temperature lowers and the difference between the current energy r and the optimal energy r0. 6. The new temperature is calculated as follows:
where D -is the total number of iterations, k -is the current iteration number, с -is a variable typically used in the general pathfinding problem in a coordinate system to determine the specific temperature at each point. For the optimization problem, we simplify and keep it as a constant с=1. The temperature will decrease according to an exponential law. 7. If T>Tend, proceed to step 4 and continue the search, otherwise, terminate the algorithm.
The flowchart of the algorithm is shown in Figure 2.
Simulation modeling is an approach to research in which the natural system is replaced by a model that accurately describes its functioning [8,9,24]. In the context of optimizing the placement of shapes on a plane, this algorithm can be broken down into the following steps:
1. Select a shape that still needs to be placed. 2. Identify all potential placement options on the plane for the selected shape that satisfy its strict constraints and compile them into the list. 3. Evaluate the quality of each position and place the shape in the most optimal option. The flowchart in Figure 3 illustrates the working principle of the algorithm.
The genetic algorithm is based on natural selection, where better-adapted species are more likely to survive [21,25]. The application of the genetic algorithm for optimizing the placement of shapes on a plane can be described through the following steps:
1. Input the required number of iterations N, which has been determined experimentally. Use the variable count=0 as a counter. 2. etrieve the list of shapes that have not yet been placed. Based on this, generate an initial valid solution x0. Evaluate this solution using the method f(x) and store the result as r0. 3. Randomly change the order of shapes in the list and generate a new valid solution x based on it, then evaluate the solution as r=f(x). 4. If r<r0, save the new solution as the current one x0=x, r0=r. 5. Increment the counter count++. If count equals N, terminate the search.
The sequence of steps for executing the algorithm is shown in the flowchart in Figure 4.
Three different types of input data were used across 20 experiments to compare and evaluate the performance of each algorithm:
1. a 200x200 grid with 80 shapes, 2. a 300x300 grid with 170 shapes, 3. a 400x400 grid with 300 shapes.
The grid size, number of shapes, and number of iterations were selected experimentally to ensure the algorithms could operate with different grid sizes. In contrast, the number of shapes would not exceed the grid's capacity. Additionally, the solution search time was kept consistent across different methods. The experiment results are presented in Table 1, which provides the quality scores of the outcomes for each algorithm. The genetic algorithm consistently delivers the best results across all grid sizes from the presented graphs. The simulated annealing method shows lower efficiency, as it is more difficult to apply to this problem. It requires finding two shapes that can be swapped, which is only sometimes feasible. The simulation modeling method sometimes produces results close to those of the genetic algorithms but lacks sufficient stability.
This paper analyzes applying optimization methods to place vector graphic objects on a plane. To solve this problem, the paper proposes using heuristic optimization methods: genetic algorithms, simulated annealing, and simulation modeling. A software application was developed to compare the effectiveness of these algorithms, using simplified input data in the form of rectangular objects placed on grids of various sizes.
The genetic algorithm showed consistently high simulation results, which are 10-20% better than the method of simulating annealing on all planes. To use the latter, it is necessary to find the shapes that need to be swapped, which is not always possible. It is not advisable to use the simulation modeling method because it shows unstable results that are sometimes close to the genetic algorithm, but can be worse than the annealing simulation method.
The results of this research could contribute to developing more efficient algorithms for optimization tasks in various industrial and applied fields, leading to resource savings and increased productivity. The findings highlight the strong potential of genetic algorithms for optimization tasks involving the placement of graphic objects while also indicating the need for further research to improve these methods and enhance their efficiency under different conditions.
The authors are appreciative of colleagues for their support and appropriate suggestions, which allowed to improve the materials of the article.
The authors have not employed any Generative AI tools.