Next Article in Journal
The GM-BP Neural Network Prediction Model for International Competitiveness of Computer Information Service Industry
Next Article in Special Issue
Metaheuristics for a Flow Shop Scheduling Problem with Urgent Jobs and Limited Waiting Times
Previous Article in Journal
An Application of an Unequal-Area Facilities Layout Problem with Fixed-Shape Facilities
Previous Article in Special Issue
Enhanced Hyper-Cube Framework Ant Colony Optimization for Combinatorial Optimization Problems
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Metaheuristics for the Minimum Time Cut Path Problem with Different Cutting and Sliding Speeds

1
Núcleo de Estudo em Machine Learning e Otimização (NEMO), Federal University of Ceará, Russas 62900-000, Brazil
2
Machine Learning & Knowledge Representation (MlKr) Lab, Innopolis University, 420500 Innopolis, Russia
3
Graduate Program in Applied Informatics, University of Fortaleza (UNIFOR), Fortaleza 60811-905, Brazil
*
Author to whom correspondence should be addressed.
Submission received: 8 October 2021 / Revised: 19 October 2021 / Accepted: 20 October 2021 / Published: 23 October 2021
(This article belongs to the Special Issue Metaheuristic Algorithms in Optimization and Applications 2021)

Abstract

:
The problem of efficiently cutting smaller two-dimensional pieces from a larger surface is recurrent in several manufacturing settings. This problem belongs to the domain of cutting and packing (C&P) problems. This study approached a category of C&P problems called the minimum time cut path (MTCP) problem, which aims to identify a sequence of cutting and sliding movements for the head device to minimize manufacturing time. Both cutting and slide speeds (just moving the head) vary according to equipment, despite their relevance in real-world scenarios. This study applied the MTCP problem on the practical scope and presents two metaheuristics for tackling more significant instances that resemble real-world requirements. The experiments presented in this study utilized parameter values from typical laser cutting machines to assess the feasibility of the proposed methods compared to existing commercial software. The results show that metaheuristic-based solutions are competitive when addressing practical problems, achieving increased performance regarding the processing time for 94% of the instances.

1. Introduction

Cutting and packing (C&P) are optimization problems that concern the efficient arrangement of items within a larger space with the same dimensionality. This type of problem appears in several real-world industrial settings, including manufacturing, logistics, and 3D printing [1,2,3]. Therefore, optimization methods for C&P can represent a valuable commercial advantage [4]. This study focused on the minimum time cut path (MTCP) problem, which aims to identify a sequence of instructions (cutting or moving the head device) that minimizes the total cutting time for a packing arrangement or layout.
Prior to the solution of MTCP, a packing procedure is executed to achieve maximal surface area utilization [5,6]. In other words, all the items must be arranged within a surface of fixed width and minimal length, as illustrated in Figure 1. According to Araújo et al.’s taxonomy [4], this is a 2 | S i | O o problem, that is, two-dimensional, with a single input minimization and an open-dimensional volume. Wäscher et al. used the term strip packing problem to refer to such [7]. In addition, the literature contains several constraints that resemble more realistic settings, including the requirement for guillotined cuts [8] or irregular objects [9].
MTCP problems have a primary objective: the minimal time required for cutting the pieces represented by an input layout [5,6]. This data concerns the packing of all the items within a surface that represent the raw material, as illustrated in Figure 1. The position of pieces in the layout stage can be performed by computer-aided design (CAD) systems [10,11] or generated by algorithmic methods [8,12,13,14]. Wäscher et al. used the term strip packing problem to refer to them [7]. In addition, the literature contains several constraints that resemble more realistic settings, including the requirement for guillotined cuts [8] or irregular objects [9].
The central aspect of MTCP, proposed in this study, is the minimal cutting time, which depends on two parameters of manufacturing laser cut machines: the cutting and the moving (or sliding) speed of the head device. The first parameter depends on the machine hardware, the shapes of pieces in the input layout, and the surface material. The second parameter refers to the speed to change the position of the cutting head without cutting. Thus, we tackled a generalization type of the cut determination problem (CPD) [15] adopting the above-mentioned restrictions differently from the studies developed by Lee et al. [16] and Derwil et al. [17], respectively.
From an optimization perspective, a solution obtained to an MTCP problem is a path through the layout area considering the equipment cutting and sliding moves and the resultant manufacturing cut time. This study tackled the minimum time cut path (MTCP) problem with different cutting and sliding speeds. For simplicity of notation, the remainder of this article will refer to this particular problem simply as MTCP.
This study presented two evolutionary metaheuristic-based approaches to tackle larger instances that resemble real-world scenarios. The metaheuristics used in the conducted experiments are a standard genetic algorithm (GA) and a biased random-key genetic algorithm (BRKGA). The experiments used an extensive set of instances from the literature and allowed one to gain valuable insights into the algorithms and their performance compared to specialized commercial software.
The remainder of this article is organized as follows. Section 2 presents the most common algorithmic approaches to MTCP problems and shows the definition and terminology for MTCP. Next, Section 3 introduces two evolutionary algorithms for the MTCP problem. Section 4 presents the results of the computational experiments using an extensive set of instances. Section 5 concludes by discussing the performance of the used algorithms and future works to tackle MTCP.

2. Literature Review

As mentioned previously, MTCP problems consider the minimization of the total cutting time to extract the pieces from the input layout, and it is often called cutting path determination (CPD) [18]. CPD aims to determine the sequence of moves for the cutting head necessary to separate all the smaller pieces from the surface (also referred to as the stage in an industrial setting). This section focuses on approaches for CPD problems. For comprehensive surveys on C&P problems, we refer to [13,19].
Hoeft and Palekar [20] categorized CPD problems according to the flexibility to choose an initial contour entry and whether a piece is only partially cut before the head device moves to another object. The first category, according to [20], contains problems with continuous cutting, i.e., the cut is allowed to start at any point of the perimeter of pieces [21,22]. In such problems, the entry point should be the same for both entry and departure. The second category is called endpoint cutting, which contains problems in which the cut starts and ends at predefined vertices of the polygons [5,6]. The last category is intermittent cutting, in which there are no restrictions on the points that can be used for entry or exit of the cutting [23,24].
The literature contains several examples of algorithmic approaches for CPD. Dewil et al. [25] proposed grouping these methods according to the technique for traversing the vertices of the polygons. Three categories (here presented with examples of studies that employ such an approach) were identified by the authors: the touring polygons problem [26,27]), the traveling salesman problem (TSP) [28,29], the generalized TSP [30,31], and the TSP with neighborhoods [21]. Figure 2 presents a classification for CPD and the degree of generalization for this problem. The generalization level grows considering the flexibility of starting a path at any point of an item’s layout. Besides, it is possible to cut only segments of a part, not necessarily starting and ending the cutting contour in the same item.
Laser cutting, as the designation suggests, applies a laser origin to cut the material. A benefit of laser cutting is that both the expanse of the cut and the heat-affected areas are tiny. Additionally, it is similar to both flame cutting and plasma cutting [32], and it is essential to highlight that the enclosed area detaches from the raw material after the cut of a complete piece contour. Depending on the supporting grid and air of the laser nozzle, it can shift its position, or if there is no supporting grid, it simply falls through. In both cases, it will be impracticable to continue cutting in this area.
The CPD problem aims to plan a path that minimizes the time required to cut all pieces regarding precedence constraints and is described in Dewil et al. [17].
Additional objectives include minimizing the cut across contours’ path lengths and the effect of heat on the cutting path sequence [33]. A possible additional constraint is the requirement for a predefined cutting sequence for the items, which are to be cut without sliding movements [16]. Manber and Israni [6] tackled the problem of sequencing a torch (flame cutter machine) for cutting regular and irregular parts arranged on a surface. The main objective was to minimize the number of piercings, i.e., small holes made near each piece to improve the cutting process.
One of the approaches for CPD problems is the use of linear integer models to determine the sequence of moves that minimizes the overall time required to cut the demand of pieces [34].
Dewil et al. [17] extended [34] by assuming an additional set of constraints that resemble real-world requirements, for example, including inner–outer contours relations, resulting from holes in parts, parts allocated in holes, or elements nested in enclosed waste areas. The consideration of the inner–outer contour means that an inner contour needs to be completely cut before the outer shape is cut. In summary, all pieces of an inner contour necessitate to be cut before the end element of its outer contour is cut. Additionally, it is possible to suggest a set of constraints about basic cuts. In some layouts, each typical cut is enveloped by a contour formed of both its two contours. Hence, no typical cut is permitted to connect both of its contours.
Another kit of priority constraints appears from the evidence that when one cut the contour of two contours in common cut with one another, the separated contour can slide, making the rest of the cut process unfeasible. To correctly cut the items of the residual contour, the laser has to move into the cut kerf. It is forbidden if a high part quality is required, and a pre-cut should have been placed earlier. When cutting a part, a tiny pre-cut can be made in a nearby element if the laser head has to begin cutting from this place later on. Several non-trivial practical extensions (additional practicalities) like collisions, bridges, and thermal effects also are present in Dewil et al. [25].
A similar approach consists of reducing CPD to graph-based problems such as the capacitated node routing problem (NRP), also known as the vehicle routing or dispatch problem [35], and then optimized through mathematical models [15,36]. These techniques address CPD by utilizing a mathematical formulation based on the NRP problem and a derived model for the traveling salesman problem (TSP). This approach has been demonstrated to be suitable for achieving optimal solutions, for instance, containing approximately 2000 edges in a reasonable time. The formulation in [15] achieved optimal results for larger instances with up to 712 edges and a maximum of 560 nodes.
It is noteworthy that the studies that use mathematical models have been impractical for more realistic instances with tens of thousands of edges and nodes. A strategy to mitigate possible limitations is using heuristics and metaheuristics for solving graph-based problems, which are equivalent to the original CPD problem. For example, Moreira et al. [5] employed this approach, also considering that the surface is at an elevation (height) and that items fall as they are cut. Despite the wide variety of CPD problems in the literature, problems with different cutting and sliding speeds have not been formally described to the best of the authors’ knowledge.

3. Evolutionary Metaheuristics for MTCP

This section introduces the steps for building two evolutionary-based approaches for tackling MTCP, considering different moving and cutting speeds: a genetic algorithm (GA) and a biased random-key genetic algorithm (BRKGA).

3.1. 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 ( μ ) and cutting speeds ( π ), 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 Silva et al. [15]. 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.
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 t x C r o s s (crossover rate). Similarly, the mutation operator is applied to the offspring with probability t x M u t (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 c h r o m ( i ) = ( i = 1 , 2 , , n , n + 1 , , 2 n ) , where n corresponds to the number of edges that must be cut from the input layout. 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.
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 c u t ) 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 o f f s e t s ). It was necessary to consider the speed π (cutting) and the other times μ (without cutting) to calculate the value of T c u t . Figure 7 illustrates the (i, i + 1 )-step of the fitness function. Note that (i) typifies each position of c h r o m , 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 c h r o m ( i ) is (x,y) edge and its position in the second part of the chromosome ( c h r o m ( 2 n + 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 π (cut speed). The next stage, ( i + 1 -step), supposed that the c h r o m ( i + 1 ) was the edge (z,w) and that its direction position ( c h r o m ( 2 n + ( 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.
f i t n e s s ( c h r o m ) = i = 1 n t ( c h r o m ( i ) ) + t o f f s e t s
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. This strategy was applied only to the n’s first elements of the vector.
On the other hand, the remaining positions of the representation were recombined through the two-point crossover. This adaptation facilitates the manipulation of each part of the applied model’s scopes, sequencing edges, and direction choices, respectively. The mutation operator was verified to ensure an expansive scan of the state space and to contain the premature convergence (optimal locations) of the GA. Similar to the idea conceived for the crossover, we applied the Shuffle Indexes method to the first part of the chromosome and the flip bit mutation strategy for the directions portion.
Finally, we detailed all values for GA parameters like population size, crossover and mutation rate, stop criteria, and others in the results Section 4.

3.2. A BRKGA-Based Approach

Genetic algorithms with random keys (RKGA) were introduced by [44] to deal with combinatorial optimization problems involving representation adapted to sequencing. In an RKGA, each chromosome is represented as a vector of real numbers in the range [ 0 , 1 [ n , where n is the problem’s dimension. A decoder receives a chromosome and maps it into a feasible problem solution. Resende [45] proposed the Biased Random-Key Genetic Algorithm (BRKGA), in which the individuals are selected in the recombination process, and it also contains the highlighted function of the probability of inheriting information from the parents ( p a ).
This study used the BRKGA due to its tolerance to several optimization problems, assuming that two elements of its framework must be represented [46]: a compatible decoder, featured in this section, and a representative fitness function, trying to minimize Equation (1), for this problem. Figure 8 illustrates the BRKGA heuristic and its parameters: the size of the population (P), the proportion of the population in the elite (Pe), and the number of new random individuals that will be included in the new population (Pm).
An important characteristic of BRKGA is the parameterized uniform crossover [47]. In this crossover type, one of the parents is extracted from the elite group, while the second parent is extracted from the non-elite set. This enables the BRKGA heuristic to mitigate a premature genetic convergence. On the other hand, it requires the calibration of the p a parameter that can affect the overall performance. This peculiar parameter of the BRKGA ensures that the child individual inherits more characteristics of an elite parent. One parent is always selected (with replacement) from the elite solutions group, and the probability that the child inherits the key of the elite parent >0.5. According to Resende [45], this is a differentiating factor in favor of faster convergence when compared to RKGA [44].
Each gene in the chromosome representation for individuals in the BRKGA contains a real value in the range [0.1). For example, Figure 9 illustrates how random keys represent alleles for each chromosome. In our proposed strategy, the value of each gene c h r o m ( i ) was used by the decoder to determine the order and the cuts and movements’ directions. Therefore, the decoder operated as follows: first, the initial n genes for each chromosome are sorted upwards, corresponding to the cut order. Then, for each of the remaining genes ( n + 1 , , 2 n ), the following function is used to determine the cuts’ direction.
f ( c h r o m ( i ) ) = 0 , if c h r o m ( i ) < 0.5 1 , otherwise
Figure 9 presents the encoding process from random keys to process an individual. Note that this process depends on problem specifications. For this reason, we illustrated this process separately from Figure 8. The input module saves the SVG file (layout) information like the edges for a cut. The dimension of the array depends on such a value. It is noteworthy that the part of the vector representing the directions does not participate in the keys’ ordering, being decoded only by the function f(chrom). In this way, sorting random keys (ascending order of keys) results in the sequencing of edges visits. After that, the decoder presents a solution containing a sequence of movements for the input layout and the fitness function defined by Equation (1), which can calculate the time required for each individual.
In this context, we use Section 4 to present our GA and BRKGA approaches’ parameters and the cutting ( π ) and moving speeds ( μ ), inherent in MTCP, for all computational tests applied.

4. Results and Discussion

The computational experiments were conducted in an Intel Xeon 3.80 GHz machine with eight cores, 8GB RAM, and an Ubuntu 18.08 operational system. The GA and the BRKGA algorithm were implemented in Python 3.7. As input data, all dataset instances were layouts extracted through the algorithm applied by Amaro et al. [12]. The result was a file in SVG format. The following sub-sections present the characteristics of the benchmark instances (Section 4.1), a comparison between GA and BRKGA (Section 4.2), and a comparison between BRKGA (best approach considered) and a commercial laser cut software in practical situations (Section 4.3).The reader can access the complete information of the data used and constructed in this section through the link presented in the Data Availability Statement.

4.1. Instances

A set of 50 problem instances was used to evaluate the presented approaches. These instances can be categorized according to the possible presence of empty space between the pieces in the input layout, being either connected (C) (Figure A1 and Figure A2 in the Appendix A.1) or separated (S) (Figure A3, Figure A4 and Figure A5 in the Appendix A.2). The presence of space between items in the latter group aimed to enable the use of support, which is quite common in some material cutting applications. The dataset was generated by the nesting approach presented in [12].
Several hyper-parameter settings (27) were tested for the GA and the BRKGA heuristics, which was executed ten times for each instance. Table 1 presents the instances, the number of vertices, both the number of edges (original and adapted layouts with the joint of the edges), and the number of polygons.
Some instances present a different number of vertices and edges due to the application of the join procedure and split edges in the original input layout. It is necessary to highlight that joining segments are treated as particular cases of splitting edges. Figure 10 illustrates the input data format (SVG file) and the output obtained by this methodology. The algorithm of preprocessing data, extracted by [15], was used to convert the input file into a graph before addressing the MTCP through the proposed adapted metaheuristic approaches. Then, the sequence of cuts and moves wasvalidated (output).

4.2. GA and BRKGA Hyper-Parameter Configuration

GA and BRKGA hyper-parameter configurations used in the experiments were selected after preliminary tests: population of 10,000, 5000, and 1000 individuals; crossover of 70%, 75%, and 80%; and mutation of 10%, 15%, and 20%. For the elite group in BRKGA, values of 30%, 20%, and 10%; mutated population of 10%, 15%, and 20%; Pa of 70%. The stopping criteria wre met when there was no improvement in the best solution found for 100 generations or when the execution time exceeded 300 s.
Table A1 (see Appendix B.1) and Table A2 (see Appendix B.2) summarize the computational results. For every connect and separate instance, the results include the objective function value (FO), the elapsed time for the best execution, the average objective values, and the elapsed computational time. It is possible to observe that the BRKGA is more suitable than the standard GA for addressing the tested instances. Every hyper-parameter setting was tested for both GA and BRKGA, and each type of layout, connected (C) and separated (S).
Figure 11 presents the number of times that a BRKGA hyper-parameter setting achieved the best solution found. For connected layouts (C), the best GA configuration addressing relation-1 (instances/executions) was obtained using the following hyper-parameters after 49 times: P = 10,000, t x C r o s s = 0.8 , and t x M u t = 0.1 . In the separated instances group (S), the best solution was obtained after 20 executions, and the configuration was the following: P = 5000, t x C r o s s = 0.75 , and t x M u t = 0.2 .
Figure 12 presents the minimum time required to reach the best value in each execution. It is possible to observe that, for each instance, the objective function value was above the average best. A consideration of the results exposes that it is not suitable to define the best configuration for relation-1. While it achieves the best result in all executions for some instances, it led to the below-average value for the remaining.
Next, we defined relation-2 considering the number of instances each configuration achieved the best FO value for at least one execution. Figure 13 presents the best hyper-parameter configuration according to the highest average value for connected and separate layouts. Therefore, the best parameters to connected instances were P = 5000, Pe = 0.30, Pm = 0.1; P = 10,000, Pe = 0.10, Pm = 0.1; P = 10,000, Pe = 0.10, and Pm = 0.2. For separate instances, the best hyper-parameters were P = 10,000, Pe = 0.20, and Pm = 0.2. Figure 14 presents the progression of the BRKGA optimal value at each generation.
Lastly, we defined relation-3 setting the configuration using each parameter option that occurred more frequently in the best solutions (modal value): P = 10,000, Pe = 0.3, and Pm = 0.10. A comparison between vertex numbers (V) and population size (P) exposed that the configuration that hyper-parameter settings with population equal to 10,000 failed to achieve the best results for instances with V 70 . For example, for the instances inst_01_26pol (V = 210) and trousers (V = 350), the value of P in the configuration that presented the best solution was 1000 for both cases. Therefore, the following hyper-parameter was selected for further experiments: P = 5000, Pe = 0.30, and Pm = 0.1. The progression of the BRKGA is shown in Figure 15 and Table A3 (see Appendix C.1) and Table A4 (see Appendix C.2). Since the configuration failed to reach the average result for both connected and separate instances, it is possible to affirm that increasing the timeout would enable better solutions.

4.3. Comparing BRKGA and a Commercial Laser Cut Machine Software

This section presents a practical case from industry comparing BRKGA using the best hyper-parameter setting (see Section 4.2) and commercial software for laser cutting machines. The characteristics of the device are shown as follows. PRISMA machine (https://www.automatisa.com.br/en/ (accessed on 8 October 2021)) produced Automatisa Laser Solutions, was 60 W, and had a maximum working area of 900 × 600 mm. The speeds π (cut) and μ (displacement) were 16.67 mm/s and 400 mm/s, respectively. Then, BRKGA was executed for all the instances, and the generated outputs (sequence of edges for cutting) were exported as SVG files. After, a similar process was repeated using the commercial software. Finally, we used the proposed instances and assigned them as input for execution to compute the machine’s software (LaserCut).
Table A5 (see Appendix D.1) presents a comparison between the introduced BRKGA approach with parameters P = 5000, Pe = 0.30, and Pm = 0.1, and LaserCut. For 50 instances analyzed, BRKGA achieved a gained time in 47 s, i.e., an improvement of 94%. It is noteworthy that for instances with separated items, the improvement was inferior to those for instances with connected items.
It is possible to notice that the BRKGA approach achieved a time of 256.56 s for the connected group and 258.76 s for the separated group—see Table A1 and Table A2. The respective settings applied to these results were: P = 1000, Pe = 0.30, and Pm = 0.1 and P = 1000, Pe = 0.30, and Pm = 0.15. It is noteworthy that, for several instances, BRKGA performed better than LaserCut. Interestingly, the results indicate an apparent relationship between the population size and the number of vertices (Table 1) in the input layout.

5. Conclusions

This study introduced a case of the MTCP problem, which more closely resembles real-world scenarios by distinguishing cutting and moving speeds. The cutting and the sliding rates for the equipment are essential parameters and, despite their relevance in real-world machinery, such features are often ignored in the literature. This study presented the minimum time cut path problem, including two presented evolutionary approaches, i.e., the genetic algorithm (GA) and biased random-key genetic algorithm (BRKGA) methods, which are suitable for addressing larger instances.
Computational tests presented extensive hyper-parameter tuning using a large set of instances extracted from the literature, which can be leveraged in future research. For all instances analyzed, the proposed methodology achieved a gain in time of 47 s and an improvement in 94% of the tests performed.
However, we noticed a decrease in performance when the input layouts had a relatively large number of vertices. This fact indicates a correlation between this parameter and the population size. Moreover, a suitable approach would consist of splitting the layout into parts, considering cutoff distances, so that the individual’s representation can also be segmented. Hence, we would build N subgroups of edges, and the evaluation would be limited in finding the best sequence for each N. Lastly, we would add the endpoint times to the beginning of all predefined N by finding a feasible solution and enabling parallel processing.
Future work will investigate how clustering methods such as K-Means can be integrated into the current approach to find feasible and quality solutions when addressing instances with a more significant number of parts positioned in a layout. This strategy will be integrated into the mathematical model. Another research direction is the investigation of an alternative representation for candidate solutions in the BRKGA algorithm. In the recent literature, there have been examples of methodology that allow the use of a purely discrete representation and the possibility of combining the discrete solutions using vector-like operations, similar to what is usually done for continuous solutions as in the random-key encoding [48,49,50].

Author Contributions

Conceptualization, B.A.J.; data curation, M.C.S. and G.N.d.C.; methodology, L.J.P.d.A., B.A.J. and M.C.S.; software, G.N.d.C.; validation, B.A.J.; writing—original draft, L.J.P.d.A., B.A.J. and P.R.P.; writing—review & editing, L.J.P.d.A. and B.A.J. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Publicly available datasets were analyzed in this study. This data can be found here: https://github.com/GUIKAR741/metaheuristics-minimun-path (accessed on 8 October 2021). The folder “algorithms” includes the codes of the two approaches developed for this study. The folder “instances” holds all input SVG layouts. The folder “results” presents the numerical experimental data. The folder “result-evolution process” contains the evolution graph of the best solution (Y) with the number of generations (X), and the folder “results-final draw” shows the ten images of the path sequence found (each instance × execution), just for the BRKGA approach with hyper-parameters [P = 5000, Pe = 0.30, and Pm = 0.1].

Conflicts of Interest

The authors declare no conflict of interest.

Abbreviations

The following abbreviations are used in this manuscript:
BRKGABiased random-key genetic algorithm
CCPContinuous cutting problem
C&PCutting and packing
CPDCut path determination
ECPEndpoint cutting problem
GAGenetic algorithm
GTSPGeneralized traveling salesman problem
ICPIntermittent cutting problem
MTCPMinimum time cut path
NRPNode routing problem
SVGScalable vector graphics
TPPTouring polygons problem
TSPTraveling salesman problem
TSP-NTraveling salesman problem with neighborhoods

Appendix A

Appendix A.1

Figure A1. First batch of instances with connected items.
Figure A1. First batch of instances with connected items.
Algorithms 14 00305 g0a1
Figure A2. Second batch of instances with connected items.
Figure A2. Second batch of instances with connected items.
Algorithms 14 00305 g0a2

Appendix A.2

Figure A3. First batch of instances with separated items.
Figure A3. First batch of instances with separated items.
Algorithms 14 00305 g0a3
Figure A4. Second batch of instances with separated items.
Figure A4. Second batch of instances with separated items.
Algorithms 14 00305 g0a4
Figure A5. Third batch of instances with separated items.
Figure A5. Third batch of instances with separated items.
Algorithms 14 00305 g0a5

Appendix B

Appendix B.1

Table A1. GA and BRKGA configurations for the connected instances (C).
Table A1. GA and BRKGA configurations for the connected instances (C).
InstancesGABRKGA
FOTIMEFOTIME
albanoBest106.38300 s104.62300 s
Average114.5300 s110.94300 s
blaz1Best154.88300 s154.22294 s
Average158.98300 s155.2300 s
blaz2Best275.27189 s269.72300 s
Average290.93300 s275.81300 s
blaz3Best428.38300 s419.32300 s
Average454.98300 s435.3472 s
dighe1Best70.47300 s70.53124 s
Average71.0925 s70.8719 s
dighe2Best53.87205 s53.87100 s
Average54.4234 s54.0315 s
fuBest23.86300 s23.82164 s
Average24.2361 s23.9826 s
inst_01_10polBest126.97131 s126.97158 s
Average127.47188 s127.3414 s
inst_01_16polBest76.73211 s76.58300 s
Average78.0826 s77.4820 s
inst_01_2polBest33.114 s33.114 s
Average33.1120 s33.1123 s
inst_01_3polBest39.245 s39.244 s
Average39.2425 s39.2427 s
inst_01_4polBest57.365 s57.366 s
Average57.3632 s57.3634 s
inst_01_5polBest69.618 s69.6141 s
Average69.737 s69.6186 s
inst_01_6polBest81.73139 s81.73103 s
Average81.8562 s81.8548 s
inst_01_7polBest96.8511 s96.859 s
Average96.9869 s97.238 s
inst_01_8polBest105.72229 s105.72127 s
Average106.10289 s106.1010 s
inst_01_9polBest123.97210 s123.97136 s
Average124.4785 s124.4710 s
inst_01_26pol_holeBest142.79300 s137.50300 s
Average162.66300 s155.83300 s
rco1Best140.52300 s140.17248 s
Average143.1132 s141.01233 s
rco2Best274.43264 s270.16300 s
Average288.92300 s275.06231 s
rco3Best403.65300 s393.92300 s
Average429.06300 s407.8564 s
shapes2Best218.02210 s214.73300 s
Average228.10300 s218.9852 s
shapes4Best425.87300 s419.83300 s
Average461.70300 s439.87300 s
spfc_instanceBest144.94300 s143.53201 s
Average150.18300 s145.56183 s
trousersBest271.78300 s256.56300 s
Average301.36300 s297.85300 s

Appendix B.2

Table A2. GA and BRKGA configurations for the separated instances (S).
Table A2. GA and BRKGA configurations for the separated instances (S).
InstancesGABRKGA
FOTIMEFOTIME
albanoBest109.83300 s107.23300 s
Average119.43300 s113.52300 s
blaz1Best162.57279 s161.86300 s
Average166.06300 s163.13300 s
blaz2Best296.30300 s291.57300 s
Average309.95300 s295.52243 s
blaz3Best499.18300 s489.88300 s
Average531.40300 s506.3877 s
dighe1Best96.53300 s96.03300 s
Average98.6537s97.4735s
dighe2Best78.9190 s78.47300 s
Average80.1856 s79.6523 s
fuBest28.04297 s27.95295 s
Average28.69300 s28.0923 s
inst_01_10polBest193.18300 s192.61149 s
Average196.74300 s194.4727 s
inst_01_16polBest173.04300 s171.16300 s
Average180.8683 s176.6968 s
inst_01_2polBest36.044 s36.044 s
Average36.0421 s36.0425 s
inst_01_3polBest48.096 s48.0933 s
Average48.0929 s48.0933 s
inst_01_4polBest72.1344 s72.1390 s
Average72.337 s72.387 s
inst_01_5polBest90.1360 s90.1356 s
Average90.3813 s90.739 s
inst_01_6polBest114.2193 s114.2151 s
Average114.6578 s114.6272 s
inst_01_7polBest138.31250 s138.31180 s
Average139.2325 s139.5912 s
inst_01_8polBest156.49264 s156.44200 s
Average157.74272 s157.8121 s
inst_01_9polBest186.61300 s186.41273 s
Average189.3627 s187.8316 s
inst_01_26pol_holeBest198.97300 s192.89295 s
Average216.82300 s205.02300 s
rco1Best162.74300 s162.59219 s
Average164.9925 s163.12191 s
rco2Best322.09300 s319.31300 s
Average334.81300 s321.63300 s
rco3Best489.66175 s480.36300 s
Average515.63300 s492.8159 s
shapes2Best229.47222 s227.79300 s
Average238.3152 s230.8542 s
shapes4Best455.2300 s447.99300 s
Average481.66152 s461.88300 s
spfc_instanceBest148.79300 s147.33300 s
Average153.36300 s149.28157 s
trousersBest303.51300 s285.76300 s
Average338.13300 s330.06300 s

Appendix C

Appendix C.1

Table A3. Connected instances (C) for considered configurations. Relation 1: P = 10,000; Pe = 30%; Pm = 10%. Relation 2: P = 10,000; Pe = 20%; Pm = 20%. Relation 3: P = 5000; Pe = 30%; Pm = 10%.
Table A3. Connected instances (C) for considered configurations. Relation 1: P = 10,000; Pe = 30%; Pm = 10%. Relation 2: P = 10,000; Pe = 20%; Pm = 20%. Relation 3: P = 5000; Pe = 30%; Pm = 10%.
InstancesRelation 1Relation 2Relation 3
FOTIMEFOTIMEFOTIME
albanoBest116.92300 s116.62300 s108,41300 s
Average117.12300 s116.92300111.41300 s
blaz1Best154.29300 s154.29300 s154.64300 s
Average154.71300 s154.74277 s154.71141 s
blaz2Best280.23300 s275.95300 s269.8300 s
Average281.7300 s277.85300 s270.91300 s
blaz3Best457.75300 s450.12300 s426.21300 s
Average460.13300 s453.97300 s428.21300 s
dighe1Best70.54281 s70.53269 s70.53124 s
Average70.73277 s70.69300 s70.69128 s
dighe2Best53.88222 s53.90202 s53.9092 s
Average53.96191 s54186 s5493 s
fuBest23.84300 s23.83300 s23.82164 s
Average23.88300 s23.90300 s23.91168 s
instance_01_10polBest126.97202 s126.97204 s126.9785 s
Average127.22175 s127.09183 s127.2290 s
instance_01_16polBest76.66300 s76.66279 s76.73135 s
Average76.81300 s76.73294 s76.88130 s
instance_01_2polBest33.1148 s33.1150 s33.1123 s
Average33.1148 s33.1150 s33.1123 s
instance_01_3polBest39.2455 s39.2457 s39.2425 s
Average39.2457 s39.2458 s39.2426 s
instance_01_4polBest57.3669 s57.3669 s57.3632 s
Average57.3672 s57.3672 s57.3634 s
instance_01_5polBest69.6186 s69.6184 s69.6140 s
Average69.6191 s69.6190 s69.6140 s
instance_01_6polBest81.73105 s81.73102 s81.7345 s
Average81.73107 s81.73108 s81.7352 s
instance_01_7polBest96.85156 s96.85165 s96.8584 s
Average96.98152 s96.98148 s96.98152 s
instance_01_8polBest105.72138 s105.72140 s105.7260 s
Average105.85148 s105.72142 s105.8568 s
instance_01_9polBest123.97165 s123.97249 s123.9770 s
Average124.10173 s124.10175 s124.1074 s
instance_artificial_01_26pol_holeBest168.32300 s167.53300 s157.02300 s
Average169.03300 s168.31300 s165.78300 s
rco1Best140.17248 s140.66251 s140.52126 s
Average140.59264 s140.94263 s140.73113 s
rco2Best276.67300 s274.08300 s270.86300 s
Average278.63300 s274.85300 s271.63300 s
rco3Best421.50300 s417.93300 s395.32300 s
Average427.17300 s420.59300 s398.33300 s
shapes2Best216.77300 s215.17300 s215.27274 s
Average218.61300 s216.53300 s216.40281 s
shapes4Best467.54300 s454.41300 s429.51300 s
Average469.71300 s464.67300 s432.10300 s
spfc_instanceBest143.90300 s143.63300 s143.69244 s
Average144.32300 s144.17300 s144.16271 s
trousersBest307.26300 s308.34300 s307,56300 s
Average309.44300 s309.46300 s308.75300 s

Appendix C.2

Table A4. Separated instances (S) for considered configurations. Relation 1: P = 10,000; Pe = 30%; Pm = 10%. Relation 2: P = 10,000; Pe = 20%; Pm = 20%. Relation 3: P = 5000; Pe = 30%; Pm = 10%.
Table A4. Separated instances (S) for considered configurations. Relation 1: P = 10,000; Pe = 30%; Pm = 10%. Relation 2: P = 10,000; Pe = 20%; Pm = 20%. Relation 3: P = 5000; Pe = 30%; Pm = 10%.
InstancesRelation 1Relation 2Relation 3
FOTIMEFOTIMEFOTIME
albanoBest121.43300 s121.23300 s111.91300 s
Average122.29300 s122.13300 s115.86300 s
blaz1Best162.19300 s161.86300 s162.31171 s
Average162.64300 s162.66300 s162.80173 s
blaz2Best297.44300 s293.96300 s291.57300 s
Average299.09300 s295.32300 s292.68300 s
blaz3Best528.67300 s522.09300 s492.80300 s
Average532.83300 s525.17300 s496.80300 s
dighe1Best96.03300 s96.25300 s96.21194 s
Average96.22300 s96.45300 s96.30202 s
dighe2Best78.47300 s78.78300 s78.64152 s
Average78.92300 s78.91300 s79.07159 s
fuBest27.96300 s27.97248 s28.03151 s
Average28.03291 s28.04263 s28.03151 s
instance_01_10polBest192.64298 s192.83260 s192.79129 s
Average193.07300 s193.48269 s193.16138 s
instance_01_16polBest182.66300 s181.72300 s173.45300 s
Average183.25300 s182.56300 s174.99300 s
instance_01_2polBest36.0449 s36.0452 s36.0423 s
Average36.0450 s36.0450 s36.0423 s
instance_01_3polBest48.0968 s48.0971 s48.0932 s
Average48.0969 s48.0971 s48.0933 s
instance_01_4polBest72.13104 s72.1396 s72.1346 s
Average72.13105 s72.1396 s72.1347 s
instance_01_5polBest90.13135 s90.13122 s90.1353 s
Average90.15119 s90.18118 s90.1856 s
instance_01_6polBest114.37158 s114.20156 s114.3772 s
Average114.47146 s114.37140 s114.4769 s
instance_01_7polBest138.39184 s138.39186 s138.3982 s
Average138,55172 s138.55179 s138.6095 s
instance_01_8polBest156.49218 s156.54224 s156.49121 s
Average156.69223 s156.66244 s156.66137 s
instance_01_9polBest186.41273 s186.66248 s186.78118 s
Average186.88250 s187.16236 s187.18103 s
instance_artificial_01_26pol_holeBest218.87300 s219300 s218.27300 s
Average219.71300 s219.55300 s219.12300 s
rco1Best162.96276 s162.63221 s162.71111 s
Average163.33232 s163.12249 s163.21113 s
rco2Best321.37300 s317.31300 s317.60273 s
Average322.51300 s318.73300 s318.79265 s
rco3Best507.25300 s492.88300 s480.36300 s
Average509.64300 s500.92300 s482.03300 s
shapes2Best228.83300 s227.79300 s227.93243 s
Average229.98300 s228.18300 s228.57267 s
shapes4Best478.50300 s475.20300 s454.27300 s
Average479.27300 s477.46300 s455.44300 s
spfc_instanceBest147.33300 s147.38300 s148.06180 s
Average148.10300 s148.09300 s148.36202 s
trousersBest347.41300 s346.45300 s345.94300 s
Average348.69300 s347.65300 s346.61300 s

Appendix D

Appendix D.1

Table A5. BRKGA X LaserCut Software.
Table A5. BRKGA X LaserCut Software.
InstancesBRKGALASERCUTGAIN
(C)(S)(C)(S)(C)(S)
albano111.41115.86118.66118.71+ftg7.25+2.85
blaz1154.71162.80177.51178.05+22.8+15.25
blaz2270.91292.68357.40323.54+86.49+30.86
blaz3428.21496.80537.55538.97+109.34+42.17
dighe170.6996.30113.83114.51+43.14+18.21
dighe25479.0788.2288.58+34.22+9.51
fu23.9128.0335.0535.81+11.14+7.78
inst_01_10pol127.22193.16200.13200.59+72.91+7.43
inst_01_16pol76.88174.99124.91185.11+48.03+10.12
inst_01_2pol33.1136.043737.15+3.89+1.11
inst_01_3pol39.2448.094950.04+9.76+1.95
inst_01_4pol57.3672.1374.5774.64+24.37+2.51
inst_01_5pol69.6190.1893.9894.61+24.37+4.43
inst_01_6pol81.73114.47118.35119.51+36.62+5.04
inst_01_7pol96.98138.60143.74144.06+46.76+5.46
inst_01_8pol105.85156.66162.04162.48+56.19+5.82
inst_01_9pol124.10187.18193.30193.85+69.20+6.67
inst_01_26pol_hole165.78219.12213.88213.03+48.10−6.09
rco1140.73163.21174.21174.61+33.48+11.40
rco2271.63318.79349.94352.05+78.31+33.26
rco3398.33482.03526.18526.90+127.85+44.87
shapes2216.40228.57245.12246.72+28.70+18.15
shapes4432.10455.44485.45486.69+53.35+31.25
spfc_instance144.16148.36175.76165.90+31.60+17.54
trousers308.75346.61302.59303.54−6.16−43.07

References

  1. Júnior, B.A.; Pinheiro, P.R. Approaches to tackle the nesting problems. In Artificial Intelligence Perspectives in Intelligent Systems; Springer: Berlin/Heidelberg, Germany, 2016; pp. 285–295. [Google Scholar]
  2. Pisinger, D. Heuristics for the container loading problem. Eur. J. Oper. Res. 2002, 141, 382–392. [Google Scholar] [CrossRef]
  3. Araújo, L.J.; Panesar, A.; Özcan, E.; Atkin, J.; Baumers, M.; Ashcroft, I. An experimental analysis of deepest bottom-left-fill packing methods for additive manufacturing. Int. J. Prod. Res. 2020, 58, 6917–6933. [Google Scholar] [CrossRef]
  4. Araújo, L.J.; Özcan, E.; Atkin, J.A.; Baumers, M. Analysis of irregular three-dimensional packing problems in additive manufacturing: A new taxonomy and dataset. Int. J. Prod. Res. 2019, 57, 5920–5934. [Google Scholar] [CrossRef]
  5. Moreira, L.M.; Oliveira, J.F.; Gomes, A.M.; Ferreira, J.S. Heuristics for a dynamic rural postman problem. Comput. Oper. Res. 2007, 34, 3281–3294. [Google Scholar] [CrossRef]
  6. Manber, U.; Israni, S. Pierce point minimization and optimal torch path determination in flame cutting. J. Manuf. Syst. 1984, 3, 81–89. [Google Scholar] [CrossRef]
  7. Wäscher, G.; Haußner, H.; Schumann, H. An improved typology of cutting and packing problems. Eur. J. Oper. Res. 2007, 183, 1109–1130. [Google Scholar] [CrossRef]
  8. Araújo, L.J.; Pinheiro, P.R. Applying backtracking heuristics for constrained two-dimensional guillotine cutting problems. In Proceedings of the International Conference on Information Computing and Applications, Ho Chi Minh City, Vietnam, 5–7 December 2011; Springer: Berlin/Heidelberg, Germany, 2011; pp. 113–120. [Google Scholar]
  9. Hopper, E.; Turton, B.C. A review of the application of meta-heuristic algorithms to 2D strip packing problems. Artif. Intell. Rev. 2001, 16, 257–300. [Google Scholar] [CrossRef]
  10. Raggenbass, A.; Reissner, J. Automatic Generation of NC Production Plans in Stamping and Laser Cutting. CIRP Ann. 1991, 40, 247–250. [Google Scholar] [CrossRef]
  11. Raggenbass, A.; Reissner, J. Stamping—Laser Combination in Sheet Processing. CIRP Ann. 1989, 38, 291–294. [Google Scholar] [CrossRef]
  12. Amaro Júnior, B.; Pinheiro, P.R.; Coelho, P.V. A Parallel Biased Random-Key Genetic Algorithm with Multiple Populations Applied to Irregular Strip Packing Problems. Available online: https://www.hindawi.com/journals/mpe/2017/1670709/ (accessed on 8 October 2021).
  13. Leao, A.A.; Toledo, F.M.; Oliveira, J.F.; Carravilla, M.A.; Alvarez-Valdés, R. Irregular packing problems: A review of mathematical models. Eur. J. Oper. Res. 2020, 282, 803–822. [Google Scholar] [CrossRef]
  14. Labrada-Nueva, Y.; Cruz-Rosales, M.H.; Rendón-Mancha, J.M.; Rivera-López, R.; Eraña-Díaz, M.L.; Cruz-Chávez, M.A. Overlap Detection in 2D Amorphous Shapes for Paper Optimization in Digital Printing Presses. Mathematics 2021, 9, 1033. [Google Scholar] [CrossRef]
  15. Silva, E.F.; Oliveira, L.T.; Oliveira, J.F.; Toledo, F.M.B. Exact approaches for the cutting path determination problem. Comput. Oper. Res. 2019, 112, 104772. [Google Scholar] [CrossRef]
  16. Lee, M.K.; Kwon, K.B. Cutting path optimization in CNC cutting processes using a two-step genetic algorithm. Int. J. Prod. Res. 2006, 44, 5307–5326. [Google Scholar] [CrossRef]
  17. Dewil, R.; Vansteenwegen, P.; Cattrysse, D. Construction heuristics for generating tool paths for laser cutters. Int. J. Prod. Res. 2014, 52, 5965–5984. [Google Scholar] [CrossRef]
  18. Dewil, R.; Vansteenwegen, P.; Cattrysse, D.; Laguna, M.; Vossen, T. An improvement heuristic framework for the laser cutting tool path problem. Int. J. Prod. Res. 2015, 53, 1761–1776. [Google Scholar] [CrossRef]
  19. Zhao, X.; Bennell, J.A.; Bektaş, T.; Dowsland, K. A comparative review of 3D container loading algorithms. Int. Trans. Oper. Res. 2016, 23, 287–320. [Google Scholar] [CrossRef] [Green Version]
  20. Hoeft, J.; Palekar, U.S. Heuristics for the plate-cutting traveling salesman problem. IIE Trans. 1997, 29, 719–731. [Google Scholar] [CrossRef]
  21. Arkin, E.M.; Hassin, R. Approximation algorithms for the geometric covering salesman problem. Discret. Appl. Math. 1994, 55, 197–218. [Google Scholar] [CrossRef] [Green Version]
  22. Veeramani, D.; Kumar, S. Optimization of the nibbling operation on an NC turret punch press. Int. J. Prod. Res. 1998, 36, 1901–1916. [Google Scholar] [CrossRef]
  23. Garfinkel, R.S.; Webb, I.R. On crossings, the Crossing Postman Problem, and the Rural Postman Problem. Networks 1999, 34, 173–180. [Google Scholar] [CrossRef]
  24. Rodrigues, A.; Soeiro Ferreira, J. Cutting path as a Rural Postman Problem: Solutions by Memetic Algorithms. IJCOPI 2012, 3, 31–46. [Google Scholar]
  25. Dewil, R.; Vansteenwegen, P.; Cattrysse, D. A review of cutting path algorithms for laser cutters. Int. J. Adv. Manuf. Technol. 2016, 87, 1865–1884. [Google Scholar] [CrossRef]
  26. Chvátal, V.; Cook, W.; Dantzig, G.B.; Fulkerson, D.R.; Johnson, S.M. Solution of a large-scale traveling-salesman problem. In 50 Years of Integer Programming 1958–2008; Springer: Berlin/Heidelberg, Germany, 2010; pp. 7–28. [Google Scholar]
  27. Ahadi, A.; Mozafari, A.; Zarei, A. Touring a sequence of disjoint polygons: Complexity and extension. Theor. Comput. Sci. 2014, 556, 45–54. [Google Scholar] [CrossRef]
  28. Khan, W.; Hayhurst, D. Two and Three-Dimensional Path Optimization for Production Machinery. J. Manuf. Sci. Eng. Trans. Asme J. Manuf. Sci. Eng. 2000, 122. [Google Scholar] [CrossRef]
  29. Erdos, G.; Kemény, Z.; Kovacs, A.; Váncza, J. Planning of Remote Laser Welding Processes. Procedia CIRP 2013, 7, 222–227. [Google Scholar] [CrossRef]
  30. Xie, S.; Tu, Y.; Liu, J.; Zhou, Z. Integrated and concurrent approach for compound sheet metal cutting and punching. Int. J. Prod. Res. 2010, 39, 1095–1112. [Google Scholar] [CrossRef]
  31. Yu, W.; Lu, L. A route planning strategy for the automatic garment cutter based on genetic algorithm. In Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014, Beijing, China, 6–11 July 2014; pp. 379–386. [Google Scholar] [CrossRef]
  32. Bobade, S.; Badgujar, T.Y.B. A State Of Art In A Sheet Metal Stamping Forming Technology-An Overview. Int. J. Adv. Res. Innov. Ideas Educ. 2017, 3760–3770. [Google Scholar]
  33. Han, G.; Na, S. A study on torch path planning in laser cutting processes part 2: Cutting path optimization using simulated annealing. J. Manuf. Syst. 1999, 18, 62–70. [Google Scholar] [CrossRef]
  34. Dewil, R.; Vansteenwegen, P.; Cattrysse, D. Cutting path optimization using tabu search. In Key Engineering Materials; Trans Tech Publ: Zurich, Switzerland, 2011; Volume 473, pp. 739–748. [Google Scholar]
  35. Golden, B.L.; Wong, R.T. Capacitated arc routing problems. Networks 1981, 11, 305–315. [Google Scholar] [CrossRef]
  36. Usberti, F.L.; França, P.M.; França, A.L.M. The open capacitated arc routing problem. Comput. Oper. Res. 2011, 38, 1543–1555. [Google Scholar] [CrossRef] [Green Version]
  37. Holland, J. Adaptation In Natural And Artificial Systems; University of Michigan Press: Ann Arbor, MI, USA, 1975. [Google Scholar]
  38. Hopper, E.; Turton, B. A genetic algorithm for a 2D industrial packing problem. Comput. Ind. Eng. 1999, 37, 375–378. [Google Scholar] [CrossRef]
  39. Onwubolu, G.; Mutingi, M. A genetic algorithm approach for the cutting stock problem. J. Intell. Manuf. 2003, 14, 209–218. [Google Scholar] [CrossRef]
  40. Park, J.Y.; Seo, J.J. A Study on Cutting Path Optimization Using Genetic Algorithm. J. Ocean Eng. Technol. 2009, 23, 67–70. [Google Scholar]
  41. Deshpande, A.S.; Kelkar, R.B. Advanced genetic operators and techniques: An analysis of dominance & diploidy, reordering operator in genetic search. In Proceedings of the Ninth WSEAS International Conference on Evolutionary Computing, Sofia, Bulgaria, 2–4 May 2008; pp. 27–33. [Google Scholar]
  42. Blickle, T.; Thiele, L. A Mathematical Analysis of Tournament Selection. In Proceedings of the 6th International Conference on Genetic Algorithms; Morgan Kaufmann Publishers Inc.: San Francisco, CA, USA, 1995; pp. 9–16. [Google Scholar]
  43. Goldberg, D.E.; Lingle, R. AllelesLociand the Traveling Salesman Problem. In Proceedings of the 1st International Conference on Genetic Algorithms; L. Erlbaum Associates Inc.: Mahwah, NJ, USA, 1985; pp. 154–159. [Google Scholar]
  44. Bean, J.C. Genetic Algorithms and Random Keys for Sequencing and Optimization. ORSA J. Comput. 1994, 6, 154–160. [Google Scholar] [CrossRef]
  45. Resende, M. Biased random-key genetic algorithms with applications in telecommunications. TOP 2010, 20, 130–153. [Google Scholar] [CrossRef]
  46. Gonçalves, J.F.; Resende, M.G.; Toso, R.F. An experimental comparison of biased and unbiased random-key genetic algorithms. Pesqui. Oper. 2014, 34, 143–164. [Google Scholar] [CrossRef]
  47. Spears, V.M.; Jong, K.A.D. On the virtues of parameterized uniform crossover. In Proceedings of the Fourth International Conference on Genetic Algorithms, San Diego, CA, USA, 13–16 July 1991; pp. 230–236. [Google Scholar]
  48. Baioletti, M.; Milani, A.; Santucci, V. Variable neighborhood algebraic differential evolution: An application to the linear ordering problem with cumulative costs. Inf. Sci. 2020, 507, 37–52. [Google Scholar] [CrossRef]
  49. Santucci, V.; Baioletti, M.; Milani, A. An algebraic framework for swarm and evolutionary algorithms in combinatorial optimization. Swarm Evol. Comput. 2020, 55, 100673. [Google Scholar] [CrossRef]
  50. Baioletti, M.; Milani, A.; Santucci, V. An algebraic approach for the search space of permutations with repetition. In Proceedings of the European Conference on Evolutionary Computation in Combinatorial Optimization (Part of EvoStar), Seville, Spain, 15–17 April 2020; Springer: Berlin/Heidelberg, Germany, 2020; pp. 18–34. [Google Scholar]
Figure 1. Example of a two-dimensional C&P problem with irregular items and a single open-dimensional surface of fixed width and variable length. This is a 2 | S i | O o problem according to Araújo et al.’s taxonomy [4].
Figure 1. Example of a two-dimensional C&P problem with irregular items and a single open-dimensional surface of fixed width and variable length. This is a 2 | S i | O o problem according to Araújo et al.’s taxonomy [4].
Algorithms 14 00305 g001
Figure 2. Classification for cutting path problems according to [18,20,25]. TPP: touring polygons problem; CCP: continuous cutting problem; TSP: traveling salesman problem; TSP-N: TSP with neighborhoods; ICP: intermittent cutting problem; GTSP: generalized TSP; ECP: endpoint cutting problem.
Figure 2. Classification for cutting path problems according to [18,20,25]. TPP: touring polygons problem; CCP: continuous cutting problem; TSP: traveling salesman problem; TSP-N: TSP with neighborhoods; ICP: intermittent cutting problem; GTSP: generalized TSP; ECP: endpoint cutting problem.
Algorithms 14 00305 g002
Figure 3. Example of the layout conversion to a set of points in the plane.
Figure 3. Example of the layout conversion to a set of points in the plane.
Algorithms 14 00305 g003
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 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.
Algorithms 14 00305 g004
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 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.
Algorithms 14 00305 g005
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.
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.
Algorithms 14 00305 g006
Figure 7. Fitness representation to t(i) and t(i + 1). (a) illustrates the i-step to compute the fitness value for each individual. (b) supposed that the c h r o m ( i + 1 ) was the edge (z,w) and that its direction position ( c h r o m ( 2 n + ( i + 1 ) ) ) had value 1.
Figure 7. Fitness representation to t(i) and t(i + 1). (a) illustrates the i-step to compute the fitness value for each individual. (b) supposed that the c h r o m ( i + 1 ) was the edge (z,w) and that its direction position ( c h r o m ( 2 n + ( i + 1 ) ) ) had value 1.
Algorithms 14 00305 g007
Figure 8. A flowchart of BRKGA and parameters.
Figure 8. A flowchart of BRKGA and parameters.
Algorithms 14 00305 g008
Figure 9. Decoder process to BRKGA proposed.
Figure 9. Decoder process to BRKGA proposed.
Algorithms 14 00305 g009
Figure 10. Input and output representation.
Figure 10. Input and output representation.
Algorithms 14 00305 g010
Figure 11. Analysis of the proposed configurations for BRKGA (relation-1).
Figure 11. Analysis of the proposed configurations for BRKGA (relation-1).
Algorithms 14 00305 g011
Figure 12. Progression of the objective values through generations when addressing connected instances. BRKGA hyper-parameter: P = 10,000, Pe = 0.30, and Pm = 0.1.
Figure 12. Progression of the objective values through generations when addressing connected instances. BRKGA hyper-parameter: P = 10,000, Pe = 0.30, and Pm = 0.1.
Algorithms 14 00305 g012
Figure 13. Analysis of the proposed configurations for BRKGA (relation-2).
Figure 13. Analysis of the proposed configurations for BRKGA (relation-2).
Algorithms 14 00305 g013
Figure 14. Evolution process defined for time limit reached instances in C-group. Configuration of BRKGA: [P = 10,000, Pe = 0.20, and Pm = 0.2].
Figure 14. Evolution process defined for time limit reached instances in C-group. Configuration of BRKGA: [P = 10,000, Pe = 0.20, and Pm = 0.2].
Algorithms 14 00305 g014
Figure 15. Evolution process defined for time limit reached instances in C-group. Configuration of BRKGA: [P = 5000, Pe = 0.30, and Pm = 0.1].
Figure 15. Evolution process defined for time limit reached instances in C-group. Configuration of BRKGA: [P = 5000, Pe = 0.30, and Pm = 0.1].
Algorithms 14 00305 g015
Table 1. Characteristics of instances used in the computational experiments.
Table 1. Characteristics of instances used in the computational experiments.
InstanceVerticesEdgesItems
OriginalAdapted
(C)(S)(C)(S)(C)(S)(C)(S)
albano1561641641641731642424
blaz139444444464477
blaz27080888089801413
blaz3971321321321301322121
dighe12054465438541515
dighe22046384630461010
fu3743434351431212
inst_01_10pol2040394029401010
inst_01_16pol2712864128421281632
inst_01_2pol78888822
inst_01_3pol8121212101233
inst_01_4pol10161616131644
inst_01_5pol12201920162055
inst_01_6pol13242324182466
inst_01_7pol15282728212877
inst_01_8pol16323132233288
inst_01_9pol18363536263699
inst_01_26pol2102642642642372646666
rco133363636403677
rco26272727281721414
rco3821081081081161082121
shapes268707070787088
shapes41271401401401471401616
spfc_instance5555555563551111
trousers3503883883884243886464
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Share and Cite

MDPI and ACS Style

Amaro Junior, B.; Santos, M.C.; de Carvalho, G.N.; de Araújo, L.J.P.; Pinheiro, P.R. Metaheuristics for the Minimum Time Cut Path Problem with Different Cutting and Sliding Speeds. Algorithms 2021, 14, 305. https://0-doi-org.brum.beds.ac.uk/10.3390/a14110305

AMA Style

Amaro Junior B, Santos MC, de Carvalho GN, de Araújo LJP, Pinheiro PR. Metaheuristics for the Minimum Time Cut Path Problem with Different Cutting and Sliding Speeds. Algorithms. 2021; 14(11):305. https://0-doi-org.brum.beds.ac.uk/10.3390/a14110305

Chicago/Turabian Style

Amaro Junior, Bonfim, Marcio Costa Santos, Guilherme Nepomuceno de Carvalho, Luiz Jonatã Pires de Araújo, and Placido Rogerio Pinheiro. 2021. "Metaheuristics for the Minimum Time Cut Path Problem with Different Cutting and Sliding Speeds" Algorithms 14, no. 11: 305. https://0-doi-org.brum.beds.ac.uk/10.3390/a14110305

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop