论文部分内容阅读
排料问题，就是在给定的一个布局空间内，按最优化组合的方式将待排物体按照一定的约束条件合理地摆放在布局空间中，并使排料利用率达到最高。排料问题在工业生产中应用十分广泛，排料的构思是否合理直接影响到耗料的多少，提高排料利用率是降低生产成本、提高产品竞争力的主要手段之一。因此，解决排料问题具有深远的理论意义及实际意义。前人已经证明自动排料问题属于NP完全问题，而紧密合理的排料在生产中可以大大提高生产效率，节约成本，因而具有重要的研究价值和实用价值。不规则形状物体的自动排料问题，一直受到广泛的重视和研究，研究方法涉及了计算几何学、人工智能、组合优化等各种理论。 由于二维不规则形状的布局问题属于NP难度问题，因此解决该问题的关键是：解决计算的可解性(capability)和难解性(intractability)。所以计算机鞋片自动排料系统首先要解决计算量的问题。要努力减少计算量，提高运算速度；其次要提高利用率，使计算机排料所得到的利用率接近或超过人工水平。利用率和运算时间是计算机排料自动化的一对重要参数，二者是对立统一的存在。本文在基于人工智能的启发式搜索方法的基础上提出了一种计算机自动鞋片排料算法。详细叙述了系统的工作过程以及为之建立的数据结构，最后还对系统的进一步完善提出了意见。该算法通过生成轮廓多边形，根据材料利用率这个启发信息来确定一种待排鞋片选取规則和定位规则，完成鞋片在矩形料片上的自动排放。由于考虑到该算法在制鞋工业中的实际应用，进一步扩充至在不规则料片上的自动排放。该算法考虑到人工排料时的经验信息，通过大小鞋片的嵌套处理提高了材料利用率；同时采用启发式搜索的策略，可以很快确定下一个待排鞋片及可能发生碰撞的合成轮廓多边形，先大步长移动，然后微调，从而减少大量的盲目检测，提高了排料的精度。 本算法不仅适用于鞋片的排料问题，还适用于其他各种套料问题，具有较强的通用性。最后，我们对温州申普信息技术有限公司提供的原始数据进行了排料，结果表明该算法在材料利用率和运算速度上都取得了比较好的效果。