基于遺傳算法的被動式木窗材下料優化

中圖分類號：S777 文獻標識碼：A DOI：10.7525/j.issn.1006-8023.2025.03.016

Abstract：In thecustomization process of pasive wooden window manufacturing，reducing material wasteduring frame cutting is keytocostreduction.This problem is modeledasaone-dimensional cutting stock problem.Toadress the issue of traditional geneticalgorithms wheretheindividual encoding method tends toleadtothedestructionofcuing patternsandlow exploration eficiency during iterations，anew individual encoding methodis proposed to maintainthe integrityofcutting patterns throughout the evolutionary process.Additionally，aheuristic strategy andacorrection strategy are introduced for individual correctionandpopulationevolution.Simulationresultsshowthat fordiferent testcases， the average material utilization rate，excluding the last remnants，exceeds 99 % ，with some improvements in the length of thelastremnants compared toother algorithms.Fortwosets ofreal production data fromenterprises，the proposed algorithmachieves the theoreticallower bound，withaverageutilizationrates （excluding the lastremnants）of 99.49%and 99.66%，respectively，outperforming the resultsofthe company's existing software.This demonstrates the algorithm's potential to efectively reduce costs and provide practical solutions in engineering applications.

Keywords：One-dimensionalcutting stock problem；genetic algorithm；heuristic algorithm；population encoding；usable leftovers

0 引言

場正在不斷擴大。其中，被動式木窗因其美觀、保溫、隔音以及低碳等優勢，逐漸受到市場的關注和喜愛[1]。然而，高昂的原料成本制約了定制化被動式木窗市場隨著人們對家具定制需求的增加，定制化家具市的進一步擴展。在生產過程中，被動式木窗的邊框材通常通過截斷標準長度的集成材獲得，這一過程中會產生各種廢料。因此，為了降低成本，可以通過減少截斷過程中原材料的浪費來實現優化，這就涉及一維下料問題。

一維下料問題（one-dimensional cutting stock prob-lem，1D-CSP）旨在通過切割給定規格的原料生成滿足生產需求的零件或產品，并盡可能減少材料浪費或使用量。這一問題在制造業中備受關注[2]，由于1D-CSP具有非確定性多項式困難（non-deterministicpolyno-mial-timehard，NP-hard）屬性，隨著問題規模的增大，求解愈發困難。為解決1D-CSP，大量文獻進行了相關研究。目前主要的解決方式有2種。一是精確算法，包括列生成[3-4]、分支-切割-定價[5]等方法，常用于求解最優解，但需要消耗大量的計算資源。二是啟發式算法，可分為傳統啟發式和元啟發式，用于獲得可接受時間內的可行解6。傳統啟發式算法，如降序首次適應算法（first fit decreasing，FFD）[7]、降序最佳適應算法（best fitdecreasing，BFD）[8]、殘差重組啟發式算法（residual recombination heuristic，RRH）等[9]，通過設計的策略快速獲取下料方案，但對于較大規模的問題，此類方法僅能得到局部解，為此許多文獻中使用元啟發算法進行求解，比如沈顯君等[1]結合粒子群算法、遺傳算法以及模擬退火算法提出的自適應廣義粒子群優化算法（adaptive general particle swarm optimization，AGPSO），魏涼良等[1]結合BFD算法提出了自適應混合遺傳算法（modified adaptive genetic algorithm hybrid-izedwithBFDalgorithm，MAHGA），侯改等[12]借助金字塔演化策略并結合差分進化算法提出了基于差分進化的金字塔演化策略算法（pyramid evolution strategy withdifferentialevolution，DEPES），丁為[13]將多種傳統啟發式算法的解作為初始解，受交叉遺傳啟發，實現算法的快速收斂。

元啟發式算法在求解問題之前，需要對個體進行編碼。對于1D-CSP，在傳統遺傳算法中，個體編碼是直接對所有需要生成的零件進行排序，個體長度等于零件個數。這種編碼方式的進化過程實質上是對排列順序進行優化。然而，當問題規模較大時，該編碼方式顯現出明顯的局限性：一方面，在優化過程中，交叉和變異操作需要頻繁打亂當前排列順序，從而實現對解空間進行探索，但這種以零件為基因單位的擾動，會破壞基因片段，進而破壞已有切割模式的完整性，最終降低探索效率；另一方面，隨著問題規模增大，交叉和變異操作對個體影響逐漸減弱，探索驅動力降低，使算法更容易陷入局部解。

本研究提出一種基于切割模式的編碼方式來求解1D-CSP。通過該編碼方式可以更加激烈地探索，有助于跳出局部解。此外，還設計一種啟發式策略和修正策略，用于個體修正和種群優化。

1 問題背景

某被動式木窗企業的定制化加工車間中，負責截斷生成被動式木窗邊框材（簡稱邊框材）的生產線工藝如圖1所示。該生產線的工藝流程為：首先，吸盤機械手將標準長度的集成材抓取并放置到傳送帶上；然后，集成材經優選鋸切割成符合訂單需求的各類邊框材；最后，工人將切割完成的邊框材碼垛并轉運至后續加工區域。邊框材的種類和數量由制造執行系統（manufacturingexecutionsystem，MES）根據總生產需求分配，以滿足訂單要求。

Fig.1 Schematic diagram of the passive wooden window frame processing production line and on-site photo

為能夠提升木窗的生產效率并降低人工成本，企業希望可以使用碼垛機械臂代替工人，為此需要能夠提前獲取到邊框材的出料順序以輔助機械臂實現高效碼垛。然而，由于生產線上的優選鋸是外購設備，無法提前獲知出料順序，企業急需開發一個有效的下料優化方案，以便將其嵌人到現有工藝流程中。下料優化方案應當考慮到多個因素，包括邊框材的尺寸、數量和排料方式，旨在實現最優的原料利用率。

2 問題模型

所提木窗企業實際生產過程中，由于標準集成材的長度僅有一種，故假設所有原料長度均為 L 且數量不受限制。現需要從這些原料上切割出 N 種零件，零件的長度為 ，相應的數量為 1 ， ? s ， N ） ，目標是尋找最優的下料方案，使得所需要的原料數量最少。考慮到最后一根原料生成的余料可直接在下一批訂單中使用或被存放到庫存中，在將來的加工中再次使用，均有利于降低生產成本[14]。本研究模型為

式中： K 為下料方案中不同切割模式的數量； 為第 k 種切割模式所使用的次數； 為第 k 種切割模式下產生的第i種邊框材的數量；1為最后一根料的余料； 和Z 分別為正整數集和整數集。第1個約束條件為需求約束，表示按照下料方案切割后，產生的邊框材需要滿足生產的種類和數量需要；第2個約束條件表示尺寸約束，即對于任意一根原料，切割后產生的邊框材總長度不大于原料長度；最后2個約束條件確定了決策空間，即每種切割模式的使用次數以及產生的邊框材個數都為整數。

3 算法設計

3.1個體編碼和種群初始化

在遺傳算法的種群中，對于1D-CSP，每個個體代表一種下料方案，一個下料方案可由多種切割模式及相應的使用次數組成。本研究算法中使用矩陣表示個體，矩陣大小為 ，其中 表示僅在下料方案中使用到的切割模式數量，可以減小個體存儲和計算成本。

以 6 m 原料生成3個 2 m 和2個 3 m 的邊框材為例，個體編碼和種群初始化的方式如圖2所示。首先，以隨機序列方式生成所有邊框材，如{2-2-2-3-3}和{2-3-3-2-2]；然后，依據尺寸約束對生成的序列進行分割，分割出的每一個子序列都是一種切割模式，如{2-2-2-3-3]分割為{2-2-2}和{3-3]，{2-3-3-2-2}分割為{2-3}、{3-2}和{2}。由于子序列中邊框材的產生順序并不影響廢料產生結果，即{2-3]與{3-2}產生的廢料長度均為 1 m ，因此對每個子序列都進行降序排序，并將排序結果進行分類統計，實現個體的矩陣編碼，見圖2中的生成的個體1（Ind.1）和個體2（Ind.2）。

在矩陣中，第1行表示每種切割模式的使用次數，第2行起每列代表一種切割模式，其中的數值表示該模式下各類邊框材的數量。相比以單個零件作為基因的編碼方式，本研究提出的編碼方式將切割模式作為基因單位，使個體的變化表現為對不同切割模式的組合。這種方式不僅避免了隨意破壞現有切割模式，還保證了切割模式的完整性，有助于將高效的切割模式遺傳給下一代，從而提高算法的求解效率和質量。

3.2 啟發式策略

盡管所設計的編碼方式中，種群中的個體已滿足模型的約束條件，但部分切割模式可能不合適，影響下料方案的優化效果。仍以 6 m 原料產生3根 2 m 以及2根 3 m 的邊框材為例。假設初始順序為{2-2-3-2-3}，分割產生3個子序列，即{2-2}、{3-2}和{3}，此時需要使用3根原料。可以發現該序列下，第1根原料產生的2 m 余料被丟棄，但其可被保留用于生成一個 2 m 的邊框材。而對于{2-2-2-3-3}的初始順序，余料長度為

0，消耗2根原料。可見切割模式滿足最大切割模式[8]條件，即 是實現最優下料的前提。考慮到當問題規模變大時，滿足最大切割模式的模式數量增加，而不同切割模式組合都有可能實現最優解，因此以隨機順序進行初始化是必要的。

為了盡可能保證用到的切割模式都滿足最大切割條件，設計一種啟發式策略，流程如圖3所示。對于任意個體，從第1列 k = 0 ， 開始判斷當前切割模式是否滿足最大切割模式條件，若滿足則向后逐步判斷。若不滿足，則從最后一列 ）開始往前，將基因所包含的內容統計到 中，并根據 對不滿足最大切割條件的模式進行補充。具體而言，按照長度的降序順序選擇可用于補充的邊框材，直到滿足最大切割模式條件。當前后搜索到同一列時，即 ，停止 的移動。繼續向后逐步搜索時，將對應模式所涉及的邊框材按照種類和數量歸還，并按邊框材長度降序順序補充，可保持種群多樣性。

值得注意的是，每個個體不僅包含切割模式，還包含相應的使用次數，每次調整補充時需要考慮數量因素。僅向后逐步搜索時，若 中符合條件的邊框材數量不能夠完全補充當前模式，那么需要在滿足最大切割條件的基礎上最大化使用次數，并從 中去除相應內容。當 個切割模式補充完整后，將 中的剩余內容按照FFD算法進行組合并添加到個體中。

3.3 遺傳算子

3.3.1選擇算子

使用隨機競爭選擇算子[2]。首先采用輪盤賭的方式選擇2個個體，然后根據適應度大小選擇更好的個體，不斷選擇直到滿足種群數量需求。該算子能夠有效減緩早熟收斂現象。

3.3.2 交叉算子

為將個體中的優秀基因遺傳下去，在選擇2個個體后，采用類似順序交叉策略的方式[15-16]。首先隨機選擇個體上的2個點，然后將2點之間的基因片段中不存在另一個個體中的基因放到前面，并將相同基因（切割模式）的使用次數進行替換。通過該方式既可以將優秀基因遺傳下去，又可以嘗試新的基因組合。

3.3.3 變異算子

對各切割模式的使用次數進行隨機變異，變異范圍從 ，其中［」表示下界， d 為各種邊框材需求的數量， 為第 k 種切割模式下各邊框材的生產數量。該算子主要是為了嘗試不同比例的切割模式組合。

3.4 修正策略

在經過交叉和變異操作后，生成的個體無法保證滿足需求約束。為此設計了一種修正策略，使得個體可以滿足需求約束。

流程如圖4所示，每次僅修正一種邊框材。從第1列 k = 0 開始，計算能夠生成的邊框材數量 p = ，并與需求數量 進行比較，當滿足需求約束的時候存在2種情況。一是在統計當前切割模式后，剛好滿足數量需求 此時令后續所有模式相應的 。二是統計切割模式后 ，為滿足需求約束時不破壞其他種類邊框材數量關系，首先對當前切割模式進行復制，然后最大化當前模式的使用次數，更新 。并對復制后的內容 進行調整，最后令后續 并且將 添加到個體中。在修正過程中，需要及時刪除不能產生邊框材的切割模式，以減少計算和存儲成本。

上述步驟后，可能某類邊框材數量少于需求個數。為此采用FFD算法對缺少的邊框材進行規劃并補充到個體中。在完成修正后，部分模式可能不滿足最大切割條件，可通過啟發式策略進行調整。

4 仿真試驗對比與分析

本研究通過Python實現算法，計算機的配置為Intel（R）Core（TM）i7-7700HQCPU@2.8GHz，內存為 。遺傳算法相關參數設置見表1。

4.1 試驗數據

為驗證本研究設計算法的性能，搜索相關文獻的算例。具體算例數據見表2。此外，采集了2組被動式

木窗邊框材下料的實際數據，該數據規模更大，算例數據見表3。表2和表3括號中的數字表示相應長度需要的數量，括號缺省表示數量為1。

4.2 算法對比

使用算例F1和F2對不同算法進行比較。本算法獨立運行20次，單獨運行時間不超過 3 5 s 。試驗結果見表4（粗體數字表示相應評價指標下不同算法對比的最優結果），所提算法在消耗的原料根數上可以達到23和24的理論下界。在算例F1中，相比Exon-AF算法的9138末根余料長度，所提算法將末根余料長度提升至9176。同樣地，在算例F2中，所提算法將末根余料長度從AGPS0算法的6704提升至6888。試驗結果表明，所提算法在計算效率和余料保留方面均表現出較高的能力。

4.3 實際應用

將基于CPLEX求解器[17]實現的列生成算法的結果作為基準，并與企業提供的下料軟件優化結果進行對比。獨立運行20次，單獨運行時間不超過 5 0 s 。結果見表5（粗體數字表示相應評價指標下不同算法對比的最優結果），在算例S1中，所提算法能夠達到139根原料的理論下界，而企業軟件未能達到該值。同時，末根余料長度相比CPLEX求解器的718，提升至1461.1。在算例S2中，所提算法的末根余料長度相較于CPLEX求解器和企業軟件，提升至4350，除末根外的平均利用率達到 9 9 . 6 6 % 。試驗結果表明，本研究所提算法相比企業現有軟件具備更好的求解能力，有助于進一步減少實際生產中的浪費，降低原料成本。

5結論

針對被動式邊框材下料問題，基于遺傳算法，通過矩陣表示改進個體編碼方式。同時，提出一種啟發式策略和修正策略，以實現個體修正和種群進化。在2個文獻算例上的運行結果表明，所提算法能夠達到理論下界，除末根外的平均利用率均在 9 9 % ，末根余料長度也優于文中提及的其他算法。與企業現有軟件的優化結果進行比較，所提算法在2個實際算例中均達到了理論下界，并且在除末根外的平均利用率上分別達到99. 4 9 % 和99. 6 6 % ，顯著優于企業現有軟件的計算結果。結果表明，本研究所提算法具備較高的求解和余料保留能力，優于企業現有軟件，能夠在工程實踐中提供更有效的解決方案。本研究所提算法通過Py-thon實現，未來可以基于 C / C + + 和并行計算技術提高計算效率，并且可以考慮將該算法用于多尺寸下料以及多維下料問題。

參考文獻

[1]ZHENG L，MUELLER M，LUO C，et al.Variations in whole-life carbon emissions of similar buildings in proximity：Ananalysisof145 residential properties in Cornwall， UK[J]. Energy and Buildings，2023，296：113387.

[2]RAVELOSV，MENESESCN，SANTOSMO.Meta-heuristics for the one-dimensional cutting stock problem with usable leftover[J]. Journal of Heuristics，2O2O，26（4）： 585-618.

[3] GILMORE P C，GOMORY R E.A linear programming approach to the cuting-stock problem[J]. Operations Research，1961，9（6） ：849-859.

[4] GILMORE P C， GOMORY R E. A linear programming approach to the cutting stock problem—Part II [J].Operations Research，1963，11（6）：863-1025.

[5]BELOV G，SCHEITHAUER G.A branch-and-cut-andprice algorithm for one-dimensional stock cuting and twodimensional two-stage cutting[Jl.European Journal of Operational Research，2006，171（1） ：85-106.

[6] CHEN Y H，HUANG HC，CAI HY，et al. A genetic algorithm approach for the multiple length cutting stock problem[C]/2019 IEEE 1st Global Conference on Life Sciencesand Technologies（LifeTech）.IEEE，2019： 162-165.

[7] JOHNSON D S，DEMERS A，ULLMAN JD，et al. Worstcase performance bounds for simple one-dimensional packing algorithms[J].SIAM Journal on Computing，1974，3 （4）：299-325.

[8]BAKER B S，COFFMAN E G.A tight asymptotic bound for next-fit-decreasing bin-packing[J]. SIAM Journal on Algebraic Discrete Methods，1981，2（2）：147-152.

[9] CAMPELLO B S C，GHIDINI C TL S，AYRES A O C，et al.A residual recombination heuristic for one-dimensional cutting stock problems[J].Top，2022，30（1） ：194-220.

[10]沈顯君，楊進才，應偉勤，等．一維下料問題的自適應 廣義粒子群優化求解[J].華南理工大學學報（自然科 學版），2007，35（9）：113-117. SHEN X J，YANG JC， YING W Q，et al. Adaptive general particle swarm optimization for one-dimension cutting stock problem[Jl. Journal of South China University of Technology（Natural Science Edition），2007，35（9）： 113-117. 法[J].華南理工大學學報（自然科學版），2003，31（6）： 26-30. WEI L L， YE J W. Modified adaptive genetic algorithm for one-dimensional cutting problem[J]. Journal of South China University of Technology （Natural Science Edition），2003，31（6）：26-30.

[12]侯改，何朗，黃樟燦，等.基于差分進化的金字塔演化 策略求解一維下料問題[J].計算機科學，2020，47（7）： 166-170. HOUG，HE L，HUANG Z C，et al. Pyramid evolution strategy based on differential evolution for solving one-dimensional cutting stock problem [Jl. Computer Science， 2020，47（7） ：166-170.

[13]丁為.線材下料優化問題建模與混合求解算法研究 [D].武漢：華中科技大學，2022. DING W. Research on modeling and hybrid solving algorithms for wire cutting stock optimization problem[D]. Wuhan：Huazhong University of Science and Technology， 2022.

[14]ALAMT，QAMARS，DIXITA，et al. Genetic algorithm： Reviews，implementations，and applications[Jl.arXiv preprint arXiv：2007.12673，2020.

[15]李培勇，王全華，裘泳銘.型材優化下料的混合遺傳算 法[J].上海交通大學學報，2001，35（10）：1557-1560. LIPY，WANGQH，QIUYM.Optimizationforone-dimensional cutting using hybrid genetic algorithm[Jl. Journal of Shanghai Jiao Tong University，2OO1，35（10）： 1557-1560.

[16]李斌，賀飛.求解一維下料問題的改進混合遺傳算法 [J].內蒙古大學學報（自然科學版），2014，45（3）： 245-250. LIB，HE F. Improved hybrid genetic algorithm for one-dimensional cuting stock problem[Jl.Journal of Inner Mongolia University （Natural Science Edition），2014，45 （3）：245-250.

[17] LU Y，VASKO F J.A Comprehensive empirical demonstration of the impact of choice constraints on solving generalizations of the O-1 knapsack problem using the integer programming option of CPLEX@[J]. Engineering Optimization，2020，52（9）：1632-1644.