实际生产中而临着越来越多的组合优化问题,其中不少属于NP-hard问题。遗憾的是,由于NP-hard问题的客观难度,迄今为止尚未设计出能在多项式计算复杂度内找出其全局最优解的求解算法。事实上,很可能不存在这样的算法,除非P=NP。因此,现有的NP-hard问题求解算法大多为基于问题特征而设计的启发式算法。启发式算法不一定能找到问题的全局最优解,但往往能在可接受的计算时问内找到满足实际要求的近似解,从而成为现实求解NP-hard问题的主流途径。论文以二维不等圆Packing问题为例,研究NP-hard问题的现实求解途径。二维不等圆Packing问题是一个典型的NP-hard问题,主要考察如何将若干个半径任意给定的圆形物体互不嵌入地置入一个特定形状的大容器内,使得大容器的尺寸尽可能地小。针对该问题的连续特征和组合特征,分别设计了有针对性的连续优化方法和组合优化方法,并将两者相结合,得到了求解不等圆Packing问题的带全局变换禁忌搜索算法GP-TS。GP-TS的算法流程为：(1)将所有待放置圆形物体随机地撒入大容器内,得到一个初始格局,并采用连续优化方法收敛至局部最优格局；(2)执行禁忌搜索过程,在禁忌规则的约束下将当前格局迭代地替换为其邻域中的最优格局；(3)若当前格局不满足无嵌入约束条件,则采用专门设计的格局变换算子在不完全破坏当前格局结构的前提下将其变换为新格局；(4)再次调用禁忌搜索过程对变换所得格局进行带禁忌约束的邻域搜索；(5)基于模拟退火思想设计接收准则,用于决定是否接收禁忌搜索所得新格局；(6)迭代地执行步骤3-5,直至找到满足约束条件的合法格局或某项强制停机条件成立为止。GP-TS原创性地将求解过程划分为连续优化、禁忌搜索(特殊的邻域搜索)和全局优化三个阶段,并根据各阶段的特征分别设计有针对性的搜索策略。与其不同,现有的不等圆Packing问题求解算法要么根据一定的构造规则将各待放置物体逐个置入大容器内合适的位置,要么只将求解过程划分连续优化和全局优化两个阶段,其算法框架与GP-TS均大不相同。分析表明,GP-TS可在连续优化、邻域搜索和全局搜索之间达成较为合理的平衡,是一个高效而稳定的不等圆Packing问题求解算法。论文详细介绍了连续优化方法、禁忌搜索过程、格局变换算子、接收准则以及停机条件等GP-TS实现的关键要素,并介绍了几个辅助性方法,用于提高GP-TS的效率。基于4组共66个国际标准算例的实验结果表明,GP-TS可改进43个算例的此前最优解,并与19个算例的此前最优解持平,GP-TS只在4个算例上所得解稍差于此前最优解。不仅如此,GP-TS在大多数算例上的计算时间大大少于此前表现最佳算法的计算时间。尽管基于不同计算平台的计算时间仅可作为辅助的评价指标,但解的优度和计算时间两方而的综合对比仍可清晰地表明GP-TS是极富竞争力的不等圆Packing问题求解算法。论文最后还总结了三条求解NP-hard问题的一般原则。由于NP-hard问题本质相通,相信这些‘般原则以及本文所设计算法GP-TS可对求解其它NP-hard问题提供有益的借鉴作用。