1   Introduction

The shipbuilding industry is widely regarded as a highly promising sector owing to its significant contributions to the global economy (Kamola-Cieslik, 2021). The industry supports numerous other industries by providing essential maritime transportation while driving economic growth to meet the rising demand for new ship constructions. This demand is propelled by global trade expansion, advancements in shipping technology, and the pursuit of more efficient and environmentally friendly vessels (Smith et al., 2022). Notably, leading shipbuilding nations such as China, South Korea, and Japan depend heavily on this industry for economic stability and growth. China, for example, has expanded its shipbuilding capacity to become the world's largest shipbuilder, a growth fueled by government policies and significant investments in shipyard infrastructure (Ko and Shinoda, 2021). South Korea, renowned for its advanced shipbuilding technology, maintains a competitive edge by specializing in high-value vessels such as LNG carriers and offshore platforms (Hong et al., 2024). Japan, with its rich maritime history, continues to lead in ecofriendly ship designs and the automation of ship production processes (Japan Ship Technology Research Association, 2020; Ko and Shinoda, 2021). Given the critical role of ships as the primary mode of transportation across waterways, their significance cannot be overstated. Ships are essential for transporting goods and people worldwide, supporting international trade and significantly influencing the global economy (Nor and Nazery, 2008). Consequently, the production of these vessels requires careful attention to ensure they meet stringent standards of efficiency, safety, and environmental sustainability. This entails the adoption of advanced technologies, the implementation of rigorous safety protocols, and strict compliance with international environmental regulations (Alblas and Pruijn, 2024). The importance of the shipbuilding industry is further highlighted by its substantial impact on global trade and economic development (Baso et al., 2020; Sutrisno et al., 2024). The industry supports an extensive network of ancillary sectors, creates employment opportunities, and fosters innovation in maritime transportation. Its ability to adapt to changing market demands and technological advancements is crucial for maintaining and enhancing the efficiency and sustainability of global maritime operations.

In ship production, key activities related to plate cutting include preparation procedures and the steel plate cutting process, collectively referred to as the fabrication process (Mustafa et al., 2022). These tasks involve a series of precise steps and the use of advanced cutting technologies, such as oxy-fuel and plasma cutting, which demand high accuracy (Saiyara, 2024). Oxy-fuel cutting, preferred for its ability to handle thick steel plates, employs the combustion of oxygen and fuel gases to cut through steel. In contrast, plasma cutting uses an accelerated jet of hot plasma to slice through metal, providing greater precision and speed, particularly for thinner plates. The importance of these cutting processes cannot be overstated, as they are fundamental to preparing and arranging plate parts for smooth assembly while preserving the ship's structural integrity. Errors during this stage can lead to significant issues during assembly, potentially compromising the vessel's quality and safety (Okubo and Mitsuyuki, 2022). Given the critical role of plate cutting, selecting the appropriate technologies and processes is essential for optimizing steel plate utilization and reducing waste. This optimization process, known as nesting, involves strategically arranging cutting patterns on steel sheets to maximize material use and minimize waste. It requires careful consideration of factors such as part shapes, sheet dimensions, and design specifications. Advanced nesting software and algorithms are instrumental in generating optimal cutting patterns, enabling effective and efficient operations (Son et al., 2020). As the shipbuilding industry evolves, ongoing advancements and refinements in nesting techniques continue to improve the precision and efficiency of plate cutting, highlighting their critical role in enhancing the quality, efficiency, and sustainability of modern shipbuilding practices. The fabrication process and plate cutting optimization rely on specific design variables, which guide the selection of appropriate nesting methods. Nesting algorithms are broadly categorized into exact, heuristic, metaheuristic, and hybrid types, each providing effective solutions for optimizing nesting in shipbuilding. A thorough understanding of the characteristics and applications of each algorithm is crucial to achieving the best possible outcomes in nesting optimization.

Although nesting is critical in the shipbuilding industry, there is a notable lack of comprehensive studies that systematically evaluate and compare the various algorithms used for nesting optimization. Existing literature often emphasizes individual algorithms without offering a holistic perspective on their comparative effectiveness across diverse shipbuilding contexts. This research addresses this gap by conducting a systematic review of prominent nesting algorithms, focusing on their application within the shipbuilding industry. The primary objective is to thoroughly evaluate these algorithms to identify the most effective methods for optimizing material utilization and minimizing waste in ship production. This study is particularly timely, given the growing pressures on the shipbuilding industry to improve efficiency, reduce costs, and adhere to increasingly stringent environmental regulations. This research aims to investigate the current state of nesting algorithms to identify the most efficient solutions available today. Additionally, it seeks to compare these algorithms based on material utilization, computational efficiency, and their applicability to various shipbuilding contexts. Understanding these factors is essential for shipbuilders, as it will enable them to select the most suitable algorithms for their specific operational needs, ensuring more sustainable and cost-effective production processes. Furthermore, the research explores the criteria for evaluating each algorithm's suitability, focusing on key factors that influence the performance of these algorithms. By examining these factors, the study aims to identify areas where existing algorithms can be improved to meet the evolving demands of the shipbuilding industry. This exploration is crucial not only for advancing current nesting technologies but also for guiding future research and development efforts in this field. Ultimately, this paper seeks to provide valuable insights that will help shipbuilders achieve greater efficiency and sustainability in their production processes, thereby strengthening the industry's ability to adapt to global market demands and technological advancements.

2   Fabrication process and plate cutting optimization

The fabrication process is a crucial phase in shipbuilding. It follows the design stage and includes the basic design, technical project, and detailed project of the intended product (ILO, 2023). This phase is critical as it transitions into the shipbuilding stage, where the actual construction of the ship's structure occurs. The shipbuilding phase is notably complex, involving several intricate processes, such as cutting steel plates and profiles, constructing panels, assembling modular cross-sectional blocks, building superblocks, and, ultimately, assembling the ship hull (Okumoto et al., 2009; Mustafa et al., 2022). Each of these steps requires precise coordination and meticulous execution to ensure the integrity and performance of the final vessel. The success of the shipbuilding phase heavily depends on the efficiency and accuracy of the plate cutting process, which begins with cutting steel according to the design specifications (Basuki et al., 2012; Firmansyah et al., 2021). The cutting process is conducted using advanced machinery, such as cutting machines, lasers, or plasma cutters, which shape the steel plates to the required dimensions and forms for the ship's construction. The precision of these cuts is critical, as any inaccuracies can result in significant issues during subsequent stages of assembly. Additionally, the plate cutting process plays a key role in the overall efficiency of shipbuilding and material utilization (Rigo and Caprace, 2011; Perez-Martinez and Fernandez, 2023). Effective plate cutting minimizes waste and optimizes material use, making it both cost-effective and environmentally friendly. The quality of the cut plates directly influences the ease of assembly and the structural integrity of the ship. As a result, continuous advancements and innovations in cutting technologies and techniques are pursued to improve accuracy, reduce waste, and enhance overall efficiency in shipbuilding.

Plate cutting with nesting is a technique used to arrange and sequence cutting patterns from larger to smaller shapes or vice versa, with the goal of minimizing waste and optimizing material utilization, fabrication, and production (Oliveira and Gordo, 2018). This method strategically places smaller shapes within a larger material sheet to minimize unused material, thereby enhancing efficiency and reducing costs. The nesting process is often optimized using various approaches or algorithms, where the algorithm's flow is determined by design variables, constraints, and an objective function. These algorithms can range from simple heuristic methods to more complex metaheuristic techniques, such as genetic algorithms (GAs), simulated annealing (SA), or particle swarm optimization (PSO). The effectiveness of the nesting process largely depends on the algorithm's ability to manage the complexities of the material layout, taking into account factors such as the geometric shapes of the parts, material properties, and cutting constraints. Additionally, the objective function in these algorithms typically aims to maximize material utilization or the material utilization ratio while adhering to specific fabrication requirements and ensuring the quality of the cut parts. The material utilization rate, a key performance metric in this context (Xu and Yang, 2022), is defined by Equation (1).

where A_fp is the area of finished products, A_rm is the area of residual material, and ∑A is the total area of raw material used. This equation measures material usage efficiency, indicating the proportion of raw material effectively used for the finished products and residual materials. A higher material utilization ratio signifies better optimization and less waste. This comprehensive approach to nesting improves material efficiency and supports sustainable manufacturing practices by minimizing waste and reducing energy consumption during the cutting process. Similarly, the design variables for optimizing nesting in plate cutting include parameters with predefined constraints, such as plate dimensions and cutting patterns. The goal is to maximize nesting efficiency, which is quantified by the total yield rate, as shown in Equation (2), as proposed by Hamada et al. (2019).

Here, AP_x represents the total area of the parts (P_x), while AM_y denotes the area of the base material (M_y). N refers to the number of ship parts, and M indicates the number of base materials used. The yield rate measures nesting efficiency by minimizing the area of base material used during the fabrication process.

Nesting optimization design variables are closely related to the packing problem, which can be classified into two types: strip packing and bin packing. Strip packing involves arranging various strip patterns or shapes of different lengths onto a plane or base material with a fixed width (Martello et al., 2003), as illustrated in Figure 1. The objective of this process is to maximize area utilization by minimizing unused space. The patterns or shapes are strategically positioned to reduce the number of strips required and improve material efficiency (Liao et al., 2016). This is particularly important in the manufacturing industry, where raw materials are often costly, and efficient material usage can result in significant cost savings. Additionally, this method helps reduce material waste, supporting sustainability and ecofriendly practices.

Figure  1  Strip packing

Download: Full-Size Img

Conversely, the bin packing problem in nesting optimization focuses on fitting parts of varying sizes and space requirements into a limited number of available base materials or bins (Han et al., 2007), as illustrated in Figure 2. The goal is to minimize the area of base material used and maximize space efficiency (Hartono et al., 2022; González-San-Martín et al., 2023). In this context, parts must be arranged in a way that optimizes base material usage, minimizes wasted space, and maximizes the capacity of the available bins. This approach is essential in logistics and storage, where efficient space utilization can lower operational costs and improve productivity. Overall, both strip packing and bin packing play crucial roles in nesting optimization, helping industries enhance material and space efficiency, reduce costs, and promote more sustainable manufacturing practices.

Figure  2  Bin packing

Download: Full-Size Img

3   Classification of nesting algorithms

Nesting algorithms are a crucial component of nesting software, particularly for strip packing and bin packing design variables. They play a pivotal role in optimizing the arrangement of parts within a specified area, such as a sheet of metal or other base material designated for cutting. The primary goal of nesting algorithms is to minimize waste, maximize space utilization, and reduce production time and costs (Goodman et al., 1994). Implementing these algorithms offers several advantages, including improved part placement, reduced waste through efficient component measurement, better material utilization, and minimized scrap (Lodi, 1999; Lodi et al., 2002; Martinez-Sykora et al., 2017).

Canellidis et al. (2013) demonstrated that strategically placing parts to maximize space utilization can significantly improve productivity and cost-effectiveness. Efficient arrangements show that nesting optimization can reduce material usage, lower production expenses, and enhance overall efficiency in the production process (Timmerman, 2013). Additionally, nesting algorithms streamline the component layout, saving time and effort by automating the optimal placement process, which further enhances efficiency. Properly organizing components contributes to higher productivity by enabling faster cutting and production processes.

Nesting algorithms also offer customization and flexibility to meet specific needs, accommodating different types of parts and constraints while adapting to various manufacturing scenarios. Overall, these algorithms help maximize material utilization, reduce waste, and enhance the overall yield from the base material. As illustrated in Figure 3, these algorithms are categorized into several types, each providing distinct approaches to achieve efficiency and effectiveness in the manufacturing process.

Figure  3  Nesting algorithm

Download: Full-Size Img

Figure 3 illustrates the classification of nesting algorithms into four main categories: exact algorithms, heuristic algorithms, metaheuristic algorithms, and hybrid algorithms. Exact algorithms, including linear programming (LP) and branch and bound, use mathematical approaches to find optimal solutions. Heuristic algorithms, such as first-fit, best-fit, and next-fit, apply practical approaches to achieve good results. Metaheuristic algorithms, such as GAs, SA, and PSO, are inspired by natural or social processes to identify optimal solutions. Hybrid algorithms combine various methods, such as GA+SA, GA+PSO, and ant colony optimization (ACO) +GA, to enhance algorithm performance. Further explanations of each category and algorithm are provided in the following subsections.

3.1   Exact algorithm

Exact algorithms guarantee the identification of the optimal solution by exploring all possible solutions (Jones, 2014). While these algorithms provide optimal solutions, they typically have high computational costs, particularly for large-scale problems. Two examples of exact algorithms are LP and branch and bound. LP involves the formulation of a problem as a set of linear equations and inequalities (Vielma et al., 2008; Huang et al., 2021). The objective is to optimize a linear function while satisfying the given linear constraints. LP models generally consist of decision variables, an objective function, and constraints. Common techniques for solving LP problems include the Simplex method and Interior-Point methods. For example, in tackling the irregular strip packing problem, Cherri et al. (2016) developed mixed-integer linear programming models to handle piece non-overlapping constraints. They achieved this by either applying direct trigonometry to formulate the constraints or decomposing pieces into convex parts to simplify the geometric handling of non-overlapping constraints.

Branch and bound is a method used to find optimal solutions for combinatorial problems by breaking them into smaller subproblems and systematically evaluating potential solutions, as illustrated in Figure 4. The algorithm involves two key steps: "branching", where the problem is divided into subproblems, and "bounding", where upper and lower bounds are calculated for these subproblems. If the bound of a sub-problem indicates that it cannot yield a better solution than the best one found so far, it is discarded (Alvarez-Valdes et al., 2013). In their study, Alvarez-Valdes et al. developed a branch-and-bound algorithm for the irregular strip packing problem. This approach involved creating more efficient formulations and exploring various branching strategies, lower bounds, and variable-fixing procedures to improve computational performance.

Figure  4  Branch-and-bound algorithm

Download: Full-Size Img

3.2   Heuristic algorithm

Heuristic algorithms use practical rules or "heuristics" to find reasonably good solutions more quickly than exact algorithms (Muriyatmoko et al., 2024). While these algorithms do not guarantee optimal solutions, they often provide satisfactory results within a reasonable time frame. Examples of heuristic algorithms include the first-fit, bestfit, and next-fit algorithms. The first-fit algorithm assigns an item to the first available bin that can accommodate it. As described by Yue (1991), the first-fit decreasing (FFD) algorithm first sorts items in descending order of size and then places each item into the first bin with sufficient remaining space. Although this method is simple and fast, it does not always yield the optimal solution. The effectiveness of the FFD algorithm has been extensively studied, with proven bounds on its performance in relation to the optimal number of bins required.

Pospelov et al. (2023) applied the best-fit algorithm for optimizing resource allocation, which begins with a sorted list of resources or bins and items to allocate. Each item is placed into the bin that will have the least leftover capacity after the placement, ensuring it fits. If no existing bin can accommodate the item, a new bin is created. While this approach is more computationally demanding than the firstfit algorithm, it generally leads to better resource utilization by minimizing gaps, making future item placements more efficient.

The next-fit algorithm, used in bin packing problems, starts with an empty bin and a counter for the number of bins, initially set to 1 (Wang et al., 2023). The algorithm iterates through the list of items, placing each item in the current bin if it fits. If an item does not fit into the current bin, that bin is closed, a new bin is initiated, and the item is placed in it. This process continues until all items are packed, with the final bin count illustrated in Figure 5. For example, with items sized [4, 8, 1, 4, 2] and bins with a capacity of 10, start with Bin 1 and place Item 4 into Bin 1, making it [4]. Item 8 does not fit, so start Bin 2 and place Item 8, making it [8]. Add Item 1 to Bin 2, making it [8, 1]. Item 4 does not fit, so start Bin 3 and place Item 4, making it [4]. Add Item 2 to Bin 3, making it [4, 2]. Finally, add Item 1 to Bin 3, making it [4, 2, 1]. The result is three bins: Bin 1 = [4], Bin 2 = [8, 1], Bin 3 = [4, 2, 1].

Figure  5  Next-fit algorithm

Download: Full-Size Img

3.3   Metaheuristic algorithm

Metaheuristic algorithms are advanced optimization techniques designed to find near-optimal solutions for a broad range of problems. These algorithms generally combine multiple heuristics and incorporate randomization to explore the solution space. Examples of metaheuristic algorithms include GAs, SA, and PSO.

GAs are based on the principles of biological evolution, utilizing processes such as selection, crossover, and mutation to evolve solutions over multiple generations. According to Lourenço et al. (2001), GAs begin with an initial population of potential solutions represented by chromosomes. These chromosomes are selected based on their fitness, undergo crossover to combine parts of two solutions, and are subject to mutation to introduce variability. This process continues until a stopping criterion is met, such as reaching a maximum number of generations or achieving an acceptable fitness level (Selow et al., 2007).

SA is an optimization method inspired by the cooling process in metallurgy, where solutions are explored randomly with a decreasing probability of accepting worse solutions over time. As explained by Ingber (1993), the SA algorithm starts with an initial solution and temperature. At each iteration, a new solution is generated by making a small random change to the current solution. If the new solution is better, it is accepted; if it is worse, it may still be accepted with a probability that decreases as the temperature lowers. The temperature gradually decreases according to a cooling schedule until it reaches a predefined minimum, at which point the algorithm stops (Gomes and Oliveira, 2006).

PSO mimics the social behavior of bird flocks or fish schools, where each "particle" in the swarm adjusts its position based on both individual and collective experiences. According to Kennedy and Eberhart (1995), PSO begins with a swarm of randomly initialized particles, each representing a potential solution. Each particle updates its position by considering its own previous best position and the best positions found by its neighbors, with the aim of converging toward the optimal solution identified by the swarm (Kareem et al., 2022). This iterative process continues until a stopping criterion, such as a maximum number of iterations or convergence to a stable solution, is reached.

3.4   Hybrid algorithm

Hybrid algorithms combine two or more algorithms from different categories to leverage their respective strengths, aiming to improve solution quality and computational efficiency (Ting et al., 2015; Azevedo et al., 2024). These algorithms are particularly useful in various applications, as they can address the limitations of one algorithm by utilizing the strengths of another. Examples of hybrid algorithms include combinations such as GA with SA, GA with PSO, and ACO with GA, among others. The GA and SA combination capitalizes on GA's ability to explore global solutions and SA's strength in local solution exploitation (Elhaddad, 2012; Bettemir and Sonmez, 2015). Similarly, the GA+PSO hybrid enhances solution search by combining GA global exploration capabilities with PSO's ability to intensify the search in promising areas (Ru and Jianhua, 2008). ACO+GA combines ACO (Lee et al., 2008; Ashari et al., 2016) with GA, where ACO uses pheromone trails to guide the search, while GA generates solution variations, improving efficiency in complex optimization problems. Each of the aforementioned categories and algorithms has unique characteristics and applications. The selection of the most suitable algorithm depends on the specific nature and requirements of the problem at hand.

4   Development of nesting algorithms in shipbuilding

Nesting algorithms play a crucial role in shipbuilding by optimizing plate cutting, reducing waste, and improving material utilization. They efficiently arrange cutting patterns, enhancing the cutting process by strategically organizing patterns from large to small. These algorithms also enable the accurate determination of material needs, support supply management, and align with production schedules (Xie et al., 2007; Xu, 2016).

Various algorithms, including exact, heuristic, metaheuristic, and hybrid methods outlined in the previous section, have been developed to enhance nesting efficiency. These advanced techniques help reduce computation time and material waste while improving material utilization. Assessing their performance under different conditions is crucial to ensure smooth integration into production processes. By choosing the most effective nesting solutions, shipbuilders can optimize material usage, cut costs, and streamline production timelines, thereby promoting sustainability and minimizing waste through optimal nesting strategies.

Nesting optimization in shipbuilding is a critical process that greatly influences material utilization, production efficiency, and overall cost-effectiveness (Egeblad et al., 2007). A comprehensive and precise consideration of nesting solutions ensures the optimal use of materials, reducing waste and minimizing production costs. In shipbuilding, where materials such as steel plates are extensively used (Suzuki et al., 2004; Yu-ichi, 2007; Uemori et al., 2012), efficient nesting results in significant savings and improved production efficiency. Additionally, it plays a crucial role in achieving accurate cuts and fits, which are essential for the structural integrity and performance of the ship.

Nesting algorithms have been classified into four categories in the previous section: exact algorithms, heuristic algorithms, metaheuristic algorithms, and hybrid algorithms. Each of these approaches has its strengths and weaknesses, and understanding them is essential for selecting the most suitable method for a specific application. Exact algorithms provide precise solutions by exploring all possible configurations, though they are often computationally intensive and may not be practical for large-scale problems due to lengthy processing times (Hifi, 2001). Heuristic algorithms offer approximate solutions by employing rules of thumb or strategies that reduce the search space. While faster than exact algorithms, they may not always find the best possible solution (Hu et al., 2015). Metaheuristic algorithms are advanced techniques that enhance the effectiveness of heuristic algorithms in exploring the solution space (Lee et al., 2023). These include methods such as GAs, SA, PSO, and others. Metaheuristic algorithms balance solution quality and computation time, making them wellsuited for complex nesting problems. Hybrid algorithms integrate elements from various algorithmic approaches to leverage the strengths of each method while minimizing their weaknesses (Fujita et al., 1993; Wu et al., 2003; Xu et al., 2017). For example, a hybrid algorithm might use a heuristic method to quickly find a good solution and then refine it using an exact algorithm.

To aid in the categorization of various identification criteria for optimizing nesting algorithms in shipbuilding, Sari et al. (2024) identified 10 essential criteria for evaluating these algorithms. Each criterion plays a crucial role in determining the effectiveness and practicality of the nesting solution, as illustrated in Figure 6 and detailed in Table 1 below.

Figure  6  Criteria for optimal nesting solutions in shipbuilding

Download: Full-Size Img

By integrating the criteria in Table 1 into the evaluation of nesting algorithms, shipbuilders can ensure that the selected solution meets both technical requirements and the practical constraints of the shipbuilding industry. This comprehensive approach fosters more efficient production processes, better resource management, and ultimately, higherquality, cost-effective shipbuilding operations. Additionally, a further review is conducted using a systematic review method, as illustrated in Figure 7. The systematic review method provides advantages such as comprehensive coverage of existing literature, rigorous evaluation of research quality, and structured synthesis of findings (Gray, 2019; Williams et al., 2021), offering a robust foundation for making informed decisions about nesting algorithms.

Figure  7  Methodology of the review

Download: Full-Size Img

The research methodology for this study began with the formulation of a clear research plan that outlined the objectives and scope of the literature review and analysis. The literature search was conducted using several academic databases, including IEEE Xplore, ScienceDirect, SpringerLink, and Google Scholar, with a focus on publications from 2018 to 2024 to ensure the inclusion of the most recent advancements in nesting algorithms. Relevant search terms were defined using Boolean operators ("and/or") to combine keywords such as "nesting algorithms", "shipbuilding", "plate cutting optimization", and "material utilization". This comprehensive search strategy played a crucial role in identifying all potentially relevant studies. The selection process involved both automated and manual filtering stages. First, duplicate records were removed, followed by the exclusion of articles that did not meet the predefined inclusion criteria. Studies were excluded if they did not focus on nesting algorithms relevant to shipbuilding, were published before 2018, or were not written in English. These criteria were strictly applied to ensure that only studies directly related to the research objectives were included in the final review. The parameters for data collection were defined, encompassing the types of algorithms reviewed, the context of their usage, key performance indicators evaluated, and specific criteria for assessing nesting algorithms. The quality of the collected data was carefully assessed to ensure its validity and reliability. The gathered information was then analyzed to identify trends and patterns, followed by the interpretation of the results to extract meaningful insights into the researched topic.

The study followed a structured and transparent review process in accordance with PRISMA guidelines (Page et al., 2020; 2021), with a flow diagram provided to overview the systematic review, as illustrated in Figure 8. The diagram details the stages of identification, screening, and inclusion, starting with 320, 261 records identified from the search and concluding with 35 studies included in the final review. This structured approach ensured that the research was based on a robust foundation, offering reliable and relevant insights into the effectiveness of various nesting algorithms in shipbuilding. Through a systematic review of the literature, the study identified the most effective algorithms for this context, evaluated their performance based on established criteria, and ensured that the solutions derived are applicable in real-world shipbuilding scenarios. To assess the effectiveness of various nesting methods, the study evaluated their alignment with 10 optimality criteria: material dimensions, part geometry, component layout, material waste reduction, overlap and collision detection capabilities, achievement of optimal solutions, real-world applicability, computation time efficiency, and cost-effective material usage. The results presented in Table 2 compare the different methods, providing valuable insights into their ability to enhance efficiency, minimize waste, and facilitate practical implementation within shipbuilding processes.

Figure  8  Flow diagram of the research study filtering process

Download: Full-Size Img

The analysis of Table 2 reveals various nesting methods employed in shipbuilding, focusing on their alignment with 10 optimality criteria. The method by Hamada et al. (2019), which is based on branch and bound, achieves 100% alignment, demonstrating strong efficiency in both strip and bin arrangements. Meanwhile, the approach by Calabrese et al. (2022), employing custom genetic nesting, achieves 90% alignment by combining elements of strip and bin packing. In contrast, the methods by Rakotonirainy and Vuuren (2020) and Liu and Chang (2023), which focus more on strip packing with hybrid SA and hybrid BonSA, respectively, achieve 70% and 60% alignment. Bin packing methods generally show higher alignment (80%–100%), while hybrid methods, such as those used by Hamada and Calabrese, demonstrate potential by combining the strengths of both approaches. This analysis offers a thorough evaluation of nesting methods, highlighting their effectiveness in reducing waste and improving efficiency in shipbuilding processes. A deeper examination of each research algorithm was then conducted, focusing on its efficiency, iteration rate, and final nesting optimization results, as detailed in Table 3.

Table 3 presents the efficiency of various nesting methods employed in the shipbuilding industry. It covers key aspects such as iteration time, iteration rate, and optimization results achieved by each method. The columns in the table include the reference number of the method, a brief description of the nesting approach, the iteration time and rate used, and the optimization outcomes, such as improvements in efficiency, material utilization rates, and reductions in cost or time. The methods listed differ in their approaches to solving nesting problems, including the use of iterative algorithms, reverse convex quadratic constraints, and the integration of multiple evolutionary algorithms. Each method is evaluated based on its effectiveness in enhancing material utilization and reducing production time and costs. This analysis builds upon the 10 evaluation criteria discussed in Table 2, with methods selected based on the highest compatibility with each design variable.

To identify the two best algorithms in each packing category (strip packing, bin packing, and hybrid packing), the data presented in Table 3 were analyzed. This analysis highlights that the research by Xu and Yang (2022) and Wang et al. (2024) are the top choices for strip packing. Xu and Yang (2022) utilize an improved GA with real number encoding, achieving an impressive material utilization rate of approximately 92.73%, as illustrated in Figure 9. Convergence occurs after around 100 generations, with further improvements in the solution observed after approximately 20000 generations. Wang et al. (2024) use the maximum residual rectangle genetic (MRRG) algorithm, which reaches a material utilization rate of 97.5%, showing a 4%–5% improvement over the previous maximum residual rectangle (MRR) algorithm, as illustrated in Figures 10 and 11. This indicates a significant increase in material utilization efficiency.

Figure  9  Nesting result based on rectangular packing method (Xu and Yang, 2022)

Download: Full-Size Img

Figure  10  Nesting results (Wang et al., 2024)

Download: Full-Size Img

Figure  11  Material utilization comparison between MRR and MRRG algorithms (Wang et al., 2024)

Download: Full-Size Img

In the bin packing category, the papers by Li et al. (2021) and (Hamada et al., 2019) stand out as the best. Li et al. (2021) introduce the hybrid adaptive genetic algorithm (HAGA), which demonstrates a high material utilization rate, reaching 100% in some instances, as shown in Table 4 and Figure 12. This algorithm performs 150 continuous iterations without significant changes, emphasizing its effectiveness in maximizing material usage. Hamada et al. (2019) utilize a branch-and-bound method with a rule-based approach that requires only 11 minutes of computation time. This method achieves a good optimization result compared with manual methods, with a utilization rate of 66.78%, as illustrated in Figure 13.

Figure  12  Nesting layout of instances (Li et al., 2021)

Download: Full-Size Img

Figure  13  Effectiveness rate of branch-and-bound algorithm (Hamada et al., 2019)

Download: Full-Size Img

For hybrid packing, the top choices are Wang et al. (2024) and Hamada et al. (2019). Wang et al. (2024) with the MRRG algorithm, achieves an impressive material utilization rate of 97.5%. This algorithm combines the maximum residual strategy with GAs, leading to significant improvements in material efficiency. Hamada et al. (2019) employ a brand-and-bound algorithm, with Figure 14 illustrating the nesting system applied to a ship's engine room. The system-generated plan achieved a 5% higher yield rate than the manually arranged plan, owing to more efficient part combinations using the same base material. This demonstrates the system's potential to improve efficiency and outcomes, particularly for complex shapes. Moreover, the system is significantly time-efficient, generating plans in 40 minutes compared with 2 hours by an expert engineer, demonstrating its superiority over manual arrangements.

Figure  14  Comparison of nesting layout: manual arrangement by expert engineer versus nesting system (Hamada et al., 2019)

Download: Full-Size Img

In conclusion, for strip packing, the studies by Xu and Yang (2022) and Wang et al. (2024) are the top performers, offering exceptional material utilization rates and efficient algorithms. For bin packing, the works by Li et al. (2021) and Hamada et al. (2019) provide efficient and rapid solutions. In hybrid packing, the combined methods of Wang et al. (2024) and Hamada et al. (2019) deliver excellent results in optimizing material utilization and operational efficiency in shipbuilding. This analysis emphasizes the importance of selecting the appropriate algorithm based on the packing type and specific industry requirements to achieve optimal material and operational efficiency.

5   Discussion

The analysis conducted using the systematic review methodology in the previous section identifies several algorithms highly suitable for nesting optimization criteria. However, based on these results, a continuous review can be performed to address deficiencies, potential future developments, and suggestions for improvement for each algorithm presented in the papers. A comparison of the disadvantages, potential developments, and future improvement suggestions for each paper is presented in Table 5.

To simplify the evaluation in Table 5, the majority of shortcomings of the proposed algorithm are categorized based on design variables: bin packing, strip packing, and hybrid packing. This categorization provides a structured approach to identifying and addressing common issues frequently encountered during algorithm development. By focusing on these recurring problems, future enhancements can avoid similar pitfalls, leading to more robust and efficient solutions. Additionally, the categorization helps identify clear patterns for future development by examining papers with well-defined and structured deficiencies. This method simplifies the evaluation process and ensures that the development is guided by a thorough understanding of past shortcomings. By adopting this approach, developers can prioritize improvements that address the most critical issues, ensuring that future algorithms are both innovative and practical. The ultimate goal is to establish a more efficient development cycle that builds on previous advancements, leading to increasingly sophisticated and effective algorithms.

Gunbeyaz et al. (2022) focused on improving productivity in ship recycling through discrete event simulation. However, their nesting optimization algorithm has several limitations, including a lack of transparency in the current tools, inadequate coverage of all activities within ship recycling yards, and limited flexibility in process modification. Future developments should aim to support decisionmaking for equipment usage, develop user-friendly frameworks to optimize yard productivity and consider both CAPEX and OPEX for new technologies. Additionally, more case studies are needed to identify risks associated with technologies such as plasma cutters. Improvements should focus on enhancing productivity through comprehensive optimization and flexible process adjustments.

Hamada et al. (2019) presented an automatic nesting system that employs the branch-and-bound method. However, the GA-based approach in this study suffers from inefficiency in computation time, a suboptimal one-point search method, and limited arrangement options with the BL method. Future improvements should address the combinatorial explosion in methods such as BL and GA, enhance the search for arrangement positions, and retain multiple intermediate proposals. The algorithm requires a broader search area for better arrangement plans and should apply the branch-and-bound method to decompose complex problems into more manageable subproblems.

Xu and Yang (2022) proposed a steel plate cutting optimization algorithm based on a genetic algorithm with real number coding. The main drawback of this algorithm is its reduced global search capability. Future research should focus on improving the model's generalizability and applicability to various cutting processes, as well as managing packing solutions for different raw material sizes. Enhancing the algorithm will involve exploring underutilized regions of the solution space to improve the global search capability.

Fang et al. (2023a) developed a hybrid reinforcement learning algorithm to address 2D irregular packing problems. However, the algorithm has several shortcomings, including poor universality, susceptibility to local optimum traps, and high computational costs. Future development should focus on leveraging machine learning and deep learning algorithms for sequential packing optimization, utilizing reinforcement learning to model sequential decision problems as Markov decision processes. To enhance the algorithm, it is essential to integrate diverse optimization techniques, utilize advanced learning models such as deep reinforcement learning, and implement improved exploration mechanisms to avoid local optima.

Research by Calabrese et al. (2022) developed a nesting algorithm aimed at optimizing part placement in additive manufacturing. However, this algorithm operates only in the XY plane, limiting its applicability to three-dimensional nesting, and does not consider the qualitative aspects of printed components. Future development should integrate the Z-axis, address qualitative factors such as surface finish and structural integrity, and enhance compatibility with commercial 3D printing systems for advanced processes such as selective laser melting. Additionally, improvements should introduce technological parameters specific to additive manufacturing, incorporate iterative processes to ensure accuracy and develop flexible integration strategies for various software environments.

The optimization algorithms discussed can be categorized into strip packing, bin packing, and hybrid packing. Strip packing, as demonstrated by Hamada et al. (2019), aims to minimize material waste by arranging parts in a strip shape but faces challenges such as computational inefficiency and suboptimal placements. The aim of bin packing, explored by Xu and Yang (2022), is to maximize space utilization in containers, but the method struggles with maintaining the global nature of the search solution and managing small-scale problems. Hybrid packing, as highlighted by Fang et al. (2023a), combines elements of both approaches to address irregular packing problems but encounters issues such as local optimum traps and high computational costs.

Future development directions for packing algorithms should focus on addressing combinatorial explosions in strip packing by enhancing search methods and preserving intermediate proposals. Additionally, improving the generalizability of bin packing models for various cutting processes is essential, along with advancing machine learning techniques for hybrid packing. Suggested improvements include broadening the search area in strip packing, exploring less characterized solution spaces in bin packing, and integrating diverse optimization methods in hybrid packing.

Implementing these algorithms across various software environments can enhance their flexibility and usability, making them more accessible to a broader range of users, including non-experts. Developing user-friendly interfaces and integration tools that allow seamless application in different industrial settings would significantly increase adoption. Ensuring that these algorithms are easily modifiable and adaptable to specific user needs will further improve their practicality and effectiveness. In summary, the primary directions for the future development of these packing algorithms are to address combinatorial explosions in strip packing by refining search methods and preserving intermediate proposals and to enhance the generalizability of bin packing models for various cutting processes. Advancing machine learning techniques for hybrid packing is also crucial. Expanding the search area in strip packing, exploring less explored solution spaces in bin packing, and incorporating diverse optimization strategies in hybrid packing are key steps forward. Additionally, integrating these algorithms into various software environments will enhance their flexibility and usability, leading to more robust and adaptable solutions for a range of packing problems. By embracing these advancements, we can achieve more efficient, reliable, and scalable packing solutions that better meet the needs of modern industrial applications.

6   Conclusions

The use of various nesting algorithms in shipbuilding has significantly improved material utilization, reduced waste, and enhanced overall production efficiency. These algorithms can be classified into exact, heuristic, metaheuristic, and hybrid categories, with each offering distinct benefits for nesting optimization. Exact algorithms provide precise solutions but are often hindered by high computational times. Heuristic algorithms deliver faster, more practical solutions, although they may not always achieve the optimal result. Metaheuristic algorithms offer a balanced approach, optimizing both solution quality and computational efficiency, making them particularly suitable for complex nesting challenges. Hybrid algorithms combine the strengths of different approaches, offering robust and efficient solutions. A systematic review of these algorithms highlights their performance across various criteria, emphasizing their practical applicability in real-world shipbuilding scenarios. This comprehensive evaluation underscores the importance of selecting the most effective algorithm to optimize material usage, reduce costs, and improve production timelines, ultimately promoting sustainable and efficient shipbuilding practices. Moreover, ongoing research suggests potential advancements, such as integrating AI, machine learning, and realtime adaptability, to further enhance the efficiency and effectiveness of nesting solutions. Overall, nesting algorithms are essential tools for enhancing productivity and sustainability in shipbuilding, with broad applications across various manufacturing sectors.