基于遗传算法的被动式木窗材下料优化

任长清, 武子棋, 闫杰, 丁星尘, 杨春梅

PDF(1697 KB)
PDF(1697 KB)
森林工程 ›› 2025, Vol. 41 ›› Issue (03) : 595-602. DOI: 10.7525/j.issn.1006-8023.2025.03.016
森工技术与装备

基于遗传算法的被动式木窗材下料优化

作者信息 +

Optimization of Passive Wooden Window Material Cutting Based on Genetic Algorithm

Author information +
History +

摘要

在定制化被动式木窗加工过程中,减少边框材下料过程中的原料浪费是降低成本的关键。为此,将该问题建模为一维下料问题,针对传统遗传算法中个体编码方式在迭代过程中容易导致切割模式被破坏和探索效率低下的问题,提出一种新的个体编码方式,以保护进化过程中切割模式的完整性。同时,设计启发式策略和修正策略,用于个体修正和种群进化。仿真试验表明,在不同算例下,除末根外的原料平均利用率均可达到99%,且末根余料长度相较其他算法也有所提高。在2组企业的实际生产数据中,与企业现有软件相比,该算法不仅达到了理论下界,还在除末根外的平均利用率上分别达到99.49%和99.66%,优于企业软件的计算结果。该算法有助于降低成本,能为工程实践提供可靠的解决方案。

Abstract

In the customization process of passive wooden window manufacturing, reducing material waste during frame cutting is key to cost reduction. This problem is modeled as a one-dimensional cutting stock problem. To address the issue of traditional genetic algorithms where the individual encoding method tends to lead to the destruction of cutting patterns and low exploration efficiency during iterations, a new individual encoding method is proposed to maintain the integrity of cutting patterns throughout the evolutionary process. Additionally, a heuristic strategy and a correction strategy are introduced for individual correction and population evolution. Simulation results show that for different test cases, the average material utilization rate, excluding the last remnants, exceeds 99%, with some improvements in the length of the last remnants compared to other algorithms. For two sets of real production data from enterprises, the proposed algorithm achieves the theoretical lower bound, with average utilization rates (excluding the last remnants) of 99.49% and 99.66%, respectively, outperforming the results of the company's existing software. This demonstrates the algorithm's potential to effectively reduce costs and provide practical solutions in engineering applications.

关键词

一维下料问题 / 遗传算法 / 启发式算法 / 种群编码 / 可用剩余物

Key words

One-dimensional cutting stock problem / genetic algorithm / heuristic algorithm / population encoding / usable leftovers

中图分类号

S777

引用本文

导出引用
任长清 , 武子棋 , 闫杰 , . 基于遗传算法的被动式木窗材下料优化. 森林工程. 2025, 41(03): 595-602 https://doi.org/10.7525/j.issn.1006-8023.2025.03.016
REN Changqing, WU Ziqi, YAN Jie, et al. Optimization of Passive Wooden Window Material Cutting Based on Genetic Algorithm[J]. Forest Engineering. 2025, 41(03): 595-602 https://doi.org/10.7525/j.issn.1006-8023.2025.03.016

参考文献

1
ZHENG L MUELLER M LUO C,et al.Variations in whole-life carbon emissions of similar buildings in proximity:An analysis of 145 residential properties in Cornwall,UK[J].Energy and Buildings2023296:113387.
2
RAVELO S V MENESES C N SANTOS M O.Meta-heuristics for the one-dimensional cutting stock problem with usable leftover[J].Journal of Heuristics202026(4):585-618.
3
GILMORE P C GOMORY R E.A linear programming approach to the cutting-stock problem[J].Operations Research19619(6):849-859.
4
GILMORE P C GOMORY R E.A linear programming approach to the cutting stock problem—Part Ⅱ[J].Operations Research196311(6):863-1025.
5
BELOV G SCHEITHAUER G.A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting[J].European Journal of Operational Research2006171(1):85-106.
6
CHEN Y H HUANG H C CAI H Y,et al.A genetic algorithm approach for the multiple length cutting stock problem[C]//2019 IEEE 1st Global Conference on Life Sciences and Technologies (LifeTech).IEEE,2019:162-165.
7
JOHNSON D S DEMERS A ULLMAN J D,et al.Worst-case performance bounds for simple one-dimensional packing algorithms[J].SIAM Journal on Computing19743(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 Methods19812(2):147-152.
9
CAMPELLO B S C GHIDINI C T L S AYRES A O C,et al.A residual recombination heuristic for one-dimensional cutting stock problems[J].Top202230(1):194-220.
10
沈显君,杨进才,应伟勤,等.一维下料问题的自适应广义粒子群优化求解[J].华南理工大学学报(自然科学版)200735(9):113-117.
SHEN X J YANG J C YING W Q,et al.Adaptive general particle swarm optimization for one-dimension cutting stock problem[J].Journal of South China University of Technology (Natural Science Edition)200735(9):113-117.
11
魏凉良,叶家玮.一维下料问题的改进自适应遗传算法[J].华南理工大学学报(自然科学版)200331(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)200331(6):26-30.
12
侯改,何朗,黄樟灿,等.基于差分进化的金字塔演化策略求解一维下料问题[J].计算机科学202047(7):166-170.
HOU G HE L HUANG Z C,et al.Pyramid evolution strategy based on differential evolution for solving one-dimensional cutting stock problem[J].Computer Science202047(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
ALAM T QAMAR S DIXIT A,et al.Genetic algorithm:Reviews,implementations,and applications[J].arXiv preprint arXiv:2007.12673,2020.
15
李培勇,王全华,裘泳铭.型材优化下料的混合遗传算法[J].上海交通大学学报200135(10):1557-1560.
LI P Y WANG Q H QIU Y M.Optimization for one-dimensional cutting using hybrid genetic algorithm[J].Journal of Shanghai Jiao Tong University200135(10):1557-1560.
16
李斌,贺飞.求解一维下料问题的改进混合遗传算法[J].内蒙古大学学报(自然科学版)201445(3):245-250.
LI B HE F.Improved hybrid genetic algorithm for one-dimensional cutting stock problem[J].Journal of Inner Mongolia University (Natural Science Edition)201445(3):245-250.
17
LU Y VASKO F J.A Comprehensive empirical demonstration of the impact of choice constraints on solving generalizations of the 0-1 knapsack problem using the integer programming option of CPLEX® [J].Engineering Optimization202052(9):1632-1644.

基金

黑龙江省重大成果转化项目(CG23013)

评论

PDF(1697 KB)

Accesses

Citation

Detail

段落导航
相关文章

/