题目 基于禁忌搜索的启发式算法求解圆形packing问题
A Heuristic Algorithm Based on Tabu Search for the Disks Packing Problem
作者 康 雁1 黄文奇2
KANG Yan1 and HUANG Wen-Qi2
单位 (云南大学软件学院 昆明 650091) 2(华中科技大学计算机科学与技术学院 武汉 430074) (kangyan1972@sina.com.cn
1(School of Software, Yunnan University, Kunming 650091) 2(School of Computer Science & Technology, Huazhong University of Science and Technology, Wuhan 430074)
关键词 圆形packing问题；禁忌搜索法；启发式算法；NP难问题
disks packing problem; tabu search method; heuristic algorithm; NP-hard problem
摘要 求解具有NP难度的圆形packing问题具有很高的理论与实用价值.现提出一个有效的启发式方法，求解了货运中常遇到的矩形区域内的不等圆packing问题.此算法首先将圆按给定的优先级分组，然后逐组地用拟物拟人法放置圆，并且在整个过程中利用了禁忌搜索法的思想，通过禁止重复前面已做的工作，使搜索能有效地逃离局部极小值的陷阱，提高了搜索效率.实验结果表明，提出的算法是一个高效的实用求解算法.
The disks packing problem, one of the NP hard problems, is of high theoretical and practical value. To solve the disks packing problem that is encountered finding a good arrangement of multiple different-sized disks in a larger rectangle and emerges in the field of transportation of freight, an effective algorithm is presented. This algorithm divides all the disks into several groups according to given priorities, and then uses the quasi-physical and quasi-human algorithm to put these disks into the rectangle without overlapping. During the packing procedure, the tabu search method is used to forbid the search doing repeated work and improve the performance of the search by helping the search escape from local minima. The effectiveness of this algorithm is demonstrated through a number of typical computational experiments.
