摘要
以卫星舱中承载板上物件的三维布局为背景,研究一类带动不平衡约束的圆柱体形和长方体形待布物的混合布局问题.采用两阶段法进行求解,首先引入基面分配策略,将待布物分配到承载板上、下基面上;然后采用禁忌搜索算法对每一基面上的待布物进行布局优化:对传统禁忌搜索算法中的邻域格局提出启发式的产生策略,并对禁忌对象和格局接受原则进行有效改进,将改进的禁忌搜索算法与局部搜索的梯度下降法相结合,提出一种启发式的布局方法——基于梯度下降的禁忌搜索算法.最后通过算例验证了文中算法的高效性.
Under the background of the three-dimensional layout design of objects on the loading plate in the satellite module,a hybrid layout problem of cylinders and cuboids with dynamic unbalance constraints is studied.The two-stage method is introduced to solve this problem.At first,based on base-plane allocation criterion,all objects are allocated to up and down base-planes of the loading plate.Then the tabu search method is used to optimize the layout of objects on each base-plane.By putting forward heuristic generating strategies of the neighborhood configuration,and improving taboo object and the configuration acceptance criterion in the general tabu search algorithm,a heuristic algorithm which combines the improved tabu search algorithm with the local search based on gradient descent method is put forward.Experimental results on two instances from the literature show that the proposed algorithm is quite effective.
出处
《计算机辅助设计与图形学学报》
EI
CSCD
北大核心
2014年第8期1232-1239,共8页
Journal of Computer-Aided Design & Computer Graphics
基金
国家自然科学基金(61373016
61103235)
江苏省"六大人才高峰"项目(DZXX-041)
南京信息工程大学教改课题(N1885013209)
南京信息工程大学实验室开放项目(N1081005141)
关键词
动不平衡约束
装填问题
禁忌搜索
启发式算法
dynamic unbalance constraints
packing problem
tabu search
heuristic algorithm
