计算机科学 ›› 2020, Vol. 47 ›› Issue (11A): 119-125.doi: 10.11896/jsjkx.200200016
郭超1,2, 王磊1,2, 尹爱华3
GUO Chao1,2, WANG Lei1,2, YIN Ai-hua3
摘要： 一刀切式二维矩形Strip Packing问题是一种NP难度问题。问题的实用背景是诸如玻璃板材切割、集成电路布局等工业生产中,需要优化布局和切割方案以提高利用率。总体框架是首先针对二维矩形Packing问题提出混合搜索算法,然后采用跳跃式查找与折半查找相结合的方式,将混合搜索算法用于求解二维矩形Strip Packing问题。从拟人途径提出占角、动作空间、极高度、组合拼凑等基本定义以及基本算法。以基本算法为基础,混合搜索算法分为3个阶段:第一阶段生成初始解。第二阶段调用邻域搜索子程序对矩形块的优先级进行调整。当邻域搜索遇到局部最优解时,采用基于随机扰动的跳坑策略子程序跳出局部最优陷阱,并在新区域继续搜索。第三阶段调用优美度枚举子程序对占角动作的选择进行优化。混合搜索算法计算了2组共91个benchmark实例,并将其计算结果与SPTRS算法进行了比较。SPTRS算法计算结果的平均相对误差是4.26%,混合搜索算法计算结果的平均相对误差是3.83%。因此,混合搜索算法是一种求解一刀切式二维矩形Strip Packing问题的高效启发式算法。
中图分类号:
| [1] LODI A,MARTELLO S,VIGO D.Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems [J].INFORMS Journal on Computing,1999,11(4):345-357. [2] MARTELLO S,MONACI M,VIGO D.An exact approach tothe strip packing problem [J].INFORMS Journal on Computing,2003,15(3):310-319. [3] JIANG X B,L X Q,LIU C C.Lowest-level left align best-fit algorithm for the 2D rectangular strip packing problem [J].Journal of Software,2009,20(6):1528-1538. [4] CUI Y D,YANG Y L,CHENG X,et al.A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem [J].Computers & Operations Research,2008,35(4):1281-1291. [5] HUANG W Q,CHEN D B,XU R C.A new heuristic algorithm for rectangle packing [J].Computers & Operations Research,2007,34(11):3270-3280. [6] HUANG W Q,CHEN D B.An efficient heuristic algorithm for rectangle-packing problem [J].Simulation Modelling and Practice Theory,2007,15(10):1356-1365. [7] HE K,HUANG W Q,JIN Y.Efficient algorithm based on action space for solving the 2D rectangular packing problem [J].Journal of Software,2012,23(5):1037-1044. [8] WANG L,YIN A H.A beauty degree enumeration algorithm for the 2D rectangular packing problem [J].Scientia Sinica Informationis,2015,45(9):1127-1140. [9] HUANG W Q,HE K.A pure quasi-human algorithm for solving the cuboid packing problem [J].Science China Series F:Information Sciences,2009,52(1):52-58. [10] HE K,HUANG W Q.An efficient place heuristic for three-dimensional rectangular packing [J].Computers & Operations Research,2011,38(1):227-233. [11] ZHANG D F,SHI L Y,LEUNG S C H,et al.A priority heuristic for the guillotine rectangular packing problem [J].Information Processing Letters,2016,116(1):15-21. [12] BORTFELDT A,JUNGMANN S.A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint [J].Annals of Operations Research,2012,196(1):53-71. [13] ALVAREZ-VALDES R,PARRENO F,TAMMRIT J M.Reactive GRASP for the strip-packing problem [J].Computers & Operations Research,2008,35(4):1065-1083. [14] LEUNG S C H,ZHANG D F.A two-stage intelligent search algorithm for the two-dimensional strip packing problem [J].European Journal of Operational Research,2011,215(1):57-69. [15] WEI L J,OON W C,ZHU W B,et al.A skyline heuristic for the 2D rectangular packing and strip packing problems [J].Euro-pean Journal of Operational Research,2011,215(2):337-346. [16] YANG S Y,HAN S H,YE W G.A simple randomized algorithm for two-dimensional strip packing [J].Computers & Operations Research,2013,40(1):1-8. [17] WEI L J,QIN H,CHEANG B,et al.An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem [J].International Transactions in Operational Research,2016,232(1/2):65-92. [18] ZHANG D F,CHE Y X,YE F R,et al.A hybrid algorithm based on variable neighborhood for the strip packing problem [J].Journal of Combinatorial Optimization,2016,32(2):513-530. [19] BORTFELDT A.A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces [J].European Journal of Operational Research,2006,172(3):814-837. [20] HE K,HUANG W Q,JIN Y.An efficient deterministic heuristic for two-dimensional rectangular packing [J].Computers & Operations Research,2012,39(7):1355-1363. [21] DENG J K,WANG L,YIN A H.A quasi-human global optimization algorithm for solving the two dimensional rectangular packing problem [J].Computer Engineering & Science,2018,40(2):331-340. [22] WANG L,YIN A H.A quasi-human algorithm for the two dimensional rectangular strip packing problem:in memory of Prof.Wenqi Huang [J].Journal of Combinatorial Optimization,2016,32(2):416-444. [23] HOPPER E,TURTON B C H.An empirical investigation ofmeta-heuristic and heuristic algorithm for a 2D packing problem [J].European Journal of Operational Research,2001,128(1):34-57. |
| [1] | 张露萍, 徐飞. 具有突触规则的脉冲神经膜系统综述 Survey on Spiking Neural P Systems with Rules on Synapses 计算机科学, 2022, 49(8): 217-224. https://doi.org/10.11896/jsjkx.220300078 |
| [2] | 耿海军, 王威, 尹霞. 基于混合软件定义网络的单节点故障保护方法 Single Node Failure Routing Protection Algorithm Based on Hybrid Software Defined Networks 计算机科学, 2022, 49(2): 329-335. https://doi.org/10.11896/jsjkx.210100051 |
| [3] | 郭彪, 唐麒, 文智敏, 傅娟, 王玲, 魏急波. 一种面向动态部分可重构片上系统的列表式软硬件划分算法 List-based Software and Hardware Partitioning Algorithm for Dynamic Partial Reconfigurable System-on-Chip 计算机科学, 2021, 48(6): 19-25. https://doi.org/10.11896/jsjkx.200700198 |
| [4] | 刘忠慧, 赵琦, 邹璐, 闵帆. 三元概念的启发式构建及其在社会化推荐中的应用 Heuristic Construction of Triadic Concept and Its Application in Social Recommendation 计算机科学, 2021, 48(6): 234-240. https://doi.org/10.11896/jsjkx.200500136 |
| [5] | 郭启程, 杜晓玉, 张延宇, 周毅. 基于改进鲸鱼算法的无人机三维路径规划 Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm 计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021 |
| [6] | 唐文君, 刘岳, 陈荣. 移动边缘计算中的动态用户分配方法 User Allocation Approach in Dynamic Mobile Edge Computing 计算机科学, 2021, 48(1): 58-64. https://doi.org/10.11896/jsjkx.200900079 |
| [7] | 郭飞雁, 唐兵. 基于用户延迟感知的移动边缘服务器放置方法 Mobile Edge Server Placement Method Based on User Latency-aware 计算机科学, 2021, 48(1): 103-110. https://doi.org/10.11896/jsjkx.200900146 |
| [8] | 张玉琴, 张建亮, 冯向东. 一种无约束优化的无参数填充函数算法 Parametric-free Filled Function Algorithm for Unconstrained Optimization 计算机科学, 2020, 47(6A): 54-57. https://doi.org/10.11896/JsJkx.191000179 |
| [9] | 冯炳超, 吴璟莉. 求解自行车共享系统静态再平衡问题的单亲遗传算法 Partheno-genetic Algorithm for Solving Static Rebalance Problem of Bicycle Sharing System 计算机科学, 2020, 47(6A): 114-118. https://doi.org/10.11896/JsJkx.190700120 |
| [10] | 张旭, 王莉莉, 杨博韬. 带有一刀切约束的二维非规则装箱算法 Heuristic Algorithms for Two-dimensional Irregular Bin Packing Problem with GuillotineConstraints 计算机科学, 2020, 47(5): 212-216. https://doi.org/10.11896/jsjkx.190400078 |
| [11] | 潘恒, 李景峰, 马君虎. 可抵御内部威胁的角色动态调整算法 Role Dynamic Adjustment Algorithm for Resisting Insider Threat 计算机科学, 2020, 47(5): 313-318. https://doi.org/10.11896/jsjkx.190800051 |
| [12] | 杨婷, 罗飞, 丁炜超, 卢海峰. 一种自适应优化松弛量的装箱算法 Bin Packing Algorithm Based on Adaptive Optimization of Slack 计算机科学, 2020, 47(4): 211-216. https://doi.org/10.11896/jsjkx.190500132 |
| [13] | 李章维,王柳静. 基于群体分布的自适应差分进化算法 Population Distribution-based Self-adaptive Differential Evolution Algorithm 计算机科学, 2020, 47(2): 180-185. https://doi.org/10.11896/jsjkx.181202356 |
| [14] | 罗飞, 任强, 丁炜超, 卢海峰. 基于最小松弛量的启发式一维装箱算法 Heuristic One-dimensional Bin Packing Algorithm Based on Minimum Slack 计算机科学, 2019, 46(9): 315-320. https://doi.org/10.11896/j.issn.1002-137X.2019.09.048 |
| [15] | 宋鑫,朱宗良,高银萍,苌道方. 动态阈值结合全局优化的船舶AIS轨迹在线压缩算法 Vessel AIS Trajectory Online Compression Algorithm Combining Dynamic Thresholding and Global Optimization 计算机科学, 2019, 46(7): 333-338. https://doi.org/10.11896/j.issn.1002-137X.2019.07.051 |
|
||
首页