基于轨迹线的临界多边形算法拓展

doi:10.16183/j.cnki.jsjtu.2020.208

摘要/Abstract

摘要：

排料问题是指如何在有限的空间内装下最多指定形状物体的问题,在工业生产中有着重要的意义.其求解需要频繁对物体进行相交校验以判断排料位置是否合法.临界多边形算法可以用于加速相交校验过程,但算法本身不能计算曲线,限制了其应用.一种基于移动碰撞法的临界多边形算法可以将工件轮廓拓展至圆弧,但其计算速度较慢.针对该问题,在基于轨迹线的临界多边形算法的基础上,分析并改进了该算法的轨迹生成策略以及外包络轮廓算法.改进后的算法能够在较短的时间内计算出包含圆弧的临界多边形,同时解决了效率和精度问题.最后,在实际的冲床上进行了加工测试,测试结果验证了算法的正确性与效率.

关键词: 临界多边形, 轨迹线算法, 排料问题

Abstract:

The nesting problem is how to nest objects of a specified shape in a two-dimensional space to obtain the maximum space utilization rate, which is of great significance in industrial production. The solution to the nesting problem requires frequent cross-checking of the objects to determine whether the nesting position is legal. The No Fit Polygon algorithm can be used to accelerate the procedure of cross-checking, but the algorithm cannot be used to calculate shapes containing curves, which limits its application. An algorithm based on orbit sliding can calculate No Fit Polygon between shapes which includes arc, but its effectiveness is not satisfactory. Aimed at this problem, and based on trajectory algorithm, the trajectory generation strategy and the profile algorithm are analyzed and improved. The improved algorithm can calculate the No Fit Polygon between shapes containing arc in a shorter time, solving both accuracy and effectiveness problems. Finally, the algorithm is tested in the real punch production process and the results of the test confirms the correctness and effectiveness of the algorithm.

Key words: No Fit Polygon, trajectory algorithm, nesting problem

中图分类号:

TP391

周鑫, 赖晓阳, 孟祥群, 王堃, 唐厚君. 基于轨迹线的临界多边形算法拓展[J]. 上海交通大学学报, 2021, 55(5): 536-543.

ZHOU Xin, LAI Xiaoyang, MENG Xiangqun, WANG Kun, TANG Houjun. Promotion of a No Fit Polygon Algorithm Based on Trajectory[J]. Journal of Shanghai Jiao Tong University, 2021, 55(5): 536-543.

图/表 15

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

表1

图13

表2

参考文献 14

[1]	ADAMOWICZ M, ALBANO A. Nesting two-dimensional shapes in rectangular modules[J]. Computer-Aided Design, 1976, 8(1):27-33. doi: 10.1016/0010-4485(76)90006-3 URL
[2]	TERRY W, AMICO M D, IORI M. Bin packing problem with general precedence constraints[J]. IFAC-PapersOnLine, 2015, 48(3):2027-2029. doi: 10.1016/j.ifacol.2015.06.386 URL
[3]	MARTELLO S, PISINGER D, VIGO D. The three-dimensional bin packing problem[J]. Operations Research, 2000, 48(2):256-267. doi: 10.1287/opre.48.2.256.12386 URL
[4]	孙佳正. 基于不完整临界多边形的二维排样问题的研究[D]. 上海: 华东师范大学, 2018.
	SUN Jiazheng. Research on 2D Layout problem based on incomplete No-Fit Polygon[D]. Shanghai: East China Normal University, 2018.
[5]	XU J J. An optimization algorithm based on no fit polygon method and hybrid heuristic strategy for irregular nesting problem [C]//The 36th China Control Memories Collection. Dalian: Technical Committee on Control Theory, Chinese Association of Automation, 2017: 1234-1239.
[6]	YANG Q. No Fit Polygon for nesting problem solving with hybridizing ant algorithms[J]. Journal of Software Engineering and Applications, 2014, 7(5):433-439. doi: 10.4236/jsea.2014.75040 URL
[7]	VALVO E L. Meta-heuristic algorithms for nesting problem of rectangular pieces[J]. Procedia Engineering, 2017, 183:291-296. doi: 10.1016/j.proeng.2017.04.041 URL
[8]	杨卫波, 王万良. 改进临界多边形生成算法[J]. 计算机工程与应用, 2013, 49(1):32-35.
	YANG Weibo, WANG Wanliang. Improved algorithm for No-Fit Polygon calculation[J]. Computer Engineering and Applications, 2013, 49(1):32-35.
[9]	杨卫波, 王万良, 张景玲, 等. 基于遗传模拟退火算法的矩形件优化排样[J]. 计算机工程与应用, 2016, 52(7):259-263.
	YANG Weibo, WANG Wanliang, ZHANG Jingling, et al. Packing optimization of rectangles based on improved genetic annealing algorithm[J]. Computer Engineering and Applications, 2016, 52(7):259-263.
[10]	刘海明, 周炯, 吴忻生. 应用临界多边形方法与小生境遗传算法求解不规则排样问题[J]. 小型微型计算机系统, 2016, 37(5):1002-1007.
	LIU Haiming, ZHOU Jiong, WU Xinsheng. Using No Fit Polygon method and niche genetic algorithm to solve irregular layout problems[J]. Small Microcomputer System, 2016, 37(5):1002-1007.
[11]	周炯. 基于临界多边形方法的二维不规则件排样问题及其算法研究[D]. 广州:华南理工大学, 2015.
	ZHOU Jiong. Two-dimensional irregular parts layout problem based on No Fit Polygon method and its algorithm research[D]. Guangzhou: South China University of Technology, 2015.
[12]	汤德佑, 周子琳. 基于临界多边形的不规则件启发式排样算法[J]. 计算机应用, 2016, 36(9):2540-2544.
	TANG Deyou, ZHOU Zilin. No-Fit-Polygon-based heuristic nesting algorithm for irregular shapes[J]. Journal of Computer Applications, 2016, 36(9):2540-2544.
[13]	刘胡瑶, 何援军. 基于轨迹计算的临界多边形求解算法[J]. 计算机辅助设计与图形学学报, 2006, 18(8):1123-1129.
	LIU Huyao, HE Yuanjun. New algorithm for No Fit Polygon calculation[J]. Journal of Computer-Aided Design & Computer Graphics, 2006, 18(8):1123-1129.
[14]	BURKE E K, HELLIER R S R, KENDALL G, et al. Irregular packing using the line and arc No-Fit Polygon[J]. Operations Research, 2010, 58(4):948-970. doi: 10.1287/opre.1090.0770 URL

多边形类别	临界多边形	运行时间/ms		优化效率/%
多边形类别	临界多边形	轨迹线算法	移动碰撞法	优化效率/%
简单凸多边形		0.47	0.55	15.5
凹多边形		9.15	11.21	18.4
扳手		50.91	67.25	24.3
齿轮		167.03	267.68	37.6

序号	板料类型	套料用时/ms		效率提升/%
序号	板料类型	临界多边形相交校验	常规相交校验	效率提升/%
1	眼子料	145.32	208.92	30.5
2	板料(窄)	208.73	391.41	46.7
3	板料(宽)	448.27	1013.15	55.8

[1]	汪维, 阮雅端, 顾鹏, 陈启美. 基于融合注意力机制DAUNet的最大裂缝宽度计算[J]. 上海交通大学学报, 2025, 59(12): 1866-1877.
[2]	毛彦嵋, 李华锋, 张亚飞. 面向跨区域场景的无监督域自适应行人重识别[J]. 上海交通大学学报, 2025, 59(12): 1878-1890.
[3]	胡丹, 崔喻婷, 周海河, 刘英莉. 改进蜣螂算法优化工艺参数[J]. 上海交通大学学报, 2025, 59(12): 1901-1915.
[4]	詹泽辉, 钟铭恩, 袁彬淦, 谭佳威, 范康. 随机平视摄像条件下的路边车辆违停检测[J]. 上海交通大学学报, 2025, 59(10): 1568-1580.
[5]	张志远, 胡冀苏, 张跃跃, 钱旭升, 周志勇, 戴亚康. 注意力引导多任务学习的前列腺癌盆腔淋巴结转移预测[J]. 上海交通大学学报, 2025, 59(8): 1216-1224.
[6]	纪冕, 林艳萍, 王冬梅, 陈立, 马昕. 足部特征点准确定位及形态参数自动测量方法[J]. 上海交通大学学报, 2025, 59(5): 703-710.
[7]	王鸿鑫, 徐德刚, 周楷文, 李林文, 温新. 数据驱动的流场稀疏数据建模[J]. 上海交通大学学报, 2025, 59(5): 684-690.
[8]	包家汉, 孙德尚, 黄建中, 胡政. 基于自适应阈值的型钢精确角点FAST检测算法[J]. 上海交通大学学报, 2025, 59(5): 691-702.
[9]	张澳圆, 胡小锋, 张亚辉. 多场景多目标动态变化下船舶小组立装焊重调度[J]. 上海交通大学学报, 2025, 59(4): 476-488.
[10]	刘建欣, 潘如如, 周建. 基于欠完备字典重构的无监督织物疵点检测方法[J]. 上海交通大学学报, 2025, 59(2): 283-292.
[11]	王可, 刘奕阳, 杨杰, 鲁爱国, 李哲, 徐明亮. 基于自适应特征增强和融合的舰载机着舰拉制状态识别[J]. 上海交通大学学报, 2025, 59(2): 274-282.
[12]	章涛, 张雪瑞, 陈勇, 钟科林, 罗其俊. 面向民机可视导航的场面多尺度目标检测[J]. 上海交通大学学报, 2024, 58(11): 1816-1825.
[13]	牛国臣, 孙翔宇, 苑峥岩. 基于双流特征提取的车路协同感知方法[J]. 上海交通大学学报, 2024, 58(11): 1826-1834.
[14]	王宝坤, 王如路, 陈锦剑, 潘越, 王鲁杰. 基于深度学习的盾构隧道表观病害自动检测方法[J]. 上海交通大学学报, 2024, 58(11): 1716-1723.
[15]	秦菁, 文渊博, 高涛, 刘瑶. 面向多天气退化图像恢复的自注意力扩散模型[J]. 上海交通大学学报, 2024, 58(10): 1606-1617.