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 条
  • [31] Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem
    Leung, TW
    Chan, CK
    Troutt, MD
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 145 (03) : 530 - 542
  • [32] A hybrid genetic algorithm with a new packing strategy for the three-dimensional bin packing problem
    Kang, Kyungdaw
    Moon, Ilkyeong
    Wang, Hongfeng
    APPLIED MATHEMATICS AND COMPUTATION, 2012, 219 (03) : 1287 - 1299
  • [33] A New Deterministic Algorithm for Two-dimensional Rectangular Packing Problems based on Polyomino Packing Models
    Hoshi, Fumiya
    Murai, Yasuyuki
    Tsuji, Hiroyuki
    Tokumasu, Shinji
    IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN AND CYBERNETICS (SMC 2010), 2010,
  • [34] Width-Packing Heuristic for Grouping in Two-Dimensional Irregular Shapes Cutting Stock Problem
    Awais, Aliya
    Naveed, Anjum
    ARABIAN JOURNAL FOR SCIENCE AND ENGINEERING, 2015, 40 (03) : 799 - 816
  • [35] A hybrid genetic algorithm/fuzzy dynamic programming approach to two-machine flowshop problems
    Zhang, Hong
    Li, Jun
    Zhang, Desheng
    PROCEEDINGS OF THE 10TH WORLD CONGRESS ON INTELLIGENT CONTROL AND AUTOMATION (WCICA 2012), 2012, : 2399 - 2402
  • [36] A two-stage intelligent search algorithm for the two-dimensional strip packing problem
    Leung, Stephen C. H.
    Zhang, Defu
    Sim, Kwang Mong
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2011, 215 (01) : 57 - 69
  • [37] A genetic algorithm for solving the two-dimensional assortment problem
    Lin, Chang-Chun
    COMPUTERS & INDUSTRIAL ENGINEERING, 2006, 50 (1-2) : 175 - 184
  • [38] Width-Packing Heuristic for Grouping in Two-Dimensional Irregular Shapes Cutting Stock Problem
    Aliya Awais
    Anjum Naveed
    Arabian Journal for Science and Engineering, 2015, 40 : 799 - 816
  • [39] A Memetic Algorithm for the Two-Dimensional Bin-Packing Problem with Partial Conflicts
    Hamdi-Dhaoui, Khaoula
    Labadie, Nacima
    Yalaoui, Alice
    PROCEEDINGS OF INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND SYSTEMS MANAGEMENT (IESM'2011): INNOVATIVE APPROACHES AND TECHNOLOGIES FOR NETWORKED MANUFACTURING ENTERPRISES MANAGEMENT, 2011, : 371 - 379
  • [40] A HYBRID POLYNOMIAL ALGORITHM FOR LINEAR PROGRAMMING
    HUANG Saing(Department of Information and Systems Management
    Systems Science and Mathematical Sciences, 1996, (01) : 67 - 75