Computer Science

Computer Science ›› 2020, Vol. 47 ›› Issue (5): 212-216.doi: 10.11896/jsjkx.190400078

• Artificial Intelligence • Previous Articles     Next Articles

Heuristic Algorithms for Two-dimensional Irregular Bin Packing Problem with GuillotineConstraints

ZHANG Xu, WANG Li-li, YANG Bo-tao   

  1. School of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China
  • Received:2019-04-12 Online:2020-05-15 Published:2020-05-19
  • About author:ZHANG Xu,born in 1994,postgra-duate.His main research interests include packing algorithm and so on.
    WANG Li-li,born in 1980,Ph.D,professor,is a member of China Computer Federation.Her main research interests include detection and imaging,pattern recognition.
  • Supported by:
    This work was supported by the Young Scientists Fund of the National Natural Science Foundation of China(61602133)

PDF (PC)

1062

Abstract: Aiming at the two-dimensional irregular packing problem with guillotine constraint in the cutting field,the definition of minimum moving distance is given firstly,and a heuristic algorithm based on maximum moving distance is proposed.The algorithm calculates the maximum moving distance needed for a convex polygon to slide into the interior of another convex polygon.The disposable positioning of the layout position avoids using the traditional NFP intersection method,and simulated annealing algorithm is used to optimize the packing process,which greatly reduces the overall time consumption of layout and meets the high requirements on layout results.

Key words: Guillotine, Heuristic algorithm, Two-dimensional irregular bin packing

CLC Number: 

  • TH164
[1]HAN W,BENNELL J A,ZHAO X,et al.Construction heuristics for two-dimensional irregular shape bin packing with guillotine constraints[J].European Journal of Operational Research,2013,230(3):495-504.
[2]HUANG H B,JIANG W D.Study on 2-D irregular packing[J].Guanxi Kexueyuan Xuebao,2004,20(4):225-227.
[3]CLAUTIAUX F,JOUGLET A,MOUKRIM A.A New Graph-Theoretical Model for k-Dimensional Guillotine-Cutting Problems[C]//International Conference on Experimental Algorithms.2008.
[4]AMOSSEN R R,PISINGER D.Multi-dimensional bin packing problems with guillotine constraints[J].Computers and Operations Research,2010,37(11):1999-2006.
[5]LI H S.Recursive Algorithm Applied Study on a Single Rectangle Blanks Unconstrained Optimal Layout[J].Journal of Chongqing University of Technology(Natural Science),2017,31(9):125-131.
[6]SWEENEY P E,PATERNOSTER E R.Cutting and PackingProblems:A Categorized,Application-Orientated Research Biblio-graphy[J].Journal of the Operational Research Society,1992,43(7):691-706.
[7]CARVALHO J M V D,RODRIGUES A J G.An LP-based Approach to a Two-stage Cutting Stock Problem[J].European Journal of Operational Research,1995,84(3):580-589.
[8]DOWSLAND K A,DOWSLAND W B.Solution Approaches to Irregular Nesting Problems[J].European Journal of Operational Research,1995,84(3):506-521.
[9]SWEENEY P E,PATERNOSTER E R.Cutting and PackingProblems:A Categorized,Application-Orientated Research Biblio-graphy[J].Journal of the Operational Research Society,1992,43(7):691-706.
[10]WANG H,LIN F,ZHANG Y W.Research on Trajectory Tracking Control of Self-Driving Vehicle Based on Simulated Annealing Algorithm[J].Journal of Chongqing University of Technology(Natural Science),2015,29(11):106-111,119.
[11]SHPITALNI M,MANEVICH V.Optimal Orthogonal Subdivision of Rectangular Sheets[J].Journal of Manufacturing Science &Engineering,1996,118(3):281-288.
[12]CARVALHO J M V D,RODRIGUES A J G.An LP-based Approach to a Two-stage Cutting Stock Problem[J].European Journal of Operational Research,1995,84(3):580-589.
[13]THEODORACATOS V E,GRIMSLEY J L.The Optimal Pac-king of Arbitrarily-Shaped Polygons Using Simulated Annealing and Polynomial-Time Cooling Schedules[J].Computer Methods in Applied Mechanics & Engineering,1995,125(1/2/3/4):53-70.
[14]MARTINEZ-SYKORA A,ALVAREZ-VALDES R,BENNELL J,et al.Constructive procedures to solve 2-dimensional bin pac-king problems with irregular pieces and guillotine cuts[J].Omega,2015,52:15-32.
[15] HAN W,ZHANG Z C.A Simulated Anneal algorithm for Irre-gular Guillotine Packing Problems[J].China Mechanical Engineering,2016,27(24):3326-3331.
[1] GENG Hai-jun, WANG Wei, YIN Xia. Single Node Failure Routing Protection Algorithm Based on Hybrid Software Defined Networks [J]. Computer Science, 2022, 49(2): 329-335.
[2] LIU Zhong-hui, ZHAO Qi, ZOU Lu, MIN Fan. Heuristic Construction of Triadic Concept and Its Application in Social Recommendation [J]. Computer Science, 2021, 48(6): 234-240.
[3] GUO Qi-cheng, DU Xiao-yu, ZHANG Yan-yu, ZHOU Yi. Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm [J]. Computer Science, 2021, 48(12): 304-311.
[4] GUO Fei-yan, TANG Bing. Mobile Edge Server Placement Method Based on User Latency-aware [J]. Computer Science, 2021, 48(1): 103-110.
[5] YANG Ting, LUO Fei, DING Wei-chao, LU Hai-feng. Bin Packing Algorithm Based on Adaptive Optimization of Slack [J]. Computer Science, 2020, 47(4): 211-216.
[6] GUO Chao, WANG Lei, YIN Ai-hua. Hybrid Search Algorithm for Two Dimensional Guillotine Rectangular Strip Packing Problem [J]. Computer Science, 2020, 47(11A): 119-125.
[7] LUO Fei, REN Qiang, DING Wei-chao, LU Hai-feng. Heuristic One-dimensional Bin Packing Algorithm Based on Minimum Slack [J]. Computer Science, 2019, 46(9): 315-320.
[8] ZHANG Shu-yu, DONG Da, XIE Bing, LIU Kai-gui. Bus Short-term Dynamic Dispatch Algorithm Based on Real-time GPS [J]. Computer Science, 2019, 46(6A): 497-501.
[9] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading [J]. Computer Science, 2018, 45(4): 94-99.
[10] SHAN Tian-yu, GUAN Yu-yang. Differential Evolution Algorithm with Adaptive Population Size Reduction Based on Population Diversity [J]. Computer Science, 2018, 45(11A): 160-166.
[11] LI Mei-zheng, LI Lei-jun, MI Ju-sheng and XIE Bin. Rough Entropy Based Algorithm for Attribute Reduction in Concept Lattice [J]. Computer Science, 2018, 45(1): 84-89.
[12] YIN Xiao-bo and LUO En. Relaxed Optimal Balanced Streaming Graph Partitioning Algorithm [J]. Computer Science, 2016, 43(4): 231-234.
[13] CHEN Xiao-pan, KONG Yun-feng, ZHENG Tai-hao and ZHENG Shan-shan. Metaheuristic Algorithm for Split Demand School Bus Routing Problem [J]. Computer Science, 2016, 43(10): 234-241.
[14] YANG Guang and ZENG Bin. Research on Reliability-aware Relay Strategy in Data Link [J]. Computer Science, 2015, 42(Z11): 253-257.
[15] WANG Jun,YU Wei,HU Ya-hui and LI Shi-jun. Heuristic Algorithm Based on 3-layer Centrality for Influence Maximization in Social Networks [J]. Computer Science, 2014, 41(1): 59-63.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.