资源描述：
《二维不规则形状自动排料算法的研究及实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第]Z卷第7期计算机辅助设计与图形学学报Vol.]Z9No.7Z000年7月JOURNALOFCOMPUERAIDEDDESIGNANDCOMPUERGRAP~ICSJuly9Z000===================================================================二维不规则形状自动排料算法的研究与实现刘嘉敏张胜男黄有群(沈阳工业大学信息科学与工程学院沈阳]]00Z3D摘要针对二维不规则形状自动排料问题9给出了解决自动排料的求解思路9并对自动排料的主要算法作
2、出了研究和改进9以便更好地提高算法效率及可靠性.关键词自动排料9不规则形状9启发式中图法分类号P39].7ZResearchandImplementationoftwoDimensionalIrregularAuto-NestingAlgorithmLIUJia-MinZ~ANGSheng-Nan~UANGYou-Oun(17f07?Cl07SCl67C6C7CE7gl7667l7gC0ll6g69Sh67}C7gP0l}6Ch7lC]7lU67Sl}9Sh67}C7g]]00Z3DAbstractAsolu
3、tionoftwodimensionalirregularauto-nestingisstudiedandimprovedinor-dertoinreasetheeffiienyandreliabilityofalgorithm.Keywordsauto-nesting9irregularshape9heuristis对不规则形状零件的排料是不适用的.引言不规则形状零件排料的困难9除了对形状本身的描述问题之外9还来自对零件间的靠接关系的描排料问题是寻找平面最优布局的优化问题9即述控制和评价方法等问题.对于不规
4、则形状零件排将一系列二维不规则形状的零件P合料问题使用计算机进行求解9经历了从模仿手工铺]9PZ99P7理地排放在原料P中9使原料的利用率(零件面积排模板9依赖人的视觉的交互排料到先将若干零件原料面积D最高9并要满足下列约束条件:拼在一个矩形中9再借用矩形排料思想的两步法9最后到对多边形直接排料的研究]9398]DPl9P互不重叠l9]9Z997..后两种方法属ZDPl必放在P内l]9Z997.于自动排料的范畴9由于不能给出和遍历全部状态93D满足一定工艺要求.目前对多边形直接排料的求解方法比较认同的是采排料
5、问题的上述一般表述9可以归结为数学规用启发式搜索方法].划问题9也可以归结为以零件排放状态为结点以废零件排料布局的优劣9直接与产品成本及企业料增加为权值的带权有向图中的最短路径问题经济效益有关.尤其是对不规则形状排料算法的研.但是9由于约束条件很难用可操作的数学公式表达9究9具有一定的学术理论价值9该问题日益引起应用使得排料问题的求解不能套用现有的数学规划求解部门和学术界的兴趣.目前国内外已有一些关于不算法.另外9图论中最短路径问题的已有算法9只对规则形状排料的软件9它们多半提供交互排料和自图的结构固定且清晰
6、一个状态结点的后继结点个动排料两种功能9但是从排料效果上看9自动排料并数有限的情况有效9如对矩形零件的排料适用6未形成相对人工排料的明显优势9这说明对不规则9而原稿收到日期:]999-04-08修改稿收到日期:]999-]]-Z.刘嘉敏9女9]964年生9硕士9主要研究领域为计算机辅助设计计算机图形学多媒体技术.张胜男9女9]970年生9硕士9主要研究领域为计算机辅助设计计算机图形学多媒体技术.黄有群9男9]94年生9教授9主要研究领域为计算机辅助设计计算机图形学多媒体技术.7期刘嘉敏等:二维不规则形状自动排
7、料算法的研究与实现89形状自动排料算法进一步深入研究是必要的O笔者佳位置位于临界多边形上O在开发一个排料软件过程中,对不规则形状自动排料算法作了一定的研究,并作出一些改进OBBBBAB2自动排料过程描述BBBB临界多边形零件排料的过程可以视为在原料上零件排放状态的变化过程O启发式搜索的思路在于不用遍历某图1临界多边形的形成一结点的所有可能后继状态,而是运用人的直觉经临界多边形法虽然确立了求取排放B相对A验和有关知识,直接6构造可能最佳的后继状态,并的最佳位置的基本原则,但A,B中只要有一个是凹在其中选最优的O
8、这些经验和有关知识可以归结为:多边形,在绕行时就可能出现A,B重叠的现象,因1)新排零件应与已排零件或原料边界保持接此,每移动一步都要作重叠判断O同时,这种事后的触且不重叠O重叠判断给移动的步长选取带来了盲目性,且步长2)新零件的最优位置与其方向和相对已排零不宜过大O对无需重叠判断的情况两个凸多边形),件的位置有关,最佳方向和相对位置的确定,缺乏可临界多边形法的算法复杂度只是OM+N),其中借用的先
