一个实用的矩形件优化排样启发式算法

A Practical Heuristic Algorithm for Rectangle Parts Packing Problem

仔细研究了传统矩形件优化排样近似算法及存在的主要问题,提出一个新的启发式算法。该算法根据最后板材的实际排放情况,采用了多种排放策略,克服了原算法的在零件数较少时的缺陷。在此基础上用Visual C++ 6.0开发了一个实用的矩形件计算机辅助排样系统。实际应用表明,新算法可获得比原近似算法更好的优化排样结果。笔者给出了算法的具体实现方法和步骤。

Based on the study of the traditional approximation algorithm for the rectangle packing problem and its main shortcoming, an improved heuristic algorithm in which different strategy is taken according to the practical layout condition of the last stock is proposed, so the defect of the former algorithm when the parts number is not large enough to fill the last stockplate is limited, and with this new algorithm a computer aided packing system for rectangle parts is developed on Visual C++ 6.0. It is proved that a more satisfying optimized packing result can be achieved. The exact steps to realize the algorithm and system are descried in detail.