计算机科学 ›› 2020, Vol. 47 ›› Issue (5): 212-216.doi: 10.11896/jsjkx.190400078
张旭, 王莉莉, 杨博韬
ZHANG Xu, WANG Li-li, YANG Bo-tao
摘要： 针对切割下料领域的二维非规则一刀切装箱问题,首先给出了最小移动距离的定义,然后给出了一种基于最大移动距离的启发式算法。该算法通过计算一个凸多边形滑动至另一个凸多边形内部所允许的最大移动距离,对待排件的摆放位置进行一次性定位,避免使用传统的NFP(Not-Fit-Polygon)预判交方法,极大地缩短了排样的整体时间,最后使用模拟退火算法对下料流程进行了优化,改善了排样结果。
中图分类号:
| [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] | 耿海军, 王威, 尹霞. 基于混合软件定义网络的单节点故障保护方法 Single Node Failure Routing Protection Algorithm Based on Hybrid Software Defined Networks 计算机科学, 2022, 49(2): 329-335. https://doi.org/10.11896/jsjkx.210100051 |
| [2] | 刘忠慧, 赵琦, 邹璐, 闵帆. 三元概念的启发式构建及其在社会化推荐中的应用 Heuristic Construction of Triadic Concept and Its Application in Social Recommendation 计算机科学, 2021, 48(6): 234-240. https://doi.org/10.11896/jsjkx.200500136 |
| [3] | 郭启程, 杜晓玉, 张延宇, 周毅. 基于改进鲸鱼算法的无人机三维路径规划 Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm 计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021 |
| [4] | 郭飞雁, 唐兵. 基于用户延迟感知的移动边缘服务器放置方法 Mobile Edge Server Placement Method Based on User Latency-aware 计算机科学, 2021, 48(1): 103-110. https://doi.org/10.11896/jsjkx.200900146 |
| [5] | 杨婷, 罗飞, 丁炜超, 卢海峰. 一种自适应优化松弛量的装箱算法 Bin Packing Algorithm Based on Adaptive Optimization of Slack 计算机科学, 2020, 47(4): 211-216. https://doi.org/10.11896/jsjkx.190500132 |
| [6] | 郭超, 王磊, 尹爱华. 求解一刀切式二维矩形Strip Packing问题的混合搜索算法 Hybrid Search Algorithm for Two Dimensional Guillotine Rectangular Strip Packing Problem 计算机科学, 2020, 47(11A): 119-125. https://doi.org/10.11896/jsjkx.200200016 |
| [7] | 罗飞, 任强, 丁炜超, 卢海峰. 基于最小松弛量的启发式一维装箱算法 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 |
| [8] | 张澍裕, 宫达, 谢兵, 刘开贵. 基于实时GPS的公交短时动态调度算法 Bus Short-term Dynamic Dispatch Algorithm Based on Real-time GPS 计算机科学, 2019, 46(6A): 497-501. |
| [9] | 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法 Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading 计算机科学, 2018, 45(4): 94-99. https://doi.org/10.11896/j.issn.1002-137X.2018.04.014 |
| [10] | 单天羽, 管煜旸. 基于种群多样性的可变种群缩减差分进化算法 Differential Evolution Algorithm with Adaptive Population Size Reduction Based on Population Diversity 计算机科学, 2018, 45(11A): 160-166. |
| [11] | 李美争,李磊军,米据生,解滨. 概念格中基于粗糙熵的属性约简方法 Rough Entropy Based Algorithm for Attribute Reduction in Concept Lattice 计算机科学, 2018, 45(1): 84-89. https://doi.org/10.11896/j.issn.1002-137X.2018.01.013 |
| [12] | 殷晓波,罗恩. 一种松弛的优化均衡流式图划分算法研究 Relaxed Optimal Balanced Streaming Graph Partitioning Algorithm 计算机科学, 2016, 43(4): 231-234. https://doi.org/10.11896/j.issn.1002-137X.2016.04.047 |
| [13] | 陈小潘,孔云峰,郑泰皓,郑珊珊. 需求可拆分校车路径问题的元启发式算法 Metaheuristic Algorithm for Split Demand School Bus Routing Problem 计算机科学, 2016, 43(10): 234-241. https://doi.org/10.11896/j.issn.1002-137X.2016.10.045 |
| [14] | 杨光,曾斌. 一种面向可靠传输的数据链中继策略研究 Research on Reliability-aware Relay Strategy in Data Link 计算机科学, 2015, 42(Z11): 253-257. |
| [15] | 柳斌,周丽娟. 一种基于IP地址随机测度的P2P主机识别算法 Heuristic Method for Identifying P2P Application Based on IP Address Entropy 计算机科学, 2014, 41(Z6): 300-302. |
|
||
首页