一种求解矩形块装填问题的拟人算法

摘要

在货物装载、木材下料、超大规模集成电路 (VLSI)设计等工作中提出了矩形块装填与切割问题,对这一问题,国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法.本文利用人类的智慧和他们上万年以来形成的经验,提出了一种求解矩形块装填问题的拟人算法.该算法使用了两个主要的思想策略,即矩形块选择策略和矩形块放置策略.用本文提出的算法,对21个测试算例进行了实算测试,测试结果表明:算法所得装填结果的优度高,计算时间短.对这21个测试算例,用本文算法计算,得到了其中16个算例的最优解,而计算时间都在2秒以内.进一步的测试表明,本文提出的算法对求解矩形块装填问题十分有效.