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 条
  • [21] Hierarchical Search-Embedded Hybrid Heuristic Algorithm for Two-Dimensional Strip Packing Problem
    Chen, Mengfan
    Li, Kai
    Zhang, Defu
    Zheng, Ling
    Fu, Xin
    IEEE ACCESS, 2019, 7 : 179086 - 179103
  • [22] A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem
    José Fernando Gonçalves
    Mauricio G. C. Resende
    Journal of Combinatorial Optimization, 2011, 22 : 180 - 201
  • [23] A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem
    Goncalves, Jose Fernando
    Resende, Mauricio G. C.
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2011, 22 (02) : 180 - 201
  • [24] A Crow Search-Based Genetic Algorithm for Solving Two-Dimensional Bin Packing Problem
    Laabadi, Soukaina
    Naimi, Mohamed
    El Amri, Hassan
    Achchab, Boujemaa
    ADVANCES IN ARTIFICIAL INTELLIGENCE, KI 2019, 2019, 11793 : 203 - 215
  • [25] A backtracking heuristic algorithm for two-dimensional strip packing with rotation
    Li, Li
    Liu, Baoguo
    Wu, Zhaoyun
    SCIENCE PROGRESS, 2025, 108 (01)
  • [26] Efficient Packing of 2D Irregular Parts: A Hybrid Approach Incorporating a Modified Genetic Algorithm and Image Processing
    Meng, Longhui
    Ding, Liang
    Mushtaq, Ray Tahir
    Anwar, Saqib
    Khan, Aqib Mashood
    MATHEMATICS, 2024, 12 (22)
  • [27] Hybrid of Linear Programming and Genetic Algorithm for optimizing Agent-based Simulation. Application to Optimization of Sign Placement for Tsunami Evacuation
    Van-Minh Le
    Chevaleyre, Yann
    Ho Tuong Vinh
    Zucker, Jean-Daniel
    2015 IEEE RIVF INTERNATIONAL CONFERENCE ON COMPUTING & COMMUNICATION TECHNOLOGIES - RESEARCH, INNOVATION, AND VISION FOR THE FUTURE (RIVF), 2015, : 138 - 143
  • [28] An exact approach for the two-dimensional strip packing problem with defects
    Yao, Shaowen
    Zhang, Hao
    Wei, Lijun
    Liu, Qiang
    COMPUTERS & INDUSTRIAL ENGINEERING, 2025, 200
  • [29] Hybrid Approach for 2D Strip Packing Problem Using Genetic Algorithm
    Thomas, Jaya
    Chaudhari, Narendra S.
    ADVANCES IN COMPUTATIONAL INTELLIGENCE, PT I, 2013, 7902 : 566 - 574
  • [30] DC Programming and DCA for Large-Scale Two-Dimensional Packing Problems
    Ndiaye, Babacar Mbaye
    Le Thi Hoai An
    Pham Dinh Tao
    Niu, Yi Shuai
    INTELLIGENT INFORMATION AND DATABASE SYSTEMS (ACIIDS 2012), PT II, 2012, 7197 : 321 - 330