Tabu search algorithm combined with global perturbation for packing arbitrary sized circles into a circular container  

作　　者：HUANG WenQi FU ZhangHua XU RuChu 

机构地区：[1]School of Computer Science and Technology, Huazhong University of Science and Technology

出　　处：《Science China(Information Sciences)》2013年第9期136-149,共14页中国科学（信息科学）（英文版）

摘　　要：The arbitrary sized circle packing problem （ACP） is concerned about how to pack a number of arbitrary sized circles into a smallest possible circular container without overlapping. As a classical NP-hard problem, ACP is theoretically important and is often encountered in practical applications. Based on the already existing Quasi-physical method, this paper proposes a hybrid algorithm named GP-TS which combines tabu search with global perturbation to solve the two-dimensional ACP. The Quasi-physical method is a continuous optimization method which is used to obtain a local optimal configuration from any initial configuration. The tabu search procedure iteratively updates the incumbent configuration with its best neighboring configuration according to some forbidden rule and aspiration criterion. If the configuration obtained by the tabu search procedure does not satisfy the constraints, the global perturbation operator is subsequently applied in order that the search jumps out of the current local optimum without destroying the incumbent configuration too much. After that, the tabu search procedure is launched again. GP-TS is performed by repeating this process until the stop criterion is met. Computational experiments based on 3 sets of representative instances show that GP-TS can improve many best known results within reasonable time.The arbitrary sized circle packing problem （ACP） is concerned about how to pack a number of arbitrary sized circles into a smallest possible circular container without overlapping. As a classical NP-hard problem, ACP is theoretically important and is often encountered in practical applications. Based on the already existing Quasi-physical method, this paper proposes a hybrid algorithm named GP-TS which combines tabu search with global perturbation to solve the two-dimensional ACP. The Quasi-physical method is a continuous optimization method which is used to obtain a local optimal configuration from any initial configuration. The tabu search procedure iteratively updates the incumbent configuration with its best neighboring configuration according to some forbidden rule and aspiration criterion. If the configuration obtained by the tabu search procedure does not satisfy the constraints, the global perturbation operator is subsequently applied in order that the search jumps out of the current local optimum without destroying the incumbent configuration too much. After that, the tabu search procedure is launched again. GP-TS is performed by repeating this process until the stop criterion is met. Computational experiments based on 3 sets of representative instances show that GP-TS can improve many best known results within reasonable time.

关 键 词：PACKING tabu search global perturbation quasi-physical quasi-human 

分 类 号：TB48[一般工业技术—包装工程] TP391.3[自动化与计算机技术—计算机应用技术]