高级检索

    基于禁忌搜索的启发式算法求解圆形packing问题

    A Heuristic Algorithm Based on Tabu Search for the Disks Packing Problem

    • 摘要: 求解具有NP难度的圆形 packing问题具有很高的理论与实用价值 现提出一个有效的启发式方法 ,求解了货运中常遇到的矩形区域内的不等圆 packing问题 此算法首先将圆按给定的优先级分组 ,然后逐组地用拟物拟人法放置圆 ,并且在整个过程中利用了禁忌搜索法的思想 ,通过禁止重复前面已做的工作 ,使搜索能有效地逃离局部极小值的陷阱 ,提高了搜索效率 实验结果表明 ,提出的算法是一个高效的实用求解算法

       

      Abstract: 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

       

    /

    返回文章
    返回