Optimizing Two-Dimensional Irregular Packing: A Hybrid Approach of Genetic Algorithm and Linear Programming

被引:3
|
作者
Liu, Cheng [1 ]
Si, Zhujun [1 ]
Hua, Jun [1 ]
Jia, Na [1 ]
机构
[1] Northeast Forestry Univ, Coll Mech & Elect Engn, Harbin 150040, Peoples R China
来源
APPLIED SCIENCES-BASEL | 2023年 / 13卷 / 22期
关键词
two-dimensional irregular packing; genetic algorithm; linear programming; no-fit-polygon; hybrid placement strategy; STRIP PACKING;
D O I
10.3390/app132212474
中图分类号
O6 [化学];
学科分类号
0703 ;
摘要
The problem of two-dimensional irregular packing involves the arrangement of objects with diverse shapes and sizes within a given area. This challenge arises across various industrial sectors, where effective packing optimization can yield cost savings, enhanced productivity, and reduced material waste. Existing methods for addressing the two-dimensional irregular packing problem encounter several challenges, such as limited computing resources, a prolonged solving time, and the propensity to converge to local optima. To address this issue, this study proposes a hybrid algorithm called the GA-LP algorithm to optimize the two-dimensional irregular packing problem in the manufacturing industry. The algorithm combines the global search capability of a genetic algorithm with the precise solving characteristics of linear programming. Matheuristics merges the advantages of metaheuristics, such as genetic algorithms, and mathematical programming, such as linear programming. The algorithm employs the no-fit-polygon technique along with the bottom-left and lowest-gravity center mixing placement strategies to acquire an initial solution via the utilization of a genetic algorithm. The algorithm then optimizes the solution obtained by the genetic algorithm using linear programming to obtain the final packing result. Experimental results, drawn from a real case involving the European Special Interest Group on Cutting and Packing (ESICUP) demonstrate that the GA-LP algorithm outperforms two hybrid algorithms from the relevant literature. Compared with recent methods, this algorithm can increase the best and average utilization rates by up to 5.89% and 4.02%, respectively, with important implications for improving work quality in areas such as packing and cutting.
引用
收藏
页数:20
相关论文
共 50 条
  • [41] Multi-reservoir operation planning using hybrid genetic algorithm and linear programming (GA-LP): An alternative stochastic approach
    Reis, LFR
    Walters, GA
    Savic, D
    Chaudhry, FH
    WATER RESOURCES MANAGEMENT, 2005, 19 (06) : 831 - 848
  • [42] Multi-Reservoir Operation Planning Using Hybrid Genetic Algorithm and Linear Programming (GA-LP): An Alternative Stochastic Approach
    L. F. R. Reis
    G. A. Walters
    D. Savic
    F. H. Chaudhry
    Water Resources Management, 2005, 19 : 831 - 848
  • [43] Two Dimensional Rectilinear Polygon Packing using Genetic Algorithm with a Hierarchical Chromosome
    Matayoshi, Mitsukuni
    2011 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN, AND CYBERNETICS (SMC), 2011, : 989 - 996
  • [44] A Genetic Algorithm for Sensor Deployment Based on Two-Dimensional Operators
    Seo, Jae-Hyun
    Kim, Yong-Hyuk
    Ryou, Hwang-Bin
    Kang, Seok-Joong
    APPLIED COMPUTING 2008, VOLS 1-3, 2008, : 1812 - 1813
  • [45] Solving nonlinear water management models using a combined genetic algorithm and linear programming approach
    Cai, XM
    McKinney, DC
    Lasdon, LS
    ADVANCES IN WATER RESOURCES, 2001, 24 (06) : 667 - 676
  • [46] A genetic algorithm for the two-dimensional knapsack problem with rectangular pieces
    Bortfeldt, Andreas
    Winter, Tobias
    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2009, 16 (06) : 685 - 713
  • [47] Design optimization of a two-dimensional hydrofoil by applying a genetic algorithm
    Ouyang, H
    Weber, LJ
    Odgaard, AJ
    ENGINEERING OPTIMIZATION, 2006, 38 (05) : 529 - 540
  • [48] An Effective Corner Increment-Based Algorithm for the Two-Dimensional Strip Packing Problem
    Chen, Zhen
    Chen, Jianli
    IEEE ACCESS, 2018, 6 : 72906 - 72924
  • [49] Enhancing the Efficiency of Heuristic Placement Algorithm for Two-dimensional Orthogonal Knapsack Packing Problem
    Shiangjen, Kanokwatt
    Chaijaruwanich, Jeerayut
    Srisujjalertwaja, Wijak
    Somhom, Samerkae
    PROCEEDINGS OF 2015 6TH IEEE INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING AND SERVICE SCIENCE, 2015, : 33 - 36
  • [50] A new linear programming approach and genetic algorithm for solving airline boarding problem
    Soolaki, Majid
    Mahdavi, Iraj
    Mandavi-Amiri, Nezam
    Hassanzadeh, Reza
    Aghajani, Aydin
    APPLIED MATHEMATICAL MODELLING, 2012, 36 (09) : 4060 - 4072